| 이산수학 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색정리 · 이항정리(파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 (예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
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})] |
| [math(\displaystyle x^n = \sum_{k=0}^n k! S(n,\,k) \binom xk)] |
| [math(x^3 = 0 \cdot 1 + 1 \cdot x + 3 \cdot (x^2 - x) + 1 \cdot \left( x^3 - 3x^2 + 2x \right) )] |
제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(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(x \cdot x^{\underline{k+1}} = x^{\underline{k+2}} + (k+1) \cdot x^{\underline{k+1}})] |
| [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})] |
조합론의 경우는 훨씬 더 간단하게 증명이 된다. 위의 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)] |
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(\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})] |
재미있게도 [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(\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)] |
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!})] |
| [math(\displaystyle \frac{\left( e^x -1 \right)^k}{k!} = \sum_{n=k}^\infty \begin{Bmatrix} n \\ k \end{Bmatrix} \frac{x^n}{n!})] |
| [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)]일 때는 아직 알려진 바가 없다. 일반항에서 음의 정수에 대한 팩토리얼이 정의되지 않기 때문