二项式反演

反演就是对于两个整数函数 \(f\) 和 \(g\)，从用 \(g\) 表示 \(f\) 转化为用 \(f\) 表示 \(g\)。

简而言之，\(f(n)\) 是 \(g(0),g(1),\cdots,g(n)\) 的一个线性组合，那么很明显，有 \(f(n)=\sum_{i=0}^na_{n,i}g(i)\)。

如果把 \(g(i),f(i)\) 用向量 \(G,F\) 表示，那么 \(F=\{a_{i,j}\}*G\)

而反演的实质就是想要找到一个下三角矩阵 \(B=\{b_{i,j}\}\) 满足 \(G=\{b_{i,j}\}*F\)，也就是 \(g(n)=\sum_{i=0}^nb_{n,i}f(i)\)

记 \(A=\{a_{i,j}\}\)，那么有 \(F=AG,G=BF\)，提一下，\(F=A(BF)\)，\(F=(AB)F\)，所以 \(AB=E\)，所以 \(B=A^{-1}\)。

所以实际上我们就是要找到 \(A\) 的逆矩阵。

求取这个逆矩阵其实很简单，我们只需要在想要的 \(a_{i,j}\) 下，把特殊的 \(f(n)\) 和 \(g(n)\) 带入进去，得到 \(b_{i,j}\) 就可以得到对普适的 \(f(n),g(n)\) 的结论。

例如，二项式反演，\(f(n)=\sum_{i=0}^n\binom{n}{i}g(i)\)，那么我们令 \(g(i)=(x-1)^i\)，那么根据二项式定理，\(f(n)=x^n\)，接下来，\((x-1)^n=\sum_{i=0}^n b_{n,i}x^i\)，很明显，因为 \((x-1)^n=\sum_{i=0}^n (-1)^{n-i}\binom{n}{i}x^i\)，所以 \(b_{n,i}=(-1)^{n-i}\binom{n}{i}\)。

我们就得到了 \(g(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)\)。