生成函数与离散概率前奏

前面几章里，我们已经用加法原理、乘法原理、排列组合、容斥和鸽巢原理解决了不少计数问题。这些方法的共同点是：先把对象拆清楚，再把“有多少种可能”数出来。

这一章换一个角度。我们把计数信息写进代数式里，让幂次记录“大小、金额、和数、选了几个”，让系数记录“有多少种方式”。这种代数式叫普通生成函数。它一开始看起来像形式上的多项式游戏，但它很快会变成一个有力的记账工具。

本章后半段会把计数自然接到离散概率。等可能模型下，概率就是一个比例：事件中有多少个结果，除以样本空间中有多少个结果。生成函数负责数清楚，概率负责把计数结果解释成可能性。

普通生成函数的直觉

先从一个很小的选择问题开始。假设某种对象最多可以选 3 个，而且每一种数量只有 1 种选法。我们可以把“不选、选 1 个、选 2 个、选 3 个”写成：

1+x+x^2+x^3

这里的 $x$ 不是用来代入具体数值的变量。它更像一个标签： $x^0$ 表示数量为 $0$ ， $x^1$ 表示数量为 $1$ ， $x^2$ 表示数量为 $2$ 。每一项前面的系数表示对应数量下有几种方式。

普通生成函数示意图：对象选择次数从不选到选三个，分别编码为 1、x、x²、x³，并组成多项式，标出幂次表示数量、系数表示方式数。 — 普通生成函数把选择数量编码为幂次，把对应方式数编码为系数。

如果某个计数序列是

a_0,a_1,a_2,a_3,\ldots

那么它的普通生成函数写成

A(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots

这句话的意思不是“我们想研究一个可以求值的函数”。在离散数学入门阶段，更重要的是把它看成一张压缩的计数表：第 $n$ 项系数 $a_n$ 记录规模为 $n$ 的对象有多少个。

普通生成函数里的 $x$ 常常只是一个形式符号。我们暂时不关心这个级数在什么数值下收敛，而是关心展开式里每个幂次的系数。对本章的大多数有限计数问题，只要目标规模有限，参与计算的项也是有限的。

一个计数表的改写

假设长度为 $n$ 的二进制字符串有 $2^n$ 个。这个计数序列是

1,2,4,8,16,\ldots

它对应的普通生成函数是

1+2x+4x^2+8x^3+16x^4+\cdots

系数 $4$ 站在 $x^2$ 前面，意思是长度为 $2$ 的二进制字符串有 $4$ 个： $00,01,10,11$ 。系数 $8$ 站在前面，意思是长度为的二进制字符串有个。

这里的生成函数没有替代乘法原理。它只是把乘法原理得到的结果排成一个代数对象。真正有用的地方在下一步：当几个选择要合在一起时，生成函数的乘法会自动把所有组合配对。

系数提取

为了准确说“取出 $x^n$ 前面的系数”，我们使用系数提取符号：

[x^n]A(x)

它读作“ $A(x)$ 中 $x^n$ 的系数”。如果

A(x)=2+5x+3x^2+7x^3+x^4

那么

[x^3]A(x)=7

放大镜框住多项式中的 7x³，旁边标出系数提取结果，说明先锁定幂次再读取系数。 — 系数提取符号先定位指定幂次，再读取该项前面的系数。

系数提取最容易出错的地方，是把幂次和系数混在一起。 $7x^3$ 这一项里， $3$ 是规模标签， $7$ 是方式数。题目问“有多少种方式达到规模 $3$ ”，答案是 $7$ ，不是 $3$ 。

例题：从多项式中读信息

设

B(x)=4+2x+9x^2+6x^5

求 $[x^0]B(x)$ 、 $[x^2]B(x)$ 和 $[x^4]B(x)$ 。

先看常数项。常数项就是 $x^0$ 项，所以 $[x^0]B(x)=4$ 。

没有出现的幂次，系数是 $0$ 。这条规则很普通，却在后面处理样本空间、硬币组合和骰子点数时经常救场。

乘法为什么会枚举组合

生成函数最值得学的地方，是乘法。先看两个简单多项式：

(1+x+x^2)(1+x^3)

展开时，我们从第一个括号里选一项，再从第二个括号里选一项，然后相乘。比如选 $x^2$ 和 $x^3$ ，就得到 $x^5$ 。幂次相加，表示两个选择的规模相加。

完整展开是

(1+x+x^2)(1+x^3)=1+x+x^2+x^3+x^4+x^5

这个式子可以解释为：第一类对象可以贡献 $0,1,2$ 的规模，第二类对象可以贡献 $0$ 或 $3$ 的规模；合在一起，总规模可以是 $0,1,2,3,4,5$ ，而且每个总规模各有一种方式。

更一般地，如果

A(x)=a_0+a_1x+a_2x^2+\cdots

和

B(x)=b_0+b_1x+b_2x^2+\cdots

那么 $A(x)B(x)$ 中 $x^n$ 的系数是

[x^n]A(x)B(x)=a_0b_n+a_1b_{n-1}+a_2b_{n-2}+\cdots+a_nb_0

每一项 $a_ib_{n-i}$ 都在说：第一部分贡献规模 $i$ ，第二部分贡献规模 $n-i$ 。把所有 $i$ 加起来，就得到总规模为的全部方式。

三层选择路径中高亮一条路径，并对应代数项 x 的三次方，说明组合对象与代数项一一配对。 — 每条选择路径贡献一个代数项，同次幂合并成系数。

生成函数乘法不是额外的魔法。它只是把“分步选择”的乘法原理写进展开式里，再用同次幂合并来完成分类计数。

硬币金额组合

硬币问题是普通生成函数最自然的入门例子之一。假设有不限数量的 $1$ 元、 $2$ 元、 $5$ 元硬币，问凑出某个金额有多少种组合。这里不区分硬币顺序，所以“ $5+2$ ”和“ $2+5$ ”算同一种组合。

一枚面值为 $1$ 的硬币可以选 $0,1,2,3,\ldots$ 枚，对金额的贡献是 $0,1,2,3,\ldots$ ，所以对应因子是

1+x+x^2+x^3+\cdots

面值为 $2$ 的硬币可以贡献金额 $0,2,4,6,\ldots$ ，对应因子是

1+x^2+x^4+x^6+\cdots

面值为 $5$ 的硬币可以贡献金额 $0,5,10,15,\ldots$ ，对应因子是

1+x^5+x^{10}+x^{15}+\cdots

三种硬币合在一起，对应的生成函数是

(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^5+x^{10}+\cdots)

凑出 $n$ 元的组合数，就是这个乘积中 $x^n$ 的系数。

硬币金额组合与生成函数乘积的对应关系，1 元、2 元、5 元硬币分别给出可选项序列，并用 x 的七次方表示总金额 7 元。 — 硬币选择问题可以转化为生成函数乘积中对应幂次项的系数问题。

例题：用 1 元、2 元、5 元凑 7 元

求使用不限数量的 $1$ 元、 $2$ 元、 $5$ 元硬币凑出 $7$ 元的组合数。

先写出生成函数。 $1$ 元、 $2$ 元、 $5$ 元硬币分别对应三个因子，所以总生成函数是

C(x)=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^5+x^{10}+\cdots)

硬币组合问题通常不区分顺序。若把 $1+2+5$ 、 $2+1+5$ 、 $5+2+1$ 都当成不同结果，数到的是排列型过程，不再是这里这个生成函数模型。

选择问题与骰子点数

生成函数不只适合硬币。只要一个问题能拆成几个独立选择，并且总规模由各部分相加得到，就可以考虑用生成函数。

例如掷一枚普通骰子，点数可能是 $1,2,3,4,5,6$ 。如果用幂次记录点数，一枚骰子的生成函数是

D(x)=x+x^2+x^3+x^4+x^5+x^6

掷两枚骰子时，总点数来自两枚骰子的点数相加，所以生成函数是

D(x)^2=(x+x^2+x^3+x^4+x^5+x^6)^2

其中 $[x^7]D(x)^2$ 表示两枚骰子点数和为 $7$ 的有序结果数。因为第一枚骰子和第二枚骰子可以区分，所以 $(1,6)$ 和 $(6,1)$ 是两个不同结果。

把和为 $7$ 的结果列出来：

(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)

共有 $6$ 个，所以

[x^7]D(x)^2=6

两个骰子的 6×6 样本空间网格，格子中标出点数和，并高亮和为 7 的六个结果，旁注概率为 6/36。 — 两个骰子的等可能样本空间共有 36 个结果，其中和为 7 的事件包含 6 个结果。

生成函数在这里完成的是计数。概率还需要下一步：明确样本空间，并确认样本空间中的结果是否等可能。

样本空间与事件

在离散概率里，样本空间通常记作 $S$ ，表示一次随机试验的所有可能结果。事件是样本空间的子集，通常记作 $A,B,E$ 等。

掷两枚骰子时，一个合适的样本空间是

S=\{(i,j):1\le i\le 6,1\le j\le 6\}

这里 $i$ 表示第一枚骰子的点数， $j$ 表示第二枚骰子的点数。样本空间里共有

6\cdot6=36

个结果。

事件“点数和为 $7$ ”可以写成

E=\{(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)\}

它有 $6$ 个结果。若两枚骰子公平，并且每个有序对等可能，则

P(E)=\frac{|E|}{|S|}=\frac{6}{36}=\frac{1}{6}

样本空间不是随便列几个看起来不同的结果。掷两枚骰子时，若把可能的和写成 $\{2,3,\ldots,12\}$ ，这些和并不等可能。和为 $7$ 的方式有 $6$ 个，和为 $2$ 的方式只有 $1$ 个，所以不能直接把 11 个和数当作等可能结果。

等可能模型

等可能模型是离散概率最先接触的模型。它的规则很短：如果样本空间 $S$ 有有限多个结果，而且每个结果发生的可能性相同，那么任意事件 $A\subseteq S$ 的概率是

P(A)=\frac{|A|}{|S|}

这条公式把概率问题变成了计数问题。分母数全部结果，分子数事件中的结果。

样本空间中 20 个结果里有 5 个属于事件 A，右侧用公式表示概率等于事件结果数除以样本空间结果数。 — 先数全部结果，再数有利结果。

例题：从计数到概率

从所有长度为 $4$ 的二进制字符串中等可能地选一个。求字符串中恰好有两个 $1$ 的概率。

先确定样本空间。长度为 $4$ 的二进制字符串每一位有 $0$ 或 $1$ 两种选择，所以总数是

|S|=2^4=16

这个例子也可以用生成函数解释。每一位要么贡献 $0$ 个 $1$ ，要么贡献 $1$ 个 $1$ ，所以一位的生成函数是 $1+x$ 。四位合在一起是

(1+x)^4

恰好两个 $1$ 的字符串数是

[x^2](1+x)^4=\binom{4}{2}=6

生成函数给出事件结果数，样本空间给出全部结果数，二者合起来得到概率。

什么时候该用生成函数

生成函数不是每道计数题都要用。它适合下面这类问题：对象可以分成若干部分，每个部分有若干可能贡献，总规模是这些贡献相加，而题目关心某个总规模的方式数。

常见信号包括：

问“凑出某个总和有多少种方法”。
每一类选择可以贡献 $0,1,2,\ldots$ 或某些固定间隔的数量。
多个独立选择合在一起，最后只关心总数、总金额、总点数或总重量。
题目需要同时比较多个规模，而不是只算一个孤立数字。

也有不适合强行使用生成函数的情形。如果问题的顺序非常重要，或者后一步的选择严重依赖前一步状态，直接用递推、分类讨论、容斥或图模型可能更清楚。

本章只使用普通生成函数的入门部分。以后如果继续学习组合数学，会看到生成函数用于解递推、处理分拆、研究 Catalan 数、连接指数生成函数和标号结构。现在先把“幂次是规模，系数是数量”这件事吃透。

章末自检

A(x)=3+4x+2x^2+9x^5

求 $[x^1]A(x)$ 、 $[x^3]A(x)$ 和 $[x^5]A(x)$ 。

$[x^1]A(x)=4$ ，因为 $x$ 项是 $4x$ 。 $[x^3]A(x)=0$ ，因为展开式中没有项。，因为项是。

用不限数量的 $2$ 元和 $3$ 元硬币凑 $8$ 元。写出生成函数表达，并求组合数。

生成函数是

(1+x^2+x^4+x^6+x^8+\cdots)(1+x^3+x^6+\cdots)

掷两枚公平骰子，求点数和至少为 $10$ 的概率。

样本空间有 $36$ 个有序结果。和为 $10$ 的结果有 $(4,6),(5,5),(6,4)$ ，共 $3$ 个；和为 $11$ 的结果有，共个；和为的结果有，共个。因此事件结果数是，概率是。

从所有长度为 $5$ 的二进制字符串中等可能地选一个。求恰好有三个 $1$ 的概率，并说明生成函数怎样给出分子。

样本空间大小是 $2^5=32$ 。恰好有三个 $1$ 的字符串数是 $\binom{5}{3}=10$ ，所以概率是。生成函数角度下，每一位对应，五位对应，分子就是。

这一章把计数问题推进到一个新的层次：先用生成函数把“有多少种方式”压进系数，再用样本空间把计数结果解释成概率。下一章进入图论语言，我们会从“数对象”转向“看对象之间怎样相连”。

离散数学与证明 I：逻辑、集合、归纳、计数与图论入门｜第 14 章：生成函数与离散概率前奏 | 自在学