Min-Max 容斥

标签：dots min Max Min 容斥 max

记号

记全集 \(U=\{a_1,a_2,\dots,a_n\}\)。

设 \(\min(S)=\min\limits_{a_i\in S}a_i\)，\(\max(S)=\max\limits_{a_i\in S}a_i\)。

---

Min-Max 容斥定理

就是两个东西：

\[\max(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\min(T) \]

\[\min(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\max(T) \]

证明第一个。

将 \(U\) 降序排序，第 \(k\) 大即为 \(a_k\)。

考虑 \(\min(T)=a_k\) 的 \(k\) 的情况。

若 \(k=1\)，只有 \(T=\{a_1\}\)，贡献为 \((-1)^2a_1=a_1\)。

若 \(k>1\)，集合内只能存在 \(a_1,\dots,a_k\)，\(a_1,\dots,a_{k-1}\) 共 \(2^{k-1}\) 种选法，分别有 \(2^{k-2}\) 种 \(|T|\) 为奇数和偶数的情况，贡献为 \(0\)。

得证。第二个同理。

Min-Max 容斥定理在期望下也成立：

\[E(\max(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(\min(T)) \]

标签：dots,min,Max,Min,容斥,max
From： https://www.cnblogs.com/SError0819/p/18036568