数学大学
回忆过去，容斥新解
组合数学 · 容斥原理和鸽巢原理
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
回忆过去，容斥新解
组合数学 · 容斥原理和鸽巢原理
容斥原理的应用（4）
经典应用：错位排列——n 个元素都不在原位的排列数。
错排公式
Dₙ = n!·Σ(−1)ⁱ/i!
容斥视角
全排列减去「至少一个归位」的各情形
容斥原理的应用（5）
区间与整除计数：用容斥处理「至少能被某素数整除」的重叠。
整除计数
被 d 整除的个数为 ⌊N/d⌋
素数组合
同时被多素数整除按乘积取交
容斥原理的应用（6）
互补转化：直接数「都不满足」困难时，用容斥从反面计算。
反面计数
都不满足 = 总数 − 至少一项满足
设计要点
让「至少一项」的交容易刻画
错排自测
点击作答
3 个元素全部不在原位的错排数是多少？
本节要点
- ✓错排：Dₙ = n!·Σ(−1)ⁱ/i!
- ✓整除计数按素数组合求交
- ✓直接难数就从反面容斥
延伸主题：推导错排递推 Dₙ=(Dₙ₋₁+Dₙ₋₂)(n−1)用容斥算一次互质计数
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1错排问题为什么特别适合用容斥？
参考答案直接数「每个元素都不归位」相互牵连，难以直接构造；而它的反面「至少有一个元素归位」的子集交非常容易刻画（固定某几个元素，其余随意排列）。容斥把难问题变成一堆简单问题。
2互补转化「从反面数」的思想何时最有效？
参考答案当「都不满足」的结构分散难刻画，而「至少满足某一项」的集合及其交易于描述时最有效。容斥的价值正在于把不规则的正面转化为规则的反面之并。
3韦恩图对几个集合开始失效？失效后靠什么？
参考答案韦恩图直观到三集合为止；四集合已难画准，更多集合不可行。失效后依靠一般容斥公式——它不依赖图形，按属性子集枚举求交并按基数定号，是可编程的通用方法。