二项式反演公式及其应用

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

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

最后简单提一下：Möbius 反演公式及其矩阵形式

反演公式与其矩阵形式

由

$$\sum_{r = 1} ^n a_{n,r} f(r) = g(n)$$

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

$$f(n) = \sum_{r = 1} ^n b_{n,r} g(r)$$

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

令

$$A = \left( \begin{matrix} a_{11} & & \\ a_{21} & a_{22} & \\ \cdots & \cdots & \ddots & \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{matrix} \right) ,\qquad B = \left( \begin{matrix} b_{11} & & \\ b_{21} & b_{22} & \\ \cdots & \cdots & \ddots & \\ b_{n1} & b_{n2} & \cdots & b_{nn} \\ \end{matrix} \right)$$

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

二项式反演公式

若

$$g(n) = \sum_{r = s} ^n {n \choose r} f(r)$$

其中 $s \geq 0$ 则

$$f(n) = \sum_{r = s} ^n (-1)^{n-r} {n \choose r} g(r)$$

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

$$\begin{aligned} c_{ij} = \sum_{k=1} ^n a_{ik} b_{kj} & = \sum_{k =j} ^ i {i \choose k} (-1)^{k-j}{k \choose j} = \sum_{k=0} ^ {i-j} {i \choose k + j} (-1)^k {k + j \choose j} \\ & = {i \choose j} \sum_{k=0} ^ {i-j} (-1)^k {i - j \choose k} = \left\{ \begin{array}{ll} 1,& i=j \\ 0,& i>j \end{array} \right. \end{aligned}$$

证毕。

二项式反演写成卷积形式便于 NTT

不妨取 $s = 0$

$$\frac{g(n)}{n!} = \sum_{i + j = n} \frac{f(i)}{i} \cdot \frac{1}{j!}$$

等价于

$$\frac{f(n)}{n!} = \sum_{i + j = n} ^n \frac{g(i)}{i!} \cdot \frac{(-1)^{j}}{j!}$$

也就是说二项式反演公式本质上是说：$\frac{1}{n!}$ 和 $\frac{(-1)^n}{n!}$ 互为卷积逆。

二项式反演公式的应用

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

(错排问题) 在 $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}$，因此

$$n! = \sum_{r = 0} ^n \left(\begin{matrix} n \\ r\end{matrix}\right) D_{n-r}$$

因此

$$D_n ＝ \sum_{r = 0} ^n (-1)^{n-r} \left(\begin{matrix} n \\ r\end{matrix}\right) r! = n! \sum_{r=0} ^n \frac{(-1)^r}{r!}$$

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

$$D_n = (n-1) (D_{n-1} + D_{n-2}),\quad n \geq 2$$

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

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

$$n^m = \sum_{r = 1} ^n \left(\begin{matrix} n \\ r\end{matrix}\right) g(m,r)$$

于是

$$g(m,n) = \sum_{r = 1} ^n (-1)^{n-r} \left(\begin{matrix} n \\ r\end{matrix}\right) r^m$$

Möbius 反演公式及其矩阵形式

由 Möbius 反演公式对应的矩阵我们有,若

$$a_{ij} = \left\{ \begin{array}{cc} 1, & j \mid i \\ 0, & else. \end{array} \right.$$

则，其逆矩阵为

$$b_{ij} = \left\{ \begin{array}{cc} \mu (\frac{i}{j}), & j \mid i \\ 0, & else. \end{array} \right.$$

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

单位根反演

DFT 的本质就是单位根反演

$$\forall k,[n \mid k] = \frac{1}{n} \sum_{i=0}^{n-1} \omega_n^{ik}$$

一个应用的例子

$$\begin{aligned} \sum_{i=0}^{[\frac{n}{k}]} [x^{ik}] f(x) &= \sum_{i=0}^n [k \mid i] [x^i] f(x)\\ &=\sum_{i=0}^n [x^i] f(x) \frac{1}{k} \sum_{j=0}^{k-1} \omega_{k}^{ji}\\ &=\frac{1}{k} \sum_{i=0}^n a_i \sum_{j=0}^{k-1} \omega_{k}^{ij}\\ &=\frac{1}{k} \sum_{j=0}^{k-1} \sum_{i=0}^n a_i(\omega_k^j)^i\\ &=\frac{1}{k} \sum_{j=0}^{k-1} f(\omega_{k}^j) \end{aligned}$$

单位根反演转自：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$，则由上面公式

$$\sum_{i \in [0, n], k \mid i} \binom{n}{i} G^i = \frac{1}{k} \sum_{j=0}^{k-1} (G+\omega_{k}^j) ^n$$

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