什麼是第二類斯特林數?
第二類斯特林數記作 \(S(n,k)\),用來計算「將 n 個相異(有標號)元素分割成恰好 k 個非空、無標號子集合」的方法數。它是組合數學中的基本量,常出現在集合分割、滿射函數以及貝爾數(Bell numbers)等問題中。這是一項純數學工具,在世界各地的運算方式完全相同。
如何使用本計算器
請輸入集合的大小 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 個元素的集合分成兩個非空群組,共有 15 種分法。
常見問題
為什麼 \(S(0,0)=1\)?依照慣例,空集合恰好有一種「分割成零個部分」的方式,也就是空分割。
當 \(k > n\) 時會怎樣?結果為 0,因為每個子集合都必須非空,而元素數量不足以填滿這麼多子集合。
它和貝爾數有什麼關係?將 \(S(n,k)\) 對所有 k(從 0 加到 n)求和,便會得到貝爾數 \(B(n)\),也就是 n 個元素的集合所有分割方式的總數。