对于序列 \(\{f_n\}\) 和 \(\{g_n\}\)，通过 \(f\) 计算出 \(g\) 叫做正演，通过 \(g\) 计算出 \(f\) 叫做反演。
形式
二项式反演讲的是：
\[g_n=\sum_{i=0}^n\binom{n}{i}f_i \Leftrightarrow f_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g_i
\]
证明
将组合数展开得到：
\[\begin{aligned}
&g_n=\sum_{i=0}^n\binom{n}{i}f_i \&\Leftrightarrow g_n=\sum_{i=0}^n \frac{n!}{i!(n-i)!}f_i \&\Leftrightarrow \frac{g_n}{n!} = \sum_{i=0}^n \frac{1}{(n-i)!}\frac{f_i}{i!}
\end{aligned}
\]
考虑序列 \(\{f_n\}\)，\(\{g_n\}\) 的指数生成函数 \(F(x),G(x)\)。上式是一个卷积的形式，写成指数生成函数就是 \(G(x)=e^xF(x) \Rightarrow F(x)=\frac{1}{e^x}G(x)\)。
将 \(e^{-x}\) 在 \(x=0\) 处泰勒展开得到 \(e^{-x} = \sum_{i=0}^n (-1)^i \dfrac{x^i}{i!}\)，和 \(G(x)\) 卷起来得到
\[\begin{aligned}
&F(x)=\sum_{k=0}^n\sum_{i=0}^k(-1)^{k-i}\frac{1}{(k-i)!}\frac{g_i}{i!}x^k \&\Rightarrow \frac{f_n}{n!}=\sum_{i=0}^n(-1)^{n-i}\frac{1}{(n-i)!}\frac{g_i}{i!} \&\Rightarrow f_n=\sum_{i=0}^n(-1)^{n-i} \frac{n!}{i!(n-i)!}g_i=\sum_{i=0}^n(-1)^{n-i} \binom{n}{i} g_i
\end{aligned}
\]
证毕。
应用
咕