生成函数

普通生成函数(OGF)

定义与严格化

对于一个数列\(\{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)\)。