제2종 스털링 수 S(n,k) 계산기

결과

Stirling Number of the Second Kind S(5, 2)

ways to partition 5 labeled elements into 2 non-empty subsets

n (집합 크기)	5
k (부분집합)	2
표기법	S(n, k)

제2종 스털링 수란?

제2종 스털링 수는 $S(n,k)$로 표기하며, 서로 다른(라벨이 붙은) n개의 원소로 이루어진 집합을 비어 있지 않은 라벨 없는 부분집합 정확히 k개로 나누는 경우의 수를 나타냅니다. 조합론의 핵심 개념으로, 집합 분할, 전사함수, 벨 수(Bell number)와 관련된 문제에서 자주 등장합니다. 순수 수학에서 정의되는 개념이므로 어느 나라에서나 동일하게 적용됩니다.

라벨이 있는 공 4개를 라벨 없는 통 2개에 나눠 담은, 집합 분할의 한 예 — $S(n,k)$는 라벨이 있는 n개의 항목을 비어 있지 않은 k개의 라벨 없는 그룹으로 나누는 경우의 수를 셉니다.

계산기 사용법

집합의 크기 n과 부분집합의 개수 k를 입력하세요. 두 값 모두 음이 아닌 정수여야 합니다. 계산 버튼을 누르면 분할의 정확한 경우의 수인 $S(n,k)$가 나옵니다. k가 n보다 크면 결과는 0이 됩니다. 원소 수보다 많은 비어 있지 않은 부분집합을 채울 수는 없기 때문입니다.

공식 설명

명시적 형태는 $$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j} j^{n}$$로, 여기서 $\binom{k}{j}$는 이항계수입니다. 이와 동등하면서 수치적으로 더 안전한 방법은 점화식 $$S(n,k) = k\cdot S(n-1,k) + S(n-1,k-1)$$을 쓰는 것입니다. 초기 조건은 $S(0,0)=1$, $n>0$일 때 $S(n,0)=0$, $k>0$일 때 $S(0,k)=0$입니다. 이 계산기는 부동소수점 상쇄 오차를 피하기 위해 점화식을 사용합니다. 유용한 특수한 경우로는 $S(n,1)=1$, $S(n,n)=1$, $S(n,2)=2^{n-1}-1$이 있습니다.

예제 풀이

n=5, k=2인 경우를 살펴봅시다. 특수한 경우 공식을 쓰면 $$S(5,2)=2^{5-1}-1=16-1=15$$입니다. 점화식으로도 확인할 수 있습니다. $$S(5,2)=2\times S(4,2)+S(4,1)=2\times 7+1=15.$$ 따라서 5개의 원소로 이루어진 집합을 비어 있지 않은 두 그룹으로 나누는 방법은 15가지입니다.