什麼是第二類斯特林數?
第二類斯特林數記作 \(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 種分法。
第 0 至 10 列的第二類斯特靈數 S(n,k) 表
每個值表示將 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 |
以遞迴式檢查一項:\(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 個子集是無標號的:交換兩個區塊會得到相同的劃分。若區塊是有標號的,計數會變成 k!·S(n,k)。
- 非空區塊
- k 個子集中的每一個都必須至少包含一個元素。這就是為什麼當 n ≥ 1 時 S(n,0)=0,且當 k > n 時 S(n,k)=0。
- 記號 S(n,k)
- 第二類斯特靈數,也可寫作 \(\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 元集合中的每個元素至少被映到一次。這類函數的個數為 \(k!\cdot S(n,k)\):先把定義域劃分成 k 個區塊,再以 k! 種方式將這些區塊指派給 k 個目標。
第二類與第一類。 第二類斯特靈數計算將集合劃分成 k 個區塊的方法數。第一類斯特靈數寫作 \(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\)?依照慣例,空集合恰好有一種「分割成零個部分」的方式,也就是空分割。
當 \(k > n\) 時會怎樣?結果為 0,因為每個子集合都必須非空,而元素數量不足以填滿這麼多子集合。
它和貝爾數有什麼關係?將 \(S(n,k)\) 對所有 k(從 0 加到 n)求和,便會得到貝爾數 \(B(n)\),也就是 n 個元素的集合所有分割方式的總數。