组合数学：递推关系与生成函数

递推关系与生成函数

递推关系

斐波那契数列通项

俗话说，斐波那契数列的通项是：

$\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$，式子化简为:

$$\begin{aligned} a^2 &= a + 1 \\ a^2 - a-1 &= 0\\ a &= \frac{1 \pm \sqrt{5}}{2} \end{aligned}$$

$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$来：

$$\left\{ \begin{aligned} & 0 = c_1 + c_2 \\ \\ & 1 = \frac{1 + \sqrt{5}}{2}c_1 +\frac{1 - \sqrt{5}}{2}c_2 \end{aligned} \right. \\$$

解得：

$$\left\{ \begin{aligned} & c_1 = \frac{1}{\sqrt{5}} \\ \\ & c_2 = -\frac{1}{\sqrt{5}} \end{aligned} \right.$$

所以就得到了开头说的那个通项公式。

可以发现，解通项公式的过程和求常系数线性微分方程的方法是类似的，碰到一些的问题的处理方式也是类似的。

常系数线性齐次递推关系

通过上述的斐波那契数列的通项的求解，我们已经可以感受到递推关系的解法了。

若某序列$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 + a_1 h_{n - 1} + ... + a_k h_{n - k} = r^n(b_qn^q +b_{q - 1}n^{q - 1} + ...b_0)$$

则将

$$(c_0 + c_1n+..c_qn^{q})r^n$$

代入$h_n$，解出这些$c$来，就可以得到一个特解。如果$r$还是特征方程的根，且是$m$重根，则要代入

$$(c_0 + c_1n+..c_qn^{q})r^nn^m$$

可以看出，求特解时，就是把等式右边的非齐次项按$r^n$的指数分个类。再顺便看一下$r$是否是特征方程的解，若是的话要乘上$n$的次方项。特解的未知数个数取决于非齐次项中的多项式的次数，把这个式子套回去可以解出所有的未知数来。具体看下面的例子。

例：求$h_n = 2h_{n - 1} + n^2$的特解。
解：
特征方程：

$$x = 2$$

将

$$c_0 +c_1n+c_2n^2$$

代入得：

$$\begin{aligned} c_0 +c_1n+c_2n^2 &= 2 (c_0 +c_1(n-1)+c_2(n - 1)^2)+n^2 \\ c_0 +c_1n+c_2n^2 &= 2 c_0 + 2c_1n - 2c_1+ 2c_2n^2 - 4c_2n + 2c_2 + n^2 \\ (c_0 - 2c_0 + 2c_1 - 2c_2) + (c_1 - 2c_1+4c_2)n + (c_2 - 2c_2 - 1)n^2 &= 0 \end{aligned}$$

上式恒成立，因此：

$$\left\{ \begin{aligned} c_0 - 2c_0 + 2c_1 - 2c_2 &= 0 \\ c_1 - 2c_1+4c_2 &= 0 \\ c_2 - 2c_2 - 1 &= 0 \end{aligned} \right.$$

解得：
$
\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$的系数上。多项式在进行乘法时，会很自然地进行排列组合，排列组合计算的结果依然保留在系数上。我目前的理解是，生成函数就是用来计算排列组合的。

生成函数既然是用来计算排列组合的，但我们现在都是在通过排列组合反推生成函数。如果是用多个生成函数的乘积来计算总的生成函数，再算出方案数，那么我们还是要手动进行多项式乘法，这个过程和我们算排列组合的过程是一样的，计算量完全没有减少。那么，生成函数到底有什么用呢？

当生成函数是无穷级数时，生成函数的形式就美观了许多，比如：

$$\begin{aligned} \frac{1}{1-x}&=1+x+x^2+x^3... \\ \frac{1}{(1-x)^k}&=\Sigma\ _{n = 0}^{\infty}\tbinom{n + k - 1}{k - 1}x^n (由多重集的组合公式)\\ e^{x} &= 1 + \frac{x}{1} + \frac{x^2}{2!} + \frac{x^3}{3!} +... \\ e^{-x} &= 1 - \frac{x}{1} + \frac{x^2}{2!} - \frac{x^3}{3!} +... \\ \end{aligned}$$

这样，再求一个复杂的排列组合时，可以先求出简单的子问题的生成函数，才把这些生成函数相乘。当生成函数是无穷级数的时候，往往能进行某些化简。求最终的生成生成函数的某个系数，就可以得到对应的方案数。

看一道经典例题：
例：确定苹果、橘子、香蕉和梨的袋装水果的袋数$h_n$的生成函数，其中各袋要有偶数个苹果，最多两个橘子，3的倍数个香蕉，最多一个梨。然后从该生成函数求出$h_n$的公式。
解：

$$\begin{aligned} g(x) &= (1 + x^2 + x^4 + ...)(1 + x + x^2)(1 + x^3 + x^6 + ...)(1 + x) \\ &= \frac{1}{1 - x^2}\frac{1}{1 - x^3}(1 + x + x^2)(1 + x) \\ &= \frac{(1 + x + x^2)(1 + x)}{(1 - x^2)(1 - x^3)} \\ &= \frac{(1 + x + x^2)(1 + x)}{(1 - x)(1 + x + x^2)(1 - x)(1+x)} \\ &= \frac{1}{(1 - x)^2} = \Sigma\ _{n = 0}^{\infty}\tbinom{n + 1}{1}x^n \end{aligned} \\$$

$\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$。
解：

$$\begin{aligned} g^{(e)}(x) &= (1+\frac{x^2}{2!}+\frac{x^4}{4!}+...)(\frac{x}{1}+\frac{x^3}{3!} + ...)(1 + \frac{x}{1} + \frac{x^2}{2!} + \frac{x^3}{3!} +...)^2 \\ &= \frac{(e^x + e^{-x})}{2}\frac{(e^x - e^{-x})}{2}e^{2x} \\ &= \frac{e^{4x}-1}{4} \\ &= \Sigma_{n = 0}^{\infty}\frac{4^nx^n}{4n!} - \frac{1}{4}\\ \end{aligned}$$

$\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)$，可以得到：

$$\begin{aligned} g(x) &= h_0 &+ h_1x &+ h_2x^2...+h_nx^n \\ -5xg(x) &= &- 5h_0x &- 5h_1x^2...-5h_{n - 1}x^n \\ 6x^2g(x) &= & &+6h_0x^2...+6h_{n - 2}x^n \\ \end{aligned}$$

把上面三个式子左右相加，由$h_n - 5h_{n - 1} + 6h_{n - 2} = 0$：

$$\begin{aligned} (1 - 5x - 6x^2)g(x) &= h_0 + (h_1 - 5h_0)x \\ (1 - 5x - 6x^2)g(x) &= x \\ g(x) &= \frac{x}{1 - 5x - 6x^2} \\ g(x) &= \frac{1}{1 - 3x} - \frac{1}{1 - 2x} \\ g(x) &= (1 + 3x + 3^2x^2 +...) - (1+2x+2^2x^2+...) \end{aligned}$$

$\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)，把编程问题变成数学问题。

生成函数是用来解决组合问题的，当问固定数量的方案数时，就要想到生成函数了。在求排列时，要利用之前的方法，求出指数生成函数，再在结果前乘一个阶乘。

递推关系对应一个生成函数，可以用生成函数来解递推关系。对普通的线性方程，这种解法太麻烦了，还不如用普通的解法。对于一些比较复杂的递推关系，生成函数才能发挥出它的用途。