组合数学、统一题库
与考前总复习
本页完成离散数学最后一章，并把十章练习按基础、提高、综合三层组织。先在“组合数学”建立方法，再用题库做针对性查漏，最后用速查表完成考前回顾。
组合数学 ⭐⭐⭐ 计数 / 二项式 / 容斥
组合数学的第一步不是代公式，而是先说清：对象是否按位置区分、是否允许重复、不同方案是否互斥。选对模型后，公式只是对计数过程的压缩。
| 方法 | 公式 | 何时使用 |
|---|---|---|
| 加法原理 ⭐⭐⭐ | 互斥的 \(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\)。 |
识别：位置有先后、每位可重复，是重复排列；首位有额外限制。
计算：首位有 \(9\) 种，其余五位各有 \(10\) 种，故方案数为 \(9\cdot10^5\)。
答案：\(\boxed{900000}\)。
二项式定理
展开时要从 \(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\)，常用于求递推的通项或受限计数。考题先写初值，再写递推的来源；只写递推式而忽略初值不能唯一确定数列。
十章统一题库 基础 8 · 提高 5 · 综合 3
每章均配置 16 题：基础题用于概念与公式反射，提高题训练两个知识点协同，综合题模拟证明或多步骤计算。点击章节筛选；每一题均给出思路、过程、答案与易错点。
离散数学考前总复习
高频公式
\(\neg\forall xP\equiv\exists x\neg P\)；\(A\triangle B=(A-B)\cup(B-A)\)；\(|A\cup B|=|A|+|B|-|A\cap B|\)。
\(\sum\deg(v)=2|E|\)；树有 \(n-1\) 条边；\(\binom nr=\frac{n!}{r!(n-r)!}\)。
高频定义
等价关系：自反、对称、传递；偏序：自反、反对称、传递；双射：既单又满；群：封闭、结合、幺元、逆元。
高频定理
Euler 回路：连通且全偶度；Euler 路：连通且零或两个奇度点；有限群子群阶整除群阶；连通平面图 \(v-e+f=2\)。
考前计算路线
逻辑题先真值/等值变形；关系题先列性质条件；图题先数度与分支；组合题先判断“有序、可重、是否重叠”。
高频证明模板
| 目标 | 推荐模板 |
|---|---|
| 证明集合相等 | 元素法：任取 \(x\)，连续写 \(x\in\) 左边 \(\Longleftrightarrow\cdots\Longleftrightarrow x\in\) 右边。 |
| 证明关系具某性质 | 从定义任取相关元素；把已知关系逐条代入；最后得到定义要求的关系。 |
| 证明是子群 | 先说明非空，再用 \(ab^{-1}\in H\) 的子群判别法。 |
| 证明树性质 | 反证：若有两条不同简单路径，则拼出回路；或用归纳法每次删去一片叶。 |
| 计数证明 | 先说明“每个对象被计数几次”；重叠问题用容斥，至少出现问题用鸽巢反证。 |
考前速查
看到 \(\to\)：优先换成 \(\neg P\lor Q\)。看到“任意/存在”的否定：量词互换并否定谓词。看到关系闭包：补自环、补反边、补路径边。看到“一笔画”：先判连通，再数奇度。看到“选若干个”：先问顺序与重复。看到“最小生成树”：Prim 保持一棵树，Kruskal 避免成环。
高频概念对比
| 概念 A | 概念 B | 关键区别 |
|---|---|---|
| \(x\in A\) | \(A\subseteq B\) | 前者是“元素—集合”关系；后者是“集合—集合”关系。 |
| 子集 | 真子集 | \(A\subseteq B\) 允许 \(A=B\)；\(A\subset B\) 还要求 \(A\ne B\)。 |
| 对称 | 反对称 | 对称要求 \(xRy\Rightarrow yRx\)；反对称要求双向相关时只能 \(x=y\)。 |
| 自反 | 反自反 | 前者所有 \((x,x)\) 都在关系中；后者所有 \((x,x)\) 都不在。 |
| 等价关系 | 偏序关系 | 二者都有自反、传递；等价加对称并形成划分，偏序加反对称并可画 Hasse 图。 |
| 单射 / 满射 / 双射 | — | 不合流 / 不遗漏陪域 / 同时满足二者；只有双射必有逆函数。 |
| Euler 路 | Hamilton 路 | 前者每条边恰一次；后者每个顶点恰一次。 |
| 极大元 | 最大元 | 极大元上方无更大可比元素，可有多个；最大元必须不小于所有元素，至多一个。 |
| 最小项 | 最大项 | 最小项只在对应输入行取 \(1\)，用于主析取范式；最大项只在对应输入行取 \(0\)，用于主合取范式。 |
| 对偶式 | 反演式 | 对偶交换 \(+,\cdot,0,1\)，不改变量；反演对整个表达式取补并用德摩根律。 |
项目验收记录
| 检查项 | 结论 |
|---|---|
| 三大模块入口与页面链接 | 高等数学、线性代数、离散数学入口均保留；离散数学十章均有已完成页面入口。 |
| 公式、真值表、卡诺图、矩阵与图示 | 统一使用 MathJax 配置；逻辑页、布尔页、图论页分别保留相应结构化内容。 |
| 移动端布局 | 各离散数学页面均使用侧栏折叠为横向导航、内容单列的媒体查询。 |
| 搜索 | 项目原有静态页面未配置跨页全文搜索；章节导航和页内锚点保持可用，未引入不完整的搜索入口。 |
| 内容状态 | 离散数学首页已改为完成态章节导航；十章入口均指向对应讲义或题库页面。 |
验收范围为静态页面结构、链接目标、公式配置与内容一致性检查。浏览器外部网络不可用时，MathJax 的下载与渲染需在具备网络的浏览器环境中加载。