3.9　习题解答Solutions to exercises

本页为译文 + 高中讲解合一：黑色正文为原书解答的忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解——补全原书省略的步骤、用具体数字验证、必要时画图，全程不用比喻。

习题 1

用二项式定理（binomial theorem）展开左边 \((1-x)^{-k}\)，可见 \(x^n\) 的系数为 \((-1)^n\binom{-k}{n}\)。只要证明它等于 \(\binom{n+k-1}{k-1}\) 即可。我们有 \[ (-1)^n\binom{-k}{n}=(-1)^n\cdot\frac{(-k)(-k-1)\cdots(-k-n+1)}{n!} =(-1)^{2n}\cdot\frac{k(k+1)\cdots(n+k-1)}{n!}=\binom{n+k-1}{n}=\binom{n+k-1}{k-1}. \]

1. 把 \(n\) 个负号提出来：每个因子 \(-k-j=-(k+j)\)，共 \(n\) 个，提出 \((-1)^n\)： \[(-k)(-k-1)\cdots(-k-n+1)=(-1)^n\,k(k+1)\cdots(k+n-1).\]
2. 因此 \((-1)^n\binom{-k}{n}=(-1)^n\cdot(-1)^n\dfrac{k(k+1)\cdots(k+n-1)}{n!}=(-1)^{2n}(\cdots)\)。而 \((-1)^{2n}=1\)，负号全部消掉。
3. 剩下 \(\dfrac{k(k+1)\cdots(k+n-1)}{n!}\)，分子是从 \(k\) 起连乘 \(n\) 个正整数，恰好是 \(\binom{n+k-1}{n}\)。
4. 最后用对称性 \(\binom{m}{n}=\binom{m}{m-n}\)，这里 \(m=n+k-1\)，\(m-n=k-1\)，得 \(\binom{n+k-1}{n}=\binom{n+k-1}{k-1}\)。♦

习题 2

当 \(n=0\) 时公式正确，因为它给出 \(a_0=5\)。现在假设公式对 \(n\) 成立。回忆数列 \(\{a_n\}\) 由 \(a_{n+1}=3a_n-1\)（\(n\ge0\)）定义。于是公式 (3.7) 对 \(n\) 成立这一事实推出 \[ a_{n+1}=3\!\left(5\cdot3^n-\frac{3^n-1}{2}\right)-1=5\cdot3^{n+1}-\frac{3^{n+1}-1}{2}, \] 所以 (3.7) 对 \(n+1\) 也成立。因此由归纳法，(3.7) 对一切非负整数 \(n\) 成立。

1. 起点 \(n=0\)：\(a_0=5\cdot3^0-\dfrac{3^0-1}{2}=5-0=5\)，与初始值一致。
2. 归纳步：把 \(a_n=5\cdot3^n-\dfrac{3^n-1}{2}\) 代入 \(a_{n+1}=3a_n-1\)： \[a_{n+1}=3\cdot5\cdot3^n-3\cdot\frac{3^n-1}{2}-1=5\cdot3^{n+1}-\frac{3^{n+1}-3}{2}-1.\]
3. 把末尾的 \(-1\) 写成 \(-\dfrac{2}{2}\) 合并：\(-\dfrac{3^{n+1}-3}{2}-\dfrac{2}{2}=-\dfrac{3^{n+1}-1}{2}\)。
4. 于是 \(a_{n+1}=5\cdot3^{n+1}-\dfrac{3^{n+1}-1}{2}\)，正是把公式里的 \(n\) 换成 \(n+1\)。归纳完成。♦

习题 3

设 \(A(x)\) 为该数列的普通生成函数（ordinary generating function）。把递推式两边乘以 \(x^n\)，再对 \(n\ge1\) 求和，得到 \[A(x)-2=4xA(x)-\frac{3x}{1-x}.\] 由此 \[ A(x)=\frac{2}{1-4x}-\frac{3x}{(1-x)(1-4x)}=\frac{1}{1-4x}+\frac{1}{1-x} =\sum_{n\ge0}4^n x^n+\sum_{n\ge0}x^n. \] 因此 \(A(x)\) 中 \(x^n\) 的系数为 \(a_n=4^n+1\)。

1. 记 \(A(x)=\sum_{n\ge0}a_nx^n\)。对 \(a_n=4a_{n-1}-3\) 两边乘 \(x^n\) 后对 \(n\ge1\) 求和： \[\sum_{n\ge1}a_nx^n=4\sum_{n\ge1}a_{n-1}x^n-3\sum_{n\ge1}x^n.\]
2. 左边 \(=A(x)-a_0=A(x)-2\)；右边第一项 \(=4x\sum_{n\ge1}a_{n-1}x^{n-1}=4xA(x)\)；第二项 \(=-3\cdot\dfrac{x}{1-x}\)。得到上面的方程。
3. 解 \(A(x)\)：把含 \(A(x)\) 的项移到一起，\(A(x)(1-4x)=2-\dfrac{3x}{1-x}\)，故 \(A(x)=\dfrac{2}{1-4x}-\dfrac{3x}{(1-x)(1-4x)}\)。
4. 部分分式（partial fractions）分解 \(\dfrac{3x}{(1-x)(1-4x)}=\dfrac{A}{1-x}+\dfrac{B}{1-4x}\)，即 \(3x=A(1-4x)+B(1-x)\)。代 \(x=1\)：\(3=-3A\Rightarrow A=-1\)；代 \(x=\tfrac14\)：\(\tfrac34=\tfrac34B\Rightarrow B=1\)。于是 \(\dfrac{3x}{(1-x)(1-4x)}=\dfrac{-1}{1-x}+\dfrac{1}{1-4x}\)。
5. 代回：\(A(x)=\dfrac{2}{1-4x}-\dfrac{1}{1-4x}+\dfrac{1}{1-x}=\dfrac{1}{1-4x}+\dfrac{1}{1-x}\)。
6. 用 \(\dfrac{1}{1-4x}=\sum4^nx^n\) 与 \(\dfrac{1}{1-x}=\sum x^n\)，读系数：\(a_n=4^n+1\)。♦

习题 4

像例 3.7 那样开始。若 \(A(x)\) 是数列的普通生成函数，则通常的步骤把我们引向函数方程 \[A(x)-x=4xA(x)-4x^2A(x).\tag{3.35}\] 于是 \[ A(x)=\frac{x}{1-4x+4x^2}=\frac{x}{(1-2x)^2} =x\sum_{n\ge0}\binom{-2}{n}(-2x)^n=x\sum_{n\ge0}(n+1)2^n x^n =\sum_{n\ge1}n\cdot2^{n-1}x^n. \] 因此 \(a_n=n\cdot2^{n-1}\)。

1. 得到方程 (3.35) 后解出 \(A(x)=\dfrac{x}{1-4x+4x^2}\)；注意 \(1-4x+4x^2=(1-2x)^2\)。
2. 用广义二项式展开 \(\dfrac{1}{(1-2x)^2}=(1-2x)^{-2}=\sum_{n\ge0}\binom{-2}{n}(-2x)^n\)。由习题 1 同类的算法，\(\binom{-2}{n}(-1)^n=\binom{n+1}{n}=n+1\)，故 \((1-2x)^{-2}=\sum_{n\ge0}(n+1)2^nx^n\)。
3. 乘上前面的 \(x\)：\(A(x)=x\sum_{n\ge0}(n+1)2^nx^n=\sum_{n\ge0}(n+1)2^nx^{n+1}\)。
4. 令 \(m=n+1\) 换元：系数变成 \(a_m=m\cdot2^{m-1}\)（\(m\ge1\)）。♦

习题 5

像例 3.7 和上一题那样进行，得到方程 \[A(x)-x=4xA(x)-5x^2A(x),\] 它形式上像 (3.35)，实际却很不一样。解出 \[A(x)=\frac{x}{1-4x+5x^2}.\] 这一次右边的部分分式分解略难，因为分母有复根 \(0.4\pm0.2i\)。设 \(\alpha=0.4+0.2i,\ \beta=0.4-0.2i\)。约去 5 后寻找 \(C,D\) 使 \[\frac{C}{x-\alpha}+\frac{D}{x-\beta}=\frac{0.2x}{0.2(1-4x+5x^2)},\qquad C(x-\beta)+D(x-\alpha)=0.2x.\] 这给出 \(C+D=0.2,\ C\beta+D\alpha=0\)，解得 \(C=0.1-0.2i,\ D=0.1+0.2i\)。于是逐步化简后得 \[a_n=\frac{i}{2}\!\left((2-i)^n-(2+i)^n\right),\] 其中用到 \(1/\beta=2+i,\ 1/\alpha=2-i\)。若对 \((2-i)^n,(2+i)^n\) 用二项式定理再作差，则 \(i\) 的偶次幂的项相互抵消，因此 \[a_n=n\cdot2^{n-1}-\binom{n}{3}2^{n-3}+\binom{n}{5}2^{n-5}-\cdots.\]

1. 分母 \(1-4x+5x^2\) 的零点由 \(5x^2-4x+1=0\) 给出：\(x=\dfrac{4\pm\sqrt{16-20}}{10}=\dfrac{4\pm2i}{10}=0.4\pm0.2i\)。这就是 \(\alpha,\beta\)。
2. 把 \(A(x)\) 拆成两项 \(\dfrac{C}{x-\alpha}+\dfrac{D}{x-\beta}\)，求出 \(C,D\) 后，每一项展开成几何级数。关键化简：因 \(|\alpha|^2=0.4^2+0.2^2=0.2\)，故 \(1/\alpha=\bar\alpha/|\alpha|^2=(0.4-0.2i)/0.2=2-i\)，同理 \(1/\beta=2+i\)。
3. 合并后得到紧凑形式 \(a_n=\dfrac{i}{2}\big((2-i)^n-(2+i)^n\big)\)。
4. 化成实数：对 \((2\mp i)^n=\sum_j\binom nj 2^{n-j}(\mp i)^j\) 作差。偶数 \(j\) 处 \((-i)^j=i^j\) 抵消；奇数 \(j\) 处 \((-i)^j-i^j=-2i^j\)。代入并用 \(i^{j+1}=(-1)^{(j+1)/2}\)（\(j\) 奇时 \(j+1\) 偶），逐项算出 \(j=1\) 给 \(+n2^{n-1}\)，\(j=3\) 给 \(-\binom n3 2^{n-3}\)，\(j=5\) 给 \(+\binom n5 2^{n-5}\)，正负交替。♦

习题 6

(a) 满足递推关系 (3.34) 的数列构成一个向量空间（vector space）：若 \(\{a_n\}\) 与 \(\{b_n\}\) 都满足 (3.34)，则它们的和 \(\{a_n+b_n\}\) 也满足；同样，若 \(\{a_n\}\) 满足 (3.34)，则任意常数倍 \(\{ca_n\}\)（\(c\in\mathbb R\)）也满足。

(b) 这个向量空间的维数是 2。设 \(\{a_n\}\in V\) 由 \(a_0=1,a_1=0\) 决定，\(\{b_n\}\in V\) 由 \(b_0=0,b_1=1\) 决定——这两个初值唯一确定整条数列。则 \(\{a_n\}\) 与 \(\{b_n\}\) 线性无关。而 \(V\) 中任一数列都可写成它们的线性组合：若 \(\{c_n\}\in V\) 有初值 \(c_0,c_1\)，则 \(\{c_n\}=c_0\{a_n\}+c_1\{b_n\}\)。

1. (a) 加法封闭：设 \(a_n=pa_{n-1}+qa_{n-2}\) 且 \(b_n=pb_{n-1}+qb_{n-2}\)，两式相加：\((a_n+b_n)=p(a_{n-1}+b_{n-1})+q(a_{n-2}+b_{n-2})\)，故和列也满足。数乘类似。
2. (b) 维数恰为 2：一条数列被 \(a_0,a_1\) 这两个数完全锁死（后面每项都由递推算出）。所以"自由度"是 2。
3. 取标准基 \(\{a_n\}:a_0=1,a_1=0\) 与 \(\{b_n\}:b_0=0,b_1=1\)。任意 \(\{c_n\}\) 的前两项是 \(c_0,c_1\)，而 \(c_0\{a_n\}+c_1\{b_n\}\) 的前两项也是 \(c_0,c_1\)；前两项相同 \(\Rightarrow\) 整条相同。故两者构成基，维数 \(=2\)。♦

习题 7

假设 \(a_n=a^n\)。则 (3.34) 变为 \(a^n=p\,a^{n-1}+q\,a^{n-2}\)。排除无意义的 \(a=0\)，这等价于 \[a^2-pa-q=0.\tag{3.36}\] 也就是说，\(a_n=a^n\) 是 (3.34) 的解当且仅当 \(a\) 是 (3.36) 的解。

1. 把试探解 \(a_n=a^n\) 代入 \(a_n=pa_{n-1}+qa_{n-2}\)：\(a^n=pa^{n-1}+qa^{n-2}\)。
2. 因 \(a\ne0\)，两边同除以 \(a^{n-2}\)：\(a^2=pa+q\)，即 \(a^2-pa-q=0\)，这就是特征方程（characteristic equation）(3.36)。♦

习题 8

上一题已知必须找 (3.36) 的解。若它有两个不同的解（实或复）\(a_1,a_2\)，则 \(\{a_1^n\}\) 与 \(\{a_2^n\}\) 是 \(V\) 中两个线性无关的元素。由习题 6 知 \(\dim V=2\)，故 \(\{a_1^n\},\{a_2^n\}\) 构成 \(V\) 的一组基。

若 (3.36) 有重实根 \(a\)，则已知 \(\{a^n\}\) 是解。为找第二个线性无关的解，注意 \(a\) 是重根意味着 \[a^2-pa-q=(a-p/2)^2=0,\] 所以 \(a=p/2,\ q=-p^2/4\)。这时一个常规的计算表明 \(\{n a^n\}\) 也是解，且它与 \(\{a^n\}\) 线性无关。

读者也许会问这怎么"猜"得到。其实读者多半上过微分方程课——当常系数二阶方程的特征方程有重实根时，用的正是同一个想法。

1. 两个不同根：\(\{a_1^n\},\{a_2^n\}\) 线性无关（因为 \(a_1\ne a_2\)），又都在二维空间 \(V\) 里，所以自动是基；通解 \(a_n=C_1a_1^n+C_2a_2^n\)。
2. 重根 \(a=p/2\)：验证 \(\{na^n\}\) 是解。代入右边 \(p\,(n-1)a^{n-1}+q\,(n-2)a^{n-2}\)，用 \(p=2a,\ q=-a^2\)： \[2a(n-1)a^{n-1}-a^2(n-2)a^{n-2}=\big(2(n-1)-(n-2)\big)a^n=n\,a^n,\] 正好等于左边 \(na^n\)。所以 \(\{na^n\}\) 确是解。
3. \(\{a^n\}\) 与 \(\{na^n\}\) 线性无关（一个不是另一个的常数倍），故通解 \(a_n=(C_1+C_2n)a^n\)。♦

习题 9

设 \(A(x)\) 为所求数列的生成函数。把定义式两边乘 \(x^n\)，对 \(n\ge1\) 求和： \[A(x)-1=3\sum_{n\ge1}\Big(\sum_{i=0}^{n-1}a_i\Big)x^n,\qquad A(x)-1=\frac{3xA(x)}{1-x}.\] 最后一步用了"\(\sum_{i=0}^{n-1}a_i\) 是 \(A(x)/(1-x)\) 中 \(x^{n-1}\) 的系数"。解 \(A(x)\)： \[ A(x)=\frac{1-x}{1-4x}=\frac{1}{1-4x}-\frac{x}{1-4x} =\sum_{n\ge0}4^nx^n-\sum_{n\ge0}4^{n-1}x^n=\sum_{n\ge0}3\cdot4^{n-1}x^n. \] 因此 \(a_n=3\cdot4^{n-1}\)（\(n\ge1\)）。

另一种做法：写出 \(a_{n+1}\) 的递推，再减去 \(a_n\) 的递推，得 \(a_{n+1}-a_n=3a_n\)，即 \(a_{n+1}=4a_n\)（\(n\ge1\)），配合 \(a_0=1,a_1=3\) 求解。

1. 关键事实：\(\dfrac{A(x)}{1-x}=\big(\sum a_ix^i\big)\big(\sum x^j\big)\)，其 \(x^{n-1}\) 项系数为 \(\sum_{i=0}^{n-1}a_i\)。所以 \(\sum_{n\ge1}\big(\sum_{i=0}^{n-1}a_i\big)x^n=x\cdot\dfrac{A(x)}{1-x}\)。
2. 代回得 \(A(x)-1=\dfrac{3xA(x)}{1-x}\)。两边乘 \((1-x)\)：\((A-1)(1-x)=3xA\)，展开 \(A-Ax-1+x=3xA\)，整理 \(A(1-4x)=1-x\)。
3. 故 \(A(x)=\dfrac{1-x}{1-4x}\)。拆开读系数：\(x^n\) 系数为 \(4^n-4^{n-1}=4^{n-1}(4-1)=3\cdot4^{n-1}\)（\(n\ge1\)）。♦

习题 10

原书此题以提问形式给出："\([x^n]\prod_{i\ge1}F_i(x)\) 会是什么？"——这是引导读者思考无穷乘积的系数何时有意义的铺垫，答案由下一题给出。

习题 11

是的。若不存在这样的 \(n\)，则对每个 \(m\)，只有有限个幂级数对所有 \(n\le m\) 含 \(x^n\) 项，于是 \([x^m]\prod_{i\ge1}F_i(x)\) 是有限的（即良定义）。

1. 把无穷乘积展开成单项相乘时，要得到 \(x^m\) 这一项，每个因子要么贡献它的常数项、要么贡献某个 \(x^{\ge1}\) 项。
2. 若除有限个因子外，其余因子的最低次正项都高于 \(m\)，那么对 \(x^m\) 有贡献的因子只有有限个，乘起来得到的 \(x^m\) 系数就是有限和——良定义。♦

习题 12

用与例 3.17 相同的技巧，得到 \[\sum_{n\ge0}p_{\text{odd}}(n)x^n=\prod_{\substack{i\ge1\\ i\ \text{odd}}}\frac{1}{1-x^i}.\tag{3.37}\]

1. 对每个奇数部分 \(i\in\{1,3,5,\dots\}\)，"用 \(k\) 个 \(i\)"贡献 \(x^{ki}\)，合起来是 \(\dfrac{1}{1-x^i}\)。
2. 各奇数部分的选择互相独立，按乘积公式把所有奇数 \(i\) 的因子相乘，即得 (3.37)。♦

习题 13

按例 3.17 之后的讨论，可见 \[\sum_{n\ge0}p_{d}(n)x^n=(1+x)(1+x^2)(1+x^3)\cdots=\prod_{j\ge1}(1+x^j).\tag{3.38}\]

1. 对每个 \(j\)，只有"用 0 次"或"用 1 次"两种选择，贡献 \(1+x^j\)。
2. 所有 \(j\) 的选择独立，相乘得 (3.38)。♦

习题 14

我们断言对一切 \(n\) 有 \(p_{\text{odd}}(n)=p_d(n)\)。证法是说明两个数列有相同的生成函数，即证 \[\prod_{\substack{i\ge1\\ i\ \text{odd}}}\frac{1}{1-x^i}=\prod_{j\ge1}(1+x^j).\tag{3.39}\] 为证此式，两边同乘 \(\prod_{j\ge1}(1-x^j)\)。左边变为 \[\frac{\prod_{j\ge1}(1-x^j)}{\prod_{\substack{i\ge1\\i\ odd}}(1-x^i)}=\prod_{\substack{i\ge1\\i\ \text{even}}}(1-x^i),\] 右边变为 \[\prod_{j\ge1}(1-x^j)(1+x^j)=\prod_{i\ge1}(1-x^{2i}).\] 所以 (3.39) 两边确实相等。

1. 左边乘 \(\prod_j(1-x^j)\) 后，分母里的奇数因子 \(1-x^i\) 被约掉，只剩下分子里的偶数因子 \(\prod_{i\,even}(1-x^i)\)。
2. 右边乘 \(\prod_j(1-x^j)\) 后，逐项配对 \((1-x^j)(1+x^j)=1-x^{2j}\)，得到 \(\prod_{j\ge1}(1-x^{2j})\)。
3. 两边都是"对所有偶数 \(m\) 取 \((1-x^m)\) 的乘积"，完全相同。故原式成立，进而 \(p_{\text{odd}}(n)=p_d(n)\)。♦

习题 15

所求的无穷乘积与习题 13 中算出的 \(\sum p_d(n)x^n\) 很像，差别在符号。也就是说，\(n\) 的一个由奇数个互异部分组成的拆分对生成函数贡献 \(-x^n\)，由偶数个互异部分组成的拆分贡献 \(+x^n\)。由欧拉五边形数定理（定理 2.28），这些项几乎全部相互抵消，只在 \(n\) 为五边形数时留下。其结论是 \[A(x)=\prod_{i\ge1}(1-x^i)=\sum_{n=-\infty}^{\infty}(-1)^n x^{n(3n+1)/2}=1-x-x^2+x^5+x^7-x^{12}+\cdots.\]

1. 展开 \(\prod_{i\ge1}(1-x^i)\)，每选一个 \(-x^i\) 就贡献一个互异部分并带一个负号；选 \(k\) 个部分则带 \((-1)^k\)。
2. 故 \([x^n]\prod(1-x^i)=\sum_{k}(-1)^k\cdot(\text{用 }k\text{ 个互异部分凑出 }n\text{ 的方法数})\)，即"偶数个"减"奇数个"。
3. 欧拉五边形数定理给出这个系数：当 \(n=\dfrac{m(3m\pm1)}{2}\)（广义五边形数）时为 \((-1)^m\)，否则为 0。写成 \(\sum_{n=-\infty}^\infty(-1)^nx^{n(3n+1)/2}\)，前几项即 \(1-x-x^2+x^5+x^7-x^{12}+\cdots\)。♦

习题 16

回忆恒等式 \(B(x)=\sum_{n\ge0}p(n)x^n=\prod_{i\ge1}\dfrac{1}{1-x^i}\)。将它与上一题结果比较，可见 \(A(x)B(x)=1\)。这意味着当 \(n\ge1\) 时 \([x^n](A(x)B(x))=0\)。用 \(A,B\) 的系数表达，得到恒等式 \[p(n)-p(n-1)-p(n-2)+p(n-5)+p(n-7)-\cdots=0,\] \[p(n)=\sum_{k=1}^{n}(-1)^{k+1}p\!\left(n-\frac{k(3k+1)}{2}\right)+\sum_{k=1}^{n}(-1)^{k+1}p\!\left(n-\frac{k(3k-1)}{2}\right),\] 其中约定当 \(m<0\) 时 \(p(m)=0\)。

1. \(A(x)B(x)=1\) 说明：除常数项外，乘积每个 \(x^n\) 系数都是 0。
2. 把 \(A(x)=1-x-x^2+x^5+x^7-\cdots\) 与 \(B(x)=\sum p(m)x^m\) 相乘，取 \(x^n\) 系数，得到 \[p(n)-p(n-1)-p(n-2)+p(n-5)+p(n-7)-p(n-12)-\cdots=0.\]
3. 移项即把 \(p(n)\) 用更小的拆分数表示，正负号按 \((-1)^{k+1}\) 交替，位移量取广义五边形数 \(\dfrac{k(3k\pm1)}{2}\)。♦

习题 17

设 \(A(x)=\sum_{n\ge0}a_n\dfrac{x^n}{n!}\) 为该数列的指数生成函数（exponential generating function）。把定义式两边乘 \(\dfrac{x^n}{n!}\) 并对 \(n\ge1\) 求和： \[\sum_{n\ge1}a_n\frac{x^n}{n!}=\sum_{n\ge1}n a_{n-1}\frac{x^n}{n!}+\sum_{n\ge1}(n+1)x^n.\] 两边都能认出 \(A(x)\)。右边最后一项就是 \(\dfrac{1}{(1-x)^2}-1\)。因此 \[A(x)=xA(x)+\frac{1}{(1-x)^2}-1,\quad A(x)(1-x)=\frac{1}{(1-x)^2}-1,\quad A(x)=\frac{1}{(1-x)^3}-\frac{1}{1-x}.\] 只剩求右边 \(x^n\) 的系数。第二项的系数是 1。第一项 \[\frac12\Big(\frac{1}{1-x}\Big)''=\frac12\sum_{n\ge2}n(n-1)x^{n-2},\] 其 \(x^n\) 系数为 \(\binom{n+2}{2}\)，于是右边 \(x^n\) 系数为 \(\binom{n+2}{2}-1\)。因此 \[a_n=n!\!\left(\binom{n+2}{2}-1\right)=\frac{(n+2)!}{2}-n!.\]

1. \(\sum_{n\ge1}n a_{n-1}\frac{x^n}{n!}=x\sum_{n\ge1}a_{n-1}\frac{x^{n-1}}{(n-1)!}=xA(x)\)。
2. \(\sum_{n\ge1}(n+1)x^n=\sum_{n\ge0}(n+1)x^n-1=\dfrac{1}{(1-x)^2}-1\)。
3. 解出 \(A(x)=\dfrac{1}{(1-x)^3}-\dfrac{1}{1-x}\)。用 \(\dfrac{1}{(1-x)^3}=\sum\binom{n+2}{2}x^n\) 读系数 \(\binom{n+2}{2}-1\)。
4. 因 \(A\) 是指数生成函数，\(a_n=n!\cdot[x^n]A(x)=n!\big(\binom{n+2}{2}-1\big)=\dfrac{(n+2)!}{2}-n!\)。♦

习题 18

设 \(A(x)=\sum_{n\ge0}a_n\dfrac{x^n}{n!}\) 为该数列的指数生成函数。两边乘 \(\dfrac{x^n}{n!}\) 并对 \(n\ge1\) 求和： \[\sum_{n\ge1}a_n\frac{x^n}{n!}=\sum_{n\ge1}a_{n-1}\frac{x^n}{(n-1)!}+\sum_{n\ge1}(-1)^n\frac{x^n}{n!},\] \[A(x)-1=xA(x)+e^{-x}-1.\] 由此 \[A(x)=\frac{e^{-x}}{1-x}=\sum_{n\ge0}\Big(\sum_{k=0}^{n}\frac{(-1)^k}{k!}\Big)x^n.\] 因此对 \(n\ge1\)，\(A(x)\) 中 \(\dfrac{x^n}{n!}\) 的系数为 \[a_n=\sum_{k=0}^{n}(-1)^k\frac{n!}{k!}.\]

1. \(\sum_{n\ge1}a_{n-1}\frac{x^n}{(n-1)!}=x\sum a_{n-1}\frac{x^{n-1}}{(n-1)!}=xA(x)\)；\(\sum_{n\ge0}(-1)^n\frac{x^n}{n!}=e^{-x}\)。得方程 \(A-1=xA+e^{-x}-1\)。
2. 整理 \(A(1-x)=e^{-x}\)，故 \(A(x)=\dfrac{e^{-x}}{1-x}\)。
3. 两个级数相乘 \(\big(\sum\frac{(-1)^k}{k!}x^k\big)\big(\sum x^m\big)\)，\(x^n\) 系数为 \(\sum_{k=0}^n\frac{(-1)^k}{k!}\)；乘 \(n!\) 得 \(a_n=\sum_{k=0}^n(-1)^k\frac{n!}{k!}\)。♦

习题 19

首先用 \(n\) 种方式选出会议委员会的主席。剩下的 \(n-1\) 人可以分到三个委员会中的任意一个，只要拨款委员会人数为偶、业务委员会人数为奇。

先看 \(n\) 为偶的情形。若 \(n\) 偶，则 \(n-1\) 奇。设 \(a,b,c\) 为三个委员会的人数。我们断言：在 \(a+b\) 为奇的所有情形中，恰好一半是"好"的。事实上，此时在好的分配与坏的分配之间存在一个双射（bijection）：它把拨款委员会与业务委员会的所有成员互换。于是若原来 \(a\) 奇 \(b\) 偶（坏），互换后变成 \(a\) 偶 \(b\) 奇（好），反之亦然。因此问题归结为：证明在 \(A,B,C\) 三字母组成、长为 \(n-1\)、其中 \(a+b\) 为奇的词中，恰有 \((3^{n-1}+1)/2\) 个。这是对的：若 \(w\) 是这样一个含 \(c\) 个字母 \(C\) 的词，则 \(c\) 有 \(\binom{n-1}{c}2^{\,n-1-c}\) 种可能。对所有偶 \(c\) 求和： \[\sum_{\substack{c=0\\ c\ \text{even}}}^{n-2}\binom{n-1}{c}2^{\,n-1-c}=\frac{(2+1)^{n-1}+(2-1)^{n-1}}{2}=\frac{3^{n-1}+1}{2}.\] \(n\) 为奇的情形非常类似，留给读者。

1. 把每个人贴上 \(A\)（拨款）、\(B\)（业务）、\(C\)（会议）三种标签之一，长为 \(n-1\) 的词共 \(3^{n-1}\) 个。约束是 \(a\) 偶、\(b\) 奇，即"好词"。
2. 第一步取一半（按 \(a+b\) 奇）：互换 \(A\leftrightarrow B\) 给出好词与坏词的双射，故 \(a+b\) 为奇的词中好词恰一半。于是只需数 \(a+b\) 为奇的词总数。
3. 固定 \(C\) 的个数 \(c\)：选哪些位置放 \(C\) 有 \(\binom{n-1}{c}\) 种；其余 \(n-1-c\) 个位置各填 \(A\) 或 \(B\) 有 \(2^{n-1-c}\) 种。\(a+b=n-1-c\)，\(n-1\) 奇时 \(a+b\) 奇 \(\Leftrightarrow c\) 偶。
4. 第二步提取偶次项：令 \(t=2\)，由二项式 \((t+1)^{m}=\sum_c\binom mc t^{m-c}\) 与 \((t-1)^m=\sum_c\binom mc(-1)^c t^{m-c}\) 相加除以 2，偶 \(c\) 项保留、奇 \(c\) 项抵消，得 \(\dfrac{3^{n-1}+1}{2}\)。再取一半本应再除 2——但这一半已是"好词数"，结合主席的 \(n\) 种选法即得总方案。♦

习题 20

考虑一篇 \(n\) 页论文的某个合法排版，去掉最后一页，则有两种可能：

(a) 最后一章仍排列正确。则论文其余部分有 \(b_{n-1}\) 种可能，被去掉的那一页有两种可能，给出原论文 \(2b_{n-1}\) 种可能。

(b) 最后一章不再排列正确。这意味着最后一章不再同时含两种页。设最后一章原有 \(i\) 页，则除最后一章外的各章有 \(b_{n-i}\) 种可能，最后一章有两种可能（所有页同一种、最后一页是另一种），合计再添 \(2\sum_{j=0}^{n-2}b_j\) 种可能。

既然递推关系已证，用归纳法证 \(b_n=2\cdot3^{n-2}\) 就是例行公事。

1. (a) 删去末页后最后一章仍合法：其余 \(b_{n-1}\) 种，末页两选，得 \(2b_{n-1}\)。
2. (b) 删去末页破坏了最后一章：说明最后一章本是"清一色 \(i-1\) 页 + 末页异色"，共 \(i\) 页；前面各章 \(b_{n-i}\) 种、最后一章 2 种，对所有 \(i\) 求和得 \(2\sum_{j=0}^{n-2}b_j\)。
3. 由递推得公比 3：对 \(n\ge3\) 把相邻两式相减， \[b_n-b_{n-1}=\Big(2b_{n-1}+2\!\!\sum_{j=0}^{n-2}\!b_j\Big)-\Big(2b_{n-2}+2\!\!\sum_{j=0}^{n-3}\!b_j\Big)=2b_{n-1}-2b_{n-2}+2b_{n-2}=2b_{n-1},\] 故 \(b_n=3b_{n-1}\)（\(n\ge3\)）。即从 \(b_2\) 起是公比 3 的等比数列，于是 \(b_n=2\cdot3^{n-2}\)（\(n\ge2\)）。♦

习题 21

(a) 我们只需把 \([n]\) 划分成三个非空块，再在每块上完成那件平凡任务。平凡任务恰有一种做法。因此 \[A(x)=B(x)=C(x)=\sum_{n\ge1}\frac{x^n}{n!}=e^x-1.\] 于是乘积公式给出"完成复合任务的方法数"的指数生成函数 \[S_3(x)=A(x)B(x)C(x)=(e^x-1)^3=e^{3x}-3e^{2x}+3e^x-1.\]

(b) 由上一题结果以及恒等式 \(e^{kx}=\sum_{n\ge0}k^n\dfrac{x^n}{n!}\)，对正 \(n\) 有 \[OS(n,3)=3^n-3\cdot2^n+3.\] 因此 \(S(n,3)=(3^{n-1}-2^n+1)/2\)（\(n>0\)），与之前的结果一致。

1. 单个非空块的指数生成函数：用 \(k\ge1\) 个元素只一种方式，故 \(\sum_{k\ge1}\frac{x^k}{k!}=e^x-1\)。
2. 三个有序块独立，乘积公式给 \((e^x-1)^3\)；用二项展开 \((e^x-1)^3=e^{3x}-3e^{2x}+3e^x-1\)。
3. 取 \(\frac{x^n}{n!}\) 系数：\(e^{kx}\) 贡献 \(k^n\)，故 \(OS(n,3)=3^n-3\cdot2^n+3\)（常数 \(-1\) 只影响 \(n=0\)）。
4. 块无序则除以 \(3!=6\)：\(S(n,3)=\dfrac{3^n-3\cdot2^n+3}{6}=\dfrac{3^{n-1}-2^n+1}{2}\)。♦

习题 22

可把问题想成：\(d_n\) 是从 \((0,0)\) 到 \((n,n)\)、用步 \((1,0),(0,1)\)、且在主对角线上时还可用 \((1,1)\) 的格点路径（lattice path）数。

设 \(p\) 为一条不以 \((1,1)\) 步开头的此类路径。这种路径数为 \(d_n-d_{n-1}\)，其生成函数为 \(D(x)(1-x)\)。这种路径可分解成两部分：第一次触到主对角线之前的部分，和之后的部分。第一部分由生成函数 \(2xC(x)\) 枚举，其中 \(C(x)\) 是例 3.16 算出的卡塔兰数（Catalan numbers）生成函数（第一部分是一条在对角线下方或上方的东北向格点路径，故有因子 2）。第二部分由 \(D(x)\) 本身枚举。用乘积公式得 \[D(x)(1-x)-1=2xC(x)D(x),\] （此分解只在 \(n\ge1\) 时可能）。解出 \[D(x)=\frac{1}{1-x-2xC(x)}=\frac{1}{\sqrt{1-4x}-x}=\frac{\sqrt{1-4x}+x}{1-4x-x^2}.\]

1. "不以 \((1,1)\) 开头"的路径：所有路径 \(d_n\) 减去"以 \((1,1)\) 开头"的（去掉首步后是 \((n-1,n-1)\) 的同类路径，共 \(d_{n-1}\)），得 \(d_n-d_{n-1}\)，生成函数 \(D(x)-xD(x)=D(x)(1-x)\)。
2. 把这种路径按"首次回到对角线"切两段：前段是一条不碰对角线（除两端）的东北路径，在对角线上方或下方，由 \(2xC(x)\) 枚举；后段又是一条同类路径，由 \(D(x)\) 枚举。乘积公式：\(D(x)(1-x)-1=2xC(x)D(x)\)（减 1 是排除空路径）。
3. 解 \(D(x)=\dfrac{1}{1-x-2xC(x)}\)，代入 \(2xC(x)=1-\sqrt{1-4x}\) 得 \(\dfrac{1}{\sqrt{1-4x}-x}\)。
4. 有理化：分子分母同乘 \(\sqrt{1-4x}+x\)，分母 \((1-4x)-x^2\)，得 \(\dfrac{\sqrt{1-4x}+x}{1-4x-x^2}\)。♦

习题 23

用格点路径的语言，\(M_n\) 是从 \((0,0)\) 到 \((n/2,n/2)\)、用步 \((1,0),(0,1),(1/2,1/2)\) 且从不越过对角线 \(x=y\) 的格点路径数。其余证明与例 3.16 很像。

首先 \(M_0=1\)。设 \(M(x)=\sum_{n\ge0}M_nx^n\)。看所有 \(n\ge1\) 局、以平局收尾、且不以平局开局的比赛序列：其数目为 \(M_n-M_{n-1}\)，生成函数为 \(M(x)(1-x)-1\)。我们再用乘积公式以另一种方式得到同一个生成函数。把第一次（在 0-0 之后）出现平局的时刻称为"临界时刻"。临界时刻把序列切成两段：临界时刻之前的部分与之后的部分。之后的部分就是一条与原来同型的序列，生成函数为 \(M(x)\)。之前的部分是一条除首尾外从不平局的序列，由类似例 3.16 的论证，其生成函数为 \(M(x)x^2\)（序列以 A 胜开头，临界时刻随 A 负而到来，故该段有 \(M_{i-2}\) 种选择，\(i\) 为段长）。由乘积公式得函数方程 \[M(x)(1-x)-1=M(x)x^2\cdot M(x),\qquad M(x)^2x^2+M(x)(x-1)+1=0.\] 解这个关于 \(M(x)\) 的二次方程，并验证负根才是有组合意义的那个，得 \[M(x)=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}.\] 数 \(M_n\) 称为莫兹金数（Motzkin numbers）。

1. "不以平局开局"的序列数 \(=M_n-M_{n-1}\)，生成函数 \(M(x)(1-x)-1\)（减 1 排除空序列）。
2. 按"第一次回到平局"切两段：前段从首胜到首次扳平，中间是更短的同型序列，由 \(M_{i-2}\) 计，对应生成函数 \(x^2M(x)\)；后段是同型序列 \(M(x)\)。乘积得 \(x^2M(x)\cdot M(x)\)。
3. 令两种数法相等：\(M(x)(1-x)-1=x^2M(x)^2\)，整理成 \(x^2M^2+(x-1)M+1=0\)。
4. 求根并取在 \(x\to0\) 时趋于 \(M_0=1\) 的那一支（负号根），得 \(M(x)=\dfrac{1-x-\sqrt{1-2x-3x^2}}{2x^2}\)。♦

习题 24

用格点路径的语言，\(r_n\) 是从 \((0,0)\) 到 \((n,n)\)、用步 \((1,0),(0,1),(1,1)\) 且从不越过主对角线的格点路径数。其余与上一题类似，但有重要差别。设 \(R(x)\) 为所求生成函数。则 \(R(x)(1-x)-1\) 是"不以平局开局"的序列数的生成函数。按上题方式定义临界时刻，乘积公式给出 \[R(x)(1-x)-1=xR(x)\cdot R(x),\] 因为临界时刻之前的部分必须以 A 胜开头、以 B 胜结尾，中间是一条由 \(r_{i-1}\) 计的序列（临界时刻在比分 \(i\!-\!i\) 时到来）。解出 \[R(x)=\frac{1-x-\sqrt{1-6x+x^2}}{2x}.\tag{3.40}\] 数 \(r_n\) 称为施罗德数（Schröder numbers）。

1. "不以平局开局"序列：\(r_n-r_{n-1}\)，生成函数 \(R(x)(1-x)-1\)。
2. 切两段：前段以 A 胜开头、B 胜结尾、中间由 \(r_{i-1}\) 计，对应 \(xR(x)\)；后段同型 \(R(x)\)。乘积 \(xR(x)^2\)。
3. 令相等 \(R(1-x)-1=xR^2\)，即 \(xR^2-(1-x)R+1=0\)。求根公式：\(R=\dfrac{(1-x)\pm\sqrt{(1-x)^2-4x}}{2x}\)，判别式 \((1-x)^2-4x=1-6x+x^2\)。
4. 取在 \(x\to0\) 趋于 \(r_0=1\) 的负号支，得 (3.40)。♦

习题 25

我们用普通生成函数的复合公式。把区间 \([1,n]\) 划分成未指定数目的若干小区间，再在每个小区间上完成"只用一种瓷砖铺满该区间"的任务。对长为 1 的区间有两种做法（红、蓝），对长为 2 的区间有三种做法（黑、白、黄），对更长的区间没有做法。因此 \(A(x)=2x+3x^2\)。于是复合公式给出 \[F(x)=\frac{1}{1-A(x)}=\frac{1}{1-2x-3x^2}.\] 由此 \(f(n)=\dfrac{3^{n+1}+(-1)^n}{4}\)。

1. "一块瓷砖盖住的区间"的生成函数：长 1 有 2 种 \(\to 2x\)，长 2 有 3 种 \(\to 3x^2\)，更长 0 种。故 \(A(x)=2x+3x^2\)。
2. 整条 \(1\times n\) 是若干块顺次拼接，复合公式给 \(F(x)=\dfrac{1}{1-2x-3x^2}\)。
3. 部分分式：\(1-2x-3x^2=(1-3x)(1+x)\)。设 \(\dfrac{1}{(1-3x)(1+x)}=\dfrac{a}{1-3x}+\dfrac{b}{1+x}\)，得 \(1=a(1+x)+b(1-3x)\)。代 \(x=\tfrac13\)：\(a=\tfrac34\)；代 \(x=-1\)：\(b=\tfrac14\)。
4. 读系数 \(f(n)=\tfrac34\cdot3^n+\tfrac14(-1)^n=\dfrac{3^{n+1}+(-1)^n}{4}\)。♦

习题 26

我们用普通生成函数的复合公式。把区间 \([1,n]\) 划分成未指定数目的若干小区间，再在每个小区间上完成"把它划成一个大小为 \(rk+1\)（\(k\) 为某非负整数）的部分"的任务。当区间长为 \(rk+1\) 时此事有一种做法，否则零种。因此内部生成函数为 \[A(x)=x+x^{r+1}+x^{2r+1}+\cdots=\frac{x}{1-x^r},\] 于是复合公式给出 \[H_r(x)=\frac{1}{1-A(x)}=\frac{1-x^r}{1-x-x^r}.\] 在 \(r=2\) 的特例下， \[\frac{1-x^2}{1-x-x^2}=1+\frac{x}{1-x-x^2},\] 这是斐波那契数（Fibonacci numbers）的生成函数（位移 1）。

1. 合法部分集合 \(\{1,\,r+1,\,2r+1,\dots\}\)，其生成函数 \(A(x)=\sum_{k\ge0}x^{rk+1}=x\sum_{k\ge0}(x^r)^k=\dfrac{x}{1-x^r}\)。
2. 合成是若干部分顺次排列，复合公式 \(H_r=\dfrac{1}{1-A(x)}=\dfrac{1}{1-\frac{x}{1-x^r}}=\dfrac{1-x^r}{1-x^r-x}=\dfrac{1-x^r}{1-x-x^r}\)。
3. \(r=2\)：\(\dfrac{1-x^2}{1-x-x^2}\)。因 \(1-x^2=(1-x-x^2)+x\)，故等于 \(1+\dfrac{x}{1-x-x^2}\)，而 \(\dfrac{x}{1-x-x^2}=\sum_{n\ge1}F_nx^n\) 正是斐波那契生成函数。♦

习题 27

设 \(A_d(x)\) 为所求生成函数。则 \[A_d(x)=\prod_{i\ge1}\big(1+x^i+\cdots+x^{(d-1)i}\big)=\prod_{i\ge1}\frac{1-x^{di}}{1-x^i}.\]

1. 部分 \(i\) 出现 \(t\) 次（\(0\le t\le d-1\)）贡献 \(x^{ti}\)，求和得 \(\sum_{t=0}^{d-1}x^{ti}=\dfrac{1-x^{di}}{1-x^i}\)。
2. 各部分独立，乘积公式相乘即得 \(A_d(x)\)。♦

习题 28

设 \(B_d(x)\) 为所求生成函数。则 \[B_d(x)=\prod_{\substack{j\ge1\\ j\ne dk}}\frac{1}{1-x^j}.\]

1. 对每个不被 \(d\) 整除的 \(j\)，"用任意非负次"给出 \(\dfrac{1}{1-x^j}\)；被 \(d\) 整除的 \(j\) 完全不允许（不放入乘积）。
2. 独立相乘得 \(B_d(x)\)。♦

习题 29

等式 \(A_d(x)=B_d(x)\) 成立，因为 \(A_d(x)\) 中那些 \(j=di\) 的因子 \(1-x^j\) 相互约去。因此对一切 \(n\) 与 \(d\ge2\)，\(n\) 的"每个部分出现少于 \(d\) 次"的拆分数等于"没有部分被 \(d\) 整除"的拆分数。

1. 由习题 27：\(A_d(x)=\dfrac{\prod_{i\ge1}(1-x^{di})}{\prod_{i\ge1}(1-x^i)}\)。
2. 分母 \(\prod_i(1-x^i)\) 含所有 \(1-x^m\)；其中 \(m=di\) 的那些恰被分子 \(\prod_i(1-x^{di})\) 约掉。
3. 约去后分母只剩 \(m\) 不是 \(d\) 倍数的因子 \(1-x^m\)，即 \(A_d(x)=\prod_{d\nmid j}\dfrac{1}{1-x^j}=B_d(x)\)。系数相等 \(\Rightarrow\) 两类拆分一样多。♦

习题 30

比分被打平的那些时刻，把进球序列切成数目不定的若干段。每一段都以主队进球开始、以客队进球结束。在它们中间，是一段"主队始终不落后"的常规进球序列。换句话说，把整条序列按"回到平局"切段，每段 = 主队先得一分 + 中间一条同型（卡塔兰）序列 + 客队扳平一分。这正好套用复合公式。

1. 设卡塔兰数生成函数 \(C(x)=\sum_{n\ge0}c_nx^n\)。一条合法序列（始终不落后、最后回到平局）按"第一次回到平局"分成若干素段：每个素段 = 一个"主队先得分"+ 中间一条更短的合法序列 + 一个"客队扳平"。
2. 一个素段的生成函数：首尾两步把长度抬高一档，中间是 \(C(x)\)，故素段的内部生成函数 \(A(x)=x\,C(x)\)（按"半长"\(n\) 计权，素段半长 \(i\) 对应 \(c_{i-1}x^i\)）。
3. 整条序列 = 若干素段顺次拼接，复合公式给 \(C(x)=\dfrac{1}{1-A(x)}=\dfrac{1}{1-xC(x)}\)。
4. 两边乘 \((1-xC(x))\)：\(C(x)\big(1-xC(x)\big)=1\)，即 \(xC(x)^2-C(x)+1=0\)。
5. 用求根公式 \(C(x)=\dfrac{1\pm\sqrt{1-4x}}{2x}\)，取在 \(x\to0\) 时有限（趋于 \(c_0=1\)）的负号支： \[C(x)=\frac{1-\sqrt{1-4x}}{2x},\] 正是公式 (3.19)。♦

返回 全书目录