反演魔术————二项式反演

演绎推理是我们在数学中经常遇到的一些方法。对于数列来说，通过原数列计算出新的数列叫作演绎，而通过计算出的数列反推出原数列则被称为反演。

形式化地，如果原数列为 $\{f_n\}$，新数列是 $\{g_n\}$ ，且满足

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

反演就是我们希望通过 $\{g_n\}$ 得到 $\{f_n\}$ :

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

结合一下就是

$g_n=\sum_{i=0}^n a_{ni} f_i \Leftrightarrow f_n=\sum_{i=0}^n b_{ni} g_i$

数列反演有许许多多种不同的类型，就例如莫比乌斯反演，二项式反演等等。其实，我们发现反演其实就是在解方程，一些方程组有算法上固定的、特殊的解，我们对于这些特殊的算法冠以具体的名字，就例如二项式反演。

二项式反演

二项式反演讲的是:

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

这个式子高度对称，它还有一个等价形式是我们所常用的：

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

其实这里应该是双箭头，但是在这里右式是反演，左式则是演绎，故我们向右推出。先来证明这个反演公式，然后介绍它的应用。

代数证明

我们从右边开始，将 $g_n=\sum_{i=0}^n C_n^i f_i$ 带入:

$\sum_{i=0}^n (-1)^{n-i} C_n^i g_i$ $= \sum_{i=0}^n (-1)^{n-i} C_n^i \sum_{j=0}^i C_i^j f_j$ $= \sum_{i=0}^n \sum_{j=0}^i (-1)^{n-i} C_n^i C_i^j f_j$

我们尝试交换求和顺序。首先我们观察到:

$C_n^iC_i^j=\frac{n!}{i!(n-i)!}\frac{i!}{j!(i-j)!}=\frac{n!}{j!(n-j)!}\frac{(n-j)!}{(n-i)!(i-j)!}=C_n^jC_{n-j}^{n-i}$

带入进去得到:

$\sum_{i=0}^n (-1)^{n-i} C_n^i g_i$ $= \sum_{i=0}^n \sum_{j=0}^i (-1)^{n-i} C_n^jC_{n-j}^{n-i} f_j$ $= \sum_{j=0}^n \sum_{i=j}^n C_n^j f_j (-1)^{n-i}C_{n-j}^{n-i}$

在这里我们交换了求和顺序，是因为我们发现两重 $\sum$ 所需要的 $(i,j)$ 依次是

$(0,0)$
$(1,0) (1,1)$
$(2,0) (2,1) (2,2)$
$(3,0) (3,1) (3,2) (3,3)$
$\ \ \ \vdots\ \ \ \ \ \ \ \ \vdots\ \ \ \ \ \ \ \ \vdots\ \ \ \ \ \ \ \ \vdots\ \ \ \ \ \ \ \ \ddots$
$(n,0) (n,1) (n,2) (n,3)\ \ \ \cdots\ \ \ (n,n)$

我们这是一行一行求得的，我们现在尝试一列一列求:

$(0,0) (1,0) (2,0) (3,0)\ \ \ \cdots\ \ \ (n,0)$
$(1,1) (2,1) (3,1)\ \ \ \cdots\ \ \ (n,1)$
$(2,2) (3,2)\ \ \ \cdots\ \ \ (n,2)$
$(3,3)\ \ \ \cdots\ \ \ (n,3)$
$\ \ \ \ \vdots $
$(n,n)$

把 $C_n^jf_j$ 提取出来得到：

$\sum_{i=0}^n (-1)^{n-i} C_n^i g_i$ $= \sum_{j=0}^n C_n^j f_j \sum_{i=j}^n (-1)^{n-i}C_{n-j}^{n-i}$

我们着眼于: $\sum_{i=j}^n (-1)^{n-i}C_{n-j}^{n-i} =\sum_{k=0}^{n-j} (-1)^kC_{n-j}^k$

• 当 $n-j \neq 0$ 时，$\sum_{k=0}^{n-j} (-1)^kC_{n-j}^k=(1-1)^{n-j}=0$
• 当 $n-j = 0$ 时，$j=n$ 且 $\sum_{k=0}^{n-j} (-1)^kC_{n-j}^k=(-1)^0C_0^0=1$

所以只有当 $j=n$ 时 $\sum_{i=0}^n (-1)^{n-i} C_n^i g_i \neq 0$，于是

$\sum_{i=0}^n (-1)^{n-i} C_n^i g_i$ $= C_n^n f_n (-1)^{0}C_{0}^{0} = f_n$

证毕。

生成函数

生成函数证法尤为简单。我们对原式展开后移项：

$g_n=\sum_{i=0}^n C_n^i f_i =\sum_{i=0}^n \frac{n!}{i!(n-i)!} f_i $ $\Leftrightarrow \frac{g_n}{n!}=\sum_{i=0}^n \frac{1}{(n-i)!} \frac{f_i}{i!}$

这是一个卷积形式，我们记 $\{f_n\}$ 的指数生成函数为 $F(x)$ ，记 $\{g_n\}$ 的指数生成函数为 $G(x)$

于是我们有 $G(x)=e^xF(x) \Leftrightarrow F(x)=e^{-x}G(x)$

考虑 $F(x)$ 的 $n$ 次方系数有:

$\frac{f_n}{n!}=\sum_{i=0}^n \frac{(-1)^{n-i}}{(n-i)!} \frac{g_i}{i!} \Leftrightarrow f_n=\sum_{i=0}^n (-1)^{n-i} \frac{n!}{i!(n-i)!} g_i $ $\Leftrightarrow f_n=\sum_{i=0}^n (-1)^{n-i} C_n^i g_i$

证毕。

二项式反演的应用

错排问题

错排问题又称伯努利错装信封问题。这个问题有很多不同的题面，下面是其中一种

伯努利错装信封问题

有一个粗心的邮差让 $n$ 封信从信封中掉了出来，但他并不知道每一封信对应着哪一个信封。不负责任的他随机地把信胡乱塞进信封里。问一共有多少种装信的方案使得信全部装进了不同的信封。

我们记错排数为 $\{D_n\}$，表示将 $n$ 封信全部装错的方案数。

我们考虑随便装，一共有 $n!$ 种方案。每种方案可能装错其中的 $0,1,2,…,n$ 封信。考虑装错 $i$ 封信的方案种数，应该是 $C_n^iD_i$, 表示先选出 $i$ 封信有 $C_n^i$ 种，然后装错它们有 $D_i$ 种，乘法原理得到一共 $C_n^iD_i$ 种。故：

$n!=\sum_{i=0}^n C_n^iD_i$

利用二项式反演公式 $g_n=\sum_{i=0}^n C_n^i f_i \Rightarrow f_n=\sum_{i=0}^n (-1)^{n-i} C_n^i g_i$ 可得:

$D_n=\sum_{i=0}^n (-1)^{n-i} C_n^i i!=\sum_{i=0}^n (-1)^{n-i}\frac{n!}{(n-i)!} $ $=n!\sum_{i=0}^n \frac{(-1)^i}{i!}$

这就是错排公式。

第二类斯特林数

将 $n$ 个不同的球放进 $m$ 个不同的盒子，保证盒子非空，求方案数。

记 $n$ 个不同的球放进 $m$ 个不同的盒子里的方案总数为 $Q_n^m$。我们来尝试 $Q_n^m$。

如果将 $n$ 个球随便放进 $m$ 个箱子里而不考虑非空，则一共有 $m^n$ 种方案数。这些方案中，只可能 $0,1,2,…,m$ 个盒子非空。其中，$i$ 个盒子非空的方案数一共 $C_m^iQ_n^i$ ，这表示选出 $i$ 个非空的盒子有 $C_m^i$ 中，他们装 $n$ 个不同的球有 $Q_n^i$ 种。于是我们就有：

$m^n=\sum_{i=0}^mC_m^iQ_n^i$

利用二项式反演公式 $g_n=\sum_{i=0}^n C_n^i f_i \Rightarrow f_n=\sum_{i=0}^n (-1)^{n-i} C_n^i g_i$ 可得:

$Q_n^m=\sum_{i=0}^m (-1)^{m-i} C_m^i i^n$

完美解决。

第二类斯特林数指的是 将 $n$ 个不同的球放进 $m$ 个无差别的盒子，保证盒子非空，求方案数。

很明显，只需要把有差别的方案数 $Q_n^m$ 除以盒子的排列数 $m!$ 就是答案，即有第二类斯特林数 $S_n^m$ :

$S_n^m=\frac{1}{m!}\sum_{i=0}^m (-1)^{m-i} C_m^i i^n$

值得一提的是，类比上面我们同样可以得到关于第二类斯特林数的等式:

$m^n=\sum_{i=0}^mP_m^iS_n^i$

再看一眼:

$m^n=S_n^0+S_n^1m+S_n^2m(m-1)+S_n^3m(m-1)(m-2)+\cdots+S_n^m m!$

这告诉我们把乘法幂转换为下降阶乘幂所需要的系数就是第二类斯特林数。

特殊多项式在整点的线性插值

对于一些多项式我们可以在整点上做到线性插值。详见我的博客《多项式的线性插值》

引用和参考

miskcoo@反演魔术：反演原理及二项式反演
vfleaking@炫酷反演魔术