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

首先我来说说什么是反演(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_1 & b_{n1}a_{11}f_1 &           &            \\
b_{n2}a_{20}f_2 & b_{n2}a_{21}f_2 & b_{n2}a_{22}f_2 &            \\
  \vdots  &   \vdots  &   \ddots  &            \\
b_{nn}a_{n0}f_n & b_{nn}a_{n1}f_n &   \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 计数,Ui 子集有 n \choose i,然后对 B 计数,Aj 子集有 i \choose j

接下来换一种方式,先对 B 进行计数,B 显然是 U 的子集,有 n \choose j 种方案,由于要求 B \subseteq ABj 个元素必须在 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+1} {k \choose i} i(i-1)^{n-1}

结语

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

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/12/inversion-magic-binomial-inversion

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

2 thoughts on “反演魔术:反演原理及二项式反演

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.