容斥原理 学习笔记

容斥原理

容斥原理(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) \]