Skip to main content

容斥原理

Summary

容斥原理（Inclusion–Exclusion Principle）用来计算多个集合并集的大小：先把各集合的大小相加，再减去两两交集，加回三三交集，如此按参与交集的集合个数的奇偶性交替加减。文中从两个、三个集合的具体式子写到 n 个集合的一般公式。随后给出 Min-max 容斥：用一个集合全部子集的最小值来表示它的最大值，反过来也成立，据此常把「所有事件都发生的期望时间」转化为更容易计算的「某一个事件发生的期望时间」，是处理期望类问题的常用工具。

参考资料​

容斥原理​

容斥原理（Inclusion–Exclusion Principle）计算多个集合并的大小：先加上各集合，减去两两交集，加回三三交集，按交集个数的奇偶交替加减。

两个集合​

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=|A|+|B|-|A\cap B|

三个集合​

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

多个集合​

∣⋃i=1nSi∣=∑m=1n(−1)m−1∑ai<ai+1∣⋂i=1mSai∣\left|\bigcup_{i=1}^nS_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right|

Min-max 容斥​

Min-max 容斥 用一个集合所有子集的 min⁡\min 表示其 max⁡\max（反之亦然），常用于期望问题，把「所有事件都发生的期望时间」转化为更易求的「某个事件发生的期望时间」。

max⁡S=∑T⊆S(−1)∣T∣−1min⁡T\max S=\sum_{T\subseteq S}{(-1)^{|T|-1}\min T} min⁡S=∑T⊆S(−1)∣T∣−1max⁡T\min S=\sum_{T\subseteq S}{(-1)^{|T|-1}\max T}