斯特林数
第二类斯特林数（Stirling Number）
为什么先介绍第二类斯特林数
虽然被称作「第二类」，第二类斯特林数却在斯特林的相关著作和具体数学中被首先描述，同时也比第一类斯特林数常用得多．
第二类斯特林数 （斯特林子集数）{𝑛𝑘}{nk}
，也可记做 𝑆(𝑛,𝑘)S(n,k)，表示将 𝑛n 个两两不同的元素，划分为 𝑘k 个互不区分的非空子集的方案数．
递推式
{𝑛𝑘}={𝑛−1𝑘−1}+𝑘{𝑛−1𝑘}{nk}={n−1k−1}+k{n−1k}
边界是 {𝑛0} =[𝑛 =0]{n0}=[n=0]．
考虑用组合意义来证明．
我们插入一个新元素时，有两种方案：
- 将新元素单独放入一个子集，有 {𝑛−1𝑘−1}{n−1k−1} 种方案；
- 将新元素放入一个现有的非空子集，有 𝑘{𝑛−1𝑘}k{n−1k} 种方案．
根据加法原理，将两式相加即可得到递推式．
通项公式
{𝑛𝑚}=𝑚∑𝑖=0(−1)𝑚−𝑖𝑖𝑛𝑖!(𝑚−𝑖)!{nm}=∑i=0m(−1)m−iini!(m−i)!
使用容斥原理证明该公式．设将 𝑛n 个两两不同的元素，划分到 𝑖i 个两两不同的集合（允许空集）的方案数为 𝐺𝑖Gi，将 𝑛n 个两两不同的元素，划分到 𝑖i 个两两不同的非空集合（不允许空集）的方案数为 𝐹𝑖Fi．
显然
𝐺𝑖=𝑖𝑛𝐺𝑖=𝑖∑𝑗=0(𝑖𝑗)𝐹𝑗Gi=inGi=∑j=0i(ij)Fj
根据二项式反演
𝐹𝑖=𝑖∑𝑗=0(−1)𝑖−𝑗(𝑖𝑗)𝐺𝑗=𝑖∑𝑗=0(−1)𝑖−𝑗(𝑖𝑗)𝑗𝑛=𝑖∑𝑗=0𝑖!(−1)𝑖−𝑗𝑗𝑛𝑗!(𝑖−𝑗)!Fi=∑j=0i(−1)i−j(ij)Gj=∑j=0i(−1)i−j(ij)jn=∑j=0ii!(−1)i−jjnj!(i−j)!
考虑 𝐹𝑖Fi 与 {𝑛𝑖}{ni} 的关系．第二类斯特林数要求集合之间互不区分，因此 𝐹𝑖Fi 正好就是 {𝑛𝑖}{ni} 的 𝑖!i! 倍．于是
{𝑛𝑚}=𝐹𝑚𝑚!=𝑚∑𝑖=0(−1)𝑚−𝑖𝑖𝑛𝑖!(𝑚−𝑖)!{nm}=Fmm!=∑i=0m(−1)m−iini!(m−i)!
同一行第二类斯特林数的计算
「同一行」的第二类斯特林数指的是，有着不同的 𝑖i，相同的 𝑛n 的一系列 {𝑛𝑖}{ni}．求出同一行的所有第二类斯特林数，就是对 𝑖 =0..𝑛i=0..n 求出了将 𝑛n 个不同元素划分为 𝑖i 个非空集的方案数．
根据上面给出的通项公式，卷积计算即可．该做法的时间复杂度为 𝑂(𝑛log𝑛)O(nlogn)．
下面的代码使用了名为 poly 的多项式类，仅供参考．
实现
---|---
实现
---|---
同一列第二类斯特林数的计算
「同一列」的第二类斯特林数指的是，有着不同的 𝑖i，相同的 𝑘k 的一系列 {𝑖𝑘}{ik}．求出同一列的所有第二类斯特林数，就是对 𝑖 =0..𝑛i=0..n 求出了将 𝑖i 个不同元素划分为 𝑘k 个非空集的方案数．
利用指数型生成函数计算．
一个盒子装 𝑖i 个物品且盒子非空的方案数是 [𝑖 >0][i>0]．我们可以写出它的指数型生成函数为 𝐹(𝑥) =+∞∑𝑖=1𝑥𝑖𝑖! =e𝑥 −1F(x)=∑i=1+∞xii!=ex−1．经过之前的学习，我们明白 𝐹𝑘(𝑥)Fk(x) 就是 𝑖i 个有标号物品放到 𝑘k 个有标号盒子里的指数型生成函数，那么除掉 𝑘!k! 就是 𝑖i 个有标号物品放到 𝑘k 个无标号盒子里的指数型生成函数．
{𝑖𝑘} =[𝑥𝑖𝑖!]𝐹𝑘(𝑥)𝑘!{ik}=[xii!]Fk(x)k!，𝑂(𝑛log𝑛)O(nlogn) 计算多项式幂即可．
另外，exp𝐹(𝑥) =+∞∑𝑖=0𝐹𝑖(𝑥)𝑖!expF(x)=∑i=0+∞Fi(x)i! 就是 𝑖i 个有标号物品放到任意多个无标号盒子里的指数型生成函数（EXP 通过每项除以一个 𝑖!i! 去掉了盒子的标号）．这其实就是贝尔数的生成函数．
这里涉及到很多「有标号」「无标号」的内容，注意辨析．
实现
---|---
## 第一类斯特林数（Stirling Number）
**第一类斯特林数** （斯特林轮换数）[𝑛𝑘][nk]，也可记做 𝑠(𝑛,𝑘)s(n,k)，表示将 𝑛n 个两两不同的元素，划分为 𝑘k 个互不区分的非空轮换的方案数．
一个轮换就是一个首尾相接的环形排列．我们可以写出一个轮换 [𝐴,𝐵,𝐶,𝐷][A,B,C,D]，并且我们认为 [𝐴,𝐵,𝐶,𝐷] =[𝐵,𝐶,𝐷,𝐴] =[𝐶,𝐷,𝐴,𝐵] =[𝐷,𝐴,𝐵,𝐶][A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]，即，两个可以通过旋转而互相得到的轮换是等价的．注意，我们不认为两个可以通过翻转而相互得到的轮换等价，即 [𝐴,𝐵,𝐶,𝐷] ≠[𝐷,𝐶,𝐵,𝐴][A,B,C,D]≠[D,C,B,A]．
### 递推式
[𝑛𝑘]=[𝑛−1𝑘−1]+(𝑛−1)[𝑛−1𝑘][nk]=[n−1k−1]+(n−1)[n−1k]
边界是 [𝑛0] =[𝑛 =0][n0]=[n=0]．
该递推式的证明可以考虑其组合意义．
我们插入一个新元素时，有两种方案：
* 将该新元素置于一个单独的轮换中，共有 [𝑛−1𝑘−1][n−1k−1] 种方案；
* 将该元素插入到任何一个现有的轮换中，共有 (𝑛 −1)[𝑛−1𝑘](n−1)[n−1k] 种方案．
根据加法原理，将两式相加即可得到递推式．
### 通项公式
第一类斯特林数没有实用的通项公式．
### 同一行第一类斯特林数的计算
类似第二类斯特林数，我们构造同行第一类斯特林数的生成函数，即
𝐹𝑛(𝑥) =𝑛∑𝑖=0[𝑛𝑖]𝑥𝑖Fn(x)=∑i=0n[ni]xi
根据递推公式，不难写出
𝐹𝑛(𝑥) =(𝑛 −1)𝐹𝑛−1(𝑥) +𝑥𝐹𝑛−1(𝑥)Fn(x)=(n−1)Fn−1(x)+xFn−1(x)
于是
𝐹𝑛(𝑥) =𝑛−1∏𝑖=0(𝑥 +𝑖) =(𝑥+𝑛−1)!(𝑥−1)!Fn(x)=∏i=0n−1(x+i)=(x+n−1)!(x−1)!
这其实是 𝑥x 的 𝑛n 次上升阶乘幂，记做 𝑥――𝑛xn―．这个东西自然是可以暴力分治乘 𝑂(𝑛log2𝑛)O(nlog2n) 求出的，但用上升幂相关做法可以 𝑂(𝑛log𝑛)O(nlogn) 求出，详情见 [多项式平移 | 连续点值平移](../../poly/shift/#同一行第一类无符号-stirling-数)．
### 同一列第一类斯特林数的计算
仿照第二类斯特林数的计算，我们可以用指数型生成函数解决该问题．注意，由于递推公式和行有关，我们不能利用递推公式计算同列的第一类斯特林数．
显然，单个轮换的指数型生成函数为
𝐹(𝑥) =𝑛∑𝑖=1(𝑖−1)!𝑥𝑖𝑖! =𝑛∑𝑖=1𝑥𝑖𝑖F(x)=∑i=1n(i−1)!xii!=∑i=1nxii
它的 𝑘k 次幂就是 [𝑖𝑘][ik] 的指数型生成函数，𝑂(𝑛log𝑛)O(nlogn) 计算即可．
实现
---|---
应用
上升幂与普通幂的相互转化
我们记上升阶乘幂 𝑥――𝑛 =∏𝑛−1𝑘=0(𝑥 +𝑘)xn―=∏k=0n−1(x+k)．
则可以利用下面的恒等式将上升幂转化为普通幂：
𝑥――𝑛=∑𝑘[𝑛𝑘]𝑥𝑘xn―=∑k[nk]xk
如果将普通幂转化为上升幂，则有下面的恒等式：
𝑥𝑛=∑𝑘{𝑛𝑘}(−1)𝑛−𝑘𝑥――𝑘xn=∑k{nk}(−1)n−kxk―
下降幂与普通幂的相互转化
我们记下降阶乘幂 𝑥𝑛―― =𝑥!(𝑥−𝑛)! =∏𝑛−1𝑘=0(𝑥 −𝑘)xn―=x!(x−n)!=∏k=0n−1(x−k)．
则可以利用下面的恒等式将普通幂转化为下降幂：
𝑥𝑛=∑𝑘{𝑛𝑘}𝑥𝑘――xn=∑k{nk}xk―
如果将下降幂转化为普通幂，则有下面的恒等式：
多项式下降阶乘幂表示与多项式点值表示的关系
在这里，多项式的下降阶乘幂表示就是用
𝑓(𝑥)=𝑛∑𝑖=0𝑏𝑖𝑥𝑖――f(x)=∑i=0nbixi―
的形式表示一个多项式，而点值表示就是用 𝑛 +1n+1 个点
(𝑖,𝑎𝑖),𝑖=0..𝑛(i,ai),i=0..n
来表示一个多项式．
显然，下降阶乘幂 𝑏b 和点值 𝑎a 间满足这样的关系：
𝑎𝑘=𝑛∑𝑖=0𝑏𝑖𝑘𝑖――ak=∑i=0nbiki―
即
𝑎𝑘=𝑛∑𝑖=0𝑏𝑖𝑘!(𝑘−𝑖)!𝑎𝑘𝑘!=𝑘∑𝑖=0𝑏𝑖1(𝑘−𝑖)!ak=∑i=0nbik!(k−i)!akk!=∑i=0kbi1(k−i)!
这是一个卷积形式的式子，我们可以在 𝑂(𝑛log𝑛)O(nlogn) 的时间复杂度内完成点值和下降阶乘幂的互相转化．
习题
参考资料与注释
- Stirling Number of the First Kind - Wolfram MathWorld
- Stirling Number of the Second Kind - Wolfram MathWorld
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, Enter-tainer, Fei Natsuka, StudyingFather, Tiphereth-A, Xeonacid, MegaOwIer, sshwy, iamtwz, ksyx, caijianhong, CCXXXI, Great-designer, H-J-Granger, isdanni, Konano, LLLMMKK, Menci, purple-vine, shuzhouliu, YanagiOrigami 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用