概念

容斥原理

通过「减去重复、加回多减」精确计算并集大小，可解错排问题；莫比乌斯反演是其在高维偏序集上的推广。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

容斥原理组合数学

01定义

容斥原理通过「加上单个、减去交叠、加回三交……」精确计算并集大小。它能解错排问题（每封信都不装对的装法数），其偏序集推广即莫比乌斯反演——数论与组合共用的核心工具。

三集合容斥：单加、双减、三加回

$|\bigcup A_i|=\sum|A_i|-\sum|A_i\cap A_j|+\cdots+(-1)^{k+1}\sum|\bigcap_{j=1}^k A_{i_j}|\cdots$ ——符号按交集深度交替。

全错位排列数 $D_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\approx\frac{n!}{e}$ ：对「至少一封信装对」取补并容斥， $e$ 竟出现在计数中。

容斥在整除格上即莫比乌斯反演： $g(n)=\sum_{d\mid n}f(d)\Rightarrow f(n)=\sum_{d\mid n}\mu(n/d)g(d)$ ——素数计数 $\pi(x)$ 的技术核心。

D_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}

\sum_{d\mid n}\mu(d)=\begin{cases}1,&n=1\\ 0,&n>1\end{cases}

错排问题由蒙莫尔 1708 年提出，伯努利与欧拉先后求解；莫比乌斯 1832 年引入 $\mu$ 函数，把容斥提升为数论反演工具。

概率论中「至少一次发生」的精确计算、筛法（埃拉托色尼筛、塞尔伯格筛）解析数论、可靠性工程的系统失效概率分析。

容斥原理：三个集合的并集计数调整各集合与交集大小，验证并集公式

|A|8|B|7|C|6两两交 |A∩B|2三交 |A∩B∩C|1