什麼是第二類斯特林數?
第二類斯特林數記作 \(S(n,k)\)(也常寫成 {n 上 k} 或 \(S_2(n,k)\)),用來計算把一個含 \(n\) 個「有標記」(可區分)元素的集合,分割成恰好 \(k\) 個「非空且無標記」子集(稱為區塊,block)的方法數。本計算器會一次算出整列數值:固定 \(n\) 後,依序列出 \(k = 0, 1, 2, \ldots, n\) 的所有 \(S(n,k)\),也就是斯特林三角形第 \(n\) 列的每一項。這是純數學中的組合量,與任何國家或地區無關,全世界通用。
使用方法
輸入一個非負整數 \(n\)(集合中的元素個數)後送出即可。工具會回傳一張兩欄表格,分別列出 \(k\) 與 \(S(n,k)\),並附上該列總和,也就是貝爾數 \(B(n)\),可方便你快速驗算結果是否正確。所有數值皆以任意精度大整數運算,因此即使數字大到遠超過 64 位元整數所能容納的範圍(大約在 \(n = 20\)~\(25\) 時就會發生),結果仍然完全精確。
公式說明
最穩定的算法是遞迴式 $$S(n,k) = k\cdot S(n-1,k) + S(n-1,k-1)$$ 由基底 \(S(0,0) = 1\) 逐步建立。邊界值為:當 \(n \ge 1\) 時 \(S(n,0) = 0\);\(S(n,n) = 1\);當 \(n \ge 1\) 時 \(S(n,1) = 1\);當 \(k > n\) 時 \(S(n,k) = 0\)。此外還有一個顯式封閉公式 $$S(n,k) = \frac{1}{k!} \cdot \sum (-1)^{k-j} \binom{k}{j} j^n$$ 但用浮點數計算時會產生嚴重的相消誤差,因此本工具改採以精確整數運算的遞迴式。
實例演算(n = 5)
第 5 列為:\(k=0 \to 0\)、\(k=1 \to 1\)、\(k=2 \to 15\)、\(k=3 \to 25\)、\(k=4 \to 10\)、\(k=5 \to 1\)。以第 4 列 \(= [0,1,7,6,1]\) 來驗算:$$S(5,2) = 2\cdot 7 + 1 = 15$$ $$S(5,3) = 3\cdot 6 + 7 = 25$$ $$S(5,4) = 4\cdot 1 + 6 = 10$$ 整列總和為 \(0+1+15+25+10+1 = 52\),正好等於貝爾數 \(B(5) = 52\)。
第二類斯特林三角形(第 0–8 列)與貝爾數
第二類斯特林數 \(S(n,k)\) 計算將一個含 \(n\) 個相異元素的集合,分割成恰好 \(k\) 個非空、無標記子集的方法數。每個元素遵循遞迴式 \(S(n,k) = k\,S(n-1,k) + S(n-1,k-1)\),其中 \(S(0,0)=1\),且對 \(n\ge 1\) 有 \(S(n,0)=0\)。每列的總和為貝爾數 \(B(n)=\sum_{k=0}^{n} S(n,k)\),即 \(n\) 元素集合的所有分割總數。
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 列總和 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 |
空白格代表 \(k>n\) 的位置,依定義其值為零。
如何閱讀此表
- 遞迴式的實例檢查:\(S(8,3) = 3\cdot S(7,3) + S(7,2) = 3\cdot 301 + 63 = 903 + 63 = 966\)。
- 另一個檢查:\(S(8,4) = 4\cdot S(7,4) + S(7,3) = 4\cdot 350 + 301 = 1400 + 301 = 1701\)。
- \(n=5\) 的列總和檢查:\(0+1+15+25+10+1 = 52 = B(5)\)。
- 邊界值:\(S(n,1)=1\) 且 \(S(n,n)=1\);另外 \(S(n,2)=2^{n-1}-1\)(例如 \(S(8,2)=127\))。
常見問題
為什麼當 \(n \ge 1\) 時 \(S(n,0) = 0\)?因為你無法把一個非空集合分割成零個區塊;只有空集合才有「空分割」,因此 \(S(0,0) = 1\)。
列總和代表什麼?把所有 \(k\) 的 \(S(n,k)\) 加總起來,就會得到貝爾數 \(B(n)\),也就是 \(n\) 元素集合的所有分割方式總數。
n 最大可以多大?本工具最多支援到 \(n = 200\);雖然數值會變得非常龐大,但拜大整數運算之賜,結果依然精確無誤。