第二類斯特林數 S(n,k) 計算器

第二類斯特林數 S(n,k) 計算器

成長中 AI Skill PRO

輸入計算

數學公式

S(n,k)=1k!∑j=0k(−1)j(kj)(k−j)nS\!\left(\text{n},\,\text{k}\right) = \frac{1}{\text{k}!}\sum_{j=0}^{\text{k}} (-1)^{j}\binom{\text{k}}{j}\left(\text{k}-j\right)^{\text{n}}
使用統計

廣告

結果

第二類斯特林數 S(5, 2)
15
將有標號的元素劃分為非空子集的方法數 (元素: 5 · 子集: 2)
n(集合大小) 5
k(子集合) 2
符號表示 S(n, k)

回報本頁錯誤

什麼是第二類斯特林數?

第二類斯特林數記作 \(S(n,k)\),用來計算「將 n 個相異(有標號)元素分割成恰好 k 個非空、無標號子集合」的方法數。它是組合數學中的基本量,常出現在集合分割、滿射函數以及貝爾數(Bell numbers)等問題中。這是一項純數學工具,在世界各地的運算方式完全相同。

四個有標號的球分入兩個無標號的箱中,展示一種集合分割
\(S(n,k)\) 計算把 n 個有標號物件分成 k 個非空無標號組的方法數。

如何使用本計算器

請輸入集合的大小 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(n,k)\) 值組成的三角形,每個值都由其上方的兩個值得到。

第 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 個元素的集合所有分割方式的總數。

最後更新:

數學和統計熱門計算器

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