본문으로 이동

스털링 수

위키백과, 우리 모두의 백과사전.

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

정의

[편집]

제1종 스털링 수

[편집]
2개의 순환을 갖는, 4개의 원소의 순열은 총 11개가 있다. 따라서 이다.

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

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

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

부호 없는 제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개의 원소의 집합의 분할의 개수는 벨 수 개이다. 이 가운데, 분할된 부분집합들의 수가 m개인 경우는 제2종 스털링 수 에 의해 주어진다. 그림에 따라, , , , 이다.

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

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

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

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

제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

성질

[편집]

생성함수

[편집]

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

점화식

[편집]

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

합 공식

[편집]

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

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

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

특별한 값

[편집]

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

또한, 인 경우 스털링 수는 크로네커 델타 이다.

인 경우는 다음과 같다.

인 경우는 다음과 같다. 여기서 조화수이다.

인 경우는 스털링 수는 항상 1이다.

인 경우는 다음과 같다.

인 경우는 다음과 같다.

역사

[편집]

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

각주

[편집]
  1. Knuth, Donald (1992). “Two notes on notation”. 《American Mathematical Monthly》 (영어) 99 (5): 403–422. arXiv:math/9205211. Bibcode:1992math......5211K. Zbl 0785.05014. 
  2. Stirling, Jacobus. 《Methodus differentialis, sive tractatus de summatione et interpolatione serierum infinitarum》 (라틴어). London: William Bowyer. 
  3. Boyadzhiev, Khristo N. (2012). “Close encounters with the Stirling numbers of the second kind”. 《Mathematics Magazine》 (영어) 85 (4): 252–266. doi:10.4169/math.mag.85.4.252. Zbl 1260.11016. 
  4. Nielsen, Niels (1965). 《Die Gammafunktion》 (독일어). 

같이 보기

[편집]

외부 링크

[편집]