什么是第二类斯特林数?
第二类斯特林数记作 \(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\cdot 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\cdot S(4,2)+S(4,1)=2\cdot 7+1=15$$也就是说,把一个含 5 个元素的集合分成两个非空小组,共有 15 种方法。
第二类斯特林数 S(n,k) 表(n 从 0 到 10)
每个数值是将 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]\)(无符号),计算恰好有 k 个轮换的 n 个元素的排列数。它们满足不同的递推式 \(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\) 个元素的集合的全部划分总数。