스털링 수

틀:위키데이터 속성 추적 조합론에서 스털링 수(Stirling數, 틀:Llang)는 조합론에서 자주 등장하는 두 종의 정수열이다.

정의

제1종 스털링 수

부호 없는 제1종 스털링 수(틀:Llang)는 다음과 같다.

x (x - 1) (x - 2) \dots (x - n + 1) = \sum_{m = 0}^{n} (- 1)^{n - m} [\binom{n}{m}] x^{m}

부호 없는 제1종 스털링 수는 $c (n, m)$ 으로 쓰기도 한다. 대괄호를 쓰는 표기는 도널드 커누스가 도입하였다.^[1] 부호 없는 제1종 스털링 수는 n개의 원소의 순열 가운데, 정확히 m개의 순환(cycle)들로 구성된 순열들의 수이다. (이 경우, 고정점은 길이 1의 순환으로 간주한다.)

(부호 있는) 제1종 스털링 수(틀:Llang)는 다음과 같다.

s (n, m) = (- 1)^{n - m} [\binom{n}{m}]

부호 없는 제1종 스털링 수의 값은 다음과 같다. 틀:OEIS

n ＼ m	0	1	2	3	4	5	6	7	8	9	10
0	1
1	0	1
2	0	1	1
3	0	2	3	1
4	0	6	11	6	1
5	0	24	50	35	10	1
6	0	120	274	225	85	15	1
7	0	720	1764	1624	735	175	21	1
8	0	5040	13068	13132	6769	1960	322	28	1
9	0	40320	109584	118124	67284	22449	4536	546	36	1
10	0	362880	1026576	1172700	723680	269325	63273	9450	870	45	1

제2종 스털링 수

제2종 스털링 수(틀:Llang)는 다음과 같다.

x^{n} = \sum_{m = 0}^{n} {\binom{n}{m}} x (x - 1) \dots (x - m + 1)

제2종 스털링 수는 $S (n, m)$ 으로 쓰기도 한다. 중괄호를 쓰는 표기는 도널드 커누스가 도입하였다.^[1]

제2종 스털링 수는 n개의 원소의 집합을 m개의 공집합이 아닌 부분집합들로 나누는 방법의 수이다.

제2종 스털링 수의 점화식은 재귀적인 표현으로 나타낼 수 있다.

$S_{n, m} = S_{n - 1, m - 1} + m \cdot S_{n - 1, m}$

제2종 스털링 수의 값은 다음과 같다. 틀:OEIS

n ＼ m	0	1	2	3	4	5	6	7	8	9	10
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1
7	0	1	63	301	350	140	21	1
8	0	1	127	966	1701	1050	266	28	1
9	0	1	255	3025	7770	6951	2646	462	36	1
10	0	1	511	9330	34105	42525	22827	5880	750	45	1

성질

생성함수

스털링 수는 다음과 같은 생성함수를 갖는다.

\sum_{n = 0}^{\infty} [\binom{n}{m}] x^{n} / n! = \frac{(- \ln (1 - x))^{m}}{m!}

\sum_{n = 0}^{\infty} {\binom{n}{m}} x^{n} / n! = \frac{(\exp (x) - 1)^{m}}{m!}

점화식

스털링 수는 다음과 같은 점화식을 만족시킨다.

[\binom{n + 1}{m}] = n [\binom{n}{m}] + [\binom{n}{m - 1}]

{\binom{n + 1}{m}} = m {\binom{n}{m}} + {\binom{n}{m - 1}}

합 공식

스털링 삼각형에서 각 열을 더하면 다음과 같다.

\sum_{m = 0}^{n} [\binom{n}{m}] = n!

\sum_{m = 0}^{n} {\binom{n}{m}} = B_{n}

여기서 $B_{n}$ 은 벨 수이다. 이는 $n$ 개의 원소에 대한 순열의 수가 $n!$ 이고, $n$ 개의 원소를 가진 집합의 분할은 벨 수 $B_{n}$ 이기 때문이다.

또한, 다음과 같은 공식이 존재한다.

\sum_{p = k}^{n} [\binom{n}{p}] (\binom{p}{k}) = [\binom{n + 1}{k + 1}]

특별한 값

$m > n$ 이라면 스털링 수는 0으로 정의한다.

[\binom{n}{m}] = {\binom{n}{m}} = 0 (m > n)

또한, $m = 0$ 인 경우 스털링 수는 크로네커 델타 $δ_{n, 0}$ 이다.

[\binom{n}{0}] = {\binom{n}{0}} = δ_{n, 0} = {\begin{matrix} 1 & n = 0 \\ 0 & n > 0 \end{matrix}

$m = 1$ 인 경우는 다음과 같다.

[\binom{n}{1}] = (n - 1)! (n \geq 1)

{\binom{n}{1}} = 1 (n \geq 1)

$m = 2$ 인 경우는 다음과 같다. 여기서 $H_{k}$ 는 조화수이다.

[\binom{n}{2}] = (n - 1)! H_{n - 1} = (n - 1)! \sum_{k = 1}^{n - 1} \frac{1}{k}

{\binom{n}{2}} = 2^{n - 1} - 1

$m = n$ 인 경우는 스털링 수는 항상 1이다.

[\binom{n}{n}] = {\binom{n}{n}} = 1 (n \geq 0)

$m = n - 1$ 인 경우는 다음과 같다.

[\binom{n}{n - 1}] = {\binom{n}{n - 1}} = (\binom{n}{2})

$m = n - 2$ 인 경우는 다음과 같다.

[\binom{n}{n - 2}] = \frac{1}{4} (3 n - 1) (\binom{n}{3})

{\binom{n}{n - 2}} = \frac{3 n - 5}{4} (\binom{n}{3})

역사

제임스 스털링(틀:Llang)이 1730년에 《미분법: 무한급수의 합과 보간에 대한 논문》(틀:Llang)이라는 책에서 도입하였다.^[2]^[3] 닐스 닐센(틀:Llang)이 1965년에 이 수들을 "스털링 수"라고 이름붙였다.^[3]^[4]

각주

틀:각주

같이 보기

외부 링크

[Knuth-1] 1.0 ^1.1 틀:저널 인용

[2] 틀:서적 인용

[Boyadzhiev-3] 3.0 ^3.1 틀:저널 인용

[4] 틀:서적 인용

[1]

[2]

[3]

[4]

스털링 수

목차

정의

제1종 스털링 수

제2종 스털링 수

성질

생성함수

점화식

합 공식

특별한 값

역사

각주

같이 보기

외부 링크

둘러보기 메뉴

스털링 수

정의

제1종 스털링 수

제2종 스털링 수

성질

생성함수

점화식

합 공식

특별한 값

역사

각주

같이 보기

외부 링크

둘러보기 메뉴

검색