min-max-容斥
\[\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}
\]
浙公網安備 33010602011771號