二项式反演
常用结论
\[g_n=\sum_{i=0}^n(-1)^i\binom ni f_i\Leftrightarrow f_n=\sum_{i=0}^n(-1)^i\binom ni g_i\\ g_n=\sum_{i=0}^n\binom ni f_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}\binom ni f_i \]反演
对于一个数列 \(f\),若有另一个数列 \(g\) 满足
\[g_n=\sum_{i=0}^{n}a_if_i \]反演即是求出
\[f_n=\sum_{i=0}^nb_ig_i \]证明
应用
可以应用于至少、至多和恰好选择方案数之间的转化。