初等组合与竞赛组合定理总目录

1. 加法原理入门

若一个任务可由若干种互不相交的方法完成，且第 \(i\) 类方法有 \(a_i\) 种，则总方法数为

\[ a_1+a_2+\cdots+a_n. \]

前置：有限集合基数概念。

定理解释：当一个任务被分成若干个互不重叠的类别时，总数就是把每一类的方法数直接加起来。关键点在于“互不相交”。

示例：从甲、乙、丙三条不同路线中选一条回家，若三条路线分别有 2、3、4 种走法，则总走法数为 \(2+3+4=9\)。

示例解释：因为每次只走其中一类路线，三类情况彼此不重叠，所以直接相加。

2. 乘法原理入门核心

若一个任务分成 \(n\) 个步骤，第 \(i\) 步有 \(a_i\) 种选法，则总方法数为

\[ a_1a_2\cdots a_n. \]

前置：有序选择、笛卡尔积基数。

定理解释：当一个任务必须按步骤连续完成时，总数要把每一步的选择数相乘。它描述的是“先做这件，再做那件”的情形。

示例：从 4 件上衣中选 1 件，再从 3 条裤子中选 1 条，则搭配方法数为 \(4\times 3=12\)。

示例解释：上衣选定后，裤子仍有 3 种可能；每件上衣都能和 3 条裤子搭配，所以总数是乘法。

3. 补集计数

若总数为 \(N\)，不合法对象数为 \(M\)，则合法对象数为

\[ N-M. \]

前置：集合补集、加法原理。

定理解释：有些正面直接数很麻烦，但“总数减去坏情况”反而更容易。这就是补集思想，也是组合里最常见的转化之一。

示例：5 位二进制串共有 \(2^5=32\) 个，其中全 0 只有 1 个，所以至少出现一个 1 的串有 \(32-1=31\) 个。

示例解释：直接去数“至少一个 1”不如反过来数“不含 1”，因为坏情况只有一个。

4. 分类计数与分步计数

复杂计数问题常可拆为“按类别求和”或“按步骤求积”。

\[ \#X=\sum_i \#X_i,\qquad \#Y=\prod_i a_i. \]

前置：加法原理、乘法原理。

定理解释：很多题不属于纯粹的“只加”或“只乘”，而是要先分类，再分步；或者先分步，再分类。会拆问题，本身就是组合的核心能力。

示例：求三位数中各位数字和为 5 的个数，可以按百位取值分类，再数后两位的分配。

示例解释：因为百位不能为 0，所以直接统一处理不方便；先按百位分类后，每一类都变成更简单的小问题。

5. 一一对应保数原则

若集合 \(A,B\) 间存在双射，则

\[ |A|=|B|. \]

前置：集合、函数、双射概念。

定理解释：如果两个对象集合能一一对应起来，那么它们的个数就一样。很多漂亮的组合证明，本质上就是在构造这种对应。

示例：从 \(n\) 个元素中选 \(k\) 个，与从同一集合中删去 \(k\) 个元素后一一对应，因此 \(\binom{n}{k}=\binom{n}{n-k}\)。

示例解释：选出 \(k\) 个元素，等价于留下 \(k\) 个元素，也等价于删去其余 \(n-k\) 个元素，所以两边计数相等。

6. 双计数原理中档核心

同一对象集按两种方式计数，所得结果相等。

\[ \sum_{x\in X} f(x)=\sum_{y\in Y} g(y). \]

前置：加法原理、集合划分。

定理解释：双计数的核心是：同一批对象，不同角度去数，答案必须一样。它是许多组合恒等式和图论结论的来源。

示例：在一个含 \(m\) 条边的图中，所有顶点度数之和等于 \(2m\)。

示例解释：按边看，每条边贡献 2 个端点；按点看，每个点贡献自己的度数。两种数法都在数“边端点总数”。

7. 排列数公式

\[ A_n^k=\frac{n!}{(n-k)!}. \]

前置：乘法原理、有序选择。

定理解释：排列数研究的是：从 \(n\) 个不同对象中，按顺序取出 \(k\) 个，一共有多少种不同取法。这里“按顺序”非常关键，因为先选谁、后选谁，会被看成不同结果。所以这个问题本质上是一个分步计数问题：第一步选第一个位置，有 \(n\) 种；第二步选第二个位置，剩下 \(n-1\) 种； ……；第 \(k\) 步选第 \(k\) 个位置，剩下 \(n-k+1\) 种。因此总数为 \[ n(n-1)\cdots(n-k+1), \] 这正好可以写成 \[ \frac{n!}{(n-k)!}. \] 这个公式可以理解为“从 \(n!\) 里截出前 \(k\) 个递减因子”。它是排列组合里最基础的计数公式之一，也是后面组合数、多项式系数等内容的起点。

示例：从 5 个人中选出 3 人排成一列，有 \[ A_5^3=5\times4\times3=60 \] 种。

示例解释：第一位可以从 5 个人中任选 1 人；选完以后，第二位只能从剩下的 4 个人里选；再选完以后，第三位只能从剩下的 3 个人里选。所以总数是 \[ 5\times4\times3=60. \] 注意这里如果只是“选 3 个人组成小组”，那就不是排列，而是组合，因为顺序已经不重要了。所以排列数的本质特征就是：**同样的人，只要次序不同，就算不同方案。**

8. 组合数公式

\[ \binom{n}{k}=\frac{n!}{k!(n-k)!}. \]

前置：排列与无序选择、除重思想。

定理解释：组合数研究的是：从 \(n\) 个不同对象中，不计顺序地选出 \(k\) 个，一共有多少种选法。和排列不同，这里只关心“选了哪些对象”，不关心它们的先后顺序。因此一个自然想法是：先按排列数来算，再把那些只是顺序不同、但本质上属于同一组的情况合并。从 \(n\) 个对象中取出 \(k\) 个并排好顺序，共有 \[ A_n^k=\frac{n!}{(n-k)!} \] 种。但对于任意一组固定的 \(k\) 个对象，它们内部可以互换顺序，共有 \[ k! \] 种排列，而这些排列在组合意义下其实都代表同一个集合。所以组合数应当是排列数再除以 \(k!\)，于是得到 \[ \binom{n}{k}=\frac{n!}{k!(n-k)!}. \] 这条公式的核心思想，就是“先多算，再除重”。

示例：从 5 个人中选 2 个人组成小组，有 \[ \binom52=10 \] 种。

示例解释：如果先按顺序选两个人，那么有 \[ A_5^2=5\times4=20 \] 种。但比如“甲乙”和“乙甲”在组成小组这件事里并没有区别，所以每一组被重复计算了 \[ 2!=2 \] 次。因此真实的无序选法应为 \[ \frac{20}{2}=10. \] 这正体现了组合与排列最本质的区别：**排列看顺序，组合不看顺序。**

9. Pascal 恒等式

\[ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}. \]

前置：组合数定义、分类讨论、固定元素思想。

定理解释： Pascal 恒等式是组合数最核心的递推关系之一。它告诉我们：从 \(n\) 个元素中选 \(k\) 个，可以按照某个固定元素“选不选”来分成两类。设这个固定元素是最后一个元素。那么所有的 \(k\) 元子集要么不包含它，要么包含它。若不包含它，就只能从剩下的 \(n-1\) 个元素中选 \(k\) 个，共有 \[ \binom{n-1}{k} \] 种；若包含它，那么还需要从其余 \(n-1\) 个元素中再选 \(k-1\) 个，共有 \[ \binom{n-1}{k-1} \] 种。两类互不重叠，合起来就是全部情况，所以得到 \[ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}. \] 这条恒等式不仅是 Pascal 三角形的来源，也是在证明很多组合恒等式和递推公式时最基础的工具之一。

示例： \[ \binom52=\binom42+\binom41=6+4=10. \]

示例解释：例如从 5 个人里选 2 个人，固定看第 5 个人。如果不选他，那么就在前 4 个人里选 2 人，有 \[ \binom42=6 \] 种；如果选他，那么还要从前 4 个人里再选 1 人，有 \[ \binom41=4 \] 种。这两类加起来就是总数 \[ 6+4=10. \] 所以 Pascal 恒等式背后的直觉非常简单：**把一个计数问题按某个固定对象是否出现来拆成两半。**

10. 对称性公式

\[ \binom{n}{k}=\binom{n}{n-k}. \]

前置：组合数定义、补集思想、一一对应。

定理解释：这条公式说明：从 \(n\) 个元素中选出 \(k\) 个，与从 \(n\) 个元素中舍去 \(n-k\) 个，本质上是同一件事。选中一组 \(k\) 元子集以后，它的补集自然是一个 \(n-k\) 元子集；反过来，给定一个 \(n-k\) 元子集，它的补集也唯一对应一个 \(k\) 元子集。因此两类对象之间存在天然的一一对应，所以数量相同。这条公式看起来简单，但非常重要，因为它说明组合数在 Pascal 三角形中左右对称，也常常能把一个不好算的问题转成一个更方便的参数形式。

示例： \[ \binom73=\binom74=35. \]

示例解释：从 7 个元素里选 3 个，等价于从 7 个元素里删去 4 个；这两种操作最后都唯一确定同一个子集。所以“选 3 个”的方案数，和“删 4 个”的方案数完全一样。这就是为什么 \[ \binom73=\binom74. \] 从直观上看，这条对称性也说明：组合数并不是单纯地随着 \(k\) 增大而一直变化，而是围绕中间层对称分布的。

11. 多项式系数

\[ \binom{n}{a_1,a_2,\dots,a_r}=\frac{n!}{a_1!a_2!\cdots a_r!}, \qquad a_1+\cdots+a_r=n. \]

前置：排列数、分组思想、组合数的推广。

定理解释：多项式系数可以看作组合数的自然推广。普通组合数 \(\binom{n}{k}\) 只是把 \(n\) 个对象分成两组：一组大小为 \(k\)，另一组大小为 \(n-k\)。而多项式系数则允许把 \(n\) 个不同对象分成 \(r\) 组，且各组大小分别固定为 \[ a_1,a_2,\dots,a_r. \] 若先把这 \(n\) 个对象排成一列，有 \(n!\) 种排法；但由于同一组内部的顺序不重要，所以第 1 组内部要除以 \(a_1!\)，第 2 组内部要除以 \(a_2!\)，……，第 \(r\) 组内部要除以 \(a_r!\)。因而总方法数为 \[ \frac{n!}{a_1!a_2!\cdots a_r!}. \] 这个量也正是多项式展开中对应项的系数，所以叫作“多项式系数”。

示例：把 5 个不同球分成 \(2,2,1\) 三组，有 \[ \frac{5!}{2!2!1!}=30 \] 种。

示例解释：若先把 5 个球全部排成一行，则有 \[ 5! \] 种排法。但如果前两个球属于同一组，那么它们交换顺序并不会改变分组结果，所以这一组内部多算了 \(2!\) 次；第二个 2 人组同理，也多算了 \(2!\) 次；单独那一组只有 1 个元素，不需要调整。因此要除以 \[ 2!2!1!. \] 这个公式在“分组”“颜色分配”“多项式展开系数”等问题里都非常常见。

12. 圆排列公式

将 \(n\) 个互异对象排成一圈的方法数为

\[ (n-1)!. \]

前置：排列数、旋转等价、等价类思想。

定理解释：在线性排列中，顺序从左到右完全固定，因此 \(n\) 个对象共有 \(n!\) 种排法。但在圆排列中，整体转动一圈不会产生新排法，因为相对位置并没有改变。也就是说，一个圆排列在写成线性序列时，会因为起点不同而对应出 \(n\) 个看似不同、实际上完全相同的表示。因此圆排列的总数应当把线性排列数 \[ n! \] 再除以 \(n\)，得到 \[ \frac{n!}{n}=(n-1)!. \] 这条公式本质上是在“按旋转去重”。所以它和普通排列最大的不同就在于：**绝对起点不重要，只看相对次序。**

示例： 4 个人围成一圈坐，有 \[ (4-1)!=6 \] 种。

示例解释：若按直线排，4 个人共有 \[ 4!=24 \] 种。但例如 \[ A,B,C,D;\quad B,C,D,A;\quad C,D,A,B;\quad D,A,B,C \] 这 4 个线性表示，在围成一圈时其实是同一种排法，因为它们只是整体转动了而已。因此每一个圆排列在直线表示里都会被重复数 \(4\) 次，所以真实的圆排列数应为 \[ \frac{24}{4}=6. \] 这就是圆排列公式的来源。

13. 可重组合（插板法）常用

非负整数解个数

\[ x_1+x_2+\cdots+x_r=n \]

等于

\[ \binom{n+r-1}{r-1}. \]

前置：组合数、隔板法、相同物品分配。

定理解释：这个公式研究的是：把 \(n\) 个完全相同的物品分给 \(r\) 个人或 \(r\) 个盒子，允许有人一个也分不到，那么分配方法共有多少种。设第 \(i\) 个人分到 \(x_i\) 个物品，那么问题就转化成求非负整数解个数 \[ x_1+x_2+\cdots+x_r=n. \] 插板法的思想是：先把 \(n\) 个相同物品排成一排，把它们看成 \(n\) 个球；然后用 \(r-1\) 块板把它们切成 \(r\) 段，每一段长度就是对应的 \(x_i\)。于是问题变成：在总共 \[ n+r-1 \] 个位置里，选出 \(r-1\) 个位置放板。因此方法数就是 \[ \binom{n+r-1}{r-1}. \] 这条公式是竞赛组合里极高频的工具之一，凡是“相同物品分配”或“非负整数解计数”几乎都会想到它。

示例：非负整数解 \[ x_1+x_2+x_3=5 \] 的个数为 \[ \binom{7}{2}=21. \]

示例解释：这里可以把 5 个单位写成 \[ \circ\ \circ\ \circ\ \circ\ \circ \] ，再插入 2 块板，把它们分成 3 段。比如 \[ \circ\ \circ\ |\ |\ \circ\ \circ\ \circ \] 就对应 \[ x_1=2,\quad x_2=0,\quad x_3=3. \] 因为一共有 5 个球和 2 块板，共 7 个位置，选择其中 2 个位置放板即可，所以总方法数是 \[ \binom72=21. \] 这也说明：允许某个变量为 0，本质上就是允许某一段长度为 0。

14. 正整数解个数

正整数解个数

\[ x_1+x_2+\cdots+x_r=n,\qquad x_i\ge 1 \]

等于

\[ \binom{n-1}{r-1}. \]

前置：可重组合、变量平移、插板法。

定理解释：和前一条不同，这里要求每个变量都至少为 1，也就是说每一份都不能为空。处理这种条件时，最常见的方法是先给每个变量“保底分配”一个单位。设 \[ y_i=x_i-1, \qquad y_i\ge 0, \] 那么原方程 \[ x_1+x_2+\cdots+x_r=n \] 就变成 \[ y_1+y_2+\cdots+y_r=n-r. \] 这时问题已经化成一个标准的非负整数解计数问题，因此答案为 \[ \binom{(n-r)+r-1}{r-1}=\binom{n-1}{r-1}. \] 所以这条公式的本质，就是把“正整数限制”通过平移转换成“非负整数限制”。

示例：正整数解 \[ x_1+x_2+x_3=5 \] 的个数为 \[ \binom42=6. \]

示例解释：因为每个变量都至少为 1，所以先令 \[ y_1=x_1-1,\quad y_2=x_2-1,\quad y_3=x_3-1. \] 那么 \[ y_1+y_2+y_3=2,\qquad y_i\ge0. \] 于是答案就变成非负整数解个数： \[ \binom{2+3-1}{3-1}=\binom42=6. \] 从插板法角度也可以理解为：因为每一段都必须至少有一个球，所以先把 5 个球中拿出 3 个，分别放进三段里保底；剩下 2 个球再自由分配。所以这条公式本质上是前一条公式的一个直接变形。

15. 二项式定理基础核心

\[ (x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k. \]

前置：组合数、乘法原理。

定理解释：展开 \((x+y)^n\) 时，每个因子都要从 \(x\) 与 \(y\) 中选一个。若最终有 \(k\) 个 \(y\)，就有 \(n-k\) 个 \(x\)，而出现这种情况的方法数正是 \(\binom{n}{k}\)。

示例：\[ (x+y)^3=x^3+3x^2y+3xy^2+y^3. \]

示例解释：例如 \(x^2y\) 这一项表示 3 个括号中有 1 个括号取 \(y\)、其余取 \(x\)，位置有 \(\binom31=3\) 种。

16. Vandermonde 恒等式

\[ \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}. \]

前置：组合数、双计数。

定理解释：从两堆元素（第一堆 \(m\) 个，第二堆 \(n\) 个）里共选出 \(r\) 个，可以按“从第一堆选了多少个”来分类。

示例：\[ \binom31\binom42+\binom32\binom41+\binom33\binom40=\binom73. \]

示例解释：从 3 个红球和 4 个蓝球中共选 3 个，既可以按颜色分类去数，也可以直接从 7 个球里选 3 个去数。

17. Hockey-stick 恒等式

\[ \binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}=\binom{n+1}{r+1}. \]

前置：Pascal 恒等式。

定理解释：这条恒等式在 Pascal 三角形中呈“冰球杆”形状，所以得名。它表示一串斜向组合数求和，可以压成一个更大的组合数。

示例：\[ \binom22+\binom32+\binom42+\binom52=\binom63. \]

示例解释：左边是 \(1+3+6+10=20\)，右边 \(\binom63=20\)。它也能用不断应用 Pascal 恒等式来理解。

18. 二项式求和

\[ \sum_{k=0}^{n}\binom{n}{k}=2^n, \qquad \sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}. \]

前置：二项式定理、求导或组合计数。

定理解释：第一式表示：每个元素都可选可不选，所以所有子集个数是 \(2^n\)。第二式表示：统计所有子集中“元素出现的总次数”。

示例：当 \(n=3\) 时，\(\binom30+\binom31+\binom32+\binom33=8\)。

示例解释：因为 3 元集合共有 \(2^3=8\) 个子集。第二个公式则可以理解成：每个固定元素在一半子集中出现，所以总贡献为 \(n2^{n-1}\)。

19. 交错二项式和

\[ \sum_{k=0}^{n}(-1)^k\binom{n}{k}=0 \quad (n\ge 1). \]

前置：二项式定理。

定理解释：把二项式定理中的 \(x=1,y=-1\) 代入，就得到这个交错和为 0。它反映了偶数大小子集与奇数大小子集数量相同。

示例：当 \(n=4\) 时，\(1-4+6-4+1=0\)。

示例解释：这正是 \((1-1)^4=0\) 的展开式。也可理解成：4 元集合的偶数子集数与奇数子集数一样多。

20. 平方和恒等式

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

前置：Vandermonde 恒等式。

定理解释：从两个各有 \(n\) 个元素的集合中一共选 \(n\) 个，若第一堆选了 \(k\) 个，则第二堆必须选 \(n-k\) 个，于是得到平方和形式。

示例：当 \(n=2\) 时，\[ \binom20^2+\binom21^2+\binom22^2=1+4+1=6=\binom42. \]

示例解释：左边看似是代数恒等式，实则是一个非常典型的双计数：从两组共 4 个元素中选 2 个。

21. 吸收恒等式

\[ k\binom{n}{k}=n\binom{n-1}{k-1}. \]

前置：组合数公式。

定理解释：这条式子常用于把“乘一个 \(k\)”变成“改一下组合数参数”。本质上是在数“选出一个 \(k\) 元子集后，再在其中指定一个特殊元素”的方法数。

示例：\[ 2\binom52=5\binom41. \]

示例解释：左边表示先从 5 人中选 2 人，再在这 2 人中指定一人；右边表示先指定这个特殊人，再从剩下 4 人中选 1 人配成一组。

22. 两集合容斥

\[ |A\cup B|=|A|+|B|-|A\cap B|. \]

前置：集合运算、加法原理。

定理解释：直接把 \(|A|\) 和 \(|B|\) 相加时，交集部分被数了两次，因此要减去一次。

示例：班里会英语的有 20 人，会法语的有 15 人，同时会两种语言的有 6 人，则至少会一种语言的有 \(20+15-6=29\) 人。

示例解释：那 6 个都会的人在“会英语”和“会法语”里各算过一次，所以总和里重复了。

23. 三集合容斥

\[ |A\cup B\cup C| =|A|+|B|+|C| -|A\cap B|-|B\cap C|-|C\cap A| +|A\cap B\cap C|. \]

前置：两集合容斥。

定理解释：三集合时，先把单集合加起来，再减去所有两两交集；但这一步会把三重交集减多一次，所以最后要再补回来。

示例：若 \(|A|=10,|B|=12,|C|=9\)，两两交分别是 3、4、2，三者交是 1，则并集大小为 \(10+12+9-3-4-2+1=23\)。

示例解释：三重交集最开始被加了 3 次，减两两交时又减了 3 次，最后变成 0 次，所以还要再加 1 次。

24. 一般容斥原理核心

\[ \left|\bigcup_{i=1}^{n}A_i\right| =\sum |A_i|-\sum |A_i\cap A_j| +\sum |A_i\cap A_j\cap A_k| -\cdots+(-1)^{n+1}\left|\bigcap_{i=1}^{n}A_i\right|. \]

前置：数学归纳法、集合运算。

定理解释：一般容斥就是“单个集合加、两两交减、三重交加……”这样交替下去。它解决的是多个条件同时出现时的重复计数问题。

示例：求 \(1\) 到 \(100\) 中能被 \(2\) 或 \(3\) 或 \(5\) 整除的数的个数，就可以用容斥来做。

示例解释：先数能被 2、3、5 整除的，再减去能被 6、10、15 整除的，最后补回能被 30 整除的。

25. 错排公式

记错排数为 \(D_n\)，则

\[ D_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}. \]

\[ D_n=(n-1)(D_{n-1}+D_{n-2}). \]

前置：容斥原理、递推。

定理解释：错排问题要求每个元素都不回到原位，是容斥原理的经典应用；递推式则来自考察第一个元素换到了哪里。

示例：\(n=3\) 时，\(D_3=2\)。

示例解释：3 个元素的错排只有 \((2,3,1)\) 与 \((3,1,2)\) 两种；任何有元素留在原位的排列都不算。

26. 满射计数公式

从 \(n\) 元集合到 \(m\) 元集合的满射个数为

\[ \sum_{k=0}^{m}(-1)^k\binom{m}{k}(m-k)^n. \]

前置：容斥原理、函数计数。

定理解释：总函数数是 \(m^n\)。若要求满射，就要排除“至少有一个值域元素没被用到”的函数，因此自然引出容斥。

示例：从 3 元集合到 2 元集合的满射个数为 \(2^3-\binom21 1^3=8-2=6\)。

示例解释：一共 8 个函数；若不是满射，则只落到单个元素上，这样的函数共有 2 个，所以满射有 6 个。

27. 基本抽屉原理入门核心

若将 \(n+1\) 个物体放入 \(n\) 个抽屉，则至少有一个抽屉中不少于 \(2\) 个物体。

前置：整数大小比较。

定理解释：位置不够分时，重复一定会发生。它是最基础、也最常用的存在性结论之一。

示例：把 13 个人分到 12 个月份里，至少有两个人出生在同一个月。

示例解释：因为月份只有 12 个“抽屉”，而人有 13 个，必然有一个月份里至少装下 2 个人。

28. 广义抽屉原理

若将 \(N\) 个物体放入 \(m\) 个抽屉，则至少有一个抽屉中物体数不少于

\[ \left\lceil \frac{N}{m}\right\rceil. \]

前置：整除与上取整。

定理解释：如果想让每个抽屉都尽量少装，那么最理想也是尽量平均分配；这样仍然会有一个抽屉至少达到平均数的上取整。

示例：把 100 个球放入 9 个盒子，至少有一个盒子中不少于 \(\lceil 100/9\rceil=12\) 个球。

示例解释：若每个盒子都至多 11 个，那么总数最多 \(9\times11=99\)，还装不下 100 个球，所以至少有一个盒子达到 12 个。

29. Erdős–Szekeres 单调子序列定理经典

任意 \(n^2+1\) 个互异实数构成的序列中，必存在长度至少 \(n+1\) 的单调递增子序列或单调递减子序列。

前置：抽屉原理、序列比较思想。

定理解释：这条定理说明：一个足够长的序列，不可能同时“没有很长的上升子序列”又“没有很长的下降子序列”。规模一大，结构必然出现。

示例：任意 10 个互异实数组成的序列中，一定存在长度至少 4 的单调递增子序列或单调递减子序列。

示例解释：因为这里取 \(n=3\)，有 \(n^2+1=10\)。所以只要序列长度达到 10，就必定出现一个长度至少 4 的单调子序列。

31. Fibonacci 递推

\[ F_n=F_{n-1}+F_{n-2},\qquad F_0=0,\ F_1=1. \]

前置：递推定义、分类讨论、最后一步分析。

定理解释： Fibonacci 递推是最经典、也最值得孩子反复体会的一类递推关系。它的核心思想不是“背公式”，而是学会看出：一个长度为 \(n\) 的结构，往往可以按“最后一段长什么样”分成两类，而这两类正好分别对应规模更小的两个同类问题。于是，大问题就自然拆成前两个小问题之和。这类递推最常出现在：铺砖、台阶、禁邻选择、线性串构造、二元串限制等题型中。它传达的一个非常重要的组合思想是：把复杂对象按最后一步拆开。在竞赛组合里，很多看上去花样很多的题，最后本质上都在做类似的事情，只不过拆分方式不一定恰好是“前一项 + 前两项”而已。

示例：用 \(1\times1\) 和 \(1\times2\) 小砖铺满长度为 \(n\) 的线段，设方案数为 \(a_n\)。则有 \[ a_n=a_{n-1}+a_{n-2}. \]

示例解释：因为最右边最后一块只有两种可能：第一种，最后放的是一块 \(1\times1\) 小砖，那么前面剩下长度 \(n-1\) 的部分，有 \(a_{n-1}\) 种铺法；第二种，最后放的是一块 \(1\times2\) 小砖，那么前面剩下长度 \(n-2\) 的部分，有 \(a_{n-2}\) 种铺法。这两类情况互不重叠，而且已经把所有可能都分完了，所以总方案数就是两者相加。这正是 Fibonacci 递推最标准、最直观的来源。

32. 线性齐次递推的一般形式

若数列满足

\[ a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}, \]

则称其为常系数线性齐次递推数列。

前置：递推、代数基本知识、数列表示。

定理解释：这是一大类非常重要的递推模型。它的意思是：当前这一项 \(a_n\)，可以由前面有限项按固定系数线性组合出来。 “线性”表示没有 \(a_{n-1}^2\)、\(a_{n-1}a_{n-2}\) 这类乘积项； “齐次”表示右边没有额外常数项或独立函数项； “常系数”表示 \(c_1,c_2,\dots,c_k\) 不随 \(n\) 改变。这一类递推在组合中非常常见，因为很多计数对象的构造，只依赖于前几步的状态，而这种依赖方式往往又是“分类后直接相加”。从学习角度看，它是 Fibonacci 递推的推广版：Fibonacci 只是其中最简单的二阶特例。理解这一条，孩子就会慢慢意识到：递推并不是零散结论，而是一整套统一框架。

示例：若 \[ a_n=a_{n-1}+a_{n-3}, \] 那么这就是一个三阶线性齐次递推。

示例解释：这里虽然只出现了 \(a_{n-1}\) 和 \(a_{n-3}\)，没有出现 \(a_{n-2}\)，但它仍属于三阶递推，因为当前项的计算涉及最远到前三项。若写成统一格式，其实就是 \[ a_n=1\cdot a_{n-1}+0\cdot a_{n-2}+1\cdot a_{n-3}. \] 所以它完全落在线性齐次递推的一般框架中。这也是为什么很多时候“有没有出现某一项”并不重要，关键在于整个结构是不是“固定系数线性组合前若干项”。

33. 特征方程法

对形如

\[ a_n=c_1a_{n-1}+\cdots+c_ka_{n-k} \]

的递推，可设 \(a_n=r^n\)，得到特征方程

\[ r^k-c_1r^{k-1}-\cdots-c_k=0. \]

前置：线性递推、多项式、指数型试探。

定理解释：特征方程法是处理常系数线性齐次递推最经典的代数工具。它背后的想法非常自然：既然递推是“前几项的固定线性组合”，那么指数型数列 \(r^n\) 往往是最适合试探的对象，因为它往后平移一项，只会多乘一个固定因子 \(r\)。把 \(a_n=r^n\) 代入递推后，就能把一个“数列问题”压缩成一个“代数方程问题”。一旦找到所有特征根，再按根的情况拼出通解，就能把原来的递推数列写成显式公式。对孩子来说，这一步特别重要，因为它让“递推”从一种看似只能逐项往后推的关系，变成一种可以整体求解的对象。

示例： Fibonacci 递推 \[ F_n=F_{n-1}+F_{n-2} \] 的特征方程是 \[ r^2-r-1=0. \]

示例解释：因为设 \(F_n=r^n\)，代入得 \[ r^n=r^{n-1}+r^{n-2}. \] 两边同时除以 \(r^{n-2}\)（默认 \(r\neq 0\)），得到 \[ r^2=r+1, \] 也就是 \[ r^2-r-1=0. \] 这说明 Fibonacci 数列背后并不是“凭空出现”的，而是对应于两个特征根所生成的指数型解的线性组合。所以后面看到通项里出现 \(\left(\frac{1+\sqrt5}{2}\right)^n\) 这类式子，就不会觉得突兀了。

34. 二阶递推的通解结构

若

\[ a_n=pa_{n-1}+qa_{n-2}, \]

则其通解由特征方程 \(r^2-pr-q=0\) 的根决定。

前置：特征方程法、二次方程求根。

定理解释：二阶递推是最常见、也最容易系统掌握的一类线性递推。它的核心结论是：递推的解长什么样，完全取决于特征方程的根长什么样。若有两个不同实根 \(r_1,r_2\)，通解一般写成 \[ a_n=A r_1^n+B r_2^n; \] 若出现重根 \(r\)，则通解一般写成 \[ a_n=(A+Bn)r^n. \] 所以，根的重合与否，会直接决定通项结构有没有额外的 \(n\) 因子。这也是为什么在递推题里，“重根”总是一个特别值得单独记住的情况。

示例：若 \[ a_n=2a_{n-1}-a_{n-2}, \] 则特征方程为 \[ r^2-2r+1=0, \] 即 \[ (r-1)^2=0. \] 所以通解形如 \[ a_n=A+Bn. \]

示例解释：因为这里的唯一特征根是 \(r=1\)，而且是重根。若只有一个简单根 \(1\)，那么只会得到常数解 \(A\cdot1^n=A\)。但这不足以覆盖全部解，所以还必须补上一项 \(Bn\cdot1^n\)，也就是 \(Bn\)。因此通解变成 \[ a_n=A+Bn. \] 这一点和微分方程里“重根时要乘 \(n\)”是非常类似的。从结构上看，重根意味着递推解的自由度还没“填满”，于是需要多一个带 \(n\) 的项来补足。

35. Catalan 型递推思想

很多递推可由“按第一个结构块切分”得到卷积型公式。

\[ a_n=\sum_{k} a_k a_{n-1-k}. \]

前置：递推、分类讨论、组合拆分、卷积思想。

定理解释：这一类递推和 Fibonacci 型递推的区别在于：它不再只是“拆成前一项和前两项”，而是把一个对象拆成“左半边 + 一个中心结构 + 右半边”。一旦这个中心结构的位置不固定，就会出现对所有切分位置求和，于是形成卷积型递推。 Catalan 数列就是这类递推最有代表性的主角。它经常出现在：合法括号序列、二叉树、凸多边形三角剖分、Dyck 路径、不交弦匹配等题型中。从方法上说，它教孩子学会看： 一个对象能不能通过某个“第一关键结构”切开，切开后左右两部分是否独立。 一旦独立，乘法就会出现；一旦切分位置可变，求和就会出现。

示例：合法括号序列、二叉树个数、Dyck 路径个数都满足 Catalan 型递推。

示例解释：以合法括号序列为例，若总共有 \(n\) 对括号，最左边那个左括号一定会和某个右括号配对。一旦这个最外层配对确定下来，整个序列就被分成“里面一段”和“后面一段”两个互相独立的合法括号序列。假设里面用了 \(k\) 对括号，那么后面就用了 \(n-1-k\) 对括号，于是该种切分对应的方案数是 \[ a_k a_{n-1-k}. \] 把所有可能的 \(k\) 全部加起来，就得到卷积型递推。所以 Catalan 型递推真正的本质不是某个特定公式，而是“先找第一个关键结构，再把问题一刀切成两半”。

36. Stirling 数（第二类）递推

把 \(n\) 个元素划分成 \(k\) 个非空无序块的方式数记为 \(S(n,k)\)，则

\[ S(n,k)=S(n-1,k-1)+kS(n-1,k). \]

前置：集合划分、递推、分类讨论。

定理解释：第二类 Stirling 数 \(S(n,k)\) 数的是：把 \(n\) 个不同元素分成 \(k\) 个非空、彼此无序的块。这类递推特别适合训练孩子“新增一个元素时，原有结构怎样变化”的思路。这里新增的元素是 \(n\)。对于它，只有两种可能：要么它自己单独成一块；要么它加入到已有的某一块中。于是整个问题就被非常自然地分成两类，而且这两类一看就是递推。这条递推是集合划分问题中最基本、最经典的一条。

示例： \[ S(3,2)=3. \]

示例解释：把集合 \(\{1,2,3\}\) 分成 2 个非空块，只有以下三种： \[ \{1\}\{2,3\},\qquad \{2\}\{1,3\},\qquad \{3\}\{1,2\}. \] 若从递推角度看，也可以这样理解：先看元素 3。若 3 单独成一块，那么前面 \(\{1,2\}\) 必须分成 \(1\) 块，对应 \(S(2,1)\)；若 3 不单独成块，那就必须加入 \(\{1,2\}\) 已经分成的 2 块中的某一块，但这里 \(S(2,2)=1\)，且有 2 个块可选，所以贡献为 \(2S(2,2)\)。因而 \[ S(3,2)=S(2,1)+2S(2,2)=1+2=3. \]

37. Stirling 数（第一类）递推

把 \(n\) 个元素分解成 \(k\) 个轮换的方式数记为 \(c(n,k)\)，则

\[ c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k). \]

前置：排列的轮换分解、递推、插入思想。

定理解释：第一类 Stirling 数和第二类 Stirling 数名字很像，但数的对象完全不同。第二类是在数“集合如何分块”；第一类是在数“排列分解成多少个轮换”。因此它不是普通的集合划分问题，而是带有排列循环结构的问题。这条递推也来自对新增元素 \(n\) 的分析：要么 \(n\) 自己单独形成一个 1-轮换；要么 \(n\) 插入到原来某个轮换中的某个位置。因为 \(n-1\) 个旧元素在所有轮换里总共有 \(n-1\) 个可插位置，所以就得到 \((n-1)c(n-1,k)\) 这一项。

示例：在讨论排列的轮换结构时，常出现第一类 Stirling 数。

示例解释：例如要数 3 个元素的排列恰好分成 2 个轮换的个数，就已经是第一类 Stirling 数的问题。它和“把 3 个元素分成 2 块”不是一回事，因为这里每一块内部还带有轮换顺序信息。这也是为什么它的递推虽然长得和第二类 Stirling 数很像，但系数却不同：第二类是“加入某个块”，所以是 \(k\)；第一类是“插入某个轮换位置”，所以是 \(n-1\)。这一点特别值得孩子分清楚。

38. Bell 数递推

Bell 数 \(B_n\) 表示 \(n\) 元集合的全部划分数。

\[ B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}B_k. \]

前置：集合划分、第二类 Stirling 数、分类计数。

定理解释： Bell 数表示：一个 \(n\) 元集合一共能分成多少种不同的非空块划分。如果说第二类 Stirling 数 \(S(n,k)\) 是“固定块数”的划分，那么 Bell 数就是把所有可能的块数全部加总起来。它反映的是集合划分问题的“总复杂度”。这条递推的一个经典理解是：考虑新元素 \(n+1\) 所在的那个块里，除了它自己之外，还包含哪些旧元素。一旦选定这批元素，剩下的元素就可以任意划分，于是得到求和公式。这种“先盯住某个特殊元素所在的块”也是组合里非常典型的切入方式。

示例： \[ B_3=5. \]

示例解释：因为集合 \(\{1,2,3\}\) 的所有划分共有 5 种： \[ \{1,2,3\}, \qquad \{1\}\{2,3\}, \qquad \{2\}\{1,3\}, \qquad \{3\}\{1,2\}, \qquad \{1\}\{2\}\{3\}. \] 从递推角度理解 \(B_{n+1}\) 时，可以固定元素 \(n+1\)。假设它所在的块里还选了 \(n-k\) 个旧元素，那么剩下的 \(k\) 个元素可以任意划分，共有 \(B_k\) 种；而选出这 \(k\) 个“留在外面”的元素有 \(\binom{n}{k}\) 种方式。所以对所有 \(k\) 求和，就得到 \[ B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}B_k. \] 这条公式很好地体现了 Bell 数的本质：它是在对“所有块数、所有划分结构”做一次总汇总。

39. 普通生成函数定义

数列 \(\{a_n\}\) 的普通生成函数定义为

\[ A(x)=\sum_{n\ge0}a_nx^n. \]

前置：幂级数、数列。

定理解释：生成函数的思想是：把“第 \(n\) 项是多少”编码到 \(x^n\) 的系数里。于是数列问题能转化成函数恒等式问题。

示例：常数数列 \(1,1,1,\dots\) 的生成函数是 \(\frac1{1-x}\)。

示例解释：因为 \(\frac1{1-x}=1+x+x^2+\cdots\)，每个次数项的系数都正好是 1。

40. 等比级数生成函数

\[ 1+x+x^2+\cdots=\frac1{1-x}. \]

前置：等比数列。

定理解释：这是最基础的生成函数恒等式。很多复杂生成函数，都是由它变形叠加出来的。

示例：\[ 1+x^2+x^4+\cdots=\frac1{1-x^2}. \]

示例解释：把 \(x\) 替换成 \(x^2\)，就得到“偶数次数项都为 1、奇数次数项为 0”的生成函数。

41. 生成函数乘法对应卷积

若

\[ A(x)=\sum a_nx^n,\qquad B(x)=\sum b_nx^n, \]

则

\[ A(x)B(x)=\sum_{n\ge0}\left(\sum_{k=0}^{n}a_kb_{n-k}\right)x^n. \]

前置：多项式乘法、求和。

定理解释：生成函数相乘时，次数 \(n\) 的系数来自所有“次数和为 \(n\)”的配对，因此自然出现卷积和。

示例：两个独立选择步骤的总计数，常用乘法型生成函数描述。

示例解释：因为“前一部分贡献 \(k\)”与“后一部分贡献 \(n-k\)”的所有可能，都被系数卷积统一装进去了。

42. 插板法的生成函数解释

非负整数解

\[ x_1+\cdots+x_r=n \]

的计数等于

\[ [x^n]\left(\frac1{1-x}\right)^r=\binom{n+r-1}{r-1}. \]

前置：普通生成函数、二项式展开。

定理解释：每个变量 \(x_i\ge0\) 都对应一个生成函数 \(1+x+x^2+\cdots\)，多个变量相乘后，\(x^n\) 的系数就是总和为 \(n\) 的解数。

示例：\(x_1+x_2+x_3=4\) 的非负整数解数是 \([x^4](1-x)^{-3}\)。

示例解释：这和插板法的答案一致，只是换成了生成函数语言。

43. 指数生成函数的基本思想

数列 \(\{a_n\}\) 的指数生成函数定义为

\[ E(x)=\sum_{n\ge0}a_n\frac{x^n}{n!}. \]

前置：幂级数、阶乘。

定理解释：指数生成函数更适合处理“带标号对象”的计数，例如排列、集合划分、图等。

示例：集合划分和排列结构里，经常用指数生成函数而不是普通生成函数。

示例解释：因为带标号对象合并时会自然出现二项式系数，而 \(\frac1{n!}\) 正好能把这些组合因子处理得更整齐。

44. Euler 分拆生成函数

\[ \sum_{n\ge 0}p(n)x^n=\prod_{m\ge 1}\frac1{1-x^m}. \]

前置：生成函数、分拆定义。

定理解释：\(p(n)\) 是整数分拆数。每个因子 \(\frac1{1-x^m}=1+x^m+x^{2m}+\cdots\) 表示部分 \(m\) 可以用 0 次、1 次、2 次……

示例：要求 5 的分拆数，可以从这个无限乘积中取出 \(x^5\) 的系数。

示例解释：例如 \(5=2+2+1\) 对应从 \((1+x+x^2+\cdots)(1+x^2+x^4+\cdots)\cdots\) 中取 \(x\cdot x^4\)。

45. Euler 奇异分拆定理经典

“拆成互异部分的分拆数” 等于 “拆成奇数部分的分拆数”。

前置：分拆、生成函数或双射思想。

定理解释：这是分拆理论里最漂亮的恒等式之一。两类看起来完全不同的分拆，最后数量竟然相同。

示例：5 的互异部分分拆有：\(5,4+1,3+2\)；奇数部分分拆有：\(5,3+1+1,1+1+1+1+1\)，都是 3 种。

示例解释：这不是巧合，而是一般规律。可以用生成函数，也可以用专门的双射来证明。

46. 分拆共轭

Ferrers 图转置给出分拆共轭，因此“最大部分为 \(k\) 的分拆数” 等于 “恰有 \(k\) 个部分的分拆数”。

前置：Ferrers 图。

定理解释：把分拆画成点阵图后，沿主对角线翻转，就把“行信息”变成“列信息”，从而得到一个自然的对应。

示例：\(5=3+1+1\) 的 Ferrers 图共轭后对应 \(5=3+1+1\) 或 \(2+1+1+1\) 这类转置关系。

示例解释：“最大部分”对应图形的最长一行，“部分个数”对应图形的总行数；转置后它们交换角色。

47. Euler 五边形数定理偏难

\[ \prod_{m\ge 1}(1-x^m) = \sum_{k\in\mathbb Z}(-1)^k x^{k(3k-1)/2}. \]

前置：生成函数、分拆理论。

定理解释：这是分拆理论的一个核心恒等式。右边指数中的 \(k(3k-1)/2\) 是广义五边形数。

示例：它常用于推导分拆函数 \(p(n)\) 的递推公式。

示例解释：表面上这是一个乘积展开式，实际上它决定了分拆数列背后非常深的结构。

48. Catalan 数公式竞赛高频

\[ C_n=\frac1{n+1}\binom{2n}{n}=\binom{2n}{n}-\binom{2n}{n+1}. \]

前置：组合数、反射法或递推。

定理解释：Catalan 数计数很多“始终不越界”的结构，例如合法括号序列、Dyck 路径、满二叉树等。

示例：\(C_3=5\)。

示例解释：3 对括号的合法匹配共有 5 种，这也是 6 边形剖分成三角形的方法数。

49. Catalan 递推

\[ C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k},\qquad C_0=1. \]

前置：括号匹配、树分裂或路径分解。

定理解释：固定最外层结构后，内部和外部会分成两个独立部分，所以出现卷积递推。

示例：\[ C_3=C_0C_2+C_1C_1+C_2C_0=2+1+2=5. \]

示例解释：最外层括号包住多少对括号，会把问题拆成左右两部分，各自独立计数。

50. Bertrand 投票定理 / Ballot 定理

若候选人 \(A\) 得 \(p\) 票、\(B\) 得 \(q\) 票，且 \(p>q\)，则随机计票顺序中 \(A\) 始终领先的比例为

\[ \frac{p-q}{p+q}. \]

前置：路径计数、反射法。

定理解释：投票问题和格点路径一一对应，所以这个结果本质上是“不碰到对角线”的路径计数。

示例：若 \(A\) 有 5 票、\(B\) 有 3 票，则 \(A\) 始终领先的比例是 \(\frac{2}{8}=\frac14\)。

示例解释：每种计票顺序可看作一条向右向上的路径，“始终领先”对应路径始终在某条边界上方。

51. 反射原理

许多“越界路径数”可通过对越界后的第一段进行反射，与另一类路径建立双射。

前置：路径计数、一一对应。

定理解释：反射法是路径计数中的一把利器。它把“坏路径”转成另一类好数的对象，从而用总数减掉坏数。

示例：Catalan 数公式中的 \(\binom{2n}{n}-\binom{2n}{n+1}\) 就可由反射法得到。

示例解释：先数所有路径，再把第一次越界的坏路径反射，发现它们恰好和另一类路径等势。

52. 格点路径计数

从 \((0,0)\) 走到 \((m,n)\)，每步只向右或向上，则路径数为

\[ \binom{m+n}{m}=\binom{m+n}{n}. \]

前置：组合数、乘法原理。

定理解释：总共要走 \(m+n\) 步，只需决定其中哪 \(m\) 步是向右，剩下自然向上。

示例：从 \((0,0)\) 到 \((2,3)\) 的路径有 \(\binom52=10\) 条。

示例解释：一共 5 步，其中 2 步选作“向右”，其余 3 步自动是“向上”。

53. 子集按大小求和

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

前置：组合数、子集概念、加法原理与乘法原理。

定理解释：这是组合里最基础、也最重要的一条恒等式之一。它表示：一个 \(n\) 元集合的全部子集个数，既可以按“子集大小”来分层统计，也可以按“每个元素选或不选”来整体统计。如果按大小分层，那么恰有 \(k\) 个元素的子集个数就是 \[ \binom{n}{k}, \] 把 \(k=0,1,2,\dots,n\) 全部加起来，就得到所有子集总数： \[ \sum_{k=0}^{n}\binom{n}{k}. \] 而如果从另一个角度看，对于集合中的每一个元素，我们只有两种选择：选它，或者不选它。一共 \(n\) 个元素，每个元素都有 2 种状态，因此总子集数应当是 \[ 2\cdot 2\cdots 2=2^n. \] 这条恒等式的本质，就是对同一个对象集进行了两种不同的计数。它也是二项式定理在 \(x=y=1\) 时最直接的组合解释之一。

示例：一个 4 元集合共有 \[ 2^4=16 \] 个子集。同时也可以写成 \[ \binom40+\binom41+\binom42+\binom43+\binom44 =1+4+6+4+1=16. \]

示例解释：这里的意思是：空集有 1 个； 1 元子集有 4 个； 2 元子集有 6 个； 3 元子集有 4 个； 4 元子集有 1 个。这些子集加起来正好是全部子集。而另一种看法则更直接：4 个元素分别决定“取 / 不取”，因此共有 \(2^4=16\) 种可能。这就是一个非常典型的“双计数”例子：一边按层分类数，一边按独立选择数。

54. 子集元素总出现次数

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

前置：双计数、组合数、子集概念。

定理解释：这条恒等式研究的不是“有多少个子集”，而是“所有子集里一共出现了多少次元素”。更准确地说，我们把一个 \(n\) 元集合的全部子集都列出来，然后把每个子集中的元素个数加起来，最后得到的总和就是 \[ \sum_{k=0}^{n}k\binom{n}{k}. \] 为什么？因为大小为 \(k\) 的子集一共有 \(\binom{n}{k}\) 个，而每个这样的子集都会贡献 \(k\) 个元素，所以这一层总贡献是 \[ k\binom{n}{k}. \] 再把所有层加起来，就得到左边。另一方面，我们也可以固定一个元素来看：对于集合中的任意一个固定元素，它会出现在哪些子集中？只要先把这个元素选上，剩下的 \(n-1\) 个元素任意选或不选，所以它恰好出现在 \[ 2^{n-1} \] 个子集中。一共有 \(n\) 个元素，因此总出现次数就是 \[ n2^{n-1}. \] 这同样是一个非常漂亮的双计数恒等式。

示例：对于 3 元集合 \(\{a,b,c\}\)，全部子集中的“元素总出现次数”为 \[ 3\cdot 2^{2}=12. \] 也可以按公式写成 \[ 0\binom30+1\binom31+2\binom32+3\binom33 =0+3+6+3=12. \]

示例解释：例如元素 \(a\) 出现在这些子集中： \[ \{a\},\{a,b\},\{a,c\},\{a,b,c\}, \] 一共 4 次；同理 \(b,c\) 也各出现 4 次，所以总出现次数为 \[ 4+4+4=12. \] 另一方面，按子集大小分层来看： 1 元子集共有 3 个，总共贡献 3； 2 元子集共有 3 个，每个贡献 2，总共贡献 6； 3 元子集共有 1 个，贡献 3；加起来也是 12。所以这条恒等式的本质就是： **一边按“子集”数元素，一边按“元素”数子集。**

55. 平均值双计数思想

通过总计数除以对象数，常可得到平均度数、平均块大小、平均出现次数等信息。

前置：双计数、平均数、基本不等式思想。

定理解释：平均值双计数思想并不是某一条单独的公式，而是一类非常常见、非常实用的方法。它的基本套路是：先把某个“总量”用两种方式算出来，然后再除以对象总数，得到平均值。一旦得到了平均值，就往往能推出存在性结论：至少有一个对象不小于平均值，至少有一个对象不大于平均值；如果所有对象都严格小于平均值，那总量就不够；如果所有对象都严格大于平均值，那总量又会超出。所以“平均值”经常是从“总计数”通向“存在性”的桥梁。在组合与图论中，这个思路非常常见，比如平均度数、平均覆盖次数、平均块大小、平均交数等等，很多极值结论都是先从平均量入手。

示例：若一个图有 \(n\) 个顶点、\(m\) 条边，则平均度数为 \[ \frac{2m}{n}. \]

示例解释：因为根据握手定理，所有顶点度数之和等于 \[ 2m. \] 再除以顶点总数 \(n\)，就得到平均度数 \[ \frac{2m}{n}. \] 这马上能推出很多结论。例如，至少存在一个顶点的度数不小于 \(\frac{2m}{n}\)；否则如果每个顶点度数都小于这个数，那么总度数就会小于 \(2m\)，矛盾。同样，也至少有一个顶点度数不大于 \(\frac{2m}{n}\)。所以平均值双计数思想的常见作用，不只是“算平均数”，而是借平均数推出“某个特殊对象一定存在”。

56. 组合恒等式的计数证明法

许多代数恒等式都可以通过构造一个具体的计数模型来证明。

前置：一一对应、双计数、分类讨论。

定理解释：组合恒等式的计数证明法，是组合数学里最有代表性的思想之一。它的核心是：遇到一个看起来纯代数的恒等式时，不急着做代数变形，而是试着把它解释成“在数某一类对象的总个数”。如果恒等式两边都能解释成同一个计数问题的两种数法，那么这个恒等式就自然成立。这种证明方法的优点很大：第一，它通常比机械代数变形更直观；第二，它能告诉你“这个式子为什么会长这样”，而不只是“怎么算出来”；第三，它往往还能启发推广，因为一旦你理解了背后的对象模型，就知道类似问题应当如何构造。所以在组合数学里，很多恒等式最有价值的部分并不是式子本身，而是它背后的计数解释。

示例：经典恒等式 \[ \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r} \] 就可以理解成：从两堆元素里总共选出 \(r\) 个元素的方法数。

示例解释：设第一堆有 \(m\) 个元素，第二堆有 \(n\) 个元素。现在要从这两堆元素中总共选 \(r\) 个。如果直接选，那么方法数显然是 \[ \binom{m+n}{r}. \] 但也可以分类来数：假设从第一堆选了 \(k\) 个，那么就必须从第二堆选 \(r-k\) 个；这样的选法有 \[ \binom{m}{k}\binom{n}{r-k} \] 种。让 \(k\) 从 0 到 \(r\) 全部跑一遍，再把这些情况加起来，就得到左边。因为左右两边都在数同一件事，所以它们必然相等。这正是计数证明法最典型的样子： **一个恒等式之所以成立，不是因为“式子碰巧变得一样”，而是因为它们本来就在数同一个对象集。**

57. 偏序集与链、反链

在偏序集中，链指两两可比的子集，反链指两两不可比的子集。

前置：集合包含关系、偏序概念。

定理解释：链代表“完全排得出大小关系”，反链则代表“彼此谁也不包含谁”。

示例：在幂集 \(\mathcal P([n])\) 中，\(\varnothing\subset\{1\}\subset\{1,2\}\) 是链；所有大小同为 2 的子集构成反链。

示例解释：同大小集合不可能真包含彼此，所以天然构成反链。

58. Sperner 定理经典

\([n]\) 的子集族中，若任意两个集合互不包含，则其最大规模为

\[ \binom{n}{\lfloor n/2\rfloor}. \]

前置：反链、二项式系数。

定理解释：在布尔格里，最大的反链由“中间层”给出，也就是元素个数最接近 \(n/2\) 的那一层。

示例：当 \(n=4\) 时，最大反链大小是 \(\binom42=6\)。

示例解释：所有 2 元子集一共 6 个，任意两个都不互相包含，而且已经达到最大值。

59. LYM 不等式

若 \(\mathcal F\subseteq\mathcal P([n])\) 是反链，则

\[ \sum_{A\in\mathcal F}\frac1{\binom{n}{|A|}}\le 1. \]

前置：Sperner 定理、链分解思想、布尔格 \(\mathcal P([n])\) 的层结构。

定理解释： LYM 不等式是 Sperner 定理的一个加强版。 Sperner 定理只告诉我们：一个反链最多能有多少个集合；而 LYM 不等式更进一步，它不是只看“个数”，而是给每个集合赋了一个“权重” \[ \frac1{\binom{n}{|A|}}. \] 这些权重反映了集合所处层的位置：在布尔格 \(\mathcal P([n])\) 里，大小为 \(k\) 的集合都位于第 \(k\) 层，而这一层一共有 \(\binom{n}{k}\) 个元素。所以一个集合 \(A\) 对应的权重，其实可以理解为“它在自己所在层里所占的比例”。 LYM 不等式说明：如果 \(\mathcal F\) 是一个反链，那么它从各层“拿走”的这些比例，加起来不能超过 1。换句话说，反链虽然可以分散在不同层，但它在整个布尔格里的“总占比”有一个统一上界。这正是为什么说它比 Sperner 定理更强：Sperner 只是它的一个直接推论。

示例：若 \(\mathcal F\) 全由 2 元子集组成，则 \[ \sum_{A\in\mathcal F}\frac1{\binom{n}{|A|}} = \sum_{A\in\mathcal F}\frac1{\binom n2} = \frac{|\mathcal F|}{\binom n2}. \] 由 LYM 不等式可得 \[ \frac{|\mathcal F|}{\binom n2}\le 1, \qquad\text{从而}\qquad |\mathcal F|\le \binom n2. \]

示例解释：这说明：如果反链里的所有集合都集中在同一层，比如都恰好是 2 元集，那么 LYM 不等式就直接退化成这一层大小的上界。而当反链分布在不同层时，LYM 不等式就比单纯“看某一层最大”更有力量，因为它会把各层贡献统一加权控制起来。例如，若一个反链既取了一些 1 元集，又取了一些 2 元集，那么它们不能随便同时取很多个，因为 \[ \frac{\#\{\text{1 元集}\}}{\binom n1}+\frac{\#\{\text{2 元集}\}}{\binom n2}\le 1. \] 这就是 LYM 不等式真正厉害的地方：它给出的不是单层极值，而是跨层约束。

60. Dilworth 定理重要

有限偏序集中，最大反链大小等于最少链覆盖数。

前置：偏序、链、反链、覆盖的概念。

定理解释： Dilworth 定理是偏序理论里最核心的极值定理之一。它研究的是一个偏序集里两种完全相反的结构：一种是链，也就是元素之间两两可比；另一种是反链，也就是元素之间两两不可比。直观上，链体现的是“纵向层次”，反链体现的是“横向宽度”。 Dilworth 定理说：一个有限偏序集里，最大的“横向宽度”（最大反链大小），恰好等于把整个偏序集拆成若干条链所需的最少条数。也就是说，一个偏序到底“有多宽”，可以完全用“最少需要多少条纵向链来覆盖它”来刻画。这是一个非常漂亮的 min-max 结论。它的意义在于：反链看起来是在研究“不能比较的一群元素”，链覆盖看起来是在研究“怎样分层整理整个集合”，这两件事原本毫不相干，但 Dilworth 定理告诉我们，它们其实是同一个量的两种表达。

示例：设 \[ P=\{2,3,4,6,12\}, \] 并按整除关系定义偏序，即 \(a\le b\) 表示 \(a\mid b\)。那么： \[ 2<4<12,\qquad 3<6<12 \] 都是链；而集合 \[ \{3,4\} \] 是一个反链，因为 \(3\nmid 4\)，\(4\nmid 3\)。在这个偏序里，最大反链大小为 2，因此根据 Dilworth 定理，整个偏序集最少可以用 2 条链覆盖。

示例解释：这里的意思是：虽然这个偏序里有不少元素，但它最“宽”的地方只有 2，也就是最多只能找到 2 个两两不可比的元素。那么整个偏序集就一定能拆成 2 条链来覆盖，而且不可能只用 1 条链。例如一种覆盖方式可以是： \[ 2<4<12,\qquad 3<6. \] 这两条链已经覆盖了全部元素。而为什么不能只用 1 条链？因为偏序中存在反链 \(\{3,4\}\)，这两个元素彼此不可比，不可能同时放进同一条链里。所以最大反链大小给出了链覆盖数的下界，而 Dilworth 定理说，这个下界正好可以达到。这也是它在整除偏序、区间包含、序列分解等题里非常常用的原因：只要你能找出一个大的反链，就知道至少要多少条链；而 Dilworth 定理保证这个数其实也够了。

61. Mirsky 定理

有限偏序集中，最大链长度等于最少反链覆盖数。

前置：偏序、链、反链、Dilworth 思想。

定理解释： Mirsky 定理可以看作 Dilworth 定理的对偶版本。 Dilworth 定理研究的是：最大反链大小 = 最少链覆盖数； Mirsky 定理则研究：最大链长度 = 最少反链覆盖数。也就是说，如果说 Dilworth 把“宽度”与“链分解”联系起来，那么 Mirsky 就是把“高度”与“反链分层”联系起来。它告诉我们：一个偏序集里最长能排出多长的一条链，就恰好需要多少层反链，才能把整个集合分层覆盖掉。这条定理的直观意义很强：如果一个偏序集的最长链长度是 \(h\)，那么你至少要用 \(h\) 个反链来覆盖全部元素，因为同一个反链里任何两个元素都不能比较，所以一条长度为 \(h\) 的链中的 \(h\) 个元素必须分散到不同的反链中。 Mirsky 定理说，这个显然的下界其实总是可以达到。因此，“偏序的高度”正好等于“最少反链层数”。

示例：设偏序集为 \[ P=\mathcal P([3]) \] ，偏序关系是集合包含。那么有一条最长链 \[ \varnothing \subset \{1\}\subset \{1,2\}\subset \{1,2,3\}, \] 长度为 4。因此根据 Mirsky 定理，整个偏序集最少可以用 4 个反链覆盖。

示例解释：在幂集偏序里，一个最自然的反链分层方式就是按集合大小来分层： \[ \{\varnothing\},\qquad \{\{1\},\{2\},\{3\}\},\qquad \{\{1,2\},\{1,3\},\{2,3\}\},\qquad \{\{1,2,3\}\}. \] 这 4 层中的每一层都是反链，因为同一层里的集合大小相同，不可能互相包含。于是，整个偏序集确实能用 4 个反链覆盖。同时也不可能少于 4 个，因为那条最长链 \[ \varnothing \subset \{1\}\subset \{1,2\}\subset \{1,2,3\} \] 中的 4 个集合彼此两两可比，它们不能落在同一个反链里，所以至少需要 4 层。这就很好地体现了 Mirsky 定理的本质： “最长链有多高，反链分层就至少要有多少层；而且正好能做到这么多层。”

62. Erdős–Ko–Rado 定理经典

当 \(n\ge 2k\) 时，\([n]\) 的 \(k\) 元子集族中，若任意两集合相交，则其最大规模为

\[ \binom{n-1}{k-1}. \]

前置：集合族、交叉结构。

定理解释：“两两相交”的 \(k\) 元集合族，做到最大时，本质上应当都含有某个固定元素。

示例：所有包含元素 1 的 \(k\) 元子集共有 \(\binom{n-1}{k-1}\) 个，而且任意两者必相交。

示例解释：因为它们都含 1，所以天然两两相交。这族集合就是 EKR 定理里的极值构造。

63. Ramsey 数定义

最小整数 \(R(s,t)\) 满足：任意对完全图 \(K_{R(s,t)}\) 的边进行红蓝二染色时，必存在一个红色 \(K_s\) 或一个蓝色 \(K_t\)。

前置：图、完全图、边染色、单色完全子图。

定理解释： Ramsey 数 \(R(s,t)\) 用来衡量这样一个临界规模：当完全图的顶点数达到这个规模以后，不管你怎样把每条边染成红色或蓝色，都已经无法避免出现某种指定大小的单色完全子图。这里的“红色 \(K_s\)”意思是：存在 \(s\) 个顶点，它们两两之间的边全是红色；“蓝色 \(K_t\)”同理。所以 Ramsey 数的本质不是在研究“能不能构造出一个好例子”，而是在研究“图大到什么程度以后，某种有序结构已经被强制出现了”。它代表的是一种非常典型的组合思想：**规模一旦足够大，完全混乱其实不可能维持下去，规则结构迟早会冒出来。** 因此，Ramsey 数常被理解为“无序不可持续到多大”的阈值。

示例：著名结论是 \[ R(3,3)=6. \] 这表示：任意对完全图 \(K_6\) 的边做红蓝二染色，必定能找到一个红色三角形或一个蓝色三角形。

示例解释：这条结论常被翻译成一个很形象的“六人聚会问题”：在 6 个人中，把任意两人之间的关系标成“认识”或“不认识”两种颜色，那么一定能找到 3 个人，使得他们两两都认识，或者两两都不认识。注意这里说的是“必定存在”，也就是不管关系如何分配，都逃不掉这个结果。同时 \(R(3,3)=6\) 还包含另一层意思：5 个点时还可以构造一种染色，使红三角和蓝三角都不存在；但到了 6 个点，这种回避就彻底不可能了。所以 6 正是这个问题的临界点。

64. Ramsey 定理

任意大的完全图在有限边染色下，总存在任意给定规模的单色完全子图。

前置：有限染色、完全图、Ramsey 数定义。

定理解释： Ramsey 定理是 Ramsey 数定义背后的总体存在性结论。它告诉我们：对于任意给定的正整数 \(m\) 和任意有限种颜色，只要完全图足够大，那么无论怎么给边染色，都一定会出现一个边全同色的 \(K_m\)。也就是说，**大规模离散结构中，某种规则模式是不可避免的。** 这条定理是 Ramsey 理论的核心起点。它的意义在于：我们不再只是看某个具体数字 \(R(s,t)\)，而是从整体上知道，这类“强制单色结构”的阈值总是存在的。换句话说，不存在“无限地逃避单色完全子图”的染色方式；你可以在小图里躲开一阵子，但只要图继续变大，终究还是要被某种单色结构逼出来。

示例：在二染色情况下，对任意给定的 \(m\)，都存在一个整数 \(N\)，使得任意对 \(K_N\) 的边进行红蓝染色，必含一个单色 \(K_m\)。

示例解释：例如当 \(m=3\) 时，这个 \(N\) 就是 \(R(3,3)=6\)。当 \(m\) 再变大时，所需的 \(N\) 也会迅速变大，虽然具体数值往往很难求，但“这样的 \(N\) 一定存在”是 Ramsey 定理保证的。所以 Ramsey 定理强调的不是“数值好不好算”，而是“有序结构在大规模中一定存在”。这也是它被称为“杂乱中必出秩序”的经典来源。

65. Turán 定理极值图论核心

在所有不含 \(K_{r+1}\) 的 \(n\) 阶图中，边数最多的图由 Turán 图 \(T_{n,r}\) 达到。

\[ e(G)\le e(T_{n,r}). \]

前置：图、完全子图、极值思想、完全 \(r\) 部图。

定理解释： Turán 定理是极值图论中最核心的起点之一。它研究的是这样一个问题：如果我们禁止图中出现一个太大的完全子图 \(K_{r+1}\)，那么这张图最多还能有多少条边？直观上讲，如果边太多，图就会越来越“团块化”，最终容易形成大的完全子图；所以想在“不出现 \(K_{r+1}\)”的前提下尽量多放边，就必须把顶点分成若干部分，使同一部分内部不连边，不同部分之间尽量全连。 Turán 定理说明，这种最优结构恰好就是尽量均匀分成 \(r\) 份的完全 \(r\) 部图，也就是 Turán 图。所以它不只是给出一个边数上界，更告诉我们：**极值构造长什么样。**

示例：当 \(r=2\) 时，Turán 定理说明：所有不含三角形 \(K_3\) 的 \(n\) 阶图中，边数最多的是把顶点尽量平均分成两部分的完全二部图。

示例解释：这是 Mantel 定理的内容，可以看作 Turán 定理最基础的特例。为什么完全二部图不会出现三角形？因为三角形需要三个点两两相连，而二部图中同一部分内没有边，所以不可能形成三角形。又为什么要“尽量平均分”？因为跨部边数等于两部分大小的乘积，在总点数固定时，这个乘积在两部分尽量接近时最大。所以 Turán 定理传达出的思想非常清楚： **在禁止大团的条件下，最稠密的图往往是“尽量均匀分部”的完全多部图。**

66. Schur 定理

任意有限着色的正整数集里，总存在同色整数 \(x,y,z\)，使得

\[ x+y=z. \]

前置：Ramsey 思想、整数加法结构、有限着色。

定理解释： Schur 定理说明：即使我们把正整数染成有限多种颜色，也无法永远逃避一种最基本的加法关系——同色解 \[ x+y=z. \] 也就是说，有限染色可以制造表面上的混乱，但在整数的加法结构里，这种混乱终究不能彻底破坏最简单的线性关系。这是 Ramsey 思想从“图的边染色”走向“整数加法结构”的一个典型例子。它告诉我们：不仅图里会强制出现单色结构，整数集合在有限着色下也一样会被迫出现同色的代数关系。

示例：如果把足够大的正整数集合染成红、蓝两色，那么总能找到三个同色整数 \(x,y,z\)，满足 \[ x+y=z. \]

示例解释：这里的关键点不是“有时会找到”，而是“无论怎么染，最终都逃不开”。比如你可能想把整数染色，试图避免同色加法三元组，但 Schur 定理告诉你：这种避免只能在很小范围内暂时成立，一旦范围足够大，就一定失败。所以它体现的是：**有限染色无法彻底打乱整数中的加法规律。**

67. van der Waerden 定理

任意有限着色的正整数区间中，总存在任意长度的单色等差数列。

前置：Ramsey 理论、等差数列、有限着色。

定理解释： van der Waerden 定理是 Ramsey 理论在整数加法结构中的另一条代表性结论。它说的是：只要把正整数按有限多种颜色染色，那么不管你怎样染，都不可能永远阻止长等差数列的出现。对任意指定的长度 \(k\)，总存在一个足够大的整数 \(N\)，使得区间 \[ \{1,2,\dots,N\} \] 的任意有限着色中，都一定包含一个长度为 \(k\) 的单色等差数列。这说明“等差数列”这种非常规则的结构，在大规模整数系统里具有强制性。也就是说，颜色虽然把集合分裂成了若干块，但仍然压不住这种线性秩序。

示例：若把 \(\{1,2,\dots,N\}\) 染成两色，只要 \(N\) 足够大，就一定存在一个很长的单色等差数列。

示例解释：例如，若我们关心长度为 3 的单色等差数列，那么从某个规模开始，无论怎样用两种颜色给区间染色，都一定会出现同色的 \[ a,\ a+d,\ a+2d. \] 更一般地，长度 \(k\) 越大，需要的区间长度 \(N\) 也越大，但 van der Waerden 定理保证这种阈值总是存在。所以这一定理的重点仍然不是“具体最小 \(N\) 是多少”，而是“单色等差数列终究躲不开”。它和 Schur 定理一起，都是整数版 Ramsey 理论的经典代表。

68. Hales–Jewett 定理偏难

在高维字母立方体的任意有限着色中，总存在一条单色组合线。

前置：Ramsey 理论、高维离散结构、有限字母表与组合线的概念。

定理解释： Hales–Jewett 定理可以看作 Ramsey 理论的一个非常高维、非常强大的总括性结论。它研究的对象不再是图边，也不再只是整数，而是由有限字母组成的高维“词空间”。例如，在字母表 \(\{1,2,\dots,m\}\) 上考虑长度为 \(n\) 的所有字符串，这些字符串构成一个高维离散立方体。所谓“组合线”，可以粗略理解为：固定大部分位置，只让某些位置同时变化，从而形成的一条规则族。 Hales–Jewett 定理说：只要维数足够大，那么无论怎样做有限着色，都一定会出现一整条这样的单色组合线。这说明在高维离散空间里，规则结构的不可避免性比低维更强。许多经典的染色定理，如 van der Waerden 定理，都可以看成它的某种投影或推论。

示例：可以把 Hales–Jewett 定理理解成 van der Waerden 定理在更高维字母空间中的推广：当维度足够高时，有限着色一定会强制产生一条单色的规则变化族。

示例解释：它的表述虽然比“单色等差数列”抽象得多，但核心思想完全一致： **规模一大，有限染色就无法阻止规则模式的出现。** 只不过这里的“规则模式”不再是数轴上的等差数列，而是高维字母立方体中的组合线。也正因为它足够一般、足够强，所以在 Ramsey 理论中地位非常高，经常被看作一个统一很多单色结构定理的上层框架。

69. 握手定理

\[ \sum_{v\in V}\deg(v)=2|E|. \]

前置：图、边、顶点度数、双计数思想。

定理解释：握手定理是图论里最基础、也最常用的一条公式之一。它的意思是：在一个有限无向图中，把所有顶点的度数加起来，结果一定等于边数的两倍。原因非常直接：每一条边都有两个端点，所以如果我们按“边”来看，每条边会贡献 2 个端点；而如果我们按“点”来看，每个顶点贡献的正是它所连接的边数，也就是它的度数。这两种数法其实都在数同一件事——图中所有“边端点关联”的总数，因此结果必然相等。这条定理本质上是一个非常标准的双计数公式。它虽然简单，但作用非常大：很多关于图的奇偶性、平均度数、边数估计、存在性结论，都是从它出发的。

示例：若一个图有 7 条边，则所有顶点度数之和必为 \[ 2\times 7=14. \]

示例解释：这里不需要知道图具体长什么样。不管这 7 条边如何连接，每条边总是恰好给总度数贡献 2，所以总度数和一定是 14。比如一个图的顶点度数可能是 \[ 4,3,3,2,1,1, \] 它们的和就是 14；换一张图，度数分布可能完全不同，但和仍然必须是 14。所以握手定理提供的是一个“整体守恒关系”，它不依赖局部形状，只依赖边数总量。

70. 奇度点个数为偶数

任意有限图中，奇数度顶点的个数是偶数。

前置：握手定理、奇偶性、整数加法。

定理解释：这条结论是握手定理最经典、也最常见的直接推论。因为握手定理告诉我们： \[ \sum_{v\in V}\deg(v)=2|E|, \] 所以所有顶点度数的总和一定是偶数。现在来观察一堆整数的和什么时候会是偶数：偶数项加起来仍是偶数；而奇数项的和，只有当奇数项的个数是偶数个时，结果才会是偶数。因此，在图的所有顶点度数中，奇数度顶点的个数不可能是奇数，只能是偶数。这条结论非常有用，因为它常常能一眼排除某些图的可能性，或者在构造图时给出必要条件。

示例：一个图不可能恰好只有 3 个奇度点。

示例解释：如果恰有 3 个奇度点，那么所有顶点度数和就是“3 个奇数加上一堆偶数”。但 3 个奇数的和是奇数，奇数再加上若干偶数，结果仍然是奇数。这就和握手定理给出的“总度数和一定是偶数”矛盾。所以奇度点个数只能是 \[ 0,2,4,6,\dots \] 这样的偶数。例如一个路径图有 2 个奇度点；一个 Euler 回路图有 0 个奇度点；但绝不可能出现 1 个或 3 个奇度点这样的情况。

71. 树的边数公式

任意 \(n\) 个顶点的树恰有

\[ n-1 \]

条边。

前置：树、连通图、无环图、归纳思想。

定理解释：树可以理解成“最简单的连通图”，也可以理解成“刚刚好连通”的图。这里“刚刚好”的意思是：如果边再少一条，图就会断开；如果边再多一条，就会出现环。树的边数公式 \[ |E|=n-1 \] 正好体现了这种临界性。它说明：一个树的边数既不会太少，也不会太多，而是恰好卡在连通与无环这两个条件同时成立的边界上。这条公式既可以用归纳法证明，也可以从“每次往树里加一个新顶点，只需连一条新边”这个过程来理解。它是树论里最根本的数量关系之一。

示例： 10 个顶点的树必有 \[ 10-1=9 \] 条边。

示例解释：例如，从一个顶点开始，它本身就是一棵树，此时有 1 个点、0 条边。之后每加入一个新顶点，为了保持连通且不产生环，只能用 1 条边把它接到原来的树上。因此每多 1 个点，就多 1 条边。从 1 个点扩展到 10 个点，一共增加了 9 次，所以边数就是 9。这条公式在树的归纳证明、图算法、生成树问题里都会反复出现，是树结构最重要的计数特征之一。

72. Cayley 公式经典

\(n\) 个标号顶点上的树的个数为

\[ n^{n-2}. \]

前置：树、标号图、Prufer 编码或双射思想。

定理解释： Cayley 公式是图论计数中最著名的公式之一。它回答了一个非常自然的问题：如果顶点已经标号为 \[ 1,2,\dots,n, \] 那么一共能构成多少棵不同的树？答案居然是一个极其简洁的闭式： \[ n^{n-2}. \] 这个结果之所以惊艳，是因为“树的形状”看起来非常复杂，各种连接方式很多，但最后总数却压缩成了这样简单的表达式。 Cayley 公式最经典的证明方法是 Prufer 编码：每一棵标号树都可以和一个长度为 \(n-2\) 的序列一一对应，而这个序列的每一项都可以从 \(1,2,\dots,n\) 中任取。因此总数正好就是 \[ n^{n-2}. \] 这条公式说明：有时候复杂图结构的计数问题，背后会隐藏着非常整齐的编码机制。

示例： 4 个标号点上的树共有 \[ 4^{4-2}=4^2=16 \] 棵。

示例解释：这里说的是“标号树”，也就是说顶点 \(1,2,3,4\) 的位置不能随便交换；只要连接关系不同，就算不同的树。例如，一棵星形树和一棵链形树当然不同；即使都是链形，如果顶点标号分配方式不同，也算不同的标号树。 Prufer 编码告诉我们：每棵这样的树都唯一对应一个长度为 2 的序列，而每个位置有 4 种可能，所以总数是 \[ 4\cdot4=16. \] 这也说明了为什么公式里会出现 \(n-2\) 次方。

73. Kirchhoff 矩阵树定理重要

图的生成树个数等于其 Laplace 矩阵任一代数余子式。

前置：矩阵、行列式、图、生成树、Laplace 矩阵。

定理解释：矩阵树定理是组合图论和线性代数之间最经典的桥梁之一。它说的是：如果我们把图的信息写进一个矩阵——通常是 Laplace 矩阵（也叫 Kirchhoff 矩阵）——那么这个矩阵删去任意一行一列后得到的行列式，恰好就是图的生成树个数。也就是说，一个看起来纯粹是“数树有多少棵”的离散计数问题，居然可以转化为“算一个行列式”的代数问题。这条定理非常强大，因为很多图的生成树数用直接数法几乎不可能做，而一旦矩阵写出来，问题就变成了标准的线性代数计算。它体现了一种很重要的组合思想： **复杂的离散结构，有时可以通过代数工具被统一编码。**

示例：求完全图 \(K_n\)、完全二部图 \(K_{m,n}\)、循环图等的生成树个数时，常直接使用矩阵树定理。

示例解释：例如完全图 \(K_n\) 的每个顶点度数都是 \(n-1\)，因此它的 Laplace 矩阵形式很整齐。对这个矩阵删去一行一列后算行列式，就可以推出生成树数是 \[ n^{n-2}, \] 这也正好回到了 Cayley 公式。所以矩阵树定理不仅能处理一般图，还能作为 Cayley 公式的一种统一证明框架。它在图论中地位很高，因为它把“结构计数”与“矩阵行列式”联系得非常精确。

74. Euler 回路判定

连通图有 Euler 回路，当且仅当每个顶点度数都为偶数。

前置：图、连通性、度数、闭路、奇偶性。

定理解释： Euler 回路是指一条经过图中每条边恰好一次、并且最后回到出发点的闭路。这条判定定理说明：一个连通图能否存在 Euler 回路，完全由各顶点度数的奇偶性决定。为什么“偶数度”是关键？因为如果你沿着一条 Euler 回路走，在中间经过某个顶点时，每次进入这个点，都必须还能沿另一条尚未走过的边离开。这样一来，与这个点有关的边就必须能一对一对地配成“进—出”两条，所以总数必须是偶数。对起点和终点，由于 Euler 回路要求最后还要回到起点，因此起点和终点其实是同一个点，也同样要满足偶数配对。因此，连通图存在 Euler 回路的必要条件是每个点度数都为偶数；而这条定理更强，它还告诉我们：这个条件同时也是充分的。

示例：若某个连通图所有顶点度数都是 2，则它必有 Euler 回路。

示例解释：因为每个点的度数都是偶数，而且图又连通，所以满足 Euler 回路判定条件。更直观地说，在每个顶点处，你总可以“从一条边进，再从另一条边出”，不会在中途卡住。例如一个简单的环图 \(C_n\) 中，每个顶点度数都是 2，所以沿着环绕一圈，正好经过每条边一次并回到起点，这就是一条 Euler 回路。反过来，如果某个连通图中有奇度点，那么在走边的过程中，某些点就会出现“进得去却配不出”的情况，从而无法形成经过所有边一次的闭路。

75. Hall 婚配定理核心

二分图 \(G=(X,Y)\) 存在覆盖 \(X\) 的匹配，当且仅当对任意 \(S\subseteq X\)，有

\[ |N(S)|\ge |S|. \]

前置：二分图、邻集、匹配。

定理解释：想让 \(X\) 中每个人都分到一个不同对象，必要条件是任何一群人能接触到的候选对象数不能比他们自己少；Hall 定理说明这也是充分条件。

示例：若 3 个男生共同认识的女生只有 2 个，就不可能给他们安排互不冲突的舞伴。

示例解释：这就是 Hall 条件失败的最直观情形：资源不够覆盖这群人。

76. König 定理

二分图中，最大匹配数等于最小点覆盖数。

前置：二分图、匹配、点覆盖。

定理解释：这是一条非常漂亮的 min-max 定理：一边是最多能挑多少条不相交边，一边是最少用多少个点能碰到所有边。

示例：若一个二分图最大匹配大小是 5，则最小点覆盖也一定大小为 5。

示例解释：这条定理只对二分图成立；一般图中情况会复杂得多。

77. Menger 定理（知识型）

两个点集之间的最小割大小等于最大点不交路径数（或边不交路径数）。

前置：路径、割、图的连通性。

定理解释：它把“最多能找到多少条彼此独立的路”和“至少删多少东西才能断开”联系起来。

示例：若两点间存在 3 条内部点互不相交的路径，则至少删掉 3 个内部点才能把它们分开。

示例解释：这体现了“路多则难断，难断则路多”的精确对应。

78. 最大流最小割定理（知识型）

网络中的最大流量等于最小割容量。

前置：网络流、容量、割集。

定理解释：流量再大也冲不过某个最窄瓶颈；而这个瓶颈恰好决定了最大可能流量。

示例：管道网络、任务分配、二分图匹配等问题，都可转化成最大流模型。

示例解释：很多看似纯组合的存在性问题，一旦建成流网络，就能用这条定理解决。

79. 图染色数定义

图的染色数 \(\chi(G)\) 是把顶点染色使相邻点异色所需的最少颜色数。

前置：图、相邻、顶点染色。

定理解释：染色数衡量一个图“冲突结构有多强”。越难染，说明图中相互制约越多。

示例：完全图 \(K_n\) 的染色数是 \(n\)。

示例解释：因为任意两个点都相邻，所以每个点都必须用不同颜色。

80. 染色多项式

图 \(G\) 的染色多项式 \(P_G(k)\) 表示用 \(k\) 种颜色对 \(G\) 做合法顶点染色的方法数。

前置：图染色、计数。

定理解释：对于固定图而言，合法染色数居然是一个关于 \(k\) 的多项式，这是一个很漂亮的结构结论。

示例：路径图 \(P_n\) 的染色多项式是 \(k(k-1)^{n-1}\)。

示例解释：第一个点随便染 \(k\) 种，后面每个点只需避开前一个点的颜色，所以各有 \(k-1\) 种。

81. 删除—收缩递推

对任意边 \(e\)，有

\[ P_G(k)=P_{G-e}(k)-P_{G/e}(k). \]

前置：染色多项式、图的删除和收缩。

定理解释：先数删掉 \(e\) 后的染色，再减去“两个端点被染成同色”的那些情形，而这些正好对应收缩后的染色。

示例：很多小图的染色多项式都靠这条递推逐步算出。

示例解释：它相当于把复杂图拆成两个更简单的图来处理。

82. 轨道—稳定子公式

群 \(G\) 作用在集合 \(X\) 上时，对任意 \(x\in X\)，有

\[ |\operatorname{Orb}(x)|\cdot |\operatorname{Stab}(x)|=|G|. \]

前置：群作用、轨道、稳定子。

定理解释：一个对象在群作用下能变出多少种不同样子，和有多少个群元素把它固定住，是互补关系。

示例：正方形旋转作用在顶点染色上时，可用这条公式分析等价类大小。

示例解释：越“对称”的对象，被固定住的群元素越多，因此它的轨道通常越小。

83. Burnside 引理经典

不同等价类（轨道）数等于各群元素固定点数的平均值：

\[ \#(\text{轨道})=\frac1{|G|}\sum_{g\in G}|\operatorname{Fix}(g)|. \]

前置：群作用、固定点。

定理解释：想数“本质不同”的对象，不必直接分轨道，只要把每种对称操作下不变的对象数平均一下即可。

示例：数圆珠项链的不同染色、数旋转同构的多边形染色，都常用 Burnside 引理。

示例解释：因为这类问题最麻烦的就是“旋转后算不算同一种”，而 Burnside 正是处理这种等价关系的工具。

84. Pólya 计数定理重要

在群作用下，可借助循环指标多项式统一求各种带色对象的等价类计数。

前置：Burnside 引理、置换循环分解。

定理解释：Pólya 定理是 Burnside 的系统化加强版。它不只数一种颜色数，而是能统一处理多色分布问题。

示例：数正六边形顶点的两色染色，若旋转视同一种，可用 Pólya 定理快速得到答案。

示例解释：相比逐个算固定点，Pólya 用循环指标一次性编码了所有对称操作的贡献。

85. Steiner 系统（知识型）

Steiner 系统 \(S(t,k,n)\) 指一个 \(n\) 元点集上的 \(k\) 元块族，使每个 \(t\) 元子集恰好属于一个块。

前置：集合族、设计理论。

定理解释：这是非常整齐的组合设计：每个小子集被覆盖得刚刚好，不多不少。

示例：著名的 Fano 平面可看作一个小型设计结构。

示例解释：这类对象兼具强对称性与精确覆盖性，所以在组合、几何、编码里都很重要。

86. BIBD 参数关系

平衡不完全区组设计中，参数满足

\[ vr=bk,\qquad \lambda(v-1)=r(k-1). \]

前置：设计理论、双计数。

定理解释：这两条关系分别来自于：数“点块关联对”以及数“固定一点和另一点共同出现”的情况。

示例：判断某组参数能否构成 BIBD 时，通常先检验这两条必要条件。

示例解释：若连参数关系都不满足，那设计结构就根本不可能存在。

87. 纠错码的 Hamming 界（知识型）

它给出纠错码长度、码字数、纠错能力之间的重要上界。

前置：编码理论、球打包思想。

定理解释：每个码字周围的“纠错球”不能重叠，否则接收到一个词时就无法唯一还原。

示例：研究二进制码能纠正多少位错误时，常先看 Hamming 界。

示例解释：这本质上也是抽屉与极值思想：空间有限，球装太多就会碰撞。

88. Kruskal–Katona 定理偏难

它刻画了给定大小的集合族，其下影（shadow）的最小可能规模。

前置：集合族、\(k\) 元子集、字典序 / 余字典序、极值组合、下影（shadow）概念。

定理解释： Kruskal–Katona 定理是极值集合论中的一条核心定理。它研究的问题不是“某个集合族有多少个集合”，而是更细地研究： 如果一个 \(k\) 元集合族已经有这么大了，那么把每个集合删掉一个元素以后，能产生多少个 \((k-1)\) 元集合？最少能少到什么程度？ 这里产生出来的所有 \((k-1)\) 元集合，统称这个集合族的“下影”或“影子”。这条定理的厉害之处在于：它告诉我们，影子的最小值不是随便乱猜，而是由一种非常整齐、非常规整的“初段集合族”达到的。也就是说，在集合族大小已经固定的前提下，若想让边界尽量小，那么集合族本身必须长得很“紧”、很“靠前”、很“压缩”。这是一种非常典型的高阶组合思想：不是单纯比较数量，而是研究“结构长什么样时最省边界”。所以它和前面那些基础计数定理不一样——前面更多是在数对象有多少个，而这条定理开始真正研究“极值结构的形状”。

示例：设 \(\mathcal F\) 是一个由若干个 3 元子集组成的集合族。对于每个 \(A\in\mathcal F\)，删去其中任意一个元素，就会得到若干个 2 元子集。所有这样得到的 2 元子集构成 \(\partial \mathcal F\)，即 \(\mathcal F\) 的下影。 Kruskal–Katona 定理研究的就是：当 \(|\mathcal F|\) 固定时，\(|\partial \mathcal F|\) 最小可以是多少。

示例解释：例如，如果 \(\mathcal F\) 由一些彼此“很集中”的 3 元集组成，那么它们删掉一个元素后得到的 2 元集可能重复很多，于是下影就会比较小；如果 \(\mathcal F\) 很分散，那么删掉一个元素以后通常会产生很多不同的 2 元集，于是下影就会更大。 Kruskal–Katona 定理告诉我们：这种“最省影子”的集合族不是随便来的，而是某种压缩到最前面的标准形。所以这条定理常被看作“集合族边界极小化”的基础工具。

89. Lovász 局部引理重要

在若干坏事件概率都不太大，且依赖关系不太强时，可保证这些坏事件可以同时都不发生。

前置：概率方法、事件依赖、独立与非独立、乘法估计、存在性证明思想。

定理解释： Lovász 局部引理（通常简称 LLL）是概率方法中最著名的高阶工具之一。它解决的是这样一种局面：你有很多“坏事件”，每个坏事件单独看发生概率都不大；但是这些坏事件之间又不是完全独立的，所以不能直接把“都不发生”的概率简单相乘。这时，局部引理告诉你：只要每个坏事件足够稀少，而且每个坏事件只和不太多的其他坏事件发生依赖，那么“所有坏事件都不发生”的情况仍然是可能的。也就是说，一个满足全部限制的好对象一定存在。这是一种非常典型的“非构造存在性证明”：它并不直接把对象造出来，而是通过概率和依赖关系估计，证明“坏情况不可能把所有可能性全部封死”。对孩子来说，可以把它先理解成一句很直观的话： 如果每个局部错误都不太容易出现，而且这些错误不会大规模互相牵连，那么全局上就有希望一个错误都不出。

示例：在图染色问题中，有时把顶点随机染色，然后把“某种局部冲突出现”看成坏事件。如果每一种冲突发生概率都很小，而且每个冲突只与周围有限多个冲突有关，那么就可以尝试用 LLL 证明：存在一种染色使所有冲突都不发生。

示例解释：例如，某个坏事件可能是“某一条边两端颜色相同”，或者“某一小块结构被染成了不允许的样子”。这些坏事件通常只依赖于附近少数几个点或边，因此依赖关系是“局部的”，不会牵扯到全图。如果再能证明每个坏事件本身发生概率足够小，那么 LLL 就会告诉我们：虽然随机染色时局部冲突可能很多，但总存在一种全局配置，把所有局部冲突同时避开。这就是局部引理最震撼的地方：它把“局部坏事件很多”与“全局好对象仍存在”联系了起来。

90. Möbius 反演在偏序中的形式

在偏序集上，若函数满足某种累加关系，则可借 Möbius 函数做反演。

前置：偏序、包含关系、约数偏序、反演思想、容斥原理的抽象理解。

定理解释： Möbius 反演在偏序中的形式，是把数论里熟悉的 Möbius 反演提升到一般偏序集上的统一框架。它研究的是这样一类问题：你先定义了一个函数 \(g\)，然后另一个函数 \(f\) 是在“所有比它小的元素”上对 \(g\) 求和得到的。也就是说， \[ f(x)=\sum_{y\le x} g(y). \] 那么问题来了：如果现在只知道 \(f\)，还能不能把原来的 \(g\) 反推回来？ Möbius 反演告诉我们：可以。只不过反推时，不是简单减法，而是要乘上偏序集里对应的 Möbius 函数。这条思想非常深，因为它把很多看起来不相干的公式统一了起来：容斥原理、约数求和、布尔格上的符号交替、约数格中的 Möbius 反演，其实都可以看成是这同一个框架的不同特例。所以这条定理真正重要的地方，不只是“能反演”，而是它让我们看见： 很多“先累加再恢复原值”的过程，本质上都是同一种数学现象。

示例：在布尔格 \(\mathcal P([n])\) 中，若 \[ f(A)=\sum_{B\subseteq A} g(B), \] 那么就可以通过布尔格上的 Möbius 反演，把 \(g(A)\) 用 \(f(B)\) 的交错和表达出来。

示例解释：这实际上就是容斥原理背后的抽象版本。因为在布尔格里，Möbius 函数就是一种按层数交替符号的系数，所以“先对子集求和，再用交错和反推回来”这件事，就和容斥完全同源。同样，在正整数按整除关系形成的偏序里，Möbius 反演就会退化成数论中熟悉的那种约数反演公式。所以这条结论最值得强调的是：它并不是又一个零散公式，而是一个统一容斥、约数求和、反推原函数的总框架。

91. Combinatorial Nullstellensatz（知识型）

它给出多项式方法处理中组合存在性问题的强力工具。

前置：多项式、域、系数、零点、代数方法解决离散问题的基本意识。

定理解释： Combinatorial Nullstellensatz（组合零点定理）是多项式方法中的一个代表性工具。它的基本精神是：想证明某个离散配置存在，不一定非要直接构造，有时可以先造一个多项式。然后通过研究这个多项式的某个高次项系数是否非零，来推出：在给定的取值集合里，总会有某个点使这个多项式不为零。一旦“不为零”恰好对应于“目标结构存在”或“某种冲突没有发生”，问题就解决了。这听起来很代数，但在组合里威力很大，因为很多离散限制条件都能被翻译成“某个多项式等于 0 或不等于 0”的形式。所以它代表的是一种非常现代的思路： 把离散问题转成代数对象，再用代数信息反推组合存在性。

示例：在一些加法组合或模意义构造题中，可以构造一个多项式，使得“多项式在所有候选点都为 0”会和某个非零系数矛盾，于是推出一定存在一个候选点使多项式不为 0。

示例解释：这类题的关键不是算多项式值，而是先把“想要的性质”编码进多项式里。比如说，若一个配置不合法，就让某个因子变成 0；若一个配置合法，就有机会使整个多项式不为 0。然后再用组合零点定理说明：由于某个高次项系数非零，这个多项式不可能在整个笛卡尔积上都为 0。于是就说明：至少有一个合法配置存在。所以它特别适合那种“看起来很难构造，但又怀疑总能存在”的题。

92. Sunflower 猜想相关结论（知识型）

研究若干集合两两交集相同的“向日葵结构”。

前置：集合族、交结构、公共核、极值集合论。

定理解释：向日葵（sunflower）是一类非常有代表性的集合族结构。若若干个集合的两两交集全都相同，那么这个公共交集就叫“核”，其余互不重叠的部分就像一片片“花瓣”，因此叫向日葵。这种结构的魅力在于：它看起来很简单，但却是极值集合论和理论计算机科学中的一个高频对象。因为一旦一个复杂集合族里出现向日葵，就说明这个集合族已经开始呈现出明显的规整性，不再是完全杂乱的。所以围绕向日葵的很多问题，本质上都在问： “一个集合族如果大到某种程度，是否必然包含这样一个规整结构？” 这正是极值组合最典型的问题类型之一。

示例：若有三个集合 \[ A_1,A_2,A_3 \] 满足 \[ A_1\cap A_2=A_1\cap A_3=A_2\cap A_3=K, \] 那么这三个集合就构成一个 3 花瓣向日葵，其中 \(K\) 是它们的核。

示例解释：这意味着每个集合都可以写成 \[ A_i=K\cup P_i, \] 其中 \(P_i\) 是第 \(i\) 片花瓣，而且这些花瓣彼此不交。所以向日葵的本质就是：公共部分完全重合，而非公共部分又彼此分离。这种结构在“大集合族中一定会不会出现某种规整子结构”的问题里特别重要。它之所以显得生僻，是因为它不是最基础的计数工具，但一旦进入极值集合论，它就会频繁出现。

93. 平面图 Euler 公式

连通平面图满足

\[ V-E+F=2. \]

前置：平面图、点数 \(V\)、边数 \(E\)、面数 \(F\)、连通性。

定理解释： Euler 公式是平面图最根本的结构公式之一。它把一个平面图里的三个基本量——顶点数、边数、面数——精确地联系起来。这里的“面”不仅包括图内部围成的区域，还包括最外面的无限大区域。这条公式的意义非常大，因为它说明：平面图虽然看起来形状变化很多，但只要是连通的，它们在“点—边—面”的总平衡关系上始终受到一个固定约束。所以后面很多平面图不等式，例如 \[ E\le 3V-6 \] 或对无三角形平面图的更强限制，都是从 Euler 公式出发推出来的。它可以说是“平面结构受限”这一整套理论的起点。

示例：立方体的骨架可看作一个平面图，它满足 \[ V=8,\qquad E=12,\qquad F=6, \] 所以 \[ 8-12+6=2. \]

示例解释：虽然立方体本身是三维物体，但它的“点和棱组成的骨架图”可以不交叉地画在平面上，因此它是平面图。这里的 6 个面，就是 5 个有限区域加上外部区域，或者按另一种平面嵌入方式理解成总共 6 个区域。 Euler 公式告诉我们：只要嵌入是平面的，这个数量关系就不会变。所以它反映的不是某幅图画的偶然现象，而是平面图固有的拓扑性质。

94. Jordan 曲线型分割思想（知识型）

平面中的简单闭曲线把平面分成内外两个区域。

前置：平面拓扑直觉、闭曲线、区域分割、平面图的基本空间观念。

定理解释： Jordan 曲线定理从表面上看很直观：一条不自交的闭曲线，好像天然就把平面分成“里面”和“外面”。但真正严格证明它并不简单，所以它在数学史上其实是很重要的一条拓扑结论。在组合和几何里，很多时候我们不会正式去写 Jordan 曲线定理，但会不停地使用它背后的思想： 只要一个简单闭合边界出现了，它就会围出一个区域。 这件事在平面图计数、区域切分、路径封闭、面数讨论里都非常关键。所以这一条更像是“底层支撑原理”——平时不一定点名说它，但很多直观推理其实都在依赖它。

示例：在讨论平面图时，若一条回路构成一个简单闭合边界，我们通常会自然认为它围出了一个内部区域，并与外部区域分开。

示例解释：这种想法其实正是 Jordan 曲线型分割思想的体现。例如在用 Euler 公式分析平面图时，我们默认“每增加一条形成新封闭边界的边，就会多出一个面”，这背后就离不开闭曲线把区域分开的直觉。所以虽然它不像排列组合公式那样能直接套数值，但它是很多平面组合论证中不可缺少的背景事实。

95. 概率方法

通过构造随机对象并证明其期望或概率满足某性质，可推出满足要求的确定性对象存在。

前置：概率、随机试验、期望、存在性证明思想。

定理解释：概率方法不是一条单独的定理，而是一整类非常强大的证明思想。它最核心的一句口号可以概括为： 如果随机挑一个对象，有正概率是好的，那么好对象就一定存在。 这听起来简单，但威力极大，因为有很多组合对象很难直接构造，却可以很容易用随机方式“先挑一个试试”。一旦能证明这个随机对象平均来看够好，或者直接有正概率满足要求，就得到了存在性结论。这类方法特别适合处理：极值图论、避免局部冲突、稀疏结构构造、染色存在性、集合族存在性等问题。它的魅力就在于：不是硬造，而是先随机，再证明随机过程不可能永远失败。

示例：要证明某种图或集合存在，有时只需定义一个随机对象，并证明它满足目标性质的概率大于 0。

示例解释：例如你想证明“存在一个没有某种坏结构、但边又很多的图”。直接构造也许很难，但你可以先随机取边，得到一个随机图。然后估计这个随机图中坏结构的期望数量、边数的期望数量。若结果显示：平均来看，边数够多而坏结构不多，那么就说明至少有一个具体图同时拥有这两个优点。这就是概率方法最典型的用法：用“平均情况”倒逼“存在好情况”。

96. 期望线性性

对任意随机变量 \(X_1,\dots,X_n\)，都有

\[ \mathbb E[X_1+\cdots+X_n]=\mathbb E[X_1]+\cdots+\mathbb E[X_n]. \]

前置：随机变量、期望、加法。

定理解释：期望线性性是概率方法里最常用、最该牢牢记住的基本工具。它最珍贵的地方在于：不要求独立性。也就是说，不管这些随机变量彼此有没有关系、会不会互相影响，只要总量能写成很多部分之和，期望就可以拆开逐项算。这在组合中太重要了，因为很多“总个数”本来就天然是若干个局部计数的和。所以在做概率组合题时，最常见的套路就是：先把目标量拆成很多个指示变量，然后再直接用期望线性性逐个求和。这会把一个原本复杂的随机对象，化成很多个小而容易处理的局部问题。

示例：求随机图中边数、三角形数、孤立点数的期望时，通常都先把总数写成很多个指示变量之和，再用期望线性性。

示例解释：比如“三角形总数”可以写成： \[ X=\sum_{T} I_T, \] 其中 \(I_T\) 表示“给定三点组 \(T\) 是否形成三角形”的指示变量。那么 \[ \mathbb E[X]=\sum_T \mathbb E[I_T]. \] 每一项 \(\mathbb E[I_T]\) 只是一个小概率，算起来很简单。整个总数的期望，就被拆成一堆小块求和。所以这条性质是概率组合的“最常用起手式”之一。

97. 二次矩法 / 方差法（知识型）

除期望外，方差与二次矩也常用于证明随机对象集中在某个范围内。

前置：方差、二次矩、Chebyshev 不等式、概率集中思想。

定理解释：只知道期望，有时并不足以说明问题。因为“平均值很好”并不代表“大多数情况都很好”：也许随机变量波动特别大，平均只是少数极端值拉出来的。这时就需要看二次矩、方差这些衡量波动大小的量。若方差足够小，就说明随机变量通常不会离期望太远，于是可以从“平均上好”进一步升级成“高概率上也好”。所以二次矩法、方差法本质上是在回答： 这个随机对象是不是稳定？它是不是大多数时候都接近期望？ 在高阶概率组合中，这一步经常是必须的。

示例：研究某种结构“通常出现多少次”时，往往不能只算期望，还要估计方差，才能证明它真的会以很高概率出现在那个数量级附近。

示例解释：例如你算出某种坏结构的期望数只有 1，这并不一定代表“通常只有 1 个”。可能一半时候是 0，另一半时候是 100，也照样期望是某个小值。只有当你进一步知道方差也不大，才能说明这个数量不会剧烈波动。所以“期望法”解决的是存在性或平均规模问题，而“二次矩法 / 方差法”进一步研究的是集中性与稳定性。

98. 半随机法 / Alteration method（知识型）

先随机产生一个大对象，再删改少量坏部分，从而得到满足条件的对象。

前置：概率方法、极值思想、删改构造、局部修补思想。

定理解释：半随机法（alteration method）可以看作概率方法的一种非常实用的加强版。它的思想特别符合竞赛直觉：一开始不要求对象完美，只要求“整体上已经不错”；然后再把少量坏部分删掉、修掉、改掉，最后得到满足条件的对象。它之所以强，是因为很多时候“直接构造一个完美对象”非常困难，但“先随机得到一个差不多的大对象”却容易得多。如果坏部分数量不多，那么修补的代价就很小，于是整体仍然能保住主要优点。所以它是一种典型的“两步走”方法： 先粗造，再精修。

示例：构造一个边很多、但没有短环的图时，可以先随机取边，得到一个边数很多的随机图；然后把每个短环中删去一条边，最后就能得到无短环图，而且剩下的边仍然很多。

示例解释：这里最关键的是：随机图虽然不完美，但它的“坏结构”（短环）预计并不太多；而每个坏结构只需删掉很少一部分边就能破坏掉。于是最后删掉的总边数不大，图的大部分规模还保留下来了。这就是半随机法的典型威力：不要求第一次就命中完美答案，而是先抓住“主体足够大”，再用局部修改清除缺陷。

99. Szemerédi 型思想（知识型）

大的稠密整数集或图中，往往强制出现长等差数列或复杂规整结构。

前置：Ramsey 思想、稠密性、极值结构、长等差数列、伪随机与规整结构的直觉。

定理解释： Szemerédi 型思想可以概括成一句非常有力量的话： 只要一个离散对象足够大、足够稠密，那么它不可能一直保持完全无结构，最终一定会长出某种规整模式。 在整数集合里，这种规整模式通常表现为长等差数列；在图论或高维组合结构里，则可能表现为更复杂的规整子结构。它和 Ramsey 思想有亲缘关系，但更强调“密度”而不是“染色”：不是说你怎么分颜色都躲不开结构，而是说你只要保留了足够高的密度，就躲不开结构。所以这是一种非常深层的“稠密即有结构”思想。它对高阶组合、加法组合、图正则性理论都有巨大影响。

示例： Szemerédi 定理说明：若正整数的一个子集具有正密度，那么其中一定包含任意长的等差数列。

示例解释：这里“正密度”的意思可以粗略理解成：这个集合在大范围里并不稀薄，而是始终占有一个固定比例级别。 Szemerédi 定理说：只要一个集合一直足够密，就不可能无限地逃避长等差数列。它和 van der Waerden 定理都在讲“长等差数列终究会出现”，但视角不同： van der Waerden 强调有限染色下的单色结构必然出现； Szemerédi 强调高密度子集本身就必然含有长等差数列。所以它可以看成“从染色 Ramsey 思想走向密度结构思想”的一个重要升级。

100. 组合专题链条建议

高阶组合里常见的一条学习链是：

双计数
递推与生成函数
集合族与极值组合
图论与匹配
群作用与 Pólya
概率方法与小众工具

前置：前述主干条目。

定理解释：这一条不再是单个定理，而是整个组合工具树的学习框架。目的是让孩子知道哪些内容该先学、哪些该后补。

示例：若孩子目前只会排列组合和抽屉原理，那么下一步通常应先打通容斥、双计数、Catalan 和基础递推。

示例解释：因为这些内容是后面集合族、图论、概率方法的共同基础，先把主干打通，后面才不容易断层。

初等组合与竞赛组合定理总目录

总目录

一、基础计数原理

二、排列、组合与多重计数

三、二项式定理与经典恒等式

四、容斥原理与错排问题

五、抽屉原理与极值思想

六、递推关系与常见数列

七、生成函数入门

八、分拆理论与 Ferrers 图

九、Catalan 体系与路径计数

十、组合恒等式与双计数

十一、集合族与偏序理论

十二、Ramsey 理论与极值组合

十三、图论基础计数结论

十四、匹配、覆盖与网络流型结论

十五、染色、多项式与图计数

十六、对称群作用与计数

十七、设计、编码与有限几何相关结论

十八、竞赛组合小众定理清单