제2종 스털링 수 표 계산기

제2종 스털링 수 표 계산기

신흥 AI Skill PRO

계산 입력

공식

S(n,k)=k·S(n−1,k)+S(n−1,k−1)S(\text{n},k) = k\cdot S(\text{n}-1,\,k) + S(\text{n}-1,\,k-1)
사용 통계

광고

결과

벨 수 B(n) = n행의 합
115975
n = 10 · 개 항목: 11 (k = 0 .. 10)
k S(n, k)
0 0
1 1
2 511
3 9330
4 34105
5 42525
6 22827
7 5880
8 750
9 45
10 1

이 페이지의 오류 신고

제2종 스털링 수란?

제2종 스털링 수는 \(S(n,k)\)로 표기하며(\({n \atop k}\) 또는 \(S_2(n,k)\)로 쓰기도 합니다), n개의 구분 가능한(라벨이 붙은) 원소로 이루어진 집합을 정확히 k개의 비어 있지 않은 부분집합(블록이라고 부릅니다)으로 나누는 경우의 수를 세는 값입니다. 단, 부분집합 자체에는 라벨이 없습니다. 이 계산기는 한 행 전체를 계산합니다. 즉 고정된 n에 대해 k = 0, 1, 2, ..., n까지 \(S(n,k)\) 값을 모두 나열해, 스털링 삼각형 n행의 모든 항을 보여 줍니다. 지역이나 국가와 무관한 순수 조합론의 양입니다.

5개의 점 집합을 색색의 고리로 비어 있지 않은 두 그룹으로 나눈 도표
\(S(n,k)\)는 서로 다른 n개의 대상을 비어 있지 않은 라벨 없는 k개의 그룹으로 나누는 경우의 수입니다.

사용 방법

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$$도 있지만, 부동소수점으로 계산하면 큰 자릿수 상쇄가 일어나므로, 이 계산기는 정확한 정수 연산을 사용하는 점화식 방식을 택했습니다.

광고
한 칸이 위 칸과 왼쪽 위 칸에서 계산되는 점화식 도표
각 항은 윗줄로부터 \(S(n,k) = k\cdot S(n-1,k) + S(n-1,k-1)\)로 만들어집니다.

풀이 예시 (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\)와 일치합니다.

광고

제2종 스털링 삼각형(0행–8행)과 벨 수

제2종 스털링 수 \(S(n,k)\)는 \(n\)개의 서로 다른 원소로 이루어진 집합을 정확히 \(k\)개의 공집합이 아닌, 라벨이 없는 부분집합으로 나누는 방법의 수를 센다. 각 항은 점화식 \(S(n,k) = k\,S(n-1,k) + S(n-1,k-1)\)을 따르며, \(S(0,0)=1\)이고 \(n\ge 1\)일 때 \(S(n,0)=0\)이다. 행의 합은 벨 수 \(B(n)=\sum_{k=0}^{n} S(n,k)\)이며, 이는 \(n\)개 원소로 이루어진 집합의 전체 분할 수이다.

n \ k 0 1 2 3 4 5 6 7 8 행의 합 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

빈 칸은 \(k>n\)인 위치로, 정의상 0이다.

표 읽는 방법

  • 점화식의 검산: \(S(8,3) = 3\cdot S(7,3) + S(7,2) = 3\cdot 301 + 63 = 903 + 63 = 966\)
  • 또 다른 검산: \(S(8,4) = 4\cdot S(7,4) + S(7,3) = 4\cdot 350 + 301 = 1400 + 301 = 1701\)
  • \(n=5\)일 때의 행 합 검산: \(0+1+15+25+10+1 = 52 = B(5)\)
  • 가장자리: \(S(n,1)=1\)이고 \(S(n,n)=1\)이며, 또한 \(S(n,2)=2^{n-1}-1\)이다(예: \(S(8,2)=127\)).

자주 묻는 질문

왜 \(n \ge 1\)일 때 \(S(n,0) = 0\)인가요? 비어 있지 않은 집합을 0개의 블록으로 나누는 것은 불가능합니다. 공집합만이 빈 분할을 가지므로 \(S(0,0) = 1\)이 됩니다.

행의 합은 무엇을 의미하나요? 모든 k에 대해 \(S(n,k)\)를 더하면 벨 수 \(B(n)\)이 되며, 이는 n개 원소 집합을 분할하는 전체 경우의 수입니다.

n은 얼마나 클 수 있나요? 이 계산기는 n = 200까지 허용합니다. 값이 매우 커지지만, 큰 정수 연산 덕분에 항상 정확하게 유지됩니다.

최종 업데이트:

수학 및 통계 인기 계산기

수학 및 통계 계산기 전체 보기