第二类斯特林数表计算器

第二类斯特林数表计算器

新兴 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} 或 S2(n,k)),表示把含有 n 个有标号(可区分)元素的集合,恰好划分为 k 个非空、无标号子集(称为"块")的方案数。本计算器会一次性算出完整的一行:对于给定的 n,依次列出 k = 0, 1, 2, …, 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·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,但在浮点运算中它会产生严重的抵消误差,因此我们采用基于精确整数的递推法。

广告
递推图,显示某格由其上方格和左上方格计算得出
每个值由上一行通过 S(n,k) = k·S(n-1,k) + S(n-1,k-1) 得到。

实例演算(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;数值会变得极其庞大,但得益于大整数运算,结果始终保持精确。

最后更新:

数学和统计热门计算器

查看全部数学和统计计算器