容斥原理 学习笔记

容斥原理

容斥原理(principle of inclusion-exclusion)：令 $X$ 为一个有限集合，$P_1, P_2,\dots , P_m$ 是一些性质的集合。

对于任意 $S \subseteq [m]$ ，即 $S\subseteq \{1,2,\cdots,m\}$ ，定义 $N(S) = \{x \in X \mid \forall i \in S : x \text{ has } P_i\}$ 。

那么 $X$ 中满足性质 $P_{1\sim m}$ 的元素个数为

$$\sum_{S \subseteq [m]} (-1)^{|S|+1} \left|N(S)\right|$$

如果是不满足任何一个性质的话，把指数中的 $|S|+1$ 改成 $|S|$ 即可。

特别地，对于任意的 $S \subseteq [m]$ ，如果 $N(S)$ 只和 $S$ 的大小（即 $|S|$ ）有关，那么式子可以化简为

$$\sum_{i=0}^{m} (-1)^{i+1} \binom{m}{i} N(i)$$

其中 $N(i)$ 表示对于任意满足 $S \subseteq [m],|S|=i$ 的 $N(S)$ 值。

如果是不满足任何一个性质的话，把指数中的 $i+1$ 改成 $i$ 即可。

问题来了，这个 $(-1)^{|S|+1}$ 是怎么来的呢？

从本质上理解的话，我们给属性集合 $S\subseteq[m]$ 赋予了一个容斥系数 $f(|S|)$

我们要让拥有 $m$ 个属性的元素只被算一次，因此考虑这个元素被哪些属性集合枚举到，得

$$\sum_{i=1}^m\dbinom{m}{i} f(i)=1$$

一个合理而简洁的构造为 $f(i) = (-1)^{i+1}$ ，代入可知正确。

---

利用容斥原理解题

容斥的经典做法。

1. 定义一些“坏性质” $P_1,\dots,P_m$

2. 找到对于每个 $S\subseteq [m]$ 计算 $N(S)$ 的方法

3. 套用容斥原理计算不满足任何一个“坏性质”的元素个数

4. 注意这里求的是不满足任何坏性质，因此用以下公式

   $$\sum_{S \subseteq [m]} (-1)^{|S|} \left|N(S)\right|$$

---

子集反演

咕咕咕。。。

---

一般化的容斥

这里还在咕咕咕。。。。

设有 $n$ 个条件 $P_i$ ，物品集合 $U$

考虑每个物品的贡献，则计数形式常为

$$\sum_{i=1}^{n}\sum_{x \in U} f(S_i)c(x,S_i)$$