形式陈述

对有限集合 $A_1,\ldots,A_n$$A_1,\dots ,A_n$，

$$ \left|\bigcup_{i=1}^n A_i\right| =\sum_i|A_i|-\sum_{i<j}|A_i\cap A_j|+\cdots+(-1)^{n+1}|A_1\cap\cdots\cap A_n|. $$$$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _i|A_i|-\sum _{i<j}|A_i\cap A_j|+\cdots +(-1{)}^{n+1}|A_1\cap \cdots \cap A_n|.$$

直觉

先把每个集合的大小相加会重复计算交集；减去两两交集后又会少算三重交集，于是按交集阶数交替修正。

例子与边界

计算不超过 $N$$N$ 且能被 $2$$2$ 或 $3$$3$ 整除的整数个数时，加上两类数量并减去能被 $6$$6$ 整除的数量。无限集合的基数不能直接使用这个有限求和公式。

推论与应用

容斥用于错排计数、欧拉函数、概率事件并集和筛法；概率版本把基数替换为概率测度。

参考资料

• Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd ed., §2.1.
• Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd ed., §8.1.