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

首先我来说说什么是反演（inversion），对于一个数列 ${f_{n}}$ 来说，如果我们知道另外一个数列 ${g_{n}}$ ，满足如下条件 $g_{n} = \sum_{i = 0}^{n} a_{n i} f_{i}$ 反演过程就是利用 $g_{0}, g_{1}, \dots, g_{n}$ 来表示出 $f_{n}$ $f_{n} = \sum_{i = 0}^{n} b_{n i} g_{i}$ 本质上来说，反演其实是一个解线性方程组的过程，但是你观察后发现，这个矩阵实际上是一个三角矩阵，那必然存在着快捷的方法。对于使得这两个反演公式成立的这些系数应该满足什么条件呢？我们现在就来探讨一番！我们首先讨论一下在什么情况下能够比较容易建立反演公式，之后介绍二项式反演以及它的两个应用，其中一个是错位排列问题

反演原理

首先我来介绍一个 $δ_{i j}$ 函数，这个函数被称为 Kronecker’s delta。它在 $i = j$ 时为 $1$ ，在 $i \neq j$ 时为 $0$ 。这个函数的定义非常简单，我介绍它完全是为了后面叙述的方便。

我们现在来考虑一下上面的式子，假设对于任意 $0 \leq n \leq N$ 都满足 $g_{n} = \sum_{i = 0}^{n} a_{n i} f_{i}$ 那么我们来考虑一下下面这个式子成立应该要满足什么条件 $\sum_{i = 0}^{n} b_{n i} g_{i} = f_{n}$ 我们可以直接将 $g_{i}$ 代入上式来计算左边的求和 $\begin{array}{rcl} \sum_{i = 0}^{n} b_{n i} g_{i} \\ = & \sum_{i = 0}^{n} b_{n i} \sum_{j = 0}^{i} a_{i j} f_{j} \\ = & \sum_{i = 0}^{n} f_{i} \sum_{j = i}^{n} b_{n j} a_{j i} \end{array}$ 对于最后一步，实际上是变换了求和顺序，为了更容易理解，我按照矩阵的形式写出来 $[\begin{matrix} b_{n 0} a_{00} f_{0} \\ b_{n 1} a_{10} f_{0} & b_{n 1} a_{11} f_{1} \\ b_{n 2} a_{20} f_{0} & b_{n 2} a_{21} f_{1} & b_{n 2} a_{22} f_{2} \\ ⋮ & ⋮ & ⋱ \\ b_{n n} a_{n 0} f_{0} & b_{n n} a_{n 1} f_{1} & \dots & b_{n n} a_{n n} f_{n} \end{matrix}]$ 那么，前一个求和是先对行进行，再将各行加起来，后一个就是先对列进行，再将各列加起来

这样的话，等式 $???$ 成立的充要条件就是 $\sum_{j = i}^{n} b_{n j} a_{j i} = δ_{n i}$ 同样地，我们反过来也能知道，整个反演公式要成立还需要满足一个必要条件 $\sum_{j = i}^{n} a_{n j} b_{j i} = δ_{n i}$ 也就是，如果你发现某个数列满足上面这个条件，那么你就可以直接建立起反演公式！事实上，在快速傅立叶变换和逆变换你也可以认为是一个反演的过程，具体可以看这一步的推导，你会发现它和这个很相似。此外，第一类 Stirling 数和第二类 Stirling 数也满足这个条件，不过我暂时没有发现它们建立起的反演公式有什么应用。我下面来介绍一个比较有用的反演公式

二项式反演

下面就来介绍二项式反演（binomial inversion），这可以表示成 $f_{n} = \sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{i}) g_{i} \Leftrightarrow g_{n} = \sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{i}) f_{i}$ 你会发现这个式子具有极强的对称性！另外一个更加常见的形式是 $f_{n} = \sum_{i = 0}^{n} (\binom{n}{i}) g_{i} \Leftrightarrow g_{n} = \sum_{i = 0}^{n} (- 1)^{n - i} (\binom{n}{i}) f_{i}$ 现在我们先来给出这个公式的一个容斥解释，之后从代数角度证明一下这个式子，最后介绍两个它的应用

反演？这里就是容斥

实际上，二项式反演是容斥原理（inclusion-exclusion principle）的一种最常见的特例子，让我们先来回忆一下容斥原理：设集合 $S$ 中具有性质 $P_{1}, P_{2}, \dots, P_{n}$ 的对象的集合为 $A_{1}, A_{2}, \dots, A_{n}$ ，那么不具有这些性质的对象的集合大小为 $\begin{aligned} | \overset{―}{A_{1}} \cap \overset{―}{A_{2}} \cap \dots \cap \overset{―}{A_{n}} | = & | S | - \sum | A_{i} | + \sum | A_{i} \cap A_{j} | \\ + \dots + (- 1)^{n} \sum | A_{1} \cap A_{2} \cap \dots \cap A_{n} | \end{aligned}$ 那么，考虑这样一种特殊的情况，若对于集族 $U = {A_{1}, A_{2}, \dots, A_{n}}$ 中任意 $i$ 个集合的并集的大小都是 $g_{i}$ ，我们不妨设 $g_{i} = | A_{1} \cap A_{2} \cap \dots \cap A_{n} |$ 明显的，在 $U$ 中一共有 $(\binom{n}{i})$ 个这样的不同交集。另外，我们定义 $g_{0} = | S |$ 这样一来，上面的容斥结果就是 $\begin{array}{rcl} | \overset{―}{A_{1}} \cap \overset{―}{A_{2}} \cap \dots \cap \overset{―}{A_{n}} | \\ = & g_{0} - (\binom{n}{1}) g_{1} + (\binom{n}{2}) g_{2} + \dots + (- 1)^{n} (\binom{n}{n}) g_{n} \end{array}$ 由于 $U$ 中任意 $i$ 个集合的交集大小都是 $g_{i}$ ，上面的公式左边的项也只和集合个数有关，我们可以设 $f_{i} = | \overset{―}{A_{1}} \cap \overset{―}{A_{2}} \cap \dots \cap \overset{―}{A_{i}} |$ 同样令 $f_{0} = | S |$ ，那么同样使用容斥原理 $\begin{array}{rclr} | A_{1} \cap A_{2} \cap \dots \cap A_{n} | \\ = & | S | - \sum | \overset{―}{A_{i}} | + \sum | \overset{―}{A_{i}} \cap \overset{―}{A_{j}} | \\ + & \dots + (- 1)^{n} \sum | \overset{―}{A_{1}} \cap \overset{―}{A_{2}} \cap \dots \cap \overset{―}{A_{n}} | \\ = & f_{0} - (\binom{n}{1}) f_{1} + (\binom{n}{2}) f_{2} + \dots + (- 1)^{n} (\binom{n}{n}) f_{n} \end{array}$ 这也正是 $g_{n}$ 的表达式，因此，整个证明就完成了！

代数证明

根据文章开头反演原理部分的讨论，加上这个公式的对称性，我们只需要证明 $\sum_{i = j}^{n} (- 1)^{i + j} (\binom{n}{i}) (\binom{i}{j}) = δ (i, j)$ 这里 $a_{n i} = (- 1)^{i} (\binom{n}{i}), b_{i j} = (- 1)^{j} (\binom{i}{j})$ 好，现在我们来证明它，首先需要一个二项式系数的知识 $\begin{array}{rcl} (\binom{n}{i}) (\binom{i}{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)]!} \\ = & (\binom{n}{j}) (\binom{n - j}{n - i}) \end{array}$ 如果运用组合推理就相当于：你有一个 $n$ 元素集 $U$ ，现在对 $(A, B)$ 进行计数，其中 $B \subseteq A \subseteq U$ 且 $| A | = i, | B | = j$ ，首先对 $A$ 计数， $U$ 的 $i$ 子集有 $(\binom{n}{i})$ ，然后对 $B$ 计数， $A$ 的 $j$ 子集有 $(\binom{i}{j})$ 接下来换一种方式，先对 $B$ 进行计数， $B$ 显然是 $U$ 的子集，有 $(\binom{n}{j})$ 种方案，由于要求 $B \subseteq A$ ， $B$ 中 $j$ 个元素必须在 $A$ 中， $A$ 还剩下 $i - j$ 个不确定的元素， $U$ 还有 $n - j$ 个可以用的元素，一共有 $(\binom{n - j}{i - j})$ 种，于是就得到上面的恒等式，那么可以得到这样最后就可以得到 $\begin{array}{rcl} \sum_{i = j}^{n} (- 1)^{i + j} (\binom{n}{i}) (\binom{i}{j}) \\ = & (\binom{n}{j}) (- 1)^{j} \sum_{i = j}^{n} (- 1)^{i} (\binom{n - j}{n - i}) \\ = & (\binom{n}{j}) (- 1)^{j} \sum_{i = 0}^{n - j} (- 1)^{n - i} (\binom{n - j}{i}) \\ = & (\binom{n}{j}) (- 1)^{n + j} (1 - 1)^{n - j} \\ = & δ_{n j} \end{array}$ 于是，反演公式就建立了！

应用

错位排列问题

求有多少个长度为 $n$ 的排列 $a_{1}, a_{2}, \dots, 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, \dots, n)$ 个位置是不变的排列组成，也就是，如果我们设 $f_{i}$ 为恰好有 $i$ 个位置是不变的排列的个数，那么可以得到 $n! = \sum_{i = 0}^{n} (\binom{n}{i}) f_{i}$ 是否觉得和刚刚的反演公式很相似？这里的 $g_{i}$ 就是 $i!$ ，那么，使用二项式反演可以得到 $\begin{array}{rcl} f_{n} & = & \sum_{i = 0}^{n} (- 1)^{n + i} (\binom{n}{i}) i! \\ = & \sum_{i = 0}^{n} (- 1)^{n + i} \frac{n!}{(n - i)!} \\ = & n! \sum_{i = 0}^{n} \frac{(- 1)^{i}}{i!} \end{array}$ 这也就是我们熟悉的错位排列

Update：有点看不懂当时这里写的是什么东西了。这里 $f_{i}$ 似乎应该理解成长度为 $i$ 的排列中错位排列的方案数。对于长度为 $n$ 的序列，可以按照有多少个不变的位置分解成 $n + 1$ 组，如果有 $j$ 个不变的位置，那么剩下 $n - j$ 个位置就是一个错位排列，所以这样一组一共有 $(\binom{n}{j}) f_{n - j}$ 个不同的方案。

球染色问题

有 $n$ 个球排成一行，你有 $k$ 种颜色，要求给每一个球染色，相邻两个球颜色不可以相同，并且每种颜色至少使用一次这是经常在高中数学组合那个部分见到的一个问题，只不过高中题目中数都很小还是和刚刚的想法一样，如果没有每种颜色至少一次这个条件，那么问题很简单，答案是 $k (k - 1)^{n - 1}$ 。这些方案是由恰好使用了 $i (i = 0, 1, 2, \dots, k)$ 种颜色的方案组成的，那么设 $f_{i}$ 为恰好使用了 $i$ 种颜色的方案数，可以得到 $k (k - 1)^{n - 1} = \sum_{i = 0}^{k} (\binom{k}{i}) f_{i}$ 经过反演得到 $f_{k} = \sum_{i = 2}^{k} (- 1)^{k + i} (\binom{k}{i}) i (i - 1)^{n - 1}$

结语

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

本文遵守 CC BY-NC 4.0 许可协议。

以下是旧版博客的评论

2017-08-23 22:39:35

徐子修 (#1)

請問二項式反演那邊-1的次方是n+i還是n-i呢
2017-08-23 22:47:45

miskcoo (#2) reply to 徐子修 (#1)

其实没有太大区别，假设 $n - i$ 非负的话， $(- 1)^{n - i} \cdot (- 1)^{2 i} = (- 1)^{n + i}$
2018-01-08 15:18:38

jjikkollp (#3)

最下面的式子是 $f_{k} = \sum (- 1)^{k - i} (\binom{k}{i}) i (i - 1)^{n - 1}$ 吧 qwq
2018-01-14 12:25:46

miskcoo (#4) reply to jjikkollp (#3)

没错… 我打错了QAQ
2018-01-18 10:01:03

MaxMercer (#5)

哇大神很喜欢你的blog，能加个qq吗...(一个还在路上的oier
2018-02-06 15:11:21

WilliamPon (#6)

作者大大，你在“反演原理”里的“为方便理解写出的矩阵”应该是错误的吧。你接下来的描述与式子相符，但矩阵无法与你的描述相符。我自己尝试根据式子写了一下，是否应该是 bn0 a00 f0 bn1 a10 f0 bn1a11f1 bn2 a20 f0 bn2a21f1 bn2a2f2 ...
2018-02-06 15:14:47

WilliamPon (#7) reply to WilliamPon (#6)

好像评论里排版有点问题，主要问题在f应是每一行从左至右递增的不过你的这篇博文真的很不错，十分感谢
2018-02-06 15:31:02

miskcoo (#8) reply to WilliamPon (#6)

没错是这样。感谢～
2018-09-19 20:19:01

cx233666 (#9)

请问最后如果是要恰好出现t次t<=k怎么做，我尝试推广了一下，好像有点问题
2018-10-07 19:07:04

cx233666 (#10)

好吧我sb了
2018-12-12 21:37:36

Twilight_ (#11)

谢谢博主！受教了
2019-02-19 15:29:19

ajcxsu (#12)

代数证明的一开始那个式子是不是 $δ (n, j)$ 呀...
2019-03-05 16:52:36

cal (#13) reply to ajcxsu (#12)

同问
2019-03-18 11:50:12

SuuTTT (#14)

**不变**的定义是不是写错了，应该是 $a_{i} / n e q i$ 啊，这样 $f_{n}$ 是错排公式才对
2019-03-18 11:51:31

SuuTTT (#15) reply to SuuTTT (#14)

$i \neq a_{i}$
2019-05-26 20:52:55

cresel (#16)

好文章！谢谢博主
2019-11-28 10:33:59

GZZ (#17)

👍 补充个事，（6）（7）两式应该是等价的，都是（3）（4）成立的充要条件，可以看成互逆的下三角矩阵
2020-05-01 21:32:50

wzsCD (#18)

"若对于集族 U={A1,A2,⋯,An} 中任意 i 个集合的并集的大小都是 gi"是不是还要证一遍对于任意g都构造的出来U？谢谢