容斥原理
GYHL
·
·
算法·理论
引入
入门例题
假设班里有 10 个学生喜欢数学，15 个学生喜欢语文，21 个学生喜欢编程，班里至少喜欢一门学科的有多少个学生呢？
是 10+15+21=46 个吗？不是的，因为有些学生可能同时喜欢数学和语文，或者语文和编程，甚至还有可能三者都喜欢。
为了叙述方便，我们把喜欢语文、数学、编程的学生集合分别用 A,B,C 表示，则学生总数等于 \left| A\cup B\cup C\right|。刚才已经讲过，如果把这三个集合的元素个数 \left| A\right|,\left| B\right|,\left| C\right| 直接加起来，会有一些元素重复统计了，因此需要扣掉 \left| A\cap B\right|,\left| B\cap C\right|,\left| C\cap A\right|，但这样一来，又有一小部分多扣了，需要加回来，即 \left| A\cap B\cap C\right|。即
\left| A\cup B\cup C\right|=\left| A\right|+\left| B\right|+\left| C\right|-\left| A\cap B\right|-\left| B\cap C\right|-\left| C\cap A\right|+\left| A\cap B\cap C \right|
把上述问题推广到一般情况，就是我们熟知的容斥原理。
定义
设 U 中元素有 n 种不同的属性，而第 i 种属性称为 P_i，拥有属性 P_i 的元素构成集合 S_i，那么
\left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}\lvert S_i\rvert-\sum_{i<j}\lvert S_i\cap S_j\rvert+\sum_{i<j<k}\lvert S_i\cap S_j\cap S_k\rvert-\cdots\\
&+(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^{m}S_{a_i}\right|+\cdots+(-1)^{n-1}|S_1\cap\cdots\cap S_n|
\end{aligned}
\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right|
证明
对于每个元素使用二项式定理计算其出现的次数。对于元素 x，假设它出现在 T_1,T_2,\cdots,T_m 的集合中，那么它的出现次数为
Cnt=&|\{T_i\}|-|\{T_i\cap T_j|i<j\}|+\cdots+(-1)^{k-1}\left|\left\{\bigcap_{i=1}^{k}T_{a_i}|a_i<a_{i+1}\right\}\right|\\
&+\cdots+(-1)^{m-1}|\{T_1\cap\cdots\cap T_m\}|\\
=&\dbinom{m}{1}-\dbinom{m}{2}+\cdots+(-1)^{m-1}\dbinom{m}{m}\\
=&\dbinom{m}{0}-\sum_{i=0}^m(-1)^i\dbinom{m}{i}\\
=&1-(1-1)^m=1
\end{aligned}
于是每个元素出现的次数为 1，那么合并起来就是并集。
证毕。