스털링 수 문서 원본 보기

{{위키데이터 속성 추적}}
[[조합론]]에서 '''스털링 수'''(Stirling數, {{llang|en|Stirling number}})는 [[조합론]]에서 자주 등장하는 두 종의 [[정수열]]이다.

== 정의 ==
=== 제1종 스털링 수 ===
[[파일:Stirling number of the first kind s(4,2).svg|섬네일|435px|right|2개의 순환을 갖는, 4개의 원소의 [[순열]]은 총 11개가 있다. 따라서 <math>\textstyle\left[{4\atop 2}\right]=11</math>이다.]]
'''부호 없는 제1종 스털링 수'''({{llang|en|unsigned Stirling numbers of the first kind}})는 다음과 같다.
:<math>x(x-1)(x-2)\cdots(x-n+1)=\sum_{m=0}^n(-1)^{n-m}\left[{n\atop m}\right]x^m</math>
부호 없는 제1종 스털링 수는 <math>c(n,m)</math>으로 쓰기도 한다. 대괄호를 쓰는 표기는 [[도널드 커누스]]가 도입하였다.<ref name="Knuth"/> 부호 없는 제1종 스털링 수는 ''n''개의 원소의 [[순열]] 가운데, 정확히 ''m''개의 순환(cycle)들로 구성된 순열들의 수이다. (이 경우, 고정점은 길이 1의 순환으로 간주한다.)

'''(부호 있는) 제1종 스털링 수'''({{llang|en|(signed) Stirling numbers of the first kind}})는 다음과 같다.
:<math>s(n,m)=(-1)^{n-m}\left[{n\atop m}\right]</math>

부호 없는 제1종 스털링 수의 값은 다음과 같다. {{OEIS|A130534}}
{| class=wikitable style="text-align:right;"
|-
! ''n''&nbsp;＼&nbsp;''m''
! style="width:7ex;"| 0
! style="width:7ex;"| 1
! style="width:7ex;"| 2
! style="width:7ex;"| 3
! style="width:7ex;"| 4
! style="width:7ex;" | 5
! style="width:7ex;" | 6
! style="width:7ex;" | 7
! style="width:7ex;" | 8
! style="width:7ex;" | 9
! style="width:7ex;" | 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종 스털링 수 ===
[[파일:Set partitions 4; Hasse; circles.svg|섬네일|315px|right|4개의 원소의 집합의 분할의 개수는 [[벨 수]] <math>B_4=15</math>개이다. 이 가운데, 분할된 부분집합들의 수가 ''m''개인 경우는 제2종 스털링 수 <math>\textstyle\left\{{4\atop m}\right\}</math>에 의해 주어진다. 그림에 따라, <math>\textstyle\left\{{4\atop 1}\right\}=1</math>,  <math>\textstyle\left\{{4\atop 2}\right\}=7</math>,  <math>\textstyle\left\{{4\atop 3}\right\}=6</math>,  <math>\textstyle\left\{{4\atop 4}\right\}=1</math>이다.]]
'''제2종 스털링 수'''({{llang|en|Stirling numbers of the second kind}})는 다음과 같다.
:<math>x^n=\sum_{m=0}^n\left\{{n\atop m}\right\}x(x-1)\cdots(x-m+1)</math>
제2종 스털링 수는 <math>S(n,m)</math>으로 쓰기도 한다. 중괄호를 쓰는 표기는 [[도널드 커누스]]가 도입하였다.<ref name="Knuth">{{저널 인용|이름=Donald|성=Knuth|저자링크=도널드 커누스|arxiv=math/9205211|bibcode=1992math......5211K|제목=Two notes on notation|저널=American Mathematical Monthly|권=99|날짜=1992|호=5|쪽=403–422|zbl=0785.05014|언어=en}}</ref>

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

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

<math>S_{n,m} = S_{n-1,m-1} + m\cdot S_{n-1,m}</math>

제2종 스털링 수의 값은 다음과 같다. {{OEIS|A008277}}
{| class=wikitable style="text-align:right;"
|-
! ''n''&nbsp;＼&nbsp;''m''
! style="width:7ex;"| 0
! style="width:7ex;"| 1
! style="width:7ex;"| 2
! style="width:7ex;"| 3
! style="width:7ex;"| 4
! style="width:7ex;" | 5
! style="width:7ex;" | 6
! style="width:7ex;" | 7
! style="width:7ex;" | 8
! style="width:7ex;" | 9
! style="width:7ex;" | 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
|-
 |}

== 성질 ==
=== 생성함수 ===
스털링 수는 다음과 같은 [[생성함수]]를 갖는다.
:<math>\sum_{n=0}^\infty\left[{n\atop m}\right]x^n/n!=\frac{(-\ln(1-x))^m}{m!}</math>
:<math>\sum_{n=0}^\infty\left\{{n\atop m}\right\}x^n/n!=\frac{(\exp(x)-1)^m}{m!}</math>

=== 점화식 ===
스털링 수는 다음과 같은 점화식을 만족시킨다.
: <math> \left[{n+1\atop m}\right] = n \left[{n\atop m}\right] + \left[{n\atop m-1}\right]</math>
:<math>\left\{{n+1\atop m}\right\}=m\left\{{n\atop m}\right\}+\left\{{n\atop m-1}\right\}</math>

=== 합 공식 ===
스털링 삼각형에서 각 열을 더하면 다음과 같다.
:<math>\sum_{m=0}^n \left[{n\atop m}\right] = n!</math>
:<math>\sum_{m=0}^n\left\{{n\atop m}\right\} = B_n</math>
여기서 <math>B_n</math>은 [[벨 수]]이다. 이는 <math>n</math>개의 원소에 대한 [[순열]]의 수가 <math>n!</math>이고, <math>n</math>개의 원소를 가진 집합의 분할은 [[벨 수]] <math>B_n</math>이기 때문이다.

또한, 다음과 같은 공식이 존재한다.
:<math>\sum_{p=k}^n\left[{n\atop p}\right]\binom pk = \left[{n+1\atop k+1}\right]</math>

=== 특별한 값 ===
<math>m>n</math>이라면 스털링 수는 0으로 정의한다.
:<math>\left[{n\atop m}\right]=\left\{{n\atop m}\right\}=0\qquad(m>n)</math>
또한, <math>m=0</math>인 경우 스털링 수는 [[크로네커 델타]] <math>\delta_{n,0}</math>이다.
:<math>\left[{n \atop 0}\right]=\left\{{n \atop 0}\right\} = \delta_{n,0}=\begin{cases}1&n=0\\0&n>0\end{cases}</math>
<math>m=1</math>인 경우는 다음과 같다.
:<math>\left[{n\atop1}\right] = (n-1)!\qquad(n\ge1)</math>
:<math>\left\{{n\atop1}\right\}=1\qquad(n\ge1)</math>
<math>m=2</math>인 경우는 다음과 같다. 여기서 <math>H_k</math>는 [[조화수]]이다.
:<math>\left[{n\atop2}\right] = (n-1)!H_{n-1}=(n-1)!\sum_{k=1}^{n-1}\frac1k</math>
:<math>\left\{{n\atop2}\right\} = 2^{n-1}-1</math>
<math>m=n</math>인 경우는 스털링 수는 항상 1이다.
:<math>\left[{n\atop n}\right]=\left\{{n\atop n}\right\}=1\qquad(n\ge0)</math>
<math>m=n-1</math>인 경우는 다음과 같다.
:<math>\left[{n\atop n-1}\right]=\left\{{n\atop n-1}\right\} =\binom n2</math>
<math>m=n-2</math>인 경우는 다음과 같다.
:<math>\left[{n\atop n-2}\right]= \frac{1}{4} (3n-1)\binom n3</math>
:<math>\left\{{n\atop n-2}\right\}=\frac{3n-5}4\binom n3</math>

== 역사 ==
[[제임스 스털링 (수학자)|제임스 스털링]]({{llang|en|James Stirling}})이 1730년에 《미분법: 무한급수의 합과 보간에 대한 논문》({{llang|la|Methodus differentialis, sive tractatus de summatione et interpolatione serierum infinitarum}})이라는 책에서 도입하였다.<ref>{{서적 인용|제목=Methodus differentialis, sive tractatus de summatione et interpolatione serierum infinitarum|이름=Jacobus|성=Stirling|위치=London|언어=la|출판사=William Bowyer|url=http://gallica.bnf.fr/ark:/12148/bpt6k62011b}}</ref><ref name="Boyadzhiev">{{저널 인용|이름=Khristo N.|성=Boyadzhiev|제목=Close encounters with the Stirling numbers of the second kind|날짜=2012|저널=Mathematics Magazine|권=85|호=4|쪽=252&ndash;266|zbl=1260.11016|doi=10.4169/math.mag.85.4.252|언어=en}}</ref> 닐스 닐센({{llang|de| Niels Nielsen}})이 1965년에 이 수들을 "스털링 수"라고 이름붙였다.<ref name="Boyadzhiev"/><ref>{{서적 인용|제목=Die Gammafunktion|url=https://archive.org/details/diegammafunktion00niel|이름=Niels|성=Nielsen|날짜=1965|언어=de}}</ref>

== 각주 ==
{{각주}}
* {{서적 인용|이름=Louis|성=Comtet|제목=Advanced combinatorics: The art of finite and infinite expansions|출판사=Reidel Publishing Company|위치=Dordrecht|날짜=1974|zbl= 0283.05001|언어=en}}
* {{서적 인용 | last=Graham | first=Ronald L. | 공저자=[[도널드 커누스|Donald E. Knuth]], Oren Patashnik |title= Concrete mathematics: a foundation for computer science | 판=2판 | publisher=Addison-Wesley Professional| 날짜=1994 | isbn=0-201-55802-5 | mr=1397498|zbl=0836.00001|언어=en }}
* {{저널 인용|이름=Arthur T.|성=Benjamin|공저자=Gregory O. Preston, Jennifer J. Quinn|url=http://www.math.hmc.edu/~benjamin/papers/harmonic.pdf|제목=A Stirling encounter with harmonic numbers|날짜=2002|저널=Mathematics Magazine|권=75|호=2|쪽=95&ndash;103|zbl=1063.05002|언어=en|확인날짜=2014-04-12|보존url=https://web.archive.org/web/20090617002133/http://www.math.hmc.edu/~benjamin/papers/harmonic.pdf|보존날짜=2009-06-17|url-status=dead}}
* {{저널 인용|제목=Close encounters with Stirling numbers of the second kind|url=https://archive.org/details/sim_mathematics-teacher_2012-11_106_4/page/n79|이름=Martin|성=Griffiths|저널=The Mathematics Teacher|권=106|호=4|날짜=2012-11|쪽=313–317|jstor=10.5951/mathteacher.106.4.0313|doi=10.5951/mathteacher.106.4.0313|언어=en}}

== 같이 보기 ==
* [[벨 수]]
* [[12정도]]

== 외부 링크 ==
* {{수학노트|title=스털링 수}}
* {{매스월드|id=StirlingNumberoftheFirstKind|title=Stirling number of the first kind}}
* {{매스월드|id=StirlingNumberoftheSecondKind|title=Stirling number of the second kind}}
* {{매스월드|id=AssociatedStirlingNumberoftheFirstKind|title=Associated Stirling number of the first kind}}

[[분류:순열]]
[[분류:계승과 이항식 주제]]
[[분류:정수열]]