Set_Inversion

拆交集：

$$[ S \subseteq ( X \cap Y ) ] = [ S \subseteq X ] [ S \subseteq Y ]$$

容斥系数：定义 $\mu ( S ) = ( - 1 ) ^ {|S|}$。

那么我们就有结论：

$$\sum _ {S \subseteq U} \mu(S) = [U = \varnothing]$$

那么引出子集反演。

若有：

$$ f ( U ) = \sum _ {S \subseteq U} g ( S )$$

那么就有：

$$
\begin{aligned}
g ( U ) = & \sum _ {R \subseteq U} [U - R = \varnothing] g ( R )
\\
= & \sum _ {R \subseteq U} \sum _ {S \subseteq U - R } \mu ( S ) g ( R )
\\
= & \sum _ {S \subseteq U} \mu ( S ) \sum _ { R \subseteq U -
S} g ( R )
\\
= & \sum _ {S \subseteq U} \mu ( S ) f ( U - S )
\\
= & \sum _ {S \subseteq U} \mu ( U - S ) f ( S )
\end{aligned}
$$

所以说：

$$f ( U ) = \sum _ {S \subseteq U} g ( S ) \Leftrightarrow g ( U ) = \sum _{ S \subseteq U} \mu ( U - S ) f(S)$$

类似地有：

$$ f ( S ) = \sum _ {S \subseteq U} g ( U ) \Leftrightarrow g ( S ) = \sum _ {S \subseteq U} \mu ( U - S ) f ( U )$$

多重集中的反演，需要扩展一下 $\mu$ 的定义，即集合中如果有重复元素，则 $\mu ( S ) = 0$。

我们又有：

$$f ( U ) = \sum _ {S \subseteq U} \sum _ { T \subseteq S } \mu ( S - T) f( U - S)$$

实际上有些像莫比乌斯反演。