斯特林數計算機

歡迎使用斯特林數計算機。這是一個全面的組合學工具，用於計算第一類斯特林數（無符號——排列中的循環）和第二類斯特林數（劃分為非空子集的集合）。本計算機具有交互式三角形視覺化、逐步遞迴推導、條形圖分佈和深入的組合學解釋，專為需要快速、準確結果及教學背景的學生、教育工作者、研究人員和競賽編程人員設計。

什麼是斯特林數？

斯特林數是在組合學、代數和分析中自然產生的兩類數列。它們以蘇格蘭數學家詹姆斯·斯特林（James Stirling, 1692–1770）的名字命名，連接著階乘、二項式係數和多項式恆等式。雖然它們不像帕斯卡三角形那樣廣為人知，但它們同樣重要，並貫穿於離散數學中。

第一類斯特林數

無符號第一類斯特林數，記作 \(|s(n,k)|\) 或 \(\left[{n \atop k}\right]\)，計算將 \(n\) 個元素分解為恰好 \(k\) 個不相交循環的排列數量。

直觀理解： 考慮元素 \(n\) 的去向。它要麼被插入到現有的循環中（有 \(n-1\) 個位置可以插入，即在其他 \(n-1\) 個元素中的每一個之前）——對應 \((n-1)\cdot|s(n-1,k)|\) 項；要麼它自己形成一個新的 1-循環——對應 \(|s(n-1,k-1)|\) 項。

關鍵事實：

• \(|s(n,1)| = (n-1)!\) — 圓排列（一個大循環）
• \(|s(n,n)| = 1\) — 恆等排列（所有元素都是不動點）
• \(|s(n,n-1)| = \binom{n}{2}\) — 一個對換
• \(\sum_{k=0}^{n} |s(n,k)| = n!\) — 排列的總數

第二類斯特林數

第二類斯特林數，記作 \(S(n,k)\) 或 \(\left\{{n \atop k}\right\}\)，計算將 \(n\) 個元素的集合劃分為恰好 \(k\) 個非空子集的方法數。

直觀理解： 考慮元素 \(n\) 的去向。它要麼加入 \(k\) 個現有子集中的一個（有 \(k\) 種選擇）——對應 \(k \cdot S(n-1,k)\) 項；要麼它自己形成一個新的單元素子集——對應 \(S(n-1,k-1)\) 項。

關鍵事實：

• \(S(n,1) = 1\) — 只有一種方法：所有元素在一個集合中
• \(S(n,n) = 1\) — 只有一種方法：每個元素都是一個單元素集
• \(S(n,2) = 2^{n-1} - 1\) — 分成兩個非空子集的方法數
• \(S(n,n-1) = \binom{n}{2}\) — 選擇哪一對元素共享同一個子集
• \(\sum_{k=0}^{n} S(n,k) = B(n)\) — 第 \(n\) 個貝爾數

顯式公式（第二類）

如何使用此計算機

1. 輸入 n： 元素總數（0 到 200）。
2. 輸入 k： 循環數量（第一類）或子集數量（第二類），滿足 0 ≤ k ≤ n。
3. 選擇種類： 選擇第一類、第二類或兩者，以便進行並排對比。
4. 計算： 點擊「計算斯特林數」查看結果，包括逐步推導、三角形視覺化和分佈圖。

對比：第一類 vs 第二類

斯特林數的應用

多項式轉換

斯特林數連接了不同的多項式基底：

• 遞增階乘：\(x^{(n)} = \sum_{k} |s(n,k)|\, x^k\)
• 普通冪：\(x^n = \sum_{k} S(n,k)\, x^{\underline{k}}\) (遞降階乘)

概率與統計

斯特林數出現在計算概率分佈的矩中，特別是在普通矩與階乘矩之間的轉換。它們在隨機排列和佔用問題（occupancy problems）的分析中至關重要。

計算機科學

在演算法分析中，斯特林數用於計算將物件分配到容器中的方式、雜湊表分析以及隨機排列的研究。第二類斯特林數直接關係到滿射函數計數：從 n 元集到 k 元集的滿射函數數量為 \(k!\, S(n,k)\)。

數論

斯特林數與伯努利數、調和數以及各種求和恆等式相關聯。它們出現在有限差分微積分和歐拉-麥克勞林公式（Euler-Maclaurin formula）中。

常見問題解答

什麼是第一類斯特林數？

無符號第一類斯特林數，記作 |s(n,k)|，用於計算將 n 個元素分解為恰好 k 個不相交循環的排列數量。它們滿足遞迴關係 |s(n,k)| = (n−1)·|s(n−1,k)| + |s(n−1,k−1)|，且 |s(0,0)| = 1。每一行的總和為 n!，因為每個排列都有一定數量的循環。

什麼是第二類斯特林數？

第二類斯特林數，記作 S(n,k)，用於計算將 n 個元素的集合劃分為恰好 k 個非空子集的方法數。它們滿足遞迴關係 S(n,k) = k·S(n−1,k) + S(n−1,k−1)，且 S(0,0) = 1。每一行的總和為貝爾數 B(n)。

第一類和第二類斯特林數有什麼區別？

第一類（無符號）計算具有 k 個循環的排列——每個循環內的順序很重要。第二類計算劃分為 k 個子集的集合劃分——子集內的順序不重要。它們透過矩陣求逆相關聯：有符號第一類數組成的三角形是第二類數三角形的逆矩陣。

斯特林數在數學中如何應用？

斯特林數出現在遞降/遞增階乘與普通冪之間的多項式轉換、計算概率分佈的矩、組合恆等式、數論以及演算法分析中。

斯特林數和貝爾數之間的關係是什麼？

第 n 個貝爾數 B(n) 等於第 n 行中所有第二類斯特林數的總和：B(n) = Σ S(n,k)，其中 k = 0 到 n。貝爾數計算將 n 個元素的集合劃分為任意數量非空子集的總方案數。

斯特林數有顯式公式嗎？

是的，第二類斯特林數有一個基於容斥原理的顯式公式：S(n,k) = (1/k!) Σ (−1)^(k−j) C(k,j) j^n，其中 j = 0 到 k。第一類斯特林數可以透過遞迴或透過與遞增階乘的聯繫來計算。

其他資源

• 第一類斯特林數 - 維基百科
• 第二類斯特林數 - 維基百科
• OEIS A008277 - 第二類斯特林數
• OEIS A130534 - 無符號第一類斯特林數