学习目标
掌握定义、公式与定理条件；能使用原讲义中的真值表、矩阵、图表、分布和统计推断题完成练习。
第 9 章：组合数学
组合数学的第一步不是代公式，而是先说清：对象是否按位置区分、是否允许重复、不同方案是否互斥。选对模型后，公式只是对计数过程的压缩。
1. 本章复习目标
2. 知识框架
概念与性质
先厘清定义、条件和性质的联系。
公式与应用
再用题型模板、例题和练习完成方法迁移。
3. 核心知识点
原讲义内容
| 方法 | 公式 | 何时使用 |
|---|---|---|
| 加法原理 ⭐⭐⭐ | 互斥的 \(r\) 类方案总数 \(n_1+\cdots+n_r\) | 一次只能走其中一种路径，例如“选文科或理科专业”。若可同时发生，不能直接相加。 |
| 乘法原理 ⭐⭐⭐ | 连续 \(r\) 步方案数 \(n_1n_2\cdots n_r\) | 一个完整方案必须依次完成每一步，例如先选班级再选学生。 |
| 排列 ⭐⭐⭐ | \(P(n,r)=\frac{n!}{(n-r)!}\) | 从 \(n\) 个不同对象中取 \(r\) 个并排位，顺序不同算不同。 |
| 组合 ⭐⭐⭐ | \(\binom nr=\frac{n!}{r!(n-r)!}\) | 从 \(n\) 个不同对象中取 \(r\) 个，不分顺序。 |
| 重复排列 ⭐⭐ | \(n^r\) | 有 \(r\) 个位置，每一位可反复选 \(n\) 种符号。 |
| 重复组合 ⭐⭐ | \(\binom{n+r-1}{r}\) | 从 \(n\) 类对象中选 \(r\) 个，可重复且不计顺序；等价于非负整数解 \(x_1+\cdots+x_n=r\)。 |
例题：6 位密码由数字构成，首位不能为 0，允许重复。
识别：位置有先后、每位可重复，是重复排列；首位有额外限制。
计算：首位有 \(9\) 种，其余五位各有 \(10\) 种，故方案数为 \(9\cdot10^5\)。
答案：\(\boxed{900000}\)。
二项式定理
\[(a+b)^n=\sum_{k=0}^{n}\binom nk a^{\,n-k}b^k.\]
展开时要从 \(n\) 个因子中选 \(k\) 个因子贡献 \(b\)，其余 \(n-k\) 个贡献 \(a\)。选择这 \(k\) 个位置的方式有 \(\binom nk\) 种，因此该项系数正是组合数。求某一项时，先令 \(b\) 的幂或总次数满足题意，再代入对应的 \(k\)。
练习 1：求 \((2x-3)^5\) 中 \(x^3\) 项。
思路：把 \(a=2x,b=-3,n=5\)。要留下 \(x^3\)，需从五个因子中选 \(k=2\) 个取 \(-3\)。
过程：\(\binom52(2x)^3(-3)^2=10\cdot8x^3\cdot9\)。
答案：\(\boxed{720x^3}\)。
易错点：\(k\) 是取 \(b\) 的次数，不是 \(x\) 的次数。
鸽巢原理与容斥原理
鸽巢原理 ⭐⭐⭐
把 \(n+1\) 个对象放入 \(n\) 个盒子，至少一盒不少于 \(2\) 个。推广为：把 \(N\) 个对象放入 \(k\) 个盒子，至少有一盒不少于 \(\left\lceil\frac Nk\right\rceil\) 个。
反向思考：若每盒至多 \(r-1\) 个，总数至多 \(k(r-1)\)。超过它，就必有一盒至少 \(r\) 个。
容斥原理 ⭐⭐⭐
\(|A\cup B|=|A|+|B|-|A\cap B|\)。
\(|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|\)。
加单集时交集被重复计数，减去两两交集后三者交集又被多减一次，所以最后加回。
练习 2：13 名学生至少有多少人生日在同一月份？
思路：把学生看作对象，12 个月看作盒子，使用推广鸽巢原理。
过程：\(\lceil13/12\rceil=2\)。若每月至多一人，总数最多 12，与 13 矛盾。
答案：\(\boxed{2}\) 人。
练习 3：40 人中会英语 \(22\) 人，会日语 \(18\) 人，两种都会 \(8\) 人，至少会一种的有多少人？
思路：两种技能可以重叠，不能直接相加；用二集合容斥。
过程：\(|E\cup J|=22+18-8=32\)。
答案：\(\boxed{32}\) 人；两种都不会的有 \(40-32=8\) 人。
易错点：交集成员在 \(22+18\) 中被数了两次，必须减一次。
递推关系与生成函数（扩展）
递推关系把较大规模答案写成较小规模答案：例如 Fibonacci 数列 \(F_n=F_{n-1}+F_{n-2}\)。生成函数把数列 \((a_n)\) 编码为 \(A(x)=\sum_{n\ge0}a_nx^n\)，常用于求递推的通项或受限计数。考题先写初值，再写递推的来源；只写递推式而忽略初值不能唯一确定数列。
4. 常见题型
方法选择
原讲义中的判断方法、真值表、矩阵、图示、分布或统计计算流程均已完整保留在“核心知识点”区。
5. 典型例题
例题使用方式
先独立作答，再核对原讲义中的关键推导、公式条件与答案。
6. 练习题
练习与解析
原有折叠练习、完整解析与易错提示均保留在“核心知识点”区。
7. 易错点
8. 公式速查
| 复习顺序 | 使用要求 | 检查项 |
|---|---|---|
| 定义与定理 | 确认适用条件 | 对象、范围、已知条件 |
| 公式与计算 | 代入前保持符号一致 | 量词、集合符号、矩阵维数或概率参数 |
| 结论 | 说明结论范围 | 结果、逻辑方向与单位 |
9. 本章总结
必须记忆
核心定义、公式和定理条件。
必须理解
概念间的区别与方法选择依据。
必须会做
原讲义中的例题、练习与综合题型。
容易丢分
忽略前提、符号不严谨、混淆相近概念或跳过关键步骤。