什麼是第二類斯特林數?
第二類斯特林數記作 \(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\)。
常見問題
為什麼當 \(n \ge 1\) 時 \(S(n,0) = 0\)?因為你無法把一個非空集合分割成零個區塊;只有空集合才有「空分割」,因此 \(S(0,0) = 1\)。
列總和代表什麼?把所有 \(k\) 的 \(S(n,k)\) 加總起來,就會得到貝爾數 \(B(n)\),也就是 \(n\) 元素集合的所有分割方式總數。
n 最大可以多大?本工具最多支援到 \(n = 200\);雖然數值會變得非常龐大,但拜大整數運算之賜,結果依然精確無誤。