第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}\) や \(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\) に一致します。

広告

第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 まで指定できます。値は非常に大きくなりますが、多倍長整数による計算のおかげで常に正確です。

最終更新:

数学と統計で人気の電卓

数学と統計の電卓をすべて見る