斯特林数计算器

欢迎使用斯特林数计算器，这是一个专门用于计算第一类斯特林数（无符号——圆排列）和第二类斯特林数（将集合划分为非空子集）的全面组合数学工具。本计算器具有交互式三角形可视化、逐步递归推导、柱状分布图以及深度的组合数学解释，旨在为需要快速、准确结果及教育背景信息的学生、教育工作者、研究人员和竞赛程序员提供帮助。

什么是斯特林数？

斯特林数是在组合数学、代数和分析中自然产生的两类数。它们以苏格兰数学家詹姆斯·斯特林（James Stirling, 1692–1770）的名字命名，是连接阶乘、二项式系数和多项式恒等式的桥梁。虽然它们不如帕斯卡三角形那样广为人知，但它们同样基础，并广泛出现于离散数学中。

第一类斯特林数

无符号第一类斯特林数，记作 \(|s(n,k)|\) 或 \(\left[{n \atop k}\right]\)，用于计算将 \(n\) 个元素分解为恰好 \(k\) 个不相交圆排列（轮换）的排列数量。

直观理解： 考虑元素 \(n\) 的去向。要么它被插入到现有的圆排列中（共有 \(n-1\) 个位置可以插入，即每个原有元素之前各有一个位置）——贡献项 \((n-1)\cdot|s(n-1,k)|\)；要么它自成一个新的单元素圆排列，贡献项 \(|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}}\) （递降阶乘幂）

概率与统计

斯特林数出现在计算概率分布的矩中，特别是在普通矩和阶乘矩之间进行转换时。它们在随机排列分析和占用问题研究中至关重要。

计算机科学

在算法分析中，斯特林数用于计算将对象分配到容器中的方法数、哈希表分析以及随机排列研究。第二类斯特林数直接关系到满射函数的计数：从 n 元集到 k 元集的满射函数数量为 \(k!\, S(n,k)\)。

数论

斯特林数与贝尔努利数、调和数以及各种求和恒等式相关。它们出现在有限差分计算和欧拉-麦克劳林公式中。

常见问题解答

什么是第一类斯特林数？

无符号第一类斯特林数，记作 |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。第一类斯特林数通常通过递归关系或递升阶乘幂的展开来计算。

附加资源

• 第一类斯特林数 - 维基百科
• 第二类斯特林数 - 维基百科
• OEIS A008277 - 第二类斯特林数
• OEIS A130534 - 无符号第一类斯特林数