제2종 스털링 수 (덤프버전으로 되돌리기)

[include(틀:이산수학)]
[목차]
{{{+2 Stirling numbers of the second kind}}}

== 개요 ==
[math(x^n)]을 [[계승(수학)#하강 계승|하강 계승]] [math(x^{\underline k})][* 순열 [math({}_x{\rm P}_k)]와 동치이다.]의 급수로 나타낼 때 각 항에 곱해지는 계수로 정의되며, [math(\begin{Bmatrix} n \\ k \end{Bmatrix})] 혹은 [math(S(n,\,k))]로 나타낸다. 1730년에 제임스 스털링이 도입하였다. 이 수의 합이 [[벨 수]]와 관련이 있고, 공교롭게도 [[벨 수]]와 똑같은 기호를 쓰는 [[베르누이 수]]와도 연관[* 베르누이 수의 일반항을 나타낼 때 제2종 스털링 수의 일반항이 쓰인다.]이 있다. [math(0 \le k \le n \le 10)] 범위에서[* [[제1종 스털링 수]]와의 관계식에서 알 수 있듯이 [math(n \ge k)]만 만족하면 두 수가 모두 음수여도 정의할 수 있다. 물론 엄밀히 따지면 이 값은 제2종 스털링 수가 아니라 제1종 스털링 수지만……덤으로 일반항 구조상 [math(n)]만 음수여도 정의할 수 있다. 다만 이는 본래 정의에 따른 값이라기보단 확장된 값에 가깝다.][* [math(n<k)]이면 조합론 수준에서는 정의되지 않으나 대수적으로도 정의된다는 점 때문에 [math(0)]인 것으로 약속한다.] [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)] ||<-10> [math(0)] ||
|| [math(1)] ||<|10> [math(0)] || [math(1)] ||<-9> [math(0)] ||
|| [math(2)] || [math(1)] || [math(1)] ||<-8> [math(0)] ||
|| [math(3)] || [math(1)] || [math(3)] || [math(1)] ||<-7> [math(0)] ||
|| [math(4)] || [math(1)] || [math(7)] || [math(6)] || [math(1)] ||<-6> [math(0)] ||
|| [math(5)] || [math(1)] || [math(15)] || [math(25)] || [math(10)] || [math(1)] ||<-5> [math(0)] ||
|| [math(6)] || [math(1)] || [math(31)] || [math(90)] || [math(65)] || [math(15)] || [math(1)] ||<-4> [math(0)] ||
|| [math(7)] || [math(1)] || [math(63)] || [math(301)] || [math(350)] || [math(140)] || [math(21)] || [math(1)] ||<-3> [math(0)] ||
|| [math(8)] || [math(1)] || [math(127)] || [math(966)] || [math(1701)] || [math(1050)] || [math(266)] || [math(28)] || [math(1)] ||<-2> [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)] ||

== 정의 ==
|| [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))]이다.

== 성질 ==
=== 점화식 ===
|| [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})]가 된다. 정리하면 위의 식이 얻어진다.

=== [[제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)]을 의미하기 때문이다.

=== 일반항 ===
|| [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)]을 음의 정수로까지 확장시킬 수 있다'''는 것이다.[* [math(n \ge 0)], [math(k<0)]일 때는 아직 알려진 바가 없다. 일반항에서 음의 정수에 대한 팩토리얼이 정의되지 않기 때문] [[베르누이 수열]] 중 [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 ^+)]의 일반항을 구할 때 쓰인다.

=== [[생성함수#지수 생성함수|지수생성함수]] ===
|| [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})] ||
~~여기까지 읽다보면 [[대략 정신이 멍해진다]]~~
== 관련 문서 ==
 * [[제1종 스털링 수]]
 * [[라흐 수]]
 * [[순열]]
 * [[벨 수]]
 * [[분할]]
 * [[베르누이 수열]]
[[분류:이산수학]]
제2종 스털링 수 (덤프버전으로 되돌리기)

캡챠
