【算法学习笔记】min-max容斥 极值反演
max-min容斥（极值反演）即为下式；
\[\begin{equation}
\max\{S\}=\sum_{T\subseteq S}(-1)^{|T|+1}\min\{T\}
\end{equation}
\]
\[\begin{equation}
\min\{S\}=\sum_{T\subseteq S}(-1)^{|T|+1}\max\{T\}
\end{equation}
\]
证明： 证明 \(\text{(1)}\) 式即可，\(\text{(2)}\) 式同理。
假设 \(\max\{S\}=\sum\limits_{T\subseteq S}f(|T|)\min\{T\}\)，则 \(f(|T|)\) 为容斥系数
显然，第 \(k\) 小的元素，仅当 \(k\) 为 \(\min\{T\}\) 时有贡献，那么这样的集合 \(T\) 有 \(\sum\limits_{i=0}^{|S|-k}\binom{|S|-k}{i}\) 个。
则第 \(|S|\) 小的元素即为 \(\max\{S\}\)，由上可得
\[\sum_{i=0}^{|S|-k}f(i+1)\binom{|S|-k}{i}=[k=|S|]
\]
即为
\[\sum_{i=0}^{n}f(i+1)\binom{n}{i}=[n=0]
\]
引理1.1 二项式反演
\[g(n)=\sum_{i=0}^nf(i)\binom{n}{i}\Leftrightarrow f(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g(i) \]证明可见 OI-wiki
由 引理1.1 得
\[f(n+1)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}[i=0]
\]
将 \(f(n+1)\) 自变量化为 \(1\)，并整理
\[\begin{align}
f(n)&=\sum_{i=0}^{n-1}(-1)^{n-i-1}\binom{n-1}{i}[i=0]\\
f(n)&=(-1)^{n-1}
\end{align}
\]
带入 \(|T|\)
\[f(|T|)=(-1)^{|T|-1}=(-1)^{|T|+1}\quad\square
\]