浅谈容斥原理

容斥原理

定理:

设有 $n$ 个集合,第 $i$ 个集合为 $A_i$,则所有集合的并集可以表示成如下形式:
$$
A_1\cup A_2\cup \cdots\cup A_n=\sum_{i=1}^n (-1)^{i-1}\sumA_1\cap A_2\cap\cdots\cap A_i
$$

证明:

假设元素 $a$​ 被 $x$​ 个集合包含,显然左式中该元素的贡献为 $1$,因为在并集内一个元素仅计算一次。

考虑其对于右式的贡献,显然它会被这个 $x$ 个集合中所有子集中被计算到,其贡献为:
$$
\sum_{i=1}^xC_x^i(-1)^{i-1}=1-\sum_{i=0}^xC_x^i(-1)^i=1
$$
由于所有元素对于左右两式的贡献均为 $1$,综上即可证得等式成立。

应用

容斥系数一般为 $(-1)^{S}$。

容斥的一些模型:

  1. 所有情况 $-$ 至少有一个 $+$ 至少有两个 $-\dots = $ 一个都没
  2. 全部都有 $-$ 一个也没 $=$ 至少有一个
  3. 至少有 $k$ 个 $- C_{k+1}^k \times $ 至少有 $k+1$ 个 $+ C_{k+2}^k\times $ 至少有 $k+2$ 个 $\dots = $ 恰好有 $k$ 个
  4. 补集转化
  5. $\min-\max$​ 容斥
  6. 容斥原理