【Practical】反演原理

在错排问题中使用过二项式反演进行求解，这里对反演原理进行介绍。

基本概念.

对于一个已经存在的数列A $_n$，如果我们知道另一个数列B $_n$，其中的项满足如下等式：

那么反演就是利用[ $b_0$, $b_1$,…, $b_n$]来表示出 $a_n$，也就是说下面一个等式成立：

举一个规模较小的例子来看：

上面给出的这一线性方程组，意思是数列 $B_n$=[a,b,c]，并且其中的每一项都可以由数列 $A_n$=[x,y,z]表示出来(例如a=x+2y+3z). 那么我们要进行的反演，就是用数列 $B_n$=[a,b,c]来表示出数列 $A_n$=[x,y,z]中的每一项，例如x=a+b+c(随便举例的，线性方程组可能无解). 所以本质上来说，反演是一个求解线性方程组的过程，运用线性代数的知识，我们发现该系数矩阵可以化为一个三角阵，那么就必然存在着从 $X_{ni}$到 $Y_{ni}$两个系数矩阵的快速变换方法。

反演原理.

假定现在我们已经拥有了一组等式，也可以说是线性方程组： $b_n=\sum_{i=0}^n {X_{ni}}{a_i} \quad$那么其反演后的方程组 $a_n=\sum_{i=0}^n {Y_{ni}}{b_i} \quad$成立的条件是什么呢？我们推导如下：

二项式反演.

在错排问题中使用过二项式反演进行求解，二项式反演的表示形式如下所示：

上面给出了反演成立的充要条件，所以我们只需要证明 $\sum_{j=i}^n {X_{ji}}{Y_{nj}} =\delta(n,i)\quad$
证明过程如下：