拉格朗日反演及相关技巧整理

技巧

描述方式

尽量使用复合逆的概念来描述拉格朗日反演,这样可以省去很多麻烦。

定义记号 \(F(x)^{-1}\) 表示 \(F(x)\) 的复合逆 (注意不要与倒数混淆),从这个角度来看拉格朗日反演公式可以表示为

\[ [x^n]F(x)^{-1} = \frac 1 n[x^{-1}] \frac 1 {F^n(x)} \\\\ [x^n]G(F(x)^{-1}) = \frac 1 n [x^{-1}] \frac{G'(x)}{F^n(x)} \]

通过与第一个式子几乎完全一样的证明方法可以证明第一个式子的一个扩展:若 \(F(G(x)) = H(x)\),则 \([x^n]F(x) = \frac 1 n [x^{-1}] \frac{H'(x)}{G^n(x)}\)。第二个式子与这一结论是等价的,但是建议尽可能使用第二个式子而不要使用这个结论。

推导技巧

除了移项等变形之外,还可以利用复合进行化简。用复合化简时注意要灵活使用左右逆,即灵活使用 \(A(x) = B(x) \Rightarrow F(A(x))= F(B(x))\)\(A(x) = B(x) \Rightarrow A(F(x)) = B(F(x))\),避免一直只想到其中一种的情况。

对于 \(F(G(x)) = H(x)\),知 \(H(x), F(x)\)\([x^n] G(x)\) 的情况,目前暂不知有什么好的做法,但是对于一些 \(H(x)\)\(G(x)\) 有较为简单的关系的问题是可做的。

例如 \(F(G(x)) = xG(x) \Rightarrow F(G(G(x)^{-1})) = G^{-1}(x)G(G(x)^{-1}) \Rightarrow F(x) = x G(x)^{-1}\),即 \(G\)\(\frac {F(x)} x\) 的复合逆,作拉格朗日反演即可。