二项式反演
文章目录
主要形式
形式一
$$f(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}f(i)$$
形式二
$$f(n)=\sum\limits_{i=0}^n\dbinom{n}{i}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}f(i)$$
形式三
$$f(n)=\sum\limits_{i=n}^m(-1)^i\dbinom{i}{n}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=n}^m(-1)^{i}\dbinom{i}{n}f(i)$$
形式四
$$f(n)=\sum\limits_{i=n}^m\dbinom{i}{n}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=n}^m(-1)^{i-n}\dbinom{i}{n}f(i)$$
证明
反演基本形式如下
$$f(n) = \sum\limits_{i=0}^n{a_i}g(i)$$
$$g(n) = \sum\limits_{i=0}^n{b_i}f(i)$$
在形式一中,有 $a_i = b_i = (-1)^i\dbinom{n}{i}$
要证
$$f(n)=\sum\limits_{i=0}^na_ig(i)\Longrightarrow g(n)=\sum\limits_{i=0}^nb_if(i)$$
只要证
$$g(n)=\sum\limits_{i=0}^nb_if(i)=\sum\limits_{i=0}^nb_i\sum\limits_{j=0}^ia_jg(j) = \sum\limits_{j=0}^ng(j)\sum\limits_{i=j}^nb_ia_j$$
只要证
$$\sum\limits_{i=j}^nb_ia_j=[j=n]$$
只要证
$$\sum\limits_{i=j}^n(-1)^i\dbinom{n}{i}\times(-1)^j\dbinom{i}{j}=[j=n]$$
引理: $\dbinom{n}{i}\dbinom{i}{j}=\dbinom{n}{j}\dbinom{n-j}{n-i}$
证明: 考虑组合意义,$n$ 个数中选 $i$ 个数,再从中选 $j$ 个数的方案数。等价于 $n$ 个数中先选出 $j$ 个数,再从剩下 $n-j$ 个数中选出 $i-j$ 个数的方案数
$\dbinom{n}{i}\dbinom{i}{j}=\dbinom{n}{j}\dbinom{n-j}{i-j}=\dbinom{n}{j}\dbinom{n-j}{n-i}$
$$\begin{aligned}
&\sum\limits_{i=j}^n(-1)^i\dbinom{n}{i}\times(-1)^j\dbinom{i}{j}\\
=&\sum\limits_{i=j}^n(-1)^{i}(-1)^j\dbinom{n}{j}\dbinom{n-j}{n-i}\\
=&\dbinom{n}{j}(-1)^j\sum\limits_{i=0}^{n-j}{(-1)}^{i+j}\dbinom{n-j}{i}\\
=&\dbinom{n}{j}(1-1)^{n-j}\\
=&[j=n]
\end{aligned}
$$
反之亦然,二项式反演得证
(感觉还是 vfk 课件上的推导更加自然