二项式反演

$g(n) =\sum_{i=1}^n{n\choose i}f(i) \Longleftrightarrow f(n)=\sum_{i=1}^n (-1)^{n-i}{n \choose i}g(i)$

先把左边代入右边消掉

$f(n)=\sum_{i=1}^{n}(-1)^{n-i}{n\choose i}*\sum_{j=1}^{i}{i\choose j}f(j)$

换一下式子的顺序

$f(n)=\sum_{j=1}^{n}f(j)*\sum_{i=j}^{n}(-1)^{n-i}{n\choose i}{i\choose j}$

拆开组合数并化简

$\sum_{i=j}^{n}(-1)^{n-i}\cfrac{n!}{i!(n-i)!}\cfrac{i!}{j!(i-j)!}$

$=\sum_{i=j}^{n}(-1)^{n-i}\cfrac{n!}{j!(n-i)!(i-j)!}$

$=\cfrac{n!}{j!}\sum_{i=j}^{n}\cfrac{(-1)^{n-i}}{(n-i)!(i-j)!}$

内乘外除$(n-j)!$

$=\cfrac{n!}{j!(n-j)!}\sum_{i=j}^{n}(-1)^{n-i}\cfrac{(n-j)!}{(n-i)!(i-j)!}$

把分数转回组合数

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

因为

$f(n)=\sum_{j=1}^{n}[j==n]*f(j)$

所以就相当于证明：

${n\choose j}\sum_{i=j}^{n}(-1)^{n-i}{n-j\choose n-i}=\begin{cases} 0\quad(j<n)\\ 1\quad(j=n) \\ \end{cases}$

证明：

• $j=n$ 时：

  原式等于：

${n\choose n}(-1)^0{0\choose0}=1$

• $j\not = n$ 时：

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

  证明：

  当 $n-j$ 为奇数时，

  取值正好有 $n-j+1$ 个，且正好两两相反可以抵消，也就是 ${n-j\choose n-i}$ 和 ${n-j\choose n-j-(n-i)}$，他们值相等，但系数相反；

  当 $n-j$ 为偶数时，

  根据二项式定理：

$\sum_{i=0}^n C(n,i) (-1)^{n-i}$

$= \sum_{i=0}^n C(n,i) (-1)^{n-i}1^i$

$=(1-1)^n$

$=0^n$

$=0$

反演得证