第2種スターリング数とは
第2種スターリング数は \(S(n,k)\)(\({n \atop k}\) や \(S2(n,k)\) とも表記)と書き、n 個の区別できる(ラベル付きの)要素を、空でない k 個の「組」(ブロック、こちらは区別しない)にちょうど分割する場合の数を表します。この計算機は行全体をまとめて計算します。すなわち n を固定したとき、k = 0, 1, 2, …, n に対する \(S(n,k)\) をすべて列挙し、スターリングの三角形の第 n 行をすべて表示します。これは純粋に数学的な組合せ量であり、国や地域による違いはありません。
使い方
0 以上の整数 n(集合の要素数)を入力して計算します。k と \(S(n,k)\) の 2 列からなる表に加え、行の合計値も表示されます。この合計はベル数 \(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 \geq 1\) のとき \(S(n,0) = 0\)、\(S(n,n) = 1\)、\(n \geq 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\) に一致します。
第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 \geq 1\) のとき \(S(n,0) = 0\) なのですか? 空でない集合を 0 個のブロックに分割することはできないからです。空の分割を持つのは空集合だけで、その場合に \(S(0,0) = 1\) となります。
行の合計は何を表しますか? \(S(n,k)\) をすべての k について足し合わせるとベル数 \(B(n)\)、すなわち n 要素の集合の分割の総数が得られます。
n はどこまで大きくできますか? 本ツールでは n = 200 まで指定できます。値は非常に大きくなりますが、多倍長整数による計算のおかげで常に正確です。