이 문서는 토막글입니다.
이 문서는 토막글로 분류되는 800바이트 이하의 문서입니다. 토막글을 채우는 것은 기여자의 따뜻한 손길입니다. 이 틀을 적용할 시 틀의 매개변수로 분류:토막글의 하위 분류 중 적절한 분류를 지정해 주시기 바랍니다.
이 문서는 토막글로 분류되는 800바이트 이하의 문서입니다. 토막글을 채우는 것은 기여자의 따뜻한 손길입니다. 이 틀을 적용할 시 틀의 매개변수로 분류:토막글의 하위 분류 중 적절한 분류를 지정해 주시기 바랍니다.
Stirling numbers of the second kind
1 개요
원소의 개수가 n인 집합을 구분되지 않는 k개의 집합으로 분할하는 방법의 수로 [math] S \left(n,k\right) [/math] 로 나타낸다. 이 수의 합이 벨 수와 관련이 있다. 참고로 제1종 스털링 수의 기호는 S를 소문자로 바꾸어 쓴 것이다.
어느 대학교에서 MT를 n명이 갔는데 방을 k개 잡아버렸다. 그런데 방 1개에 적어도 1명은 들어가야 한다.
이 때 가능한 경우의 수가 [math] S \left(n,k\right) [/math]이다.
2 성질
- [math] S\left(n,k\right)=S\left(n-1,k-1\right)+kS\left(n-1,k\right) [/math]
위의 MT를 예시로 들면 어느 1명이 있다고 하자.이 1명이 혼자 있을지, 아니면 다른사람이 있는 방에 들어갈지 선택 하게 하자. 만약 혼자 있는다고 하면 방은 구분되지 않으므로 그냥 [math]S\left(n-1,k-1\right)[/math]다. 하지만 다른 사람이 있는 방에 들어간다고 하면 우선 1번을 넘어간뒤 2번을 고르게 하자. 이런 식으로 우선 모든 사람이 방을 고르게 한 뒤 1번에게 남은 방중 1개를 고르라고 하자. 그러면 [math] S\left(n-1,k\right)\times k[/math]다. 따라서 [math] S\left(n,k\right)=S\left(n-1,k-1\right)+kS\left(n-1,k\right) [/math]
- [math]\displaystyle \ S\left(n, k\right) = {1\over k!}\sum_{r=0}^{k-1}\binom{k}{r}\left(-1\right)^r\left(k-r\right)^n [/math]