容斥原理

容斥原理是指一种计数方法。先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。

两个集合的容斥原理
$$
n(A∪B)=n(A)+n(B) -n(A∩B)
$$

三个集合的容斥原理
$$
|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
$$

不难看出规律为：奇数次的加入，偶数次的剔除。

n个集合的容斥原理

$$
\left|\bigcup_{i=1}^{n} A_{i}\right|=\sum_{i=1}^{n}\left|A_{i}\right|-\sum_{1 \leq i<j \leq n}\left|A_{i} \cap A_{j}\right|+\cdots+\sum_{1 \leq i<j<k \leq n}\left|A_{i} \cap A_{j} \cap A_{k}\right|-\cdots+(-1)^{n-1}\left|A_{1} \cap \cdots \cap A_{n}\right|
$$

也可写成
$$
\left|\bigcup_{i=1}^{n} A_{i}\right|=\sum_{\emptyset \neq J \subseteq{1,2, \ldots, n}}(-1)^{|J|-1}\left|\bigcap_{j \in J} A_{j}\right|
$$
或

$$
\left|\bigcup_{i=1}^{n} A_{i}\right|=\sum_{k=1}^{n}(-1)^{k+1}\left(\sum_{1 \leq i_{1}<\cdots<i_{k} \leq n}\left|A_{i_{1}} \cap \cdots \cap A_{i_{k}}\right|\right)
$$
直观演示：【容斥原理背后的几何直觉-3个集合】
哔哩哔哩

从视频可以看出，偶数的重复了，然而剔除偶数次的过程导致奇数次也缺失了，故而之后需要加上（如果有的话）。

ps:MathpixShip识别公式的准确率还是很高的