OI-wiki 组合数学深度解析：第一类与第二类斯特林数（定义、递推、通项公式与多项式算法）

OI-wiki 组合数学深度解析：第一类与第二类斯特林数（定义、递推、通项公式与多项式算法）

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

本篇指南以 OI-wiki 组合数学板块的《斯特林数》文档为主体，系统讲解两类斯特林数的组合定义、递推式、通项公式、同行/同列整行计算的多项式算法及其在幂次转化、多项式表示互换中的应用。读完本文，你将掌握斯特林数的全部核心性质、容斥原理与二项式反演推导通项公式的完整路径，并能直接运行基于 NTT 与多项式 exp/log 的O(n log n)整行求解代码，用于组合计数类竞赛题与数学建模场景。

为什么先介绍第二类斯特林数

虽然被称作"第二类"，第二类斯特林数却在斯特林的相关著作与《具体数学》中被首先描述，同时也比第一类斯特林数常用得多。因此 OI-wiki 将第二类斯特林数作为本节的开篇内容，从它出发建立"集合划分"的组合直觉，再过渡到基于"轮换"的第一类斯特林数。

第二类斯特林数（斯特林子集数）

第二类斯特林数记作 $\begin{Bmatrix}n\ k\end{Bmatrix}$，也可记作 $S(n,k)$，表示将 $n$ 个两两不同的元素，划分为 $k$ 个互不区分的非空子集的方案数。

递推式

$$ \begin{Bmatrix}n\ k\end{Bmatrix}=\begin{Bmatrix}n-1\ k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\ k\end{Bmatrix} $$

边界为 $\begin{Bmatrix}n\ 0\end{Bmatrix}=[n=0]$（Iverson 括号，当且仅当 $n=0$ 时为 1）。

该递推式可以用组合意义证明。向 $n-1$ 个元素构成的划分中插入一个新元素时，只有两种方案：

• 将新元素单独放入一个新的子集：其余 $n-1$ 个元素需要划分成 $k-1$ 个非空子集，贡献 $\begin{Bmatrix}n-1\ k-1\end{Bmatrix}$ 种方案；
• 将新元素放入一个现有的非空子集：$n-1$ 个元素已划分成 $k$ 个非空子集，新元素有 $k$ 个可选的子集，贡献 $k\begin{Bmatrix}n-1\ k\end{Bmatrix}$ 种方案。

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

通项公式

$$ \begin{Bmatrix}n\m\end{Bmatrix}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!} $$

该公式使用容斥原理（相关基础见 OI-wiki 容斥原理）证明。设：

• $G_i$：将 $n$ 个两两不同的元素划分到 $i$ 个两两不同的集合（允许空集）的方案数；
• $F_i$：将 $n$ 个两两不同的元素划分到 $i$ 个两两不同的非空集合（不允许空集）的方案数。

显然每个元素可以独立选择进入 $i$ 个盒子之一，故 $G_i=i^n$。同时，从 $i$ 个盒子中挑选出 $j$ 个非空盒子，其余为空，可得

$$ G_i=\sum\limits_{j=0}^i\binom{i}{j}F_j $$

根据二项式反演：

$$ \begin{aligned} F_i&=\sum\limits_{j=0}^{i}(-1)^{i-j}\binom{i}{j}G_j\ &=\sum\limits_{j=0}^{i}(-1)^{i-j}\binom{i}{j}j^n\ &=\sum\limits_{j=0}^{i}\dfrac{i!(-1)^{i-j}j^n}{j!(i-j)!} \end{aligned} $$

最后考察 $F_i$ 与 $\begin{Bmatrix}n\i\end{Bmatrix}$ 的关系：第二类斯特林数要求集合之间互不区分，因此 $F_i$（有标号集合）恰好是 $\begin{Bmatrix}n\i\end{Bmatrix}$ 的 $i!$ 倍。于是

$$ \begin{Bmatrix}n\m\end{Bmatrix}=\dfrac{F_m}{m!}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!} $$

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

"同一行"的第二类斯特林数，指 $n$ 相同、$i$ 不同的一系列 $\begin{Bmatrix}n\i\end{Bmatrix}$。求出同一行的全部值，就是求 $i=0..n$ 时"将 $n$ 个不同元素划分为 $i$ 个非空子集"的全部方案数。

观察通项公式

$$ \begin{Bmatrix}n\i\end{Bmatrix}=\dfrac{1}{i!}\sum_{j=0}^{i}(-1)^{i-j}\binom{i}{j}j^n $$

其中求和部分是 $\dfrac{(-1)^{j}j^n}{j!}$ 与 $\dfrac{(-1)^{-i}}{(i-j)!}$ 的卷积，因此构造两个多项式一次乘法即可求出整行，时间复杂度 $O(n\log n)$（模 $998244353$ 意义下的 NTT，见下方poly类的乘法实现）。

OI-wiki 给出的参考实现分为两部分：多项式工具类poly与主程序。其中poly类来自 fstdlib 项目（Build v0.0.2），提供了 NTT 卷积乘法、inv（多项式求逆）、log（多项式对数）、exp（多项式指数）等基础操作，其核心乘法采用标准的 NTT 三步流程：位逆序重排（rev）→ 蝶形变换（dft_for_module）→ 点值相乘后逆变换并除以长度 $N$：

// poly 类（fstdlib，仅展示核心声明与 NTT 乘法） class poly { private: std::vector<int> data; public: poly(std::size_t len = std::size_t(0)) { data = std::vector<int>(len); } void resize(std::size_t len, int val = 0) { data.resize(len, val); } int &operator[](std::size_t b) { return data[b]; } poly operator*(const poly &h) const; poly operator*=(const poly &h); poly operator*(const int &h) const; poly operator+(const poly &h) const; poly operator-(const poly &h) const; poly inv(void) const; poly inv(const int &h) const; friend poly sqrt(const poly &h); friend poly log(const poly &h); friend poly exp(const poly &h); }; int qpow(int a, int b, int p = mod) { int res = 1; while (b) { if (b & 1) res = (ll)res * a % p; a = (ll)a * a % p, b >>= 1; } return res; } poly poly::operator*(const poly &h) const { int N = 1; while (N < (int)(size() + h.size() - 1)) N <<= 1; std::vector<int> f(this->data), g(h.data); f.resize(N), g.resize(N); rev.resize(N); for (int i = 0; i < N; ++i) rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? N >> 1 : 0); dft_for_module(f, N, 1), dft_for_module(g, N, 1); for (int i = 0; i < N; ++i) f[i] = (ll)f[i] * g[i] % mod; dft_for_module(f, N, -1), f.resize(size() + h.size() - 1); for (int i = 0, inv = qpow(N, mod - 2); i < (int)f.size(); ++i) f[i] = (ll)f[i] * inv % mod; return f; }

主程序部分，利用阶乘与阶乘逆元构造卷积的两个因子：$g_i = (-1)^i\cdot\dfrac{1}{i!}$，$f_i = i^n\cdot\dfrac{1}{i!}$，一次卷积后逐项输出即为 $\begin{Bmatrix}n\i\end{Bmatrix}$（乘上 $i!$ 之前的值对应 $\dfrac{F_i}{i!}$ 的卷积形式，代码直接输出f[i]即为答案）：

int main() { scanf("%d", &n); fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod; exgcd(fact[n], mod, ifact[n], ifact[0]), ifact[n] = (ifact[n] % mod + mod) % mod; for (int i = n - 1; i >= 0; --i) ifact[i] = (ll)ifact[i + 1] * (i + 1) % mod; poly f(n + 1), g(n + 1); for (int i = 0; i <= n; ++i) g[i] = (i & 1 ? mod - 1ll : 1ll) * ifact[i] % mod, f[i] = (ll)qpow(i, n) * ifact[i] % mod; f *= g, f.resize(n + 1); for (int i = 0; i <= n; ++i) printf("%d ", f[i]); return 0; }

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

"同一列"的第二类斯特林数，指 $k$ 相同、$i$ 不同的一系列 $\begin{Bmatrix}i\k\end{Bmatrix}$。求出同一列的全部值，就是求 $i=0..n$ 时"将 $i$ 个不同元素划分为 $k$ 个非空子集"的全部方案数。

这里采用指数型生成函数（EGF）求解。一个盒子装 $i$ 个物品且盒子非空的方案数是 $[i>0]$，其 EGF 为

$$ F(x)=\sum\limits_{i=1}^{+\infty}\dfrac{x^i}{i!} = \mathrm{e}^x-1 $$

$F^k(x)$ 就是 $i$ 个有标号物品放到 $k$ 个有标号盒子里的 EGF，再除以 $k!$ 即得 $i$ 个有标号物品放到 $k$ 个无标号盒子的 EGF：

$$ \begin{Bmatrix}i\k\end{Bmatrix}=\dfrac{\left[\dfrac{x^i}{i!}\right]F^k(x)}{k!} $$

用 $O(n\log n)$ 的多项式幂运算（exp(log(f >> 1) * k) << k，即先求 $\log$ 再乘 $k$ 再 $\exp$）即可完成计算。

进一步地，$\exp F(x)=\sum\limits_{i=0}^{+\infty}\dfrac{F^i(x)}{i!}$ 正是 $i$ 个有标号物品放到任意多个无标号盒子里的 EGF（EXP 通过每项除以 $i!$ 去掉了盒子的标号），这其实就是贝尔数的生成函数，详见 OI-wiki 贝尔数。

此处涉及大量"有标号 / 无标号"的辨析：第二类斯特林数要求盒子无标号且非空，$F^k(x)$ 天然对应有标号盒子，故必须除以 $k!$ 消除标号；而 $\exp F(x)$ 的级数展开形式已经蕴含了"任意多个无标号盒子"的语义。

int main() { scanf("%d%d", &n, &k); poly f(n + 1); fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod; for (int i = 1; i <= n; ++i) f[i] = qpow(fact[i], mod - 2); f = exp(log(f >> 1) * k) << k, f.resize(n + 1); int inv = qpow(fact[k], mod - 2); for (int i = 0; i <= n; ++i) printf("%lld ", (ll)f[i] * fact[i] % mod * inv % mod); return 0; }

第一类斯特林数（斯特林轮换数）

第一类斯特林数记作 $\begin{bmatrix}n\ k\end{bmatrix}$，也可记作 $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]\neq[D,C,B,A]$，即通过翻转得到的轮换不等价——这是轮换与子集（无序、可任意重排）的本质区别，也是两类斯特林数计数对象不同的根源。

递推式

$$ \begin{bmatrix}n\ k\end{bmatrix}=\begin{bmatrix}n-1\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\ k\end{bmatrix} $$

边界为 $\begin{bmatrix}n\ 0\end{bmatrix}=[n=0]$。

证明同样基于插入新元素的组合意义，两种方案为：

• 将新元素置于一个单独的轮换中：其余 $n-1$ 个元素构成 $k-1$ 个轮换，贡献 $\begin{bmatrix}n-1\ k-1\end{bmatrix}$ 种方案；
• 将新元素插入任何一个现有的轮换：$n-1$ 个元素构成 $k$ 个轮换，新元素可以插入到任意一个元素的后面（共 $n-1$ 个位置），贡献 $(n-1)\begin{bmatrix}n-1\ k\end{bmatrix}$ 种方案。

两式相加即得递推式。注意系数从第二类的 $k$ 变成了第一类的 $n-1$，这正对应"加入现有子集"与"插入轮换缝隙"两种计数方式的差异。

通项公式

第一类斯特林数没有实用的通项公式。这是两类斯特林数的重要差异，也是同行计算只能依靠生成函数/上升幂途径的原因。

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

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

$$ F_n(x)=\sum\limits_{i=0}^n\begin{bmatrix}n\i\end{bmatrix}x^i $$

由递推公式可写出

$$ F_n(x)=(n-1)F_{n-1}(x)+xF_{n-1}(x) $$

于是

$$ F_n(x)=\prod\limits_{i=0}^{n-1}(x+i)=\dfrac{(x+n-1)!}{(x-1)!} $$

这其实是 $x$ 的 $n$ 次上升阶乘幂$x^{\overline n}$。它自然可以暴力分治乘（每次合并两半多项式，总复杂度 $O(n\log^2 n)$）求出；但利用上升幂相关做法（倍增 $f_{2n}(x)=f_n(x)f_n(x+n)$ 并借助多项式平移计算 $f_n(x+n)$）可以做到 $O(n\log n)$，详情见 OI-wiki 多项式平移｜连续点值平移 一节——那里给出了递推式 $T(n)=T(n/2)+O(n\log n)=O(n\log n)$ 的完整推导，并以洛谷 P5408「第一类斯特林数·行」为例说明实现要点。

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

仿照第二类，可用 EGF 解决。注意：由于第一类的递推公式和行数 $n$ 有关，不能利用递推公式计算同列的第一类斯特林数，必须另辟蹊径。

单个轮换的 EGF 为（$(i-1)!$ 是 $i$ 个元素的环形排列数，除以 $i!$ 后得到 $\frac{1}{i}$）：

$$ F(x)=\sum\limits_{i=1}^n\dfrac{(i-1)!x^i}{i!}=\sum\limits_{i=1}^n\dfrac{x^i}{i} $$

其 $k$ 次幂 $F^k(x)$ 就是 $\begin{bmatrix}i\k\end{bmatrix}$ 的 EGF，$O(n\log n)$ 计算多项式幂即可：

int main() { scanf("%d%d", &n, &k); fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod; ifact[n] = qpow(fact[n], mod - 2); for (int i = n - 1; i >= 0; --i) ifact[i] = (ll)ifact[i + 1] * (i + 1) % mod; poly f(n + 1); for (int i = 1; i <= n; ++i) f[i] = (ll)fact[i - 1] * ifact[i] % mod; f = exp(log(f >> 1) * k) << k, f.resize(n + 1); for (int i = 0; i <= n; ++i) printf("%lld ", (ll)f[i] * fact[i] % mod * ifact[k] % mod); return 0; }

应用

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

记上升阶乘幂 $x^{\overline{n}}=\prod_{k=0}^{n-1} (x+k)$。两类斯特林数给出幂次转化的两套恒等式：

• 上升幂 → 普通幂（用第一类斯特林数）：

$$ x^{\overline{n}}=\sum_{k} \begin{bmatrix}n\ k\end{bmatrix} x^k $$

• 普通幂 → 上升幂（用第二类斯特林数，附 $(-1)^{n-k}$ 修正）：

$$ x^n=\sum_{k} \begin{Bmatrix}n\ k\end{Bmatrix} (-1)^{n-k} x^{\overline{k}} $$

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

记下降阶乘幂 $x^{\underline{n}}=\dfrac{x!}{(x-n)!}=\prod_{k=0}^{n-1} (x-k)$。对应恒等式为：

• 普通幂 → 下降幂：

$$ x^n=\sum_{k} \begin{Bmatrix}n\ k\end{Bmatrix} x^{\underline{k}} $$

• 下降幂 → 普通幂：

$$ x^{\underline{n}}=\sum_{k} \begin{bmatrix}n\ k\end{bmatrix} (-1)^{n-k} x^k $$

这四组恒等式在组合恒等式化简、和式求和与计数问题中频繁使用，是斯特林数最核心的代数应用。

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

多项式的下降阶乘幂表示是指用

$$ f(x)=\sum\limits_{i=0}^nb_i{x^{\underline{i}}} $$

的形式表示一个多项式；点值表示则用 $n+1$ 个点 $(i,a_i),\ i=0..n$ 表示。

下降阶乘幂系数 $b$ 与点值 $a$ 之间满足：

$$ a_k=\sum\limits_{i=0}^{n}b_ik^{\underline{i}} $$

将下降幂展开：

$$ \begin{aligned} a_k&=\sum\limits_{i=0}^{n}\dfrac{b_ik!}{(k-i)!}\ \dfrac{a_k}{k!}&=\sum\limits_{i=0}^kb_i\dfrac{1}{(k-i)!} \end{aligned} $$

这是一个卷积形式的式子：$\dfrac{a_k}{k!}$ 是 $b_i$ 与 $\dfrac{1}{(k-i)!}$ 的卷积。因此可以在 $O(n\log n)$ 的时间复杂度内完成点值表示与下降阶乘幂表示的互相转化，这为"拉格朗日插值求单点值""多项式多点求值"等场景提供了新的计算途径。

与贝尔数的关系

第二类斯特林数的一个直接推论是贝尔数（见 OI-wiki 贝尔数）：每个贝尔数都是相应第二类斯特林数的和，

$$ B_n = \sum_{k=0}^n\begin{Bmatrix}n\ k\end{Bmatrix} $$

因为第二类斯特林数是把 $n$ 元集合划分为正好 $k$ 个非空子集的方案数，对 $k$ 求和即得划分成任意多个非空子集的总方案数。反过来，贝尔数的 EGF 封闭形式 $\hat B(x)=\exp(\mathrm{e}^x - 1)$ 与本文同一列第二类斯特林数计算中的 $\exp F(x)$（$F(x)=\mathrm{e}^x-1$）完全一致，两条路径互相印证。

习题

• HDU 3625 Examining the Rooms（考察第一类斯特林数的组合意义与递推）
• UOJ 540 联合省选 2020 组合数问题（将组合数用斯特林数展开后交换求和次序）
• UOJ 269 清华集训 2016 如何优雅地求和（利用下降幂表示与点值表示的卷积互转）

参考资料与注释

1. 本文公式推导与算法流程主要依据 OI-wiki《斯特林数》，递推式、通项公式、同行/同列计算的生成函数构造与参考代码均出自该文档。
2. 多项式平移加速同行第一类斯特林数的做法见 OI-wiki《多项式平移｜连续点值平移》。
3. 第二类斯特林数与贝尔数的联系见 OI-wiki《贝尔数》。
4. 通项公式推导中用到的容斥原理与二项式反演基础见 OI-wiki《容斥原理》。
5. Stirling Number of the First Kind / Second Kind（Wolfram MathWorld）可作为两类斯特林数的标准参考定义。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki