容斥原理在 OI 中的应用
tsqtsqtsq0309
·
·
算法·理论
容斥原理
引入
假设班里有 10 个学生喜欢数学，15 个学生喜欢语文，21 个学生喜欢编程，班里至少喜欢一门学科的有多少个学生呢？
第一眼看到这一题，很多人可能直接会想到 10+15+21=46 个学生。然而，这只是一种理想情况。实际生活中，一个人不可能只会喜欢一种。反映到这道题上来说。也许有一部分既喜欢语文又喜欢数学，也许有一部分既喜欢语文又喜欢编程，也许有一部分既喜欢数学又喜欢编程，也许有一部分都喜欢。对于实际情况而言，如果只是简单粗暴地将每一部分的人数加起来，可能就会出现将部分同学算了几次的情况。在出现这种情况时，我们就需要将重复的部分减掉一份。具体地：
解：令集合 A=\left\{喜欢数学\right\}。相应地，B=\left\{喜欢语文\right\}，C=\left\{喜欢编程\right\}。则易知答案为：
ans=|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C| + |A\cap B\cap C|
上式便是容斥原理的一种简单应用。
定义
首先给出容斥原理的一般形式：
\begin{aligned}
\left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|-\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}
至于证明有两种方式：
- 数学归纳法
- 考虑每一个数的贡献
这里给出其中一种方式：
证明：当 n=2 时，等式显然成立(证明略)。
假设 n=s(s\ge 2,s\in \N^+) 时结论成立，则当 n=s+1 时：
|\bigcup^n_{i=1}A_i|=|\bigcup^{s+1}_{i=1}A_i|=|(\bigcup^s_{i=1}A_i)\cup A_{s+1}| \\
=|\bigcup^s_{i=1}A_i|+|A_{s+1}|-|(\bigcup^s_{i=1}A_i)\cap A_{s+1}| \\
=|\bigcup^s_{i=1}A_i|+|A_{s+1}|-|\bigcup(A_i\cap A_{s+1})| \\
=\sum_{1\le i_1\le s+1}|A_i|+\sum^s_{k=2}(-1)^{k-1}\sum_{1\le i_1<i_2<\cdots <i_k\le s}|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|+ \\
\sum^{s-1}_{k=1}(-1)^k\sum_{1\le i_1<i_2<\cdots<i_k\le s}|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|+ \\
\sum^{s-1}_{k=1}(-1)^k\sum_{1\le i_1<i_2\cdots<i_k\le s}|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}\cap A_{i_{s+1}}|+(-1)^s|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_s\cap A_{s+1}| \\
=\sum_{1\le{i_1}\le s+1}|A_i|+[\sum^s_{k=2}(-1)^{k-1}\sum_{1\le i_1<i_2<\cdots <i_k\le s}|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|+ \\
\sum^s_{k=2}(-1)^{k-1}\sum_{1\le i_1<i_2<\cdots <i_{k-1}\le s}|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_{k-1}}\cap A_{i_{s+1}}|]+(-1)^s|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_s\cap A_{s+1}| \\
=\sum_{1\le i_1\le s+1}|A_{i_1}|+\sum^s_{k=2}(-1)^{k-1}\sum_{1\le i_1<i_2<\cdots<i_k\le s+1}|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|+(-1)^s|A_1\cap A_2\cap\cdots\cap A_{s+1}| \\
=\sum^{s+1}_{k=1}(-1)^{k-1}\sum_{1\le i_1<i_2<\cdots<i_k\le s+1}|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}| \\
=\sum^{n}_{k=1}(-1)^{k-1}\sum_{1\le i_1<i_2<\cdots<i_k\le n}|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}| \\
所以当 n=s+1 时，结论仍成立。因此对任意 n\in \N^+,n\ge2 均可使所证等式成立。
应用
错排
给定 n 个数，将这 n 个数放入集合 S 中，试求出使得 \forall i \in [1, n], S_i \ne i 的方案数。
递推做法：
f_i=\begin{cases}
0, & i=1 \\
(n-1)\times f_{i-1}\times f_{i-2}, & otherwise \\
\end{cases}
直接求解 f_n 即可。
容斥做法：
直接求解错排的个数不是十分方便，我们可以转换一下思路。
很显然：错排个数 = 全排个数 - 不是错排的个数
ans=|U|-|\sum^n_{i=1}A_i| \\
=A^n_n-\sum_{i=1}^nA_i+\sum_{1\le i<j\le n}|A_i\cap A_j|-\sum_{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|...
对每一项进行分析：
对于第二项而言，|A_i| 表示第 i 个位置必须是 i，而其他位置可以随便搞，依据全排列相关结论可知 |A_i|=(n-1)!，则：
\sum_{i=1}^nA_i=n\times(n-1)!=\frac{n!}{1!}
对于第三项而言，|A_i\cap A_j| 表示第 i 个位置必须是 i 且第 j 个位置必须是 j（注意 i\ne j），而其他位置可以随便搞，依据全排列相关结论可知 |A_i\cap A_j|=(n-2)!，则：
\sum_{1\le i<j\le n}|A_i\cap A_j|=C^2_n(n-2)!=\frac{n!}{2!(n-2)!}(n-2)!=\frac{n!}{2!}
以此类推：
\sum_{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|=C^3_n(n-3)!=\frac{n!}{3!(n-3)!}(n-3)!=\frac{n!}{3!} \\
\sum_{1\le i<j<k<l\le n}|A_i\cap A_j\cap A_k\cap A_l|=C^4_n(n-4)!=\frac{n!}{4!(n-4)!}(n-4)!=\frac{n!}{4!} \\
\sum_{1\le i<j<k<l<m\le n}|A_i\cap A_j\cap A_k\cap A_l\cap A_m|=C^5_n(n-5)!=\frac{n!}{5!(n-5)!}(n-5)!=\frac{n!}{5!} \\
...
最终答案为：
ans=|U|-|\sum^n_{i=1}A_i| \\
=A^n_n-\sum_{i=1}^nA_i+\sum_{1\le i<j\le n}|A_i\cap A_j|-\sum_{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|... \\
=A^n_n-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+\frac{n!}{4!}-\frac{n!}{5!}... \\
=A^n_n-\sum^n_{i=1}(-1)^i\frac{n!}{i!}