제2종 스털링 수란?
제2종 스털링 수는 \(S(n,k)\)로 표기하며(\({n \atop k}\) 또는 \(S_2(n,k)\)로 쓰기도 합니다), n개의 구분 가능한(라벨이 붙은) 원소로 이루어진 집합을 정확히 k개의 비어 있지 않은 부분집합(블록이라고 부릅니다)으로 나누는 경우의 수를 세는 값입니다. 단, 부분집합 자체에는 라벨이 없습니다. 이 계산기는 한 행 전체를 계산합니다. 즉 고정된 n에 대해 k = 0, 1, 2, ..., n까지 \(S(n,k)\) 값을 모두 나열해, 스털링 삼각형 n행의 모든 항을 보여 줍니다. 지역이나 국가와 무관한 순수 조합론의 양입니다.
사용 방법
0 이상의 정수 n(집합의 원소 개수)을 입력하고 실행하세요. 계산기는 k와 \(S(n,k)\) 두 열로 구성된 표를 반환하며, 여기에 행 합인 벨 수 \(B(n)\)도 함께 보여 줍니다. 벨 수는 결과가 맞는지 빠르게 확인하는 좋은 수단입니다. 모든 값은 임의 정밀도 정수로 계산되므로, 64비트 정수 범위를 훌쩍 넘어 커지더라도(대략 n = 20~25부터 그렇습니다) 정확한 값을 그대로 유지합니다.
공식 설명
가장 안정적인 방법은 점화식 $$S(n,k) = k\cdot S(n-1,k) + S(n-1,k-1)$$이며, 기본값 \(S(0,0) = 1\)에서 출발해 차근차근 쌓아 올립니다. 경계값은 \(n \ge 1\)일 때 \(S(n,0) = 0\), \(S(n,n) = 1\), \(n \ge 1\)일 때 \(S(n,1) = 1\), 그리고 \(k > n\)일 때 \(S(n,k) = 0\)입니다. 한편 닫힌 형태의 명시적 공식 $$S(n,k) = \frac{1}{k!} \cdot \sum (-1)^{k-j} C(k,j)\, j^n$$도 있지만, 부동소수점으로 계산하면 큰 자릿수 상쇄가 일어나므로, 이 계산기는 정확한 정수 연산을 사용하는 점화식 방식을 택했습니다.
풀이 예시 (n = 5)
5행은 다음과 같습니다. k=0 → 0, k=1 → 1, k=2 → 15, k=3 → 25, k=4 → 10, k=5 → 1. 4행 = [0,1,7,6,1]에서 검산해 보면 \(S(5,2) = 2\cdot 7 + 1 = 15\), \(S(5,3) = 3\cdot 6 + 7 = 25\), \(S(5,4) = 4\cdot 1 + 6 = 10\)입니다. 행의 합은 \(0+1+15+25+10+1 = 52\)이며, 이는 벨 수 \(B(5) = 52\)와 일치합니다.
자주 묻는 질문
왜 \(n \ge 1\)일 때 \(S(n,0) = 0\)인가요? 비어 있지 않은 집합을 0개의 블록으로 나누는 것은 불가능합니다. 공집합만이 빈 분할을 가지므로 \(S(0,0) = 1\)이 됩니다.
행의 합은 무엇을 의미하나요? 모든 k에 대해 \(S(n,k)\)를 더하면 벨 수 \(B(n)\)이 되며, 이는 n개 원소 집합을 분할하는 전체 경우의 수입니다.
n은 얼마나 클 수 있나요? 이 계산기는 n = 200까지 허용합니다. 값이 매우 커지지만, 큰 정수 연산 덕분에 항상 정확하게 유지됩니다.
