二项式反演

会证二项式反演啦！

其实推式子还是很好玩的，对吧。

先来说一下二项式反演的内容：

设你有两个数列 $f$ 和 $g$ ，满足：

g_{i} = \sum_{j = 1}^{i} (\binom{i}{j}) f_{j}

那么一定有：

f_{i} = \sum_{j = 1}^{i} (- 1)^{i - j} (\binom{i}{j}) g_{j}

其实二项式反演还有另一种形式，只不过最常用的是上面那种，在这里也写出来：

如果有：

g_{i} = \sum_{j = 1}^{i} (- 1)^{j} (\binom{i}{j}) f_{j}

那么：

f_{i} = \sum_{j = 1}^{i} (- 1)^{j} (\binom{i}{j}) g_{j}

下面来证明一下第一种形式。

把第一个式子代入第二个可以知道：

f_{i} = \sum_{j = 1}^{i} (- 1)^{i - j} (\binom{i}{j}) \sum_{k = 1}^{j} (\binom{j}{k}) f_{k}

整理一下， $f_{k}$ 的系数就是：

\sum_{j = k}^{i} (- 1)^{i - j} (\binom{i}{j}) (\binom{j}{k})

我们只要证明上面的式子等价于 $[i == k]$ 即可，把二项式系数拆成阶乘的形式：

\sum_{j = k}^{i} (- 1)^{i - j} \frac{i!}{j! (i - j)!} * \frac{j!}{k! (j - k)!}

消掉 $j!$ ，再把 $i!$ 和 $k!$ 提出来：

(\sum_{j = k}^{i} (- 1)^{i - j} \frac{1}{(i - j)! (j - k)!}) * \frac{i!}{k!}

再在前面乘以 $(i - k)!$ ，后面除以 $(i - k)!$ ：

(\sum_{j - k}^{i} (- 1)^{i - j} \frac{(i - k)!}{(i - j)! (j - k)!}) * \frac{i!}{k! (i - k)!}

就等于：

(\sum_{j = k}^{i} (- 1)^{i - j} (\binom{i - k}{j - k})) * (\binom{i}{k})

不难发现前面那一项就是 $i - k$ 的二项式系数错位相减，这是等于 $[i - k = 0]$ 的，也就是在 $i! = k$ 时，前一项永远为 $0$ 。而 $i == k$ 时，前后两项都为 $1$ ，因此得证。

$n o t e$ ：有些题目的式子推出来是下标从 $0$ 开始的，也可以用二项式反演。因为证明过程并没有用到那个 $1$ 。

然后就可以用二项式反演来套路题目了，一般就是你要求 $f$ ，已经知道一个好求的 $g$ 满足 $g_{i} = \sum_{j = 1}^{i} (\binom{i}{j}) f_{j}$ ，然后就只要二项式反演一下就好了。