容斥原理简述

大家好，欢迎来到IT知识分享网。

1. 问题引入

主要用来解决集合的计数问题。

最常见的应用题，A活动多少人，B活动多少人，AB两活动多少人之类的。

两三个集合的时候还能画图进行识别，三个以上的集合则看不太出来了。

2. 公式

$$\begin{gathered} \left|A_1\cup A_2\cup A_3\dots \cup A_m\right|=\sum _{1\le i\le m}\left|A_i\right|- \\ \sum _{1\le i<j\le m}\left|A_i\cap A_j\right|+ \\ \sum _{1\le i<j<k\le m}\left|A_i\cap A_j\cap A_k\right|-\dots \\ +(-1{)}^{m-1}\left|A_1\cap A_2\cap A_3\dots \cap A_m\right|= \\ \sum _{k=1}^n(-1{)}^{k-1}\sum _{1<i_1<i_2<\dots <i_k\le n}|A_{i_1}\cap A_{i_2}\dots A_{i_k}| \end{gathered}$$

3. 证明

引入1
$$\left|\bigcup _{i=1}^n{A}_i\right|=\left|A_1\cup A_2\dots A_i\right|$$
引入2 德摩根定理
$$\begin{gathered} \overline{A\cup B}=\overline{A}\cap \overline{B} \\ \overline{A\cap B}=\overline{A}\cup \overline{B} \end{gathered}$$

数学归纳法

当 n = 2 时
$$\left|A_1\cup A_2\right|=\left|A_1\right|+\left|A_2\right|-\left|A_1\cap A_2\right|$$
成立。
假设当$n=s(s\ge 2,s\in N^{\ast })$时，结论成立。则当$n=s+1$

$$\begin{gathered} \left|\bigcup _{i=1}^n{A}_i\right|=\left|\bigcup _{i=1}^{s+1}{A}_i\right|=\left|\left(\bigcup _{i=1}^s{A}_i\right)\cup A_{s+1}\right| \\ = \\ \left|\bigcup _{i=1}^s{A}_i\right|+\left|A_{s+1}\right|-\left|\left(\bigcup _{i=1}^s{A}_i\right)\cap A_s\right| \\ = \\ \left|\bigcup _{i=1}^s{A}_i\right|+\left|A_{s+1}\right|-\left|\bigcup _{i=1}^s(A_i\cap A_{s+1})\right| \\ = \\ \sum _{1\le i_1\le s+1}\left|A_i\right|+\sum _{k=2}^s(-1{)}^{k-1}\sum _{1\le i_1<i_2<i_3..\le s}\left|A_{i_1}\cap A_{i_2}\cap A_{i_3}\dots \cap A_{i_k}\right|+\sum _{k=2}^{s+1}(-1{)}^{k-1}\sum _{1\le i_1<i_2\dots <i_k\le s+1}|A_{i_1}\cap A_{i_2}\cap A_{i_3}..A_{i_k}| \\ = \\ \sum _{1\le i\le s+1}|A_i|+\sum _{k=2}^s(-1{)}^{k-1}\sum _{1\le i_1<i_2<i_3..i_k\le s}\left|A_{i_1}\cap A_{i_2}\cap A_{i_3}\dots \cap A_{i_k}\right|+\sum _{k=2}^s(-1{)}^{k-1}\sum _{1\le i_1<i_2<i_3..\le i_k\le s+1}\left|A_{i_1}\cap A_{i_2}\cap A_{i_3}\dots \cap A_{i_k}\right|+(-1{)}^s|A_1\cap A_2\cap A_3\cap \dots A_{s+1}| \\ = \\ \sum _{1\le i\le s+1}|A_i|+\sum _{k=2}^{s+1}(-1{)}^{k-1}\sum _{1\le i_1<i_2..i_k\le s+1}|A_{i_1}\cap A_{i_2}\cap \dots A_{i_k}|+(-1{)}^s|A_1\cap A_2\cap A_3\cap \dots A_{s+1}| \\ = \\ \sum _{k=1}^{s+1}(-1{)}^{k-1}\sum _{1\le i_1<i_2<i_3\dots <i_k\le s+1}|A_{i_1}\cap A_{i_2}\dots \cap A_{i_k}| \end{gathered}$$
成立得证。

另一种证明则是元素出现个数的时候的证明,参见OI_WIKI。

参考