已知
- $S$ 为全集
- $A_{k}$ 为具有性质的 $P_{k}$ 的集合
则容斥原理
$$
\left| \bar{A}{1} \cap \bar{A}{2} \cap \dots \cap \bar{A}{n} \right| = \left| S \right| -\sum{i}\left| A_{i} \right| + \sum_{i\neq j}\left| A_{i}\cap A_{j} \right|-\dots+(-1)^{n}\left| A_{1}\cap A_{2}\cap\dots \cap A_{n} \right|
$$
应用
可以用容斥原理解决全错拍问题 记 $A_{k}$ 为第 $k$ 个人正确排列 则
- $\left| A_{i} \right|=(n-1)!$
- $\left| A_{i} \cap A_{j} \right|=(n-2)!$
- $\left| A_{i}\cap A_{j}\cap A_{k} \right|=(n-3)!$
- $\dots$
全错排方案数为
$$ \begin{align} \left| \bar{A}{1} \cap \bar{A}{2} \cap \dots \cap \bar{A}{n} \right| & = n! - C{n}^{1}\cdot(n-1)!+C_{n}^{2}\cdot(n-2)!-\dots \ & =n!\cdot \left[ 1-\frac{1}{1!}+\frac{1}{2!}-\dots+(-1)^{n} \frac{1}{n!} \right] \end{align} $$