Min-Max 容斥

\[ made \ by \ Ameiyo \]

前言

这个东西给我的感觉有点类似 绝对值恒等式 。

为什么这么说呢？因为二者都是让不该做贡献的数的系数和为 $ 0 $ ，当然 Min-Max 荣斥 并没有绝对值。

先给出式子，这里用到一个东西叫，也不是很难的东西。

然后，以下用 Min(S) 表示集合 $ S $ 中最小的数， Max(S) 同理。

则有

\[Max(S) = \sum _{\varnothing \neq T \subseteq S} (-1) ^ {|T| - 1} Min(T)\]
把 Min 和 Max 交换也同样满足。

这其实是一个可以用容斥讲明的问题，这里从代数方面证明。

假设容斥系数为 $ d(x) $ 。

考虑某个第 $ k $ 大的数，当其做贡献时，比他小的数肯定不能出现在集合中，假设其选择了 $ i $ 个比他大的数。

那么他的系数和 \[ w_k = \sum _{i=0} ^{n-k} C_{n - k}^i d(i + 1) \] 。

而当 $ n = k $ 时， $ w_k = 1 $ ；否则， $ w_k = 0 $ 。即 \[ [n - k == 0] = \sum _{i = 0} ^{n - k} C_{n - k} ^i d(i + 1) \] 。

把上式二项式反演一下( $ f(n - k) = [n - k == 0] $ , $ g(i) = d(i + 1) $ ) ，就得到

\[d(n - k + 1) = \sum _{i = 0} ^{n-k} (-1) ^{n - k - i} C_{n - k}^{i} [i == 0] = (-1) ^ {n - k}\]

所以 $ d(i) = (-1) ^{i - 1} $ 。

证毕。

似乎是根据期望的线性性质，所以 Min-Max 容斥 在期望条件下也成立，即
\[Emax(S) = \sum (-1) ^{|T| - 1} Emin(T)\]
交换后同理。

\[ in \ 2019.12.8 \]