第2種スターリング数の表計算 - S(n,k)を高精度算出

結果

ベル数 B(n) = 第 n 行の合計

115975

n = 10 · 11 entries (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}$ や $S2(n,k)$ とも表記）と書き、n 個の区別できる（ラベル付きの）要素を、空でない k 個の「組」（ブロック、こちらは区別しない）にちょうど分割する場合の数を表します。この計算機は行全体をまとめて計算します。すなわち n を固定したとき、k = 0, 1, 2, …, n に対する $S(n,k)$ をすべて列挙し、スターリングの三角形の第 n 行をすべて表示します。これは純粋に数学的な組合せ量であり、国や地域による違いはありません。

5個の点の集合を色付きの輪で2つの空でないグループに分けた図 — $S(n,k)$ は、n個の異なる対象をk個の空でないラベルなしグループに分ける方法の数を表します。

使い方

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$$ も存在しますが、浮動小数点で計算すると大きな桁落ちが生じます。そのため本ツールでは整数のまま正確に計算できる漸化式を用いています。

あるセルが上のセルと左上のセルから計算される漸化式の図 — 各要素は上の行から $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$ に一致します。