$$
\begin{aligned}
\max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-1}\min(T)\
\min(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-1}\max(T)
\end{aligned}
$$

这里只证明第一个式子,下一个式子类似可证。

设集合 $S={a_i},|S|=n$ 满足 $i<j\Leftrightarrow a_i<a_j$,由此我们有:

$$
\begin{aligned}
\sum\limits_{T\subseteq S}(-1)^{|T|-1}\min(T)&=\sum\limits_{i=1}^na_i\sum\limits_{j=0}^{n-i} (-1)^{j+1}\dbinom{n-i}{j}\
&=\sum\limits_{i=1}^na_i[n-i=0]=a_n=\max(S)
\end{aligned}
$$

应当注意到的是,假设具有一般性,而非特殊性。

min-max 容斥还有扩展形式,设 $\max_k(S)$ 集合 $S$ 中的第 $k$ 大值,$\min_k(S)$ 为集合 $S$ 中的最小值,则我们有:

$$
\begin{aligned}
max_k(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\min(T)\
min_k(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\max(T)
\end{aligned}
$$

同样由上面的假设,我们可以得到:

$$
\begin{aligned}
\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\min(T)&=\sum\limits_{i=1}^na_i\sum\limits_{j=0}^{n-i}\dbinom{n-i}{j}\dbinom{j}{k-1}(-1)^{j+1-k}\
&=\sum\limits_{i=1}^na_i\sum\limits_{j=0}^{n-i}\dbinom{n-i}{k-1}\dbinom{n-i-k+1}{j-k+1}(-1)^{j+1-k}\
&=\sum\limits_{i=1}^na_i\dbinom{n-i}{k-1}\sum\limits_{j=0}^{n-i}\dbinom{n-i-k+1}{j-k+1}(-1)^{j+1-k}\
&=a_{n-k}
\end{aligned}
$$