【笔记】二项式反演

Author Avatar
Sakits 5月 06, 2018

介绍

形式一

公式

fn=i=0n(1)i(ni)gign=i=0n(1)i(ni)fif_n=\sum_{i=0}^n(-1)^i\binom{n}{i}g_i \Leftrightarrow g_n=\sum_{i=0}^n(-1)^i\binom{n}{i}f_i

证明

  见:http://blog.miskcoo.com/2015/12/inversion-magic-binomial-inversion

形式二

公式

fn=i=0n(ni)gign=i=0n(1)ni(ni)fif_n=\sum_{i=0}^n\binom{n}{i}g_i \Leftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f_i

证明

gn=i=0n(1)ni(ni)fi=i=0n(1)ni(ni)j=0i(ij)gi=j=0n(1)nii=jn(ni)(ij)gi=j=0n(1)nii=jn(nj)(njij)gi=j=0n(nj)i=jn(1)ni(njij)gi=j=0n(nj)i=0nj(1)i(1)nji(nji)gi=j=0n(nj)i=0nj(11)njgi=gn\begin{aligned} g_n&=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f_i\\ &=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}\sum_{j=0}^i\binom{i}{j}g_i\\ &=\sum_{j=0}^n(-1)^{n-i}\sum_{i=j}^n\binom{n}{i}\binom{i}{j}g_i\\ &=\sum_{j=0}^n(-1)^{n-i}\sum_{i=j}^n\binom{n}{j}\binom{n-j}{i-j}g_i\\ &=\sum_{j=0}^n\binom{n}{j}\sum_{i=j}^n(-1)^{n-i}\binom{n-j}{i-j}g_i\\ &=\sum_{j=0}^n\binom{n}{j}\sum_{i=0}^{n-j}(1)^{i}(-1)^{n-j-i}\binom{n-j}{i}g_i\\ &=\sum_{j=0}^n\binom{n}{j}\sum_{i=0}^{n-j}(1-1)^{n-j}g_i\\ &=g_n \end{aligned}

形式三

fk=i=kn(ik)gigk=i=kn(1)ik(ik)fif_k=\sum_{i=k}^n\binom{i}{k}g_i \Leftrightarrow g_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}f_i

证明

gn=i=kn(1)ik(ik)fi=i=kn(1)ik(ik)j=in(ji)gj=j=kni=kj(1)ik(ji)(ik)gj=j=kni=kj(1)ik(jk)(jkik)gj=j=kn(jk)i=kj(1)ik(jkik)gj=gn\begin{aligned} g_n&=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}f_i\\ &=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}\sum_{j=i}^n\binom{j}{i}g_j\\ &=\sum_{j=k}^n\sum_{i=k}^j(-1)^{i-k}\binom{j}{i}\binom{i}{k}g_j\\ &=\sum_{j=k}^n\sum_{i=k}^j(-1)^{i-k}\binom{j}{k}\binom{j-k}{i-k}g_j\\ &=\sum_{j=k}^n\binom{j}{k}\sum_{i=k}^j(-1)^{i-k}\binom{j-k}{i-k}g_j\\ &=g_n \end{aligned}

应用

1.错排公式

  令f(n)f(n)表示nn个数字任意放的方案数,易得f(n)=n!f(n)=n!
  令g(n)g(n)表示nn个数字都不放在自己位置上的方案数,可得:

f(n)=i=0n(ni)gif(n)=\sum_{i=0}^n\binom{n}{i}g_i

  二项式反演可得:

gn=i=0n(1)ni(ni)fi=i=0n(1)ni(ni)i!=i=0n(1)nin!(ni)!=n!i=0n(1)ii!\begin{aligned} g_n&=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f_i\\ &=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}i!\\ &=\sum_{i=0}^n(-1)^{n-i}\frac{n!}{(n-i)!}\\ &=n!\sum_{i=0}^n\frac{(-1)^i}{i!} \end{aligned}