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

結果

Stirling Number of the Second Kind S(5, 2)

ways to partition 5 labeled elements into 2 non-empty subsets

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 通りあるということです。