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

3.3　生成函数的乘积Products of generating functions

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

本节我们处理这样一类问题：在这些问题中，生成函数（generating function）比上一节求解递推关系时还要更加不可或缺。

本节目标上一节我们用单个生成函数解递推。本节要解决的核心问题是：当一个计数任务可以切成两段（或多段）、每段各做一件不同的事时，整体的生成函数恰好等于各段生成函数的乘积。把这条“乘积法则”讲透，就能机械地解出许多原本很难猜出公式的难题，并自然地通向整数的拆分（partition）。

3.3.1　普通生成函数

例 3.12 一支检修队在路边给 \(n\) 根电线杆刷漆，从路的一端开始，一根接一根地往前刷。每刷一根杆，他们从红、蓝、绿三种颜色中随机选一种。某个时刻他们发现快下班了，今天没法再刷更多杆。为了庆祝一天工作结束，他们从剩下没刷的杆里随机挑一根，在上面用红色画一张笑脸。当这支愉快的检修队离开后，这条路上的电线杆可以呈现出多少种不同的样子？

本例与前几节问题的区别在于：工人们这里按两条不同的规则行事——在意识到时间到之前用一条规则，之后用另一条规则。而且我们并不知道这个转变发生在什么时候，也就是说，刷了多少根杆之后他们才挑一根没刷的杆来画笑脸。我们不妨假设这件事发生在已经刷了 \(i\) 根杆之后。这意味着前 \(i\) 根杆有 \(3^i\) 种刷法；接着检修队从剩下的杆里挑一根，有 \(n-i\) 种挑法。于是根据乘积原理（product principle），这条街可以有 \(3^i(n-i)\) 种不同样子。参见图 3.2。

记 \(a_n\) 为检修队离开后电线杆可能呈现的样子数。对 \(i\in[0,n]\) 使用加法原理，上一段的论证表明 \[\tag{3.16}a_n=\sum_{i=0}^{n}3^i(n-i).\] 取自然的初始条件 \(a_0=0\)（没有杆，就没有杆可以画笑脸，检修队压根不会来），由此算出最初几个值 \(a_1=1\) 与 \(a_2=5\)。

图 3.2　乘积原理在起作用：固定分界点 \(i\)，前段 \(3^i\) 种 × 后段 \((n-i)\) 种，再对所有 \(i\) 求和。

现在我们想为 \(a_n\) 找一个显式公式。为此注意：(3.16) 的右边非常像两个生成函数之乘积中 \(x^n\) 的系数。为把这一观察说得更精确，令 \(A(x)=\sum_{n\ge0}a_nx^n\)，并令 \[B(x)=\sum_{n\ge0}3^nx^n=\frac{1}{1-3x},\qquad D(x)=\sum_{n\ge0}nx^n=\frac{x}{(1-x)^2}.\] 正如所说，关键的观察是 \[\tag{3.17}A(x)=B(x)D(x).\] 的确，右边 \(x^n\) 的系数是 \(\sum_{i=0}^{n}3^i(n-i)\)，而由 (3.16) 它又正好等于 \(a_n\)。

因此我们可以把 \(a_n\) 求作 \([x^n]A(x)=[x^n]B(x)D(x)\)。幸运的是 \(B(x)\) 与 \(D(x)\) 我们都已显式知道，于是 (3.17) 给出 \[A(x)=B(x)D(x)=\frac{1}{1-3x}\cdot\frac{x}{(1-x)^2}=\frac{x}{(1-3x)(1-x)^2}.\] 为得到 \(A(x)\) 的幂级数形式，我们像在微积分里学过的那样把最后这个表达式分解成部分分式（partial fractions）之和。也就是说，我们要找实数 \(P,Q,R\)，使得 \[A(x)=\frac{x}{(1-3x)(1-x)^2}=\frac{P}{1-3x}+\frac{Q}{1-x}+\frac{R}{(1-x)^2}.\] 例行的计算给出 \(P=3/4,\;Q=-1/4,\;R=-1/2\)。于是 \[\begin{aligned}A(x)&=\frac34\cdot\frac{1}{1-3x}-\frac14\cdot\frac{1}{1-x}-\frac12\cdot\frac{1}{(1-x)^2}\\&=\sum_{n\ge0}\frac34\,3^nx^n-\sum_{n\ge0}\frac14x^n-\sum_{n\ge0}\frac12(n+1)x^n\\&=\sum_{n\ge0}\frac{3^{n+1}-1-2(n+1)}{4}\,x^n.\end{aligned}\] 因此我们得到 \(a_n=\dfrac{3^{n+1}-1-2(n+1)}{4}\)。请读者自行验证这个公式确实正确。

数字验证把刚得到的公式代入小 \(n\) 检验：

\(n=1\)：\(a_1=\dfrac{3^{2}-1-2\cdot2}{4}=\dfrac{9-1-4}{4}=\dfrac44=1\)。
\(n=2\)：\(a_2=\dfrac{3^{3}-1-2\cdot3}{4}=\dfrac{27-1-6}{4}=\dfrac{20}{4}=5\)。
两者都与上面由 (3.16) 直接数出的 \(a_1=1,\;a_2=5\) 吻合。♦

把方法拆成三步这就是本节的标准套路：

切两段、设系数列。把任务在分界点 \(i\) 处切成“前段”和“后段”，分别数清楚每段的方案数，写成卷积式 \(a_n=\sum_{i}f_i g_{n-i}\)。
认出是乘积。卷积正是两个普通生成函数相乘后 \(x^n\) 的系数，故 \(A(x)=B(x)D(x)\)。
部分分式回展开。把闭形式拆成 \(\frac{1}{1-cx}\)、\(\frac{1}{(1-x)^2}\) 这类已知展开的分式，逐项读出系数。

上一例最重要的特征是：检修队先做一件事，到某一刻又改做另一件事。把区间 \([1,n]\) 切成两段、再在每段上考虑不同结构，这个想法在许多问题中都会出现。幸运的是，对这些情形，两段计数的普通生成函数之乘积是一件非常有力的工具。

我们再看一个用同样思路就能解决的类似问题。

例 3.13 一名学生为期末考试期制订复习计划。她把这段时间分成两部分。在第一部分，她每一天要么复习物理，要么复习抽象代数；只有一天例外，那天她上午只复习当天所选的科目，下午放松。在第二部分，她把所有天都用于组合数学，只有两天例外，那两天她休息（这两天不必相邻）。若考试期共 \(n\) 天，这名学生有多少种不同的复习计划？

解：同样假设第一部分占 \(k\) 天，第二部分占 \(n-k\) 天。这意味着学生在第一部分有 \(k2^k\) 种方案（每天二选一共 \(2^k\) 种，再从 \(k\) 天里选出那个“下午放松”的特殊日有 \(k\) 种），在第二部分有 \(\binom{n-k}{2}\) 种方案（从 \(n-k\) 天里选两天休息）。于是由乘积原理，对固定的 \(k\)，学生有 \(k2^k\binom{n-k}{2}\) 种方案。对所有允许的 \(k\) 求和（即 \(1\le k\le n-2\)，否则天数不够安排休息），可见她总共有 \[\sum_{k=1}^{n-2}k2^k\binom{n-k}{2}\] 种方案。沿用上一例的思路，考虑各部分方案数的生成函数，即 \[B(x)=\sum_{n\ge1}n2^nx^n=\frac{2x}{(1-2x)^2},\qquad D(x)=\sum_{n\ge2}\binom{n}{2}x^n=\frac{x^2}{(1-x)^3}.\] 令 \(A(x)=B(x)D(x)\)。与上一例类似，学生的全部方案数，即 \(\sum_{k=1}^{n-2}k2^k\binom{n-k}{2}\)，正好是 \([x^n]A(x)\)。所以我们只需求这个系数。由上面两式， \[A(x)=B(x)D(x)=\frac{2x}{(1-2x)^2}\cdot\frac{x^2}{(1-x)^3}=\frac{2x^3}{(1-2x)^2(1-x)^3}.\] 把这个生成函数化成部分分式形式是一件繁琐的活，不过有各种软件包可以替我们完成。无论怎样，我们得到 \[\begin{aligned}A(x)&=\frac{2}{(1-x)^3}+\frac{2}{(1-x)^2}+\frac{6}{1-x}+\frac{2}{(1-2x)^2}-\frac{12}{1-2x}\\&=\sum_{n\ge0}(n+2)(n+1)x^n+\sum_{n\ge0}2(n+1)x^n+\sum_{n\ge0}6x^n\\&\qquad+\sum_{n\ge0}(n+1)2^{n+1}x^n-\sum_{n\ge0}12\cdot2^nx^n\\&=\sum_{n\ge0}\bigl(2^{n+1}(n-5)+(n+1)(n+4)+6\bigr)x^n.\end{aligned}\] 因此学生拥有的方案数是 \(a_n=2^{n+1}(n-5)+(n+1)(n+4)+6\)。请读者自行验证这确实是正确的公式，特别地 \(a_1=a_2=0\)，\(a_3=2\)。♦

逐项核对系数合并看末行那一步“五项合一”是怎么来的：

\(\dfrac{2}{(1-x)^3}\to 2\binom{n+2}{2}=(n+2)(n+1)\)；\(\dfrac{2}{(1-x)^2}\to 2(n+1)\)；\(\dfrac{6}{1-x}\to 6\)。三者合计 \((n+2)(n+1)+2(n+1)+6=n^2+5n+10=(n+1)(n+4)+6\)。
\(\dfrac{2}{(1-2x)^2}\to 2(n+1)2^n=(n+1)2^{n+1}\)；\(-\dfrac{12}{1-2x}\to -12\cdot2^n=-6\cdot2^{n+1}\)。两者合计 \((n+1-6)2^{n+1}=(n-5)2^{n+1}\)。
合起来即 \(2^{n+1}(n-5)+(n+1)(n+4)+6\)。代 \(n=3\)：\(2^4(-2)+4\cdot7+6=-32+34=2\)，与直接枚举一致。♦

我们的结果很好地体现了这套方法的威力。毕竟公式 \(a_n=2^{n+1}(n-5)+(n+1)(n+4)+6\) 是相当难猜到的，要用组合方法去证明它也相当困难——对公式中的 \(2^{n+1}(n-5)\)、\((n+1)(n+4)\) 或 \(6\) 这几项似乎都没有什么简单的解释。然而我们的生成函数方法运转得相当机械，无需任何灵光一现的妙想。

我们已经看了同一计数原理的两个例子，现在来表述适用于这类情形的一般定理。

定理 3.14（乘积公式 Product formula）设 \(f_n\) 是在集合 \([n]\) 上完成某一任务的方案数，\(g_n\) 是在 \([n]\) 上完成另一任务的方案数。设 \(F(x)\) 与 \(G(x)\) 分别是数列 \(\{f_n\}_{n\ge0}\) 与 \(\{g_n\}_{n\ge0}\) 的普通生成函数。
设 \(h_n\) 是这样的方案数：把集合 \([n]\) 切成两个区间 \(\{1,2,\cdots,i\}\) 与 \(\{i+1,i+2,\cdots,n\}\)，然后在第一个区间上完成第一项任务、在第二个区间上完成第二项任务。设 \(H(x)\) 是数列 \(\{h_n\}_{n\ge0}\) 的普通生成函数。则 \[\tag{3.18}H(x)=F(x)G(x).\]

证明. 数 \(h_n\) 的定义给出递推关系 \[h_n=\sum_{i=0}^{n}f_i\,g_{n-i}.\] 的确，对任一固定的 \(i\)，第一项任务有 \(f_i\) 种做法，第二项任务有 \(g_{n-i}\) 种做法，于是两者都做有 \(f_i g_{n-i}\) 种做法。对所有 \(i\) 求和，由加法原理即得此式。
现在注意 \(h_n\) 是 \(H(x)\) 中 \(x^n\) 的系数，而 \(\sum_{i=0}^{n}f_i g_{n-i}\) 是 \(F(x)G(x)\) 中 \(x^n\) 的系数。既然对所有 \(n\) 这些系数都相等，幂级数 \(H(x)\) 与 \(F(x)G(x)\) 也相等。♦

为什么“相乘”就对应“切两段”把两个幂级数相乘 \(\bigl(\sum f_i x^i\bigr)\bigl(\sum g_j x^j\bigr)\) 展开，凡是指数加起来等于 \(n\)（即 \(i+j=n\)）的项才贡献到 \(x^n\)：

每一行是一种切法 \(i\)：左红块（前段方案 \(f_i\)）配右蓝块（后段方案 \(g_{n-i}\)）。把所有行加起来，正是乘积里 \(x^n\) 的系数。

注意例 3.12 正是乘积公式的一次直接应用。的确，要在前 \(i\) 根杆上完成的第一项任务是把每根杆涂成红、蓝或绿，对应生成函数 \(F(x)=\sum_{n\ge0}3^nx^n=\frac{1}{1-3x}\)；要在后 \(n-i\) 根杆上完成的第二项任务是挑出一根杆，对应生成函数 \(G(x)=\sum_{n\ge0}nx^n=\frac{x}{(1-x)^2}\)。正如我们现在无需进一步解释就明白的，合并任务的生成函数于是就是 \(F(x)G(x)=\frac{x}{(1-x)^2(1-3x)}\)。

在进攻更难的问题之前，我们再看乘积公式的一个简单应用。

例 3.15 一本组合数学教材的某一节含有 \(n\) 道习题。一位尽责的教授使用这本书，她既想让学生练习本节讨论的基本方法，又想为对更难问题感兴趣的学生提供挑战。于是她会把前 \(2i\) 道题布置为家庭作业（对某个整数 \(i\ge2\)），并把剩下习题中的某一道作为附加题。她有多少种不同的布置方式？

解：用乘积公式的语言来说，教授把集合 \([n]\) 切成两个区间，然后把第一个区间里的所有题都布置成作业（如果这个区间的长度是偶数且至少为 4，她只有一种做法；否则有零种做法），再从第二个区间里挑一道题（如果该区间长度为 \(j\)，则有 \(j\) 种做法）。因此，仍用乘积公式的记号， \[F(x)=x^4+x^6+\cdots=\sum_{i\ge2}x^{2i}=x^4\sum_{i\ge0}(x^2)^i=\frac{x^4}{1-x^2},\] \[G(x)=\sum_{j\ge0}jx^j=\frac{x}{(1-x)^2}.\] 由乘积公式， \[H(x)=F(x)G(x)=\frac{x^5}{(1-x^2)(1-x)^2}.\] 虽然还有工作要做，但已能看出我们走在正确的轨道上：因为 \(H(x)\) 不会出现指数小于 5 的项；的确，如果这一节的习题少于 5 道，教授就无法做出她的选择。

为求 \([x^n]H(x)\)，只需求 \([x^{n-5}]\dfrac{1}{(1-x^2)(1-x)^2}\)。这是一个例行但繁琐的计算，也可由计算机完成（下一例会再多谈一点）。无论怎样，我们得到 \[\frac{H(x)}{x^5}=\frac{1}{2(1-x)^3}+\frac{1}{4(1-x)^2}+\frac{1}{8(1-x)}+\frac{1}{8(1+x)}.\] 利用习题 1 中证明的恒等式（即 \(\frac{1}{(1-x)^{k+1}}=\sum_{n\ge0}\binom{n+k}{k}x^n\)），这给出 \[\begin{aligned}\frac{H(x)}{x^5}&=\frac12\sum_{n\ge0}\binom{n+2}{2}x^n+\frac14\sum_{n\ge0}(n+1)x^n\\&\qquad+\frac18\sum_{n\ge0}x^n+\frac18\sum_{n\ge0}(-1)^nx^n\\&=\sum_{n\ge0}\frac{4\binom{n+2}{2}+2(n+1)+1+(-1)^n}{8}\,x^n.\end{aligned}\] 于是教授拥有的方案数 \(h_n\)，就是上式中 \(x^{n-5}\) 的系数，即 \[h_n=\frac{4\binom{n-3}{2}+2(n-4)+1+(-1)^{n-5}}{8}.\] ♦

现在让我们在一个更难的经典问题上练习使用乘积公式。一旦看到这个问题的数值解，它会让我们想起以前见过的东西。

例 3.16 上周末两支足球队踢了一场激动人心的比赛，最终打成平局，每队各进 \(n\) 球。整场比赛里，主队常常领先、客队从未领先，因此屡屡看似主队将赢。这 \(2n\) 个进球可以有多少种不同的发生顺序？

解：为更好地理解问题，先对小 \(n\) 计算上述问题的答案 \(h_n\)。用 \(A\) 记主队进的一个球，用 \(B\) 记客队进的一个球。若 \(n=1\)，进球顺序只能是 \(AB\)（因主队从不落后）。若 \(n=2\)，有两种可能，即 \(AABB\) 与 \(ABAB\)。若 \(n=3\)，有五种可能，即 \(AAABBB,\,AABABB,\,AABBAB,\,ABAABB,\,ABABAB\)。所以 \(h_1=1,\,h_2=2,\,h_3=5\)。又注意 \(h_0=1\)，因为“两队都不进球”有唯一一种方式（就是不进球）。令 \(H(x)=\sum_{n\ge0}h_nx^n\)。

使这个问题比之前的问题、或比第 1 章某些标准计数问题更难的，是“主队从不落后”这个条件。没有这个条件，方案数将是 \(\binom{2n}{n}\)，因为我们只需数由 \(n\) 个 \(A\) 与 \(n\) 个 \(B\) 组成的长为 \(2n\) 的词。现在我们还附加了一个条件：词的任何前缀中 \(B\) 的个数都不能多于 \(A\) 的个数。

我们想用乘积公式来计算 \(H(x)\)。难点在于弄清楚如何把 \(H(x)\) 分解成两个生成函数之积。乘积公式里所说的“两项任务”分别是什么呢？

假设比赛没有以 0–0 的无进球平局收场。把客队首次把比分扳平的那一刻称为比赛的关键时刻（critical moment）。既然比赛最终打平，我们可以确定一定存在一个关键时刻。设在关键时刻比分是 \(i\) 比 \(i\)。

现在我们把比赛分成两部分：关键时刻之前的部分，与关键时刻之后的部分。

首先，我们断言关键时刻之后比赛有 \(h_{n-i}\) 种完成方式。的确，只要把关键时刻之前进的所有球都抹去，那么剩下的比赛必须以双方各 \(n-i\) 球的平局结束，且主队从不落后。因此关键时刻之后比赛的完成方式数由生成函数 \[G(x)=H(x)\] 来枚举。

弄清楚关键时刻之前进球能有多少种方式则更有意思一些。注意，说这种方式数是 \(h_i\) 是不对的，因为客队在关键时刻之前从未扳平，而 \(h_i\) 并未把这一点考虑进去。相反，请观察以下事实：在关键时刻之前，主队必定进了第一个球，客队必定进了最后一个球。把这第一个球与最后一个球之间（但不含这两个球）的时段称为比赛的中段（middle period）。于是全场的第一个球在中段之前，关键时刻在中段之后。（足球比赛其实没有“中段”，只有上下两个半场，但这无关紧要。）那么中段以双方各 \(i-1\) 球的平局结束，并且就中段内进的球而言，主队从不落后。的确，说“就中段内进的球而言主队从不落后”，等价于说“就整场而言客队在关键时刻之前没有扳平比分”——这是因为中段开始时主队领先。因此，以 \(i\) 比 \(i\) 平局到达关键时刻的方式数，等于以 \(i-1\) 比 \(i-1\) 平局结束的中段的数目，也就是 \(h_{i-1}\)。

于是，若关键时刻在 \(i\) 比 \(i\) 时到来，则从比赛开始走到关键时刻有 \(h_{i-1}\) 种方式。因此，比赛中关键时刻之前那部分的方案数生成函数是 \[F(x)=\sum_{i\ge1}h_{i-1}x^i=xH(x).\]

现在我们准备好使用乘积公式了。别忘了我们的分解只在 \(n>0\) 时有效（若根本没有进球，就没有关键时刻）。数列 \(h_1,h_2,\cdots\) 的生成函数是 \(H(x)-1\)，因为 \(h_0=1\)。因此乘积公式给出 \[\tag{3.19}H(x)-1=xH(x)^2.\] 这是关于 \(H(x)\) 的一个二次方程。解之，得 \[\tag{3.20}H(x)=\frac{1-\sqrt{1-4x}}{2x}.\]

为什么取“减号”这一支我们希望机敏的读者会因我们没有解释二次方程 (3.19) 的解中 \(\pm\sqrt{1-4x}\) 为何变成了单单的 \(-\sqrt{1-4x}\) 而感到不满。下面是我们的解释：数 \(h_n\) 当然由 \(n\) 唯一确定，因此生成函数 \(H(x)\) 也是唯一的。所以幂级数 \(\frac{1-\sqrt{1-4x}}{2x}\) 与 \(\frac{1+\sqrt{1-4x}}{2x}\) 中只有一个能等于 \(H(x)\)。要看出是哪一个，只需看 \(H(x)\) 本身：由 \(H(x)\) 的定义知 \(H(0)=h_0=1\)。另一方面，函数 \(\frac{1+\sqrt{1-4x}}{2x}\) 在 \(x=0\) 处甚至没有定义，因为此处分母为 0 而分子为 2。而函数 \(\frac{1-\sqrt{1-4x}}{2x}\) 可以延拓到 \(x=0\)，因为在该点分式的分子与分母都等于 0。用洛必达法则或别的办法容易验证 \(\lim_{x\to0}\frac{1-\sqrt{1-4x}}{2x}=1\)，所以取负号是合理的。（事实上，一旦知道正号不对，又因为 \(H(x)\) 确实存在且必为这两支之一，就立即知道负号是对的。）

为求出数 \(h_n\)，我们需要求 \([x^n]H(x)\)。为此，先用二项式定理（binomial theorem）展开 \(\sqrt{1-4x}\)。我们得到 \[\tag{3.21}(1-4x)^{1/2}=\sum_{n\ge0}\binom{1/2}{n}(-4x)^n.\] 现在需要计算 \(\binom{1/2}{n}\)。由二项式系数的定义， \[\tag{3.22}\binom{1/2}{n}=\frac{\tfrac12\cdot\tfrac{-1}{2}\cdot\tfrac{-3}{2}\cdots\tfrac{-2n+3}{2}}{n!}=(-1)^{n-1}\frac{(2n-3)!!}{2^n\,n!}.\] 把它与 (3.21) 比较，得 \[\tag{3.23}\sqrt{1-4x}=-\sum_{n\ge0}\frac{2^n(2n-3)!!}{n!}x^n=1-2\sum_{n\ge1}\frac{1}{n}\binom{2n-2}{n-1}x^n.\] 最后，把所得表达式代入 (3.20) 即得 \(H(x)\) 的幂级数形式。这给出 \[\tag{3.24}H(x)=\frac{1-\sqrt{1-4x}}{2x}=\sum_{n\ge0}\frac{1}{n+1}\binom{2n}{n}x^n.\] 因此 \(h_n=\dfrac{1}{n+1}\binom{2n}{n}\)。注意这表明数 \(h_n\) 实际上等于卡塔兰数（Catalan number）\(c_n\)，我们曾在例 1.34 之后定义过它。♦

数字核对：卡塔兰数由 \(h_n=\frac{1}{n+1}\binom{2n}{n}\) 逐个算：\(h_0=\frac11\binom00=1\)，\(h_1=\frac12\binom21=1\)，\(h_2=\frac13\binom42=\frac{6}{3}=2\)，\(h_3=\frac14\binom63=\frac{20}{4}=5\)。与前面手数的 \(1,1,2,5\) 完全一致。

注记（Remarks）：

注意 (3.19) 等价于递推关系 \[\tag{3.25}h_n=\sum_{i=0}^{n-1}h_i\,h_{n-1-i}\qquad(n\ge1),\quad h_0=1.\] 事实上，证明例 3.16 结论的另一种途径是：先证 (3.25)，再把两边同乘 \(x^n\)、对 \(n\ge1\) 求和，然后认出左边是 \(H(x)-1\)、右边是 \(xH(x)\cdot H(x)\)。
我们曾提到，本例所数的进球序列与从 \((0,0)\) 到 \((n,n)\)、永不越过对角线 \(x=y\) 的东北格点路径（northeastern lattice path）等势。事实上这两个集合之间有一个简单的双射：字母 \(A\) 对应一个向东的步，字母 \(B\) 对应一个向北的步。注意，关键时刻对应于东北格点路径首次触及对角线 \(x=y\) 的时刻。

例：序列 \(AABABB\) 对应路径东、东、北、东、北、北。整条路径不越过对角线 \(\Longleftrightarrow\) 任何前缀中 \(A\) 不少于 \(B\)（主队从不落后）。这类路径共 \(c_n\) 条。

为扩大乘积公式的适用范围，注意当我们把 \([n]\) 切成两个区间时，“二”这个数目并没有什么神奇之处。如果我们把 \([n]\) 切成三个连续区间，使它们两两不相交且并集为 \([n]\)，然后在每个区间上完成各种任务，可以类似地论证。也就是说，若 \(A(x),B(x),C(x)\) 是枚举三项任务各自方案数的生成函数，那么由乘积公式，\(A(x)B(x)\) 就是完成前两项任务的方案数生成函数；再对 \(A(x)B(x)\) 与 \(C(x)\) 应用一次乘积公式，得 \(A(x)B(x)C(x)\) 是完成全部三项任务的方案数生成函数。若任务多于三项，可同样处理。这引出一批新的应用，由下例引入。

例 3.17 求只用 1 元、2 元、5 元纸币付 \(n\) 元的方法数 \(h_n\)。使用纸币的顺序无关紧要，只有每种面额的张数才算数。

解：设 \(a_n\)（分别地 \(b_n,c_n\)）是只用 1 元（分别地只用 2 元、只用 5 元）纸币付 \(n\) 元的方法数。设 \(A(x)\)（分别地 \(B(x),C(x)\)）是对应数列的普通生成函数。则对所有 \(n\ge0\) 有 \(a_n=1\)；而 \(b_n=1\) 当 \(n\) 被 2 整除、否则 \(b_n=0\)；\(c_n=1\) 当 \(n\) 被 5 整除、否则 \(c_n=0\)。这导出生成函数 \[A(x)=\sum_{n\ge0}x^n=\frac{1}{1-x},\quad B(x)=\sum_{n\ge0}(x^2)^n=\frac{1}{1-x^2},\quad C(x)=\sum_{n\ge0}(x^5)^n=\frac{1}{1-x^5}.\] 因此，由乘积公式，数 \(h_n\) 的生成函数 \(H(x)=\sum_{n\ge0}h_nx^n\) 是 \[\tag{3.26}H(x)=A(x)B(x)C(x)=\frac{1}{(1-x)(1-x^2)(1-x^5)}.\] ♦

有几点说明需要补充。第一，你可能会问这个结果有什么用——我们并没有得到 \(h_n\) 的公式，而手算 \(\frac{1}{(1-x)(1-x^2)(1-x^5)}\) 的部分分式分解会是相当大的工作量。如前所述，标准的数学软件（如 Mathematica 或 Maple）能很轻松地替我们做这件繁琐的活。例如在 Maple 中可输入

convert(1/((1-x)*(1-x^2)*(1-x^5)), parfrac);

计算机会返回 \[\frac{x^3+2x^2+x+1}{5(x^4+x^3+x^2+x+1)}+\frac{1}{8(x+1)}-\frac{13}{40(x-1)}+\frac{1}{4(x-1)^2}-\frac{1}{10(x-1)^3}.\] 现在求 \(h_n\) 的幂级数形式就相对省力了，特别是如果我们注意到可以把中间那一项的分子和分母同乘以 \(x-1\)，把分母变成 \(5(x^5-1)\)。

如果我们只是想知道数列的前 15 个值，只需在 Maple 中输入

series(1/((1-x)*(1-x^2)*(1-x^5)), x=0, 16);

并回车。Maple 会返回 \[\begin{aligned}&1+x+2x^2+2x^3+3x^4+4x^5+5x^6+6x^7+7x^8+8x^9\\&\quad+10x^{10}+11x^{11}+13x^{12}+14x^{13}+16x^{14}+18x^{15}+O(x^{16}),\end{aligned}\] 于是对 \(n\le15\)，\(h(n)\) 就是上式中 \(x^n\) 的系数。

手验一个系数付 4 元（\(h_4=3\)）的所有方式：\(4=1+1+1+1\)；\(4=2+1+1\)；\(4=2+2\)。共 3 种，与展开式中 \(3x^4\) 的系数一致（不能用 5 元，因 \(5>4\)）。

第二点说明意义更深远：注意我们其实只是找到了把非负整数 \(n\) 拆分（partition）成等于 1、2 或 5 的部分的拆分数的生成函数。不言而喻，把结果推广到允许其他部分的情形是容易的。由于这种方法应用广泛，值得花些时间探讨 \(H(x)\) 与“\(n\) 拆成大小为 1、2、5 的部分”之间的联系。

我们已经看到 \[H(x)=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^5+x^{10}+\cdots).\] 把所有乘法都展开后，右边一个典型的被加项将形如 \(x^i\,x^{2j}\,x^{5k}=x^n\)。这意味着 \(i+2j+5k=n\)，换句话说，\(n\) 有一个分成 \(k+j+i\) 个部分的拆分，其中 \(k\) 个部分是 5、\(j\) 个部分是 2、\(i\) 个部分是 1。\(n\) 拆成允许大小的每个拆分都对应一个等于 \(x^n\) 的被加项，这再次表明 \(H(x)\) 中 \(x^n\) 的系数就是 \(n\) 拆成大小为 1、2、5 的部分的拆分数。

从每个因子里各取一项相乘：取 \(x^{2}\)（两张 1 元）·\(x^{2}\)（一张 2 元）·\(x^{0}\)（零张 5 元）= \(x^4\)，对应 \(4=1+1+2\)。每种取法 ↔ 一个拆分。

动手验证理解请你试着找出右边对应于“把 5 拆成允许部分”的那些被加项，以检验你对上例的理解。（提示：\(5=1{+}1{+}1{+}1{+}1=2{+}1{+}1{+}1=2{+}2{+}1=5\)，对应取法各是什么？）

有大量关于整数拆分的迷人定理可以用生成函数来证明。建议读者先做补充习题 9、10、11、12 热身；然后做习题 12、13、14，以得到一个关于拆分的非常有趣的恒等式；习题 27、28、29 则推广了这个恒等式。

其中一些习题会涉及无穷个无穷和之积。这对读者来说可能很陌生，因此我们在这里讨论一下这个概念。为避免记号过于繁杂，我们用一个例子来讨论，而不是在完全一般的情形下进行。

设 \(p_{\text{even}}(n)\) 为把 \(n\) 只拆成偶数部分的拆分数，并令 \(p_{\text{even}}(0)=1\)。我们断言下列等式成立： \[\tag{3.27}\sum_{n\ge0}p_{\text{even}}(n)x^n=(1+x^2+x^4+\cdots)(1+x^4+x^8+\cdots)\cdots\] \[\tag{3.28}=\prod_{i\ge1}\frac{1}{1-x^{2i}}.\]

首先，我们怎么知道右边——一个无穷个无穷和之积——是良定义（well-defined）的呢？让我们把这个问题反过来问：可能出什么问题？右边在什么时候会变得没有意义？右边是若干个和之积。我们会像处理有限和那样去计算它，即先逐项相乘（这些是有限的乘积），再把它们加起来。当我们计算诸如 \(x^2\cdot x^{10}\cdot x^{14}\) 这样的有限逐项乘积时，每一个这样的乘积都是有定义的。问题可能出现在之后，即把这些乘积相加时：如果有无穷多个这样的乘积都等于某个 \(x^k\)，那我们就没法把它们加起来了。（这里我们不会把无穷和与它的极限等同起来，即便那个极限存在。）

为什么 (3.28) 仍然良定义关键在于：固定一个指数 \(k\)，要凑出 \(x^k\)，只能从有限个因子里各取一个 \(x^{2i}\) 的正次幂、其余因子都取常数项 1——因为一旦某因子取了 \(x^{2i}\)（\(i\ge1\)），指数至少增加 2，而总指数被 \(k\) 限死。所以第 \(i\ge \lceil k/2\rceil+1\) 个因子只能取 1。于是凑成 \(x^k\) 的方式只有有限多种，相加完全合法。这恰好对应：把 \(k\) 拆成偶数部分的拆分只有有限多个，其个数正是 \(p_{\text{even}}(k)\)。

返回全书目录

3.3.1 普通生成函数

3.3.1　普通生成函数