生成函数，卡特兰数，伯努利数与斯特林数总结

生成函数

生成函数绪论

对于函数 $f:\mathbb{N}\to\mathbb{C}$，定义其普通生成函数（OGF）$\mathbf{F}(z)=\sum_{i\geq 0} f(i)z^i$，指数生成函数（EGF）$\hat{\mathbf{F}(z)}=\sum_{i\geq 0} \frac{f(i)}{i!}z^i$​。

我们使用 $\langle f(0),f(1),f(2),\cdots \rangle$ 来表示 $f$ 的普通生成函数。

若存在 $S\subseteq \mathbb{C}$ 使得 $\forall z\in S$，生成函数 $\mathbf{F}(z)$ 收敛，此时 $\mathbf{F}(z)$ 若可用有限项函数 $g(z)$ 表示，则称 $g(z)$ 为 $\mathbf{F}(z)$ 的封闭形式。

可以发现大多数生成函数不存在较好的封闭形式，如各种常见生成函数的若干位截断，以及生成函数的 Euler 变换等。

定义 $n^{\underline{m}}=\prod_{i=n-m+1}^{n} i$，读作 $n$ 的 $m$ 次下降幂（Factorial Power 或 Falling Factorial）。

定义 $n^{\overline{m}}=\prod_{i=n}^{n+m-1}i$，读作 $n$ 的 $m$ 次上升幂（Pochhammer Symbol 或 Rising Factorial）。

定义广义二项式系数 $\binom{\alpha}{n}=\frac{1}{n!}\alpha^{\underline{n}}$，这样就将组合数推广到了 $\alpha\in\mathbb{C},n\in\mathbb{N}$​。

上指标反转定理：$\binom{n}{m}=(-1)^m\binom{n-m-1}{m}$，常用于处理上指标为负数的情况。

牛顿二项式定理：

$$(n+m)^{\alpha}=\sum_{i\geq 0} \binom{\alpha}{i}n^im^{\alpha-i}$$

可以发现与二项式定理十分类似。

生成函数的乘法有 $[z^n](\mathbf{F}(z)\cdot \mathbf{G}(z))=\sum_{i\leq 0}^{n}([z^i]\mathbf{F}(z))([z^{n-i}]\mathbf{G}(z))$，据此生成函数的乘法又称卷积。

卷积可用 FFT 优化做到 $O(n\log n)$（在有限域 $\mathbb{Z}/p\mathbb{Z}$ 中可用 NTT 替代），不过 FFT 不允许在 NOI 中考察，故 $O(n^2)$ 暴力卷积足够。

常见生成函数的封闭形式

例 1：$\langle 1,1,1,\cdots\rangle=\frac{1}{1-z}$。

证明（R to L）：$\frac{1}{1-z}=(1-z)^{-1}=\sum_{i\geq 0}\binom{-1}{i}(-z)^i=\sum_{i\geq 0}\binom{i}{i}z^i=\sum_{i\geq 0}z^i=\langle 1,1,1,\cdots\rangle$​。

证明（L to R）：记 $\mathbf{F}(z)=\langle 1,1,1,\cdots \rangle$，则 $z\mathbf{F}(z)=\langle 0,1,1,1,\cdots\rangle$，故 $z\mathbf{F}(z)+1=\mathbf{F}(z)$，解得 $\mathbf{F}(z)=\frac{1}{1-z}$。

例 2：$\langle 1,c,c^2,\cdots\rangle=\frac{1}{1-cz}$。

证明：$\frac{1}{1-cz}=(1-cz)^{-1}=\sum_{i\geq 0}\binom{-1}{i}(-cz)^i=\sum_{i\geq 0}c^iz^i=\langle 1,c,c^2,\cdots\rangle$。

例 3：$\langle \binom{n}{0},\binom{n}{1},\binom{n}{2},\cdots \rangle=(1+z)^n$。

证明：二项式定理。

例 4：$\langle \binom{n+0-1}{0},\binom{n+1-1}{1},\binom{n+2-1}{2},\cdots\rangle=\frac{1}{(1-z)^n}$。

证明：$\frac{1}{(1-z)^n}=(1-z)^{-n}=\sum_{i\geq 0} \binom{-n}{i}(-z)^i=\sum_{i\geq 0}\binom{n+i-1}{i}z^i=\langle \binom{n+0-1}{0},\binom{n+1-1}{1},\binom{n+2-1}{2},\cdots\rangle$。

例 5：$\langle \binom{0}{n},\binom{1}{n},\binom{2}{n},\cdots\rangle=\frac{x^n}{(1-x)^{n+1}}$。

证明：$\frac{z^n}{(1-z)^{n+1}}=z^n(1-z)^{-n-1}=z^n\sum_{i\geq 0} \binom{-n-1}{i}(-z)^i=z^n\sum_{i\geq 0}\binom{n+i}{n}z^i=\sum_{i\geq 0}\binom{i}{n}z^i$。

例 6：$\langle 0,\frac{(-1)^{1+1}}{1},\frac{(-1)^{2+1}}{2},\cdots\rangle=\ln(1+z)$。

证明：根据数学知识得 $(\ln(1+z))^{(n)}=(-1)^{n+1}(1+z)^{-n}(n-1)!$。故 $(\ln(1+z))^{(n)}(0)=(-1)^{n+1}(n-1!)$，代入 Taylor 公式即得证。

例 7：$\langle \frac{1}{0!},\frac{1}{1!},\frac{1}{2!},\cdots\rangle=\exp(z)$。

证明：根据数学知识得 $(e^z)^{(n)}=e^z$。故 $(e^z)^{(n)}(0)=1$，代入 Taylor 公式即得证。

生成函数与递推

求 Fibonacci 数列的生成函数与通项公式。

由于 $\mathrm{fib}(n)=\mathrm{fib}(n-1)+\mathrm{fib}(n-2)$，故 $\mathrm{fib}$ 的生成函数 $\mathbf{A}(z)$ 满足 $\mathbf{A}(z)=\mathbf{A}(z)(z+z^2)+z$（最后的那个 $z$ 是为了处理 $\mathrm{fib}(0)=0,\mathrm{fib}(1)=1$）。

解得：

$$\boxed{\mathbf{A}(z)=\frac{z}{1-z-z^2}}$$

欲求通项公式，尝试对 $\mathbf{A}(z)$ 进行变形：

$$\mathbf{A}(z)=\frac{z}{1-z-z^2}=-\frac{z}{(z-z_0)(z-z_1)}=-\frac{-\frac{z_1}{z_0}(z-z_0)+(z-z_1)}{(z-z_0)(z-z_1)}\cdot \left(-\frac{z_1}{z_0}+1\right)^{-1}$$

其中 $z_0,z_1$ 为 $1-z-z^2=0$ 的两个根。

令 $b=-\frac{z_1}{z_0}\cdot \left(-\frac{z_1}{z_0}+1\right)^{-1},a=\left(-\frac{z_1}{z_0}+1\right)^{-1}$，得到：

$$\mathbf{A}(z)=-\left(\frac{a}{z-z_0}+\frac{b}{z-z_1}\right)$$

讨论一下 $\frac{1}{z-k}=-(z-k)^{-1}=-\sum_{i\geq 0}\binom{-1}{i}z^ik^{-1-i}(-1)^{-1-i}=-\sum_{i\geq 0}k^{-1-i}z^i$，对 $\mathbf{A}(z)$ 变形：

$$\mathbf{A}(z)=a\sum_{i\geq 0}z_0^{-i-1}z^i+b\sum_{i\geq 0} z_1^{-i-1} z^i=\sum_{i\geq 0}((az_0^{-1})(z_0^{-1})^i+(bz_1^{-1})(z_1^{-1})^i)z^i$$

故通项公式为 $\mathrm{fib}(n)=(az_0^{-1})(z_0^{-1})^n+(bz_1^{-1})(z_1^{-1})^n$，经计算得：

$$z_0=\frac{-1-\sqrt{5}}{2},z_1=\frac{-1+\sqrt{5}}{2},a=\frac{5+\sqrt{5}}{10},b=\frac{5-\sqrt{5}}{10}$$

代入得到：

$$\boxed{\mathrm{fib}(n)=\frac{\sqrt{5}}{5}\left(-\left(\frac{1-\sqrt{5}}{2}\right)^n+\left(\frac{1+\sqrt{5}}{2}\right)^n\right)}$$

• PS：写完后发现好像有更好的方法，比如直接用方程解出 $a,b$ 之类，不过直接代数变形感觉自然一些，虽然这样计算麻烦。
• PPS：好像网上的公式最前面的系数都是 $\frac{1}{\sqrt{5}}$，原因不明，反正都是等价的。

生成函数方法解递推式是中学阶段所谓“特征根法”的一种理论依据。

事实上一般的常系数齐次线性递推（以下简称线性递推）也可以用此方法求出生成函数与通项公式，由于通项公式极其复杂且不实用，我们仅讨论生成函数。

定理：对于任意线性递推，其生成函数均为有理函数。我们将会构造这样的有理函数来证明它。

现在我们需要根据线性递推关系 $a_n=\sum_{i=1}^{k} f_i a_{n-i}$ 求出 $P,Q$，使得 $[z^n]\left(\frac{P(z)}{Q(z)}\right)=a_n$。

考虑如果我们已经求出了这样的 $R(z)=\frac{P(z)}{Q(z)}$，那么它应该具有怎样的性质。简便起见，令 $C(z)=\sum_{i=1}^{k} f_iz^i,A(z)=\sum_{n\geq 0} \sum_{n=0}^{k-1} a_nz^n$。

然后稍作推导：

$$\begin{aligned} R(z)&=\sum_{n\geq 0} a_nz^n=\sum_{n\geq k}a_nz^n+\sum_{n=0}^{k-1} a_nz^n\\ &=\sum_{n\geq k} z^n\sum_{i=1}^{k} f_ia_{n-i}+\sum_{n=0}^{k-1} a_nz^n\\ &=\sum_{n\geq 0}z^n\sum_{i=1}^{k} f_ia_{n-i}+\sum_{n=0}^{k-1} a_nz^n-\sum_{n=0}^{k-1} z^n\sum_{i=1}^{n} f_ia_{n-i}\\ &=C(z)R(z)+A(z)-(A(z)C(z) \bmod z^k) \end{aligned}$$

因此：

$$\begin{aligned} &R(z)=C(z)R(z)+A(z)-(A(z)C(z) \bmod z^k)\\ &\implies (1-C(z))R(z)=A(z)-(A(z)C(z) \bmod z^k)\\ &\implies R(z)=\frac{A(z)-(A(z)C(z) \bmod z^k)}{1-C(z)} \end{aligned}$$

令 $P(z)=A(z)-(A(z)C(z) \bmod z^k),Q(z)=1-C(z)$ 即得到合法的 $P,Q$。

这个生成函数有什么用呢？我们可以结合 Bostan-Mori 求分式远处系数算法 $O(k\log k\log n)$ 求出线性递推的某一项，这远远快于常规的矩阵快速幂算法（$O(k^3\log n)$）。

让我们着手解决一道非线性递推。

求递推式 $a_n=a_{n-1}+a_{n-2}+1$，$a_0=a_1=1$ 的生成函数 $\mathbf{A}(z)$。

根据递推公式，很容易写出新的方程：

$$\mathbf{A}(z)=(z+z^2)\mathbf{A}(z)+\frac{1}{1-z}$$

故可以解得：

$$\mathbf{A}(z)=\frac{1}{(1-z)(1-z-z^2)}$$

由此例我们可以看到，许多对线性递推进行微小变形的非线性递推，仍然可以用生成函数轻易解决。

生成函数的一些应用

求：

$$\sum_{i=0}^{n}\binom{i}{n-i}$$

不妨构造生成函数，然后进行代数变换：

$$\begin{aligned} \mathbf{A}(z)&=\sum_{i\geq 0}\left(\sum_{j=0}^{i}\binom{j}{i-j}\right)z^i=\sum_{j\geq 0}\sum_{i\geq j}\binom{j}{i-j}z^i=\sum_{j\geq 0}\sum_{i\geq 0}\binom{j}{i}z^{i+j}=\sum_{i\geq 0}z^i\sum_{j\geq 0}\binom{j}{i}z^j=\sum_{i\geq 0} z^i\cdot \frac{z^i}{(1-z)^{i+1}}\\ &=\frac{1}{1-z}\sum_{i\geq 0}\left(\frac{z^2}{1-z}\right)^i=\frac{1}{1-z}\cdot \frac{1}{1-\frac{z^2}{1-z}}=\frac{1}{1-z}\cdot \frac{1-z}{1-z-z^2}=\frac{1}{1-z-z^2} \end{aligned}$$

根据经典的结果，Fibonacci 数列的生成函数是 $\frac{z}{1-z-z^2}$，故我们立即得到原式即为 $\mathrm{fib}(n+1)$。

证明范德蒙德卷积公式：

$$\sum_{i\geq 0}\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}$$

不妨构造生成函数，然后进行代数变换：

$$\begin{aligned} \mathbf{A}(z)&=\sum_{k\geq 0}\left(\sum_{i\geq 0}\binom{n}{i}\binom{m}{k-i}\right) z^k=\sum_{k\geq 0}\sum_{i\geq 0}\binom{n}{i}z^i\cdot \binom{m}{k-i}z^{k-i}=\left(\sum_{i\geq 0} \binom{n}{i}z^i\right)\left(\sum_{i\geq 0}\binom{m}{i}z^i\right)\\ &=(1+z)^n(1+z)^m=(1+z)^{n+m}=\sum_{k\geq 0}\binom{n+m}{k}z^k \end{aligned}$$

故原命题得证。

卡特兰数与伯努利数

卡特兰数

定义卡特兰数 $C_n$ 表示 $n$ 个点的无标号有根二叉树数量（区分左右子树）。

求卡特兰数的卷积递推公式、生成函数、通项公式、递推公式。

根据卡特兰数的定义，我们有：

$$C_n=\sum_{i=0}^{n-1}C_iC_{n-i-1}$$

大意就是枚举左子树有 $i$ 个点，那么右子树就有 $n-i-1$ 个点（还有一个点是根本身），根据乘法原理乘起来即可。

边界条件 $C_0=1$​，我们得到了卡特兰数的卷积递推公式，现在尝试求出它的生成函数 $\mathbf{C}(z)$。

根据卷积递推公式，我们有 $\mathbf{C}(z)=z\mathbf{C}(z)^2+1$，解方程 $z\mathbf{C}(z)^2-\mathbf{C}(z)+1=0$ 得到两个根：

$$\mathbf{C}_0(z)=\frac{1-\sqrt{1-4z}}{2z},\mathbf{C}_1(z)=\frac{1+\sqrt{1-4z}}{2z}$$

取 $z=0$，$\mathbf{C}_0(z)$ 会得到未定式，$\mathbf{C}_1(z)$ 则无定义。由于 $z=0$ 处生成函数的极限必须有定义，所以舍去 $\mathbf{C}_1(z)$ 并对 $\mathbf{C}_0(z)$ 进行分子有理化：

$$\mathbf{C}_0(z)=\frac{2}{1+\sqrt{1-4z}}$$

满足 $\mathbf{C}_0(0)=1$ 符合条件，故令 $\mathbf{C}(z)=\mathbf{C}_0(z)$ 得到：

$$\boxed{\mathbf{C}(z)=\frac{2}{1+\sqrt{1-4z}}=\frac{1-\sqrt{1-4z}}{2z}}$$

现在我们推导通项公式，对 $\mathbf{C}(z)$ 进行代数变形：

$$\mathbf{C}(z)=(1-(1-4z)^{1/2})(2z)^{-1}=(2z)^{-1}\left(1-\sum_{i\geq 0} \binom{1/2}{i}(-4z)^{i}\right)$$

考察广义二项式系数 $\binom{1/2}{i}$：

$$\begin{aligned} \binom{1/2}{i}&=\frac{1}{i!}\left(\frac{1}{2}\right)^{\underline{i}}=\frac{1}{i!}\prod_{k=0}^{i-1} \left(\frac{1}{2}-k\right)=\frac{1}{i!}\prod_{k=0}^{i-1}\frac{1-2k}{2}=\frac{1}{i!\cdot 2^i}\prod_{k=0}^{i-1}1-2k=\frac{(-1)^{i+1}}{i!\cdot 2^i}\prod_{k=1}^{i-1}2k-1\\ &=\frac{(-1)^{i+1}}{i!\cdot 2^i}\cdot \frac{(2i-2)!}{2^{i-1}(i-1)!}=\frac{(-1)^{i+1}(2i-2)!}{i!(i-1)!2^{2i-1}}=\binom{2i-1}{i}\cdot \frac{(-1)^{i+1}}{(2i-1)2^{2i-1}} \end{aligned}$$

将结果代入和式：

$$\begin{aligned} \sum_{i\geq 0}\binom{1/2}{i}(-4z)^i&=\sum_{i\geq 0}\binom{2i-1}{i}\cdot \frac{(-1)^{i+1}}{(2i-1)2^{2i-1}}\cdot (-1)^i\cdot 2^{2i}\cdot z^i\\&=-2\sum_{i\geq 0}\frac{1}{2i-1}\binom{2i-1}{i}z^i \end{aligned}$$

将结果代入原式：

$$\begin{aligned} (2z)^{-1}\left(1-\sum_{i\geq 0} \binom{1/2}{i}(-4z)^{i}\right)&=\frac{1}{2z}\left(1+2\sum_{i\geq 0}\frac{1}{2i-1}\binom{2i-1}{i}z^i\right)\\ &=\frac{1}{z}\sum_{i\geq 1}\frac{1}{2i-1}\binom{2i-1}{i}z^i=\sum_{i\geq 1}\frac{1}{2i-1}\binom{2i-1}{i}z^{i-1}\\ &=\sum_{i\geq 0}\frac{1}{2i+1}\binom{2i+1}{i+1}z^i=\sum_{i\geq 0}\frac{1}{2i+1}\cdot \frac{2i+1}{i+1}\binom{2i}{i}z^i\\ &=\sum_{i\geq 0}\frac{1}{i+1}\binom{2i}{i}z^i \end{aligned}$$

故我们得到了卡特兰数的一个通项公式：

$$\boxed{C_n=\frac{1}{n+1}\binom{2n}{n}}$$

又因为：

$$\frac{1}{n+1}\binom{2n}{n}=\binom{2n}{n}-\frac{n}{n+1}\binom{2n}{n}=\binom{2n}{n}-\frac{n}{n+1}\cdot \frac{(2n)!}{(n!)^2}=\binom{2n}{n}-\frac{(2n)!}{(n-1)!(n+1)!}=\binom{2n}{n}-\binom{2n}{n-1}$$

故我们得到了卡特兰数的另一个通项公式：

$$\boxed{C_n=\binom{2n}{n}-\binom{2n}{n-1}}$$

不妨将卡特兰数邻项作比：

$$\frac{C_n}{C_{n-1}}=\frac{\frac{1}{n+1}\binom{2n}{n}}{\frac{1}{n}\binom{2n-2}{n-1}}=\frac{\frac{(2n)!}{(n!)^2(n+1)}}{\frac{(2n-2)!}{((n-1)!)^2n}}=\frac{2n(2n-1)}{n(n+1)}=\frac{4n-2}{n+1}$$

故我们得到了卡特兰数的递推公式：

$$\boxed{C_n=\frac{4n-2}{n+1}\cdot C_{n-1},C_0=1}$$

伯努利数

定义伯努利数 $B_n$ 满足隐式递推公式 $\sum_{k=0}^{n}\binom{n+1}{k}B_k=[n=0]$，证明：

• $[z^n]\frac{z}{e^z-1}=\frac{B_n}{n!}$，换句话说 $B_n$ 的指数生成函数 $\hat{\mathbf{B}}(z)=\frac{z}{e^z-1}$。
• 定义 $S_k(n)=\sum_{i=0}^{n-1}i^k$，则 $S_k(n)=\frac{1}{k+1}\sum_{i=0}^{k}B_i\binom{k+1}{i}n^{k-i+1}$。

先来求 $B_n$ 的 EGF，我们可以适当对隐式递推公式变形：

$$\begin{aligned} \sum_{k=0}^{n}\binom{n+1}{k}B_k&=[n=0]\\ \sum_{k\geq 0}\binom{n+1}{k}B_k&=[n=0]+B_{n+1}\\ \sum_{k\geq 0} \frac{1}{k!(n+1-k)!}B_k&=[n=0]+\frac{1}{(n+1)!}B_{n+1}\\ \sum_{k\geq 0}\frac{B_k}{k!}\cdot \frac{1}{(n-k)!}&=[n=1]+\frac{1}{n!}B_n \end{aligned}$$

将和式改写为生成函数：

$$\hat{\mathbf{B}}(z)\cdot e^z=z+\hat{\mathbf{B}}(z)\implies \hat{\mathbf{B}}(z)=\frac{z}{e^z-1}$$

故我们得到了伯努利数的指数生成函数。现在来证明它与等幂求和 $S_k(n)$ 的关系。

考虑求 $S_k(n)$ 的指数生成函数 $\hat{\mathbf{S}}_n(z)$：

$$\begin{aligned} \hat{\mathbf{S}}_n(z)=\sum_{k\geq 0}\frac{S_k(n)}{k!}z^k=\sum_{k\geq 0}\sum_{i=0}^{n-1}\frac{z^ki^k}{k!}=\sum_{i=0}^{n-1}\sum_{k\geq 0}\frac{(iz)^k}{k!}=\sum_{i=0}^{n-1}e^{iz}=\frac{e^{nz}-1}{e^z-1} \end{aligned}$$

由于 $\frac{e^{nz}-1}{e^z-1}=\frac{z}{e^z-1}\cdot \frac{e^{nz}-1}{z}$，又因为：

$$\frac{e^{nz}-1}{z}=\sum_{i\geq 1}\frac{n^i}{i!}z^{i-1}=\sum_{i\geq 0}\frac{n^{i+1}z^i}{(i+1)!}$$

所以得到：

$$S_k(n)=k![z^k]\hat{\mathbf{S}}_n(z)=k!\sum_{i=0}^{k}\frac{B_i}{i!}\cdot \frac{n^{k-i+1}}{(k-i+1)!}=\frac{1}{k+1}\sum_{i=0}^{k}B_in^{k-i+1}\frac{(k+1)!}{i!(k-i+1)!}=\frac{1}{k+1}\sum_{i=0}^{k}B_i\binom{k+1}{i}n^{k-i+1}$$

这个公式启示我们 $S_k(n)$ 是一个关于 $n$ 的最高 $k+1$ 次多项式。因此我们可以 $O(k^2)$ 递推求出 $B_n$ 然后 $O(k)$ 解决等幂求和问题。

不过更加务实的方法是直接求出 $S_k(0),\cdots,S_k(k+1)$ 这 $k+2$ 个点值，然后拉格朗日插值求出系数。

由于点值在 $\mathbb{N}$ 上连续，所以我们可以优化拉格朗日插值到 $O(k)$。 这一方法将在下一节介绍。

等幂求和

上一节我们讨论了伯努利数，并给出了一个预处理 $O(k^2)$ 查询 $O(k)$ 的算法。不过正如前文提到的，我们有更好的算法。

观察拉格朗日插值法的公式（假设 $k+2$ 个点分别为 $(x_0,y_0),(x_1,y_1),\cdots,(x_{k+1},y_{k+1})$）：

$$f(x)=\sum_{i=0}^{k+1}y_i\prod_{0\leq j\leq k+1,j\neq i} \frac{x-x_j}{x_i-x_j}$$

由于我们假定 $x_i=i$，所以有（钦定 $x>k$）：

$$\begin{aligned} f(x)&=\sum_{i=0}^{k+1}y_i\prod_{0\leq j\leq k+1,j\neq i}\frac{x-j}{i-j}=\sum_{i=0}^{k+1}y_i\cdot \frac{1}{x-i}\left(\prod_{j=0}^{k+1}x-j\right)\cdot \prod_{j=0}^{i-1}\frac{1}{i-j}\cdot \prod_{j=i+1}^{k+1}\frac{1}{i-j}\\ &=\sum_{i=0}^{k+1}y_i\cdot \frac{x^{\underline{k+2}}}{x-i}\cdot \frac{1}{i!}\cdot \frac{(-1)^{k-i+1}}{(k-i+1)!} \end{aligned}$$

这样拉格朗日插值法就被优化到了 $O(k\log p)$（其中 $p$ 是模数），可以通过模板题 CF622F The Sum of the k-th Powers。

斯特林数

第二类斯特林数

第二类斯特林数定义：$n \brace m$ 表示将 $n$ 个有标号的小球放入 $m$ 个无标号的盒子中，使得盒子均非空的方案数。

求第二类斯特林数的递推公式、通项公式、列指数生成函数（固定下指标）、二元生成函数（关于行为 OGF，关于列为 EGF）。

根据第二类斯特林数的定义，我们很容易写出它的递推公式：

$$\boxed{{n\brace m}={n-1\brace m-1}+m{n-1\brace m},{n\brace 0}=[n=0]}$$

证明是平凡的，考虑第 $n$ 个球的方法，要么在 $n-1$ 个球的基础上新增一个盒子放入（${n-1\brace m-1}$），要么放入以前的一个装有球的盒子中（$m{n-1\brace m}$）。通过这个公式，可以 $O(n^2)$ 求出前 $n$ 行的第二类斯特林数。

现在考虑它的通项公式。考虑到若允许空盒，且盒子有标号，则方案数显然为 $g(m)=m^n$，然后可以根据 $f,g$ 的关系来二项式反演：

$$g(m)=m^n=\sum_{i=0}^{m}\binom{m}{i}f(i)\implies f(m)=\sum_{i=0}^{m}(-1)^{m-i}\binom{m}{i}g(i)\implies f(m)=\sum_{i=0}^{m}(-1)^{m-i}\binom{m}{i}i^n$$

其中 $f(i)$ 表示不允许空盒，但 $i$ 个盒子有标号的方案数。由于 ${n\brace m}=\frac{f(m)}{m!}$ 所以可以求出第二类斯特林数的通项公式：

$$\boxed{{n\brace m}=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{m-i}\binom{m}{i}i^n}$$

通过这个公式，可以借助 FFT/NTT 加速卷积，在 $O(n\log n)$ 的时间复杂度内求第 $n$​ 行的第二类斯特林数。

接下来考虑第二类斯特林数的列指数生成函数，即：

$$\begin{aligned} \hat{\mathbf{S}}_m(z)&=\frac{1}{m!}\sum_{n\geq 0}\sum_{i=0}^{m}(-1)^{m-i}\binom{m}{i}i^n\frac{z^n}{n!}\\ &=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{m-i}\binom{m}{i}\sum_{n\geq 0}\frac{z^ni^n}{n!}=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{m-i}\binom{m}{i}e^{iz}\\ &=\boxed{\frac{1}{m!}(e^z-1)^m} \end{aligned}$$

通过这个公式，可以 $O(n\log n)$ 多项式快速幂算法求出第二类斯特林数某一列的前 $n$​ 项。

多项式快速幂：对于多项式 $P(z)$，欲求 $P^k(z)$，则按照 $P(z)$ 的性质分类讨论：

1. 若 $P(0)=1$，则 $P^k(z)=\exp(k\ln(P(z)))$​。
2. 若 $P(0)\not\in\{0,1\}$，则 $P^k(z)=P(0)\exp(k\ln((P(0))^{-1}\cdot P(z)))$。
3. 否则，令 $P'(z)=z^{-1}P(z)$，则 $P^k(z)=z^k(P'(z))^k$，至于 $(P'(z))^k$ 则继续套用多项式快速幂即可。

这样就保证求 $\ln$ 时，真多项式的常数项始终为 $1$，以便得到正确的结果。

时间复杂度 $O(n\log n)$。

最后是第二类斯特林数的二元生成函数，即：

$$\begin{aligned} \mathbf{S}(x,y)&=\sum_{m\geq 0}y^m\hat{\mathbf{S}}_m(x)=\sum_{m\geq 0}\frac{y^m}{m!}\cdot (e^x-1)^m=\boxed{e^{y\left(e^x-1\right)}} \end{aligned}$$

这个生成函数形式非常漂亮，易于记忆，但是（在 OI 中）实用价值不高，不过可以帮助记忆前一个结果。

注意我们没有提到第二类斯特林数的行生成函数，事实上第二类斯特林数的行生成函数与 Touchard 多项式或 Bell 多项式 有关，是较难处理的，故略去。

第一类斯特林数

第一类斯特林数定义：${n\brack m}$ 表示将 $n$ 个互相区分的小球放入 $m$​ 个互不区分的圆排列，使得圆排列均非空的方案数。

求第一类斯特林数的递推公式、行普通生成函数、列指数生成函数、二元生成函数（关于行为 OGF，关于列为 EGF）。

根据第一类斯特林数的定义，我们很容易写出它的递推公式：

$$\boxed{{n\brack m}={n-1 \brack m-1}+(n-1){n-1\brack m},{n\brack 0}=[n=0]}$$

证明是平凡的，考虑第 $n$ 个小球，要么在一个新的圆排列中（${n-1\brack m-1}$），要么接在某一个元素后面（$(n-1){n-1\brack m}$​）。

通过递推公式，可以 $O(n^2)$ 求前 $n$ 行的第一类斯特林数。

接下来求其行普通生成函数 $\mathbf{s}_n(z)$，根据递推公式，我们有 $\mathbf{s}_n(z)=z\mathbf{s}_{n-1}(z)+(n-1)\mathbf{s}_{n-1}(z)$，即 $\mathbf{s}_n(z)=(z+n-1)\mathbf{s}_{n-1}(z)$，结合 $\mathbf{s}_0(z)=1$ 可以直接推导出：

$$\boxed{\mathbf{s}_n(z)=z^{\overline{n}}}$$

使用倍增法 $z^{\overline{n}}=z^{\overline{k}}(z+k)^{\overline{n-k}}$ 结合多项式点值平移技术，可以做到 $O(n\log n)$ 求第一类斯特林数第 $n$​ 行的值。

多项式点值平移：对于 $n$ 次多项式多项式 $P(z)$，求多项式 $P(z+k)$。为了方便，下面记 $a_i=[z^i]P(z)$，则：

$$\begin{aligned} P(z+k)&=\sum_{i\geq 0} a_i(z+k)^i=\sum_{i\geq 0}a_i\sum_{j=0}^{i}\binom{i}{j}z^jk^{i-j}=\sum_{j\geq 0}z^j\sum_{i\geq j}\binom{i}{j}a_ik^{i-j}\\ &=\sum_{j\geq 0}z^j\sum_{i\geq j}\frac{i!}{j!(i-j)!}a_ik^{i-j}=\sum_{j\geq 0}\frac{z^j}{j!}\sum_{i\geq j} a_ii!\cdot \frac{k^{i-j}}{(i-j)!} \end{aligned}$$

令 $f(i)=a_ii!,g(i)=\frac{k^i}{i!}$，代入化简：

$$\begin{aligned} P(z+k)&=\sum_{j\geq 0}\frac{z^j}{j!}\sum_{i\geq j} f(i)g(i-j)=\sum_{j\geq 0}\frac{z^j}{j!}\sum_{i=0}^{n-j} f(i+j)g(i)=\sum_{j\geq 0}\frac{z^j}{j!}\sum_{i=0}^{n-j} f'(n-i-j)g(i) \end{aligned}$$

其中 $f'(i)=f(n-i)$。这样末尾的和式就是卷积的形式，可以用 FFT/NTT 优化。时间复杂度 $O(n\log n)$。

然后是求其列指数生成函数 $\hat{\mathbf{s}}_m(z)$。考虑第一类斯特林数的组合意义，可以写出下面的等式：

$$\frac{1}{n!}{n\brack m}=\frac{1}{m!}[z^n]\left(\sum_{i\geq 1}(i-1)!\frac{z^i}{i!}\right)^m$$

这之中的原因是长为 $i$ 的圆排列有 $(i-1)!$ 种，那么写出每一个圆排列的指数生成函数（不妨先假定圆排列之间区分，这样放入的小球在自然也就区分了）$\sum_{i\geq 1}(i-1)!\frac{z^i}{i!}$，$m$ 次幂后除以顺序系数 $m!$ 就是答案。

根据这个等式可以立即写出 $\hat{\mathbf{s}}_m(z)$ 的表达式：

$$\begin{aligned} \hat{\mathbf{s}}_m(z)&=\frac{1}{m!}\left(\sum_{i\geq 1}(i-1)!\frac{z^i}{i!}\right)^m=\frac{1}{m!}\left(\sum_{i\geq 1}\frac{z^i}{i}\right)^m\\ &=\frac{1}{m!}\left(-\sum_{i\geq 1}\frac{(-z)^i(-1)^{i+1}}{i}\right)^m=\frac{1}{m!}\left(-\ln(1-z)\right)^m=\boxed{\frac{1}{m!}(-1)^m\ln^m(1-z)} \end{aligned}$$

事实上大多数时候我们只需要做到第一步即可，可以对 $\sum_{i\geq 1}\frac{z^i}{i}$ 多项式快速幂，$O(n\log n)$ 时间复杂度内求第一类斯特林数某一列的前 $n$ 项。

仿照我们推导第二类斯特林数的二元生成函数的过程，同样可以求出第一类斯特林数的二元生成函数：

$$\mathbf{s}(x,y)=\sum_{i\geq 0} y^i\hat{\mathbf{s}}_m(x)=\sum_{i\geq 0}y^i\frac{1}{i!}(-1)^i\ln^i(1-x)=\sum_{i\geq 0}\frac{(-y\ln(1-x))^i}{i!}=\boxed{e^{-y\ln(1-x)}}$$

这个结果同样非常易于记忆，但是在 OI 种的用途大概也只有方便推列指数生成函数了吧。

普通幂、上升幂与下降幂的转换

普通幂、上升幂和下降幂可以通过斯特林数进行转换，这里给出六个公式：

上升幂转普通幂	下降幂转普通幂
$x^{\overline{n}}=\sum\limits_{i\geq 0}{n\brack i}x^i$	$x^{\underline{n}}=\sum\limits_{i\geq 0}{n\brack i}(-1)^{n-i}x^i$​
普通幂转上升幂	普通幂转下降幂
$x^n=\sum\limits_{i\geq 0} {n\brace i}(-1)^{n-i}x^{\overline{i}}$	$x^n=\sum\limits_{i\geq 0}{n\brace i}x^{\underline{i}}$
上升幂转下降幂	下降幂转上升幂
$x^{\overline{n}}=(-1)^n(-x)^{\underline{n}}$	$x^{\underline{n}}=(-1)^n(-x)^{\overline{n}}$

其中上升幂转普通幂已经在第一类斯特林数的行生成函数中证明。这里将证明余下五个。

上升幂转下降幂：

$$x^{\overline{n}}=\prod_{i=0}^{n-1}x+i=(-1)^n\prod_{i=0}^{n-1}-x-i=(-1)^n(-x)^{\underline{n}}$$

下降幂转上升幂是类似的。

下降幂转普通幂：

$$x^{\underline{n}}=(-1)^{n}(-x)^{\overline{n}}=(-1)^n\sum_{i\geq 0}{n\brack i}(-x)^i=(-1)^n\sum_{i\geq 0}{n\brack i}(-1)^ix^i=\sum_{i\geq 0}{n\brack i}(-1)^{n-i}x^i$$

普通幂转下降幂：右侧的和式可以看成有 $x$ 个盒子，选出 $i$ 个盒子非空，有 $x^{\underline{i}}$ 种，将 $n$ 个球放入盒子中使得每个盒子非空的方案数是 ${n\brace i}$，故右侧的和式的意义是将 $n$ 个互相区分的小球放入 $x$ 个互相区分的盒子，不加任何其他限制的方案数。而这个方案数的答案就是左侧的 $x^n$，故该等式成立。这个证明很容易推广到 $x\in\mathbb{R}$ 的情况。

普通幂转上升幂：

$$x^n=(-1)^n(-x)^n=(-1)^n\sum_{i\geq 0}{n\brace i} (-x)^{\underline{i}}=(-1)^n\sum_{i\geq 0}{n\brace i}(-1)^ix^{\overline{i}}=\sum_{i\geq 0}{n\brace i}(-1)^{n-i}x^{\overline{i}}$$

另外值得一提的是，普通幂、上升幂和下降幂有一个共性——都满足二项式定理：

$$\boxed{\begin{aligned} &(a+b)^n=\sum_{i\geq 0} \binom{n}{i} a^i b^{n-i}\\ &(a+b)^{\underline{n}}=\sum_{i\geq 0}\binom{n}{i} a^{\underline{i}} b^{\underline{n-i}}\\ &(a+b)^{\overline{n}}=\sum_{i\geq 0}\binom{n}{i}a^{\overline{i}}b^{\overline{n-i}} \end{aligned}}$$

证明：对于下降幂的二项式定理，等式左侧可以看成 $a+b$ 个数中，选 $n$ 个数的形成的排列数，而右侧可以看成将 $a+b$ 个数分成两组，甲组 $a$ 个数乙组 $b$ 个数，枚举甲组选择 $i$ 个数，则方案数为 $a^{\underline{i}}$，同理乙组方案数为 $b^{\underline{n-i}}$。最后在排列的 $i$ 个位置分配给甲组，剩余分配给乙组即可，这一部分方案数是 $\binom{n}{i}$。故等式两边求的是同一个东西，所以相等。这个证明很容易推广到 $a,b\in\mathbb{R}$ 的情况。

对于上升幂的二项式定理，只需要将上升幂转成下降幂即可。

反转公式与斯特林反演

证明反转公式：

$$\sum_{i\geq 0} {n\brack i}{i \brace m}(-1)^{n-i}=\sum_{i\geq 0} {n\brace i}{i \brack m}(-1)^{n-i}=[n=m]$$

我们以证明连等式第二项和第三项相等为例，第一项与第三项相等是类似的：

$$\begin{aligned} x^n&=\sum_{i\geq 0}{n\brace i}(-1)^{n-i}x^{\overline{i}}=\sum_{i\geq 0}{n\brace i}(-1)^{n-i}\sum_{m\geq 0} {i\brack m}x^m=\sum_{m\geq 0}x^m\sum_{i\geq 0} {n\brace i}{i\brack m}(-1)^{n-i}\\ &\implies \sum_{i\geq 0} {n\brace i}{i\brack m}(-1)^{n-i}=[n=m] \end{aligned}$$

反转公式看起来就很像莫比乌斯反演公式和单位根反演公式，这引导我们构造类似的反演形式。

证明斯特林反演：

$$f(n)=\sum_{i\geq 0}{n\brace i}g(i)\iff g(n)=\sum_{i\geq 0}(-1)^{n-i}{n \brack i}f(i)$$

证明？其实就是反转公式 + 克罗内克函数描述的矩阵反演啦！可以参考 算法｜斯特林数、容斥和反演整理 - 知乎。

习题

UOJ 540. 【统一省选2020】组合数问题：给定一个 $m$ 次多项式 $f(x)=a_{0}+a_{1}x+\cdots+a_{m}x^{m}$。

给出 $n,x,p,m$，你需要求出：

$$\sum_{k=0}^{n}\binom{n}{k}f(k)x^{k}\pmod{p}$$

$1\leq n,x,p\leq 10^{9},0\leq m\leq\min(n,10^{3})$

大力推式子：

$$\begin{aligned} &\sum_{k=0}^{n}x^{k}\binom{n}{k}\sum_{t=0}^{m}a_{t}k^{t}\\ =&\sum_{t=0}^{m}a_{t}\sum_{k=0}^{n}k^{t}x^{k}\binom{n}{k}=\sum_{t=0}^{m}a_{t}\sum_{k=0}^{n}x^{k}\binom{n}{k}\sum_{i=0}^{t}\begin{Bmatrix}t\\i\end{Bmatrix}\binom{k}{i}i!\\ =&\sum_{t=0}^{m}a_{t}\sum_{i=0}^{t}\begin{Bmatrix}t\\i\end{Bmatrix}i!\sum_{k=0}^{n}\binom{n}{k}\binom{k}{i}x^{k}=\sum_{t=0}^{m}a_{t}\sum_{i=0}^{t}\begin{Bmatrix}t\\i\end{Bmatrix}\binom{n}{i}i!\sum_{k=0}^{n}\binom{n-i}{k-i}x^{k}\\ =&\sum_{t=0}^{m}a_{t}\sum_{i=0}^{t}\begin{Bmatrix}t\\i\end{Bmatrix}\binom{n}{i}i!x^{i}\sum_{k=0}^{n-i}\binom{n-i}{k}x^{k}\\ =&\sum_{t=0}^{m}a_{t}\sum_{i=0}^{t}\begin{Bmatrix}t\\i\end{Bmatrix}\binom{n}{i}i!x^{i}(1+x)^{n-i}=\sum_{t=0}^{m}a_{t}\sum_{i=0}^{t}\begin{Bmatrix}t\\i\end{Bmatrix}x^{i}(1+x)^{n-i}n^{\underline{i}} \end{aligned}$$

这个式子显然可以 $O(m^2\log n)$ 计算（精细的实现也许可以做到 $O(m^2)$ ？），这个时间复杂度完全可以承受。

• P5320 [BJOI2019] 勘破神机
• P6295 有标号 DAG 计数