第二類斯特林數表計算器

第二類斯特林數表計算器

成長中 AI Skill PRO

輸入計算

數學公式

S(n,k)=k·S(n−1,k)+S(n−1,k−1)S(\text{n},k) = k\cdot S(\text{n}-1,\,k) + S(\text{n}-1,\,k-1)
使用統計

廣告

結果

貝爾數 B(n) = 第 n 列總和
115975
n = 10 · 筆: 11 (k = 0 .. 10)
k S(n, k)
0 0
1 1
2 511
3 9330
4 34105
5 42525
6 22827
7 5880
8 750
9 45
10 1

回報本頁錯誤

什麼是第二類斯特林數?

第二類斯特林數記作 \(S(n,k)\)(也常寫成 {n 上 k} 或 \(S_2(n,k)\)),用來計算把一個含 \(n\) 個「有標記」(可區分)元素的集合,分割成恰好 \(k\) 個「非空且無標記」子集(稱為區塊,block)的方法數。本計算器會一次算出整列數值:固定 \(n\) 後,依序列出 \(k = 0, 1, 2, \ldots, n\) 的所有 \(S(n,k)\),也就是斯特林三角形第 \(n\) 列的每一項。這是純數學中的組合量,與任何國家或地區無關,全世界通用。

圖示用彩色環將含 5 個點的集合分成 2 個非空群組
\(S(n,k)\) 表示將 \(n\) 個相異物件分成 \(k\) 個非空無標號群組的方法數。

使用方法

輸入一個非負整數 \(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$$ 但用浮點數計算時會產生嚴重的相消誤差,因此本工具改採以精確整數運算的遞迴式。

廣告
遞迴圖,顯示某格由其上方格與左上方格計算得出
每個值由上一列透過 \(S(n,k) = k\cdot S(n-1,k) + S(n-1,k-1)\) 求得。

實例演算(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\);雖然數值會變得非常龐大,但拜大整數運算之賜,結果依然精確無誤。

最後更新:

數學和統計熱門計算器

查看全部數學和統計計算器