生成函数：把计数写进代数

先说清楚：什么算一种方法？

题目的规则是：面值 1 的硬币最多用两枚，面值 2 的最多用一枚，也可以一种都不用。同面值的硬币没有编号，我们不区分究竟用了哪一枚。还有一条独立的规则：付款记录只写每种用了几枚，不写递出的顺序。因此，按“1、2”和按“2、1”的次序递出硬币，都留下“一枚 1、一枚 2”这同一份记录。下面可以换一种记录规则，检查区别究竟来自哪里。

把 1 单位硬币的数量暂时记为 $a$，把 2 单位硬币的数量记为 $b$。字母只是数量的名字：$a$ 可以是 0、1、2，$b$ 可以是 0、1。每枚第二种硬币贡献 2，所以总量是 $a + 2b$。例如 $a = 1$、$b = 1$ 时，总量是 $1 + 2 \times 1 = 3$。

对每个 $a$，都有 $b = 0$ 和 $b = 1$ 两种选择。因此我们一共有 $3 \times 2 = 6$ 对数量：(0,0)、(0,1)、(1,0)、(1,1)、(2,0)、(2,1)。第一项数量相同的对由 $a$ 分组，每组刚好有两个不同的 $b$，所以既没有漏掉，也没有重复。对应的总量分别是 0、2、1、3、2、4。

于是总量 0、1、2、3、4 对应的方法数是 1、1、2、1、1。这里总量 0 的方法数是 1，因为两种硬币都不取，确实是一种确定的选择；它和“根本没有合法选择”不同。接下来我们想把这张“总量对应方法数”的表保存下来，并且让记录本身帮助我们计算。

怎样让记录也能帮我们计算？

先看普通表格。表里需要两件不同的信息：付出的金额是多少，以及能付出这个金额的办法有几种。例如“金额是 2”和“办法有 2 种”虽然都出现了数字 2，却不能混为一谈。用两列能把它们分开，但我们还想让记录帮助我们合并选择：一份选择付 2，另一份付 3，合起来应当记录 5。我们需要一种相乘时会把这两个金额相加的写法。

我们用字母 $x$ 作一个记号。两个 $x$ 相乘，简写成 $x^{2}$；三个相乘，写成 $x^{3}$。右上角的数字叫指数，它告诉我们乘了几个 $x$。于是 $x^{2}x^{3}=(x\times x)(x\times x\times x)=x^{5}$：两组中的 2 个和 3 个合起来正好是 5 个。这正是我们需要的规则，所以选择用指数记录金额。$x$ 在这里不代表某枚硬币，也不需要代入金额；金额已经写在指数的位置。

金额为 0 时，我们没有要接在一起的 $x$，把这份记录写成 $x^0=1$。为什么用 1？因为一份付款加上“什么也不付”，金额应当保持原样；乘以 1 也恰好不改变另一项。这个约定让零金额也遵守同一套合并规则。

每一种选择贡献一项。两种不同的选择都给出总量 2，就得到 $x^{2} + x^{2} = 2x^{2}$。前面的 2 叫作系数，它数的是方法；上面的 2 是指数，它记的是总量。若没有方法凑出总量 5，对应项就是 $0x^{5}$，通常不写出来。因此前面的表可以写成：

例如读 $2x^{2}$ 这一项，就是“总量 2，有 2 种方法”。读常数项 1，就是“总量 0，有 1 种方法”。这里不是用整个式子的数值回答某一个总量的问题，而是找到对应指数，再读取它前面的系数。

为什么有时相加，有时相乘？

先看加法。回到开头的两幅硬币图：取两枚 1，或者取一枚 2。这是两个互不重叠的选择，因为前者没有 2 单位硬币，后者有一枚。它们各贡献一个 $x^{2}$，合起来是 $x^{2} + x^{2} = 2x^{2}$，表示总量 2 有两种方法。这里相加的前提是两组方法互不重叠。如果同一个选择同时出现在两个清单里，直接相加就会重复计算它。

现在回到硬币。我们不是在两种硬币之间二选一，而是要为每一种硬币都作一次选择。1 单位硬币可以取 0、1、2 枚，记录为 $A(x) = 1 + x + x^{2}$；2 单位硬币可以取 0、1 枚，记录为 $B(x) = 1 + x^{2}$。我们需要从 $A$ 中选一项，同时从 $B$ 中选一项。相乘的每个式子叫作一个因子，所以这里 $A$ 和 $B$ 就是两个因子。

合并两份选择时，总量应该相加。乘法恰好能够做到这一点：$x^{2}x^{3} = (x \times x)(x \times x \times x) = x^{5}$，两个指数对应的份数 2 和 3 合成了 5。一般地，把 $i$ 个 $x$ 和 $j$ 个 $x$ 接在一起，共有 $i + j$ 个 $x$，所以 $x^{i}x^{j} = x^{i+j}$。若某个指数是 0，相应因子是 1，不改变另一个总量，这也符合“什么都不取”的意思。

为什么乘两个括号会列出全部选择？按分配律，$A$ 的每一项都要乘整个 $B$，也就是分别乘 $B$ 的两项并相加。这样，$A$ 中的每个选择都会与 $B$ 中的每个选择配对一次。把中间的每一项写出来，就能逐一核对：

下面把这六次配对放进表格。选定目标总量后，点“计入下一对”。每个符合目标的格子被计入时，就把它贡献的 1 留在计数中；没有被计入的格子不会悄悄消失。蓝色硬币标 1，金色硬币标 2，数值也始终写在硬币上。

以目标 2 为例，第一对是 $A$ 的常数项与 $B$ 的 $x^{2}$，相乘得到 $x^{2}$，表示取 0 枚 1 和 1 枚 2；另一对是 $A$ 的 $x^{2}$ 与 $B$ 的常数项，也得到 $x^{2}$，表示取 2 枚 1 和 0 枚 2。因此系数是 $1 + 1 = 2$。两种方法恰好回到了开头的两幅图。

从一张小表得到一般的规则

以后把总量 $n$ 的方法数记为 $a_{n}$。下标 $n$ 表示我们正在看哪个总量，所以 $a_{0}$ 是总量 0 的方法数，$a_{1}$ 是总量 1 的方法数，不是 $a$ 乘 0 或 $a$ 乘 1。把这些数按指数排在一起的式子，称为这个数列的普通生成函数。本页说“生成函数”时都指这种记录法。

$A(x)$ 是这一整份记录的名字。为什么还叫“函数”？有限记录本来就是一个多项式；适当条件下，无穷记录也可以对应数值函数。不过本页使用的是它的“按系数记录”的意义，后面会严格说明无穷记录怎么运算，不需要先画出一条曲线，也不需要证明数值级数收敛。

前面的两个单独因子中，每个允许的金额只对应一种选择。例如，只考虑 1 单位硬币，金额 2 只有“取两枚”这一种。现在允许第一份记录 $A$ 中有 $a_i$ 种选择给出金额 $i$，第二份记录 $B$ 中有 $b_j$ 种选择给出金额 $j$。这里下标是在指出金额，前面的数是在数办法。对第一份记录中的每一种选择，都能配上第二份记录的全部 $b_j$ 种选择。这样共有 $a_i$ 组，每组 $b_j$ 对，所以是 $a_ib_j$ 对；每对的金额都是 $i+j$。

要找总量 $n$，只能选择 $i + j = n$ 的配对。因为总量不为负，$i$ 只能从 0 走到 $n$；一旦 $i$ 确定，$j$ 就只能是 $n - i$。所以依次检查 (0,n)、$(1,n-1)$、一直到 (n,0)，把各自的方法数相加，就得到乘积中 $x^{n}$ 的系数。

左边的 $[x^{n}]$ 意思是“取后面式子里 $x^{n}$ 的系数”，不是乘以 $x^{n}$。右边的 $\Sigma$ 是把刚才那串加法缩写：让 $i$ 依次等于 0、1、……、$n$，每次算一项 $a_{i}b_{n-i}$，然后全部相加。这条系数相乘、按总指数相加的规则，也叫卷积。我们先把它的意思算清楚，名字本身不增加新的操作。

这里的严格性来自两个方向。任何合法的配对都有一个确定的 $i$ 和 $j$，因此一定出现在上面的某一项里，不会漏掉。反过来，每一项只组合总量恰为 $i$ 和 $n - i$ 的两个选择，所以不会混入总量错误的配对。不同的 $i$ 不可能描述同一对，因为同一份 $A$ 选择的总量是确定的，所以也不会跨项重复。

不过还要核对：一个最终对象是否恰好对应一对选择？在硬币问题中，从最后取出的硬币可以唯一读回两种数量，所以配对与最终对象一一对应。若两个因子记录了同一个动作，或某些配对被题目禁止，就不能未经调整直接相乘。代数只会忠实执行我们写入的规则，不会替我们修正计数对象。

硬币可以无限取，为什么还算得清？

现在让 1 单位硬币的供给没有上限。我们可以取 0、1、2、3、……枚，每个数量只有一种选择，于是记录变成 $S(x) = 1 + x + x^{2} + x^{3} + \cdots$。三个点表示按同样的规则继续，每一个非负整数指数的系数都是 1，不是只写了几个样本就猜后面的规律。

这样按非负整数指数排列、允许有无限多项的记录，叫形式幂级数。“形式”提醒我们：先按系数来理解，不把 $x$ 当成某个实际数值去求无限和。两个这样的式子相等，是说每一个指数对应的系数都相等。相加时逐个系数相加；相乘时使用上一节已经说明的配对规则。

这样的乘法会不会要求一次相加无限多个数？对于固定的 $x^{n}$，不会。因为 $i$ 和 $j$ 都不为负，$i + j = n$ 只有 (0,n) 到 (n,0) 这 $n + 1$ 种指数配对。更高次的项不可能降低总指数来帮助凑 $n$。这就是我们能在有限的表格里准确计算一个指定系数的原因。

我们想给 $S(x)$ 找一个更短的写法。注意乘一个 $x$ 会把每项指数增加 1，因此 $xS(x) = x + x^{2} + x^{3} + \cdots$。把这两份记录相减，常数项是 $1 - 0 = 1$；每个正整数指数上的系数都是 $1 - 1 = 0$。所以：

这不是把一个模糊的“最后一项”消掉，而是对每一个确定的系数做了有限次减法。我们现在允许负系数参加中间代数运算，例如 $1 - x$ 中 $x$ 的系数是 $-1$；这个中间式子并不是在数“负一种选择”。最终的计数记录仍然有非负整数系数。

一个式子与 $1 - x$ 相乘得到 1，我们就把它称为 $1 - x$ 的乘法逆，写作 $1/(1 - x)$。在这里，这个分式表示形式幂级数的乘法逆。我们刚才证明了 $S$ 就是这样的式子。

如果每枚硬币的值是一个正整数 $d$，取 0、1、2、……枚就贡献 1、$x^{d}$、$x^{2d}$、……。乘 $x^{d}$ 会把每个允许指数挪到下一个允许指数，再相减只留下常数项 1；其他不为 $d$ 的倍数的指数始终是 $0 - 0$。因此同样得到：

这里 $d$ 必须为正。若允许无限多枚值为 0 的硬币，并把不同数量视为不同选择，那么仅总量 0 就有无限种方法，不能再用一个有限整数系数记录。这也说明我们的条件不是无关紧要的附注。至于把 $x$ 代成 1 后的数值问题，本页没有这样做；形式恒等式不声称 $1 + 1 + 1 + \cdots$ 是一个有限数。

例一：用 1、2、5 单位硬币凑总额

现在把硬币换成三种硬币，面值分别为 1、2、5，每种都可以取任意非负整数枚。同面值硬币不作区别，排列顺序也不算新方法。我们想凑出 5。前一节的规则分别给出三份记录，然后用乘法把三个数量选择合起来：

三个无穷记录能不能像普通括号那样相乘、改换分组和顺序？可以。对任何一个目标指数 $n$，只有 0 到 $n$ 之间的指数能参与，所以每个系数都只来自有限个普通整数乘积。下面抵消三个分母时，用到的正是这一点。理由放在下面的选读中。

最后一个分式是前面三个乘法逆的合写：把 $C(x)$ 乘以三个分母，每个分母恰好抵消它对应的级数因子，得到 1。这个写法缩短记录，但还没有自动给出目标的数值答案，我们仍要取 $x^{5}$ 的系数。

若分别取 $a$、$b$、$c$ 枚硬币，这三个因子中选出的项是 $x^{a}$、$x^{2b}$、$x^{5c}$，乘积为 $x^{a+2b+5c}$。因此只需列出满足 $a + 2b + 5c = 5$ 的非负整数数量。先固定 $c$：它只能是 0 或 1，因为 $c \ge 2$ 时，仅 5 单位硬币就已达到 10，超过 5。

下面构造清单时，5 的枚数保持不变，2 的枚数逐个增加，不足的金额用 1 补齐；这一组列完，5 的枚数就增加一枚。蓝色标 1、金色标 2、粉色标 5。点“加上下一个选择”后，硬币和等式一起保留下来。改动目标会清空旧清单，避免把不同题目的计数混在一起。

这个列举为什么完整？对目标 $n$，每个合法方案都有唯一的 $c$。固定它之后，每个合法方案也有唯一的 $b$，而 $a$ 只能等于 $n - 5c - 2b$。程序和手算都只让 $5c \le n$、$2b \le n - 5c$，再算这个非负的 $a$。因此每个生成的三元组合法，每个合法的三元组也必定会被生成一次。它不是靠观察几行图案来证明的。

作为相邻的检查，把目标改成 6。$c = 0$ 时，$b = 0$、1、2、3，对应 $a = 6$、4、2、0，共 4 种；$c = 1$ 时，剩下 1，只能 $b = 0$、$a = 1$，又有 1 种。合计 $4 + 1 = 5$。这和目标 5 的四种选择不同，清单能把新增或消失的对象直接展示出来。

这也和不定方程相连：我们在数方程 $a + 2b + 5c = n$ 的非负整数解。生成函数把不同 $n$ 的答案放在同一份记录中；它没有把“整数且非负”的限制抹去，而是通过每个因子里允许出现的指数来保存这些限制。

例二：最多取几枚，或者至少取几枚？

无限供给不能代替有限供给。若值为 $d$ 的硬币最多取 $m$ 枚，$d$ 是正整数、$m$ 是非负整数，允许的数量只有 0 到 $m$，因此记录应当在 $x^{md}$ 停下来：

像前面一样乘 $x^{d}$，得到 $x^{d} + x^{2d} + \cdots + x^{(m+1)d}$。做 $B - x^{d}B$ 时，指数 $d$ 到 $md$ 的系数都是 $1 - 1$，常数项留下 1，最高的 $x^{(m+1)d}$ 只出现在被减掉的式子里，留下 $-x^{(m+1)d}$。于是每一步为：

最后一步是两边乘前面已经构造的形式逆 $1/(1 - x^{d})$，并不是在任意数值 $x$ 处随意除以一个可能为零的数。当 $m = 0$ 时，中间没有需要相消的项，$B = 1$，式子同样给出 $(1 - x^{d})/(1 - x^{d}) = 1$。

例如只有两枚 2 单位硬币，允许 0、1、2 枚，记录就是 $1 + x^{2} + x^{4}$。代入 $d = 2$、$m = 2$，上式给出 $(1 - x^{6})/(1 - x^{2})$，其中指数 6 来自 $(2 + 1) \times 2$。若还允许任意枚 1 单位硬币，想凑出 5，就分别取 0、1、2 枚 2，剩下的 1 的枚数是 5、3、1，所以有 3 种。

若至少要取 $r$ 枚值为 $d$ 的硬币，其中必定包含 $r$ 枚，它们贡献 $rd$。除此以外，还可以取 0、1、2、……枚，贡献 0、$d$、$2d$、……。所以记录为 $x^{rd}(1 + x^{d} + x^{2d} + \cdots )$。每个符合“至少 $r$ 枚”的选择都能唯一减去这 $r$ 枚，剩下一个非负数量，因此这样的分解既不漏也不重复。

比如至少一枚 2 单位硬币，且任意枚 1 单位硬币凑 5，先拿走必需的那枚 2，剩下 $5 - 2 = 3$。剩余 3 可以用三枚 1，或一枚 2 加一枚 1，只有两种。放回必需的 2，就得到 (1 的枚数, 2 的枚数) $= (3, 1)$、$(1, 2)$。对应记录是 $x^{2}/((1 - x)(1 - x^{2}))$，前面的 $x^{2}$把每个原来总量增加了 2。

例三：两枚骰子，顺序为什么不能丢？

换一个计数对象。桌上有第一枚和第二枚骰子，每枚的点数可以是 1 到 6。我们现在只计数点数结果，不假设骰子公平，也不计算概率。第一枚出 1、第二枚出 6，与第一枚出 6、第二枚出 1，是两个不同结果，因为两枚骰子可以区分。

每枚骰子每个点数对应一种结果，所以记录是 $D(x) = x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6}$。没有常数项，因为一枚骰子没有 0 点这个结果。两个因子虽然写法相同，但第一个记录第一枚，第二个记录第二枚；相乘时这两个位置仍然保留着。

第一枚若是 $i$，第二枚必须是 $7 - i$。让 $i = 1$、2、3、4、5、6，第二枚依次是 6、5、4、3、2、1，每个都在允许范围内。因此有 (1,6)、(2,5)、(3,4)、(4,3)、(5,2)、(6,1)，每一对贡献 $1 \times 1 = 1$，合计 6 种。

下面表格的行保留第一枚的点数，列保留第二枚的点数。格子里写两者之和，✓ 表示和等于目标。拖动目标时，检查哪些格子会被选中，再读下方逐项相加的计数。比如目标 2 只有 (1,1)，而目标 12 只有 (6,6)。

不要因为最终的代数乘法可以交换两个因子，就认为可以忘掉对象的区别。把两枚骰子的名字交换，会把 (1,6) 对应到 (6,1)，说明两个命名方式有相同的总计数，并没有把这两个结果合并成一个。在硬币题里，我们从一开始就只选每种数量；在骰子题里，我们从一开始就分别选每枚的点数。不同的计数问题，需要不同的记录。

例四：从铺砖的递推得到生成函数

前面的因子来自几种可以分别选择的物品。现在考虑另一种问题：用长度为 1 和长度为 2 的砖，铺满长度为 $n$ 的单行长条，不能重叠，也不能留空。砖都横着放，1 砖彼此一样，2 砖彼此一样，但从左到右的顺序是铺法的一部分。例如长 3 的条，按“1、2”和按“2、1”排列时，两块砖占据的位置不同。

把长 $n$ 的铺法数记为 $a_{n}$。长 0 时没有格子需要铺，什么也不放就完成要求，所以 $a_{0} = 1$。长 1 时只能放一块 1 砖，因此 $a_{1} = 1$。这两个起点需要明确写下，因为后面每一步的计数都从它们开始。

当 $n \ge 2$ 时，我们按最后一块砖分类。若最后一块长 1，去掉它后，前面正好是长 $n - 1$ 的完整铺法。反过来，每个长 $n - 1$ 的铺法后面添一块 1，都得到唯一一个最后是 1 的铺法。这两个操作互相撤销，所以这一类恰有 $a_{n-1}$ 种。

若最后一块长 2，同样去掉它会留下长 $n - 2$ 的铺法；在任意这种短铺法后添一块 2 又能唯一恢复，因此第二类有 $a_{n-2}$ 种。一个铺法的最后一块不能同时是 1 和 2，所以两类没有重叠；砖只有这两种长度，所以每个铺法也一定属于其中一类。于是我们能把两类相加：

用前面的值计算后面的值，这种关系叫递推关系。这里 $a_{2} = a_{1} + a_{0} = 1 + 1 = 2$；$a_{3} = a_{2} + a_{1} = 2 + 1 = 3$；$a_{4} = a_{3} + a_{2} = 3 + 2 = 5$；$a_{5} = a_{4} + a_{3} = 5 + 3 = 8$。它们属于斐波那契型的递推，但我们不依赖这个名字，而依赖刚才“最后一块砖”的完整分类。

下面蓝色短砖标 1，金色长砖标 2。先保留长 4，逐次点“下一种铺法”，能看到 $1+1+1+1$、$1+1+2$、$1+2+1$、$2+1+1$、$2+2$ 这五种。每一块砖的宽度对应它占据的长度；下面的加法把这个图形和总长连在一起。

现在让同一份记录自己错开一格

我们把全部铺法数记进 $F(x)$。为了让 $a_{n}$、$a_{n-1}$ 和 $a_{n-2}$ 出现在同一个指数的位置，可以分别使用 $F$、$xF$ 和 $x^{2}F$：乘 $x$ 把原来的 $a_{n-1}x^{n-1}$ 变成 $a_{n-1}x^{n}$；乘 $x^{2}$ 把 $a_{n-2}x^{n-2}$ 变成 $a_{n-2}x^{n}$。我们不是任意选择乘数，而是要把递推式里的三项对齐。

做 $F - xF - x^{2}F$。常数项只有 $F$ 提供，所以是 $a_{0} = 1$。$x$ 的系数是 $a_{1} - a_{0} = 1 - 1 = 0$，因为 $x^{2}F$ 还没有 $x$ 这一项。对每个 $n \ge 2$，$x^{n}$ 的系数则是 $a_{n} - a_{n-1} - a_{n-2}$；由已经证明的递推式，这正好是 0。我们把起始的两项单独处理，不能把只对 $n \ge 2$ 成立的递推套到它们上。

最后的分式仍表示形式乘法逆：$F$ 就是乘 $1 - x - x^{2}$ 后得到 1 的那份记录，而我们是用具体铺法数把它构造出来的。

这说明一个短分式可以保存整条递推及其起点。我们没有宣称看见分式就不需要计算：比如求 $x^{5}$ 的系数，仍可按已经证明的规则得到 1、1、2、3、5、8，读取第 5 次幂前面的 8。相较于列出全部铺法，这个递推只保留计数；而生成函数又把递推转成了一个可以与其他记录相乘、移动指数的代数对象。

例如一块装饰板由“固定长 2 的端头”接上一段这样的铺砖长条组成，总长要是 6。端头只有一种，因此贡献 $x^{2}$，整板的记录是 $x^{2}F(x)$。要凑 $x^{6}$，只能配上 $F$ 中的 $x^{4}$，其系数是 $a_{4} = 5$，所以有 5 种。这也直接对应“去掉固定端头，剩下长 4”的五种铺法。我们再次用一个具体对象核对了代数。

自己试一试，再逐步核对

下面每题都可以用实际选择来理解，并用系数核对。答案可以展开，不要求记住某个计数公式。重要的是每一步都能说明：我们数的对象是什么，为什么刚好数一次。

我们从“凑出 2 有两种方法”开始，把每个选择写成一项。由此证明了：加法记录互不重叠的方案，乘法记录可以唯一拆开的组合。指数负责总量，系数负责方法数。无穷供给、有限供给、骰子和铺砖的形式虽然不同，都需要同样的核对：这个系数里的每一份贡献，在原问题中是哪一种选择？弄清这个对应关系，才能知道式子算出的是否正是我们想数的东西。