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]만 만족하면 두 수가 모두 음수여도 정의할 수 있다. 물론 엄밀히 따지면 이 값은 제2종 스털링 수가 아니라 제1종 스털링 수지만……덤으로 일반항 구조상 [math(n)]만 음수여도 정의할 수 있다. 다만 이는 본래 정의에 따른 값이라기보단 확장된 값에 가깝다.][4]이면 조합론 수준에서는 정의되지 않으나 대수적으로도 정의된다는 점 때문에 [math(0)]인 것으로 약속한다.] [math(begin{Bmatrix} n \ k end{Bmatrix})] 값은 다음과 같다.
[math(n Bigbackslash 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))]이다.
제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})]가 된다. 정리하면 위의 식이 얻어진다.
조합론의 경우는 훨씬 더 간단하게 증명이 된다. 위의 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(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 -cdotscdots right) right} right] \ = k^n - binom k1 (k-1)^n + binom k2 (k-2)^n - binom k3 (k-3)^n +cdotscdots + (-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(k<0)]일 때는 아직 알려진 바가 없다. 일반항에서 음의 정수에 대한 팩토리얼이 정의되지 않기 때문] 베르누이 수열 중 [math(B_n ^-)]의 일반항을 구할 때 위 식이 쓰이기도 한다.
재미있게도 [math(begin{Bmatrix} n+1 \ k+1 end{Bmatrix})]을 일반항으로 나타내면
재미있게도 [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})]
|