反演魔术：反演原理及二项式反演

首先我来说说什么是反演（inversion），对于一个数列$\{f_n\}$来说，如果我们知道另外一个数列$\{g_n\}$，满足如下条件

$$g_n = \sum_{i=0}^n a_{ni}f_i$$

反演过程就是利用 $g_0, g_1, \cdots, g_n$ 来表示出 $f_n$

$$f_n = \sum_{i = 0}^n b_{ni}g_i$$

本质上来说，反演其实是一个解线性方程组的过程，但是你观察后发现，这个矩阵实际上是一个三角矩阵，那必然存在着快捷的方法。对于使得这两个反演公式成立的这些系数应该满足什么条件呢？我们现在就来探讨一番！

我们首先讨论一下在什么情况下能够比较容易建立反演公式，之后介绍二项式反演以及它的两个应用，其中一个是错位排列问题

反演原理

首先我来介绍一个 $\delta_{ij}$ 函数，这个函数被称为 Kronecker's delta，它是这样定义的

$$\delta_{ij} = \left \{ \begin{eqnarray*} 0 ~ ~ ~ ,i \neq j\\ 1 ~ ~ ~ ,i = j \end{eqnarray*} \right .$$

这个函数的定义非常简单，我介绍它完全是为了后面叙述的方便

好，我们现在来考虑一下上面的式子，假设对于任意 $0 \leq n \leq N$ 都满足

$$g_n = \sum_{i=0}^n a_{ni}f_i$$

那么我们来考虑一下下面这个式子成立应该要满足什么条件

$$\begin{equation} \label{inversion-2} \sum_{i = 0}^n b_{ni}g_i = f_n \end{equation}$$

我们可以直接将 $g_i$ 代入上式来计算左边的求和

$$\begin{eqnarray*} & & \sum_{i=0}^n b_{ni}g_i \\ &=& \sum_{i=0}^n b_{ni} \sum_{j=0}^i a_{ij}f_j \\ &=& \sum_{i=0}^n f_i \sum_{j=i}^n b_{nj}a_{ji} \end{eqnarray*}$$

对于最后一步，实际上是变换了求和顺序，为了更容易理解，我按照矩阵的形式写出来

$$\begin{bmatrix} b_{n0}a_{00}f_0 & & & \\ b_{n1}a_{10}f_0 & b_{n1}a_{11}f_1 & & \\ b_{n2}a_{20}f_0 & b_{n2}a_{21}f_1 & b_{n2}a_{22}f_2 & \\ \vdots & \vdots & \ddots & \\ b_{nn}a_{n0}f_0 & b_{nn}a_{n1}f_1 & \cdots & b_{nn}a_{nn}f_n \\ \end{bmatrix}$$

那么，前一个求和是先对行进行，再将各行加起来，后一个就是先对列进行，再将各列加起来

这样的话，等式 $\ref{inversion-2}$ 成立的充要条件就是

$$\sum_{j=i}^n b_{nj}a_{ji} = \delta_{ni}$$

同样地，我们反过来也能知道，整个反演公式要成立还需要满足一个必要条件

$$\sum_{j=i}^n a_{nj}b_{ji} = \delta_{ni}$$

也就是，如果你发现某个数列满足上面这个条件，那么你就可以直接建立起反演公式！

事实上，在快速傅立叶变换和逆变换你也可以认为是一个反演的过程，具体可以看这一步的推导，你会发现它和这个很相似。此外，第一类 Stirling 数和第二类 Stirling 数也满足这个条件，不过我暂时没有发现它们建立起的反演公式有什么应用。我下面来介绍一个比较有用的反演公式

二项式反演

下面就来介绍二项式反演（binomial inversion），这可以表示成

$$f_n = \sum_{i=0}^n (-1)^i {n \choose i} g_i \Leftrightarrow g_n = \sum_{i=0}^n (-1)^i {n \choose i} f_i$$

你会发现这个式子具有极强的对称性！另外一个更加常见的形式是

$$f_n = \sum_{i=0}^n {n \choose i} g_i \Leftrightarrow g_n = \sum_{i=0}^n (-1)^{n-i} {n \choose i} f_i$$

现在我们先来给出这个公式的一个容斥解释，之后从代数角度证明一下这个式子，最后介绍两个它的应用

反演？这里就是容斥

实际上，二项式反演是容斥原理（inclusion-exclusion principle）的一种最常见的特例子，让我们先来回忆一下容斥原理

设集合 $S$ 中具有性质 $P_1, P_2, \cdots, P_n$ 的对象的集合为 $A_1, A_2, \cdots, A_n$，那么不具有这些性质的对象的集合大小为

$$\begin{aligned} |\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}|= & |S| - \sum |A_i| + \sum |A_i \cap A_j| \\ &+ \cdots + (-1)^n \sum |A_1 \cap A_2 \cap \cdots \cap A_n| \end{aligned}$$

那么，考虑这样一种特殊的情况，若对于集族 $\mathcal{U} = \{A_1, A_2, \cdots, A_n\}$ 中任意 $i$ 个集合的并集的大小都是 $g_i$，我们不妨设

$$g_i = |A_1 \cap A_2 \cap \cdots \cap A_n|$$

明显的，在 $\mathcal{U}$ 中一共有 $n \choose i$ 个这样的不同交集。另外，我们定义 $g_0 = |S|$

这样一来，上面的容斥结果就是

$$\begin{eqnarray*} & &|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}| \\ &=& g_0 - {n \choose 1} g_1 + {n \choose 2} g_2 + \cdots + (-1)^n {n \choose n} g_n \end{eqnarray*}$$

由于 $\mathcal{U}$ 中任意 $i$ 个集合的交集大小都是 $g_i$，上面的公式左边的项也只和集合个数有关，我们可以设

$$f_i = |\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_i}|$$

同样令 $f_0 = |S|$，那么同样使用容斥原理

$$\begin{eqnarray*} & & &|A_1 \cap A_2 \cap \cdots \cap A_n| \\ &=& &|S| - \sum |\overline{A_i}| + \sum |\overline{A_i} \cap \overline{A_j}| \\ & &+& \cdots + (-1)^n \sum |\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}|\\ &=& &f_0 - {n \choose 1} f_1 + {n \choose 2} f_2 + \cdots + (-1)^n {n \choose n} f_n \end{eqnarray*}$$

这也正是 $g_n$ 的表达式，因此，整个证明就完成了！

代数证明

根据文章开头反演原理部分的讨论，加上这个公式的对称性，我们只需要证明

$$\sum_{i=j}^n (-1)^{i+j} {n \choose i}{i \choose j} = \delta(i, j)$$

这里 $a_{ni} = (-1)^i { n \choose i }, b_{ij} = (-1)^j { i \choose j }$

好，现在我们来证明它，首先需要一个二项式系数的知识

$$\begin{eqnarray*} {n \choose i}{i \choose j} & = & \frac{n!i!}{i!(n-i)!j!(i-j)!} \\ & = & \frac{n!}{j!(n-j)!} \cdot \frac{(n-j)!}{(n-i)![(n-j)-(n-i)]!} \\ & = & {n \choose j}{{n-j} \choose {n-i}} \\ \end{eqnarray*}$$

如果运用组合推理就相当于是，你有一个 $n$ 元素集 $U$，现在对 $(A, B)$ 进行计数，其中 $B \subseteq A \subseteq U$ 且 $|A| = i, |B| = j$，首先对 $A$ 计数，$U$ 的 $i$ 子集有 $n \choose i$，然后对 $B$ 计数，$A$ 的 $j$ 子集有 $i \choose j$

接下来换一种方式，先对 $B$ 进行计数，$B$ 显然是 $U$ 的子集，有 $n \choose j$ 种方案，由于要求 $B \subseteq A$，$B$ 中 $j$ 个元素必须在 $A$ 中，$A$ 还剩下 $i - j$ 个不确定的元素，$U$ 还有 $n - j$ 个可以用的元素，一共有 ${n - j} \choose {i - j}$ 种，于是就得到上面的恒等式，那么可以得到

这样最后就可以得到

$$\begin{eqnarray*} & & \sum_{i=j}^n (-1)^{i+j} {n \choose i}{i \choose j} \\ &=& {n \choose j} (-1)^j \sum_{i=j}^n (-1)^i {{n-j} \choose {n-i}} \\ &=& {n \choose j} (-1)^j \sum_{i=0}^{n-j} (-1)^{n-i} {{n-j} \choose i} \\ &=& {n \choose j} (-1)^{n + j} (1 - 1)^{n - j} \\ &=& \delta_{nj} \end{eqnarray*}$$

于是，反演公式就建立了！

应用

错位排列问题

求有多少个长度为 $n$ 的排列 $a_1, a_2, \cdots, a_n$，满足对于所有的 $1 \leq i \leq n$，使得 $i \neq a_i$

这个问题有很多解法，我们来介绍一个有意思的解法：

为了叙述方便，我们称位置 $i$ 是不变的当且仅当 $a_i = i$

首先我们知道，如果不考虑 $i \neq a_i$ 这个条件，问题是很简单的，长度为 $n$ 的排列一共有 $n!$ 种。并且这些排列是由恰好有 $k(k = 0, 1, 2, \cdots, n)$ 个位置是不变的排列组成，也就是，如果我们设 $f_i$ 为恰好有 $i$ 个位置是不变的排列的个数，那么可以得到

$$n! = \sum_{i=0}^n {n \choose i} f_i$$

是否觉得和刚刚的反演公式很相似？这里的 $g_i$ 就是 $i!$，那么，使用二项式反演可以得到

$$\begin{eqnarray*} f_n &=& \sum_{i=0}^n (-1)^{n+i} {n \choose i} i! \\ &=& \sum_{i=0}^n (-1)^{n+i} \frac{n!}{(n-i)!} \\ &=& n!\sum_{i=0}^n \frac{(-1)^{i}}{i!} \\ \end{eqnarray*}$$

这也就是我们熟悉的错位排列

球染色问题

有 $n$ 个球排成一行，你有 $k$ 种颜色，要求给每一个球染色，相邻两个球颜色不可以相同，并且每种颜色至少使用一次

这是经常在高中数学组合那个部分见到的一个问题，只不过高中题目中数都很小

还是和刚刚的想法一样，如果没有每种颜色至少一次这个条件，那么问题很简单，答案是 $k(k-1)^{n-1}$。这些方案是由恰好使用了 $i(i=0, 1, 2, \cdots, k)$ 种颜色的方案组成的，那么设 $f_i$ 为恰好使用了 $i$ 种颜色的方案数，可以得到

$$k(k-1)^{n-1} = \sum_{i=0}^k {k \choose i} f_i$$

经过反演得到

$$f_k = \sum_{i=2}^k (-1)^{k+i} {k \choose i} i(i-1)^{n-1}$$

结语

其实不仅仅是二项式反演，很多问题中最经常用到的方法就是把条件放宽，求出一个好计算的问题，之后加上这个条件得到方程，利用反演公式算出答案，思想很类似的一题是 BZOJ-3456. 城市规划