容斥原理

引入

入门例题

假设班里有

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$ 的集合中，那么它的出现次数为 $$\begin{aligned} 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$，那么合并起来就是并集。 证毕。