图论与组合 I · 计数：从容斥到生成函数

用 1、2、5 分硬币凑 5 分，有 4 种硬币组合，却有 9 种依次投币的序列。两个答案都对，区别在于“换个顺序算不算新方案”。本页先把对象和判重规则写清楚，再推导加乘、容斥、递推与生成函数；图上的路线和生成树是另一组对照。

先修：集合与函数、数学归纳与极限语言、多项式。第 4 节使用形式幂级数，不要求先证明解析收敛；涉及真实函数取值时才另查收敛域。

1. 加法、乘法和除法：先明确何时是同一方案

加法原理要求分类互斥且穷尽。若分两类后一个对象落入两类，直接相加会重计，需要容斥。乘法原理要求每一步的可选数量在相应分支上已知；若不同第一步有不同数量的后续，先逐支相乘再相加，不能随便取一个公共乘数。

例如从 \(n\) 个不同对象中选出 \(k\) 个并排成序列，不重复，\(0\le k\le n\)：

若不计顺序，每个 \(k\) 元子集恰好对应 \(k!\) 个序列，因此

除法需要每类都有同样多的表示。带重复对象、对称图形或不同稳定子的情形，不能未经核对就除以一个阶乘；处理对称计数时可接到 群作用。

隔板法数的是哪一种“球放盒”？

\(k\) 个不可区分的球放入 \(n\ge1\) 个有标签的盒子，允许空盒；一个方案就是

把 \(k\) 个星号与 \(n-1\) 块隔板排在一起，每个间隔的星号数对应一个 \(x_i\)。这个对应可逆，所以方案数为 \(\binom{k+n-1}{n-1}\)。若每盒至少一个球，先各放一个，\(k\ge n\) 时得到 \(\binom{k-1}{n-1}\)；\(k<n\) 时为 0。

换成不同的球、有标签的盒，每个球有 \(n\) 个去处，允许空盒时为 \(n^k\)。若盒子也无标签，问题进入整数分拆或集合划分，不能继续使用同一个隔板公式。

双计数的证明比背恒等式更可靠

从 \(n\) 个不同对象中选 \(k\) 个，按是否包含指定对象分类：

从两组各 \(n\) 人中一共选 \(n\) 人，按第一组选了 \(k\) 人分类：

两边数的是同一个集合，分类也不重不漏，这才是恒等式成立的原因。鸽笼原理同样是有限分类：把任意 \(n+1\) 个整数按模 \(n\ge1\) 的余数放入 \(n\) 类，必有两个同类，因此差能被 \(n\) 整除。

2. 容斥：让每个被覆盖的元素最后恰好算一次

对有限集合 \(A_1,\ldots,A_n\)，

固定一个恰好属于 \(r\ge1\) 个集合的元素。它在右边的净计数为

完全不在并集中的元素贡献 0。逐元素核对就证明了公式；无需猜测该加哪一项。

错排：概率接近，不是答案相同

\(n\) 封不同的信随机一一放入 \(n\) 个有对应标签的信封。\(A_i\) 表示第 \(i\) 封放对。固定一组 \(j\) 封都放对后，其余有 \((n-j)!\) 种排列；选择这组有 \(\binom nj\) 种。对“一个也没放对”容斥：

\(D_0=1,D_1=0,D_2=1,D_3=2,D_4=9\)。只有在全部 \(n!\) 个排列等可能时，错排概率才是 \(D_n/n!\)。利用交错级数余项，

因此概率趋于 \(1/e\)，不是 10 封与一万封的计数相同，有限规模概率也不完全相同。\(n\ge1\) 时 \(D_n\) 是 \(n!/e\) 最近的整数；\(n=0\) 要单独用初值，不能套这个取整结论。

另一递推是 \(D_n=(n-1)(D_{n-1}+D_{n-2})\)，\(n\ge2\)：先让信 1 去信封 \(j\ne1\)。若信 \(j\) 去信封 1，剩下是 \(n-2\) 的错排；否则把信 1 与指向信封 1 的关系收缩，可一一对应到 \(n-1\) 的错排。两类分别贡献 \(D_{n-2}\) 与 \(D_{n-1}\)，再乘 \(n-1\) 个 \(j\)。

实验把容斥的每个带符号整数项和累计和列出，再与递推结果核对。核对有限规模不能替代上面的分类证明，但能暴露符号、初值和索引错误。

3. 递推：每个较大对象怎样唯一拆成较小对象？

设 \(a_m\) 是用步长 1 或 2、按顺序走到总长度 \(m\) 的方法数。空序列给 \(a_0=1\)，\(a_1=1\)。按最后一步分类，删掉最后的 1 或 2 得到唯一的较小序列，因此

若 Fibonacci 约定是 \(F_0=0,F_1=1\)，则 \(a_m=F_{m+1}\)，不是 \(F_m\)。明确初值可以避免公式全对、指标却整体错一位。

对这个递推试 \(a_m=r^m\)，得到 \(r^2=r+1\)。两个不同根为 \(\varphi=(1+\sqrt5)/2\) 与 \(\psi=(1-\sqrt5)/2\)，结合初值得

常系数递推与常系数微分方程都有特征根方法，但一个使用移位算子、一个使用微分算子；离散解的 \(r^m\) 与连续解的 \(e^{\lambda t}\) 不能不加转换地混为同一对象。实际计算较大整数时，直接用浮点 Binet 公式取整可能舍入出错，精确整数递推更适合本实验。

4. 普通生成函数：指数记规模，系数记数量

定义 \(A(x)=\sum_{m\ge0}a_mx^m\)，符号 \([x^m]A(x)\) 表示取第 \(m\) 项系数。先把它看作形式幂级数：一个系数序列，而不是必须在某个实数 \(x\) 上求值的函数。

两个级数相乘时

对于固定 \(m\)，右边只有有限项。这对应“先选规模 \(j\) 的 A 对象，再选规模 \(m-j\) 的 B 对象”，前提是拆分方式唯一、总规模可加。若拆分不唯一，乘积会多算表示。

在有理数或实数系数的形式级数中，常数项非零就有乘法逆；在整数系数环中，常数项需为可逆元 \(\pm1\)。本页的分母常数项都是 1。形式运算不需要解析收敛；例如 \(\sum m!x^m\) 的收敛半径为零，仍可作为形式级数。要代入数值、积分或使用解析极限时，才需另外核对相应条件。MIT 的《Mathematics for Computer Science》第 14–15 章提供了计数与形式级数的系统背景。

把上一节递推乘 \(x^m\)，从 \(m=2\) 起求和：

减去的 \(1+x\) 和 \(1\) 都来自初值，不能省略。生成函数没有创造新的计数对象，只是把同一递推整理成代数等式。

同样三种面额，为什么有两种生成函数？

忽略顺序的硬币组合。每种面额可取任意非负数量，面额 2 的因子是 \(1+x^2+x^4+\cdots\)，于是

每个乘积项恰好对应数量三元组 \((u_1,u_2,u_5)\)。这是硬币无限供应、同面额不可区分的模型；有库存上限时应改成有限多项式。

计顺序的投币序列。每个位置可选 1、2 或 5，长度为 \(\ell\) 的序列由 \((x+x^2+x^5)^\ell\) 编码；再把所有长度相加：

因为每枚硬币价值为正，固定金额只涉及有限长度，这个形式几何级数合法。加入“零面额物品可无限取”后，固定规模可能有无穷多个对象，原计数就需要重新定义。

金额为 5 时，\([x^5]U=4\)、\([x^5]O=9\)。实验中“先遍历面额再累计金额”给组合，“按金额递增、按最后一枚面额求和”给有序序列。循环次序改变的是数学问题。

5. Catalan：第一对括号在哪里闭合？

合法括号串有 \(m\) 对括号，任意前缀中左括号不少于右括号。空串给 \(C_0=1\)。非空串唯一写成

其中最左括号的匹配右括号确定了拆分点。若 \(A\) 有 \(j\) 对，\(B\) 就有 \(m-1-j\) 对，因此

满足常数项 \(C(0)=1\) 的形式解为 \((1-\sqrt{1-4x})/(2x)\)，分子可被 \(x\) 整除；不是在 \(x=0\) 作未经说明的 \(0/0\)。展开得

同一数列还数：有 \(m\) 个内部结点的有序满二叉树、凸 \((m+2)\) 边形的三角剖分、不越过对角线的 \(m\) 步右加 \(m\) 步上格路。树是否有序、是否满、数内部结点还是全部结点必须说明；一般“二叉树形态”没有唯一约定，不能直接报 Catalan。

6. 图的计数：路线、边端点和生成树各数什么？

本实验的图是有限、无向、无自环、无重边的简单图，顶点有标签。路线起点固定为 0，终点任意，长度是边数；一个对象是按行进顺序记录的顶点序列。

简单路径不重复顶点；游走允许重复。设邻接矩阵为 \(M\)，则 \((M^k)_{ij}\) 数从 \(i\) 到 \(j\) 的长度 \(k\) 游走，固定起点的总数是 \(\sum_j(M^k)_{0j}\)。证明按倒数一步顶点分类，恰好给出矩阵乘法。简单路径不能仅用同一状态递推，因为还需知道哪些顶点已访问。

在 \(K_n\) 上，从固定起点走 \(k\) 步，游走有 \((n-1)^k\) 条；当 \(0\le k\le n-1\) 时简单路径有 \((n-1)!/(n-1-k)!\) 条，\(k\ge n\) 时为 0。\(k=0\) 两者都为 1。换成不固定起点或把逆序视作同一对象，计数会变化。

握手引理 \(\sum_v\deg(v)=2|E|\) 数的是每条边的两个端点。一般无向多重图若按通常约定让自环贡献度 2，它也成立；实验采用简单图以便邻接矩阵和路线规则统一。度和为偶只是必要信息，不能单独证明任意给定度序列都能实现。

为什么生成树数不是任意路径数？

生成树包含原图的全部顶点，边取自原图，并且连通无圈。\(n\) 个顶点的树有 \(n-1\) 条边；对有限无向简单图，“连通且有 \(n-1\) 条边”等价于树。不连通图的生成树数是 0；孤立的单顶点按约定有一棵空边生成树。

Cayley 公式

数的是标号完全图上的生成树；单顶点单独为 1。证明的一个入口是 Prüfer 编码：反复删去当前最小标签叶子、记录它的邻点，得到长度 \(n-2\) 的标签序列；反向每次选当前未在剩余编码中出现的最小标签作叶子，可唯一恢复树。因此树与 \(n^{n-2}\) 个序列一一对应。

一般图用拉普拉斯矩阵 \(L=\operatorname{diag}(\deg)-M\)。删去同一行列得到 \(L^{(r)}\)，Matrix–Tree 定理给

它给出了计数的行列式表示；实验的精确整数计算验证当前有限图，不替代定理的证明。路径图有 1 棵生成树，\(n\ge3\) 的简单循环图有 \(n\) 棵（恰好删除任意一条边），断开图为 0。下一页会继续图的连通与树结构。

7. 三道可展开的核对题

下一页：图的语言与结构。遇到新计数问题，先写出对象、规模、是否计顺序和边界初值，再决定使用哪一种工具。