生成函数(mother function)是一种非常诡异的求数列通项的方法。核心思想是把数列\(a\)的第\(n\)项当作某个某个位置函数\(A(x)\)的\(x^n\)系数系数。我们通过递推式来求得\(A(x)\)，然后将\(A(x)\)展开来得到\(x^n\)的系数既是数列的通项：
\begin{equation}A(x)=\sum_{i=0}{a_i*x^i}\end{equation}
下面我们就以几个循序渐进的例子来讲解这个生成函数方法的使用。
线性递推
线性递推式是数列递推式中最简单的递推式，其形式如下：
\begin{equation}a_{n+1}=p*a_n+q\end{equation}
其中\(p,q\)为常数。这里为了简单起见，我们以\(p=2,q=1,a_0=0\)为例来说明生成函数方法的使用。假设该数列的生成函数为\(A(x)=\sum_{i=0}{a_ix^i}\),则我们可以得到
\begin{equation}\begin{aligned}A(x)&=\sum_{i=0}{a_ix^i}\\&=a_0 +\sum_{i=0}{a_{i+1}x^{i+1}}\\&=a_0+\sum_{i=0}{(2*a_i+1)x^{i+1}}\\&=a_0+x*(2*\sum_{i=0}{a_ix^i}+\sum_{i=0}{x^i})\\&=a_0+x*(2*A(x)+\sum_{i=0}{x^i})\\&=a_0+2x*A(x)+\frac{x}{1-x}\\&=2x*A(x)+\frac{x}{1-x}\end{aligned}\end{equation}
由此我们可以得到：
\begin{equation}\begin{aligned}A(x)&=\frac{x}{(1-x)(1-2x)}\\&=x\left\{\frac{2}{1-2x}-\frac{1}{1-x}\right\}\\&=\{2x+(2x)^2+(2x)^3+\cdots\}-\{x+x^2+x^3+\cdots\}\\&=\sum_{i=1}{(2^i-1)x^i}\end{aligned}\end{equation}
所以，通过这么长的递推,我们终于得到了\(a_i=2^i-1\)，虽然说这个递推高一水平的人就可以做出来。但是我们总是会经历一个从这TM也需要证到这TM也能证的过程吧。
伪线性递推
所谓伪线性递推是我生造的一个词，其递推结构与之前的一样，只不过\(q,p\)可能为\(i\)的线性表示。下面以例子来说明：
\begin{equation}a_{i+1}=2a_i+i \quad a_0=1\end{equation}
这里重复之前的推导过程，我们可以得到:
\begin{equation}\frac{A(x)-1}=2x*A(x)+x\sum_{i=1}{ix^i}\end{equation}
此时我们需要利用微积分的知识：
\begin{equation}\sum_{i=1}{ix^i}=\sum_{i=1}{x(\frac{d(x^n)}{dx})}=x(\frac{d}{dx})\sum_{i=1}{x^i}=x(\frac{d}{dx})\frac{1}{1-x})=\frac{x}{(1-x)^2}\end{equation}
所以，我们将上式带入到之前，可以得到：
\begin{equation}A(x)=\frac{1-2x+2x^2}{(1-x)^2(1-2x)}=\frac{-1}{(1-x)^2}+\frac{2}{1-2x}\end{equation}
又因为
\begin{equation}\frac{1}{(1-x)^2}=\sum_{i=0}{(i+1)x^i}\end{equation}
所以
\begin{equation}a_i=2^{i+1}-i-1\end{equation}
斐波那契数列
斐波那契数列作为数列里面最经典的例子，本文自然不能放过。其数列递推式如下:
\begin{equation}F_{n+2}=F_{n+1}+F_n \quad w.r.t. \quad F_0=0,F_1=1\end{equation}
同样 ，设其生成函数为\(A(x)\) ，我们可以得到
\begin{equation}\begin{aligned}A(x)&=x+x(F_2x+F_3x^2+F_4x^3+\cdots)\\&=x+x\left\{\{F_1x+F_2x^2+F_3x^3+\cdots\}+\{F_0x+F_1x^2+F_2x^3+\cdots\}\right\}\\&=x+x(A(x)+xA(x))\end{aligned}\end{equation}
所以
\begin{equation}A(x)=\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\left\{\frac{1}{(1-(1+\sqrt{5})x/2}-\frac{1}{1-(1-\sqrt{5})x/2}\right\}\end{equation}
然后经过一些稀里糊涂的中间步骤，我们可以得到
\begin{equation}F_i=\frac{1}{\sqrt{5}}\big((\frac{1+\sqrt{5}}{2})^i-(\frac{1+\sqrt{5}}{2})^i\big)\end{equation}
双索引递推
在上文中我们只涉及到了一个变量\(x\)，此时对应只有一个索引的数列的情况。对于有两个不同索引的数列递推式，单一变量的生成函数不再适用，我们需要添加另外的一个变量\(y\)来构造双变量的生成函数\(B(x,y)\)。这种情况。在排列组合问题中，双索引的数列是非常常见的。例如，给定非负整数\(n,k\)且\(0\le k\le n\)，我们能从\(\{1,2,\cdots , n\}\)中得到多少个不同的\(k\)子集。
此时我们假设\(f(n,k)\)是该问题的解，我们可以非常容易的得到下面的递推式
\begin{equation}\label{二项式}f(n,k)=f(n-1,k)+f(n-1,k-1) \quad w.r.t. f(n,0)=1\end{equation}
此时我们定义一个新的生成函数
\begin{equation}B_n(x)=\sum_{k\ge0}{f(n,k)x^k}\end{equation}
根据原来的递推公式\ref{二项式}，我们可以得到
\begin{equation}\begin{aligned}& B_n(x)-1=(B_{n-1}(x)-1)+xB_{n-1}(x)\\\Rightarrow & B_n(x)=(1+x)B_{n-1}(x)\\\Rightarrow & B_n(x)=(1+x)^n\\\Rightarrow & f(n,k)=\binom{n}{k}\end{aligned}\end{equation}
双变量生成函数
对付一些简单的双索引递推公式，我们很多时候用单变量的生成函数即可处理。然而，不是所有的双索引递推都是这么简单的。考虑下面的一个排列组合的例子：将一个大小为\(n\)的集合分割为\(k\)个不为空的子集。例如\(n=4,k=2\)时，其不同划分有如下几种：
\begin{equation} (12),(34);(13),(24);(14),(23);(123),(4);(124),(3);(134),(2);(234)(1) \end{equation}
我们用\(f(n,k)\)来代表其不同的子集划分数。根据\(\{n\}\)这个元素是否单独作为一个集合，我们可以把原来的问题分为两种情况：
-
是单独集合，原问题规约到了将\(n-1\)个元素划分为\(k-1\)子集的问题，此时的子集划分个数为\(f(n-1,k-1)\);
-
不是单独集合，此时对于任意的一个\(n-1\)元素的\(k\)划分，元素\(n\)可以插入到这\(k\)个划分的任意一个集合中，此时的子集划分个数为\(f(n-1,k)*k\)。
所以，我们有如下的递推式：
\begin{equation} f(n,k)=f(n-1,k-1)+kf(n-1,k) \quad w.r.t.\quad n\ge k\ge 0\end{equation}
此时，我们设
\begin{equation} B_k(x)=\sum_{n}{f(n,k)x^n}\end{equation}
由此定义我们可以得到：
\begin{equation}\begin{aligned}B_k(x)&=\sum_{n}{f(n,k)x^n}\\&=\sum_{n}{(f(n-1,k-1)x^n+kf(n-1,k)x^n}\\&=x\sum_{n}{f(n-1,k-1)x^{n-1}}+kx\sum_{n}{f(n-1,k)x^{n-1}}\\&=xB_{k-1}(x)+kxB_k(x)\end{aligned}\end{equation}
所以，我们可以得到\(B_k(x)\)的解析式为
\begin{equation}B_k(x)=\frac{x}{1-kx}B_{k-1}(x)=\frac{x^k}{(1-x)(1-2x)(1-3x)\cdots(1-kx)}\end{equation}
现在我们的问题就在于如何求出后面的展开式。为此，我们定义一个记号\([x^n]B(x)\)为函数\(B(x)\)展开式中\(x^n\)的系数。此时
\begin{equation}\begin{aligned}f(n,k)&=[x^n]\left\{\frac{x^k}{(1-x)(1-2x)(1-3x)\cdots(1-kx)}\right\}\\&=[x^{n-k}]\left\{\frac{1}{(1-x)(1-2x)(1-3x)\cdots(1-kx)}\right\}\\&=[x^{n-k}]\sum_{r=1}^{k}{\frac{{\alpha}_r}{1-rx}} \\&=\sum_{r=1}^{k}{{\alpha}_r[x^{n-k}]\frac{1}{1-rx}}\\&=\sum_{r=1}^{k}{{\alpha}_r r^{n-k}}\end{aligned}\end{equation}
在这里我们得到了一个看上去非常美的结果，但是其实目前还没啥用，因为我们还没有求出满足下式的常数\({\alpha}_r\)。
\begin{equation}\frac{x^k}{(1-x)(1-2x)(1-3x)\cdots(1-kx)}=\sum_{i=1}^{k}{\frac{{\alpha}_i}{1-ix}}\end{equation}
为了得到\({\alpha}_r\),我们又需要利用一些诡异的技巧。首先在上式两边都乘以\(1-rx\)，然后令\(x=1/r\)。此时右边就只剩下\({\alpha}_r\)了。所以
\begin{equation}\begin{aligned}{\alpha}_r&=\frac{1}{(1-1/r)(1-2/r)\cdots (1-(r-1)/r)(1-(r+1)/r)\cdots (1-k/r)}\\&={(-1)}^{k-r}\frac{r^{k-1}}{(r-1)!(k-r)!}\end{aligned}\end{equation}
将此式带入之前的式子，可得
\begin{equation}f(n,k)=\sum_{r=1}^{k}{(-1)^{k-r}}{\frac{r^n}{r!(k-r)!}}\end{equation}
现在是不是感觉很爽!
其实写本篇文章的动机是为了求解这个递推式
\begin{equation}f(m,n)=m*(f(m-1,n-1)+f(m,n-1))\quad n \geq m \quad f(m,m)=m! \, f(1,n)=1\end{equation}
该递推式的背景是一道微软的面试题，具体的内容忘记了。这是一个写代码的题，主要考察点是DP优化。但是正如前面所说的，我们可以直接求出其通项公式。其求解过程跟之前的基本一样.此时，我们设
\begin{equation} B_k(x)=\sum_{n}{f(n,k)x^n}\end{equation}
由此定义我们可以得到：
\begin{equation}\begin{aligned}B_k(x)&=\sum_{n}{f(n,k)x^n}\\&=k\sum_{n}{(f(n-1,k-1)x^n+f(n-1,k)x^n}\\&=kx\sum_{n}{f(n-1,k-1)x^{n-1}}+kx\sum_{n}{f(n-1,k)x^{n-1}}\\&=kx(B_{k-1}(x)+B_k(x))\end{aligned}\end{equation}
所以，我们可以得到\(B_k(x)\)的解析式为
\begin{equation}B_k(x)=\frac{kx}{1-kx}B_{k-1}(x)=\frac{x^kk!}{(1-x)(1-2x)(1-3x)\cdots(1-kx)}\end{equation}
由此可得
\begin{equation}\begin{aligned}f(n,k)&=k![x^n]\left\{\frac{x^k}{(1-x)(1-2x)(1-3x)\cdots(1-kx)}\right\}\\&=k![x^{n-k}]\left\{\frac{1}{(1-x)(1-2x)(1-3x)\cdots(1-kx)}\right\}\\&=k![x^{n-k}]\sum_{r=1}^{k}{\frac{{\alpha}_r}{1-rx}} \\&=k!\sum_{r=1}^{k}{{\alpha}_r[x^{n-k}]\frac{1}{1-rx}}\\&=k!\sum_{r=1}^{k}{{\alpha}_r r^{n-k}}\\&=k!\sum_{r=1}^{k}{(-1)^{k-r}}{\frac{r^n}{r!(k-r)!}}\end{aligned}\end{equation}