浅谈容斥原理

浅谈容斥原理

容斥原理

定理：

，则所有集合的并集可以表示成如下形式：

证明：

假设元素 a​ 被 x​ 个集合包含，显然左式中该元素的贡献为 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. 容斥原理