【学习笔记】min-max容斥

Posted on 2021-11-16 Edited on 2022-02-24

前言

好久以前就想学来着, 咕了大概快两年…

对于一个集合 $S$ , 设 $max(S)$ 为集合中最大的元素, $min(S)$ 为集合中最小的元素, 则有:

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

反过来也成立.

这个式子的原理在于:

$max(\{x\}) = min(\{x\}) = x$

证明:

构造容斥系数 $f(x)$ 使得原式成立.

$max(S) = \sum_{T \subseteq S}{f(|T|)min(T)}$

考虑集合 $S$ 中第 $k$ 小的数会被统计到的贡献, 就是枚举哪些集合的最小值为这个数.

$\sum_{i=0}^{n-k}{\binom{n-k}{i}f(i+1)} = [n-k = 0]$

把 $n-k$ 换一下, 更形式化的表示.

$\sum_{i=0}^x{\binom{x}{i}f(i+1)} = [x = 0]$

记 $F(x) = f(x+1), G(x) = [x = 0]$ .

则有,

$\sum_{i=0}^x{\binom{x}{i}F(i) = G(x)}$

二项式反演,

$F(x) = \sum_{i=0}^x{(-1)^{x-i} \binom{x}{i} G(i)} \\ =(-1)^x$

故,

$f(x+1) = (-1)^x\\ f(x) = (-1)^{x-1}$

所以原式成立.

$min-max$ 容斥对于期望同样满足, 可以很方便的解决一些概率期望问题.

即满足,

$\mathbb{E}(max(S)) = \sum_{T \subseteq S}{(-1)^{|T|-1}\mathbb{E}(min(S))}$

先给出公式

$kthmax(S) = \sum_{T \subseteq S}{(-1)^{|T|-k} \binom{|T|-1}{k-1} min(T)}$

考虑构造容斥系数 $f(x)$ 使得,

$kthmax(S) = \sum_{T \subseteq S}{f(|T|) min(T)}$

考虑第 $x$ 小的元素的贡献,

$\sum_{i=0}^{n-x}{\binom{n-x}{i}f(i+1)} = [n−x+1=k] \\ \sum_{i=0}^{x}{\binom{x}{i}f(i+1)} = [x = k-1]$

二项式反演,

$f(x+1) = \sum_{i=0}^{x}{(-1)^{x-i} \binom{x}{i} [i = k-1]} \\ f(x) = (-1)^{x-k} \binom{x-1}{k-1}$

证毕.

还是可以用于期望.