스털링 수

조합론에서 **스털링 수**(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종 스털링 수의 값은 다음과 같다. A130534 {| class=wikitable |- ! *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)으로 쓰기도 한다. 중괄호를 쓰는 표기는 도널드 커누스가 도입하였다.언어=en 제2종 스털링 수는 *n*개의 원소의 집합을 *m*개의 공집합이 아닌 부분집합들로 나누는 방법의 수이다. 제2종 스털링 수의 점화식은 재귀적인 표현으로 나타낼 수 있다. S_{n,m} = S_{n-1,m-1} + m\cdot S_{n-1,m} 제2종 스털링 수의 값은 다음과 같다. A008277 {| class=wikitable |- ! *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 pk = \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\atop1}\right] = (n-1)!\qquad(n\ge1) :\left\\n\atop1}\right\\}=1\qquad(n\ge1) m=2인 경우는 다음과 같다. 여기서 H_k는 조화수이다. :\left[{n\atop2}\right] = (n-1)!H_{n-1}=(n-1)!\sum_{k=1}^{n-1}\frac1k :\left\\n\atop2}\right\\} = 2^{n-1}-1 m=n인 경우는 스털링 수는 항상 1이다. :\left[{n\atop n}\right]=\left\\n\atop n}\right\\}=1\qquad(n\ge0) m=n-1인 경우는 다음과 같다. :\left[{n\atop n-1}\right]=\left\\n\atop n-1}\right\\} =\binom n2 m=n-2인 경우는 다음과 같다. :\left[{n\atop n-2}\right]= \frac{1}{4} (3n-1)\binom n3 :\left\\n\atop n-2}\right\\}=\frac{3n-5}4\binom n3
# 역사
제임스 스털링(James Stirling)이 1730년에 《미분법: 무한급수의 합과 보간에 대한 논문》(Methodus differentialis, sive tractatus de summatione et interpolatione serierum infinitarum)이라는 책에서 도입하였다.url=http://gallica.bnf.fr/ark:/12148/bpt6k62011b언어=en 닐스 닐센(Niels Nielsen)이 1965년에 이 수들을 "스털링 수"라고 이름붙였다.언어=de