奥数专题 · 专题二：组合数学

合

专题二：组合数学

Combinatorics · 数"有多少种"的学问

"任意 6 个人里必有 3 个互相认识或互相不认识"——听着像玄学？其实就是"5 只鸽子飞进 4 个巢，必有一个巢住俩"。组合数学的妙处，是用废话推出硬结论。

卡必背公式 / 记忆口诀

鸽巢原理（抽屉原理）

容斥原理（加减加减）

拉姆齐数 R(3,3)=6

口诀：组合核心——数东西

这一节在六专题里的位置：上节数论研究"一个整数的脾气"，这节研究"一堆东西有几种排法"。因为计算机本质是在"数可能性"，组合数学直接喂给概率算法、搜索引擎倒排、随机化算法。

这节要学：加法/乘法原理 → 鸽巢 → 排列组合 → 容斥

合是什么：数"一共有多少种可能"

排队多少种、握手多少次、走路几条道——组合数学不关心某一个数，只关心"有多少种"。竞赛常考：加法原理与乘法原理、排列组合、鸽巢原理、容斥原理、递推计数、卡特兰数入门。

两句口诀："或"字一出用加法（分类），"先…再…"一出用乘法（分步）。排队讲究顺序是排列，组队不讲究顺序是组合。

路考点心法：看到「专题二：组合数学」先想什么

• 题型识别：先看是数论/组合/几何/不等式/函数方程哪类——不同类型有不同套路

• 方法选择：抽屉原理/染色法/反证法/构造法/不变量——奥数就这几把刷子

• 别忘验证：竞赛题有陷阱——算出答案要检查边界条件

想怎么想到的：三问定方向

问一："分类还是分步？"互斥的几类用加，缺一不可的几步用乘。问二："有没有'至少'两个字？"有——立刻切换补集模式，数"一个都没有"。问三："有没有'任意'？"有——上鸽巢原理，想清楚谁当鸽子、谁当笼子。

核心方法三招

巢方法一：鸽巢原理

n+1 只鸽子进 n 个巢，必有一个巢住了至少 2 只。听起来像废话，用起来是杀招：证明"必有两人生日同月""必有两数同余"全靠它。

容方法二：容斥原理（补集思想）

"至少有一个"正着数最容易漏、容易重；反着数——先数"一个都没有"，再从总数减掉。|A∪B| = |A| + |B| − |A∩B|，多退少补。

递方法三：递推计数

总数数不清？看"最后一步"：f(n) = 从 n−1 上来的 + 从 n−2 上来的。把大问题拆成小问题，递归到底。卡特兰数就是这么来的。

经典例题

先审题憋三分钟，再点开看完整过程。

例1. 10 个人围坐一张圆桌吃饭，有多少种不同的坐法？

审题："围圆桌"——大家一起顺移一个位子，实际还是同一桌。

思路：先直线排，再除掉重复的旋转。

逐步解法：直线排 10 人有 10! 种；圆桌上顺时针转 1~10 个位置算同一种，要除以 10：坐法 = 10!÷10 = 9! = 362880。也可以先钉死一个人不动，剩下 9 人全排列 9!。

答案：9! = 362880 种

【自评反馈】和答案对得上 → 继续下一题；对不上 → 回到本页"是什么"和例题区，把卡住的那步再推一遍。

例2. 证明：任意 6 个人中，必有 3 人互相认识，或必有 3 人互相不认识。（R(3,3)=6）

审题：把人画成点，认识画红线、不认识画蓝线，要证必有同色三角形。

思路：任取一点看它的 5 条线——鸽巢原理逼它至少 3 条同色。

逐步解法：取 A，连出 5 条线，至少 3 条同色。不妨设红（A 认识 B、C、D）。再看 B、C、D 之间：若有一条红线（如 BC 红），则 A、B、C 三人两两认识，红三角形；若一条红线都没有，则 B、C、D 两两不认识，蓝三角形。两种情况必居其一。

证毕：6 人中必有 3 个互为熟人或互为陌生人

【自评反馈】和答案对得上 → 继续下一题；对不上 → 回到本页"是什么"和例题区，把卡住的那步再推一遍。

例3. 从 (0,0) 出发每步向右或向上走到 (n,n)，且始终不穿过对角线 y=x，路径有多少条？（卡特兰数入门）

审题：无限制时总路径 C(2n,n)，现在要剔除"犯规"路径。

思路：补集——总数减去"穿过对角线"的路径数。

逐步解法：总路径 = C(2n,n)。犯规路径用反射法一一对应到"从 (0,−1) 到 (n,n)"的路径 = C(2n, n−1)。合法路径 = C(2n,n) − C(2n,n−1) = $\frac{C(2n,n)}{n+1}$。n=3 时 = C(6,3)/4 = 5 条。

答案：第 n 个卡特兰数 Cₙ = (2n)! / (n!·(n+1)!)

【自评反馈】和答案对得上 → 继续下一题；对不上 → 回到本页"是什么"和例题区，把卡住的那步再推一遍。

用用途与案例

现实里：彩票中奖概率、扑克牌手牌、招聘选人、日程排班全靠它。科研里：鸽巢原理是"证明一定存在"的万金油；卡特兰数数的不只是走路，还有合法括号序列、二叉树形态、进出栈序列——程序员天天用。

延延展：往楼上走一步

组合往上是图论与拉姆齐理论：R(3,3)=6 只是个开头，"任意 n 个人里必有多少个互相认识/不认识"是现代组合数学的大问题，计算机科学家还在算。容斥往上是概率的 inclusion-exclusion，是概率论的骨架。

防坑警示

坑一：圆桌忘了除以 n。10! 当答案就错了——直线排队和圆桌不是一回事。为什么错：旋转算同一种坐法。怎么改：圆桌先钉死一个人，剩下的全排列。

坑二：排列组合搞混。"选 2 个人分任正副组长"是排列（20 种），"选 2 个组员"才是组合（10 种）。为什么错：没问自己"顺序重不重要"。

奥数思维点拨 · 组合

突破口：把"至少有一个"翻译成"总数减去一个都没有"。正着数十个有九个错——"或"字一出现边界就模糊。先退一步问："反过来，什么都没发生有多少种？"总数一减，答案自己跳出来。

费曼学习法：讲给别人听

① 用自己的话讲：组合就是用废话推硬结论：鸽巢原理说"n+1 只鸽子进 n 个巢必有一双"，计数时用加/乘/容斥三件套。

② 举个反例（什么条件下不成立）：鸽巢原理只保证"存在"，不告诉你在哪；重复计数时不除以分类数会翻倍算错。

③ 哪里还说不清：什么时候该用插板法、什么时候用隔板法？

记

本专题小结

① 分类加、分步乘；排列看顺序、组合不看。② "至少"想补集，"任意"想鸽巢。③ 圆桌先钉死一个人。

费曼学习法

合上书，给一个完全不懂的人讲清楚「专题二：组合数学」——说不清楚的地方就是你没真懂的。

证专题二：组合数学的关键定理与公式

核心性质：① 鸽巢原理（加强形式）：把 $n$ 个物品放进 $k$ 个抽屉，则至少有一个抽屉里不少于 $\left\lceil \frac{n}{k} \right\rceil$ 个物品；$n=k+1$ 时即为"必有一个抽屉至少 $2$ 个"。
② 容斥原理：$|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |B\cap C| - |C\cap A| + |A\cap B\cap C|$。
③ 拉姆齐数：$R(3,3)=6$，即任意 $6$ 人中必有 $3$ 人互相认识或 $3$ 人互相不认识，而 $5$ 人时未必。
④ 范德蒙德恒等式：$\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$。

推导（不跳步）：以 $R(3,3)=6$ 为例——① 任取 $6$ 人中的一人，记作 $X$。② $X$ 与其余 $5$ 人的关系只有"认识"或"不认识"两种，$5$ 个人分进 $2$ 个抽屉，由鸽巢原理必有至少 $\left\lceil\frac{5}{2}\right\rceil = 3$ 人与 $X$ 同类（都认识或都不认识）。③ 设这 $3$ 人都与 $X$ 认识，分别记为 $A,B,C$。④ 若 $A,B,C$ 中有任意两人互相认识，比如 $A$ 认识 $B$，则 $X,A,B$ 三人两两认识，得证。⑤ 若 $A,B,C$ 中任意两人都不认识，则 $A,B,C$ 本身就是三个互不相识的人，也得证。
再看 $5$ 人为何不够：把 $5$ 人排成一圈，每人只认识左右邻居——既找不到三人两两认识，也找不到三人两两不认识。

直觉把握：鸽巢原理说的是"东西比格子多，挤是必然的"——不告诉你哪个格子挤，只保证一定存在。拉姆齐定理就是把这个"必然"连推两层：第一层用鸽巢找出 $3$ 个同伙，第二层在这 $3$ 人内部二选一。组合数学的杀伤力就在这儿：只用废话推出硬结论。

例题：证明边长为 $2$ 的正方形内任取 $5$ 个点，必有两个点距离不超过 $\sqrt{2}$

【审题】"必有"二字直指鸽巢原理——关键是抽屉怎么划。

逐步：① 把正方形均分成 $4$ 个边长为 $1$ 的小正方形，这就是 $4$ 个抽屉。② $5$ 个点放进 $4$ 个抽屉，由鸽巢原理必有两个点落在同一个小正方形内。③ 小正方形内两点最远也就是它的对角线，长度为 $\sqrt{1^2+1^2}=\sqrt{2}$。④ 答案：必存在两点距离 $\le \sqrt{2}$，证毕。
现代应用：这就是哈希碰撞的数学原型——$n+1$ 个键塞进 $n$ 个桶，冲突必然发生。布隆过滤器"一定有误判率"、负载均衡"总有一台机器更忙"，都是同一条鸽巢原理在说话。

例题：$1$ 到 $100$ 中，能被 $2$ 或 $3$ 或 $5$ 整除的数有多少个？

【审题】出现"或"字，说明集合有重叠，直接相加会重复计数——容斥原理出场。

逐步：① 先加单倍的：$\lfloor\frac{100}{2}\rfloor + \lfloor\frac{100}{3}\rfloor + \lfloor\frac{100}{5}\rfloor = 50+33+20 = 103$。② 减去两两重叠的：$\lfloor\frac{100}{6}\rfloor + \lfloor\frac{100}{10}\rfloor + \lfloor\frac{100}{15}\rfloor = 16+10+6 = 32$。③ 加回三重重叠的：$\lfloor\frac{100}{30}\rfloor = 3$。④ 合起来 $103 - 32 + 3 = 74$。⑤ 答案：$74$ 个。
现代应用：容斥就是数据库与搜索引擎里的集合计数——"符合关键词 A 或 B 或 C 的文档有几篇"必须去重，否则同一个文档会被数三遍；位图索引求并集大小，用的正是这个加减加减。

例题：证明 $\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$（范德蒙德恒等式）

【审题】左边是"求和"，右边是"一个组合数"——这类题的标准打法是双计数：同一个东西用两种方式数。

逐步：① 设想有 $m$ 个男生、$n$ 个女生，要从中选出 $r$ 个人，直接的选法就是 $\binom{m+n}{r}$。② 换一种数法：按"选了几个男生"分类，若选 $k$ 个男生则必选 $r-k$ 个女生，这一类有 $\binom{m}{k}\binom{n}{r-k}$ 种。③ 把所有 $k$ 从 $0$ 到 $r$ 的情况加起来，就是左边。④ 两种方法数的是同一件事，故相等。⑤ 答案：恒等式成立。
现代应用："同一个量用两种方式算"是算法分析里估复杂度的常用套路；而范德蒙德恒等式本身在概率论里就是"两个独立二项分布相加仍是二项分布"的代数版本。

④ 用途与案例

工程：专题二：组合数学

在工程、物理、计算机、金融等领域，专题二：组合数学是基础工具——理解"使用场景"比死记公式重要。

日常：你见过但没注意的专题二：组合数学

生活中处处有专题二：组合数学——价格波动、几何造型、统计图表、游戏设计——只不过没人告诉你这就是数学。