제2종 스털링 수란?
제2종 스털링 수는 \(S(n,k)\)로 표기하며, 서로 다른(라벨이 붙은) n개의 원소로 이루어진 집합을 비어 있지 않은 라벨 없는 부분집합 정확히 k개로 나누는 경우의 수를 나타냅니다. 조합론의 핵심 개념으로, 집합 분할, 전사함수, 벨 수(Bell number)와 관련된 문제에서 자주 등장합니다. 순수 수학에서 정의되는 개념이므로 어느 나라에서나 동일하게 적용됩니다.
계산기 사용법
집합의 크기 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가지입니다.
0부터 10까지의 第2종 스털링 수 S(n,k) 표
각 항목은 n개의 구별 가능한 원소를 정확히 k개의 비어 있지 않은, 구별되지 않는 블록으로 나누는 방법의 수입니다. 이 표는 점화식 \(S(n,k)=k\cdot S(n-1,k)+S(n-1,k-1)\)으로 만들어지며, \(S(0,0)=1\)이고 \(n\ge 1\)일 때 \(S(n,0)=S(0,n)=0\)입니다. 빈 칸은 \(k>n\)인 경우로, 이때 S(n,k)=0입니다. 마지막 열은 행의 합, 즉 벨 수 B(n)입니다. 예를 들어 S(10,4) = 34105입니다.
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 행의 합 B(n) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | ||||||||||
| 1 | 0 | 1 | 1 | |||||||||
| 2 | 0 | 1 | 1 | 2 | ||||||||
| 3 | 0 | 1 | 3 | 1 | 5 | |||||||
| 4 | 0 | 1 | 7 | 6 | 1 | 15 | ||||||
| 5 | 0 | 1 | 15 | 25 | 10 | 1 | 52 | |||||
| 6 | 0 | 1 | 31 | 90 | 65 | 15 | 1 | 203 | ||||
| 7 | 0 | 1 | 63 | 301 | 350 | 140 | 21 | 1 | 877 | |||
| 8 | 0 | 1 | 127 | 966 | 1701 | 1050 | 266 | 28 | 1 | 4140 | ||
| 9 | 0 | 1 | 255 | 3025 | 7770 | 6951 | 2646 | 462 | 36 | 1 | 21147 | |
| 10 | 0 | 1 | 511 | 9330 | 34105 | 42525 | 22827 | 5880 | 750 | 45 | 1 | 115975 |
점화식으로 한 항목 확인: \(S(6,3)=3\cdot S(5,3)+S(5,2)=3\cdot 25+15=90\). 항상 \(S(n,1)=1\), \(S(n,2)=2^{n-1}-1\), \(S(n,n-1)=\binom{n}{2}\), \(S(n,n)=1\)입니다.
핵심 용어와 표기법
- 집합 분할
- 집합을 공집합이 아닌, 서로 겹치지 않는 부분집합(블록)들로 나누는 방법으로, 그 합집합이 전체 집합이 됩니다. 블록의 순서와 블록 안의 원소 순서는 중요하지 않습니다.
- 구별되는 블록 vs. 구별되지 않는 블록
- n개의 원소는 구별됩니다(예: 1, 2, …, n). k개의 부분집합은 구별되지 않습니다. 즉 두 블록을 서로 바꾸면 같은 분할이 됩니다. 블록에 번호를 붙인다면 개수는 대신 k!·S(n,k)가 됩니다.
- 공집합이 아닌 블록
- k개의 부분집합 각각은 최소 한 개의 원소를 포함해야 합니다. 그래서 n ≥ 1일 때 S(n,0)=0이고, k > n이면 S(n,k)=0입니다.
- 표기 S(n,k)
- 第2종 스털링 수로, \(\left\{ n \atop k \right\}\)로도 씁니다. 다음 식으로 계산합니다: \(S(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}\).
- 벨 수 B(n)
- n개 원소의 집합을 블록 개수에 상관없이 나누는 전체 분할의 수입니다: \(B(n)=\sum_{k=0}^{n}S(n,k)\). 처음 값들은 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975입니다.
- 이항 계수
- \(\binom{k}{j}=\frac{k!}{j!\,(k-j)!}\)로, k개 중 j개를 고르는 방법의 수입니다. 위의 포함-배제 공식에 등장합니다.
- 전사 함수(표면사상)
- n개 원소의 집합에서 k개 원소의 집합 위로 가는 함수로, k개 원소의 각 원소가 적어도 한 번은 대응되는 함수입니다. 그러한 함수의 수는 \(k!\cdot S(n,k)\)입니다. 정의역을 k개의 블록으로 나눈 뒤 블록들을 k개의 대상에 k!가지 방법으로 배정하기 때문입니다.
第2종 vs. 第1종. 第2종 스털링 수는 집합을 k개의 블록으로 나누는 분할의 수를 셉니다. 第1종 스털링 수는 \(c(n,k)\) 또는 \(\left[ n \atop k \right]\)(부호 없는 형태)로 쓰며, n개 원소의 순열 중 정확히 k개의 사이클을 갖는 것의 수를 셉니다. 이들은 다른 점화식 \(c(n,k)=(n-1)\,c(n-1,k)+c(n-1,k-1)\)을 따르며, 부호를 고려하면 第2종과 서로 역행렬 관계에 있습니다.
자주 묻는 질문
왜 \(S(0,0)=1\)인가요? 관례적으로 공집합을 0개의 부분으로 나누는 분할은 정확히 하나, 즉 빈 분할이 존재한다고 봅니다.
k가 n보다 크면 어떻게 되나요? 결과는 0입니다. 모든 부분집합은 비어 있지 않아야 하는데 원소가 너무 적기 때문입니다.
벨 수와는 어떤 관계가 있나요? k를 0부터 n까지 변화시키며 \(S(n,k)\)를 모두 더하면 벨 수 \(B(n)\)이 됩니다. 이는 n개의 원소로 이루어진 집합의 전체 분할 수를 뜻합니다.