反演的容斥证法

一堆非常 trivial 的东西，用来备忘。

莫比乌斯反演

$$g(n)=\sum_{d|n} f(d)$$

现在已知 $g$，要求 $f$。

那么有如下推导：

$$ \begin{aligned} f(n)&=\sum_{d|n} f(d)[d=n] \\ &=\sum_{d|n} f(d)[\frac{n}{d}=1] \\ &=\sum_{d|n} f(d)[\forall p_i, p_i \nmid \frac{n}{d}] \\ \end{aligned} $$

考虑对最后一个柿子容斥。

记 $S, T$ 为由 $n$ 的本质不同素因子构成的集合，$\text{val}(S)$ 表示 $\prod_{d\in S} d$。

$$ \begin{aligned} f(n) &= \sum_{S} (-1)^{|S|} \sum_{T\supset S} f(\frac{n}{\text{val}(T)}) \\ &= \sum_{S} (-1)^{|S|} g(\frac{n}{\text{val}(S)}) \\ &= \sum_{d|n} \mu(d) g(\frac{n}{d}) \end{aligned} $$

发现 $\mu$ 实质上起到了控制容斥系数的作用。

二项式反演

$$g(n)=\sum_{i=0}^n \binom{n}{i} f(i)$$

现在已知 $g$，要求 $f$。

那么：

$$ \begin{aligned} f(n)&=\sum_{i=0}^n \binom{n}{i} f(i) [i=n] \\ &= \sum_{i=0}^{n} \binom{n}{i} f(i) \cdot 0 ^{n-i} \end{aligned} $$

（此处我们认为 $0^{0} = 1$）

考虑如何用容斥原理刻画这个 $0^{n-i}$：相当于总共 $n-i$ 个位置，每个位置既不能选，也不能不选。即：

$$ 0^{n-i}=\sum_{j=0}^{n-i} \binom{n-i}{j}(-1)^{j}=\sum_{j=0}^{n-i} \binom{n-i}{j}(-1)^{n-i-j} $$

也就是任取一个位置集合 $S$，他都是非法的！

那么就有：

$$ \begin{aligned} f(n)&=\sum_{i=0}^{n} \binom{n}{i} f(i) \sum_{j=0}^{n-i} \binom{n-i}{j}(-1)^{n-i-j} \\ &=\sum_{i=0}^{n} \binom{n}{i} f(i) \sum_{j=i}^{n} \binom{n-i}{j-i}(-1)^{n-j} \\ &=\sum_{j=0}^{n}\sum_{i=0}^{j}\binom{n}{i}\binom{n-i}{j-i}f(i)(-1)^{n-j} \\ &=\sum_{j=0}^{n}\sum_{i=0}^{j}\binom{n}{j}\binom{j}{i}f(i)(-1)^{n-j} \ \ \text{\red{(组合意义)}} \\ &=\sum_{j=0}^n \binom{n}{j} (-1)^{n-j} \sum_{i=0}^{j} \binom{j}{i} f(i) \\ &=\sum_{j=0}^n \binom{n}{j} (-1)^{n-j} g(j) \\ &=\sum_{i=0}^n \binom{n}{i} (-1)^{n-i} g(i) \end{aligned} $$