首页 📚学习笔记

二项式定理

$(a+b)^n=\sum_{i=0}^{n}C_n^i·a^i·b^{n-i}$


二项式反演

$$ \begin{align} f_n=\sum_{i=0}^n (-1)^iC_n^ig_i\quad ⟺\quad g_n=\sum_{i=0}^n (-1)^iC_n^if_i \end{align} $$

但常用的是

$$ \begin{align} f_n=\sum_{i=0}^n\binom{n}{i}g_i\quad ⟺\quad g_n=\sum_{i=0}^n (-1)^{n-i}\binom{n}{i}f_i\\ f_n=\sum_{i=n}^m\binom{i}{n}g_i\quad ⟺\quad g_n=\sum_{i=n}^m (-1)^{i-n}\binom{i}{n}f_i \end{align} $$


证明

$$ \begin{align} \sum_{i=0}^n (-1)^{n-i}\binom{n}{i}f_i&=\sum_{i=0}^n (-1)^{n-i}C_n^i\sum_{j=0}^i\binom{i}{j}g_j\\ &=\sum_{i=0}^n \sum_{j=0}^i(-1)^{n-i}\binom{n}{i}\binom{i}{j}g_j \end{align} $$

因为

$$ \begin{align} \binom{n}{i}\binom{i}{j}&=\frac{n!}{i!(n-i)!}\times\frac{i!}{j!(i-j)!}\\ &=\frac{n!}{j!(n-j)!}\times\frac{(n-j)!}{(n-i)!(i-j)!}\\ &=\binom{n}{j}\binom{n-j}{n-i} \end{align} $$

$$ \begin{align} \sum_{i=0}^n (-1)^{n-i}\binom{n}{i}f_i&=\sum_{i=0}^n \sum_{j=0}^i(-1)^{n-i}\binom{n}{i}\binom{i}{j}g_j\quad\\ &=\sum_{i=0}^n \sum_{j=0}^i(-1)^{n-i}\binom{n}{j}\binom{n-j}{n-i}g_j\\ &=\sum_{j=0}^n \sum_{i=j}^n(-1)^{n-i}\binom{n}{j}\binom{n-j}{n-i}g_j\\ &=\sum_{j=0}^n \binom{n}{j}g_j\sum_{i=j}^n(-1)^{n-i}\binom{n-j}{n-i}\\ \end{align} $$

看看后面那个我们我们用$k$代替$n-i$, $m$代替$n-j$

$$ \begin{align} \sum_{i=j}^n(-1)^{n-i}\binom{n-j}{n-i}&=\sum_{k=0}^{n-j}(-1)^{k}\binom{n-j}{k}\\ &=\sum_{k=0}^{m}(-1)^{k}\binom{m}{k}(1)^{m-k}\\ &=\sum_{k=0}^{m}\binom{m}{k}(-1)^{k}(1)^{m-k}\\ &=(1-1)^m \end{align} $$

所以只有当$m=n-j=0$时为$1$,其余时候为$0$

所以$j=n$

$$ \begin{align} \sum_{i=0}^n (-1)^{n-i}\binom{n}{i}f_i&=\sum_{j=0}^n \binom{n}{j}g_j\sum_{i=j}^n(-1)^{n-i}\binom{n-j}{n-i}\\ &= \binom{n}{n}g_n(-1)^0\binom{0}{0}\\ &=g_n \end{align} $$

证毕.


如何应用

我们一般会设$g(i)$为至多有$i$个满足条件,$f(i)$为恰好有$i$个满足条件

一般$f$就是我们最终要求得的答案

对于每一个$j<=i,f(j)$就会在$g(i)$里面算$C_j^i$次,可得

$$ \begin{align} g(n)=\sum_{i=0}^{n}\binom{n}{i} f(i) \end{align} $$

二项式反演可得

$$ \begin{align} f(n)=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}g(i) \end{align} $$

至少的话用另一个即可




文章评论

目录