在上一篇博文中，介绍过数论中的 Mobius 反演公式，让我想起了另一个经典的反演公式－－－二项式反演公式。然而本质上反演公式就是矩阵求逆的过程。只是他们的逆有很简单的形式，因此就有了这样两个反演公式而已。
Mobius 反演在上一篇博客中已经提及，现在着重提一下二项式反演公式，这个公式让我在2014年ACM－ICPC亚洲区域赛西安站拿银，当时F题答案直接算需要$n^3$复杂度，而利用二项式反演公式后，可以在$n^2$复杂度内完美解决。1A过题，感觉超爽。
反演公式与其矩阵形式
由
$$\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 \left(\begin{matrix} n \\ r\end{matrix}\right) f(r)$$
其中 $s \geq 0$ 则
$$f(n)
= \sum _{r = s} ^n (-1)^{n-r} \left(\begin{matrix} n \\ r\end{matrix}\right) g(r)$$
Proof: 要证明反演公式，只需证明，对应的矩阵 $A$ 和 $B$ 互为逆即可. 令 $C = A*B$ 则
$$\begin{align}
c _{ij} = \sum _{k=1} ^n a _{ik} b _{kj} & = \sum _{k =j} ^ i \left(\begin{matrix} i \\ k\end{matrix}\right) (-1)^{k-j} \left(\begin{matrix} k \\ j\end{matrix}\right) =
\sum _{k=0} ^ {i-j} \left(\begin{matrix} i \\ k+j\end{matrix}\right) (-1)^k \left(\begin{matrix} k+j \\ j\end{matrix}\right) \\
& = \left(\begin{matrix} i \\ j\end{matrix}\right) \sum _{k=0} ^ {i-j} (-1)^k \left(\begin{matrix} i-j \\ k\end{matrix}\right) = \left\{ \begin{array}{ll} 1,& i=j \\ 0,& i>j\end{array} \right.
\end{align}$$
证毕。
两类反演公式的应用
这两类反演公式在组合数学和数论中都有诸多应用，这里简单的提几个。
(错排问题) 在 $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$$
Mobius反演在可重复圆排列中有重要应用，这里就不说了。
Mobius 矩阵
由 Mobius 反演公式对应的矩阵我们有,若
$$a _{ij} = \left\{ \begin{array}{cc} 1, & j|i \\
0, & else. \end{array} \right.$$
则，其逆矩阵为
$$b _{ij} = \left\{ \begin{array}{cc} \mu (\frac{i}{j}), & j|i \\
0, & else. \end{array} \right.$$