什么是第二类斯特林数?
第二类斯特林数记作 S(n,k)(也写成 {n 取 k} 或 S2(n,k)),表示把含有 n 个有标号(可区分)元素的集合,恰好划分为 k 个非空、无标号子集(称为"块")的方案数。本计算器会一次性算出完整的一行:对于给定的 n,依次列出 k = 0, 1, 2, …, n 对应的 S(n,k),也就是斯特林三角形第 n 行的全部数值。它是一个纯数学的组合量,与任何国家或地区的规则无关,全球通用。
使用方法
输入一个非负整数 n(即集合中的元素个数)并提交即可。工具会返回一张包含两列的表格:k 与 S(n,k),同时给出该行的行和,也就是贝尔数 B(n)——这是一个方便的校验值。所有结果都用任意精度大整数计算,因此即便数值远超 64 位整数所能表示的范围(大约在 n = 20–25 时就会出现),结果依然保持精确。
公式详解
最稳健的方法是使用递推式 S(n,k) = k·S(n-1,k) + S(n-1,k-1),从初始条件 S(0,0) = 1 逐层构建。边界值为:当 n ≥ 1 时 S(n,0) = 0;S(n,n) = 1;当 n ≥ 1 时 S(n,1) = 1;当 k > n 时 S(n,k) = 0。此外还有一个显式闭式公式 S(n,k) = (1/k!) · Σ (-1)^(k-j) C(k,j) j^n,但在浮点运算中它会产生严重的抵消误差,因此我们采用基于精确整数的递推法。
实例演算(n = 5)
第 5 行为:k=0 → 0,k=1 → 1,k=2 → 15,k=3 → 25,k=4 → 10,k=5 → 1。可由第 4 行 [0,1,7,6,1] 验证:S(5,2) = 2·7 + 1 = 15,S(5,3) = 3·6 + 7 = 25,S(5,4) = 4·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 ≥ 1 时 S(n,0) = 0?因为无法把一个非空集合划分成零个块;只有空集本身拥有"空划分",所以 S(0,0) = 1。
行和是什么?把 S(n,k) 对所有 k 求和,得到的就是贝尔数 B(n),即含 n 个元素的集合的全部划分总数。
n 最大能取多少?本工具支持 n 最大到 200;数值会变得极其庞大,但得益于大整数运算,结果始终保持精确。