二项式反演

二项式反演

常用结论

[g_n=sum_{i=0}^n(-1)^iinom ni f_iLeftrightarrow f_n=sum_{i=0}^n(-1)^iinom ni g_i\ g_n=sum_{i=0}^ninom ni f_iLeftrightarrow g_n=sum_{i=0}^n(-1)^{n-i}inom ni f_i ]

反演

对于一个数列 (f)，若有另一个数列 (g) 满足

[g_n=sum_{i=0}^{n}a_if_i ]

反演即是求出

[f_n=sum_{i=0}^nb_ig_i ]

证明

引用

应用

可以应用于至少、至多和恰好选择方案数之间的转化。