首先我来说说什么是反演(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。它在 $i = j$ 时为 $1$,在 $i \neq j$ 时为 $0$。 这个函数的定义非常简单,我介绍它完全是为了后面叙述的方便。

我们现在来考虑一下上面的式子,假设对于任意 $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. 城市规划

本文遵守 Attribution-NonCommercial 4.0 International 许可协议。