二项式反演口胡
由于 wtcl ，所以讲得很基础
反演是什么
假设我们已经知道了 \(g(n)=\sum_{i=0}^n a_{ni}f(j)\) 中的 \(a\) 这个系数数组
我们想要推求的是某一个 \(b\) 数组，满足 \(f(n)=\sum_{i=0}^nb_{ni}g(i)\)
我们考虑 \(a,b\) 两个数组有什么关系，假装我们现在已经的确找到了这样一个 \(b\)
那么：
\[\begin{align} f(n)&=\sum_{i=0}^n b_{ni}\sum_{j=0}^ia_{ij}f(j)\\ &=\sum_{i=0}^n f(i)\sum_{j=i}^nb_{nj}a_{ji} \end{align} \]所以我们只要求 \(\sum_{j=i}^nb_{nj}a_{ji}=[i=n]\) 即可，这里可以把 \(n,i\) 看成是一个常量
也就是说，只要我们找到了这种 \(b\) ，就完成了我们的二项式反演，可以从更直观的角度理解上面那个式子的变化
（上图是白嫖的老师课件里老师白嫖的不知道哪位大佬的图）
二项式反演
基础式
\[g(n)=\sum_{i=0}^n(-1)^i\binom nif(i) \Leftrightarrow f(n)=\sum_{i=0}^n(-1)^i\binom ni g(i) \]我们现在的任务是证明 \(\sum_{i=j}^n(-1)^{i+j}\binom ni\binom ij=[j=n]\)
首先得知道这个东西：
\[\binom ni\binom ij =\binom nj\binom{n-j}{i-j} \]一种方式是直接按照组合数定义展开证明，
另一种是组合数的意义：左式是 \(n\) 选 \(i\) ，\(i\) 选 \(j\) ，那我不妨直接 \(n\) 选 \(j\) ，然后从剩下的 \(n-j\) 个数中不足没有选的 \(i-j\) 个
那么：
\[\begin{align} &\sum_{i=j}^n(-1)^{i+j}\binom ni\binom ij\\ =&\sum_{i=j}^n(-1)^{i+j}\binom nj\binom {n-j}{i-j}\\ =&(-1)^j\binom nj\sum_{i=j}^n (-1)^i \binom{n-j}{i-j}\\ =&(-1)^j\binom nj\sum_{i=0}^{n-j}(-1)^{i+j}\binom{n-j}{i}\\ =&(-1)^{2j}\binom nj\sum_{i=0}^{n-j}(-1)^i\binom{n-j}{i}\\ \end{align} \]这个时候我们直接二项式定理，\((x+y)^n\sum_{i=0}^n \binom ni x^i y^{n-i}\) 那么
\[(-1)^{2j}\binom nj\sum_{i=0}^{n-j}(-1)^i\binom{n-j}{i}=(-1)^{2j}\binom nj\ 0^{n-j} \]再这里我们令 \(0^0=1\) ，那么原式显然当且仅当 \(j=n\) 时为 \(1\)
由于很难找到这种含 \((-1)^i\) 的容斥系数，所以这个基本式作用不大
变式1
\[g(n)=\sum_{i=0}^n\binom ni f(i)\Leftrightarrow f(n)=\sum_{i=0}^n(-1)^{n-i}\binom ni g(i) \]很容易证明它，我们的基本式叫做：\(g(n)=\sum_{i=0}^n(-1)^i\binom nif(i) \Leftrightarrow f(n)=\sum_{i=0}^n(-1)^i\binom ni g(i)\)
那么，我们令 \(h(x)=(-1)^xf(x)\) ，那么，利用基本式，
\[g(n)=\sum_{i=0}^n\binom ni h(x)\Rightarrow \frac {h(n)}{(-1)^n}=\sum_{i=0}(-1)^i\binom ni g(i)\Rightarrow f(n)=\sum_{i=0}^n(-1)^{n-i}\binom ni g(i) \]这里给出一个小应用：
题意：错排问题 ，有多少种排列方式，使得 $ p_i \neq ??$
解题：虽然我们可以直接套错排公式，这里还是介绍一下二项式反演怎么做
定义 \(??(i)\) 表示恰好有 \(??\) 个错开，\(??(i)\) 表示至多有 \(??\) 个元素错开
那么有： $ ??(i) = ??!$ , \(??(i) = \sum_{j=0}(-1)^{i-j}\binom ij f(j)\)
反演一下：\(f(n)=\sum_{i=0}^n(-1)^{n-i}\binom ni g(i)\)
变式2
\[g(n)=\sum_{i=n}^m\binom in f(i)\Leftrightarrow f(n)=\sum_{i=n}^m(-1)^{i-n}\binom in g(i) \]证明略去