子集反演推到容斥原理

· · 算法·理论

引入

子集反演又叫容斥原理的一般化，但我之前一直不知道怎么用子集反演推导容斥原理，现在终于会了。

推导

子集反演（补集形式）：

f(S) = \sum_{T\supseteq S} g(T) \Leftrightarrow g(S) = \sum_{T\supseteq S} (-1)^{|T|-|S|}f(T)

设 f(S) := \text{钦定满足 S 中条件的元素个数} = \left| \bigcap_{i\in S}A_i \right|，g(S) := \text{恰好满足 S 中条件的元素个数}。U 为条件的全集，\Omega 为统计对象的全集。

那么有

f(S) = \sum_{S\subseteq T \subseteq U} g(T)

于是

g(S) = \sum_{S\subseteq T \subseteq U} (-1)^{|T|-|S|}f(T)

将 S=\varnothing 带入其中，得

g(\varnothing) = \sum_{T\subseteq U} (-1)^{|T|}\left| \bigcap_{i\in T}A_i \right|

又有

g(\varnothing) = |\Omega| - \left| \bigcup_{i\in U}A_i \right|

于是得到

\left| \bigcup_{i\in U}A_i \right| = \sum_{\varnothing \subset T\subseteq U}(-1)^{|T|-1}\left| \bigcap_{i\in T}A_i \right|