제2종 스털링 수 계산기

이름표가 붙은 원소 n개짜리 집합을 공집합이 아닌 부분집합 «정확히 k개»로 나누는 방법의 수 S(n,k)입니다. {1,2,3,4}를 정확히 2덩어리로 나누는 방법은 {1}{2,3,4}, {2}{1,3,4}, {3}{1,2,4}, {4}{1,2,3}, {1,2}{3,4}, {1,3}{2,4}, {1,4}{2,3}로 정확히 7가지(S(4,2)=7)입니다.

벨 수 B(n)은 «몇 덩어리로 나누든 상관없이» 전부 센 것이고, 제2종 스털링 수는 그중 «딱 k덩어리로 나눈 것»만 골라 센 것입니다. 그래서 k=0부터 n까지 S(n,k)를 전부 더하면 B(n)이 됩니다 — 예를 들어 S(4,0)+S(4,1)+S(4,2)+S(4,3)+S(4,4) = 0+1+7+6+1 = 15 = B(4)입니다.

점화식 S(n,k) = k·S(n-1,k) + S(n-1,k-1)을 씁니다. n번째 원소 하나를 놓고, 이미 있는 k개 덩어리 중 하나에 끼워 넣거나(k가지 중 선택) 혼자 새 덩어리를 만드는(k-1덩어리에서 새 덩어리 하나 추가) 두 경우로 나눠 셉니다.

네. 점화식과는 완전히 다른 유도(포함배제 원리로 단사가 아닌 함수를 걸러내는 방법)로도 계산해 대조했습니다. S(n,k) = (1/k!)·Σ(-1)ʲ·C(k,j)·(k-j)ⁿ라는 식인데, 부호가 계속 바뀌는 항들을 더하는데도 점화식과 정확히 같은 값이 나오는지 넓은 구간에서 확인했습니다.

이름이 비슷하지만 전혀 다릅니다. edu/stirling-cycle은 «스털링 열기관 사이클»(열역학)을 다루는 도구이고, 이 계산기가 다루는 «제2종 스털링 수»는 조합론에서 쓰는 수입니다. 둘 다 19세기 수학자 제임스 스털링의 이름을 땄을 뿐 서로 관계가 없습니다.

아니요. 모든 계산은 브라우저 안에서만 이뤄지며 서버로 전송되지 않습니다.