Bóna · 枚举与解析组合学导论 · 第 3 章 生成函数

3.2　热身：求解递推关系Warming up: Solving recurrence relations

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

我们从生成函数（generating function）的一个应用开始研究它们：用生成函数来求解递推关系（recurrence relation）。虽然许多递推关系不用生成函数也能解出来，但这将是一次很好的热身，为后面更精巧的技巧应用作准备。

本节目标学会一套固定的“流水线”做法：给定一个数列的递推关系（例如 \(a_n=3a_{n-1}-1\)），把整个数列打包成一个幂级数 \(A(x)=\sum a_nx^n\)，由递推关系解出 \(A(x)\) 的封闭表达式，再读出 \(x^n\) 的系数，从而得到 \(a_n\) 的显式公式——不必先算出 \(a_{n-1}\) 就能直接算出 \(a_n\)。

3.2.1　普通生成函数

五个戴红帽子的人开始散布一条谣言：如果你不戴上红帽子，你就会生病。每过一小时，他们每个人都把谣言告诉另外两个人，这些人立刻相信，戴上红帽子，并以同样的速度加入散布谣言的队伍。没有人会被告知两遍谣言；红帽子正是用来标记“已被告知”的。与此同时，每小时会有一个人不再相信谣言，摘下他的红帽子，并停止散布谣言。除此之外，没有别人会停止散布谣言。问 \(n\) 小时后有多少人戴着红帽子？

听到这个问题，自然的想法是先看看头几个小时里发生了什么。设 \(a_n\) 表示第 \(n\) 小时结束时戴红帽子的人数。那么我们知道 \(a_0=5\)，并且当 \(n\ge 1\) 时

\[\tag{3.5}a_n=3a_{n-1}-1.\]

这是因为：每个人在自己之外又带来两个追随者（于是原来的 \(a_{n-1}\) 人各自“变成 3 人份”，得 \(3a_{n-1}\)），而又有一个人摘掉了红帽子（故减去 \(1\)）。

一个戴帽人，一小时后变成 3 个戴帽人（本人 + 2 个新人） 己 己 新 新 全体 \(a_{n-1}\) 人 → \(3a_{n-1}\) 人，再扣掉摘帽的 1 人 → \(a_n=3a_{n-1}-1\)
每个旧成员一小时后“扩成三个”（自己加两个新人），故乘以 3；同时有 1 人退出，故减 1。

公式 (3.5) 足以逐个算出 \(a_1,a_2,\dots\) 的值。事实上，\(a_1=3a_0-1=14\)，\(a_2=3a_1-1=41\)。我们当然可以这样一直算下去，但很快就会变得乏味而冗长。而且这样做效率也不高：假设我们只想知道 \(a_{200}\) 是多少，那么用上面这种一步一步的方法，就得先算出 \(a_1,a_2,\dots,a_{199}\)，然后才能算 \(a_{200}\)。我们的目标是找到一个公式，能直接给出 \(a_n\) 的值，而不需要先知道 \(a_{n-1}\) 或数列 \(\{a_i\}_{i\ge 0}\) 的其他元素。（在本书余下的部分，我们用记号 \(\{a_i\}_{i\ge 0}\) 表示数列 \(a_0,a_1,\dots\)。）

先把头几项算清楚
  1. \(a_0=5\)（初始就有 5 个戴帽人）。
  2. \(a_1=3\times 5-1=15-1=14\)。
  3. \(a_2=3\times 14-1=42-1=41\)。
  4. \(a_3=3\times 41-1=123-1=122\)。
要算 \(a_{200}\) 就必须先把 \(a_1\) 到 \(a_{199}\) 全算一遍——这正是我们想要一个显式公式来避免的麻烦。

关键的想法是：我们可以用一个幂级数把数列 \(\{a_i\}_{i\ge 0}\) 的全部元素编码进去。这就引出了生成函数这一技巧，它是本章的核心主题，也是组合计数中一种极其有用的方法。

定义 3.3 设 \(f_0,f_1,\dots\) 是一个实数列。则形式幂级数（formal power series） \[F(x)=\sum_{n\ge 0}f_nx^n\] 称为数列 \(\{f_i\}_{i\ge 0}\) 的普通生成函数（ordinary generating function）。

下面这个例子只是把我们已经知道、且最近刚提到过的一个事实，换用生成函数的语言重新叙述一遍。

例 3.4 设对所有 \(n\ge 0\) 有 \(f_n=1\)。这个数列的普通生成函数是 \[F(x)=\sum_{n\ge 0}f_nx^n=\sum_{n\ge 0}x^n=\frac{1}{1-x}.\] 我们恳请读者花点时间证明上面的求和。（提示：把等式 \(\sum_{n\ge 0}x^n=\dfrac{1}{1-x}\) 两边同乘以 \(1-x\)，看看左边消去了什么。）
动手验证提示 把 \((1-x)\) 乘进部分和 \(1+x+x^2+\dots+x^N\)： \[(1-x)(1+x+x^2+\dots+x^N)=1-x^{N+1},\] 中间各项两两抵消，只剩首尾。除以 \(1-x\) 得 \(1+x+\dots+x^N=\dfrac{1-x^{N+1}}{1-x}\)，在形式幂级数意义下令项数无限增多，即得 \(\sum_{n\ge 0}x^n=\dfrac{1}{1-x}\)。
例 3.5 设 \(f_n=n\)。则 \[F(x)=\sum_{n\ge 0}f_nx^n=x\sum_{n\ge 1}nx^{n-1}=x\left(\frac{1}{1-x}\right)'=\frac{x}{(1-x)^2}.\]
这里用到了什么
  1. 因为 \(f_0=0\)，求和可以从 \(n\ge 1\) 开始，\(\sum_{n\ge 1}nx^n\)。
  2. 提出一个 \(x\)：\(\sum_{n\ge 1}nx^n=x\sum_{n\ge 1}nx^{n-1}\)。
  3. 注意 \(nx^{n-1}=(x^n)'\)，所以 \(\sum_{n\ge 1}nx^{n-1}=\left(\sum_{n\ge 0}x^n\right)'=\left(\dfrac{1}{1-x}\right)'=\dfrac{1}{(1-x)^2}\)。
  4. 乘回那个 \(x\)，得 \(F(x)=\dfrac{x}{(1-x)^2}\)。♦
（这正是上一节公式 (3.4) \(\sum_{n\ge 0}(n+1)x^n=\dfrac{1}{(1-x)^2}\) 移项后的样子。）

在上面这两个例子中，我们都是由显式公式给出数列，然后用这个公式算出生成函数。然而往往——正如我们关于红帽与谣言的贯穿例子那样——我们要做的是反过来：在已知一个数列的生成函数时，求出该数列的显式公式。在正式进攻散布谣言的问题之前，先看一个这种“反向计算”的例子。

例 3.6 已知 \[F(x)=\sum_{n\ge 0}f_nx^n=\frac{x}{1-3x},\] 求 \(f_n\) 的显式公式。
解：关键的观察是，\(f_n\) 不是别的，正是 \(F(x)\) 中 \(x^n\) 的系数。于是我们要找这个系数的公式，等价地，要找 \(\dfrac{1}{1-3x}\) 中 \(x^{n-1}\) 的系数。然而，把例 3.4 里的 \(x\) 换成 \(3x\)，就有 \[\frac{1}{1-3x}=\sum_{n\ge 0}(3x)^n=\sum_{n\ge 0}3^n\cdot x^n.\] 因此我们要找的系数是 \(f_n=3^{n-1}\)。♦

本章里我们的技巧会非常频繁地要求某个形式幂级数 \(A(x)\) 中 \(x^n\) 的系数。为此，我们引入记号 \([x^n]A(x)\) 来表示这个系数。于是上一例的结果用此记号可写成 \([x^n]F(x)=3^{n-1}\)。

记号 \([x^n]\)“\([x^n]A(x)\)”读作“\(A(x)\) 中 \(x^n\) 的系数”。例如 \([x^2](1+5x+7x^2+\dots)=7\)。求数列的显式公式，就归结为求 \([x^n]\) 应用到生成函数上的结果。

用生成函数解红帽递推

在我们的贯穿例子里，我们要找数 \(a_n\) 的显式公式。为此，先要算出它们的普通生成函数 \(A(x)=\sum_{n\ge 0}a_nx^n\)。为了能做到这一点，我们需要一个 \(A(x)\) 满足的恒等式。可以这样得到这样的恒等式：取数列的定义递推关系，即方程 \(a_n=3a_{n-1}-1\)，两边同乘以 \(x^n\)，然后对所有使该定义方程成立的 \(n\) 求和；在我们这里就是对 \(n\ge 1\) 求和。于是得到

\[\sum_{n\ge 1}a_nx^n=3\sum_{n\ge 1}a_{n-1}x^n-\sum_{n\ge 1}x^n.\]

现在注意，左边几乎正好就是 \(A(x)\)，只是缺了 \(a_0\) 这一项。也就是说，左边是 \(A(x)-a_0=A(x)-5\)。类似地，注意右边第一项不是别的，正是 \(3xA(x)\)，而右边第二项正是 \(\dfrac{x}{1-x}\)（再想一下例 3.4）。因此上面这个恒等式就给出

\[A(x)-5=3xA(x)-\frac{x}{1-x},\] \[A(x)(1-3x)=5-\frac{x}{1-x},\]

或者，解出 \(A(x)\)：

\[\tag{3.6}A(x)=\frac{5}{1-3x}-\frac{x}{(1-x)(1-3x)}.\]
逐项核对“平移”技巧
  1. 左边 \(\sum_{n\ge 1}a_nx^n\)：与 \(A(x)=\sum_{n\ge 0}a_nx^n\) 只差 \(n=0\) 那一项 \(a_0x^0=5\)，故等于 \(A(x)-5\)。
  2. 右边第一项 \(3\sum_{n\ge 1}a_{n-1}x^n\)：把下标整体往回挪，令 \(m=n-1\)，得 \(3\sum_{m\ge 0}a_mx^{m+1}=3x\sum_{m\ge 0}a_mx^m=3xA(x)\)。乘上 \(x\) 正对应“指标加一”的移位。
  3. 右边第二项 \(\sum_{n\ge 1}x^n=\dfrac{x}{1-x}\)（即 \(\sum_{n\ge 0}x^n-1=\dfrac{1}{1-x}-1\)）。
  4. 把三块拼起来，整个递推变成只含一个未知量 \(A(x)\) 的方程，解之即得 (3.6)。

正如在例 3.6 中那样，我们现在可以通过求 \([x^n]A(x)\) 的显式公式来求 \(a_n\) 的显式公式。根据 (3.6)，这个系数等于 \(\dfrac{5}{1-3x}\) 中 \(x^n\) 的系数减去 \(\dfrac{x}{(1-x)(1-3x)}\) 中 \(x^n\) 的系数，所以我们需要算这两个系数。前者很容易算，因为

\[\frac{5}{1-3x}=5\cdot\frac{1}{1-3x}=5\cdot\sum_{n\ge 0}3^nx^n,\]

所以这个幂级数中 \(x^n\) 的系数是 \(5\cdot 3^n\)。

算 (3.6) 右边第二项中 \(x^n\) 的系数，即 \(\dfrac{x}{(1-x)(1-3x)}\) 中的系数，要稍微难一点。

有好几种办法可以绕过这个困难。也许最快的是把 \(\dfrac{x}{(1-x)(1-3x)}\) 分解成部分分式（partial fractions）之和。也就是说，我们可以寻找实数 \(P\) 和 \(Q\)，使得

\[\frac{x}{(1-x)(1-3x)}=\frac{P}{1-x}+\frac{Q}{1-3x}.\]

两边同乘以 \((1-x)(1-3x)\)，得到

\[x=P+Q-x(3P+Q).\]

所以必须有 \(P+Q=0\) 且 \(3P+Q=-1\)，由此得 \(P=-1/2\) 与 \(Q=1/2\)。因此我们有

\[\frac{x}{(1-x)(1-3x)}=\frac{1}{2}\cdot\frac{1}{1-3x}-\frac{1}{2}\cdot\frac{1}{1-x}=\frac12\sum_{n\ge 0}3^nx^n-\frac12\sum_{n\ge 0}x^n=\sum_{n\ge 0}\frac{3^n-1}{2}x^n.\]

这个幂级数中 \(x^n\) 的系数是 \(\dfrac{3^n-1}{2}\)，这正是 \(\dfrac{x}{(1-x)(1-3x)}\) 中 \(x^n\) 的系数。因此，

\[\tag{3.7}[x^n]A(x)=a_n=5\cdot 3^n-\frac{3^n-1}{2}.\]

这就是 \(n\) 小时后戴红帽子的人数。

部分分式怎么定 \(P,Q\)
  1. 设 \(\dfrac{x}{(1-x)(1-3x)}=\dfrac{P}{1-x}+\dfrac{Q}{1-3x}\)，通分后分子相等：\(x=P(1-3x)+Q(1-x)\)。
  2. 整理成 \(x\) 的多项式：\(x=(P+Q)-(3P+Q)x\)。
  3. 左边 \(x\) 的常数项是 \(0\)、一次项系数是 \(1\)，逐项比较：\(P+Q=0\)，\(3P+Q=-1\)。
  4. 两式相减：\(2P=-1\Rightarrow P=-\tfrac12\)，再得 \(Q=\tfrac12\)。
  5. 每个 \(\dfrac{1}{1-cx}\) 都按例 3.4 展开成 \(\sum c^nx^n\)，读出 \(x^n\) 系数 \(\dfrac{3^n-1}{2}\)。
用公式 (3.7) 回代验证
  1. \(n=0\)：\(5\cdot 1-\dfrac{1-1}{2}=5-0=5=a_0\)。✓
  2. \(n=1\)：\(5\cdot 3-\dfrac{3-1}{2}=15-1=14=a_1\)。✓
  3. \(n=2\)：\(5\cdot 9-\dfrac{9-1}{2}=45-4=41=a_2\)。✓
现在算 \(a_{200}=5\cdot 3^{200}-\dfrac{3^{200}-1}{2}\) 可以一步到位，不必再逐项往上爬。

我们还可以利用如下事实：

\[[x^n]\frac{x}{(1-x)(1-3x)}=[x^{n-1}]\frac{1}{(1-x)(1-3x)},\]

然后再把后者分解成部分分式之和。

我们就这样成功找到了 \(a_n\) 的显式公式。我们请读者验证这个公式确实正确：先用这个公式算出 \(a_n\) 的头几个值，发现得到 \(5,14,41\)（正如应当的那样），再用一个更一般的论证说明我们的公式对所有 \(n\) 都正确。参见习题 2。

为什么生成函数的想法起了作用？定义方程 (3.5) 的缺点在于它含有两个未知量 \(a_n\) 和 \(a_{n-1}\)。然而生成函数 \(A(x)\) 把 \(a_n\) 的所有值都囊括进去了，所以当我们把 (3.5) 翻译成一个含 \(A(x)\) 的方程（即 (3.6)）时，那个方程里唯一的未知量就是 \(A(x)\)。因此我们能从那个方程得到 \(A(x)\) 的显式表达式。一旦知道了 \(A(x)\)，确定 \(a_n\) 就只是计算问题了。

流水线（请记住这五步）
  1. 写出递推关系，并标明它在哪些 \(n\) 上成立。
  2. 两边乘 \(x^n\)，对这些 \(n\) 求和。
  3. 把每个求和凑成 \(A(x)\) 的形式（指标移位对应乘 \(x\) 的幂，缺项要补正）。
  4. 解出 \(A(x)\) 的封闭式，必要时做部分分式分解。
  5. 对每个 \(\dfrac{1}{1-cx}=\sum c^nx^n\) 读系数，得 \(a_n=[x^n]A(x)\)。

让我们再看一个例子来练习这个方法。

例 3.7 五个戴红帽子的人开始散布一条谣言。在第一个小时里，他们每个人把谣言告诉一个此前没戴红帽子的人。这些新皈依者将戴上红帽子并加入散布谣言的队伍。然后同样的趋势继续下去，遵循这样的规则：每个人在加入后的第一个小时里把谣言告诉一个别人，而在此后每个小时里把谣言告诉九个别人。没有人会摘下红帽子。问 \(n\) 小时后有多少人戴红帽子？

设 \(b_n\) 为 \(n\) 小时后戴红帽子的人数。那么 \(b_0=5\)，\(b_1=10\)。同前一样，我们先找数 \(b_n\) 满足的递推规则。关于 \(b_n\) 我们知道什么？第一，在第 \(n\) 个小时里，由 \(b_{n-1}\) 计数的每个人都把故事告诉一个别人，产生 \(2b_{n-1}\) 个戴红帽子的人。第二，在第 \(n\) 个小时里，那些同时也被 \(b_{n-2}\) 计数的人（即那些不是新皈依者的人），每人又多告诉八个人（在已经算进去的之外），产生额外的 \(8b_{n-2}\) 个戴红帽子的人。这就导致恒等式

\[\tag{3.8}b_n=2b_{n-1}+8b_{n-2},\]

对所有 \(n\ge 2\) 成立。

拆开 (3.8) 的两块
  1. 第 \(n\) 小时的“在场者”就是上一小时的 \(b_{n-1}\) 人；他们每人各发展 1 个新人，于是连本带新 \(=2b_{n-1}\)。
  2. 其中“老资格”的人（即两小时前就在场、被 \(b_{n-2}\) 计数的人），每人在已发展的之外再发展 8 个，于是再加 \(8b_{n-2}\)。
  3. 两块相加：\(b_n=2b_{n-1}+8b_{n-2}\)。验证：\(b_2=2\cdot 10+8\cdot 5=20+40=60\)。

下一步是定义普通生成函数 \(B(x)=\sum_{n\ge 0}b_nx^n\)，并把 (3.8) 翻译成一个含 \(B(x)\) 的方程。为此，把 (3.8) 两边乘以 \(x^n\)，对所有使 (3.8) 成立的 \(n\)（即 \(n\ge 2\)）求和。得到

\[\sum_{n\ge 2}b_nx^n=2\sum_{n\ge 2}b_{n-1}x^n+8\sum_{n\ge 2}b_{n-2}x^n=2x\sum_{n\ge 2}b_{n-1}x^{n-1}+8x^2\sum_{n\ge 2}b_{n-2}x^{n-2}.\]

现在该在最后这个方程的两边寻找接近 \(B(x)\) 的表达式了。我们发现，最后这个方程等价于

\[B(x)-5-10x=2x(B(x)-5)+8x^2B(x),\] \[B(x)(1-2x-8x^2)=5,\] \[B(x)=\frac{5}{1-2x-8x^2}.\]
那些“缺项”从哪来
  1. 左边 \(\sum_{n\ge 2}b_nx^n=B(x)-b_0-b_1x=B(x)-5-10x\)（因 \(b_0=5,\,b_1=10\)）。〔注：原书此处印作 \(B(x)-15x-5\)，其中 \(15x\) 为笔误，正确应为 \(10x\)；否则无法导出下一行的 \(B(x)(1-2x-8x^2)=5\)。〕
  2. \(2x\sum_{n\ge 2}b_{n-1}x^{n-1}=2x\big(B(x)-b_0\big)=2x(B(x)-5)\)（求和从 \(b_1\) 起，缺 \(b_0\)）。
  3. \(8x^2\sum_{n\ge 2}b_{n-2}x^{n-2}=8x^2\,B(x)\)（这一块从 \(b_0\) 起，正好是完整的 \(B(x)\)）。
  4. 把含 \(B(x)\) 的项归到一边：\(B(x)(1-2x-8x^2)=5\)，于是 \(B(x)=\dfrac{5}{1-2x-8x^2}\)。

为了求出 \(B(x)\) 的幂级数形式，我们使用微积分里学过、并在前一例中勾勒过的部分分式技巧。如果你对这一技巧记得很有把握，可以跳过下面这一段。

我们处在一个幸运的情形：分母可以很好地分解，即 \(1-2x-8x^2=(1+2x)(1-4x)\)。因此我们有

\[\frac{5}{1-2x-8x^2}=\frac{C}{1+2x}+\frac{D}{1-4x},\] \[5=C(1-4x)+D(1+2x),\] \[5=x(2D-4C)+C+D.\]

（常数）多项式 \(5\) 要等于多项式 \(x(2D-4C)+C+D\)，唯一的办法是后者中 \(x\) 的系数为 \(0\)、常数项为 \(5\)。这导致 \(D=10/3\) 与 \(C=5/3\)。因此我们得到

\[B(x)=\frac{5}{1-2x-8x^2}=\frac{5}{3}\cdot\frac{1}{1+2x}+\frac{10}{3}\cdot\frac{1}{1-4x}.\]

利用 (3.4)（或例 3.4 的换元），这导致

\[\tag{3.9}\begin{aligned}B(x)&=\frac{5}{3}\sum_{n\ge 0}(-2x)^n+\frac{10}{3}\sum_{n\ge 0}(4x)^n\\&=\frac{5}{3}\sum_{n\ge 0}(-1)^n\cdot 2^nx^n+\frac{10}{3}\sum_{n\ge 0}4^nx^n\\&=\sum_{n\ge 0}\left(\frac{5}{3}(-1)^n\cdot 2^n+\frac{10}{3}4^n\right)x^n.\end{aligned}\]

最后，我们得到 \(b_n=[x^n]B(x)\)，即

\[\tag{3.10}b_n=\frac{5}{3}(-1)^n\cdot 2^n+\frac{10}{3}4^n.\]

可以再次验证这个公式对所有 \(n\ge 0\) 都正确。请读者在补充习题 2 中完成验证。

\(1-2x-8x^2\) = \(1+2x\) · \(1-4x\) 分母分解后，每个一次因式各对应一项 \(\frac{1}{1-cx}=\sum c^nx^n\)，于是 \(b_n\) 是 \((-2)^n\) 与 \(4^n\) 的线性组合
把二次分母分解成两个一次因式，是部分分式法能读出系数的关键；两根 \(-2\) 与 \(4\) 直接出现在通项 \(b_n\) 里。

上面两个递推关系，即 (3.5) 和 (3.8)，之所以相当容易求解，是因为当我们把它们乘以 \(x^n\) 并对所有使方程成立的 \(n\) 求和后，得到的表达式中很容易认出相关数列的生成函数：它要么只是被乘上一个常数，要么被乘上 \(x\) 的某个幂。但有时候，我们在最后一步要费些功夫才能找出生成函数。下面的例子说明了这一点。

例 3.8 设 \(a_0=1\)，并假设对所有整数 \(n\ge 1\) 有 \[\tag{3.11}\binom{n+2}{2}=\sum_{i=0}^{n}a_ia_{n-i}.\] 求 \(a_n\) 的显式公式。

这个递推关系有点不寻常，因为 \(a_n\) 依赖于之前所有的值 \(a_i\)，而不只是少数几个。我们可以直接算出 \(a_1=3/2\) 与 \(a_2=15/8\)。

直接算头两项
  1. \(n=1\)：左边 \(\binom{3}{2}=3\)；右边 \(\sum_{i=0}^{1}a_ia_{1-i}=a_0a_1+a_1a_0=2a_0a_1=2a_1\)。由 \(2a_1=3\) 得 \(a_1=3/2\)。
  2. \(n=2\)：左边 \(\binom{4}{2}=6\)；右边 \(a_0a_2+a_1a_1+a_2a_0=2a_2+a_1^2=2a_2+\tfrac94\)。由 \(2a_2+\tfrac94=6\) 得 \(a_2=\tfrac{15}{8}\)。
注意右边 \(\sum_{i=0}^{n}a_ia_{n-i}\) 正是两个生成函数相乘时 \(x^n\) 的系数（卷积，即上一节公式 (3.3)）。

解：注意 (3.11) 当 \(n=0\) 时也成立（此时左边 \(\binom{2}{2}=1\)，右边 \(a_0a_0=1\)）。现在把 (3.11) 两边乘以 \(x^n\)，对所有 \(n\ge 0\)（即所有使等式成立的 \(n\)）求和。得到

\[\sum_{n\ge 0}\binom{n+2}{2}x^n=\sum_{n\ge 0}\sum_{i=0}^{n}a_ia_{n-i}\,x^n.\]

现在该在两边寻找生成函数 \(A(x)=\sum_{n\ge 0}a_nx^n\) 了。然而，我们要比之前更有办法一点。注意左边恰好是 \((1-x)^{-3}\)（细节见习题 1）。至于右边，注意它恰好是 \(A(x)^2\)。事实上，把公式 (3.3) 应用于 \(B(x)=A(x)\) 即可。因此，上面这个方程其实就是说

\[(1-x)^{-3}=A(x)^2,\qquad (1-x)^{-3/2}=A(x).\]
两边为什么是这两样东西
  1. 右边：两个幂级数 \(A(x)\cdot A(x)\) 相乘，\(x^n\) 的系数恰是 \(\sum_{i=0}^{n}a_ia_{n-i}\)（卷积公式 (3.3)）。所以右边整体 \(=A(x)^2\)。
  2. 左边：\(\binom{n+2}{2}\) 是 \((1-x)^{-3}\) 中 \(x^n\) 的系数（即广义二项式 \((1-x)^{-3}=\sum_{n}\binom{n+2}{2}x^n\)）。所以左边 \(=(1-x)^{-3}\)。
  3. 两边相等给出 \(A(x)^2=(1-x)^{-3}\)；取（系数为 \(a_0=1>0\) 的）那个开方分支，得 \(A(x)=(1-x)^{-3/2}\)。

为了计算 \(A(x)\) 的系数，我们需要算二项式系数 \(\dbinom{-3/2}{n}\)。我们得到

\[\binom{-3/2}{n}=\frac{\left(-\tfrac32\right)\left(-\tfrac52\right)\cdots\left(-\tfrac{2n+1}{2}\right)}{n!}=(-1)^n\,\frac{3\cdot 5\cdots(2n+1)}{2^n\cdot n!}.\]

于是，按广义二项式定理 \((1-x)^{-3/2}=\sum_{n\ge 0}\binom{-3/2}{n}(-x)^n=\sum_{n\ge 0}\binom{-3/2}{n}(-1)^nx^n\)，两个 \((-1)^n\) 相消，得到 \(a_n\) 的显式公式

\[a_n=[x^n]A(x)=\frac{3\cdot 5\cdots(2n+1)}{2^n\cdot n!}=\frac{(2n+1)!}{4^n\,(n!)^2}.\]
化简与验证
  1. 把分子 \(3\cdot 5\cdots(2n+1)\) 配上偶数因子：\(3\cdot5\cdots(2n+1)=\dfrac{(2n+1)!}{2\cdot4\cdots(2n)}=\dfrac{(2n+1)!}{2^n\,n!}\)。
  2. 代回得 \(a_n=\dfrac{(2n+1)!}{2^n n!\cdot 2^n n!}=\dfrac{(2n+1)!}{4^n(n!)^2}\)。
  3. \(n=0\)：\(\dfrac{1!}{1\cdot 1}=1=a_0\)。✓
  4. \(n=1\)：\(\dfrac{3!}{4\cdot 1}=\dfrac{6}{4}=\dfrac32=a_1\)。✓
  5. \(n=2\)：\(\dfrac{5!}{16\cdot 4}=\dfrac{120}{64}=\dfrac{15}{8}=a_2\)。✓ ♦
这里 \(a_n\) 依赖于全部历史项 \(a_0,\dots,a_n\)，但靠把右边的卷积识别成 \(A(x)^2\)，递推照样被一举解开。

返回 全书目录