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

3.4　生成函数的复合Compositions of generating functions

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

在本节中，我们把生成函数（generating function）技术的适用范围进一步推广。

本节目标前面我们已经会把一个集合“切成若干段”，并对每一段用乘积公式计数。本节要解决的新问题是：当“段数”事先未知、可以是任意多时，如何把所有可能的段数一次性算清楚。关键工具是把一个生成函数代入另一个生成函数，即生成函数的复合。

3.4.1　普通生成函数

我们先来研究这样一种情形：仍然把集合 \([n]\) 划分成若干区间（interval），但划分方式比以前更复杂。

例 3.23 一位组合学专业的博士生，他的学位论文必须恰好有 \(n\) 页。论文可以有任意多的章，但每一章都必须至少包含一页正文和至少一页插图。此外，任何一章中的正文页数与插图页数都必须是整数。求该学生排布论文页面的方案数 \(b_n\) 的显式公式。

这道题的困难之处在于：我们不知道论文将会有多少章。如果我们知道恰好有两章、或恰好有三章，就可以轻松地用（普通生成函数的）乘积公式得到答案。

事实上，设 \(a_n\) 为一章能被排布的方案数。我们断言：当 \(n\ge 2\) 时 \(a_n=2^n-2\)，而当 \(n<2\) 时 \(a_n=0\)。这是因为每一页要么是正文页、要么是插图页（两种选择），但该学生不允许整章全是正文页、也不允许整章全是插图页（要从 \(2^n\) 种中去掉这两种）。定义 \(A(x)=\sum_{n\ge 0}a_nx^n\)，即数列 \(\{a_n\}\) 的普通生成函数。于是 \[\tag{3.30}A(x)=\sum_{n\ge 1}(2^n-2)x^n=\sum_{n\ge 1}2^nx^n-2\sum_{n\ge 1}x^n\] \[\tag{3.31}=\frac{2x}{1-2x}-\frac{2x}{1-x}=\frac{2x^2}{(1-2x)(1-x)}.\]

一份 \(n\) 页论文：先切成若干章，每章既有正文页(T)又有插图页(I) T I T I T T I I 第 1 章 第 2 章 第 3 章 红色竖线是“断章”处；每一章内部既要有 T 又要有 I（不能全 T 或全 I）
每一章是 \([n]\) 中的一段连续页；困难在于章数任意。一章 \(n\) 页的排法数为 \(2^n-2\)（去掉“全正文”与“全插图”两种）。
例（一章的方案数为什么是 \(2^n-2\)） 取 \(n=3\)。三页中每页选 T 或 I，共 \(2^3=8\) 种：TTT、TTI、TIT、TII、ITT、ITI、IIT、III。去掉“全 T”的 TTT 和“全 I”的 III，剩 \(8-2=6=2^3-2\) 种。代入 (3.30) 得 \([x^3]A(x)\) 的系数确为 \(2^3-2=6\)。

如果论文恰好由两章组成，那么由乘积公式可知，该学生可能的排布方案由生成函数 \(A^2(x)\) 计数。

因此，如果论文恰好含一章或两章，那么所有可能性由生成函数 \(A(x)+A^2(x)\) 计数。我们当然可以这样继续下去；即，若论文恰好由 \(k\) 章组成，则方案数由形式幂级数 \(A^k(x)\) 给出；若至多有 \(k\) 章，则由幂级数 \(\sum_{n=1}^{k}A^n(x)\) 给出。如果我们约定“写一篇没有任何章的论文”有一种方式，那么可记 \(A^0(x)=1\)，于是 \(\sum_{n=0}^{k}A^n(x)\) 是“至多 \(k\) 章的论文”的方案数生成函数。

你或许会说：这一切都很好，但它把我们引向何处？毕竟我们并不知道论文将有多少章，而上述方法似乎依赖于这一信息。所幸，事实并非如此。要理解原因，注意到这个无穷和 \[\tag{3.32}\sum_{n=0}^{\infty}A^n(x)=1+A(x)+A^2(x)+A^3(x)+\cdots\] 实际上是一个良定义的幂级数。也就是说，即便我们把无穷多个幂级数相加，在它们的和中，\(x^m\) 的系数对每个 \(m\) 都是有限的。（这段关于幂级数无穷和的讨论，大概会让读者想起 (3.27) 之后关于幂级数无穷乘积的讨论。）的确，\(A^n(x)\) 中指数最低的项是 \(x^{2n}\)。因此，对任意 \(m\)，只有有限多个形如 \(A^n(x)\) 的幂级数会带有 \(x^m\) 项，即那些满足 \(2n\le m\) 的项。于是，在我们这个无穷和 \(\sum_{n=0}^{\infty}A^n(x)\) 中，\(x^m\) 的系数只是有限多个系数之和。

为什么无穷和仍是良定义的幂级数
  1. \(A(x)\) 的最低次项是 \(x^2\)（因为 \(a_0=a_1=0\)）。
  2. 把 \(k\) 个 \(A(x)\) 相乘，得到 \(A^k(x)\)，它的最低次项至少是 \(x^{2k}\)。
  3. 固定一个 \(m\)。只有当 \(2k\le m\)，即 \(k\le m/2\) 时，\(A^k(x)\) 才可能贡献 \(x^m\) 项。
  4. 满足 \(k\le m/2\) 的 \(k\) 只有有限个，所以 \(x^m\) 的总系数是有限多项之和——求和有意义。

因此，无穷和 \(\sum_{n=0}^{\infty}A^n(x)\) 确实是有意义的；并且由前面的论证，它就是“一篇 \(n\) 页论文可被排成零章、或一章、或两章、或任意章数的方案数”的生成函数——因为求和项不会中断。所以至少我们已经找到了所求数列的生成函数。幂级数 \(B(x)=\sum_{n=0}^{\infty}A^n(x)\) 恰好就是普通生成函数 \(\sum_{n=0}^{\infty}b_nx^n\)，其中 \(b_n\) 是把一篇 \(n\) 页论文排成任意章数（每章至少一页正文、至少一页插图）的方案数。

你可能又要问：这又有什么用？我们能拿“无穷个无穷和（幂级数）之和”做什么呢？所幸，这个问题的答案远没有想象中糟糕。关键的观察是 \[B(x)=\sum_{n=0}^{\infty}A^n(x)=\frac{1}{1-A(x)}.\] 然而我们对 \(A(x)\) 有精确公式，因为已在 (3.30) 中算出。利用该公式，得 \[B(x)=\frac{1}{1-A(x)}=\frac{1}{1-\dfrac{2x^2}{(1-2x)(1-x)}}.\] 换句话说，现在我们已经有了数列 \(b_n\) 的生成函数的显式公式！求出 \(b_n\) 就只是计算问题了。用部分分式（partial fractions），我们求得 \[B(x)=\frac{(1-x)(1-2x)}{(1-2x)(1-x)-2x^2}=\frac{(1-x)(1-2x)}{1-3x}\] \[=\frac{2}{9}\cdot\frac{1}{1-3x}-\frac{6x-7}{9}\] \[=\frac{2}{9}\left(\sum_{n\ge 0}3^nx^n\right)-\frac{2}{3}x+\frac{7}{9}\] \[=1+2\sum_{n\ge 2}3^{\,n-2}x^n.\] 也就是说，如果论文有 \(n\) 页且 \(n\ge 2\)，那么把它的页面排成若干章的方案数为 \[b_n=2\cdot 3^{\,n-2}.\]

分步：从无穷和到 \(1/(1-A)\) 再到闭式
  1. 几何级数求和：\(\sum_{n\ge 0}A^n=1+A+A^2+\cdots=\dfrac{1}{1-A}\)，这与数的等比级数 \(\sum r^n=\frac{1}{1-r}\) 形式完全一致，只是把公比换成了幂级数 \(A(x)\)。
  2. 代入 \(A(x)\)：把 (3.31) 的 \(A(x)=\dfrac{2x^2}{(1-2x)(1-x)}\) 代入，分子分母同乘 \((1-2x)(1-x)\)，分母变成 \((1-2x)(1-x)-2x^2\)。
  3. 化简分母：\((1-2x)(1-x)=1-3x+2x^2\)，减去 \(2x^2\) 得 \(1-3x\)。于是 \(B(x)=\dfrac{1-3x+2x^2}{1-3x}\)。
  4. 提取闭式系数：作多项式除法 / 部分分式，得到 \(\dfrac{2}{9}\cdot\dfrac{1}{1-3x}+\dfrac{7}{9}-\dfrac{2}{3}x\)，再展开 \(\dfrac{1}{1-3x}=\sum 3^nx^n\)。
  5. 核对低次项：常数项 \(\frac{2}{9}+\frac{7}{9}=1=b_0\)；\(x^1\) 系数 \(\frac{2}{9}\cdot 3-\frac{2}{3}=\frac{2}{3}-\frac{2}{3}=0=b_1\)（一页论文无法既含正文又含插图，符合直觉）；\(n\ge 2\) 时系数为 \(\frac{2}{9}\cdot 3^n=2\cdot 3^{n-2}\)。♦
例（小数字验证 \(b_n=2\cdot 3^{n-2}\)） 取 \(n=2\)：公式给 \(b_2=2\cdot 3^0=2\)。直接数：两页只能是一章（TI 或 IT），恰好 \(2\) 种。取 \(n=3\)：公式给 \(b_3=2\cdot 3^1=6\)。直接数：一章三页有 \(6\) 种（见前例），分成两章时每章至少 \(2\) 页共需 \(\ge 4\) 页，做不到，所以 \(b_3=6\)。两处都吻合。

这是一个非常漂亮而紧凑的 \(b_n\) 公式。我们在习题 20 中请读者寻找一个不使用生成函数的证明。

对某个公式而言，存在一个不用生成函数的证明，并不会降低另一个使用生成函数的证明的价值。常常出现这样的情况（正如习题 20）：一个组合证明只是验证公式的正确性，而生成函数证明则把它推导出来。换言之，对于组合证明，我们可能需要事先知道公式；而对于生成函数证明，则不需要。

上面这段计算的新颖之处在于：我们把幂级数 \(A(x)\) 代入到了幂级数 \(1/(1-x)\) 的 \(x\) 处。也就是说，我们对生成函数作了复合（composition）。让我们把这一概念形式化。

定义 3.24 设 \(F(x)=\sum_{n=0}^{\infty}f_nx^n\) 为形式幂级数，又设 \(A(x)\) 为常数项为 0 的形式幂级数。则这两个幂级数的复合是幂级数 \[F(A(x))=\sum_{n=0}^{\infty}f_nA^n(x),\] 其中我们约定 \(A^0(x)=1\)。

注意，这是一个有意义的定义，因为 \(F(A(x))\) 中 \(x^n\) 的系数对每个 \(n\) 都是有限的。的确，\(A^m(x)\) 中最小的指数至少是 \(m\)（因 \(A(x)\) 常数项为 0），所以若 \(m>n\)，则 \(A^m(x)\) 没有 \(x^n\) 项。于是 \([x^n]F(A(x))\) 是有限多个有限项之和。

为什么要求 \(A(x)\) 常数项为 0若 \(A(x)\) 含有非零常数项 \(a_0\)，那么 \(A^0,A^1,A^2,\dots\) 每一个都会给出常数项贡献（\(a_0^0,a_0^1,a_0^2,\dots\)），于是 \([x^0]F(A(x))=\sum f_n a_0^n\) 变成无穷多个数相加，可能根本不收敛——复合就失去意义。要求 \(a_0=0\) 正是为了让每个 \(x^n\) 的系数都只由有限项决定。

既然我们已把复合形式幂级数的技术形式化，便可把前一个例子背后的核心思想加以推广。

定理 3.25 设 \(a_k\) 是在一个 \(k\) 元集合上执行某项任务的方案数，且 \(a_0=0\)，并设 \(A(x)=\sum_{k\ge 0}a_kx^k\)。设 \(b_n\) 是把区间 \([n]\) 分割成任意多个互不相交的非空子区间、再在每个子区间上执行由数列 \(a_i\) 计数的那项任务的方案数。令 \(b_0=1\)，\(B(x)=\sum_{n\ge 0}b_nx^n\)。则 \[B(x)=\frac{1}{1-A(x)}.\]
证明. 由乘积公式，把 \([n]\) 分成 \(k\) 个非空区间、再在每个区间上执行由 \(A(x)\) 计数的任务，其方案数由生成函数 \(A^k(x)\) 给出。
这里有一个细微之处。乘积公式并不要求我们把 \([n]\) 分成的区间是非空的。然而，即便我们在此处要求非空，也并未“作弊”，因为反正 \(a_0=0\)。也就是说，形式幂级数 \(\sum_{k\ge 0}a_kx^k\) 与 \(\sum_{k\ge 1}a_kx^k\) 是相同的。另一方面，对当前问题我们必须要求区间非空，否则就会有无穷多种把 \([n]\) 分成不相交区间的方式（只要不断添加空区间即可）。这是要求 \(a_0=0\) 至关重要的一个原因。
对所有 \(k\) 求和，我们得到：若对可能性的数目没有限制，则把 \([n]\) 分成不相交非空子区间、再在每个区间上执行原任务的方案数由幂级数 \[\sum_{k\ge 0}A^k(x)=\frac{1}{1-A(x)}=B(x)\] 计数。这里，由于 \(a_0=0\)，左边是一个良定义的和。这显示了要求 \(a_0=0\) 的另一个原因。♦
把 \([n]\)（这里 \(n=7\)）切成非空子区间，再在每段上做任务，权重相乘 1 2 3 4 5 6 7 \(a_2\) \(a_2\) \(a_3\) 此切法贡献 \(a_2\,a_2\,a_3\)；对所有切法、所有段数 \(k\) 求和即 \(\sum_k A^k(x)=\frac1{1-A(x)}\)
把长度 \(n\) 切成 \(k\) 段：每段贡献 \(A(x)\)，\(k\) 段相乘得 \(A^k(x)\)；段数 \(k\) 从 0 到任意，全部加起来就是等比级数之和 \(1/(1-A(x))\)。
例 3.26 今年秋季，美国国会将有 \(n\) 个工作日，分成若干（数目未定）个会期。在每个会期内，有一天被指定为全体会议日，其余各天（若还有剩余的话）各自被指定为委员会工作日或小组委员会工作日。求国会安排其会季的方案数 \(b_n\) 的显式公式。

解. 这正是定理 3.25 适用的情形，其中“安排一个会期”是第一项任务。设 \(a_n\) 为安排一个会期的方案数。一个 \(n\) 天的会期：先从 \(n\) 天中挑出 \(1\) 天作全体会议日（\(n\) 种），其余 \(n-1\) 天每天二选一（委员会 / 小组委员会，\(2^{n-1}\) 种），故 \(a_n=n\cdot 2^{n-1}\)。因此 \[A(x)=\sum_{n\ge 0}a_nx^n=\sum_{n\ge 0}n\cdot 2^{n-1}x^n=\frac{x}{(1-2x)^2}.\] 最后一步可由恒等式 \(\sum_{n\ge 0}nx^{n-1}=1/(1-x)^2\) 得到，该式我们在叙述公式 (3.4) 之后已证。

因此，若 \(b_n\) 为执行这个复合任务（把秋季分成会期，再为每个工作日指定工作类型）的方案数，且 \(B(x)=\sum_{n\ge 0}b_nx^n\)，则由定理 3.25， \[B(x)=\frac{1}{1-A(x)}=\frac{1}{1-\dfrac{x}{(1-2x)^2}}\] \[=\frac{(1-2x)^2}{(1-2x)^2-x}=1+\frac{x}{(1-2x)^2-x}\] \[=1+\frac{x}{4x^2-5x+1}=1+\frac{1}{3}\cdot\frac{1}{1-4x}-\frac{1}{3}\cdot\frac{1}{1-x}\] \[=1+\frac{1}{3}\sum_{n\ge 0}4^nx^n-\frac{1}{3}\sum_{n\ge 0}x^n=1+\sum_{n\ge 0}\frac{4^n-1}{3}x^n.\] 于是，安排秋季立法会季的方案数为 \(b_n=(4^n-1)/3\)，对 \(n\ge 1\) 成立。♦

分步：例 3.26 的化简
  1. 定第一任务：一个会期 \(m\) 天，选 1 天作全体会议（\(m\) 种）× 其余每天二选一（\(2^{m-1}\) 种）\(=m\cdot 2^{m-1}\)，得 \(A(x)=x/(1-2x)^2\)。
  2. 套定理 3.25：会期数任意，故 \(B(x)=1/(1-A(x))\)。
  3. 通分：分母 \((1-2x)^2-x=1-4x+4x^2-x=4x^2-5x+1=(1-x)(1-4x)\)。
  4. 部分分式：\(\dfrac{x}{(1-x)(1-4x)}=\dfrac{1/3}{1-4x}-\dfrac{1/3}{1-x}\)，展开后 \(x^n\) 系数为 \(\frac{1}{3}(4^n-1)\)。♦
例（验证 \(b_n=(4^n-1)/3\)） \(n=1\)：\((4-1)/3=1\)。一天只能成一个会期，那天必是全体会议日，确实 \(1\) 种。\(n=2\)：\((16-1)/3=5\)。直接数：分成两个一天会期 \(1\) 种；合成一个两天会期时选 1 天作全体会议（\(2\) 种）×另一天二选一（\(2\) 种）\(=4\) 种；共 \(1+4=5\) 种。吻合。

既然读者现在已知道 \(b_n\) 的公式，我们就在补充习题 19 中请读者寻找一个不用生成函数的归纳证明。

例 3.27 设 \(f_n\) 为把 \(n\) 写成各部分为 1 或 2 的合成（composition）的数目。令 \(f_0=1\)。求生成函数 \(F(x)=\sum_{n\ge 0}f_nx^n\) 的闭式。

解. 我们把 \([n]\) 切成若干非空区间，然后把得到的每个区间“辨认”为长度为 1 或长度为 2 的区间。若给定区间恰好是长度 1 或 2，我们能以一种方式做到；否则以零种方式。这表明 \(A(x)=x+x^2\)，因此由定理 3.25， \[F(x)=\frac{1}{1-x-x^2}=1+x+2x^2+3x^3+5x^4+\cdots.\] ♦

数 \(f_n\) 称为斐波那契数（Fibonacci numbers）。请读者证明它们满足递推关系 \(f_n=f_{n-1}+f_{n-2}\)，对 \(n\ge 2\) 成立。

把长度 \(n=3\) 的条用“1 格砖”和“2 格砖”铺满，共 \(f_3=3\) 种 2 + 1 2 1 1 + 2 1 2 1 + 1 + 1 1 1 1 每种铺法对应把 \([3]\) 切成长度只取 1 或 2 的区间；段权重 \(A(x)=x+x^2\) 递推 \(f_n=f_{n-1}+f_{n-2}\)：看最后一块砖是 1 格还是 2 格 \(f_0,f_1,f_2,f_3,f_4,\dots = 1,1,2,3,5,\dots\)
把 \(n\) 合成为 1 与 2，等价于用长 1、长 2 两种砖铺满长度 \(n\) 的条。\(A(x)=x+x^2\)，代入 \(1/(1-A)\) 得斐波那契生成函数。

定理 3.25 可以按如下方式推广。

定理 3.28（普通生成函数的复合公式） 设 \(a_n\) 为在一个 \(n\) 元集合上执行某项任务的方案数，且令 \(a_0=0\)。设 \(b_n\) 为在一个 \(n\) 元集合上执行另一项任务的方案数，且 \(b_0=1\)。最后，设 \(c_n\) 为把 \([n]\) 分成非空区间、然后在每个区间上执行第一项任务、再在这些区间所构成的集合上执行第二项任务的方案数。那么，若 \(A(x)\)、\(B(x)\)、\(C(x)\) 分别记这三个数列的普通生成函数，则等式 \[\tag{3.33}C(x)=B(A(x))\] 成立。
证明. 若我们把 \([n]\) 分成 \(k\) 个非空区间，则由乘积公式，在每个区间上执行第一项任务的方案数由生成函数 \(A(x)^k\) 给出。然后，在这 \(k\) 个给定区间所构成的集合上执行第二项任务有 \(b_k\) 种方式，于是得到生成函数 \(b_kA(x)^k\)。对所有 \(k\) 求和，我们得到 \[C(x)=\sum_{k\ge 0}b_kA(x)^k=B(A(x)).\] ♦
看懂复合公式的“两层任务”定理 3.25 是定理 3.28 的特例：取第二项任务为“什么都不做”，即对任意 \(k\) 个区间只有 \(1\) 种方式（\(b_k=1\)）。此时 \(B(x)=\sum_{k\ge 0}x^k=\frac{1}{1-x}\)，代入得 \(C(x)=B(A(x))=\frac{1}{1-A(x)}\)，正是定理 3.25。一般情形里，内层 \(A\) 管“每一段内部怎么做”，外层 \(B\) 管“把这些段当作 \(k\) 个对象再怎么做”。
复合公式 \(C(x)=B(A(x))\)：内层 \(A\) 作用于每段，外层 \(B\) 作用于“段的集合” 第一任务 \(A\) 第一任务 \(A\) \(A\) 把 3 段看成 3 个对象，再做第二任务 \(B\)（权重 \(b_3\)） \(\displaystyle C(x)=\sum_{k\ge0}b_k\,A(x)^k\) \(=B(A(x))\)
分两层：白格 \([n]\) 先切成段（绿框，每段权重来自 \(A\)），再把这些段当成 \(k\) 个蓝点组成的新对象做外层任务（权重 \(b_k\)）。求和即 \(B(A(x))\)。
例 3.29 一位足球教练让她的 \(n\) 名队员站成一排。然后她在若干处把这一排断开，形成若干非空的小组，并在每个小组里选一名组长。最后，她从这些小组中选出一个去执行某项特定任务。求她可以这样安排的方案数 \(c_n\) 的生成函数。

解. 显然，在一个 \(m\) 名队员的小组里选组长有 \(m\) 种方式，故 \(a_m=m\)（\(m>0\)）。类似地，从 \(k\) 个小组中选一个有 \(k\) 种方式，故 \(b_k=k\)（\(k\ge 1\)），并取 \(b_0=1\)。因此 \[A(x)=\sum_{m\ge 1}mx^m=\frac{x}{(1-x)^2},\qquad B(x)=1+\sum_{k\ge 1}kx^k=1+\frac{x}{(1-x)^2}.\] 于是由定理 3.28， \[C(x)=B(A(x))=1+\frac{A(x)}{\bigl(1-A(x)\bigr)^2}.\] 把 \(A(x)=\dfrac{x}{(1-x)^2}\) 代入：先算 \(1-A(x)=\dfrac{(1-x)^2-x}{(1-x)^2}=\dfrac{1-3x+x^2}{(1-x)^2}\)，故 \[C(x)=1+\frac{\dfrac{x}{(1-x)^2}}{\left(\dfrac{1-3x+x^2}{(1-x)^2}\right)^2}=1+\frac{x(1-x)^2}{(1-3x+x^2)^2}.\] ♦

分步：例 3.29 为什么这样套公式
  1. 认出两层任务：第一任务＝“在一个小组内选组长”，作用于每段；第二任务＝“从所有小组里挑一个”，作用于“小组的集合”。这正是定理 3.28 的结构。
  2. 写内层 \(A\)：\(m\) 人小组选组长有 \(m\) 种，\(a_m=m\)；用 \(\sum_{m\ge1}mx^m=\dfrac{x}{(1-x)^2}\)（注意 \(a_0=0\)，符合定理要求）。
  3. 写外层 \(B\)：\(k\) 个小组挑一个有 \(k\) 种，\(b_k=k\)（\(k\ge1\)），且约定 \(b_0=1\)，得 \(B(x)=1+\dfrac{x}{(1-x)^2}\)。
  4. 复合：把 \(A(x)\) 代入 \(B\) 的 \(x\)，即 \(C(x)=B(A(x))\)，化简得到 \(1+\dfrac{x(1-x)^2}{(1-3x+x^2)^2}\)。♦
\(n\) 名队员断成小组（绿框），每组选组长（★），再挑一个小组（金框）执行任务 ★ ★ ★ ← 被选中执行任务的小组 每组内选组长＝内层 \(a_m=m\)；从 \(k\) 组挑一组＝外层 \(b_k=k\) 合起来 \(C(x)=B(A(x))=1+\dfrac{x(1-x)^2}{(1-3x+x^2)^2}\)
★ 为组长，金色虚框为被选中执行任务的小组。两层选择分别由 \(A\)（组内选组长）与 \(B\)（组间选一组）刻画，复合即得 \(C\)。

返回 全书目录