递推关系与生成函数
递推关系
斐波那契数列通项
俗话说，斐波那契数列的通项是：
$\frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2})^n - \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})^n (n \geq 0)$
看上去如此玄妙的式子是怎么推出来的呢？
我们都知道，斐波那契数列是:$0,1,1,2,3,5,8,13,21,34,55…$。规律是，从第三项开始，后一项等于前两项之和，即$h_n = h_{n - 1} + h_{n - 2} (n >= 2), h_0 = 0, h_1 = 1$。通过观察，我们发现这个数列增长得十分快，速度似乎和指数函数差不多。因此我们产生了大胆的假设：假设$h_n = a^n$。
由通项公式：$h_n = h_{n - 1} + h_{n - 2}$,$a^n = a^{n - 1}+a^{n - 2}$。由于此时$n\geq2,a_n\neq0$，式子化简为:
$h_n$有多个解，这些解的线性组合同样满足条件。因此可以将解表示为$h_n = c_1(\frac{1 + \sqrt{5}}{2})^n + c_2(\frac{1 - \sqrt{5}}{2})^n$。注意到还有条件$h_0 = 0, h_1 = 1$没有使用。等式有两个，未知数也有两个，因此可以解出$c_1, c_2$来：
解得：
所以就得到了开头说的那个通项公式。
可以发现，解通项公式的过程和求常系数线性微分方程的方法是类似的，碰到一些的问题的处理方式也是类似的。
常系数线性齐次递推关系
通过上述的斐波那契数列的通项的求解，我们已经可以感受到递推关系的解法了。
若某序列$h_i$满足递推关系$h_n = a_1 h_{n - 1} + … + a_k h_{n - k} + b$，其中$a_i,b$可能依赖于$n$,$a_k \neq 0$，则称序列满足k阶线性递推关系。若$b = 0$，则还称它是齐次。若$a_i$都是常数，则称它还是常系数。正如标题所讲，本节讨论常系数线性齐次递推关系。
由递推关系得到的方程$x^k = a_1x^{k - 1} + … a_k$被叫做特征方程。特征方程的k个根叫特征根，一个特征根对应一个原递推关系的解。如果p是根，则$p^n$是$h_n$的一个解。如果p是二重根，则$p^n,np^n$是$h_n$的解，依此类推。$h_n$解的最终表达形式是每个特征根对应的解的线性组合。如果此时数列$h_n$有初始值，那么再解个多元一次方程，就可以完全求出$h_n$的通项了。
综上，求常系数线性齐次递推关系就是先解一个一元多次的特征方程，求出数列的表达形式，才根据初始条件解一个多元一次方程，得到数列的通项。
常系数线性非齐次递推关系
由于特征方程有多个根，因此递推关系有多个解，这些解要以通解的形式写出来。而某一个单独能满足条件的递推关系叫做特解。又根据叠加原理，$h_n + a_1 h_{n - 1} + … + a_k h_{n - k} = b$和$h_n + a_1 h_{n - 1} + … + a_k h_{n - k} = c$的解加起来，就是$h_n + a_1 h_{n - 1} + … + a_k h_{n - k} = b + c$的解。因此对于一个常系数线性非齐次递推关系，不用再像之前一样直接求出通解，而是只要求出一个特解，再加上齐次情况的通解，就可以得到该递推关系的特解。我们现在要完成的任务就是求常系数线性非齐次递推关系的特解。
求非齐次的特解我只知道公式，不理解公式的由来，这里就直接给公式了。若：
则将
代入$h_n$，解出这些$c$来，就可以得到一个特解。如果$r$还是特征方程的根，且是$m$重根，则要代入
可以看出，求特解时，就是把等式右边的非齐次项按$r^n$的指数分个类。再顺便看一下$r$是否是特征方程的解，若是的话要乘上$n$的次方项。特解的未知数个数取决于非齐次项中的多项式的次数，把这个式子套回去可以解出所有的未知数来。具体看下面的例子。
例：求$h_n = 2h_{n - 1} + n^2$的特解。
解：
特征方程：
将
代入得：
上式恒成立，因此：
解得：
$
\left\{
\begin{aligned}
c_0 &= -6 \\
c_1 &= -4 \\
c_2 &= -1
\end{aligned}
\right.
$
得到一个特解：
$h_n = -6 - 4n - n^2$
生成函数
生成函数的用处
若有一个数列$h_0,h_1,h_2…$，则它的生成函数定义为$g(x) = h_0 + h_1x + h_2x^2…$。若数列是无穷的，则这个级数也是无穷的。
生成函数乍看上去非常奇怪，因此必须要先理解生成函数是用来做什么的。生成函数正是为了解决一些问题而定义出来的。
设$h_n$为从集合$\{2a\}$中取出n个字母的方案数，则数列为$1,1,1,0,0…$，生成函数$g_1(x) = 1 + x + x^2$。同理，从集合$\{3b\}$中取出n个字母的方案数得到的生成函数$g_2(x) = 1 + x + x^2 + x^3$。那么现在，从集合$\{2a,3b\}$中取出n个字母的方案数得到的生成函数是什么呢？
还是先求出方案数序列。$h_0 = 1,h_1 = |\{a,b\}| = 2, h_2 = |\{aa,ab,bb\}| = 3,h_3 = |\{aab,abb,bbb\}| = 3, h_4 = |\{aabb,abbb\}| = 2, h_5 = |\{aabbb\}| = 1$。则其生成函数$g(x) = 1 + 2x + 3x^2 + 3x^3 + 2x^4 + x^5 = (1 + x + x^2)(1 + x + x^2 + x^3) = g_1(x)g_2(x)$。“巧合”发生了。一个问题的解的生成函数等于子问题的解的生成函数相乘。
生成函数的本质，就是把“总和”为$n$的方案数放到$x^n$的系数上。多项式在进行乘法时，会很自然地进行排列组合，排列组合计算的结果依然保留在系数上。我目前的理解是，生成函数就是用来计算排列组合的。
生成函数既然是用来计算排列组合的，但我们现在都是在通过排列组合反推生成函数。如果是用多个生成函数的乘积来计算总的生成函数，再算出方案数，那么我们还是要手动进行多项式乘法，这个过程和我们算排列组合的过程是一样的，计算量完全没有减少。那么，生成函数到底有什么用呢？
当生成函数是无穷级数时，生成函数的形式就美观了许多，比如：
这样，再求一个复杂的排列组合时，可以先求出简单的子问题的生成函数，才把这些生成函数相乘。当生成函数是无穷级数的时候，往往能进行某些化简。求最终的生成生成函数的某个系数，就可以得到对应的方案数。
看一道经典例题：
例：确定苹果、橘子、香蕉和梨的袋装水果的袋数$h_n$的生成函数，其中各袋要有偶数个苹果，最多两个橘子，3的倍数个香蕉，最多一个梨。然后从该生成函数求出$h_n$的公式。
解：
$\therefore h_n = n + 1$
指数生成函数
在求多重集合的排列问题，比如从集合$\{2a,3b\}$中能拼出多少个长度为3的单词这样的问题时，我们要先求出各种组合的方案，除以每个数出现次数的阶乘，最后再乘上总数的阶乘。生成函数既然是解决排列组合问题的，自然也能解决此类多重集排列问题。在刚才的生成函数的基础上，加上我们平时求多重集排列的方法，就得到了指数生成函数的概念。
类似地，对于序列$h_n$，其指数生成函数定义为$g^{(e)}(x) = h_0 + h_1\frac{x}{1} + h_2\frac{x^2}{2}…$。由于在分母上除了一个阶乘，生成函数很容易变成$e^x$之类的形式，大概指数生成函数的名字就是这样得来的。$x^n$前面的系数再乘一个$n!$就是多重集n排列的方案数。
用法看例题即可快速理解：
例：如果偶数个方格被涂成红色以及奇数个方格被涂成白色，试确定用红、白、蓝和绿为1行$n$列棋盘的方格着色的方案数$h_n$。
解：
$\therefore h_0 = 0, h_n = 4^{n - 1}(n \geq 1)$
无穷级数带了一个常数项，因此通项在0的时候要单独写出来。
ACM中也有一些题要用到生成函数的思想，但解题时最后还是要用FFT。等以后碰到了相关的题目，我会把题解写在ACM分类中。
递推关系与生成函数
用生成函数解递推关系
好吧，生成函数还是有其他用途的，比如求解递推关系。不然为什么课本把这两个概念放在同一章呢？
只用一道例题来说明用生成函数求常系数线性齐次递推关系的方法：
例：
求$h_n - 5h_{n - 1} + 6h_{n - 2} = 0,h_0 = 0, h_1 = 1, h_2 = 5$的解。
设数列的生成函数为$g(x)$，可以得到：
把上面三个式子左右相加，由$h_n - 5h_{n - 1} + 6h_{n - 2} = 0$：
$\therefore h_n = 3^n - 2^n$
虽然感觉这种方法很高大上，但是比起直接解特征方程来，这种方法还是太麻烦了。既然如此，我们是不是可以不用生成函数来解递推关系的问题了？
当然不是。仔细看一下上面的解题过程，我们求解递推关系完全是在对生成函数$g(x)$做各种各样的操作，好像和递推关系是否线性、齐次什么的一点关系也没有。对于最开始特征方程法解不了的一些递推，用生成函数可能可以解出来。不妨看下面一个问题：
例：（Catalan数）对于一个有$n$个节点的二叉树，在保持左右子树的有序性，即不考虑任何变换的情况下，有多少种可能的形态？（比如$n = 2$时有两种，一个节点是根，另一个节点是根的左儿子或者右儿子）
解：
为了方便，记$n$个节点的二叉树的形态数为$h_n$。
考虑把问题转换成子问题。当现在有$n$个节点时，我们需要先选一个节点为根，再把剩下的节点放到根的左右子树中。如果根的左子树放了$a$个节点，那么右子树就要放$n - 1 - a$个节点，也就是说左右子树的节点和一定是$n - 1$。在这种情况下，问题就变成了两个子问题：$a$个节点的二叉树和$n - 1 - a$个节点的二叉树有多少个？我们把这两个数算出来，再一乘，就是当左边放$a$个节点时，$n$个节点的二叉树的形态数。
当然，我们不能只算$a$个节点，因为根左右子树的节点数可能是$0, 1，2，3…n - 1$。因此我们要讨论所有情况，并且把每种情况下的总情况数算出来，再进行累加。因此可以得到递推公式:
$h_n = \Sigma_{i = 0}^{n - 1}h_{i}h_{n-1-i}$
特别地，这里要令$h_0 = 1$。
由于这个递推关系根本不是线性的，我们无法用特征函数来解。考虑用生成函数$g(x)$来表示数列的每一项，即：
$g(x) = \Sigma_{i = 0}^{\infty}h_ix^i$
突然，我们发现：
$g^2(x) = h_0 + (h_0h_1 + h_1h_0)x + (h_0h_2 + h_1h_1 + h_2h_0)x^2 + …$
每一项中x的系数在递推公式中都可以找到。把递推公式代入式子：
$g^2(x) = h_0 + h_2x + h_3x^2 + …$
由于$h_0 = h_1 = 1$：
$
\begin{aligned}
g^2(x) &= h_1 + h_2x + h_3x^2 + … \\
&= \frac{1}{x}(h_1x + h_2x^2 + h_3x^3 + …) \\
&= \frac{1}{x}(g(x) - h_0) \\
&= \frac{1}{x}(g(x) - 1) \\
xg^2(x) &= g(x) - 1 \\
\end{aligned}
\\
\begin{aligned}
xg^2(x) - g(x) + 1 &= 0 \\
g(x) &= \frac{1 \pm \sqrt{1-4x}}{2x}
\end{aligned}
$
由于$h_0 = 0$，$g(x) = \frac{1 - \sqrt{1-4x}}{2x} = \frac{1}{x}(\frac{1}{2} - \frac{1}{2}(1 - 4x)^{1/2})$
根据牛顿二项式定理：
$
\begin{aligned}
(1 + x)^{1/2} = 1 + \Sigma_{n = 1}^{\infty}\frac{(-1)^{n - 1}}{n\times 2^{2n-1}}\tbinom{2n - 2}{n - 1}x^n
\end{aligned}
$
所以：
$
\begin{aligned}
(1 - 4x)^{1/2} &= 1 + \Sigma_{n = 1}^{\infty}\frac{(-1)^{n - 1}}{n\times 2^{2n-1}}\tbinom{2n - 2}{n - 1}x^n(-4)^n \\
&= 1 + \Sigma_{n = 1}^{\infty}\frac{(-1)^{1}}{n\times 2^{-1}}\tbinom{2n - 2}{n - 1}x^n \\
&= 1 - 2\times \Sigma_{n = 1}^{\infty}\frac{1}{n}\tbinom{2n - 2}{n - 1}x^n
\end{aligned}
$
套回开始的式子中:
$g(x) = \Sigma_{n = 1}^{\infty}\frac{1}{n}\tbinom{2n - 2}{n - 1}x^{n - 1}$
所以，$h_n = \frac{1}{n + 1}\tbinom{2n}{n}$。
如果我们把$h_0$看成第一项的话，那么第$n$项的值就是$\frac{1}{n}\tbinom{2n - 2}{n - 1}$。这个数就是著名的卡特兰(Catalan)数。
在这个过程中，我们完全是在对生成函数进行求解，而没有管递推关系的形式是怎么样的。这其中最妙的一步是发现了$g^2(x)$正好可以得到递推关系中的右半部分，只能说这种解法不是推算出来，而是突发奇想的。
总结
有时候推出来看似花里胡哨的递推关系，只要式子是线性的，就可以利用特征方程的方法求出通项来，从而把O(n)的时间复杂度变成O(1)，把编程问题变成数学问题。
生成函数是用来解决组合问题的，当问固定数量的方案数时，就要想到生成函数了。在求排列时，要利用之前的方法，求出指数生成函数，再在结果前乘一个阶乘。
递推关系对应一个生成函数，可以用生成函数来解递推关系。对普通的线性方程，这种解法太麻烦了，还不如用普通的解法。对于一些比较复杂的递推关系，生成函数才能发挥出它的用途。
