斯特林数

第二类斯特林数（Stirling Number）

第二类斯特林数（斯特林子集数），也可记做 ，表示将 个两两不同的元素，划分为 个互不区分的非空子集的方案数。

递推式

边界是 。

考虑用组合意义来证明。

我们插入一个新元素时，有两种方案：

• 将新元素单独放入一个子集，有 种方案；
• 将新元素放入一个现有的非空子集，有 种方案。

根据加法原理，将两式相加即可得到递推式。

通项公式

使用容斥原理证明该公式。设将 个两两不同的元素，划分到 个两两不同的集合（允许空集）的方案数为 ，将 个两两不同的元素，划分到 个两两不同的非空集合（不允许空集）的方案数为 。

显然

根据二项式反演

考虑 与 的关系。第二类斯特林数要求集合之间互不区分，因此 正好就是 的 倍。于是

同一行第二类斯特林数的计算

“同一行”的第二类斯特林数指的是，有着不同的 ，相同的 的一系列 。求出同一行的所有第二类斯特林数，就是对 求出了将 个不同元素划分为 个非空集的方案数。

根据上面给出的通项公式，卷积计算即可。该做法的时间复杂度为 。

下面的代码使用了名为 poly 的多项式类，仅供参考。

同一列第二类斯特林数的计算

“同一列”的第二类斯特林数指的是，有着不同的 ，相同的 的一系列 。求出同一列的所有第二类斯特林数，就是对 求出了将 个不同元素划分为 个非空集的方案数。

利用指数型生成函数计算。

一个盒子装 个物品且盒子非空的方案数是 。我们可以写出它的指数型生成函数为 。经过之前的学习，我们明白 就是 个有标号物品放到 个有标号盒子里的指数型生成函数，那么除掉 就是 个有标号物品放到 个无标号盒子里的指数型生成函数。

， 计算多项式幂即可。

另外， 就是 个有标号物品放到任意多个无标号盒子里的指数型生成函数（EXP 通过每项除以一个 去掉了盒子的标号）。这其实就是贝尔数的生成函数。

这里涉及到很多“有标号”“无标号”的内容，注意辨析。

第一类斯特林数（Stirling Number）

第一类斯特林数（斯特林轮换数），也可记做 ，表示将 个两两不同的元素，划分为 个互不区分的非空轮换的方案数。

一个轮换就是一个首尾相接的环形排列。我们可以写出一个轮换 ，并且我们认为 ，即，两个可以通过旋转而互相得到的轮换是等价的。注意，我们不认为两个可以通过翻转而相互得到的轮换等价，即 。

递推式

边界是 。

该递推式的证明可以考虑其组合意义。

我们插入一个新元素时，有两种方案：

• 将该新元素置于一个单独的轮换中，共有 种方案；
• 将该元素插入到任何一个现有的轮换中，共有 种方案。

根据加法原理，将两式相加即可得到递推式。

通项公式

第一类斯特林数没有实用的通项公式。

同一行第一类斯特林数的计算

类似第二类斯特林数，我们构造同行第一类斯特林数的生成函数，即

根据递推公式，不难写出

于是

这其实是 的 次上升阶乘幂，记做 。这个东西自然是可以暴力分治乘 求出的，但用上升幂相关做法可以 求出。

同一列第一类斯特林数的计算

仿照第二类斯特林数的计算，我们可以用指数型生成函数解决该问题。注意，由于递推公式和行有关，我们不能利用递推公式计算同列的第一类斯特林数。

显然，单个轮换的指数型生成函数为

它的 次幂就是 的指数型生成函数， 计算即可。

应用

上升幂与普通幂的相互转化

我们记上升阶乘幂 。

则可以利用下面的恒等式将上升幂转化为普通幂：

如果将普通幂转化为上升幂，则有下面的恒等式：

下降幂与普通幂的相互转化

我们记下降阶乘幂 。

则可以利用下面的恒等式将普通幂转化为下降幂：

如果将下降幂转化为普通幂，则有下面的恒等式：

多项式下降阶乘幂表示与多项式点值表示的关系

在这里，多项式的下降阶乘幂表示就是用

的形式表示一个多项式，而点值表示就是用 个点

来表示一个多项式。

显然，下降阶乘幂 和点值 间满足这样的关系：

即

这是一个卷积形式的式子，我们可以在 的时间复杂度内完成点值和下降阶乘幂的互相转化。

习题

• HDU3625 Examining the Rooms
• UOJ540 联合省选 2020 组合数问题
• UOJ269 清华集训 2016 如何优雅地求和

参考资料与注释

1. Stirling Number of the First Kind - Wolfram MathWorld
2. Stirling Number of the Second Kind - Wolfram MathWorld