스털링 수

조합론에서 스털링 수(Stirling數, 영어: Stirling number)는 조합론에서 자주 등장하는 두 종의 정수열이다.

정의

제1종 스털링 수

2개의 순환을 갖는, 4개의 원소의 순열은 총 11개가 있다. 따라서 $\textstyle \left[{4 \atop 2}\right]=11$이다.

부호 없는 제1종 스털링 수(영어: unsigned Stirling numbers of the first kind)는 다음과 같다.

$x(x-1)(x-2)\cdots (x-n+1)=\sum _{m=0}^{n}(-1)^{n-m}\left[{n \atop m}\right]x^{m}$

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

(부호 있는) 제1종 스털링 수(영어: (signed) Stirling numbers of the first kind)는 다음과 같다.

$s(n,m)=(-1)^{n-m}\left[{n \atop m}\right]$

부호 없는 제1종 스털링 수의 값은 다음과 같다. (OEIS의 수열 A130534)

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종 스털링 수

4개의 원소의 집합의 분할의 개수는 벨 수 $B_{4}=15$개이다. 이 가운데, 분할된 부분집합들의 수가 m개인 경우는 제2종 스털링 수 $\textstyle \left\{{4 \atop m}\right\}$에 의해 주어진다. 그림에 따라, $\textstyle \left\{{4 \atop 1}\right\}=1$, $\textstyle \left\{{4 \atop 2}\right\}=7$, $\textstyle \left\{{4 \atop 3}\right\}=6$, $\textstyle \left\{{4 \atop 4}\right\}=1$이다.

제2종 스털링 수(영어: Stirling numbers of the second kind)는 다음과 같다.

$x^{n}=\sum _{m=0}^{n}\left\{{n \atop m}\right\}x(x-1)\cdots (x-m+1)$

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

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

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

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

제2종 스털링 수의 값은 다음과 같다. (OEIS의 수열 A008277)

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 }\left[{n \atop m}\right]x^{n}/n!={\frac {(-\ln(1-x))^{m}}{m!}}$

$\sum _{n=0}^{\infty }\left\{{n \atop m}\right\}x^{n}/n!={\frac {(\exp(x)-1)^{m}}{m!}}$

점화식

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

$\left[{n+1 \atop m}\right]=n\left[{n \atop m}\right]+\left[{n \atop m-1}\right]$

$\left\{{n+1 \atop m}\right\}=m\left\{{n \atop m}\right\}+\left\{{n \atop m-1}\right\}$

합 공식

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

$\sum _{m=0}^{n}\left[{n \atop m}\right]=n!$

$\sum _{m=0}^{n}\left\{{n \atop m}\right\}=B_{n}$

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

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

$\sum _{p=k}^{n}\left[{n \atop p}\right]{\binom {p}{k}}=\left[{n+1 \atop k+1}\right]$

특별한 값

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

$\left[{n \atop m}\right]=\left\{{n \atop m}\right\}=0\qquad (m>n)$

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

$\left[{n \atop 0}\right]=\left\{{n \atop 0}\right\}=\delta _{n,0}={\begin{cases}1&n=0\\0&n>0\end{cases}}$

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

$\left[{n \atop 1}\right]=(n-1)!\qquad (n\geq 1)$

$\left\{{n \atop 1}\right\}=1\qquad (n\geq 1)$

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

$\left[{n \atop 2}\right]=(n-1)!H_{n-1}=(n-1)!\sum _{k=1}^{n-1}{\frac {1}{k}}$

$\left\{{n \atop 2}\right\}=2^{n-1}-1$

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

$\left[{n \atop n}\right]=\left\{{n \atop n}\right\}=1\qquad (n\geq 0)$

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

$\left[{n \atop n-1}\right]=\left\{{n \atop n-1}\right\}={\binom {n}{2}}$

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

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

$\left\{{n \atop n-2}\right\}={\frac {3n-5}{4}}{\binom {n}{3}}$

역사

제임스 스털링(영어: James Stirling)이 1730년에 《미분법: 무한급수의 합과 보간에 대한 논문》(라틴어: Methodus differentialis, sive tractatus de summatione et interpolatione serierum infinitarum)이라는 책에서 도입하였다. 닐스 닐센(독일어: Niels Nielsen)이 1965년에 이 수들을 "스털링 수"라고 이름붙였다.

각주

• Comtet, Louis (1974). 《Advanced combinatorics: The art of finite and infinite expansions》 (영어). Dordrecht: Reidel Publishing Company. Zbl 0283.05001. 
• Graham, Ronald L.; Donald E. Knuth, Oren Patashnik (1994). 《Concrete mathematics: a foundation for computer science》 (영어) 2판. Addison-Wesley Professional. ISBN 0-201-55802-5. MR 1397498. Zbl 0836.00001.  CS1 관리 - 추가 문구 (링크)
• Benjamin, Arthur T.; Gregory O. Preston, Jennifer J. Quinn (2002). “A Stirling encounter with harmonic numbers” (PDF). 《Mathematics Magazine》 (영어) 75 (2): 95–103. Zbl 1063.05002. 2009년 6월 17일에 원본 문서 (PDF)에서 보존된 문서. 2014년 4월 12일에 확인함. 
• Griffiths, Martin (2012년 11월). “Close encounters with Stirling numbers of the second kind”. 《The Mathematics Teacher》 (영어) 106 (4): 313–317. doi:10.5951/mathteacher.106.4.0313. JSTOR 10.5951/mathteacher.106.4.0313. 

같이 보기

• 벨 수
• 12정도

외부 링크

• 이철희. “스털링 수”. 《수학노트》. 
• Weisstein, Eric Wolfgang. “Stirling number of the first kind”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Stirling number of the second kind”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Associated Stirling number of the first kind”. 《Wolfram MathWorld》 (영어). Wolfram Research.