子集反演推到容斥原理

引入

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

子集反演（补集形式）：

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|