数学大学
容斥原理的精妙
组合数学 · 容斥原理和鸽巢原理
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
容斥原理的精妙
组合数学 · 容斥原理和鸽巢原理
容斥原理的应用（1）
容斥原理的出发点：先全加，减重复，加回头，逐步精确。
两集合公式
|A∪B| = |A|+|B|−|A∩B|
思想
多算的减掉，减多的加回
容斥原理的应用（2）
三集合容斥：加三个单集、减三个交集、加回三个集的交。
符号交替
按交集元素个数奇偶交替加减
韦恩图辅助
七个区域逐块核对不重不漏
容斥原理的应用（3）
一般容斥公式：对任意属性组合求交，符号按属性个数确定。
一般公式
N(恰含 r 属性) 用子集和的交替和表达
核心动作
枚举属性子集求交，正负号按 |子集| 定
本节要点
- ✓两集合：加、减一次交
- ✓三集合：三加三减再加一
- ✓一般公式：子集求交，奇偶定号
延伸主题：算一次三人重叠计数推导四集合公式符号规律
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1容斥原理为什么符号必须交替加减？
参考答案一个元素若恰属于 k 个集合，它在单集合和中被加 k 次、两两交中被减 C(k,2) 次……按子集大小交替累加后，恰使只有当 k 等于目标个数时净贡献为 1，其余为零。交替符号是精确校正的机制。
2容斥在数「恰含 r 个属性」时为什么还要用到更大子集的交？
参考答案恰含 r 个属性的元素也属于包含它们的更大属性子集，会污染直接统计。必须用全部子集的交替和做系统性校正，把多余贡献逐层消去，才能隔离出精确的 r 属性计数。
3容斥原理与「反面计数」是什么关系？
参考答案求「至少一项满足」本身就是一个容斥计算：并集大小由各集合及其交交替加减得到。先容斥出并集，再用总数减去并集，就是全不满足的计数——容斥常是反面计数的引擎。