当前位置：网站首页>组合数学——二项式反演

组合数学——二项式反演

2022-08-06 23:43:00 【爱寂寞的时光】

在处理组合数的时候，我们经常能够遇到形如：

$\sum_{i=0}^n \binom{n}{i} g(i)$

我们想反过来求 $g (n)$ 考虑 $f$ 的 EGF 为 $F (x)$ 而 $g$ 的 EGF 为 $G (x)$ 。并且 $\sum_{n \ge 0} \frac{x^n}{n!} = e^x$ 那么：

$F(x) = C(x)G(x) = e^xG(x)$

那么 $G(x) = F(x) e^{-x}$ ，再次展开得到：

$\sum_{i = 0}^n \binom{n}{i} (-1)^{n-i}f(i)$

上述过程为二项式反演。

我们对于固定的 $n$ ，求出 $S (n, m)$ 。

考虑引理：

$m^n=\displaystyle \sum _{i=0}^{m} \begin{Bmatrix}n\\i\end{Bmatrix} \times i! \times \begin{pmatrix}m\\i\end{pmatrix}$

左边是把 $n$ 个物品随机放入 $m$ 个箱子中，右边 $i$ 是枚举非空箱子的个数，我们将 $n$ 个物品分成 $i$ 个集合塞到 $i$ 个非空的箱子中。

$m^n + 1=\displaystyle \sum _{i=0}^{m} \begin{Bmatrix}n\\i\end{Bmatrix} \times i! \times \begin{pmatrix}m\\i\end{pmatrix}$

经过二项式反演可得：

$\begin{Bmatrix}n\\m\end{Bmatrix} m!=\sum\limits _{i=0}^{m}(-1)^{m-i}\begin{pmatrix}m\\i\end{pmatrix}i^n$

化简可得：

$\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits _{i=0}^{m}\frac{(-1)^{m-i}}{(m-i)!}\times \frac{i^n}{i!}$

直接使用 NTT 卷积可做。

版权声明
本文为[爱寂寞的时光]所创，转载请带上原文链接，感谢
https://blog.csdn.net/jiahonghao2002/article/details/126173954