算数・递推式与生成函数

July 14th, 2018

递推式（Recurrence）与生成函数（Generating Function）

前言

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

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

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

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

0.符号约定

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

我们以 $< a_{n} >$ 作为数列 $< a_{1}, a_{2}, \dots, a_{n}, \dots >$ 的缩写。

若 $c o n d i t i o n$ 为真，则我们有 $[c o n d i t i o n] = 1$ ，否则为 $0$ 。

没有明确说明的情况下， $G (z), F (z)$ 意为数列 $< g_{n} >, < f_{n} >$ 的生成函数。

1.定义与基本性质

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

\begin{matrix} (1) & G (z) = g_{0} + g_{1} z + g_{2} z^{2} + \dots = \sum_{n \geq 0}^{\infty} g_{n} z^{n} \end{matrix}

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

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

\begin{matrix} (2) & α F (z) + β G (z) = \sum_{n} (α f_{n} + β g_{n}) z^{n} \end{matrix}

\begin{matrix} (3) & z^{m} G (z) = \sum_{n} g_{n - m} z^{n} \end{matrix}

\begin{matrix} (4) & G (c z) = \sum_{n} c^{n} g_{n} z^{n} \end{matrix}

\begin{matrix} (5) & G^{'} (z) = \sum_{n} (n + 1) g_{n + 1} z^{n} \end{matrix}

\begin{matrix} (6) & \int_{0}^{z} G (t) d t = \sum_{n \geq 1} \frac{1}{n} g_{n - 1} z^{n} \end{matrix}

\begin{matrix} (7) & F (z) G (z) = \sum_{n} (\sum_{k} f_{k} g_{n - k}) z^{n} \end{matrix}

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

\begin{aligned} (8) & (1 + z + z^{2} + . . .) G (z) & = \sum_{n} (\sum_{k \leq n} g_{k}) z^{n} \\ (9) & \frac{1 - z^{n}}{1 - z} G (z) & = \sum_{n} (\sum_{k \leq n} g_{k}) z^{n} \\ (10) & \frac{1}{1 - z} G (z) & = \sum_{n} (\sum_{k \leq n} g_{k}) z^{n} \end{aligned}

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

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

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

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

\begin{matrix} (11) & \sum_{n \geq 1} \frac{1}{n} z^{n} = l n \frac{1}{1 - z} \end{matrix}

2.与递推式

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

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

ex.2.1 一个经典问题

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

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

\begin{matrix} (12) & g_{n} = g_{1} g_{n - 1} + g_{2} g_{n - 2} + \dots + g_{n - 1} g_{1} = \sum_{k = 1}^{n - 1} g_{k} g_{n - k}, n \geq 2, g_{1} = 1 \end{matrix}

由于递推式并没有 $g_{0}$ ，因而生成函数以 $g_{1}$ 作为第一项，即有

\begin{matrix} (13) & G (z) = g_{1} + g_{2} z + \dots = \sum_{k = 1}^{\infty} g_{k} z^{k - 1} \end{matrix}

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

\begin{aligned} (14) & G^{2} (z) & = g_{1} g_{1} + g_{1} g_{2} z + g_{2} g_{1} z + \dots + g_{n} g_{n} z^{2 (n - 1)} + \dots \\ (15) & G^{2} (z) & = \sum_{k = 1}^{1} g_{k} g_{2 - k} + \sum_{k = 1}^{2} g_{k} g_{3 - k} z + \dots + \sum_{k = 1}^{n - 1} g_{k} g_{n - k} z^{n - 2} + \dots \\ (16) & = \frac{1}{z} (g_{2} z + \dots g_{n} z^{n - 1} + \dots) \end{aligned}

这样我们很容易就能看出

\begin{matrix} (17) & G (z) = z G^{2} (z) + g_{1} = z G^{2} (z) + 1 \end{matrix}

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

\begin{matrix} (18) & G (z) = \frac{1 - \sqrt{1 - 4 z}}{2 z} \end{matrix}

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

\begin{matrix} (19) & lim_{x \to 0} \frac{1 - \sqrt{1 - 4 z}}{2 z} = 1 \end{matrix}

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

ex.2.2 源于快速排序

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

我们假设待排序数列为

\begin{matrix} (20) & a_{1}, \dots, a_{n} \end{matrix}

选定枢纽元之后，设比枢纽元小的元素数量为 $k$ ，由于数列完全随机，我们可以认为 $k$ 是从 $[1, n - 1]$ 中均匀采样的。因此，令 $n$ 个数进行快速排序总的比较次数 $c_{n}$ ，我们能够建立如下递推式

\begin{matrix} (21) & c_{n} = n - 1 + \frac{1}{n} \sum_{k = 1}^{n} (c_{k} + c_{n - k}) = n - 1 + \frac{2}{n} \sum_{k = 1}^{n} c_{k} \end{matrix}

其中第一项的 $n - 1$ 为与枢纽元进行比较的开销，而 $c_{k}$ 与 $c_{n - k}$ 分别代表分割之后的子问题所对应的答案。总的平均比较次数则为不同大小的子问题的平均比较数量。

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

\begin{aligned} (22) & C (z) & = c_{1} + \sum_{n = 2}^{\infty} (n - 1 + \frac{2}{n} \sum_{k = 1}^{n} c_{k}) z^{n - 1} \\ (23) & C^{'} (z) & = \sum_{n = 2}^{\infty} ((n - 1) n + 2 \sum_{k = 1}^{n} c_{k}) z^{n - 1} \\ (24) & = \sum_{n = 2}^{\infty} n (n - 1) z^{n - 1} + 2 \sum_{n = 2}^{\infty} \sum_{k = 1}^{n} c_{k} z^{n - 1} \\ (25) & = z (\frac{1}{1 - z})^{″} + \frac{2 C (z)}{1 - z} \\ (26) & = \frac{2 z}{(1 - z)^{3}} + \frac{2 C (z)}{1 - z} \end{aligned}

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

\begin{matrix} (27) & C (z) = \frac{- 2 l n (1 - z) - 2 x}{(1 - z)^{2}} \end{matrix}

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

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

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

\begin{matrix} (28) & a_{n} = 4 a_{n - 1} - 4 a_{n - 2} + (\binom{n}{2}) 2^{n} + 1, a_{0} = a_{1} = 1, n \geq 2 \end{matrix}

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

\begin{aligned} (29) & a_{n} - 4 a_{n - 1} + 4 a_{n - 2} & = n (n - 1) 2^{n - 1} + 1 \\ (30) & \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{aligned}

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

\begin{matrix} (31) & \sum_{n = 0}^{\infty} a_{n} x^{n} - (a_{0} + a_{1} x) - 4 x (\sum_{n = 0}^{\infty} a_{n} x^{n} - a_{0}) + 4 x^{2} \sum_{n = 0}^{\infty} a_{n} x^{n} \end{matrix}

\begin{matrix} (32) & = (1 - 4 x + 4 x^{2}) g (x) - (1 + x) + 4 x \end{matrix}

再来看看右边的情况

\begin{aligned} (33) & \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} \\ (34) & = \frac{x^{2}}{2} \frac{d^{2}}{d x^{2}} \frac{1}{1 - 2 x} \end{aligned}

且有

\begin{matrix} (35) & \sum_{n = 2}^{\infty} x^{n} = \frac{1}{1 - x} - (1 + x) \end{matrix}

因而我们得到

\begin{matrix} (36) & (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) \end{matrix}

\begin{matrix} (37) & 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})} \end{matrix}

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

2.1 到此为止？

细心一点的读者可能发现，我们可能可以使用在算数・二项式系数与组合恒等式中提到的二项式定理来求解这个ex2.1，注意到

\begin{matrix} (38) & \sqrt{1 - 4 z} = \sum_{k \geq 0} (\binom{1 / 2}{k}) (- 4 z)^{k} = 1 + \sum_{k \geq 1} \frac{1}{2 k} (\binom{- 1 / 2}{k - 1}) (- 4 z)^{k} \end{matrix}

从而有

\begin{aligned} (39) & \frac{1 - \sqrt{1 - 4 z}}{2 z} & = \sum_{k \geq 1} \frac{1}{k} (\binom{- 1 / 2}{k - 1}) (- 4 z)^{k - 1} \\ (40) & = \sum_{n \geq 0} (\binom{- 1 / 2}{n}) \frac{(- 4 z)^{n}}{n + 1} \\ (41) & = \sum_{n \geq 0} (\binom{2 n}{n}) \frac{z^{n}}{n + 1} \end{aligned}

因而得到

\begin{matrix} (42) & g_{n} = (\binom{2 n}{n}) \frac{1}{n + 1} \end{matrix}

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

\begin{matrix} (43) & - l n (1 - z) = \sum_{k} \frac{z^{k}}{k} \end{matrix}

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

\begin{aligned} (44) & C (z) & = \frac{- 2 l n (1 - z) - 2 x}{(1 - z)^{2}} \\ (45) & = \sum_{k \geq 2} \frac{2 z^{k}}{k} \sum_{k \geq 0} (k + 1) z^{k} \end{aligned}

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

\begin{matrix} (46) & c_{n} = 2 (n + 1) \sum_{k = 1}^{n} \frac{1}{k} - 4 n = 2 (n + 1) H_{n} - 4 n \end{matrix}

这也揭示了快速排序的平均时间复杂度为 $O (n l o g_{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_{1} z)^{d_{1}} \dots (1 - p_{l} z)^{d_{l}}$ ， ${p_{1}, \dots, p_{l}}$ 是不同的实数，且有 $d e g r e e (P (z)) < d_{1} + \dots + d_{l}$ ，则有

\begin{matrix} (47) & [z^{n}] R (z) = f_{1} (n) p_{1}^{n} + \dots + f_{l} (n) p_{l}^{n} \forall n \geq 0 \end{matrix}

其中 $f_{k} (n)$ 是首项系数 $a_{k}$ 满足以下等式的 $d_{k} - 1$ 次多项式

\begin{matrix} (48) & a_{k} = \frac{P (1 / p_{k})}{(d_{k} - 1)! q_{0} \prod_{j \neq k} (1 - p_{j} / p_{k})^{d_{j}}} \end{matrix}

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

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

\begin{aligned} (49) & R (z) & = \frac{P (x)}{q_{0} (1 - p_{1} z)^{d_{1}} \dots (1 - p_{l} z)^{d_{l}}} \\ (50) & = \frac{1}{q_{0}} (\frac{A_{1} (z)}{(1 - p_{1} z)^{d_{1}}} + \dots + \frac{A_{l} (z)}{(1 - p_{l} z)^{d_{l}}}) \end{aligned}

其中 $A_{k} (z)$ 是低于 $d_{k}$ 次的多项式。我们将上式通分，即可得到

\begin{matrix} (51) & \sum_{j} A_{j} (z) \prod_{k \neq j} (1 - p_{k} z)^{d_{k}} = P (z) \end{matrix}

\begin{matrix} (52) & \Rightarrow \sum_{j} A_{j} (1 / p_{j}) \prod_{k \neq j} (1 - p_{k} / p_{j})^{d_{k}} = P (1 / p_{j}) \end{matrix}

由 $\frac{1}{1 - p z} = 1 + p z + \dots + p^{n} z^{n} + \dots$ 逐次微分，即可得到

\begin{array}{r} (53) & \frac{(d_{i} - 1)!}{(1 - p_{i} z)^{d_{i}}} = (d_{i} - 1)! + \dots + (d_{i} + n - 1)! p^{n} z^{n} + \dots \\ (54) & \frac{1}{(1 - p_{i} z)^{d_{i}}} = 1 + d_{i} p z + \dots + \frac{d_{i}^{\overset{―}{n}}}{n!} p^{n} z^{n} + \dots \end{array}

因而将

\begin{matrix} (55) & R (z) = \frac{1}{q_{0}} (\frac{A_{1} (z)}{(1 - p_{1} z)^{d_{1}}} + \dots + \frac{A_{l} (z)}{(1 - p_{l} z)^{d_{l}}}) \end{matrix}

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

\begin{matrix} (56) & \frac{1}{q_{0}} A_{k} (z) \frac{d_{k}^{\overset{―}{n}}}{n!} p_{k}^{n} \end{matrix}

即

\begin{matrix} (57) & \frac{1}{q_{0}} \frac{1}{(d_{k} - 1)!} A_{k} (z) \frac{(d_{k} + n - 1)!}{n!} p_{k}^{n} \end{matrix}

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

\begin{matrix} (58) & \frac{1}{q_{0}} \frac{1}{(d_{k} - 1)!} A_{k} (z) \end{matrix}

而由

\begin{matrix} (59) & \sum_{j} A_{j} (1 / p_{j}) \prod_{k \neq j} (1 - p_{j} / p_{k})^{d_{j}} = P (1 / p_{j}) \end{matrix}

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

\begin{matrix} (60) & A_{j} (1 / p_{j}) = \frac{P (1 / p_{j})}{\prod_{k \neq j} (1 - p_{j} / p_{k})^{d_{j}}} \end{matrix}

最终在

\begin{matrix} (61) & \frac{1}{q_{0}} \frac{1}{(d_{k} - 1)!} A_{k} (z) \end{matrix}

取 $z = 1 / p_{k}$ ，得到

\begin{matrix} (62) & a_{k} = \frac{P (1 / p_{k})}{(d_{k} - 1)! q_{0} \prod_{j \neq k} (1 - p_{j} / p_{k})^{d_{j}}} \end{matrix}

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

\begin{matrix} (63) & g_{n} = g_{n - 1} + 2 g_{n - 2} + (- 1)^{n} [n \geq 0] + [n = 1] \end{matrix}

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

\begin{matrix} (64) & G (z) = \frac{1 + z + z}{(1 - 2 z) (1 + z)^{2}} \end{matrix}

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

\begin{matrix} (65) & g_{n} = a_{1} 2^{n} + (a_{2} n + c) (- 1)^{n} \end{matrix}

其中

\begin{matrix} (66) & a_{1} = \frac{1 + 1 / 2 + 1 / 4}{(1 + 1 / 2)^{2}} = 7 / 9, a_{2} = \frac{1 - 1 + 1}{1 - 2 / (- 1)} = 1 / 3 \end{matrix}

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

\begin{matrix} (67) & g_{n} = \frac{7}{9} 2^{n} + (\frac{1}{3} n + \frac{2}{9}) (- 1)^{n} \end{matrix}

4.后记

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

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

mathematics (9)