Stirling numbers of the second kind
[math(x^n)]을
하강 계승 [math(x^{\underline k})]
[1] 순열 [math({}_x{\rm P}_k)]와 동치이다.
의 급수로 나타낼 때 각 항에 곱해지는 계수로 정의되며, [math(\begin{Bmatrix} n \\ k \end{Bmatrix})] 혹은 [math(S(n,\,k))]로 나타낸다. 1730년에 제임스 스털링이 도입하였다. 이 수의 합이
벨 수와 관련이 있고, 공교롭게도
벨 수와 똑같은 기호를 쓰는
베르누이 수와도 연관
[2] 베르누이 수의 일반항을 나타낼 때 제2종 스털링 수의 일반항이 쓰인다.
이 있다. [math(0 \le k \le n \le 10)] 범위에서
[3] 제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)]
| [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)]
|
[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})]가 된다. 정리하면 위의 식이 얻어진다.
- || [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)]을 음의 정수로까지 확장시킬 수 있다는 것이다.
[5] [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})]
|
여기까지 읽다보면 대략 정신이 멍해진다
이 문서의 내용 중 전체 또는 일부는 2023-12-16 14:33:28에 나무위키
제2종 스털링 수 문서에서 가져왔습니다.
이 문서의 내용 중 전체 또는 일부는 2023-12-16 14:33:28에 나무위키 제2종 스털링 수 문서에서 가져왔습니다.