최근 수정 시각 : 2024-11-04 22:00:06

제2종 스털링 수

이산수학
Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" 		이론
<colbgcolor=#3CC> 기본 대상 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합 경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타 P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설
관련 문서 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 }}}}}}}}}


1. 개요2. 정의3. 성질
3.1. 점화식3.2. 제1종 스털링 수와의 관계3.3. 일반항3.4. 지수생성함수
4. 관련 문서

Stirling numbers of the second kind

1. 개요

[math(x^n)]을 하강 계승 [math(x^{\underline k})][1]의 급수로 나타낼 때 각 항에 곱해지는 계수로 정의되며, [math(\begin{Bmatrix} n \\ k \end{Bmatrix})] 혹은 [math(S(n,\,k))]로 나타낸다. 1730년에 제임스 스털링이 도입하였다. 이 수의 합이 벨 수와 관련이 있고, 공교롭게도 벨 수와 똑같은 기호를 쓰는 베르누이 수와도 연관[2]이 있다. [math(0 \le k \le n \le 10)] 범위에서[3][4] [math(\begin{Bmatrix} n \\ k \end{Bmatrix})] 값은 다음과 같다.
[math(n \Big\backslash k)] [math(0)] [math(1)] [math(2)] [math(3)] [math(4)] [math(5)] [math(6)] [math(7)] [math(8)] [math(9)] [math(10)]
[math(0)] [math(1)] [math(0)]
[math(1)] [math(0)] [math(1)] [math(0)]
[math(2)] [math(1)] [math(1)] [math(0)]
[math(3)] [math(1)] [math(3)] [math(1)] [math(0)]
[math(4)] [math(1)] [math(7)] [math(6)] [math(1)] [math(0)]
[math(5)] [math(1)] [math(15)] [math(25)] [math(10)] [math(1)] [math(0)]
[math(6)] [math(1)] [math(31)] [math(90)] [math(65)] [math(15)] [math(1)] [math(0)]
[math(7)] [math(1)] [math(63)] [math(301)] [math(350)] [math(140)] [math(21)] [math(1)] [math(0)]
[math(8)] [math(1)] [math(127)] [math(966)] [math(1701)] [math(1050)] [math(266)] [math(28)] [math(1)] [math(0)]
[math(9)] [math(1)] [math(255)] [math(3025)] [math(7770)] [math(6951)] [math(2646)] [math(462)] [math(36)] [math(1)] [math(0)]
[math(10)] [math(1)] [math(511)] [math(9330)] [math(34105)] [math(42525)] [math(22827)] [math(5880)] [math(750)] [math(45)] [math(1)]

2. 정의

[math(\displaystyle x^n = \sum_{k=0}^n S(n,\,k)x^{\underline k})]
부호 없는 제1종 스털링 수와 비슷하게 [math(S(n,\,k))]는 종종 [math(\begin{Bmatrix} n \\ k \end{Bmatrix})]로 표기되곤 한다. [math(x^{\underline k} = {}_x{\rm P}_k = k! \dbinom xk)]의 관계에 있으므로 위 식은 다음과 같이 나타낼 수도 있다.
[math(\displaystyle x^n = \sum_{k=0}^n k! S(n,\,k) \binom xk)]
이를테면 [math(n=3)]일 때, [math(x^{\underline 0} = 1)], [math(x^{\underline 1} = x)], [math(x^{\underline 2} = x(x-1) = x^2 - x)], [math(x^{\underline 3} = x(x-1)(x-2) = x^3 - 3x^2 + 2x)]이므로
[math(x^3 = 0 \cdot 1 + 1 \cdot x + 3 \cdot (x^2 - x) + 1 \cdot \left( x^3 - 3x^2 + 2x \right) )]
로부터 [math(\begin{Bmatrix} 3 \\ 0 \end{Bmatrix} = 0)], [math(\begin{Bmatrix} 3 \\ 1 \end{Bmatrix} = 1)], [math(\begin{Bmatrix} 3 \\ 2 \end{Bmatrix} = 3)], [math(\begin{Bmatrix} 3 \\ 3 \end{Bmatrix} = 1)]이다.

제1종 스털링 수와 마찬가지로 조합론을 이용해서도 정의할 수 있는데, 원소의 개수가 [math(n)]인 집합을 구분되지 않는 [math(k)]개의 부분 집합으로 분할하는 방법의 수가 된다. 예를 들어 어느 대학교에서 MT를 [math(n)]명이 갔는데 방을 [math(k)]개 잡았고 각 방에는 적어도 [math(1)]명이 들어가야 한다고 할 때 가능한 경우의 수가 [math(S (n,\,k))]이다.
각 정의에 입각해서 점화식을 써보면 두 경우 모두 완전히 같은 식이 유도가 되어 동치임을 알 수 있다.

참고로 제1종 스털링 수의 기호는 [math(S)]를 소문자로 바꾸어 쓴 [math(s(n,\,k))]이다.

3. 성질

3.1. 점화식

[math(\begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix} = \begin{Bmatrix} n \\ k \end{Bmatrix} + (k+1) \begin{Bmatrix} n \\ k+1 \end{Bmatrix})]
급수를 이용한 증명에서는 하강 계승을 변형시켜서 유도해줄 수 있다.
[math(\displaystyle \begin{aligned} x^{n+1} &= \sum_{k=0}^{n+1} \begin{Bmatrix} n+1 \\ k \end{Bmatrix} x^{\underline k} \\ &= x \cdot x^n = x \sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} x^{\underline k} = \sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} x \cdot x^{\underline k} \end{aligned})]
첫 번째 식에서 [math(\begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix})]는 [math(x^{\underline{k+1}})]의 계수이다. 따라서 [math(x \cdot x^n)]에 관한 식에서는 [math(x \cdot x^{\underline k})]를 변형해서 [math(x^{\underline{k+1}})]이 나오도록 하면 된다.
[math(x^{\underline k} = \dfrac{x!}{(x-k)!} = \dfrac{x!}{(x-k-1)!(x-k)} = \dfrac{x^{\underline{k+1}}}{x-k})]
이므로
[math(x \cdot x^{\underline k} = x^{\underline{k+1}} + k \cdot x^{\underline k})]
이다. 한편, 이 관계식의 [math(k)]에 [math((k+1))]을 대입한
[math(x \cdot x^{\underline{k+1}} = x^{\underline{k+2}} + (k+1) \cdot x^{\underline{k+1}})]
에서도 [math(x^{\underline{k+1}})]항이 얻어지므로 이를 [math(x \cdot x^n)]에 관한 등식에 대입한다.
[math(\begin{aligned} \begin{Bmatrix} n \\ k \end{Bmatrix} x \cdot x^{\underline k} + \begin{Bmatrix} n \\ k+1 \end{Bmatrix} x \cdot x^{\underline{k+1}} &= \begin{Bmatrix} n \\ k \end{Bmatrix} \left( x^{\underline{k+1}} + k \cdot x^{\underline k} \right) + \begin{Bmatrix} n \\ k+1 \end{Bmatrix} \left\{ x^{\underline{k+2}} + (k+1) \cdot x^{\underline{k+1}} \right\} \\ &= \begin{Bmatrix} n \\ k \end{Bmatrix} k \cdot x^{\underline k} + \left[\begin{Bmatrix} n \\ k \end{Bmatrix} + (k+1) \begin{Bmatrix} n \\ k+1 \end{Bmatrix} \right] x^{\underline{k+1}} + \begin{Bmatrix} n \\ k+1 \end{Bmatrix} x^{\underline{k+2}} \end{aligned})]
대괄호 부분이 [math(x^{n+1})]의 전개식에서 [math(\begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix})]에 해당한다.

조합론의 경우는 훨씬 더 간단하게 증명이 된다. 위의 MT를 예시로 들면, [math((n+1))]번째 사람이 추가로 MT에 참가해서 방을 [math((k+1))]개로 늘린다고 할 때, 독방을 쓰는 경우와 다른 사람이 들어가 있는 방에 포함되는 경우로 나눌 수 있다. 독방을 쓴다고 하면 [math(n)]명이었을 때의 [math(k)]개 방으로 나눈 경우 [math(\begin{Bmatrix} n \\ k \end{Bmatrix})]가 그대로 쓰인다. 한편, 다른 사람이 있는 방에 들어간다고 하면 [math(n)]명이었을 때 [math((k+1))]개 방으로 나눈 경우에서 각 방에 들어가는 모든 경우가 포함되므로 [math((k+1) \begin{Bmatrix} n \\ k+1 \end{Bmatrix})]가 된다. 정리하면 위의 식이 얻어진다.

3.2. 제1종 스털링 수와의 관계

  • [math(\begin{Bmatrix} n \\ k \end{Bmatrix} = \begin{bmatrix} -k \\ -n \end{bmatrix})]

    두 성분을 교환하고 각 성분의 부호를 모두 바꿔주면 스털링 수의 종류가 바뀐다. 위 관계는 점화식을 이용해서 간단하게 증명이 가능하다. 우변의 부호 없는 제1종 스털링 수에 점화식을 적용하면
    [math(\begin{bmatrix} -k \\ -n \end{bmatrix} = \begin{bmatrix} -k-1 \\ -n-1 \end{bmatrix} - (k+1) \begin{bmatrix} -k-1 \\ -n \end{bmatrix})]

    이 되는데, 우변의 제2항을 이항하면
    [math(\begin{bmatrix} -k-1 \\ -n-1 \end{bmatrix} = \begin{bmatrix} -k \\ -n \end{bmatrix} + (k+1) \begin{bmatrix} -k-1 \\ -n \end{bmatrix})]

    이제 각 성분을 교환하고 [math(-1)]을 곱해주면 제2종 스털링 수의 점화식 꼴이 된다.
    [math(\begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix} = \begin{Bmatrix} n \\ k \end{Bmatrix} + (k+1) \begin{Bmatrix} n \\ k+1 \end{Bmatrix})]
  • [math(\displaystyle \sum_{r=k}^n s(n,\,r) S(r,\,k) = \sum_{r=k}^n S(n,\,r) s(r,\,k) = \delta_{n,\,k})]

    [math(\delta_{n,\,k})]는 크로네커 델타이다. 두 식 모두 라흐 수의 정의처럼 각 스털링 수의 정의를 연달아 적용함으로써 도출된다.
    [math(\displaystyle \begin{aligned} x^{\underline n} &= \sum_{r=0}^n s(n,\,r) x^r = \sum_{r=0}^n s(n,\,r) \sum_{k=0}^r S(r,\,k) x^{\underline k} = \sum_{r=0}^n \sum_{k=0}^r s(n,\,r) S(r,\,k) x^{\underline k} \\ &= \sum_{k=0}^n \sum_{r=0}^n s(n,\,r) S(r,\,k) x^{\underline k} = \sum_{k=0}^n \left( \sum_{r=0}^n s(n,\,r) S(r,\,k) \right) x^{\underline k} \end{aligned} \\ \therefore \sum_{r=0}^n s(n,\,r) S(r,\,k) = \sum_{r=k}^n s(n,\,r) S(r,\,k) = \delta_{n,\,k} \\ \begin{aligned} x^n &= \sum_{r=0}^n S(n,\,r) x^{\underline r} = \sum_{r=0}^n S(n,\,r) \sum_{k=0}^r s(r,\,k) x^k = \sum_{r=0}^n \sum_{k=0}^r S(n,\,r) s(r,\,k) x^k \\ &= \sum_{k=0}^n \sum_{r=0}^n S(n,\,r) s(r,\,k) x^k = \sum_{k=0}^n \left( \sum_{r=0}^n S(n,\,r) s(r,\,k) \right) x^k \end{aligned} \\ \therefore \sum_{r=0}^n S(n,\,r) s(r,\,k) = \sum_{r=k}^n S(n,\,r) s(r,\,k) = \delta_{n,\,k})]

    부호 없는 스털링 수, 그러니까 [math(s(n,\,k) = (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix})]표기를 이용하면 다음과 같이 된다.
    [math(\displaystyle \begin{aligned} \sum_{r=k}^n (-1)^r \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix} &= (-1)^n \delta_{n,\,k} \\ \sum_{r=k}^n (-1)^r \begin{Bmatrix} n \\ r \end{Bmatrix} \begin{bmatrix} r \\ k \end{bmatrix} &= (-1)^k \delta_{n,\,k} \end{aligned})]

    두 식에서 우변의 [math(-1)]의 지수가 다르지만 사실 둘 다 [math((-1)^n)]을 쓰든 [math((-1)^k)]를 쓰든 상관 없다. 어차피 부호가 제 역할을 하는 경우는 [math(\delta_{n,\,k} = 1)], 즉 [math(n=k)]일 때 뿐이며, 좌변에서 [math(n=k)]란 곧 [math((-1)^k \begin{bmatrix} k \\ k \end{bmatrix} \begin{Bmatrix} k \\ k \end{Bmatrix} = (-1)^k = (-1)^n)]을 의미하기 때문이다.

3.3. 일반항

[math(\displaystyle S(n,\,k) = \frac 1{k!} \sum_{r=0}^k \binom kr (-1)^r (k-r)^n)]
조합론을 이용한 정의에서, [math(k)]개의 각 부분 집합에는 공집합이 없어야하는 것이 포인트이다. 즉, 공집합을 허용하도록 분할하는 모든 경우의 수에서 공집합이 적어도 하나 있는 모든 경우를 빼면 [math(S(n,\,k))]가 얻어진다.
MT를 예로, 먼저 빈 방이 생기는 걸 허용하여 [math(n)]명을 [math(k)]개의 호실에 배정하는 경우의 수는 [math(n)]명이 동등한 [math(k)]개의 선택권을 갖는 경우와 같으므로 [math(k^n)]가지가 된다. 다음으로 빈 방이 [math(r)]개만 생기도록 하는 경우의 수는, ([math(k)]개의 방에서 [math(r)]개를 임의로 골라낸 경우의 수)[math(\times(k-r))]개의 방에 차례로 배정하는 경우의 수)이므로 [math(\dbinom kr (k-r)^n)]이 된다. 이제, 포함·배제의 원리에 따라 빈 방 없이 배정하는 경우를 구하면
[math(\displaystyle k^n - \left[ \binom k1 (k-1)^n - \left\{ \binom k2 (k-2)^n - \left( \binom k3 (k-3)^n -\cdots\cdots \right) \right\} \right] \\ = k^n - \binom k1 (k-1)^n + \binom k2 (k-2)^n - \binom k3 (k-3)^n +\cdots\cdots + (-1)^k \binom kk (k-k)^n \\ = \sum_{r=0}^k (-1)^r \binom kr (k-r)^n)]
위 식은 각 방에 차례로 배정하는 경우(즉, 각 부분집합이 구분되는 경우)와 같으므로 이를 [math(k!)]로 나눠서 구분되지 않는 부분 집합으로 만들어주면 된다. 즉
[math(\displaystyle S(n,\,k) = \frac 1{k!} \sum_{r=0}^k (-1)^r \binom kr (k-r)^n)]
가 된다. [math(\dbinom kr = \dbinom k{k-r})]이라는 성질을 이용하여
[math(\displaystyle \begin{aligned} S(n,\,k) &= \frac 1{k!} \sum_{r=0}^k (-1)^{k-r} \binom kr r^n \\ &= \frac{(-1)^k }{k!} \sum_{r=0}^k (-1)^r \binom kr r^n \end{aligned})]
로 나타내기도 한다. 위 식과 제1종 스털링 수와의 관계로부터 중요한 특징이 유도되는데, 바로 [math(\boldsymbol n)]을 음의 정수로까지 확장시킬 수 있다는 것이다.[5] 베르누이 수열 중 [math(B_n ^-)]의 일반항을 구할 때 위 식이 쓰이기도 한다.

재미있게도 [math(\begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix})]을 일반항으로 나타내면
[math(\displaystyle \begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix} = \frac{(-1)^{k+1}}{(k+1)!} \sum_{r=0}^{k+1} (-1)^r \binom{k+1}r r^{n+1})]
이 되고 [math(r=0)]인 항은 생략할 수 있으므로 [math(r=1)]부터 더해주고 식을 변형해주면 다음과 같이 된다.
[math(\displaystyle = \frac{(-1)^{k+1}}{k!} \sum_{r=1}^{k+1} \frac{(-1)^r}{k+1} \frac{(k+1)!}{r!(k-r+1)!} r^{n+1} = \frac{(-1)^{k+1}}{k!} \sum_{r=1}^{k+1} (-1)^r \frac{k!}{(r-1)!(k-r+1)!} r^n \\ = \frac{(-1)^{k+1}}{k!} \sum_{r=1}^{k+1} (-1)^r \binom k{r-1} r^n = \frac{(-1)^{k+1}}{k!} \sum_{r=0}^k (-1)^{r+1} \binom kr (r+1)^n \\ = \frac{(-1)^k}{k!} \sum_{r=0}^k (-1)^r \binom kr (r+1)^n)]
즉, [math(n)]과 [math(k)]가 모두 [math(1)]씩 증가해도 일반항에서 [math(r^n)]항만 변할 뿐이다. 참고로 [math(\displaystyle k! \begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix} = (-1)^k \sum_{r=0}^k (-1)^r \binom kr (r+1)^n)]을 보르피츠퀴 수(Worpitzky number) [math(W_{n,\,k})]라고 하며, 베르누이 수열 중 [math(B_n ^+)]의 일반항을 구할 때 쓰인다.

3.4. 지수생성함수

[math(\displaystyle \frac{\left( e^x -1 \right)^k}{k!} = \sum_{n=0}^\infty \begin{Bmatrix} n \\ k \end{Bmatrix} \frac{x^n}{n!})]
제2종 스털링 수 특성상 [math(n<k)]이면 [math(\begin{Bmatrix} n \\ k \end{Bmatrix} = 0)]이기 때문에 일반적으론 다음과 같은 축약식으로 나타낸다.
[math(\displaystyle \frac{\left( e^x -1 \right)^k}{k!} = \sum_{n=k}^\infty \begin{Bmatrix} n \\ k \end{Bmatrix} \frac{x^n}{n!})]
좌변의 식을 변형해서 정리해주면 제2종 스털링 수의 일반항이 튀어나오면서 간단하게 증명이 된다.
[math(\displaystyle \begin{aligned} \frac{\left( e^x -1 \right)^k}{k!} &= \frac 1{k!} \sum_{r=0}^k \binom kr {\left( e^x \right)}^r (-1)^{k-r} \\ &= \frac 1{k!} \sum_{r=0}^k \binom kr (-1)^{k-r} \sum_{n=0}^\infty \frac{(xr)^n}{n!} = \sum_{n=0}^\infty \frac 1{k!} \sum_{r=0}^k \binom kr (-1)^{k-r} \frac{x^n r^n}{n!} \\ &= \sum_{n=0}^\infty \left\{ \frac 1{k!} \sum_{r=0}^k \binom kr (-1)^{k-r} r^n \right\} \frac{x^n}{n!} = \sum_{n=0}^\infty \begin{Bmatrix} n \\ k \end{Bmatrix} \frac{x^n}{n!} \end{aligned})]

[math(\begin{Bmatrix} n \\ k \end{Bmatrix})]대신에 [math(\begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix})]를 대입할 경우 지수생성함수는 다음과 같이 된다.
[math(\displaystyle \begin{aligned} \sum_{n=0}^\infty \begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix} \frac{x^n}{n!} &= \sum_{n=0}^\infty \left\{ \frac 1{(k+1)!} \sum_{r=0}^{k+1} \binom{k+1}r (-1)^{k-r+1} r^{n+1} \right\} \frac{x^n}{n!} \\ &= \sum_{n=0}^\infty \frac 1{(k+1)!} \sum_{r=1}^{k+1} \binom{k+1}r (-1)^{k-r+1}r \frac{x^n r^n}{n!} = \frac 1{(k+1)!} \sum_{r=1}^{k+1} \frac{(k+1)!}{r!(k-r+1)!}(-1)^{k-r+1}r \sum_{n=0}^\infty \frac{(xr)^n}{n!} \\ &= \frac 1{k!} \sum_{r=1}^{k+1} \frac{k!}{(r-1)!(k-r+1)!}(-1)^{k-r+1}\left(e^x \right)^r = \frac 1{k!} \sum_{r=1}^{k+1} \binom k{r-1} (-1)^{k-r+1} \left( e^x \right)^r \\ &= \frac 1{k!} \sum_{r=0}^k \binom kr (-1)^{k-r} \left( e^x \right)^{r+1} \\ &= \frac{e^x \left( e^x -1 \right)^k}{k!} \end{aligned})]
여기까지 읽다보면 대략 정신이 멍해진다

4. 관련 문서

[1] 순열 [math({}_x{\rm P}_k)]와 동치이다. [2] 베르누이 수의 일반항을 나타낼 때 제2종 스털링 수의 일반항이 쓰인다. [3] 제1종 스털링 수와의 관계식에서 알 수 있듯이 [math(n \ge k)]만 만족하면 두 수가 모두 음수여도 정의할 수 있다. 물론 엄밀히 따지면 이 값은 제2종 스털링 수가 아니라 제1종 스털링 수지만……덤으로 일반항 구조상 [math(n)]만 음수여도 정의할 수 있다. 다만 이는 본래 정의에 따른 값이라기보단 확장된 값에 가깝다. [4] [math(n<k)]이면 조합론 수준에서는 정의되지 않으나 대수적으로도 정의된다는 점 때문에 [math(0)]인 것으로 약속한다. [5] [math(n \ge 0)], [math(k<0)]일 때는 아직 알려진 바가 없다. 일반항에서 음의 정수에 대한 팩토리얼이 정의되지 않기 때문

분류