标签：limits dbinom Longleftrightarrow sum 矩阵 反演

反演

“反演”的本质 : 两个函数之间的双向关系。

我们通常可以用矩阵来描述这种关系。

\[F = G*A\\ F*A^T=G \]

\(A\)即为关系矩阵。

所谓反演就是关系矩阵的逆。

\[B = A^T\\ F*B=F*A^T=G \]

利用关系矩阵，我们就可以实现两个矩阵（函数）的来回变化。

二项式反演：

形式一：

\[A[n,i]=(-1)^i\dbinom{n}{i}, B[n,i]=(-1)^i\dbinom{n}{i}\\ F(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}G[i] \Longleftrightarrow G(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}F[i] \]

该反演成立的从要条件就是\(A*B=I\)。

证明：

\[A*B[x,y]=\sum\limits_{i=0}^nA[x,i]*B[i,y]\\ =\sum\limits_{i=0}^n(-1)^i\dbinom{x}{i}(-1)^y\dbinom{i}{y}\\ \left.\begin{array}{l} \because i>y \Longrightarrow \dbinom{y}{i}=0\\ \because i<x \Longrightarrow \dbinom{i}{x}=0 \end{array} \right\} \Longrightarrow A*B[x,y]=[x=y]\Longrightarrow A*B=I \]

形式二：

\[A[n,i]=\dbinom{n}{i}, B[n,i]=(-1)^{n-i}\dbinom{n}{i}\\F(n)=\sum\limits_{i=0}^n\dbinom{n}{i}G[i] \Longleftrightarrow G(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}F[i] \]

因为：

\[A*B[x,y]=\sum\limits_{i=0}^nA[x,i]*B[i,y]\\ =\sum\limits_{i=0}^n(-1)^i\dbinom{x}{i}(-1)^y\dbinom{i}{y}\\ =\sum\limits_{i=0}^n\dbinom{x}{i}(-1)^{i-y}\dbinom{i}{y} \]

所以有了新的关系对：\(A[n,i]=\dbinom{n}{i}\), \(B[n,i]=(-1)^{n-i}\dbinom{n}{i}\)

形式三：

\[A[n,i]=\dbinom{i}{n}, B[n,i]=(-1)^{i-n}\dbinom{i}{n}\\F(n)=\sum\limits_{i=0}^n\dbinom{i}{n}G[i] \Longleftrightarrow G(n)=\sum\limits_{i=0}^n(-1)^{i-n}\dbinom{i}{n}F[i] \]

结论：任意互逆矩阵在转置后依然互逆。

证明：

\[A*B=I\\ (A*B)^T=B^T*A^T=I^T\\ I=I^T\\ A^T*B^T=I \]

\(A[n,i]={\dbinom{n}{i}}\)转置后\(A[n,i]=\dbinom{i}{n}\)

\(B[n,i]={(-1)^{n-i}\dbinom{n}{i}}\)转置后\(B[n,i]=(-1)^{i-n}\dbinom{i}{n}\)

形式四：

\[A[n,i]=(-1)^i\dbinom{i}{n}, B[n,i]=(-1)^{i}\dbinom{i}{n}\\F(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{i}{n}G[i] \Longleftrightarrow G(n)=\sum\limits_{i=0}^n(-1)^{i}\dbinom{i}{n}F[i] \]

证明如形式二。

标签：limits,dbinom,Longleftrightarrow,sum,矩阵,反演
From： https://www.cnblogs.com/Peng1984729/p/18531121