二项式反演证明&各种反演

二项式反演

二项式反演：

$$g(n)=\sum_{i=0}^n{(-1)^iC_n^if(i)}\Leftrightarrow f(n)=\sum_{i=0}^n{(-1)^iC_n^ig(i)}$$

恒等变换后，是更为常用的形式：

$$g(n)=\sum_{i=0}^{n}{C_n^if(i)}\Leftrightarrow f(n)=\sum_{i=0}^n{(-1)^{n-i}C^i_ng(i)}$$

证明

用 $a_i$ 代替

$$g(n)=\sum_{i=0}^n{(-1)^iC_n^if(i)}$$

中每一项的系数 $(-1)^iC^i_n$：

$$g(n)=\sum_{i=0}^{n}{a_if(i)}$$

此时 $a_i=(-1)^iC_n^i$。

同样用 $b_i$ 代替 $f(n)$ 每一项的系数：

$$f(n)=\sum_{i=0}^n{b_ig(i)}$$

如果

$$g(n)=\sum_{i=0}^n{a_if(i)}\Rightarrow f(n)=\sum_{i=0}^n{b_ig(i)}$$

，需要推出的条件：

$$f(n)=\sum_{i=0}^N{b_ig(i)}=\sum_{i=0}^n{b_i\sum_{j=0}^i{a_{ij}f(j)}}=\sum_{j=0}^n{f(j)\sum_{i=j}^n{b_ia_{ij}}}$$

如果式子成立，我们需要证明的就是：

$$\sum_{i=j}^n{b_ia_{ij}}=[j=n]$$ $$\sum_{i=j}^N{(-1)^iC_n^i}\times (-1)^jC_i^j=[j=n]$$

• $$C_n^iC_i^j=\frac{n!}{(n-i)!i!}\times \frac{i!}{(i-j)!j!}=\frac{n!}{(n-i)!(i-j)!j!}$$

$$=\frac{n!}{(n-j)!j!}\times\frac{(n-j)!}{(i-j)!(n-i)!}$$ $$=\frac{n!}{(n-j)!j!}\times\frac{(n-j)!}{((n-j)-(n-i))!(n-i)!}$$ $$=C_n^jC_{n-j}^{n-i}$$ $$C_n^iC_i^j=C_n^jC_{n-j}^{n-i}$$

带入这个结果：

$$=\sum_{i=j}^n{(-1)^i(-1)^jC_n^jC_{n-j}^{n-i}}$$ $$=C_n^j(-1)^j\sum_{i=0}^{n-j}{(-1)^{i+j}C_{n-j}^i}=C_n^j(1-1)^{n-j}$$

如果 $j\not=n$，那么结果为 $0$。

而如果 $j=k$，带入原式结果为 $=[j=n]$。

所以：

$$g(n)=\sum_{i=0}^n{(-1)^iC_n^if(i)}\Leftrightarrow f(n)=\sum_{i=0}^n{(-1)^iC_n^ig(i)}$$

同样，恒等变换完的：

$$g(n)=\sum_{i=0}^{n}{C_n^if(i)}\Leftrightarrow f(n)=\sum_{i=0}^n{(-1)^{n-i}C^i_ng(i)}$$

也成立。

一般形式

$$g(n)=\sum_{i=0}^n{(-1)^iC_n^if(i)}\Leftrightarrow f(n)=\sum_{i=0}^n{(-1)^iC_n^ig(i)}$$ $$g(n)=\sum_{i=j}^n{(-1)^iC_i^jf(i)}\Leftrightarrow f(n)=\sum_{i=j}^n{(-1)^iC_i^jg(i)}$$ $$g(n)=\sum_{i=0}^{n}{C_n^if(i)}\Leftrightarrow f(n)=\sum_{i=0}^n{(-1)^{n-i}C^i_ng(i)}$$ $$g(n)=\sum_{i=j}^{n}{C_i^jf(i)}\Leftrightarrow f(n)=\sum_{i=j}^n{(-1)^{i-j}C^j_ig(i)}$$

各种反演

• 序列

$$F_n=\sum_{i=0}^n{a_{ni}f_i}$$

有

$$f_n=\sum_{i=0}^n{b_{ni}F_i}$$

充要条件是：

$$\sum_{j=i}^n{b_{nj}a_{ji}}=\delta_{n_i}$$

• 斯特林数反演

$$a_{ni}=\big\{_i^n \big\},b_{ni}=(-1)^{n-i}\big[_i^n\big]$$

$a$ 是第二类斯特林数，$b$ 是第一类斯特林数。

$$F_n=\sum_{i=0}^n{\big\{_i^n \big\}f_i}$$ $$f_n=\sum_{i=0}^n{(-1)^{n-i}\big[_i^n\big]F_i}$$

• 莫比乌斯反演

$$a_{ni}=[i\mid n],b_{ni}=[i\mid n]\mu{(\frac{n}{i})}$$ $$F_n=\sum_{d\mid n}{f_d}$$ $$f_n=\sum_{d\mid n}{\mu{(\frac{n}{d})}F_d}$$

• 伯努利数反演

$$a_{ni}=\frac{1}{n-i+1}C_n^i,b_{ni}=C_n^iB_{n-i}$$ $$F_n=\sum_{i=0}^n{\frac{1}{n-i+1}C_n^if_i}$$ $$f_n=\sum_{i=0}^n{C_n^iB_{n-i}F_i}$$

$B_i$ 是伯努利数。

• 拉氏反演（拉赫数，也叫第三类斯特林数）

$$a_{ni}=b_{ni}=L(n,i)=(-1)^n\frac{n!}{i!}C_{n-1}^{i-1}$$ $$F_n=\sum_{i=0}^n{L(n,i)f_i}$$ $$f_n=\sum_{i=0}^n{L(n,i)F_i}$$

$L(n,i)$ 是 $Lah$ 数。

• 最值反演（$min-max$ 容斥）

$$f(S)=\min S,g(S)=(-1)^{|S|-1}\max S$$ $$\max S=\sum_{T\subseteq S}{(-1)^{|T|-1}}\min T$$

推广：

$$k_{th}\max S=\sum_{T\subseteq S}{(-1)^{|T|-k}C_{|T|-1}^{k-1}\min T}$$

$S,T$ 是集合。

• 单位根反演

$$\sum_{i=0}^{\infty}{[x^{ik}]f(x)=\frac{1}{k}\sum_{j=0}^{k-1}{f(w^j_k)}}$$

$w_k=e^{\frac{2\pi i}{k}}$ 就是单位根。

• 拉格朗日反演

$$F(G(x))=x$$ $$[x^i]F(x)=\frac{1}{i}[x^{i-1}](\frac{x}{G(x)})^i$$