一.反演的定义.
演绎：对于一个形如 f i = ∑ j = 1 i g j f_i=\sum_{j=1}^{i}g_j fi=∑j=1igj，我们称其为演绎（正演）.
反演：对于一个演绎 f i = ∑ j = 1 i g j f_i=\sum_{j=1}^{i}g_j fi=∑j=1igj，我们称它对应的反演为 g i = ∑ j = 1 i B i , j f j g_i=\sum_{j=1}^{i}B_{i,j}f_j gi=∑j=1iBi,jfj.
也就是说演绎和反演的关系是：
f i = ∑ j = 1 i A i , j g j ⇔ g i = ∑ j = 1 i B i , j f j f_i=\sum_{j=1}^{i}A_{i,j}g_j\Leftrightarrow g_i=\sum_{j=1}^{i}B_{i,j}f_j fi=j=1∑iAi,jgj⇔gi=j=1∑iBi,jfj
我们来推导一下什么时候才会满足这个条件：
f i = ∑ j = 1 i A i , j ∑ k = 1 j B j , k f k = ∑ j = 1 i f j ∑ k = j i A i , k B k , j f_i=\sum_{j=1}^{i}A_{i,j}\sum_{k=1}^{j}B_{j,k}f_k\\ =\sum_{j=1}^{i}f_{j}\sum_{k=j}^{i}A_{i,k}B_{k,j}\\ fi=j=1∑iAi,jk=1∑jBj,kfk=j=1∑ifjk=j∑iAi,kBk,j
同时反过来代入：
g i = ∑ j = 1 i B i , j ∑ k = 1 j A j , k g k = ∑ j = 1 i g j ∑ k = j i B i , k A k , j g_i=\sum_{j=1}^{i}B_{i,j}\sum_{k=1}^{j}A_{j,k}g_k\\ =\sum_{j=1}^{i}g_{j}\sum_{k=j}^{i}B_{i,k}A_{k,j}\\ gi=j=1∑iBi,jk=1∑jAj,kgk=j=1∑igjk=j∑iBi,kAk,j
这个时候，我们发现必然有：
∑ k = j i A i , k B k , j = ∑ k = j i B i , k A k , j = [ i = j ] \sum_{k=j}^{i}A_{i,k}B_{k,j}=\sum_{k=j}^{i}B_{i,k}A_{k,j}=[i=j] k=j∑iAi,kBk,j=k=j∑iBi,kAk,j=[i=j]
由此我们可以得出一个定理：
∑ k = j i A i , k B k , j = [ i = j ] ⇔ ( f i = ∑ j = 1 i A i , j g j ⇔ g i = ∑ j = 1 i B i , j f j ) \sum_{k=j}^{i}A_{i,k}B_{k,j}=[i=j]\Leftrightarrow \left(f_i=\sum_{j=1}^{i}A_{i,j}g_j\Leftrightarrow g_i=\sum_{j=1}^{i}B_{i,j}f_j\right) k=j∑iAi,kBk,j=[i=j]⇔(fi=j=1∑iAi,jgj⇔gi=j=1∑iBi,jfj)
二.反演原理.
我们把 f f f和 g g g都写成一列的矩阵形式，可以得到：
f i , 1 = ∑ j = 1 i A i , j g j , 1 ⇔ g i , 1 = ∑ j = 1 i B i , j f j , 1 f_{i,1}=\sum_{j=1}^{i}A_{i,j}g_{j,1}\Leftrightarrow g_{i,1}=\sum_{j=1}^{i}B_{i,j}f_{j,1} fi,1=j=1∑iAi,jgj,1⇔gi,1=j=1∑iBi,jfj,1
写成矩阵的形式就是：
[ f 1 , 1 f 2 , 1 f 3 , 1 ⋮ f n , 1 ] [ A 1 , 1 0 0 ⋯ 0 A 2 , 1 A 2 , 2 0 ⋯ 0 A 3 , 1 A 3 , 2 A 3 , 3 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ A n , 1 A n , 2 A n , 3 ⋯ A n , n ] = [ g 1 , 1 g 2 , 1 g 3 , 1 ⋮ g n , 1 ] ⇔ [ g 1 , 1 g 2 , 1 g 3 , 1 ⋮ g n , 1 ] [ B 1 , 1 0 0 ⋯ 0 B 2 , 1 B 2 , 2 0 ⋯ 0 B 3 , 1 B 3 , 2 B 3 , 3 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ B n , 1 B n , 2 B n , 3 ⋯ B n , n ] = [ f 1 , 1 f 2 , 1 f 3 , 1 ⋮ f n , 1 ] \left[\begin{matrix} f_{1,1}\\ f_{2,1}\\ f_{3,1}\\ \vdots\\ f_{n,1} \end{matrix}\right] \left[\begin{matrix} A_{1,1}&0&0&\cdots&0\\ A_{2,1}&A_{2,2}&0&\cdots&0\\ A_{3,1}&A_{3,2}&A_{3,3}&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ A_{n,1}&A_{n,2}&A_{n,3}&\cdots&A_{n,n} \end{matrix}\right]= \left[\begin{matrix} g_{1,1}\\ g_{2,1}\\ g_{3,1}\\ \vdots\\ g_{n,1} \end{matrix}\right]\Leftrightarrow\left[\begin{matrix} g_{1,1}\\ g_{2,1}\\ g_{3,1}\\ \vdots\\ g_{n,1} \end{matrix}\right] \left[\begin{matrix} B_{1,1}&0&0&\cdots&0\\ B_{2,1}&B_{2,2}&0&\cdots&0\\ B_{3,1}&B_{3,2}&B_{3,3}&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ B_{n,1}&B_{n,2}&B_{n,3}&\cdots&B_{n,n} \end{matrix}\right]= \left[\begin{matrix} f_{1,1}\\ f_{2,1}\\ f_{3,1}\\ \vdots\\ f_{n,1} \end{matrix}\right] ⎣⎢⎢⎢⎢⎢⎡f1,1f2,1f3,1⋮fn,1⎦⎥⎥⎥⎥⎥⎤⎣⎢⎢⎢⎢⎢⎡A1,1A2,1A3,1⋮An,10A2,2A3,2⋮An,200A3,3⋮An,3⋯⋯⋯⋱⋯000⋮An,n⎦⎥⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎢⎡g1,1g2,1g3,1⋮gn,1⎦⎥⎥⎥⎥⎥⎤⇔⎣⎢⎢⎢⎢⎢⎡g1,1g2,1g3,1⋮gn,1⎦⎥⎥⎥⎥⎥⎤⎣⎢⎢⎢⎢⎢⎡B1,1B2,1B3,1⋮Bn,10B2,2B3,2⋮Bn,200B3,3⋮Bn,3⋯⋯⋯⋱⋯000⋮Bn,n⎦⎥⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎢⎡f1,1f2,1f3,1⋮fn,1⎦⎥⎥⎥⎥⎥⎤
定睛一看，矩阵 A A A和矩阵 B B B互为逆矩阵，所以说求反演系数本质上就是在求逆矩阵.
我们称之为反演原理.
三.转置反演.
考虑一个类似于反演的形式：
f i = ∑ j = i n A j , i g j ⇔ g i = ∑ j = i n B j , i f j f_{i}=\sum_{j=i}^{n}A_{j,i}g_j\Leftrightarrow g_i=\sum_{j=i}^{n}B_{j,i}f_j fi=j=i∑nAj,igj⇔gi=j=i∑nBj,ifj
直接代入式子得到：
f i = ∑ j = i n A j , i ∑ k = j n B k , j f k = ∑ j = i n f j ∑ k = i j B j , k A k , i f_{i}=\sum_{j=i}^{n}A_{j,i}\sum_{k=j}^{n}B_{k,j}f_k\\ =\sum_{j=i}^{n}f_{j}\sum_{k=i}^{j}B_{j,k}A_{k,i} fi=j=i∑nAj,ik=j∑nBk,jfk=j=i∑nfjk=i∑jBj,kAk,i
同理可得到：
g i = ∑ j = i n g j ∑ k = i j A j , k B k , i g_{i}=\sum_{j=i}^{n}g_{j}\sum_{k=i}^{j}A_{j,k}B_{k,i} gi=j=i∑ngjk=i∑jAj,kBk,i
即：
∑ k = i j A j , k B k , i = ∑ k = i j B j , k A k , i = [ i = j ] \sum_{k=i}^{j}A_{j,k}B_{k,i}=\sum_{k=i}^{j}B_{j,k}A_{k,i}=[i=j] k=i∑jAj,kBk,i=k=i∑jBj,kAk,i=[i=j]
若此时有反演：
f i ′ = ∑ j = 1 i A i , j ′ g j ′ ⇔ g i ′ = ∑ j = 1 i B i , j ′ f j ′ f'_{i}=\sum_{j=1}^{i}A'_{i,j}g'_{j}\Leftrightarrow g'_{i}=\sum_{j=1}^{i}B'_{i,j}f'_{j} fi′=j=1∑iAi,j′gj′⇔gi′=j=1∑iBi,j′fj′
由上面的结论得到：
∑ k = j i A i , k ′ B k , j ′ = ∑ k = j i B i , k ′ A k , j ′ = [ i = j ] \sum_{k=j}^{i}A'_{i,k}B'_{k,j}=\sum_{k=j}^{i}B'_{i,k}A'_{k,j}=[i=j] k=j∑iAi,k′Bk,j′=k=j∑iBi,k′Ak,j′=[i=j]
那么此时就可以让 A j , i = A i , j ′ , B j , i = B i , j ′ A_{j,i}=A'_{i,j},B_{j,i}=B'_{i,j} Aj,i=Ai,j′,Bj,i=Bi,j′.
发现 A A A为 A ′ A' A′的转置矩阵， B B B为 B ′ B' B′的转置矩阵，故称下面两个反演互为转置反演：
f i = ∑ j = 1 i A i , j g j ⇔ g i = ∑ j = 1 i B i , j f j f i = ∑ j = i n A j , i g j ⇔ g i = ∑ j = i n B j , i f j f_{i}=\sum_{j=1}^{i}A_{i,j}g_j\Leftrightarrow g_i=\sum_{j=1}^{i}B_{i,j}f_j\\f_{i}=\sum_{j=i}^{n}A_{j,i}g_j\Leftrightarrow g_i=\sum_{j=i}^{n}B_{j,i}f_j fi=j=1∑iAi,jgj⇔gi=j=1∑iBi,jfjfi=j=i∑nAj,igj⇔gi=j=i∑nBj,ifj
若放到矩阵上来说，就是一个三角矩阵的转置矩阵的逆矩阵等于这个三角矩阵的逆矩阵的转置矩阵，即：
A ‾ − 1 = A − 1 ‾ \overline{A}^{-1}=\overline{A^{-1}} A−1=A−1
注意其前提为 A A A是个三角矩阵.
四.转移反演中的某个系数.
假设我们有如下形式的反演：
f i = ∑ j = 1 i A i , j c j g j ⇔ g i = ∑ j = 1 i B i , j f j f_{i}=\sum_{j=1}^{i}A_{i,j}c_{j}g_j\Leftrightarrow g_i=\sum_{j=1}^{i}B_{i,j}f_j\\ fi=j=1∑iAi,jcjgj⇔gi=j=1∑iBi,jfj
考虑如何把系数 c i c_i ci转移到右式中.
设 z i = c j g j z_{i}=c_{j}g_{j} zi=cjgj，那么有：
f i = ∑ j = 1 i A i , j z j ⇔ z i c i = ∑ j = 1 i B i , j f j f i = ∑ j = 1 i A i , j z j ⇔ z i = ∑ j = 1 i B i , j c i f j f_{i}=\sum_{j=1}^{i}A_{i,j}z_{j}\Leftrightarrow \frac{z_{i}}{c_{i}}=\sum_{j=1}^{i}B_{i,j}f_{j}\\ f_{i}=\sum_{j=1}^{i}A_{i,j}z_{j}\Leftrightarrow z_{i}=\sum_{j=1}^{i}B_{i,j}c_{i}f_{j} fi=j=1∑iAi,jzj⇔cizi=j=1∑iBi,jfjfi=j=1∑iAi,jzj⇔zi=j=1∑iBi,jcifj
同理也有：
f i = ∑ j = i n A j , i c j g j ⇔ g i = ∑ j = i n B j , i f j f i = ∑ j = i n A j , i z j ⇔ z i = ∑ j = i n B j , i c i f j f_{i}=\sum_{j=i}^{n}A_{j,i}c_jg_j\Leftrightarrow g_i=\sum_{j=i}^{n}B_{j,i}f_j\\ f_{i}=\sum_{j=i}^{n}A_{j,i}z_j\Leftrightarrow z_{i}=\sum_{j=i}^{n}B_{j,i}c_if_{j} fi=j=i∑nAj,icjgj⇔gi=j=i∑nBj,ifjfi=j=i∑nAj,izj⇔zi=j=i∑nBj,icifj
我们称这个技巧为系数转移.
五.往乘法上的拓展.
乘法意义下的反演：
f i = ∏ j = 1 i g j A i , j ⇔ g i = ∏ j = 1 i f j B i , j f_{i}=\prod_{j=1}^{i}g^{A_{i,j}}_{j}\Leftrightarrow g_{i}=\prod_{j=1}^{i}f^{B_{i,j}}_{j} fi=j=1∏igjAi,j⇔gi=j=1∏ifjBi,j
这种反演对应了把加法换成乘法并把乘法换成幂后的广义矩阵乘法，由于它本质上与最初的反演相同，所以之前反演拥有的性质这个反演都拥有.
六.一个经典的反演变换.
对于一个反演：
f i = ∑ j = 1 i ( − 1 ) j A i , j g j ⇔ g i = ∑ j = 1 i ( − 1 ) j B i , j f j f_i=\sum_{j=1}^{i}(-1)^{j}A_{i,j}g_j\Leftrightarrow g_i=\sum_{j=1}^{i}(-1)^{j}B_{i,j}f_{j} fi=j=1∑i(−1)jAi,jgj⇔gi=j=1∑i(−1)jBi,jfj
很容易变换出与它等价的7种形式：
f i = ∑ j = 1 i A i , j g j ⇔ g i = ∑ j = 1 i ( − 1 ) i − j B i , j f j f i = ∑ j = i n ( − 1 ) j A j , i g j ⇔ g i = ∑ j = i n ( − 1 ) j B j , i f j f i = ∑ j = i n A j , i g j ⇔ g i = ∑ j = i n ( − 1 ) j − i B j , i f j f i = ∏ j = 1 i g j ( − 1 ) j A i , j ⇔ g i = ∏ j = 1 i f j ( − 1 ) j B i , j f i = ∏ j = 1 i g j A i , j ⇔ g i = ∏ j = 1 i f j ( − 1 ) i − j B i , j f i = ∏ j = i n g j ( − 1 ) j A j , i ⇔ g i = ∏ j = i n f j ( − 1 ) j B j , i f i = ∏ j = i n g j A j , i ⇔ g i = ∏ j = 1 i f j ( − 1 ) j − i B j , i f_{i}=\sum_{j=1}^{i}A_{i,j}g_j\Leftrightarrow g_i=\sum_{j=1}^{i}(-1)^{i-j}B_{i,j}f_j\\ f_{i}=\sum_{j=i}^{n}(-1)^{j}A_{j,i}g_j\Leftrightarrow g_i=\sum_{j=i}^{n}(-1)^{j}B_{j,i}f_{j}\\ f_{i}=\sum_{j=i}^{n}A_{j,i}g_j\Leftrightarrow g_i=\sum_{j=i}^{n}(-1)^{j-i}B_{j,i}f_{j}\\ f_i=\prod_{j=1}^{i}g^{(-1)^{j}A_{i,j}}_j\Leftrightarrow g_i=\prod_{j=1}^{i}f^{(-1)^{j}B_{i,j}}_{j}\\ f_i=\prod_{j=1}^{i}g^{A_{i,j}}_j\Leftrightarrow g_i=\prod_{j=1}^{i}f^{(-1)^{i-j}B_{i,j}}_{j}\\ f_i=\prod_{j=i}^{n}g^{(-1)^{j}A_{j,i}}_j\Leftrightarrow g_i=\prod_{j=i}^{n}f^{(-1)^{j}B_{j,i}}_{j}\\ f_i=\prod_{j=i}^{n}g^{A_{j,i}}_j\Leftrightarrow g_i=\prod_{j=1}^{i}f^{(-1)^{j-i}B_{j,i}}_{j}\\ fi=j=1∑iAi,jgj⇔gi=j=1∑i(−1)i−jBi,jfjfi=j=i∑n(−1)jAj,igj⇔gi=j=i∑n(−1)jBj,ifjfi=j=i∑nAj,igj⇔gi=j=i∑n(−1)j−iBj,ifjfi=j=1∏igj(−1)jAi,j⇔gi=j=1∏ifj(−1)jBi,jfi=j=1∏igjAi,j⇔gi=j=1∏ifj(−1)i−jBi,jfi=j=i∏ngj(−1)jAj,i⇔gi=j=i∏nfj(−1)jBj,ifi=j=i∏ngjAj,i⇔gi=j=1∏ifj(−1)j−iBj,i
七.集合间的反演.
集合反演：集合间的反演形如：
f ( S 1 ) = ∑ S 2 ⊆ S 1 A ( S 1 , S 2 ) g ( S 2 ) ⇔ g ( S 1 ) = ∑ S 2 ⊆ S 1 B ( S 1 , S 2 ) f ( S 2 ) f(S_1)=\sum_{S_2\subseteq S_1}A(S_1,S_2)g(S_2)\Leftrightarrow g(S_1)=\sum_{S_2\subseteq S_1}B(S_1,S_2)f(S_2) f(S1)=S2⊆S1∑A(S1,S2)g(S2)⇔g(S1)=S2⊆S1∑B(S1,S2)f(S2)
集合间的反演可以把集合写成二进制的形式，这样就对应了数列上的反演.
转置反演与系数转移的方法仍然适用于集合间的反演.
今天的文章 反演原理相关分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/83285.html