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}[n0]$Iverson 括号当且仅当 $n0$ 时为 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_{i0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!} $$该公式使用容斥原理相关基础见 OI-wiki 容斥原理证明。设$G_i$将 $n$ 个两两不同的元素划分到 $i$ 个两两不同的集合允许空集的方案数$F_i$将 $n$ 个两两不同的元素划分到 $i$ 个两两不同的非空集合不允许空集的方案数。显然每个元素可以独立选择进入 $i$ 个盒子之一故 $G_ii^n$。同时从 $i$ 个盒子中挑选出 $j$ 个非空盒子其余为空可得$$ G_i\sum\limits_{j0}^i\binom{i}{j}F_j $$根据二项式反演$$ \begin{aligned} F_i\sum\limits_{j0}^{i}(-1)^{i-j}\binom{i}{j}G_j\ \sum\limits_{j0}^{i}(-1)^{i-j}\binom{i}{j}j^n\ \sum\limits_{j0}^{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_{i0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!} $$同一行第二类斯特林数的计算同一行的第二类斯特林数指 $n$ 相同、$i$ 不同的一系列 $\begin{Bmatrix}n\i\end{Bmatrix}$。求出同一行的全部值就是求 $i0..n$ 时将 $n$ 个不同元素划分为 $i$ 个非空子集的全部方案数。观察通项公式$$ \begin{Bmatrix}n\i\end{Bmatrix}\dfrac{1}{i!}\sum_{j0}^{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::vectorint data; public: poly(std::size_t len std::size_t(0)) { data std::vectorint(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::vectorint 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}$。求出同一列的全部值就是求 $i0..n$ 时将 $i$ 个不同元素划分为 $k$ 个非空子集的全部方案数。这里采用指数型生成函数EGF求解。一个盒子装 $i$ 个物品且盒子非空的方案数是 $[i0]$其 EGF 为$$ F(x)\sum\limits_{i1}^{\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_{i0}^{\infty}\dfrac{F^i(x)}{i!}$ 正是 $i$ 个有标号物品放到任意多个无标号盒子里的 EGFEXP 通过每项除以 $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}[n0]$。证明同样基于插入新元素的组合意义两种方案为将新元素置于一个单独的轮换中其余 $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_{i0}^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_{i0}^{n-1}(xi)\dfrac{(xn-1)!}{(x-1)!} $$这其实是 $x$ 的 $n$ 次上升阶乘幂$x^{\overline n}$。它自然可以暴力分治乘每次合并两半多项式总复杂度 $O(n\log^2 n)$求出但利用上升幂相关做法倍增 $f_{2n}(x)f_n(x)f_n(xn)$ 并借助多项式平移计算 $f_n(xn)$可以做到 $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_{i1}^n\dfrac{(i-1)!x^i}{i!}\sum\limits_{i1}^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_{k0}^{n-1} (xk)$。两类斯特林数给出幂次转化的两套恒等式上升幂 → 普通幂用第一类斯特林数$$ 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_{k0}^{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_{i0}^nb_i{x^{\underline{i}}} $$的形式表示一个多项式点值表示则用 $n1$ 个点 $(i,a_i),\ i0..n$ 表示。下降阶乘幂系数 $b$ 与点值 $a$ 之间满足$$ a_k\sum\limits_{i0}^{n}b_ik^{\underline{i}} $$将下降幂展开$$ \begin{aligned} a_k\sum\limits_{i0}^{n}\dfrac{b_ik!}{(k-i)!}\ \dfrac{a_k}{k!}\sum\limits_{i0}^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_{k0}^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 如何优雅地求和利用下降幂表示与点值表示的卷积互转参考资料与注释本文公式推导与算法流程主要依据 OI-wiki《斯特林数》递推式、通项公式、同行/同列计算的生成函数构造与参考代码均出自该文档。多项式平移加速同行第一类斯特林数的做法见 OI-wiki《多项式平移连续点值平移》。第二类斯特林数与贝尔数的联系见 OI-wiki《贝尔数》。通项公式推导中用到的容斥原理与二项式反演基础见 OI-wiki《容斥原理》。Stirling Number of the First Kind / Second KindWolfram MathWorld可作为两类斯特林数的标准参考定义。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考