Skip to main content

容斥原理

参考资料​

容斥原理​

两个集合​

∣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}^{n}S_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 容斥​

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}}