二项式反演

二项式反演的基本形式

证明

将$f(n) = \sum{i = 0}^{n}{g(i)C_n^i}$代入$g(n) = \sum{i = 0}^n{(-1)^{n-i}C_n^if(i)}$中的$f(i)$可以得到

考虑枚举$g(j)$的系数 于是有

将$Cn^i$和$C_i^j$和并得到 $C_n^jC{n - j}^{i - j}$ 即

由二项式定理得到

发现只有当$n - j = 0$有值 得到

所以这个是正确的。

意义上

若现在有 ${% raw %} g(n)= \sum_{i = 0}^n{a_{ni}f(i)} {% endraw %}$和${% raw %}f(n)=\sum_{i = 0}^n{b_{ni}g(i)}{% endraw %}**$ 将第一个式子强行带入第二个式子 可以得到

假设现在有 ${% raw %}\delta_{ij} = [i == j]{% endraw %}$ 明显反演式成立的条件是${% raw %}\sum_{j = i}^n{b_{nj}}{a_{ij}} = \delta_{ij} {% endraw %}$

也就是说如果能找出这么一个关系 就可以直接反演。