递推式(Recurrence)与生成函数(Generating Function)

前言

原文写于2014年3月22日。修订于2018年7月14日。

也是终于完成了这个系列第二篇，在寻找良好素材的时候也无意中发现了不少相关方面的优秀资料，一时兴起而做的决定为自己也带来了诸多益处，这实在令人欣慰.

用生成函数求解递推式是一个非常机械的过程，按照流程一步步做就能得到答案。不过大多数时候也并不像听上 去那么容易—如之前组合恒等式的证明那样，我们需要注意和处理令人厌烦的角标。

本文不期望读者能够掌握什么具体的知识，但如若能够为诸君于某刻解决问题时作一份参考，亦或是能有些许思路上的共鸣，之于我都将是莫大的荣誉。

0.符号约定

$[z^n]R(z)$意为多项式$R(z)$中$z^n$的系数。

我们以$<a_n>$作为数列$<a_1, a_2, \cdots, a_n, \cdots>$的缩写。

若$condition$为真，则我们有$[condition] = 1$，否则为$0$。

没有明确说明的情况下，$G(z),F(z)$意为数列$<g_n>,<f_n>$的生成函数。

1.定义与基本性质

一般来说，给定一个序列$<g_n>$，其生成函数(Ordinary Generating Function)$G(z)$定义如下：

$$G(z) = g_0 + g_1 z + g_2 z^2 + \cdots = \sum_{n \ge 0}^{\infty} g_n z^n$$

尽管定义中的$z$并没有被指明是一个什么样的东西，它仅仅只是一个符号，或者某种特征的替代表示，但为了讨论方便，也为了迎合我们的需要，我们视$G(z)$为一个复变量的函数且$\lvert z \rvert <1$。

设$F(z),G(z)$分别为序列$<g_n>,<f_n>$的生成函数，通过一些简单的计算—加法，积分，数乘等，我们可以发现：

$$\alpha F(z) + \beta G(z) = \sum_n(\alpha f_n + \beta g_n)z^n$$ $$z^mG(z) = \sum_n g_{n-m}z^n$$ $$G(cz) = \sum_n c^n g_n z^n$$ $$G'(z) = \sum_n (n+1) g_{n+1} z^n$$ $$\int_0^z G(t)dt = \sum_{n \ge 1}{1 \over n}g_{n-1}z^n$$ $$F(z)G(z) = \sum_n(\sum_k f_k g_{n-k})z^n$$

最后一个等式看起来非常的熟悉，在样式上似乎是我们在前一篇所提到过的卷积，应用前面曾提到的些许结论，我们令数列$<f_k>$为$<1,1,\cdots>$，则可得到:

$$\begin{align} (1 + z + z^2 + ...)G(z) &= \sum_n(\sum_{k \le n}g_k)z^n \\ \frac{1-z^n}{1-z}G(z) &= \sum_n(\sum_{k \le n}g_k)z^n \\ \frac{1}{1-z}G(z) &= \sum_n(\sum_{k \le n}g_k)z^n \end{align}$$

这是一个非常有用的等式，他告诉我们用$1 \over 1-z$来乘以一个生成函数，会得到其数列的自累加的生成函数。

注意到我们这里用了一些幂级数的基本知识（即$F(x)$的计算部分），实际上，这也正是我们引入生成函数的原因—通过一些分析的手段去解决离散的，有关于数列的问题。

在这里我们不会用到什么深奥的幂级数知识，但即便如此，生成函数作为工具也已经十分强大。

简单的关于幂级数的知识可以让我们得到许多生成函数的封闭形式，例如调和数列$H_n = <0,1,{1 \over 2},{1 \over 3},{1 \over 4},\cdots>$的生成函数：

$$\sum_{n \ge 1}{1 \over n}z^n = ln{1 \over 1-z}$$

2.与递推式

我们希望借助幂级数来解决一些关于数列的问题，例如通过数列的递推式去求解通项公式，这也是我们引入生成函数的原因，那么它能够胜任么？

我们首先来看一个简单的例子。

ex.2.1 一个经典问题

假设我们有$n$个数$a_1,\cdots,a_n$，这$n$个数的乘积需要通过$n-1$次乘法来加以确定，因而我们要问，在乘积$a_1\cdots a_n$中有多少种插入括号的方法 $g_n$，使得乘法的次序被完全指定（我们假定交换律并不成立）。

我们这样来思考这个问题，我们为这$n$个数不断的添置括号（当然是合法的嵌套形式），直到置完成$n$个括号，这时候已经不存在游离于括号之外的因子，让我们来看看添置第$n-1$个括号的情形，由于在添置第$n-1$个括号之前我们已经添置了$n-2$个括号，由于每一个括号将两个因子（形式上的）“合成”了一个因子，在添置$n-2$个括号之后，$n$个因子必然已经被分裂成这样的形式$(a_1a_2\cdots a_k)(a_{k+1}\cdots a_n)$，进而我们就能够确定一个关于$g_n$的递推式

$$g_n = g_1g_{n-1}+g_2g_{n-2}+\cdots +g_{n-1}g_1 = \sum_{k=1}^{n-1} g_kg_{n-k}, n \ge 2, g_1 = 1$$

由于递推式并没有$g_0$，因而生成函数以$g_1$作为第一项，即有

$$G(z) = g_1 + g_2z + \cdots = \sum_{k=1}^{\infty} g_k z^{k-1}$$

数列$g_n$的递推式是一个卷积式，初看并没有什么头绪，不过我们可以做一些简单的尝试，很容易观察到，如果我们对$G(z)$进行平方，就能够得到$g_ig_j$此类的项。

$$\begin{align} G^2(z) &= g_1g_1 + g_1g_2z + g_2g_1z + \cdots + g_ng_nz^{2(n-1)} + \cdots \\ G^2(z) &= \sum_{k=1}^1 g_kg_{2-k} + \sum_{k=1}^2 g_kg_{3-k}z + \cdots + \sum_{k=1}^{n-1} g_kg_{n-k}z^{n-2} + \cdots \\ &= {1 \over z}(g_2z + \cdots g_nz^{n-1} + \cdots) \end{align}$$

这样我们很容易就能看出

$$G(z) = zG^2(z) + g_1 = zG^2(z) + 1$$

经由一些简单的代数运算，我们就能得到

$$G(z) = {1 - \sqrt {1-4z} \over 2z}$$

实际上求解上面的代数方程我们会得到关于$G(z)$的两个封闭表达式，然而其中有一个在$z\rightarrow 0$时得到$\infty$，尽管我们没有定义$n=0$的情形，但是对于没有因子的情形，一个空的括号应该表示一种添置括号的方法，因而$G(0)=1$更加符合我们的逻辑。且有

$$\lim_{x \to 0} {1 - \sqrt {1-4z} \over 2z} = 1$$

之后，只需要运用你在高数课上习得的知识，将$G(z)$展开为的某一幂级数的形式，其每一项的系数即为数列$<g_n>$的值。

ex.2.2 源于快速排序

我们都知道快排的平均时间复杂度是$O(nlog_2 n)$，对于这个结果的分析在许多算法相关的书籍上都有介绍，不过今天让我们来看看对于$n$个随机数进行快速排序总的比较次数的平均情况。

我们假设待排序数列为：

$$a_1,\cdots,a_n$$

每一个枢纽元$a_k$都将待排序数列分为两部分。由于数列完全随机，事实上我们可以认为这两部分中待排序数的个数与混乱程度没有什么差异，又由于对于$a_1,\cdots,a_n$一共有$n$种选取枢纽元的方法，考虑到选取枢纽元之后需要进行$n-1$次比较,设$n$个数进行快速排序总的比较次数$c_n$,我们能够建立如下递推式:

$$c_n = n-1 + {1 \over n}\sum_{k=1}^{n}(c_k+c_{n-k}) = n-1 + {2 \over n}\sum_{k=1}^{n}c_k$$

注意到我们有$n$种选取枢纽元的方法，因此平均情况的比较次数应为这$n$方法比较次数总和的$\frac{1}{n}$。

令$C(z)$为$<c_n>$的生成函数，我们发现递推式中有一个自累加的项，因而结合第一节中的结论，我们有：

$$\begin{align} C(z) &= c_1 + \sum_{n=2}^\infty (n-1 + {2 \over n}\sum_{k=1}^{n}c_k)z^{n-1} \\ C'(z) &= \sum_{n=2}^\infty ((n-1)n+2\sum_{k=1}^{n}c_k)z^{n-1} \\ &= \sum_{n=2}^\infty n(n-1)z^{n-1} + 2\sum_{n=2}^\infty \sum_{k=1}^{n} c_k z^{n-1}\\ &= z({1 \over 1-z})'' + {2C(z) \over 1-z}\\ &= {2z \over (1-z)^3} + {2C(z) \over 1-z} \end{align}$$

求解这个微分方程,我们就能得到

$$C(z) = {-2ln(1-z)-2x \over (1-z)^2}$$

来看看我们是怎么处理上面这个递推式的，在我们发现可能可以用到之前某些已经得到的结论的时候，${2 \over n}\sum_{k=1}^{n}c_k$项上的$1/n$就变成了最大的障碍，因此我们需要消除它，而对$C(z)$求导无疑就是最直接的选择。

ex.2.3 它看起来奇怪而熟悉

或许更多时候我们遇到的递推式会是这样的

$$a_n=4a_{n-1}-4a_{n-2}+{n\choose 2}2^n+1, a_0 = a_1 = 1, n \ge 2$$

线性的递推项，和一个可能比较奇怪的尾项，运用我们之前所提到的技术，设$A(x)$为$<a_n>$的生成函数，则我们有：

$$\begin{align} a_n-4 a_{n-1}+4 a_{n-2}&=n(n-1)2^{n-1}+1 \\ \sum_{n=2}^{\infty} (a_n-4 a_{n-1}+4 a_{n-2}) x^n &= \sum_{n=2}^{\infty} n(n-1)2^{n-1} x^n + \sum_{n=2}^{\infty} x^n \end{align}$$

把边界加入进去，我们得到：

$$\sum_{n=0}^{\infty} a_n x^n - (a_0+a_1x ) - 4 x \left (\sum_{n=0}^{\infty} a_n x^n - a_0\right ) + 4 x^2 \sum_{n=0}^{\infty} a_n x^n$$ $$= (1-4 x+4 x^2)g(x) - (1+x) + 4 x$$

再来看看右边的情况：

$$\begin{align} \sum_{n=2}^{\infty} n(n-1)2^{n-1} x^n &= \frac{x^2}{2}\sum_{n=2}^{\infty} n(n-1)2^n x^{n-2} \\ &= \frac{x^2}{2} \frac{d^2}{dx^2} \frac{1}{1-2 x} \end{align}$$

且有

$$\sum_{n=2}^{\infty} x^n = \frac{1}{1-x}-(1+x)$$

因而我们得到：

$$(1-4 x+4 x^2)g(x) - (1+x) + 4 x = \frac{4 x^2}{(1-2 x)^3} + \frac{1}{1-x} - (1+x)$$ $$g(x) = \frac{1-10 x+44 x^2-84 x^3+80 x^4-32 x^5}{(1-x)(1-2 x)^3 (1-4 x+4 x^2)}$$

这结果简直让人菊花一紧。

2.1 到此为止？

细心一点的读者可能发现，我们可能可以使用在数音[之一]中提到的二项式定理来求解这个ex2.1，注意到

$$\sqrt{1-4z} = \sum_{k \ge 0}{1/2 \choose k}(-4z)^k =1+ \sum_{k \ge 1}{1 \over 2k}{-1/2 \choose k-1}(-4z)^k$$

从而有

$$\begin{align} {1-\sqrt{1-4z} \over 2z} &= \sum_{k \ge 1}{1 \over k}{-1/2 \choose k-1}(-4z)^{k-1} \\ &=\sum_{n \ge 0}{-1/2 \choose n}{(-4z)^n \over n+1} \\ &= \sum_{n \ge 0}{2n \choose n}{z^n \over n+1} \end{align}$$

因而得到

$$g_n = {2n \choose n}{1 \over n+1}$$

而快速排序所得到的式子看起来更麻烦一些，因为其中有对数，但事实上这真是它简单的地方，因为我们知道

$$-ln(1-z) = \sum_k {z^k \over k}$$

加以之前惯用的技术，我们有

$$\begin{align} C(z) &= {-2ln(1-z)-2x \over (1-z)^2} \\ & =\sum_{k \ge 2}\frac{2z^k}{k} \sum_{k \ge 0}(k+1)z^k \\ \end{align}$$

经过略显繁琐的代数运算与系数比对,我们能够得到

$$c_n = 2(n+1)\sum_{k=1}^n {1 \over k} -4n = 2(n+1)H_n -4n$$

这也揭示了快速排序的平均时间复杂度为$O(nlog_2 n)$.

3.一般策略

很多时候，将一个复杂的生成函数展开为幂级数形式是非常困难的，这让人感到沮丧。不过，通过上面的计算我们发现，我们能够经常得到一些形如$P(x)/Q(x)$，其中$P(x)$与$Q(x)$是两个多项式的生成函数。多项式经常是一种特殊的结构，那么在这里我们是否也有一些特殊的性质呢？

幸运的是，混凝土数学（《具体数学》 by Knuth）上，有一个如下叙述的定理：

---

若生成函数$R(z) = P(z)/Q(z)$，其中$Q(z) = q_0 (1-p_1z)^{d_1} \cdots (1-p_lz)^{d_l}$，${p_1,\cdots,p_l}$是不同的实数，且有$degree(P(z)) < d_1 + \cdots + d_l$，则有

$$[z^n]R(z) = f_1(n)p_1^n + \cdots +f_l(n)p_l^n\ for\ all\ n \ge 0$$

其中$f_k(n)$是首项系数$a_k$满足以下等式的$d_k-1$次多项式:

$$a_k = {P(1/p_k) \over (d_k-1)!q_0 \prod_{j \neq k}(1-p_j / p_k)^{d_j}}$$

---

但书中并没有给出证明，因此我试着证明了一下。

在初等的代数书中介绍了多项式的带余除法的概念，借助带余除法，我们知道上述有理函数$R(z)$可以分解成以下形式:

$$\begin{align} R(z) &= {P(x) \over {q_0 (1-p_1z)^{d_1} \cdots (1-p_lz)^{d_l}}} \\ &= {1 \over q_0}({A_1(z) \over (1-p_1z)^{d_1}}+\cdots+{A_l(z) \over (1-p_lz)^{d_l}}) \end{align}$$

其中$A_k(z)$是低于$d_k$次的多项式。我们将上式通分，即可得到：

$$\sum_j A_j(z) \prod_{k \neq j}(1-p_kz)^{d_k} = P(z)$$ $$\Rightarrow \sum_j A_j(1/p_j) \prod_{k \neq j}(1-p_k/p_j)^{d_k} = P(1/p_j)$$

由${1 \over 1-pz} = 1 + pz + \cdots + p^nz^n + \cdots$逐次微分，即可得到

$$\begin{align} \frac{(d_i-1)!}{(1-p_iz)^{d_i}} = (d_i-1)! + \cdots + (d_i+n-1)! p^n z^n + \cdots \\ \frac{1}{(1-p_i z)^{d_i}} = 1 + d_ipz + \cdots + \frac{d_i^{\overline n}}{n!} p^nz^n + \cdots \end{align}$$

因而将

$$R(z) = \frac{1}{q_0}(\frac{A_1(z)}{(1-p_1z)^{d_1}}+\cdots+\frac{A_l(z)}{(1-p_lz)^{d_l}})$$

逐项进行幂级数展开，则对于每一个展开式中的$z^n$项，其系数为

$$\frac{1}{q_0} A_k(z)\frac{d_k^{\overline n}}{n!}p_k^n$$

即

$$\frac{1}{q_0} \frac{1}{(d_k-1)!} A_k(z)\frac{(d_k+n-1)!}{n!}p_k^n$$

因而我们能够知道其系数$f_k(n)$是一个次数为$d_k-1$的关于n的多项式。则其首项系数(即 $n^{d_k-1}$的系数)$a_k$为

$$\frac{1}{q_0} \frac{1}{(d_k-1)!}A_k(z)$$

而由

$$\sum_j A_j(1/p_j) \prod_{k \neq j}(1-p_j/p_k)^{d_j} = P(1/p_j)$$

可以看出，对于每一个确定的$p_j$，含有$A_k\ k \neq j$项的连乘因子中必有取$z=p_j$的项， 使得乘积为0，因而有:

$$A_j(1/p_j) = \frac{P(1/p_j)}{\prod_{k \neq j}(1-p_j/p_k)^{d_j}}$$

最终在

$$\frac{1}{q_0} \frac{1}{(d_k-1)!}A_k(z)$$

取$z=1/p_k$，得到：

$$a_k =\frac{P(1/p_k)}{(d_k-1)!q_0 \prod_{j \neq k}(1-p_j / p_k)^{d_j}}$$

---

我们来简单演示一下这个定理的用法，譬如递推式

$$g_n=g_{n-1}+2g_{n-2}+(-1)^n[n\ge 0]+[n=1]$$

我们很容易就可求得其生成函数是

$$G(z) = {1+z+z \over (1-2z)(1+z)^2}$$

所以根据定理,我们知道对于某个常数$c$，有

$$g_n = a_1 2^n + (a_2 n+c)(-1)^n$$

其中

$$a_1 = {1+1/2+1/4 \over (1+1/2)^2} = 7/9, a_2 = {1-1+1 \over 1-2/(-1)} = 1/3$$

再将$n=0$的情形代入，即可得到通项公式为

$$g_n = {7 \over 9}2^n +({1 \over 3}n + {2 \over 9})(-1)^n$$

4.后记

生成函数是一项非常实用的工具，在这里我仅仅介绍了其冰山一角。更多的有关于生成函数的知识，只有等到我们遇到相关问题之时再做介绍了。

在这篇部分问题的解答过程中，我也曾走入歧途，一度执迷于创造新奇的方法而忽略了现有的工具，于定理证明上挣扎许久。实际上，如果你无法解出一个问题，那么要么是有一个更简单的问题你未能解决，要么是你仍有工具还未使用。