第2種スターリング数 S(n,k) の計算

第2種スターリング数 S(n,k) の計算

成長中 AI Skill PRO

計算を入力してください

公式

S(n,k)=1k!∑j=0k(−1)j(kj)(k−j)nS\!\left(\text{n},\,\text{k}\right) = \frac{1}{\text{k}!}\sum_{j=0}^{\text{k}} (-1)^{j}\binom{\text{k}}{j}\left(\text{k}-j\right)^{\text{n}}
利用統計

広告

結果

第2種スターリング数 S(5, 2)
15
区別できる要素を空でない部分集合に分ける方法の数 (要素: 5 · 部分集合: 2)
n(要素数) 5
k(部分集合) 2
記号 S(n, k)

このページの誤りを報告

第2種スターリング数とは

第2種スターリング数(記号 \(S(n,k)\))は、n 個の区別できる(ラベル付きの)要素からなる集合を、空でない k 個の区別しない部分集合にちょうど分割する場合の数を表します。組合せ論における基本的な量であり、集合の分割、全射の数え上げ、ベル数などの問題に登場します。これは純粋数学の概念であり、国や地域を問わず同じように成り立つツールです。

4個のラベル付きボールを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 通りあるということです。

パスカルの三角形のように並べた小さなスターリング数の三角形グリッド
\(S(n,k)\) の値からなる三角形。各値はすぐ上の2つの値から作られます。

第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 個の要素からなる集合の分割の総数です。

最終更新:

数学と統計で人気の電卓

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