容斥原理

求若干集合并集的大小时，直接相加会重复计数交集部分，容斥原理通过"加加减减"消除重复。

定义

对有限集合 $A,B$：

$$|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|$$

一般地

$$\left|\bigcup_{i=1}^{n}A_i\right|=\sum_{\emptyset\ne I\subseteq\{1,\dots,n\}}(-1)^{|I|+1}\left|\bigcap_{i\in I}A_i\right|$$

示例

1 到 100 中能被 2 或 3 整除的整数个数：$|A\cup B|=50+33-16=67$。

两个集合的情形可用维恩图验证；更一般的计数常配合组合数写出各项系数。