第2種スターリング数とは
第2種スターリング数(記号 \(S(n,k)\))は、n 個の区別できる(ラベル付きの)要素からなる集合を、空でない k 個の区別しない部分集合にちょうど分割する場合の数を表します。組合せ論における基本的な量であり、集合の分割、全射の数え上げ、ベル数などの問題に登場します。これは純粋数学の概念であり、国や地域を問わず同じように成り立つツールです。
計算ツールの使い方
集合の要素数 n と、分割する部分集合の個数 k を入力してください。いずれも非負整数である必要があります。「計算」を押すと、分割の正確な総数 \(S(n,k)\) が得られます。k が n より大きい場合、結果は 0 になります。要素の数より多くの「空でない部分集合」を作ることはできないためです。
公式の解説
明示的な公式は次のとおりです。$$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j} j^{n}$$ここで \(C(k,j)\) は二項係数です。これと同値で、数値計算上より安全な方法が次の漸化式です。$$S(n,k) = k\,S(n-1,k) + S(n-1,k-1)$$初期条件は \(S(0,0)=1\)、n>0 のとき \(S(n,0)=0\)、k>0 のとき \(S(0,k)=0\) です。本ツールでは、浮動小数点演算による桁落ちを避けるため、この漸化式を用いて計算しています。覚えておくと便利な特殊値として、\(S(n,1)=1\)、\(S(n,n)=1\)、\(S(n,2)=2^{n-1}-1\) があります。
計算例
n=5、k=2 の場合を考えます。特殊値の公式を使うと $$S(5,2)=2^{5-1}-1=16-1=15$$ となります。漸化式でも確認できます。$$S(5,2)=2\times S(4,2)+S(4,1)=2\times 7+1=15$$ つまり、5 個の要素からなる集合を、空でない 2 つのグループに分ける方法は 15 通りあるということです。
第2種スターリング数 S(n,k)の表(n = 0~10)
各値は、n個の区別可能な要素の集合を、ちょうどk個の空でない、順序のないブロックに分割する方法の数です。この表は漸化式 \(S(n,k)=k\cdot S(n-1,k)+S(n-1,k-1)\) から作られ、\(S(0,0)=1\)、\(n\ge 1\) のとき \(S(n,0)=S(0,n)=0\) です。空欄のセルは \(k>n\) を表し、このとき S(n,k)=0 です。最後の列は行の合計であり、ベル数 B(n) になります。例えば、S(10,4) = 34105 です。
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 行の合計 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 | ||
| 9 | 0 | 1 | 255 | 3025 | 7770 | 6951 | 2646 | 462 | 36 | 1 | 21147 | |
| 10 | 0 | 1 | 511 | 9330 | 34105 | 42525 | 22827 | 5880 | 750 | 45 | 1 | 115975 |
漸化式による1つの値の確認:\(S(6,3)=3\cdot S(5,3)+S(5,2)=3\cdot 25+15=90\)。常に \(S(n,1)=1\)、\(S(n,2)=2^{n-1}-1\)、\(S(n,n-1)=\binom{n}{2}\)、\(S(n,n)=1\) が成り立ちます。
主な用語と記法
- 集合の分割
- 集合を、空でない互いに素な部分集合(ブロック)に分け、それらの和集合が元の集合全体になるようにすること。ブロックの順番やブロック内の要素の順番は問題にしません。
- ラベル付きとラベルなし
- n個の要素はラベル付き(区別可能、例:1, 2, …, n)です。k個の部分集合はラベルなしで、2つのブロックを入れ替えても同じ分割とみなします。ブロックにラベルが付いている場合、その数は代わりに k!·S(n,k) になります。
- 空でないブロック
- k個の部分集合はそれぞれ少なくとも1つの要素を含まなければなりません。このため、n ≥ 1 のとき S(n,0)=0 であり、k > n のとき S(n,k)=0 となります。
- 記法 S(n,k)
- 第2種スターリング数のことで、\(\left\{ n \atop k \right\}\) とも書かれます。次の式で計算されます:\(S(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}\)。
- ベル数 B(n)
- n個の要素からなる集合を、任意の個数のブロックに分割する場合の総数です:\(B(n)=\sum_{k=0}^{n}S(n,k)\)。最初の値は 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975 です。
- 二項係数
- \(\binom{k}{j}=\frac{k!}{j!\,(k-j)!}\)。k個から j個を選ぶ方法の数です。上記の包除原理の式に現れます。
- 全射(サージェクション)
- n個の集合から k個の集合への関数であり、k個の集合の各要素が少なくとも1回は写されるもの。そのような関数の数は \(k!\cdot S(n,k)\) です。定義域を k個のブロックに分け、そのブロックを k個の対象へ k! 通りの方法で割り当てるためです。
第2種と第1種の違い。 第2種スターリング数は、集合を k個のブロックに分割する方法を数えます。第1種スターリング数は \(c(n,k)\) または \(\left[ n \atop k \right]\)(符号なし)と書かれ、n個の要素の順列のうち、ちょうど k個のサイクルを持つものを数えます。両者は異なる漸化式 \(c(n,k)=(n-1)\,c(n-1,k)+c(n-1,k-1)\) に従い、符号を含めると互いに逆行列の関係にあります。
よくある質問
なぜ \(S(0,0)=1\) なのですか? 慣例として、空集合を 0 個の部分に分割する方法はちょうど 1 通り(空の分割)と定められているためです。
k > n のときはどうなりますか? すべての部分集合は空であってはならず、要素の数が足りないため、結果は 0 になります。
ベル数とはどう関係しますか? \(S(n,k)\) を k=0 から n まですべて合計するとベル数 \(B(n)\) が得られます。これは n 個の要素からなる集合の分割の総数です。