「科普向」拉格朗日反演的几种形式

· · 个人记录

以下设 F(G(x)) = G(F(x)) = x，默认在 “形式 Laurent 级数” 下进行。

形式 Laurent 级数可以理解为包含有限负次项的幂级数。

为了规避形如 \sum_{k\geq 0} y^{-k} = \frac{1}{1-y^{-1}} = \frac{y}{y-1} = -\sum_{k>0} y^k 之类的问题。

它在有限次运算下构成域（？应该是吧）。

复合逆 F(G(x)) = G(F(x)) = x 存在的前提是 F, G 只含正次项（包括常数项也没有），且一次项不为零。

由于在此限制下复合运算构成群，因此复合逆存在且左逆等于右逆。

流行的形式：

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

对称的形式（和上面等价）：

n[x^n]F^k(x) = k[x^{-k}]G^{-n}(x)

该形式的证明：https://www.luogu.com.cn/blog/EntropyIncreaser/shi-xing-zheng-ming-la-ge-lang-ri-fan-yan 。

规避除法的形式：

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

这是由于 [x^{-k-1}]G'(x)\times G^{-n-1}(x) = -\frac{1}{n}[x^{-k}]x(G^{-n})' = \frac{k}{n}[x^{-k}]G^{-n}。

对应的复合形式：

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

对应的齐次形式：

[x^n]H(F(x)) = [x^0]xH(x)G'(x){G^{-n-1}(x)}

由于 F(G(x)) = x，有 G'(x) = 1 / F'(G(x))，此时 G'(x)G^{-n-1}(x) 可以写成复合 (x^{-n-1}/F')(G(x)) 的形式。

多元拉反：

Never Gonna Give You Up （想也知道，怎么可能会有这种内容）。