Stirling数原理与应用

可视化演示

Stirling数分为第一类与第二类，分别描述排列与划分的计数。本文详解第一类Stirling数与排列的轮换计... 切换模式查看不同维度。

引子：从排队到分组

团建策划师小张手里有 n 位员工。老板说“拍张合影”，这就是排列：谁站第一个、谁站第二个，位置有序，所以 n 位员工里选 k 个排成一列有 P(n,k) 种。老板又说“挑几个人玩桌游”，这就是组合：只关心是哪几个人，不关心顺序，所以有 C(n,k) 种。可当老板说“把所有人分成几个旅行团，每个团内部还要围篝火坐成一圈”时，小张犯难了——这不是简单的排队或挑人，而是“先分组、再围圈”的复合问题。Stirling 数正是为这种问题而生。

排列与组合是计数世界的基础砖块，而 Stirling 数把它们向前推进了一大步。第二类 Stirling 数 S(n,k) 回答“把 n 个不同元素分成 k 个非空、无标签的组有多少种方式”，第一类 Stirling 数 c(n,k) 则回答“把 n 个不同元素分成 k 个围成圆圈的轮换有多少种方式”。两者的共同点是都要“分组”，区别在于分组之后组内是否需要围成圆圈、考虑圆桌上的相对顺序。

$$\displaystyle P(n,k)=\frac{n!}{(n-k)!},\qquad C(n,k)=\binom{n}{k}$$

1. 排列的分母：$$n!$$ 是所有员工的全排列数，除以 $$(n-k)!$$ 表示只安排前 k 个位置、其余 n-k 人不参与排队。

2. 排列的含义：$$\dfrac{n!}{(n-k)!}$$ 计算的是从 n 个不同元素中选 k 个并排成一列的方式数，等价于“第一个位置有 n 种选择，第二个有 n-1 种……逐位填空”。

3. 组合的除法：$$\binom{n}{k}$$ 等于排列数再除以 $$k!$$，因为选出的 k 个人不在乎内部顺序，所以要“抹掉” k! 种排队方式。

4. 对比的意义：P 强调“顺序”，C 强调“集合”，而 Stirling 数要在 C 的基础上再追问一句——分完组之后，组内要不要围圈、组与组之间认不认标签？

如果说排列是“拍合影”，组合是“圈名单”，那么 Stirling 数就是团建手册里最厚的那一章：它把“选人”升级为“组队”，把“组队”升级为“围圈”。接下来的两节，我们把这一章翻开来仔细读。

第一类Stirling数：篝火旁的圆桌

傍晚的篝火晚会开始了。小张要把 n 位员工分成 k 堆篝火，每堆围成一个圆圈坐下。这里有个关键规则：圆形座位没有“第一个位置”，整体旋转后大家相邻关系不变，算同一种坐法；但左右手互换的镜像算不同。这种“围成圆圈”的排列在数学上叫轮换，记作 (1 2 3) = (2 3 1)，但 (1 3 2) 是另一个轮换。第一类 Stirling 数 c(n,k) 统计的正是“n 个人分成 k 个轮换”的方案数。

当 k=1 时，n 个人围成一圈有 (n-1)! 种：先固定一个人当“圆心参照”，其余 n-1 人排成一列，圆圈的旋转等价性正好被抹去。当 k=n 时，每人自己一堆篝火，只有 1 种。这些边界条件让递推关系有了出发点。现在新员工入职，他要加入这场晚会：要么自己抱一捆柴，新开一堆篝火；要么插到某位老员工右手边的空位——而已经有 n-1 位老员工，所以有 n-1 个空位可选。

$$\displaystyle c(n,k)=c(n-1,k-1)+(n-1)\,c(n-1,k),\qquad c(n,1)=(n-1)!,\ c(n,n)=1$$

1. 两种去向相加：$$c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)$$，把新元素的所有可能分成“自立门户”与“加入旧圈”两类，互不重叠。

2. 自立门户：$$c(n-1,k-1)$$ 表示先让其余 n-1 人围成 k-1 堆，新员工单独一堆，自然凑成 k 堆。

3. 插入旧圈：$$c(n-1,k)$$ 表示其余 n-1 人已经围成 k 堆，此时新员工要插入其中一圈。

4. 系数来源：$$(n-1)$$ 是因为每个老员工右手边都有一个空位，n-1 个老员工就有 n-1 个插入位置，每个位置给出一种新坐法。

5. 边界条件：$$c(n,1)=(n-1)!$$ 是全员围一圈，$$c(n,n)=1$$ 是每人单独一圈。

从篝火晚会的角度看，第一类 Stirling 数就是在回答：“n 位员工按'围圈不按站位'的规则分成 k 堆，究竟有几种坐法？” 它比排列多了一层“圆桌去旋转”的智慧，又比组合多了一层“圈内相对顺序”的讲究。这份“圆桌账本”，在密码学分析随机置换时还会再次登场。

第二类Stirling数：旅行社的分组方案

第二天，团建改成了自由行。老板只提一个要求：n 位员工分成 k 个旅行团，每个团至少一人，团与团之间不编号——“一团”和“二团”只是叫法，交换名字不算新方案；同一个团里的人也不排先后。这种把集合拆成若干非空、无标签子集的操作，数学上叫集合划分。第二类 Stirling 数 S(n,k) 统计的正是“n 个不同元素分成 k 个非空块”的划分总数。

沿用新员工的思路来推导递推：新同事入职后，要么干脆自己成立一个独立小团，要么加入已有的 k 个团之一。注意，此时已有 k 个团，所以“加入”有 k 种选择——这正是与第一类 Stirling 数的关键差异：第一类系数是“人数 n-1”，第二类系数是“团数 k”。边界同样友好：全员一个团或每人一团，都只有 1 种方案。

$$\displaystyle S(n,k)=S(n-1,k-1)+k\,S(n-1,k),\qquad S(n,1)=S(n,n)=1$$

1. 递推拆解：$$S(n,k)=S(n-1,k-1)+k\,S(n-1,k)$$，把“n 人分 k 团”归结为“新员工到来之前”的两种状态。

2. 自立一团：$$S(n-1,k-1)$$ 对应其余 n-1 人已分成 k-1 团，新员工单独成团。

3. 加入老团：$$S(n-1,k)$$ 对应其余 n-1 人已分成 k 团，新员工必须进入其中一个。

4. 乘上 k：$$k\,S(n-1,k)$$ 中的系数 k 表示他有 k 个团可选择，三种不同选择产生三倍方案。

5. 边界条件：$$S(n,1)=S(n,n)=1$$ 给递推提供地基，类似杨辉三角最外层的两个 1。

第二类 Stirling 数就是“自由行分组账本”。它不考虑团内顺序，也不给团贴标签，只关心“哪些人在一起”。这份账本在机器学习中很有用——聚类的本质就是寻找一种“好的划分”，而 Stirling 数告诉我们所有可能划分的数量级，让你明白为什么穷举聚类方案是不可能的。

递推关系的构造：新同事的两种选择

把第一节和第二节的递推放在一起看，你会发现惊人的对称美。第一类：$c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)$，系数是“老员工人数”；第二类：$S(n,k)=S(n-1,k-1)+kS(n-1,k)$，系数是“已有团数”。差别的根源在于“加入”的语义：围篝火时新员工要在某个具体的人旁边坐下，所以有 n-1 个位置；进旅行团时只要挑一个团即可，所以有 k 个选择。这个构造性思想——“新元素要么自立，要么加入”——是整个递推表的发动机。

这种递推结构与帕斯卡三角（杨辉三角）异曲同工：每一行都由上一行“错位相加”生成，只是系数不再是 1 而是随行列变化的数。正因如此，我们可以像填乘法表一样把两个三角形表完整算出来。比如第二类三角形前几行是：n=3 时为 1,3,1；n=4 时为 1,7,6,1；n=5 时为 1,15,25,10,1。每一行两端是 1，中间的每个数都能从上一行两个数按规则算出。

$$\displaystyle S(5,3)=S(4,2)+3\,S(4,3)=7+3\times 6=25$$

1. 代入递推：$$S(5,3)=S(4,2)+3\,S(4,3)$$ 把规模从 5 降为 4，拆成“新员工自立”与“加入 3 个老团”两类。

2. 查上一行：$$S(4,2)=7$$ 表示 4 人分 2 团的方案数是 7；$$S(4,3)=6$$ 表示 4 人分 3 团的方案数是 6。

3. 加权合并：$$7+3\times 6$$ 中，3 是新人可选择的团数，6 种旧划分各放大 3 倍。

4. 计算结果：$$7+18=25$$ 表明 5 人分 3 团共有 25 种互不相同的划分方式。

递推表就像团建策划师的速查手册：有了它，任何规模的“分组围圈”问题都能像查字典一样快速得到答案，而不用真的把所有方案摆出来数一遍。这种“用上一行算下一行”的智慧，是动态规划算法最早的思想雏形之一。

贝尔数：所有团建方案的总和

老板突然问小张：“不管分几团，你总共有多少种分组方案？”这就是贝尔数（Bell number）要回答的问题：把 n 个不同元素的所有划分方案数加起来。记作 B_n，它等于 S(n,0)+S(n,1)+…+S(n,n)。拿 3 位员工举例：全员一团有 1 种（{123}），两人一团加一人单飞有 3 种（{12}{3}、{13}{2}、{23}{1}），每人一团有 1 种（{1}{2}{3}），所以 B_3=5。贝尔数像是一棵树的“总叶数”，把第二类 Stirling 数每行全部相加。

贝尔数还有一个优雅的递推公式，用“领队”来理解非常直观：请 n+1 位员工里的某位当领队，假设与他同团的还有 j 人，那么先从其余 n 人中选出这 j 人（$\binom{n}{j}$ 种），剩下 n-j 人随便分组（B_{n-j} 种）。对 j 求和，就得到递推式。这个公式把“划分”问题递归地拆成了“先选同团伙伴，再安排剩余的人”。

$$\displaystyle B_n=\sum_{k=0}^{n}S(n,k),\qquad B_{n+1}=\sum_{j=0}^{n}\binom{n}{j}B_{j}$$

1. 总账定义：$$B_n=\sum_{k=0}^{n}S(n,k)$$，其中 k 从 0 到 n 遍历所有可能的团数。

2. S(n,0) 的约定：当 n>0 时 $$S(n,0)=0$$，因为没有人却要分 0 团没有意义；而 $$B_0=1$$ 表示 0 个人只有“空划分”一种方案，它是递推的基石。

3. 领队选同伴：$$\binom{n}{j}$$ 表示先从其余 n 人中选出 j 人与领队同团。

4. 递归剩余：$$B_{j}$$ 实际是 $$B_{n-j}$$ 的另一种写法——剩下的 n-j 人随便分组，它的方案数正是贝尔数。

5. 对 j 求和：$$\sum_{j=0}^{n}$$ 遍历“领队所在团”的所有可能大小，把各类情况加起来。

贝尔数是“有多少种分组方式”的终极答案。在无监督学习中，聚类算法本质上就是在贝尔数规模的候选方案空间里寻找一个“好的划分”——贝尔数增长极快，B_10 就有 115975，这解释了为什么聚类必须靠启发式而非穷举。

显式公式：容斥原理揭开底牌

递推表虽好用，但若要一口算出 S(n,k)，我们需要显式公式。思路回到“球盒模型”：把 n 位员工看成 n 个球，把 k 个团看成 k 个编了号的盒子。允许空盒时，每位员工独立选择盒子，共有 $k^n$ 种分配。但这多算了两笔账：一是出现了空盒，二是盒子有编号而真实划分中团是无标签的。

先用容斥原理剔除空盒：从 k 个盒子中挑 i 个强迫为空，有 $\binom{k}{i}$ 种挑法，剩下 k-i 个盒子随便装，有 $(k-i)^n$ 种，并乘以 $(-1)^i$ 做奇偶抵消。这一步把“没有空盒”的方案精确打捞出来。最后再除以 $k!$：因为 k 个有标签盒子的全排列 $k!$ 种写法对应同一个无标签划分，所以除以 $k!$ 抹去标签。

$$\displaystyle S(n,k)=\frac{1}{k!}\sum_{i=0}^{k}(-1)^{i}\binom{k}{i}(k-i)^{n}$$

1. 总方案：$$k^n$$ 是 n 位员工每人任选一个编号盒子的所有方式，允许空盒。

2. 容斥变量：$$(-1)^{i}$$ 的符号交替出现，是容斥原理的“加加减减”：减掉有空盒的，加回空盒重叠的……

3. 选择空盒：$$\binom{k}{i}$$ 表示从 k 个盒子中挑出 i 个指定为空盒。

4. 剩余分配：$$(k-i)^n$$ 表示剩下 k-i 个盒子完全自由地接收 n 位员工。

5. 去标签：$$\dfrac{1}{k!}$$ 把 k! 种盒子编号方式合并为一种，因为真实旅行团没有“一号团、二号团”的区分。

以 S(4,2) 验证：$k=2$ 时原式等于 $\frac{1}{2}(2^4-2\times1^4+0)=7$，与递推表一致。显式公式就像团建的“万能模板”：不查表、不递推，直接代入 n 和 k 就能算出答案，是程序实现时的首选。

组合恒等式与应用：从计数到工具

Stirling 数不仅是计数器，更是组合数学的“语法”。第一个重要的恒等式是幂和展开：$x^n=\sum_{k=0}^{n}S(n,k)(x)_k$，其中 $(x)_k=x(x-1)\cdots(x-k+1)$ 是下降阶乘。它的组合解释很漂亮：把 n 位员工每人发一顶帽子，帽子共有 x 种颜色且允许同色——左边 $x^n$ 数的是所有染色方案；右边先把员工分成 k 个同色小组（S(n,k) 种），再给 k 个小组依次挑 x 种颜色中的 k 种不同颜色（$(x)_k$ 种）。

第二个恒等式是两类 Stirling 数的正交性：$\sum_{k=m}^{n}S(n,k)\,c(k,m)=\delta_{nm}$，当且仅当 n=m 时为 1，否则为 0。这就像同一批员工的两份档案——“分组账本”和“围圈账本”——互为逆变换，组合起来可以互相校验、互推公式。

$$\displaystyle x^{n}=\sum_{k=0}^{n}S(n,k)\,(x)_{k},\qquad \sum_{k=m}^{n}S(n,k)\,c(k,m)=\delta_{nm}$$

1. 左侧计数：$$x^{n}$$ 是 n 位员工每人从 x 种颜色里挑一顶帽子的染色总数。

2. 分组：$$S(n,k)$$ 先把员工按“同色”分成 k 个无标签小组。

3. 下降阶乘：$$(x)_{k}=x(x-1)\cdots(x-k+1)$$ 表示依次给 k 个小组挑互不相同的颜色，挑过的颜色不能再选。

4. 正交记号：$$\delta_{nm}$$ 是克罗内克函数，n=m 时取 1，否则取 0。

5. 求和范围：$$\sum_{k=m}^{n}$$ 表示遍历中间所有可能的团数，两类 Stirling 数在这一路上恰好“一进一出”互相抵消。

这些恒等式让 Stirling 数成为算法设计与概率统计的常客：在分析随机置换的轮换个数时，第一类 Stirling 数给出精确分布；在计算生日问题、占位问题等概率模型时，第二类 Stirling 数提供计数基础；在密码学中分析伪随机置换的轮换结构时，两类 Stirling 数更是不可或缺。

---

AI 应用场景

Python 演示

from math import comb, factorialfrom functools import lru_cache  @lru_cache(maxsize=None)def s2(n, k):    """第二类 Stirling 数 S(n,k): n 个元素分成 k 个非空无标签块"""    if k == 0 or k > n:        return 1 if n == 0 and k == 0 else 0    if k == 1 or k == n:        return 1    return s2(n - 1, k - 1) + k * s2(n - 1, k)  @lru_cache(maxsize=None)def s1(n, k):    """无符号第一类 Stirling 数 c(n,k): n 个元素分成 k 个轮换"""    if k == 0 or k > n:        return 1 if n == 0 and k == 0 else 0    if k == n:        return 1    return s1(n - 1, k - 1) + (n - 1) * s1(n - 1, k)  def bell(n):    """贝尔数: n 个元素所有划分方案的总数"""    return sum(s2(n, k) for k in range(n + 1))  def explicit_s2(n, k):    """用容斥显式公式计算 S(n,k)，与递推结果互相验证"""    total = 0    for i in range(k + 1):        total += (-1) ** i * comb(k, i) * (k - i) ** n    return total // factorial(k)  if __name__ == "__main__":    print("第二类 S(n,k) 三角表:")    for n in range(6):        print(n, [s2(n, k) for k in range(n + 1)])     print("第一类 c(n,k) 三角表:")    for n in range(6):        print(n, [s1(n, k) for k in range(n + 1)])     print("贝尔数 B_1..B_8:", [bell(n) for n in range(1, 9)])    print("S(8,3) 递推 =", s2(8, 3), " 容斥公式 =", explicit_s2(8, 3))

1. @lru_cache(maxsize=None)给递归函数装上“记忆手环”，避免重复计算同一个 (n,k)，就像查表而不是从头枚举。
2. if k == 1 or k == n: return 1边界条件：全员一团或每人一团都只有 1 种分法。
3. s2(n - 1, k - 1) + k * s2(n - 1, k)第二类递推：新元素自立一团，或加入已有 k 个团之一。
4. s1(n - 1, k - 1) + (n - 1) * s1(n - 1, k)第一类递推：新元素自立一圈，或插到 n-1 个老员工右手边的空位。
5. sum(s2(n, k) for k in range(n + 1))贝尔数就是第二类 Stirling 数按行求和，把“按团数分列”的账本叠成总账。
6. (-1) ** i * comb(k, i) * (k - i) ** n容斥公式的单次迭代：选 i 个空盒并加/减符号。
7. total // factorial(k)除以 k! 去掉盒子标签，把“有编号盒子”还原成“无标签旅行团”。

常见误区

面试题