|
이산수학 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 first kind
1. 개요
하강 계승 또는 상승 계승을 급수 표기로 나타냈을 때의 각 계수로 정의되는 수로, 제임스 스털링이 1730년에 도입하였다. 부호 없는 제1종 스털링 수 [math(\begin{bmatrix} n \\ k \end{bmatrix})][주의]와 부호 있는 제1종 스털링 수 [math(s(n,\,k) = (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix})]로 나뉘며 [math(0 \le k \le n \le 10)] 범위에서[2][3] [math(\begin{bmatrix} n \\ k \end{bmatrix})] 값은 다음과 같다. 아래 테이블에서 배경이 어두운 칸은 [math(s(n,\,k))]의 부호가 [math((-))]임을 의미한다.| [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(2)] | [math(3)] | [math(1)] | [math(0)] | |||||||
| [math(4)] | [math(6)] | [math(11)] | [math(6)] | [math(1)] | [math(0)] | ||||||
| [math(5)] | [math(24)] | [math(50)] | [math(35)] | [math(10)] | [math(1)] | [math(0)] | |||||
| [math(6)] | [math(120)] | [math(274)] | [math(225)] | [math(85)] | [math(15)] | [math(1)] | [math(0)] | ||||
| [math(7)] | [math(720)] | [math(1764)] | [math(1624)] | [math(735)] | [math(175)] | [math(21)] | [math(1)] | [math(0)] | |||
| [math(8)] | [math(5040)] | [math(13068)] | [math(13132)] | [math(6769)] | [math(1960)] | [math(322)] | [math(28)] | [math(1)] | [math(0)] | ||
| [math(9)] | [math(40320)] | [math(109584)] | [math(118124)] | [math(67284)] | [math(22449)] | [math(4536)] | [math(546)] | [math(36)] | [math(1)] | [math(0)] | |
| [math(10)] | [math(362880)] | [math(1026576)] | [math(1172700)] | [math(723680)] | [math(269325)] | [math(63273)] | [math(9450)] | [math(870)] | [math(45)] | [math(1)] | |
2. 정의
[math(x)]의 [math(n)]승 하강 계승 [math(x^{\underline n})]을 [math(x)]의 [math(n)]차식으로 나타냈을 때 [math(x^k)]의 계수를 제1종 스털링 수 [math(s(n,\,k))]로 정의한다. 즉| [math(\displaystyle x^{\underline n} = \prod _{k=0}^{n-1}(x-k) = x(x-1)(x-2) \cdots\cdots(x-n+1) = \sum_{k=0}^n s(n,\,k) x^k)] |
| [math(\displaystyle x^{\overline n} = \prod_{k=0}^{n-1}(x+k) = x(x+1)(x+2) \cdots\cdots(x+n-1) = \sum_{k=0}^n \left| s(n,\,k) \right| x^k)] |
각 하강 계승, 상승 계승을 이용한 정의식으로부터 다음과 같은 관계를 알 수 있다.
| [math(s(n,\,k) = (-1)^{n-k} c(n,\,k) = (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix})] |
[math(k=0)]일 때는 상수항의 계수를 의미하며 값이 두 가지 경우로 나뉜다. [math(n \ge 1)]이면 상수항이 없는 곱셈식이 되므로 [math(s(n,\,0) = 0)]이지만, [math(n=0)]이면 순열과의 관계로부터 [math(x^{\underline 0} = {}_x {\rm P}_0 = \dfrac{x!}{x!} = 1)]이므로 편의상 [math(s(0,\,0)=1)]로 정의한다. 또 부호 없는 제1종 스털링 수의 정의식에 [math(x=1)]을 대입하면 다음과 같은 관계식을 유도할 수 있다.
| [math(\displaystyle 1^{\overline n} = \prod_{k=1}^n k = n! = \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix})] |
부호 없는 제1종 스털링 수는 조합론으로도 정의할 수 있는데, 원소의 개수가 [math(n)]인 집합을 구분되지 않는 [math(k)]개의 순환[4]으로 분할하는 방법의 수이다.
예를 들어 [math(a)], [math(b)], [math(c)], [math(d)]를 원소로 갖는 집합을 [math(2)]개의 순환으로 분할해보면
[math(\begin{pmatrix} a \end{pmatrix},\,\begin{pmatrix} b & c & d \end{pmatrix})]
[math(\begin{pmatrix} a \end{pmatrix},\,\begin{pmatrix} b & d & c \end{pmatrix})]
[math(\begin{pmatrix} b \end{pmatrix},\,\begin{pmatrix} a & c & d \end{pmatrix})]
[math(\begin{pmatrix} b \end{pmatrix},\,\begin{pmatrix} a & d & c \end{pmatrix})]
[math(\begin{pmatrix} c \end{pmatrix},\,\begin{pmatrix} a & b & d \end{pmatrix})]
[math(\begin{pmatrix} c \end{pmatrix},\,\begin{pmatrix} a & d & b \end{pmatrix})]
[math(\begin{pmatrix} d \end{pmatrix},\,\begin{pmatrix} a & b & c \end{pmatrix})]
[math(\begin{pmatrix} d \end{pmatrix},\,\begin{pmatrix} a & c & b \end{pmatrix})]
[math(\begin{pmatrix} a & b \end{pmatrix},\,\begin{pmatrix} c & d \end{pmatrix})]
[math(\begin{pmatrix} a & c \end{pmatrix},\,\begin{pmatrix} b & d \end{pmatrix})]
[math(\begin{pmatrix} a & d \end{pmatrix},\,\begin{pmatrix} b & c \end{pmatrix})]
로 [math(11)]가지가 얻어지며 [math(\begin{bmatrix} 4 \\ 2 \end{bmatrix} = 11)]이다.
위의 두 정의가 왜 동치인지 직관적으로 와닿지 않을 수도 있는데, 각 정의를 바탕으로 점화식을 써보면 완전히 똑같은 식이 유도된다(후술).
3. 성질
3.1. 점화식
| [math(\begin{bmatrix} n+1 \\ k+1 \end{bmatrix} = \begin{bmatrix} n \\ k \end{bmatrix} + n \begin{bmatrix} n \\ k+1 \end{bmatrix})] |
| [math(\displaystyle x^{\overline{n+1}} = \prod_{k=0}^n(x+k) = (x+n)\prod _{k=0}^{n-1}(x+k) = (x+n) x^{\overline n} = x \cdot x^{\overline n} + n \cdot x^{\overline n})] |
조합론을 이용한 증명의 경우, [math(n)]개 원소를 분할한 경우에서 [math((n+1))]번째 원소를 끼워넣는 방법을 고려해서 유도할 수 있는데, [math((n+1))]번째 원소를 길이가 [math(1)]인 순환으로 남기는 방법과 다른 순환에 포함시키는 방법으로 나누어서 생각할 수 있다. 전자의 경우 [math((n+1))]번째 원소 자체가 [math(1)]개의 순환이므로 [math(n)]개의 원소를 [math(k)]개의 순환으로 분할한 경우의 수 [math(\begin{bmatrix} n \\ k \end{bmatrix})]가 그대로 쓰인다. 후자의 경우, [math(n)]개의 원소를 [math((k+1))]개의 순환으로 분할한 것을 대칭군 표기법으로 나열한 뒤, 각 순환의 원소에서 맨 앞, 사이 사이, 맨 뒤에 끼워넣어보면 되는데, 예를 들어 순환의 길이가 [math(m)]이라고 하면 [math((n+1))]번째 원소가 들어갈 자리의 수는 [math((m+1))]이지만 맨 앞과 맨 뒤에 끼워넣는 경우는 같은 순환이므로 결과적으로 각 순환에서 원소 하나를 끼워넣어서 새로운 순환이 생길 경우의 수는 순환의 길이 [math(m)]과 같다. 각 순환의 길이를 모두 합한 값은 원소의 총 개수 [math(n)]과 같으므로 경우의 수는 [math(\begin{bmatrix} n \\ k+1 \end{bmatrix})]에 [math(n)]을 곱한 값 [math(n \begin{bmatrix} n \\ k+1 \end{bmatrix})]이 된다.
또한 [math(s(n,\,k) = (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix})]였으므로 이를 대입해서 정리하면
| [math(s(n+1,\,k+1) = s(n,\,k) - n s(n,\,k+1))] |
3.2. 제2종 스털링 수와의 관계
-
[math(\begin{bmatrix} n \\ k \end{bmatrix} = \begin{Bmatrix} -k \\ -n \end{Bmatrix})]
두 성분을 교환하고 각 성분의 부호를 모두 바꿔주면 스털링 수의 종류가 바뀐다. 위 관계는 점화식을 이용해서 간단하게 증명이 가능하다. 우변의 제2종 스털링 수에 점화식을 적용하면
[math(\begin{Bmatrix} -k \\ -n \end{Bmatrix} = \begin{Bmatrix} -k-1 \\ -n-1 \end{Bmatrix} - n \begin{Bmatrix} -k-1 \\ -n \end{Bmatrix})]
이 되는데, 우변의 제2항을 이항하면
[math(\begin{Bmatrix} -k-1 \\ -n-1 \end{Bmatrix} = \begin{Bmatrix} -k \\ -n \end{Bmatrix} + n \begin{Bmatrix} -k-1 \\ -n \end{Bmatrix})]
이제 각 성분을 교환하고 [math(-1)]을 곱해주면 제1종 스털링 수의 점화식 꼴이 된다.
[math(\begin{bmatrix} n+1 \\ k+1 \end{bmatrix} = \begin{bmatrix} n \\ k \end{bmatrix} + n \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 \begin{aligned} \frac{\left\{ \ln(1+x) \right\}^k}{k!} &= \sum_{n=0}^\infty s(n,\,k) \frac{x^n}{n!} \\ \frac{ \left\{ - \ln(1-x) \right\}^k}{k!} &= \sum_{n=0}^\infty \begin{bmatrix} n \\ k \end{bmatrix} \frac{x^n}{n!} \end{aligned})] |
| [math(\displaystyle \begin{aligned} \frac{\left\{ \ln(1+x) \right\}^k}{k!} &= \sum_{n=k}^\infty s(n,\,k) \frac{x^n}{n!} \\ \frac{ \left\{ - \ln(1-x) \right\}^k}{k!} &= \sum_{n=k}^\infty \begin{bmatrix} n \\ k \end{bmatrix} \frac{x^n}{n!} \end{aligned})] |
| [math(\displaystyle \begin{aligned}(1+x)^r &= \sum_{n=0}^\infty \frac{r^{\underline n}}{n!} x^n = \sum_{n=0}^\infty \left\{ \sum_{k=0}^n s(n,\,k) r^k \right\} \frac{x^n}{n!} = \sum_{k=0}^\infty r^k \sum_{n=0}^\infty s(n,\,k) \frac{x^n}{n!} \\ &= e^{\ln(1+x)^r} = e^{r \ln(1+x)} = \sum_{k=0}^\infty \frac{ \left\{r \ln(1+x) \right\}^k}{k!} = \sum_{k=0}^\infty r^k \frac{ \left\{ \ln(1+x) \right\}^k}{k!} \end{aligned} \\ \therefore \frac{ \left\{ \ln(1+x) \right\}^k}{k!} = \sum_{n=0}^\infty s(n,\,k) \frac{x^n}{n!} = \sum_{n=k}^\infty s(n,\,k) \frac{x^n}{n!})] |
| [math(\displaystyle \begin{aligned}(1-x)^{-r} &= \sum_{n=0}^\infty \frac{(-r)^{\underline n}}{n!}(-x)^n = \sum_{n=0}^\infty \frac{(-1)^n r^{\overline n}}{n!}(-1)^n x^n = \sum_{n=0}^\infty \frac{ r^{\overline n}}{n!} x^n = \sum_{n=0}^\infty \left\{ \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} r^k \right\} \frac{x^n}{n!} = \sum_{k=0}^\infty r^k \sum_{n=0}^\infty \begin{bmatrix} n \\ k \end{bmatrix} \frac{x^n}{n!} \\ &= e^{\ln(1-x)^{-r}} = e^{-r \ln(1-x)} = \sum_{k=0}^\infty \frac{ \left\{ -r \ln(1-x) \right\}^k}{k!} = \sum_{k=0}^\infty r^k \frac{ \left\{ -\ln(1-x) \right\}^k}{k!} \end{aligned} \\ \therefore \frac{ \left\{ -\ln(1-x) \right\}^k}{k!} = \sum_{n=0}^\infty \begin{bmatrix} n \\ k \end{bmatrix} \frac{x^n}{n!} = \sum_{n=k}^\infty \begin{bmatrix} n \\ k \end{bmatrix} \frac{x^n}{n!} )] |
4. 관련 문서
[주의]
벡터나
행렬과 혼동할 수 있기 때문에 사전에 이것이 부호 없는 제1종 스털링 수임을 알려주어야 한다.
[2]
제2종 스털링 수와의 관계식에서 알 수 있듯이 [math(n \ge k)]만 만족하면 두 수가 모두 음수여도 정의할 수 있다. 물론 엄밀히 따지면 이 값은 제1종 스털링 수가 아니라 제2종 스털링 수지만……
[3]
[math(n<k)]이면 조합론 수준에서는 정의되지 않으나 대수적으로도 정의된다는 점 때문에 [math(0)]인 것으로 약속한다.
[4]
방향이 있는 원순열이다. 1 → 2 → 3 → 4 → 1과 1 → 4 → 3 → 2 → 1은 같은 원순열이지만 다른 순환이다.
대칭군의 표기법으로 나타내면 전자는 [math(\begin{pmatrix} 1 & 2 & 3 & 4 \end{pmatrix})]이고 후자는 [math(\begin{pmatrix} 1 & 4 & 3 & 2 \end{pmatrix})]로 극명하게 다르다는 것을 알 수 있다.