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

3.8　习题Exercises

本页为译文 + 高中讲解合一：黑色正文为每道习题的忠实翻译；彩色框（解题思路 / 方法提示 / 例）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。每题只给思路与方法，不必给出最终完整答案（完整解答见对应“习题解答”一节）。

本节是什么这是第 3 章（生成函数）的全部习题。题目大致分四类：幂级数恒等式（第 1、10、11 题）、线性与非线性递推求通项（第 3、4、5、9、17、18 题）、序列空间的线性代数（第 6、7、8 题）、分拆与生成函数（第 12–16 题）以及计数与格路径模型（第 19–23 题）。下面逐题翻译并给出入手方法。

  1. 证明：对所有正整数 \(k\)， \[(1-x)^{-k}=\sum_{n\ge 0}\binom{n+k-1}{k-1}x^n.\]

    解题思路这是“负指数二项式定理”的核心公式。有两条路：
    1. 代数路线。已知最基本的几何级数 \(\dfrac{1}{1-x}=\sum_{n\ge0}x^n\)，即 \(k=1\) 时成立（此时 \(\binom{n+0}{0}=1\)）。对 \(k\) 作数学归纳：把 \((1-x)^{-(k+1)}=(1-x)^{-k}\cdot(1-x)^{-1}\) 写成两幂级数相乘，用乘积的系数（卷积）求出 \(x^n\) 的系数，再用组合恒等式 \(\sum_{j=0}^{n}\binom{j+k-1}{k-1}=\binom{n+k}{k}\)（“曲棍球棒恒等式”）合并。
    2. 组合路线。\((1-x)^{-k}=\big(\sum_{m\ge0}x^m\big)^k\)，展开后 \(x^n\) 的系数就是方程 \(m_1+m_2+\cdots+m_k=n\)（各 \(m_i\ge0\)）的非负整数解个数，即“\(n\) 个相同球放进 \(k\) 个不同盒子”的隔板法计数 \(\binom{n+k-1}{k-1}\)。
    小验证取 \(k=2,n=2\)：右边系数 \(\binom{3}{1}=3\)。左边 \((1-x)^{-2}=1+2x+3x^2+\cdots\)，\(x^2\) 系数正是 \(3\)。对得上。

  2. 我们如何能快速验证公式 (3.7) 对所有 \(n\) 确实成立？

    解题思路这里要回到 3.x 节中写出的那条公式 (3.7)。验证“一个含 \(n\) 的恒等式对所有 \(n\) 成立”的标准方法是：把它转化为生成函数等式。具体做法：把待证等式两边各自乘以合适的 \(x^n\)（或 \(x^n/n!\)）再对 \(n\) 求和，看左右两边是否化成同一个已知的闭形式（如 \(\frac1{1-x}\)、\(e^x\) 等）。若两个幂级数处处系数相等，则等式逐项成立。
    方法要点“验证一族等式”不需要逐个 \(n\) 代入；只要证明两边生成函数相同即可一次性覆盖所有 \(n\)。这正是生成函数把“无穷条等式”压缩成“一条等式”的威力。

  3. 求 \(a_n\) 的显式公式：已知 \(a_0=2\)，且对所有整数 \(n\ge1\) 有 \[a_n=4a_{n-1}-3.\]

    解题思路这是一阶常系数非齐次线性递推。两种入手法：
    1. 不动点法。设 \(a_n=L\) 为常数解，则 \(L=4L-3\Rightarrow L=1\)。令 \(b_n=a_n-1\)，则 \(b_n=4b_{n-1}\)，是纯几何递推，\(b_n=b_0\cdot4^n\)。由 \(b_0=a_0-1=1\) 得 \(b_n=4^n\)，故 \(a_n=4^n+1\)。
    2. 生成函数法。令 \(A(x)=\sum_{n\ge0}a_nx^n\)，把递推乘 \(x^n\) 求和，凑出 \(A(x)\) 的方程，解出有理函数后部分分式分解，回读系数。
    验证\(a_0=4^0+1=2\)；\(a_1=4a_0-3=4\cdot2-3=5\)，而 \(4^1+1=5\)，对得上。

  4. 求 \(a_n\) 的显式公式：已知 \(a_0=0\)，\(a_1=1\)，且对所有整数 \(n\ge2\) 有 \[a_n=4a_{n-1}-4a_{n-2}.\]

    解题思路二阶常系数齐次线性递推。写出特征方程 \(t^2=4t-4\)，即 \(t^2-4t+4=(t-2)^2=0\)，得重根 \(t=2\)。重根时通解形如 \(a_n=(A+Bn)\,2^n\)。代入初值 \(a_0=0,a_1=1\) 定出 \(A,B\)。
    1. \(a_0=A=0\)。
    2. \(a_1=(0+B)\cdot2=2B=1\Rightarrow B=\tfrac12\)，故 \(a_n=\tfrac{n}{2}2^n=n\,2^{n-1}\)。

  5. 求 \(a_n\) 的显式公式：已知 \(a_0=0\)，\(a_1=1\)，且对所有整数 \(n\ge2\) 有 \[a_n=4a_{n-1}-5a_{n-2}.\]

    解题思路同样是二阶齐次递推，但特征方程 \(t^2-4t+5=0\) 的判别式 \(16-20=-4<0\)，得共轭复根 \(t=2\pm i\)。可用复指数形式 \(a_n=\alpha(2+i)^n+\beta(2-i)^n\) 并由初值定系数；也可把复根写成模辐角形式 \(2\pm i=\sqrt5\,e^{\pm i\theta}\)（\(\theta=\arctan\tfrac12\)），得到实数通项 \(a_n=(\sqrt5)^n\,(C\cos n\theta+D\sin n\theta)\)。
    提示复根情形最终一定能化成只含实数的形式（含 \(\cos n\theta,\sin n\theta\)），因为递推系数与初值都是实数。

  6. （需要线性代数基础。）设 \(V\) 是所有满足递推关系 \[a_n=pa_{n-1}+qa_{n-2}\qquad(n\ge2)\tag{3.34}\] 的复数序列 \(\{a_n\}\) 的集合，其中 \(p,q\) 为固定实数。
    (a) 证明 \(V\) 是实数域上的向量空间。
    (b) \(V\) 的维数是多少？

    解题思路(a) 按向量空间定义逐条核对：序列的逐项相加与逐项数乘是否仍满足同一递推。关键是线性——若 \(\{a_n\},\{b_n\}\) 都满足 (3.34)，则 \(\{a_n+b_n\}\) 与 \(\{\lambda a_n\}\) 也满足，因为递推两边都是关于序列的线性表达式。零序列是零向量。
    维数的关键观察(b) 一个满足 (3.34) 的序列被前两项 \((a_0,a_1)\) 完全确定：之后每一项都由递推唯一算出。于是映射 \(\{a_n\}\mapsto(a_0,a_1)\) 是 \(V\) 到 \(\mathbb{C}^2\)（作为实向量空间）的同构。注意标量域是实数：\(\mathbb{C}^2\) 作为实向量空间是 4 维（一个复数算两维实数），故 \(\dim_{\mathbb{R}}V=4\)。（若把标量改成复数则 \(\dim_{\mathbb{C}}V=2\)；本题明确要求实数域，所以答案是 4。）

  7. 设 \(V\) 如上一题所定义。求 \(V\) 中所有每一项都形如 \(a_n=a^n\)（对所有非负整数 \(n\)）的元素。

    解题思路把 \(a_n=a^n\) 代入递推 (3.34)：\(a^n=p\,a^{n-1}+q\,a^{n-2}\)。当 \(a\ne0\) 时两边除以 \(a^{n-2}\) 得 特征方程 \(a^2=pa+q\)。所以“纯几何序列 \(a^n\)”落在 \(V\) 中，当且仅当公比 \(a\) 是特征方程 \(t^2-pt-q=0\) 的根。
    提示这解释了为什么第 4、5 题要解特征方程：特征根 \(a\) 给出的几何序列 \(a^n\) 正是 \(V\) 的“基本解”。

  8. \(^{+}\) 设 \(V\) 如第 6 题定义。求 \(V\) 的一组基，并写出你所找基元素的显式公式。

    解题思路由第 6 题知（在实数域上）\(\dim_{\mathbb{R}}V=4\)，所以要找四个实线性无关的解。由第 7 题，特征方程 \(t^2-pt-q=0\) 的根 \(r\) 给出几何解 \(\{r^n\}\in V\)。由于标量只能取实数，把一个复序列乘以 \(i\) 得到的序列与原序列实线性无关，于是每个几何解都能“配对”出两个实基元素。
    1. 两个不同根 \(r_1\ne r_2\)：取 \(\{r_1^n\},\{i\,r_1^n\},\{r_2^n\},\{i\,r_2^n\}\) 这四个序列。它们实线性无关（映到 \(\mathbb{C}^2\) 后行列式正比于 \(|r_1-r_2|^2\neq0\)），构成 \(V\) 的一组基。
    2. 重根 \(r_1=r_2=r\)：几何解只有一个，需补上 \(\{n\,r^n\}\)（直接代入可验证它也满足递推，参见第 4 题）；再配上乘 \(i\) 的版本，得基 \(\{r^n\},\{i\,r^n\},\{n\,r^n\},\{i\,n\,r^n\}\)。

  9. 解递推关系：\(a_0=1\)，且对所有 \(n\ge1\) 有 \[a_n=3\sum_{i=0}^{n-1}a_i.\]

    解题思路“当前项等于前面所有项之和的 3 倍”这类含累加和的递推，标准技巧是错位相减消去求和号。
    1. 记 \(S_{n-1}=\sum_{i=0}^{n-1}a_i\)，则 \(a_n=3S_{n-1}\)，且 \(a_{n+1}=3S_n=3(S_{n-1}+a_n)\)。
    2. 两式相减：\(a_{n+1}-a_n=3a_n\Rightarrow a_{n+1}=4a_n\)（对 \(n\ge1\)）。这是几何递推。
    3. 由 \(a_0=1\) 得 \(a_1=3\cdot a_0=3\)，此后 \(a_n=3\cdot4^{n-1}\)（\(n\ge1\)）。
    验证\(a_2=3(a_0+a_1)=3\cdot4=12=3\cdot4^{1}\)。对。

  10. 设 \(F_1,F_2,\dots\) 是一列形式幂级数，满足 \(F_i(0)=1\) 对所有 \(i\) 成立。证明：若存在正整数 \(n\)，使得序列中有无穷多个 \(F_i\) 含有 \(x^n\) 项（系数非零），则无穷乘积 \(\prod_{i\ge1}F_i\) 无定义。

    解题思路关键在“形式幂级数无穷乘积有定义”的判准：要使 \(\prod F_i\) 中每个固定次数 \(x^n\) 的系数由有限步运算确定，必须只有有限多个因子对 \(x^n\) 有贡献。条件 \(F_i(0)=1\) 保证常数项乘起来收敛到 1。
    1. 计算乘积中 \(x^n\) 的系数时，每个含非零 \(x^n\) 项的因子都会贡献一份。
    2. 若有无穷多个 \(F_i\) 都贡献 \(x^n\) 项，则该系数是一个无穷和，在形式幂级数环里没有意义（无法求出确定值）。
    3. 故乘积无定义。用反证或直接展开 \(x^n\) 系数即可说清。

  11. 上一题命题的逆命题成立吗？

    解题思路逆命题大意是：“若对每个 \(n\) 只有有限多个 \(F_i\) 含 \(x^n\) 项，则乘积有定义。”要判断真假，需检查在该条件下，乘积中每个 \(x^n\) 的系数是否都只是有限和。建议先尝试证明它为真（这正是无穷乘积有定义的充分条件），再考虑边界情形是否需要额外要求（如 \(F_i(0)=1\)）。给出证明或反例。

  12. 设 \(p_{\text{odd}}(n)\) 为整数 \(n\) 拆成奇数部分的拆分数，约定 \(p_{\text{odd}}(0)=1\)。求数列 \(p_{\text{odd}}(n)\) 的普通生成函数（ordinary generating function）。

    解题思路拆分生成函数的标准构造：每个允许使用的部分 \(k\) 贡献一个因子 \(\dfrac{1}{1-x^k}=1+x^k+x^{2k}+\cdots\)（表示 \(k\) 用 0、1、2、… 次）。只允许奇数部分，就只乘奇数 \(k\) 的因子： \[\sum_{n\ge0}p_{\text{odd}}(n)\,x^n=\prod_{k\ \text{奇}}\frac{1}{1-x^k}=\prod_{j\ge1}\frac{1}{1-x^{2j-1}}.\]
    小例\(n=3\)：奇数拆分有 \(3,\;1+1+1\)，共 2 个；展开乘积验证 \(x^3\) 系数确为 2。

  13. 设 \(p_d(n)\) 为整数 \(n\) 拆成互不相同部分的拆分数，约定 \(p_d(0)=1\)。求数列 \(p_d(n)\) 的普通生成函数。

    解题思路“各部分互不相同”意味着每个 \(k\) 最多用一次，所以它的因子只有两项 \((1+x^k)\)： \[\sum_{n\ge0}p_d(n)\,x^n=\prod_{k\ge1}(1+x^k).\]
    小例\(n=4\)：互异拆分有 \(4,\;3+1\)，共 2 个（\(2+2\)、\(1+1+\dots\) 都不算）。展开 \(\prod(1+x^k)\) 验证 \(x^4\) 系数为 2。

  14. \(^{+}\) 比较前两题的结果。它们告诉我们 \(p_{\text{odd}}(n)\) 与 \(p_d(n)\) 之间有怎样的联系？

    解题思路把两个生成函数化到一起。对“互异部分”的生成函数用恒等式 \(1+x^k=\dfrac{1-x^{2k}}{1-x^k}\)： \[\prod_{k\ge1}(1+x^k)=\prod_{k\ge1}\frac{1-x^{2k}}{1-x^k}.\] 分子是所有偶数次幂 \(1-x^{2k}\)，恰好把分母中偶数 \(k\) 的因子 \(1-x^{2k}\) 全部约掉，只剩奇数 \(k\) 的 \(\dfrac{1}{1-x^k}\)。于是两个生成函数相等，从而对所有 \(n\)：
    欧拉定理（结论方向）\(p_{\text{odd}}(n)=p_d(n)\)：把 \(n\) 拆成奇数部分的方法数，等于把 \(n\) 拆成互异部分的方法数。

  15. \(^{+}\) 用仅一个求和号把无穷乘积 \[\prod_{i\ge1}(1-x^i)\] 表示为无穷和。

    解题思路这是著名的欧拉五边形数定理（pentagonal number theorem）。结论是 \[\prod_{i\ge1}(1-x^i)=\sum_{k=-\infty}^{\infty}(-1)^k\,x^{k(3k-1)/2}.\] 指数 \(g_k=\dfrac{k(3k-1)}{2}\)（\(k=0,\pm1,\pm2,\dots\)）就是广义五边形数。证明思路是把展开后 \(x^n\) 的系数解释为“拆成互异部分、按部分个数奇偶带符号”的带号计数，再构造一个对合（involution）使绝大多数项两两抵消，仅五边形数处留下 \(\pm1\)。
    前几项\(\prod(1-x^i)=1-x-x^2+x^5+x^7-x^{12}-x^{15}+\cdots\)，指数 \(1,2,5,7,12,15\) 正是五边形数。

  16. 利用上一题的结果，证明拆分数 \(p(n)\) 的一条递推关系。

    解题思路已知拆分生成函数 \(\sum p(n)x^n=\prod_{i\ge1}\dfrac{1}{1-x^i}\)。因此 \[\Big(\sum_{n\ge0}p(n)x^n\Big)\Big(\prod_{i\ge1}(1-x^i)\Big)=1.\] 把上一题的五边形数展开代入第二个因子，比较两边 \(x^n\) 的系数（左边为 0（当 \(n\ge1\)）、右边由卷积给出），即得欧拉递推：
    欧拉递推\[p(n)=\sum_{k\ge1}(-1)^{k-1}\Big[p\big(n-\tfrac{k(3k-1)}{2}\big)+p\big(n-\tfrac{k(3k+1)}{2}\big)\Big].\]

  17. 求 \(a_n\) 的显式公式：\(a_n=na_{n-1}+(n+1)!\)（\(n\ge1\)），\(a_0=0\)。

    解题思路系数随 \(n\) 变化（变系数递推），适合用除以 \(n!\) 做归一化，化成累加式。令 \(b_n=\dfrac{a_n}{n!}\)。两边同除 \(n!\)： \[\frac{a_n}{n!}=\frac{a_{n-1}}{(n-1)!}+\frac{(n+1)!}{n!}\;\Longrightarrow\; b_n=b_{n-1}+(n+1).\] 这是简单的累加递推，从 \(b_0=0\) 逐步求和得 \(b_n=\sum_{j=1}^{n}(j+1)\)，再乘回 \(n!\) 得 \(a_n\)。
    提示\(\sum_{j=1}^{n}(j+1)=\dfrac{n(n+1)}{2}+n=\dfrac{n(n+3)}{2}\)，故 \(a_n=\dfrac{n(n+3)}{2}\,n!\)。

  18. 求 \(a_n\) 的显式公式：\(a_n=na_{n-1}+(-1)^n\)，\(a_0=1\)。

    解题思路同样用 \(b_n=\dfrac{a_n}{n!}\) 归一化： \[b_n=b_{n-1}+\frac{(-1)^n}{n!}.\] 于是 \(b_n=\sum_{k=0}^{n}\dfrac{(-1)^k}{k!}\)（注意 \(b_0=a_0=1\) 对应 \(k=0\) 项）。这正是 \(e^{-1}\) 的部分和——也是“错排数（derangement）”的特征。最后 \(a_n=n!\sum_{k=0}^{n}\dfrac{(-1)^k}{k!}=D_n\)。
    验证\(a_1=1\cdot1+(-1)=0=D_1\)；\(a_2=2\cdot0+1=1=D_2\)。对。

  19. 为例 3.22 的结果给出一个组合证明。不要使用归纳法。

    解题思路“组合证明”指通过双计数（double counting）或建立双射（bijection）来证明等式：让等式两边各自数同一个有限集合，从而必然相等；或构造两类对象之间的一一对应。回到例 3.22 的具体陈述，找出等式两边各在数什么对象，再说明它们其实是同一批对象的两种数法。不要用 \(n\to n+1\) 的归纳。

  20. 设 \(b_n\) 如例 3.23 所定义。证明 \[b_n=2(b_{n-1}+b_{n-2}+\cdots+b_0).\] 再由此推出当 \(n\ge2\) 时 \(b_n=2\cdot3^{n-2}\)。不要使用生成函数。

    解题思路第一步靠组合分解：按某个“第一处发生变化的位置”把被计数对象分类，每类对应一个更小的 \(b_j\)，前面的系数 2 来自两种选择，由此得累加递推。第二步用第 9 题同样的错位相减技巧：
    1. 记 \(T_{n-1}=b_{n-1}+\cdots+b_0\)，则 \(b_n=2T_{n-1}\)，\(b_{n+1}=2T_n=2(T_{n-1}+b_n)\)。
    2. 相减得 \(b_{n+1}-b_n=2b_n\Rightarrow b_{n+1}=3b_n\)（对 \(n\ge2\) 起几何增长，公比 3）。
    3. 定出初值后即得 \(b_n=2\cdot3^{n-2}\)。

  21. 设 \(OS(n,3)\) 为把 \([n]\) 拆成三个非空块的有序拆分数。也就是说 \(OS(n,3)=3!\,S(n,3)\)，因为 \(S(n,3)\) 所数的每个拆分的三个块都能以 6 种不同方式排序。
    (a) 求指数生成函数（exponential generating function） \[OS_3(x)=\sum_{n\ge0}OS(n,3)\,\frac{x^n}{n!}\] 的显式公式。
    (b) 由此推出 \(OS(n,3)\) 与 \(S(n,3)\) 的公式。

    解题思路(a) 用指数生成函数的乘积法则：把 \([n]\) 分成三个有标号、非空的块、且块本身有序，相当于三个“非空集合结构”的有序组合。单个非空块的 EGF 是 \(e^x-1\)（去掉空集的常数项 1）。三个有序块相乘： \[OS_3(x)=(e^x-1)^3.\]
    1. (b) 把 \((e^x-1)^3\) 二项展开：\((e^x-1)^3=e^{3x}-3e^{2x}+3e^{x}-1\)。
    2. 读取 \(\dfrac{x^n}{n!}\) 的系数：\(OS(n,3)=3^n-3\cdot2^n+3\cdot1^n-0=3^n-3\cdot2^n+3\)（\(n\ge1\)）。
    3. 再由 \(S(n,3)=\dfrac{OS(n,3)}{6}=\dfrac{3^n-3\cdot2^n+3}{6}\)。
以下三题的提示（原文给出）在下面这几道题中，读者不妨把问题翻译成格路径（lattice paths）的语言：把每一局比赛的结果画成在坐标格上向某方向走一步，把“总比分平局”翻译成路径回到某条对角线/坐标轴，把“某人从不落后”翻译成路径始终不越过某条边界。这类约束正是卡塔兰数（Catalan number）、莫茨金数（Motzkin number）一类计数的来源。

  1. \(^{+}\) 两位国际象棋特级大师下了一系列对局，计分规则如下：若某局分出胜负，胜者得 1 分、负者得 0 分；若某局为和棋，则双方各得 1 分。他们的系列赛以 \(n\!:\!n\) 平局结束。赛后一位记者注意到：和棋只在当前累计比分恰为平局时才出现。设 \(d_n\) 为这种情形可能发生的方式数，并令 \(d_0=1\)。求普通生成函数 \(D(x)=\sum_{n\ge0}d_nx^n\)。

    解题思路把比赛序列翻译成格路径。胜负局让两人比分差变化（一人 +1），和棋让两人同时 +1（比分差不变）。关键约束“和棋只发生在平分时”把整条赛程切成若干段：每两次“回到平分”之间是一段“非平分”的胜负序列，段与段之间可以插入和棋。
    1. 分解（decomposition）。用“第一次回到累计平分”的位置把序列拆成“一个不可分的首块 + 余下部分”，得到 \(D(x)\) 关于自身的方程（自指结构 → 二次方程），类似卡塔兰数生成函数的推导。
    2. 解方程。解出 \(D(x)\)（通常含 \(\sqrt{\,\cdot\,}\) 的闭形式），取在 \(x=0\) 处满足 \(D(0)=d_0=1\) 的那一支。

  2. \(^{+}\) 两位特级大师下 \(n\) 局，采用传统计分：胜得 1 分，和棋双方各得半分，负得 0 分。设 \(M_n\) 为：在大师 A 从不落后的前提下，系列赛最终以累计平局（即 \(\tfrac n2\!:\!\tfrac n2\)）收场的方式数。求数列 \(M_n\) 的普通生成函数。

    解题思路仍翻译成格路径。把每一局对 A 的“净得分相对 B 的领先量”画成一步：胜为 \(+1\)、负为 \(-1\)、和为 \(0\)（水平步）。三种步对应莫茨金路径的上、下、平三种走法。
    1. 约束翻译。“A 从不落后”= 路径始终保持在横轴上方（高度 \(\ge0\)）；“最终平局”= 路径终点回到高度 0。这正是莫茨金路径（Motzkin path）的定义。
    2. 建立方程。按路径“第一次回到 0”的位置作首步分解：要么第一步是水平步（贡献因子 \(x\)），要么是一个由上步…下步包住的拱形（内部又是莫茨金结构）。得到 \(M(x)=1+xM(x)+x^2M(x)^2\)，解此二次方程即得莫茨金数的生成函数。
    小例莫茨金数前几项 \(M_0,M_1,M_2,M_3=1,1,2,4\)：\(n=2\) 时的两种走法是“两步水平”与“一上一下”。

返回 全书目录