本文主要是介绍二项式反演入门，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

对于序列 \(\{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} \]

证毕。

应用

咕

这篇关于二项式反演入门的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！