二项式反演公式及其应用
最后更新于：2022年6月25日 下午
在 上一篇博文 中，介绍过数论中的 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} \]
具体的例子求：\(\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 的，那就更好了！