容斥原理备忘录

2020-05-20

记录以备忘.

综述

虽然是很基础的东西, 但是不妨回头再看它一眼.

又因为本文定位于备忘, 所有不会有关于任何公式的证明, ~~其实就是公式的罗列~~… 如果真的对证明感兴趣, 不妨去文末的参看资料看看.

设全集 $U$ 中有 $n$ 中不同条件 $P_{i\ldots n}$, 记 $A_i$ 为满足条件 $P_i$ 元素的集合.

$| \bigcup_{i = 1} ^ n A_i | = \sum_{k = 1} ^ n (-1) ^ {k - 1} \sum_{1 \le i_1,\ \cdots,\ i_k \le n} | \bigcap_{j = 1} ^ k A_{i_j} |$

$|\bigcap_{i = 1} ^ n A_i| = |U| - |\bigcup_{i = 1} ^ n \bar A_i|$

直接将之前的式子带入, 则有

$|\bigcap_{i = 1} ^ n A_i| = |U| - \sum_{k = 1} ^ n (-1) ^ {k - 1} \sum_{1 \le i_1,\ \cdots,\ i_k \le n} | \bigcap_{j = 1} ^ k \bar A_{i_j} |$

进一步可以得到

$|\bigcap_{i = 1} ^ n A_i| = \sum_{k = 0} ^ n (-1) ^ k \sum_{1 \le i_1,\ \cdots,\ i_k \le n} |\bigcap_{j = 1} ^ k \bar A_{i_j}|$

至于其他情况, 可用摩根定律进行转化.

很多时候集合中元素具体是什么不会影响结果, 此时枚举集合大小同时乘一个组合数作为系数就可以得出一些式子.

$g(n) = \sum_{k = n} ^ m \binom{k}{n} f(k) \Leftrightarrow f(n) = \sum_{k = n} ^ m (-1) ^ {k - n} \binom{k}{n} g(k)$

虽然本质是容斥原理, 但是在实际中可能 (?) 会更好用一点.

此时的 $f(n)$, $g(n)$ 有组合意义, 例如 $f(n)$ 表示在总共 $m$ 个物品中, 恰好选择 $n$ 个满足某个条件元素的方案数, $g(n)$ 表示钦定 $n$ 个满足某个条件元素的方案数.

记 $f(S)$, $g(S)$ 为两个关于集合 $S$ 的函数, 那么有

$f(S) = \sum_{T \subseteq S} g(T) \Leftrightarrow g(S) = \sum_{T \subseteq S} (-1) ^ {|S| - |T|} f(T)$

类似地, 有

$f(S) = \sum_{S \subseteq T} g(T) \Leftrightarrow g(S) = \sum_{S \subseteq T} (-1) ^ {|T| - |S|} f(T)$

对于一个集合 $S$, 记 $\max\{S\}$ 为集合 $S$ 中最大值, $\min\{S\}$ 为集合 $S$ 中最小值, 那么有

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

同时可以推广到第 $k$ 大值. 记 $\operatorname{kmax}\{S\}$ 为集合 $S$ 中的第 $k$ 大值, 那么有

$\operatorname{kmax}\{ S \} = \sum_{|T| \ge k,\ T \subseteq S} (-1) ^ {|T| - k} \binom{|T| - 1}{k - 1} \min\{T\}$

同时由期望的线性性可以得到

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

一个常见的问题为, 询问一个集合中所有元素都出现的期望时间. 此时就可以套用该公式, 从而转为计算子集中元素第一次出现的期望时间.