Stirling numbers of the second kind1. 개요
$$x^n$$을
하강 계승 $$x^{\underline k}$$
[1]의 급수로 나타낼 때 각 항에 곱해지는 계수로 정의되며, $$\begin{Bmatrix} n \\ k \end{Bmatrix}$$ 혹은 $$S(n,\,k)$$로 나타낸다. 1730년에 제임스 스털링이 도입하였다. 이 수의 합이
벨 수와 관련이 있고, 공교롭게도
벨 수와 똑같은 기호를 쓰는
베르누이 수와도 연관
[2] 베르누이 수의 일반항을 나타낼 때 제2종 스털링 수의 일반항이 쓰인다.
이 있다. $$0 \le k \le n \le 10$$ 범위에서
[3] 제1종 스털링 수와의 관계식에서 알 수 있듯이 n \ge k만 만족하면 두 수가 모두 음수여도 정의할 수 있다. 물론 엄밀히 따지면 이 값은 제2종 스털링 수가 아니라 제1종 스털링 수지만……덤으로 일반항 구조상 n만 음수여도 정의할 수 있다. 다만 이는 본래 정의에 따른 값이라기보단 확장된 값에 가깝다.
n<k이면 조합론 수준에서는 정의되지 않으나 대수적으로도 정의된다는 점 때문에 [math(0)]인 것으로 약속한다.
$$\begin{Bmatrix} n \\ k \end{Bmatrix}$$ 값은 다음과 같다.
$$n \Big\backslash k$$
| [math(0)]
| $$1$$
| $$2$$
| $$3$$
| $$4$$
| $$5$$
| $$6$$
| $$7$$
| $$8$$
| $$9$$
| $$10$$
|
[math(0)]
| $$1$$
| [math(0)]
|
$$1$$
| [math(0)]
| $$1$$
| [math(0)]
|
$$2$$
| $$1$$
| $$1$$
| [math(0)]
|
$$3$$
| $$1$$
| $$3$$
| $$1$$
| [math(0)]
|
$$4$$
| $$1$$
| $$7$$
| $$6$$
| $$1$$
| [math(0)]
|
$$5$$
| $$1$$
| $$15$$
| $$25$$
| $$10$$
| $$1$$
| [math(0)]
|
$$6$$
| $$1$$
| $$31$$
| $$90$$
| $$65$$
| $$15$$
| $$1$$
| [math(0)]
|
$$7$$
| $$1$$
| $$63$$
| $$301$$
| $$350$$
| $$140$$
| $$21$$
| $$1$$
| [math(0)]
|
$$8$$
| $$1$$
| $$127$$
| $$966$$
| $$1701$$
| $$1050$$
| $$266$$
| $$28$$
| $$1$$
| [math(0)]
|
$$9$$
| $$1$$
| $$255$$
| $$3025$$
| $$7770$$
| $$6951$$
| $$2646$$
| $$462$$
| $$36$$
| $$1$$
| [math(0)]
|
$$10$$
| $$1$$
| $$511$$
| $$9330$$
| $$34105$$
| $$42525$$
| $$22827$$
| $$5880$$
| $$750$$
| $$45$$
| $$1$$
|
2. 정의
$$\displaystyle x^n = \sum_{k=0}^n S(n,\,k)x^{\underline k}$$
|
부호 없는
제1종 스털링 수와 비슷하게 $$S(n,\,k)$$는 종종 $$\begin{Bmatrix} n \\ k \end{Bmatrix}$$로 표기되곤 한다. $$x^{\underline k} = {}_x{\rm P}_k = k! \dbinom xk$$의 관계에 있으므로 위 식은 다음과 같이 나타낼 수도 있다.
$$\displaystyle x^n = \sum_{k=0}^n k! S(n,\,k) \binom xk$$
|
이를테면 $$n=3$$일 때, $$x^{\underline 0} = 1$$, $$x^{\underline 1} = x$$, $$x^{\underline 2} = x(x-1) = x^2 - x$$, $$x^{\underline 3} = x(x-1)(x-2) = x^3 - 3x^2 + 2x$$이므로
$$x^3 = 0 \cdot 1 + 1 \cdot x + 3 \cdot (x^2 - x) + 1 \cdot \left( x^3 - 3x^2 + 2x \right) $$
|
로부터 $$\begin{Bmatrix} 3 \\ 0 \end{Bmatrix} = 0$$, $$\begin{Bmatrix} 3 \\ 1 \end{Bmatrix} = 1$$, $$\begin{Bmatrix} 3 \\ 2 \end{Bmatrix} = 3$$, $$\begin{Bmatrix} 3 \\ 3 \end{Bmatrix} = 1$$이다.
제1종 스털링 수와 마찬가지로 조합론을 이용해서도 정의할 수 있는데, 원소의 개수가 $$n$$인 집합을 구분되지 않는 $$k$$개의 부분 집합으로 분할하는 방법의 수가 된다. 예를 들어 어느 대학교에서 MT를 $$n$$명이 갔는데 방을 $$k$$개 잡았고 각 방에는 적어도 $$1$$명이 들어가야 한다고 할 때 가능한 경우의 수가 $$S (n,\,k)$$이다.
각 정의에 입각해서 점화식을 써보면 두 경우 모두 완전히 같은 식이 유도가 되어 동치임을 알 수 있다.
참고로
제1종 스털링 수의 기호는 $$S$$를 소문자로 바꾸어 쓴 $$s(n,\,k)$$이다.
3. 성질
$$\begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix} = \begin{Bmatrix} n \\ k \end{Bmatrix} + (k+1) \begin{Bmatrix} n \\ k+1 \end{Bmatrix}$$
|
급수를 이용한 증명에서는 하강 계승을 변형시켜서 유도해줄 수 있다.
$$\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}$$
|
첫 번째 식에서 $$\begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix}$$는 $$x^{\underline{k+1}}$$의 계수이다. 따라서 $$x \cdot x^n$$에 관한 식에서는 $$x \cdot x^{\underline k}$$를 변형해서 $$x^{\underline{k+1}}$$이 나오도록 하면 된다.
$$x^{\underline k} = \dfrac{x!}{(x-k)!} = \dfrac{x!}{(x-k-1)!(x-k)} = \dfrac{x^{\underline{k+1}}}{x-k}$$
|
이므로
$$x \cdot x^{\underline k} = x^{\underline{k+1}} + k \cdot x^{\underline k}$$
|
이다. 한편, 이 관계식의 $$k$$에 $$(k+1)$$을 대입한
$$x \cdot x^{\underline{k+1}} = x^{\underline{k+2}} + (k+1) \cdot x^{\underline{k+1}}$$
|
에서도 $$x^{\underline{k+1}}$$항이 얻어지므로 이를 $$x \cdot x^n$$에 관한 등식에 대입한다.
$$\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}$$
|
대괄호 부분이 $$x^{n+1}$$의 전개식에서 $$\begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix}$$에 해당한다.
조합론의 경우는 훨씬 더 간단하게 증명이 된다. 위의 MT를 예시로 들면, $$(n+1)$$번째 사람이 추가로 MT에 참가해서 방을 $$(k+1)$$개로 늘린다고 할 때, 독방을 쓰는 경우와 다른 사람이 들어가 있는 방에 포함되는 경우로 나눌 수 있다. 독방을 쓴다고 하면 $$n$$명이었을 때의 $$k$$개 방으로 나눈 경우 $$\begin{Bmatrix} n \\ k \end{Bmatrix}$$가 그대로 쓰인다. 한편, 다른 사람이 있는 방에 들어간다고 하면 $$n$$명이었을 때 $$(k+1)$$개 방으로 나눈 경우에서 각 방에 들어가는 모든 경우가 포함되므로 $$(k+1) \begin{Bmatrix} n \\ k+1 \end{Bmatrix}$$가 된다. 정리하면 위의 식이 얻어진다.
- || $$\begin{Bmatrix} n \\ k \end{Bmatrix} = \begin{bmatrix} -k \\ -n \end{bmatrix}$$ ||
두 성분을 교환하고 각 성분의 부호를 모두 바꿔주면 스털링 수의 종류가 바뀐다. 위 관계는 점화식을 이용해서 간단하게 증명이 가능하다. 우변의 부호 없는
제1종 스털링 수에 점화식을 적용하면
$$\begin{bmatrix} -k \\ -n \end{bmatrix} = \begin{bmatrix} -k-1 \\ -n-1 \end{bmatrix} - (k+1) \begin{bmatrix} -k-1 \\ -n \end{bmatrix}$$
|
이 되는데, 우변의 제2항을 이항하면
$$\begin{bmatrix} -k-1 \\ -n-1 \end{bmatrix} = \begin{bmatrix} -k \\ -n \end{bmatrix} + (k+1) \begin{bmatrix} -k-1 \\ -n \end{bmatrix}$$
|
이제 각 성분을 교환하고 $$-1$$을 곱해주면 제2종 스털링 수의 점화식 꼴이 된다.
$$\begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix} = \begin{Bmatrix} n \\ k \end{Bmatrix} + (k+1) \begin{Bmatrix} n \\ k+1 \end{Bmatrix}$$
|
- ||$$\displaystyle \sum_{r=k}^n s(n,\,r) S(r,\,k) = \sum_{r=k}^n S(n,\,r) s(r,\,k) = \delta_{n,\,k}$$ ||
$$\delta_{n,\,k}$$는
크로네커 델타이다. 두 식 모두
라흐 수의 정의처럼 각 스털링 수의 정의를 연달아 적용함으로써 도출된다.
$$\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}$$
|
부호 없는 스털링 수, 그러니까 $$s(n,\,k) = (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix}$$표기를 이용하면 다음과 같이 된다.
$$\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}$$
|
두 식에서 우변의 $$-1$$의 지수가 다르지만 사실 둘 다 $$(-1)^n$$을 쓰든 $$(-1)^k$$를 쓰든 상관 없다. 어차피 부호가 제 역할을 하는 경우는 $$\delta_{n,\,k} = 1$$, 즉 $$n=k$$일 때 뿐이며, 좌변에서 $$n=k$$란 곧 $$(-1)^k \begin{bmatrix} k \\ k \end{bmatrix} \begin{Bmatrix} k \\ k \end{Bmatrix} = (-1)^k = (-1)^n$$을 의미하기 때문이다.
$$\displaystyle S(n,\,k) = \frac 1{k!} \sum_{r=0}^k \binom kr (-1)^r (k-r)^n$$
|
조합론을 이용한 정의에서, $$k$$개의 각 부분 집합에는 공집합이 없어야하는 것이 포인트이다. 즉, 공집합을 허용하도록 분할하는 모든 경우의 수에서 공집합이 적어도 하나 있는 모든 경우를 빼면 $$S(n,\,k)$$가 얻어진다.
MT를 예로, 먼저 빈 방이 생기는 걸 허용하여 $$n$$명을 $$k$$개의 호실에 배정하는 경우의 수는 $$n$$명이 동등한 $$k$$개의 선택권을 갖는 경우와 같으므로 $$k^n$$가지가 된다. 다음으로 빈 방이 $$r$$개만 생기도록 하는 경우의 수는, ($$k$$개의 방에서 $$r$$개를 임의로 골라낸 경우의 수)$$\times(k-r)$$개의 방에 차례로 배정하는 경우의 수)이므로 $$\dbinom kr (k-r)^n$$이 된다. 이제,
포함·배제의 원리에 따라 빈 방 없이 배정하는 경우를 구하면
$$\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$$
|
위 식은 각 방에 차례로 배정하는 경우(즉, 각 부분집합이 구분되는 경우)와 같으므로 이를 $$k!$$로 나눠서 구분되지 않는 부분 집합으로 만들어주면 된다. 즉
$$\displaystyle S(n,\,k) = \frac 1{k!} \sum_{r=0}^k (-1)^r \binom kr (k-r)^n$$
|
가 된다. $$\dbinom kr = \dbinom k{k-r}$$라는 성질을 이용하여
$$\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종 스털링 수와의 관계로부터 중요한 특징이 유도되는데, 바로 '''$$\boldsymbol n$$을 음의 정수로까지 확장시킬 수 있다'''는 것이다.
[5] n \ge 0, k<0일 때는 아직 알려진 바가 없다. 일반항에서 음의 정수에 대한 팩토리얼이 정의되지 않기 때문
중 $$B_n ^-$$의 일반항을 구할 때 위 식이 쓰이기도 한다.
재미있게도 $$\begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix}$$을 일반항으로 나타내면
$$\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}$$
|
이 되고 $$r=0$$인 항은 생략할 수 있으므로 $$r=1$$부터 더해주고 식을 변형해주면 다음과 같이 된다.
$$\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$$
|
즉, $$n$$과 $$k$$가 모두 $$1$$씩 증가해도 일반항에서 $$r^n$$항만 변할 뿐이다. 참고로 $$\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) $$W_{n,\,k}$$라고 하며,
베르누이 수열 중 $$B_n ^+$$의 일반항을 구할 때 쓰인다.
$$\displaystyle \frac{\left( e^x -1 \right)^k}{k!} = \sum_{n=0}^\infty \begin{Bmatrix} n \\ k \end{Bmatrix} \frac{x^n}{n!}$$
|
제2종 스털링 수 특성상 $$n<k$$이면 $$\begin{Bmatrix} n \\ k \end{Bmatrix} = 0$$이기 때문에 일반적으론 다음과 같은 축약식으로 나타낸다.
$$\displaystyle \frac{\left( e^x -1 \right)^k}{k!} = \sum_{n=k}^\infty \begin{Bmatrix} n \\ k \end{Bmatrix} \frac{x^n}{n!}$$
|
좌변의 식을 변형해서 정리해주면 제2종 스털링 수의 일반항이 튀어나오면서 간단하게 증명이 된다.
$$\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}$$
|
$$\begin{Bmatrix} n \\ k \end{Bmatrix}$$대신에 $$\begin{Bmatrix} n+1 \\ k+1 \end{Bmatrix}$$를 대입할 경우 생성함수는 다음과 같이 된다.
$$\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. 관련 문서