竞赛组合：母函数、图论与递推

高中组合竞赛的核心是把“看起来无从下手”的离散问题，转化成可计算的结构：等价分类、双计数、递推、图模型。

一、 核心知识点讲解

1. 双计数 (Double Counting)

对同一集合按两种方式计数，是组合证明最常见武器。

典型模板：

• 按“元素视角”统计；
• 按“容器视角”统计；
• 两个表达式相等，得到恒等式或不等式。

例如二项式恒等式

$$\sum_{k=0}^{n}\binom{n}{k}^2=\binom{2n}{n}$$

就是对“从两组各 $n$ 人中选 $n$ 人”进行双计数。

2. 抽屉原理与极值思想

• 抽屉原理：若把 $N$ 个对象放入 $m$ 个盒子，必有一盒不少于 $\lceil N/m\rceil$ 个。
• 极值思想：先取“最大/最小”对象，再利用其极端性构造矛盾。

这两类方法常用于存在性问题，尤其是“必有两数同余”“必有结构重复”“最短反例不存在”。

3. 递推与生成函数

将序列 $\{a_n\}$ 转化为形式幂级数

$$A(x)=\sum_{n\ge 0}a_nx^n$$

可把递推关系变为代数方程。

4. 常用递推模型

• Catalan 数：$C_n = \frac{1}{n+1} \binom{2n}{n}$。应用：括号匹配、出栈次序、多边形三角剖分。
• 第二类 Stirling 数：将 $n$ 个不同元素分成 $k$ 个非空子集的方案数。

5. 图论模型（竞赛常用）

• Ramsey 思想：规模足够大时，必有“全同色子结构”。
• 平面图与欧拉公式：$V-E+F=2$（连通平面图）。
• 握手定理：$\sum \deg(v)=2E$，常用于奇偶性与度数下界。

6. 容斥原理 (Inclusion-Exclusion Principle)

处理“至少”或“至多”问题的标准工具。

• 基本形式： $|A_1 \cup A_2 \cup \dots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap \dots \cap A_n|$
• 补集形式： $|\bigcap \bar{A_i}| = |S| - \sum |A_i| + \sum |A_i \cap A_j| - \dots$
• 错位排列 (Derangements)：$n$ 个元素的错排数 $D_n$ 满足： $D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$ 且满足递推式：$D_n = (n-1)(D_{n-1} + D_{n-2})$。

竞赛策略

组合题先做“题型归类”：计数恒等式优先双计数，存在性优先抽屉原理，序列问题优先递推/母函数，涉及排除多个属性的计数优先容斥原理。

---

二、 经典例题实战

例题 1：卡特兰数的应用

一个 $n \times n$ 方格，从左下角走最短路径到右上角，且不跨越主对角线的路径有多少条？

点击查看解析与答案

解析过程

1. 路径计数：总走法为 $\binom{2n}{n}$。
2. 不合法路径判定：跨越对角线意味着路径触碰了直线 $y = x + 1$。
3. 反射原理：每一条非法路径都可以唯一地映射为从 $(-1, 1)$ 到 $(n, n)$ 的路径。
4. 计算非法数：$\binom{2n}{n-1}$。
5. 结果：$\binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1} \binom{2n}{n}$。
6. 结论：这就是第 $n$ 个卡特兰数 $C_n$。

答案

$C_n = \frac{1}{n+1} \binom{2n}{n}$

例题 2：双计数证明恒等式

证明

$$\sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}.$$

点击查看解析与答案

考虑集合 $S=\{(A,x)\mid A\subseteq[n],\ x\in A\}$ 的元素个数。

1. 按子集大小计数：若 $|A|=k$，则贡献 $k$ 个有序对，总数为

$$\sum_{k=0}^{n}k\binom{n}{k}.$$

2. 按元素计数：固定 $x$，含 $x$ 的子集有 $2^{n-1}$ 个；$x$ 有 $n$ 种，总数为 $n2^{n-1}$。

两种计数相等，结论成立。

例题 3：抽屉原理的同余模型

证明：任取 $n+1$ 个整数，必存在两个整数之差能被 $n$ 整除。

点击查看解析与答案

按模 $n$ 余数分类，只有 $n$ 个余数类：$0,1,\dots,n-1$。任取 $n+1$ 个整数，至少两个同余（抽屉原理）。同余两数之差可被 $n$ 整除，命题得证。

例题 4：递推求闭式

定义数列 $a_0=1$，且 $a_n=2a_{n-1}+1\ (n\ge1)$。求 $a_n$。

点击查看解析与答案

构造平移量 $b_n=a_n+1$，则

$$b_n=(a_n+1)=2a_{n-1}+2=2b_{n-1},\quad b_0=2.$$

故 $b_n=2^{n+1}$，从而

$$a_n=2^{n+1}-1.$$

例题 5：容斥原理的应用 (High Difficulty)

求 $1, 2, \dots, 1000$ 中不能被 5, 6, 8 中任何一个数整除的整数个数。

点击查看解析与答案

解析过程

设 $S = \{1, 2, \dots, 1000\}$，$A$ 为被 5 整除的集合，$B$ 为被 6 整除的集合，$C$ 为被 8 整除的集合。 我们需要计算 $|S| - |A \cup B \cup C|$。

1. 单个集合大小：$|A| = \lfloor 1000/5 \rfloor = 200$, $|B| = \lfloor 1000/6 \rfloor = 166$, $|C| = \lfloor 1000/8 \rfloor = 125$。
2. 两两相交：
   • $|A \cap B| = \lfloor 1000/\operatorname{lcm}(5,6) \rfloor = \lfloor 1000/30 \rfloor = 33$。
   • $|A \cap C| = \lfloor 1000/\operatorname{lcm}(5,8) \rfloor = \lfloor 1000/40 \rfloor = 25$。
   • $|B \cap C| = \lfloor 1000/\operatorname{lcm}(6,8) \rfloor = \lfloor 1000/24 \rfloor = 41$。
3. 三者相交：
   • $|A \cap B \cap C| = \lfloor 1000/\operatorname{lcm}(5,6,8) \rfloor = \lfloor 1000/120 \rfloor = 8$。
4. 计算并集：$|A \cup B \cup C| = (200+166+125) - (33+25+41) + 8 = 491 - 99 + 8 = 400$。
5. 结果：$1000 - 400 = 600$。

答案

600

---

三、 配套练习

练习 1（基础）

证明：

$$\sum_{k=0}^{n}\binom{n}{k}=2^n.$$

点击查看过程与答案

把 $[n]$ 的所有子集按大小分类计数，左式是分类计数，右式是每个元素选/不选共 $2^n$ 个子集。

练习 2（提高）

证明：任意 6 个整数中，必有两个数之和是偶数。

点击查看过程与答案

整数按奇偶分两类。取 6 个数，至少 3 个同类；同类中任取 2 个，和为偶数。

练习 3（提高）

设连通平面图有 $V$ 个顶点、$E$ 条边、$F$ 个面。若每个面边数至少为 3，证明

$$E\le 3V-6\quad (V\ge 3).$$

点击查看过程与答案

由面边计数得 $3F\le2E$。再由欧拉公式 $V-E+F=2$ 得

$$2=V-E+F\le V-E+\frac{2E}{3}=V-\frac{E}{3}.$$

故 $E\le3V-6$。

练习 4（挑战）

设 $n\ge1$，证明

$$\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0.$$

点击查看过程与答案

由二项式定理

$$(1-1)^n=\sum_{k=0}^n\binom{n}{k}1^{n-k}(-1)^k=0.$$

因此结论成立。

练习 5（高难度 - 错位排列）

5 个人把帽子扔进黑箱，每人随机取回一个。求恰有 2 个人拿对帽子的方案数。

点击查看过程与答案

1. 先选出拿对帽子的 2 个人：$\binom{5}{2} = 10$ 种方案。
2. 剩下 3 个人必须全部拿错，即进行错位排列：$D_3$。
3. $D_3 = 3!(1 - 1 + 1/2 - 1/6) = 6 \cdot (1/3) = 2$。
4. 总方案数：$10 \cdot 2 = 20$。

答案：20