二项式反演公式及其应用

上一篇博文中,介绍过数论中的 Mobius 反演公式,让我想起了另一个经典的反演公式: 二项式反演公式。本质上反演公式就是矩阵求逆的过程。

只是它的逆有很简单的形式,因此才有了二项式反演公式,这个公式帮助我们队伍在2014年ACM-ICPC亚洲区域赛西安站拿银,当时F题答案直接算需要$n^3$复杂度,而利用二项式反演公式后,可以在$n^2$复杂度内完美解决。1A过题,感觉超爽。

最后简单提一下:Mobius反演公式及其矩阵形式

反演公式与其矩阵形式

其中$g(n)$已知,解出$f(n)$

为其反演公式,也称上面两式互为反演公式。

则上述反演公式本质上就是求矩阵$A$的逆$B$.

二项式反演公式

其中 $s \geq 0$ 则

Proof: 要证明反演公式,只需证明,对应的矩阵 $A$ 和 $B$ 互为逆即可. 令 $C = A \star B$ 则

证毕。

二项式反演公式的应用

二项式反演公式在组合数学和数论中都有诸多应用,这里简单的提两个。

(错排问题) 在 $n$ 个数字 $1,2,\dots,n$ 形成 $n!$ 个排列 $a_1a_2 \dots a_n$ 中满足 $a_i \neq i$ 的排列有多少个?

不妨设答案为$D_n$ ,则可以看出恰好有 $r$ 个 $a_i=i$的排列数为$ \left(\begin{matrix} n \\ r\end{matrix}\right) D_{n-r}$ ,因此

因此

当然 $D_n$ 还有递推关系式 $D_1=0,D_2 = 1$

(满射个数) 求$m$元集$A$到$n$元集$B$的满身的个数$g(m,n)$

类似于错排的思路,我们有

于是

Mobius反演公式及其矩阵形式

由 Mobius 反演公式对应的矩阵我们有,若

则,其逆矩阵为

本文参考了豆瓣百度文库以及 许胤龙,孙淑玲《组合数学引论》。

单位根反演

DFT的本质就是单位根反演

一个应用的例子

单位根反演转自:https://www.cnblogs.com/cjyyb/p/10838495.html

具体的例子求:$\sum_{i \in [0,n],k \mid i} \binom{n}{i}G^i$

计$f(x) = (G+x)^n$,则由上面公式

即复杂度$O(k \log n)$,如果要结果模一个NFT friendly的,那就更好了!

如有帮助,烦请资瓷(一块也是爱0.0)