03 生成函数

定义与严格化

对于一个数列$\{a_n\}$，我们可以定义一个关于$z$的函数$F(z)=\sum\limits_{n \geq 0}a_nz^n$。这个函数就称为这个数列对应的生成函数。

生成函数实际上并不是数学分析意义中的多项式函数，这里的$z$并不是某个实数或复数，而是一个形式上的数，所对应的级数也只是一个形式级数。这些代数运算本质上是定义在$(\cdots,a_{-1},a_0,a_1,\cdots)$这个无穷维向量上的运算法则。在$z$的收敛半径内，形式级数有着和多项式类似的运算法则。所以，我们不必太关心为什么我们可以对生成函数进行这些运算，我们只需要知道这么做是正确的。对形式级数严格化的证明，除了能向我们证实这确实是对的以外没有别的意义，而这个工作前人已经帮我们做好了。

封闭表达式

一些数列的生成函数往往具有简洁的封闭表达式：

如果$a_n=1$，那么对应的有$F(z)=\sum\limits_{n=0}^{\infty}z^n=\dfrac{1}{1-z}$。在这里，我们用到了等比级数的求和运算，这个运算在形式级数上是正确的。右侧的封闭表达式和左侧的无穷级数表达的含义是完全相同的。

如果$a_k=\dbinom{n}{k}$，那么$F(z)=\sum\limits_{k=0}^{n}\dbinom{n}{k}z^k=(1+z)^n$。这里用到了二项式定理。

如果$a_k=\left(\left(\begin{array}{c}n \\k\end{array}\right)\right)=\binom{n+k-1}{k}$，我们记得它的组合意义是$k$个一样的小球放进$n$个不同的箱子里，箱子可以为空。这等价于插隔板，因此等价于找$n$个和为$k$的数的个数（考虑顺序）。这可以理解为生成函数中$z$的指数运算。如果写出$F(z)=(1+z+z^2+\cdots)^n$，那么展开以后$z^k$的系数恰好对应了方案数。因此$F(z)$就是我们要的生成函数。而每个括号内我们都能够写成封闭表达式$\dfrac{1}{1-z}$，因此$F(z)=\dfrac{1}{(1-z)^n}$。

基本运算

对于两个生成函数$F(z)=\sum\limits_{n}f_nz^n,G(z)=\sum\limits_{n}g_nz^n$。那么有运算法则：

$\left [z^{k}\right](F+G)=f_{k}+g_{k}$

$\left[z^{k}\right]\left(z^{m} F\right)=f_{k-m}$

$\left[z^{k}\right](c \cdot F)=c f_{k}$

$\left[z^{k}\right]\left(F^{\prime}\right)=(k+1) f_{k+1}$

斐波那契通项公式（二阶线性递推）

我们把斐波那契数列拓展到下标为全体整数，定义$n \leq 0$时$f_n=0$，$n > 0$时$f_n=f_{n-1}+f_{n-2}+\bold{1}[n=1]$。两边同时乘以$z^n$得$f_nz^n=f_{n-1}z^n+f_{n-2}z^n+\bold{1}[n=1]z^n$。这个等式对全体整数$n$成立，对全体等数累加得$\sum\limits_{n}f_nz^n=z\sum\limits_{n}f_{n-1}z^{n-1}+z^2\sum\limits_{n}f_{n-2}z^{n-2}+z$。将生成函数的定义代入得$F(z)=zF(z)+z^2F(z)+z$。由此解得封闭表达式$F(z)=\dfrac{z}{1-z-z^2}$。裂项得$F(z)=\dfrac{1}{\sqrt{5}}\cdot\dfrac{1}{1-\frac{1+\sqrt{5}}{2}z}-\dfrac{1}{\sqrt{5}}\cdot\dfrac{1}{1-\frac{1-\sqrt{5}}{2}z}$。即$F$是两个生成函数的和，这两个生成函数都是等比级数。因此可以写出$[z^n]F(z)=[z^n]\left(\dfrac{1}{\sqrt{5}}\cdot\dfrac{1}{1-\frac{1+\sqrt{5}}{2}z}\right)-[z^n]\left(\dfrac{1}{\sqrt{5}}\cdot\dfrac{1}{1-\frac{1-\sqrt{5}}{2}z}\right)$，即$f_n=\dfrac{1}{\sqrt{5}}\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\dfrac{1}{\sqrt{5}}\left(\dfrac{1-\sqrt{5}}{2}\right)^n$。

扇形图的生成树（$n$阶线性递推）

有$0$到$n$共$n+1$个节点，$1$到$n$依次相连形成一条链。并且$1$到$n$的每个点都与$0$相连，形成一张扇形图，求这张图的生成树个数$f_n$。

假设$(0,n)$这条边没被选，那么必须选择$(n,n-1)$这条边。而余下的$0$到$n-1$这个子图必须选出一颗生成树，而$f_{n-1}$中的每个方案都是可行的。因此方案数为$f_{n-1}$。

假设$(0,n)$这条边被选了，我们枚举链上的选边情况。考虑链上从$n$到$k$间的每条边都被选，而$k$到$k-1$的边没有被选（$2\leq k \leq n$）。显然$n$到$k$这些点到$0$的边一定不能再选了。而$1$到$k-1$这些点必须构成生成树。和上面类似，每种情况的方案数都恰好为$f_{k-1}$。还要考虑到$k=1$的情况贡献1。因此总方案数为$\sum\limits_{k=2}^{n}f_{k-1}+1$。

所以可以写出递推式：$f_n=f_{n-1}+\sum\limits_{k=1}^{n-1}f_k+\bold{1}[n>0]$。当$n \leq 0$时，$f_n=0$。

那么考虑用生成函数，得到$\sum\limits_{n}f_nz^n=z\sum\limits_{n}f_{n-1}z^{n-1}+\sum\limits_{n}\left(\sum\limits_{k=1}^{n-1} f_k\right)z^n+\sum\limits_{n \geq 1}z^n$。其中$\sum\limits_{n}\left(\sum\limits_{k=1}^{n-1} f_k\right)z^n=\sum\limits_{k \geq 1}f_k\left(\sum\limits_{n \geq k+1}z^n\right)=\sum\limits_{k \geq 1}f_kz^k\left(\sum\limits_{n \geq k+1}z^{n-k}\right)$，右侧即为$\sum\limits_{k \geq 1}f_kz^k \cdot \dfrac{z}{1-z}$。将生成函数代入，$F(z)=zF(z)+F(z)\dfrac{z}{1-z}+\dfrac{z}{1-z}$，解得$F(z)=\dfrac{z}{1-3z+z^2}$。同样裂项就可以求出$f_n$的通项是等比加等比的结构。

卷积（生成函数的乘法）

把两个生成函数$F(z)=\sum\limits_{n}f_nz^n,G(z)=\sum\limits_{n}g_nz^n$相乘，那么根据多项式的运算法则，得到$[z^n]F(z)*G(z)=\sum\limits_{k}f_kg_{n-k}$。

因此，如果生成函数的封闭表达式可以看作两个表达式的积，那么它的通项就可以用$f,g$的通项的卷积表示。比如，$k$个相同的小球放进$n$个不同的箱子，每个箱子小球个数不能超过$t$个。那我们用生成函数容易写出$f_n=[z^k]\left(1+z^2+\cdots+z^t\right)^n=[z^k]\left(\dfrac{1-z^{t+1}}{1-z}\right)^n$，这可以看作$\dfrac{1}{(1-z)^n}$与$(1-z^{t+1})^n$的乘积。而这两个生成函数对应数列的通项都是容易写出的。

卷积可以推广到多元的情形：$[z^n]F^{(1)}(z)*\cdots*F^{(m)}(z)=\sum\limits_{i_1+\cdots+i_m=n}\prod\limits_{j=1}^{m}f^{(j)}_{i_j}$

通过多元卷积，我们对扇形图的生成树个数又有一种新的计算方法：考虑$1$到$n$的链在选边后被分成了$m$段，那么每段必须恰好只有一个点与$0$相连。因此可以直接写出$f_n=\sum\limits_{m>0}\sum\limits_{i_1+\cdots+i_m=n}\prod\limits_{j=1}^{m}i_j$。考虑$g_n=n$，有生成函数$G(z)=\sum\limits_{n>0}nz^n=z\sum\limits_{n>0}nz^{n-1}=z(z+z^2+\cdots)'=z(\dfrac{z}{1-z})'=\dfrac{z}{(1-z)^2}$。

于是$f_n=\sum\limits_{m>0}[z^n]G^m(z)=[z^n]\sum\limits_{m>0}G^m(z)$。$G(z)$作为一个变量本身构成了等比数列，因此有$f_n=[z^n]\dfrac{G(z)}{1-G(z)}=[z^n]\dfrac{z}{1-3z+z^2}$。这和上面得到的结果是相同的。

数的分划

一个整数可以写成若干奇数的和，称为奇分划；一个整数也可惜写成若干互不相同的数的和，称为不同数分划。 欧拉用生成函数证明了：对于任意整数，奇分划的个数与不同数分划的个数是相同的。

奇分划可以写成生成函数的形式$O(z)=(1+z^2+\cdots)(1+(z^3)^2+\cdots)(1+(z^5)^2+\cdots)\cdots$，它的封闭表达式为$O(z)=\dfrac{1}{1-z}\cdot\dfrac{1}{1-z^3}\cdot\dfrac{1}{1-z^5}\cdots$

而不同数分划的生成函数为$D(z)=(1+z)(1+z^2)(1+z^3)\cdots$。应用平方差公式，$D(z)=\dfrac{1-z^2}{1-z}\cdot\dfrac{1-z^4}{1-z^2}\cdot\dfrac{1-z^6}{1-z^3}\cdots$。分子上的偶数项都会被约分，从而恰好得到$O(z)=D(z)$。

第二类斯特林数的生成函数

斯特林数是一个二元函数。我们考虑固定$k$的斯特林数形成的生成函数：$S_k(z) = \sum\limits_n\left\{\begin{array}{}n\\k\end{array}\right\} \cdot z^n$。考虑到边界情况后，有递推关系：

$\left\{\begin{array}{}n\\k\end{array}\right\} = \left\{\begin{array}{}n-1\\k-1\end{array}\right\}+k\left\{\begin{array}{}n-1\\k\end{array}\right\}+\mathbb{1}[n=k=0]$

那么依照生成函数求解递推式的惯例，两边同时乘以$z^n$并对全体整数$n$累加得到$S_k(z)=zS_{k-1}(z)+kzS_{k}(z)$，即$S_k(z) = \dfrac{z}{1-kz}S_{k-1}(z)$。累乘（其中$S_0(z) = 1$）得到$S_k(z) = \dfrac{z^k}{\prod\limits_{j=1}^{k}(1-jz)}$。

对$S_k(z)$裂项，假设$S_k(z) = \sum\limits_{j=1}^{k}\dfrac{\alpha_j}{1-jz}+C$。此时我们可以用有理函数积分时待定系数的trick，在求解$\alpha_i$时在等式两边同时乘以$1-iz$，此时等式关系依然对$z$恒成立。那么取$z=\dfrac{1}{i}$，则左边变成$\dfrac{(1/i)^k}{\prod\limits_{j \neq i}(1-j/i)}$，而右边只剩下$\alpha_i$。因此$\alpha_i = \dfrac{1/i^k}{\prod\limits_{j \neq i}(1-j/i)}=$ $\dfrac{1}{i\prod\limits_{j \neq i}(i-j)}=\dfrac{(-1)^{k-i}}{i!(k-i)!}=(-1)^{k-i}\dbinom{k}{i}\cdot \dfrac{1}{k!}$。

因此$[z^n]S_k(z)=\sum\limits_{j=1}^{k}\alpha_j \cdot j^n = \sum\limits_{j=1}^{k}(-1)^{k-j}\dbinom{k}{j}\dfrac{j^n}{k!}=\dfrac{1}{k!}\sum\limits_{i=0}^{k-1}(-1)^i\dbinom{k}{i}(k-i)^n$

$=\dfrac{1}{k!}\sum\limits_{i=0}^{k}(-1)^i\dbinom{k}{i}(k-i)^n$。可以发现和我们用容斥得到的结论是一致的。

卡特兰数

$n$个节点的二叉树形态数量$c_n$称为卡特兰数列。容易发现有递推式

$c_n=\sum\limits_{k=0}^{n-1}c_k\cdot c_{n-1-k}+\mathbb{1}[n=0]$

设生成函数$C(z) = \sum\limits_{n}c_nz^n$两边同时乘以$z^n$并对全体整数$n$求和（中间的部分是卷积），得到$C(z) = z[C(z)]^2+1$。二次方程求根公式得$C(z) = \dfrac{1 \pm \sqrt{1-4z}}{2z}$。由于$C(0)=1$，所以舍去$\dfrac{1+\sqrt{1-4z}}{2z}$（发散），并且确实有$\lim\limits_{z \to 0}\dfrac{1-\sqrt{1-4z}}{2z} = \lim\limits_{z \to 0}\dfrac{1-{(1-4z)}}{2z(1+\sqrt{1-4z})}=1$。因此$C(z) = \dfrac{1 - \sqrt{1-4z}}{2z}$。由广义二项式定理展开得$\sqrt{1-4z}=\sum\limits_{n \geq 0}\dbinom{\frac{1}{2}}{n}(-4z)^{n}$。代入得$C(z)= \dfrac{1-\sum\limits_{n \geq 0}\dbinom{\frac{1}{2}}{n}(-4z)^{n}}{2z} = \dfrac{-\sum\limits_{n \geq 1}\dbinom{\frac{1}{2}}{n}(-4z)^{n}}{2z}=2\sum\limits_{n \geq 1}\dbinom{\frac{1}{2}}{n}(-4z)^{n-1}$ $=2\sum\limits_{n \geq 0}\dbinom{\frac{1}{2}}{n+1}(-4)^nz^n$。

因此$c_n = 2\dbinom{1/2}{n+1}(-4)^n = 2\dfrac{(\frac{1}{2}-0)(\frac{1}{2}-1)\cdots(\frac{1}{2}-n)}{(n+1)!}(-2)^n2^n$ $=\dfrac{(-1+2)(-1+4)\cdots(-1+2n)}{(n+1)!}2^n = \dfrac{(2n-1)!!}{(n+1)!}2^n=\dfrac{(2n)!}{(2n)!!(n+1)!}2^n$ $=\dfrac{(2n)!}{n! \cdot 2^n \cdot (n+1)!}2^n = \dfrac{1}{n+1}\dbinom{2n}{n}$

指数生成函数

考虑一个最简单的递推关系$f_n=nf_{n-1}+\mathbb{1}[n=0]$。显然$f_n = n!$。但当我们试图用普通的生成函数去根据递推关系求解通项时却碰到了问题：设$F(z) = \sum\limits_{n}f_nz^n$。在递推关系两边同时乘以$z^n$并对$n$求和，得到$\sum\limits_{n}f^nz^n=\sum\limits_{n}f_{n-1}\cdot nz^n+1$。由于$F'(z) = \sum\limits_{n}f_n \cdot nz^{n-1}$，因此$\sum\limits_{n}f_{n-1}nz^n=\sum\limits_{n}f_{n-1}(n-1)z^n+\sum\limits_{n}f_{n-1}z^n=$ $\sum\limits_{n}f_n\cdot nz^{n+1}+zF(z)$ $= z^2F'(z)+zF(z)$。原式即为$F(z) = z^2F'(z)+zF(z)+1$。这是一个微分方程，并且恰好没有封闭形式的解。

为了处理这类问题，我们使用“指数生成函数”。数列$f_n$的指数生成函数定义为$\widehat F(z) = \sum\limits_{n\geq 0}\dfrac{f_n}{n!}\cdot z^n$。我们注意到当$f_n \equiv 1$时，$\widehat{F}(z) = \sum\limits_{n \geq 0}\dfrac{z^n}{n!}$，根据Taylor公式有$\widehat{F}(z) = e^z$。

因此，当我们已知$f_nz^n=f_{n-1}\cdot nz^n+\mathbb{1}[n=0]$时，两边同时除以$n!$再对$n$累加，得到$\sum\limits_{n}\dfrac{f^n}{n!}z^n=\sum\limits_{n}\dfrac{f_{n-1}}{(n-1)!}z^n +1$，所以$\widehat{F}(z) = z\widehat{F}(z)+1$，解得$\widehat{F}(z) = \dfrac{1}{1-z}$。因此$[z^n]\widehat{F}(z) = 1 = \dfrac{f_n}{n!}$，解得$f_n = n!$。

指数生成函数的卷积和二项式有相似之处：设$\widehat F(z) = \sum\limits_{n\geq 0}\dfrac{f_n}{n!}\cdot z^n,\widehat G(z) = \sum\limits_{n\geq 0}\dfrac{g_n}{n!}\cdot z^n$。设$\widehat{H}(z) = \sum\limits_{n \geq 0}\dfrac{h_n}{n!}z^n$，那么$[z^n](\widehat{F}*\widehat{G}) = \sum\limits_{k=0}^{n}\dfrac{f_kg_{n-k}}{k!(n-k!)} = \dfrac{h_n}{n!}$。因此$h_n = \sum\limits_{k=0}^{n}\dfrac{n!}{k!(n-k!)}f_kg_{n-k}=\sum\limits_{k=0}^{n}\dbinom{n}{k}f_kg_{n-k}$

生成树计数

我们认为$n$个有编号的节点的两个生成树是相同的当且仅当每个对应节点的父节点编号与子节点编号全都相同。设$n$个节点的可能生成树个数是$t_n$个。考虑递推关系，把其中一个节点固定为根节点，我们枚举其子树个数$m$。每一次需要各个子树中的节点个数$k_i$满足$k_1+\cdots+k_m = n-1$，对于每种$\{k_i\}$的选取，方案数为$\dbinom{n-1}{k_1}\dbinom{n-1-k_1}{k_2}\cdots\dbinom{k_m}{k_m} = \dfrac{(n-1)!}{k_1!(n-1-k_1)!}\cdot \dfrac{(n-1-k_1)!}{k_2!(n-1-k_1-k_2)!}\cdots 1$ $=\dfrac{(n-1)!}{k_1!\cdots k_m!}$。在考虑子树顺序的前提下，我们的统计是完全的并且不重复的。而子树的顺序是不能认为是不同的生成树个数的。答案中的一种分组方案在我们的统计方法中会被重复统计$m!$遍。每个分组中生成树的方案数是$t_{k_i}$，并且我们可以任意选一个点作为子树的根节点。综上，有递推关系：

$t_n = \sum\limits_{m=1}^{n-1}\dfrac{1}{m!}\sum\limits_{\sum k_i = n-1}\dfrac{(n-1)!}{k_1!\cdots k_m!}t_{k_1}\cdots t_{k_m} \cdot k_1 \cdots k_m$

有$t_n = \sum\limits_{m=1}^{n-1}\dfrac{1}{m!}\sum\limits_{\sum k_i = n-1}(n-1)!\dfrac{t_{k_1}}{(k_1-1)!}\dfrac{t_{k_2}}{(k_2-1)!}\cdots\dfrac{t_{k_m}}{(k_m-1)!}$

我们发现$\dfrac{t_i}{(i-1)!}$是一个共同的结构，因此有$\dfrac{t_n}{(n-1)!}= \sum\limits_{m=1}^{n-1}\dfrac{1}{m!}\sum\limits_{\sum k_i = n-1}\prod\limits_{j=1}^{m}\dfrac{t_{k_j}}{(k_j-1)!}$

我们将发现，这个问题用指数生成函数求解起来是方便的。设$\dfrac{u_n}{n!} = \dfrac{t_n}{(n-1)!}$，即$u_n = nt_n$，那么$\dfrac{u_n}{n!}=\sum\limits_{m=1}^{n-1}\dfrac{1}{m!}\sum\limits_{\sum k_i = n-1}\prod\limits_{j=1}^{m}\dfrac{t_{k_j}}{k_j!}$。设$\widehat{U}(z) = \sum\limits_{n}\dfrac{u_n}{n!}z^n$，右侧是$U$的$m$元卷积的形式。因此两边同时乘以$z^n$对所有$n$累加，有

$[z^n]\widehat{U}(z)=[z^n]\sum\limits_{m=1}^{n-1}\dfrac{z}{m!}[\widehat{U}(z)]^{m}=[z^{n-1}]\sum\limits_{m\geq 1}\dfrac{[\widehat{U}(z)]^m}{m!}$

生成函数本身构成了自然对数幂级数的形式，因此

$=[z^{n-1}](e^{\widehat{U}(z)}-1)=[z^n]ze^{\widehat{U}(z)}$

因此得到方程$\widehat{U} = ze^{\widehat{U}}$。由拉格朗日反演定理得$[z^n]\widehat{U}(z)=\dfrac{n^{n-2}}{(n-1)!}=\dfrac{u_n}{n!}$。因此$t_n = \dfrac{u_n}{n}=n^{n-2}$。