浅谈容斥原理

2022-09-19 13:27:30 浏览数 (1)

浅谈容斥原理

容斥原理

定理：

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

证明：

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

个集合中所有子集中被计算到，其贡献为：

sum_{i=1}^xC_x^i(-1)^{i-1}=1-sum_{i=0}^xC_x^i(-1)^i=1

由于所有元素对于左右两式的贡献均为

应用

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

容斥的一些模型：

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

0 人点赞