第二类斯特林数 S(n,k) 计算器

第二类斯特林数 S(n,k) 计算器

增长中 AI Skill PRO

输入计算

数学公式

S(n,k)=1k!∑j=0k(−1)j(kj)(k−j)nS\!\left(\text{n},\,\text{k}\right) = \frac{1}{\text{k}!}\sum_{j=0}^{\text{k}} (-1)^{j}\binom{\text{k}}{j}\left(\text{k}-j\right)^{\text{n}}
使用统计

广告

结果

第二类斯特林数 S(5, 2)
15
将有标号的元素划分为非空子集的方法数 (元素: 5 · 子集: 2)
n(集合大小) 5
k(子集数) 2
记号 S(n, k)

报告本页错误

什么是第二类斯特林数?

第二类斯特林数记作 \(S(n,k)\),表示把 \(n\) 个互不相同(有标记)的元素,恰好划分成 \(k\) 个非空、无标记子集的方案数。它是组合数学中的基础概念,广泛出现在集合划分、满射计数以及贝尔数等问题中。这是一个纯数学工具,在任何国家、任何场景下的算法都完全一致。

四个有标号的球分入两个无标号的箱中,展示一种集合划分
\(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)\) 值组成的三角形,每个值都由其上方的两个值得到。

第二类斯特林数 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\) 个元素的集合的全部划分总数。

最后更新:

数学和统计热门计算器

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