容斥原理复习笔记

venn图正确性证明

我们要证的是每个被覆盖过的点最后的贡献都是$1$

考虑一个点,如果它被覆盖过$n$次,那么被一个圆覆盖的贡献是$C_{n}^1 1$,被两个圆覆盖的贡献是$C_{n}^2 (-1)$, $\dots$

我们实际上要证明对于任意的$n$

$\sum_{i=1}^n (-1)^{i-1} C_{n}^i = 1$

反演

反演的本质

考虑两个函数$f(i), g(i)$,若有$f(i) = \sum_{i=1}^n a[n][i] g(i)$,其中$a[n][i]$是我们已知的系数。

反演就是找到$b[n][i]$满足$g(i) = \sum_{i=1}^n b[n][i] f(i)$

记$\delta (x, y) = \begin{cases} 1 & i = j \\ 0 &Otherwise\end{cases}$

也就是说

同理可证

一些常见的反演

二项式反演

$f(n) = \sum_{i=1}^n {n \choose i} f(n)$

$g(n) = \sum_{i=1}^n (-1)^i {n \choose i} f(i)$

根据上面反演公式的推导,我们只需要证明

这里只给出第一个的推导过程,第二个同理

用到的引理

  1. ${n \choose i} = {n \choose n - i}$
  2. $\sum_{i=0}^n (-1)^i {n \choose i} = 0$这可证明可以沿用之前=1的思路

斯特灵反演

我们只需要证

这里只给出一种构造出来的证明思路,但是我不会证明这种构造的唯一性qwq

首先有

  • $x^{\underline{n}} = (-1)^n (-x)^{\overline{n}}$
  • $x^{\overline{n}} = (-1)^n (-x)^{\underline{n}}$

那么有

莫比乌斯反演

参考资料

fastle大佬的博客


一只菜鸡