Lagrange 反演

形式 Laurent 级数

我们已经知道形式幂级数环 $\mathbb{C}[[x]]$ 了，定义形式 Laurent 级数环：

$$\mathbb{C}\left(\left(x\right)\right):=\left\{\sum _{k\ge N}{a}_k{x}^k:N\in \mathbb{Z},a_k\in \mathbb{C}\right\}$$

我们可以仿照形式幂级数的乘法逆元定义来定义 $\mathbb{C}\left(\left(x\right)\right)$ 上元素的乘法逆元：

若对于 $f:={\sum }_{k\ge N}{f}_k{x}^k$ 且 $f_N\ne 0$ 存在 $g={\sum }_{k\ge -N}{g}_k{x}^k$ 满足 $fg=1$ 那么

$$g_k:=\{\begin{array}{ll}{f}_N^{-1},& \text{ if }k=-N\text{,}\\ -f_N^{-1}{\sum }_{i>N}{f}_i{g}_{k-i},& \text{ otherwise}\end{array}$$

与形式幂级数类似的，我们也对非零的 $f(x)={\sum }_{k\ge N}{f}_k{x}^k$ 定义：

$$\mathrm{ord}f:=\min \{k:f_k\ne 0\}$$

显然对于 $g\ne 0$ 有

$$\mathrm{ord}(fg)=\mathrm{ord}(f)+\mathrm{ord}(g)$$

形式留数

形式留数是形式 Laurent 级数中 $x^{-1}$ 项的系数。记 $\mathrm{res}f:=[x^{-1}]f$。

引理：对于任何形式 Laurent 级数 $f$ 有 $\mathrm{res}{f}^{\prime }=0$。

证明：考虑形式导数的定义 ${\left(x^k\right)}^{\prime }=k{x}^{k-1}$。

引理：对于任何形式 Laurent 级数 $f,g$ 有 $\mathrm{res}(f^{\prime }g)=-\mathrm{res}(f{g}^{\prime })$。

证明：考虑乘法法则 $(fg{)}^{\prime }=f^{\prime }g+f{g}^{\prime }$ 所以 $0=\mathrm{res}((fg{)}^{\prime })=\mathrm{res}(f^{\prime }g)+\mathrm{res}(f{g}^{\prime })$。

引理：对于形式 Laurent 级数 $f(x)\ne 0$ 有 $\mathrm{res}(f^{\prime }/f)=\mathrm{ord}f$。

证明：设 $\mathrm{ord}f=k$ 那么

$$\begin{array}{rl}\mathrm{res}\left(\frac{f^{\prime }}{f}\right)& =\mathrm{res}\left(\frac{k{f}_k{x}^{k-1}+\cdots }{f_k{x}^k+f_{k+1}{x}^{k+1}+\cdots }\right)\\ & =\mathrm{res}\left(\frac{k{f}_k{x}^{-1}+\cdots }{f_k+f_{k+1}x+\cdots }\right)\\ & =k\end{array}$$

引理：对于形式 Laurent 级数 $f$ 和形式幂级数 $g\ne 0$ 有 $\mathrm{res}(f)\mathrm{ord}(g)=\mathrm{res}(f(g)g^{\prime })$。

证明：考虑线性性，我们只需证明 $f=x^k$ 其中 $k\in \mathbb{Z}$ 的情况即可，若 $k\ne -1$ 那么

$$\begin{array}{rl}\mathrm{res}{x}^k& =0\\ \mathrm{res}(g^k{g}^{\prime })& =\mathrm{res}\left(\frac{1}{k+1}{\left(g^{k+1}\right)}^{\prime }\right)\\ & =\frac{1}{k+1}\mathrm{res}\left({\left(g^{k+1}\right)}^{\prime }\right)\\ & =0\end{array}$$

若 $k=-1$ 那么

$$\begin{array}{rl}\mathrm{res}f& =\mathrm{res}\left(x^{-1}\right)=1\\ \mathrm{res}(f(g)g^{\prime })& =\mathrm{res}(g^{\prime }/g)\\ & =\mathrm{ord}(g)\\ & =\mathrm{res}(f)\mathrm{ord}(g)\end{array}$$

复合逆

记 $A(x)\circ B(x):=A(B(x))$。

命题：$f(x):={\sum }_{k\ge 1}{f}_k{x}^k$ 存在复合逆 $f^{⟨-1⟩}(x)$ 当且仅当 $f(0)=0\ne f^{\prime }(0)$，此时 $f^{⟨-1⟩}(x)$ 是唯一的。进一步说：若 $g(x)={\sum }_{k\ge 1}{g}_k{x}^k$ 满足 $f(g(x))=x$ 或 $g(f(x))=x$ 那么 $g(x)=f^{⟨-1⟩}(x)$。

证明：考虑

$$\begin{array}{rl}g(f(x))& =g_1(f_{1}x+f_2{x}^2+f_3{x}^3+\cdots )\\ & +g_2(f_{1}x+f_2{x}^2+\cdots {)}^2\\ & +g_3(f_{1}x+\cdots {)}^3\\ & +\cdots \\ & =g_1{f}_{1}x+(g_1{f}_2+g_2{f}_1^2)x^2+(g_1{f}_3+2g_2{f}_1{f}_2+g_3{f}_1^3)x^3+\cdots \end{array}$$

因为 $g(f(x))=x$ 所以有下面的方程组

$$\{\begin{array}{ll}{g}_1{f}_1& =1\\ g_1{f}_2+g_2{f}_1^2& =0\\ g_1{f}_3+2g_2{f}_1{f}_2+g_3{f}_1^3& =0\\ ⋮& \end{array}$$

我们只能在 $f_1\ne 0$ 时才能解出第一个等式，然后依次可以解出 $g_2,\dots$。

特别的，考虑 $f(h(x))=x$ 那么 $g(f(h(x)))=g(x)$，进而 $g(x)=g\circ f\circ h(x)=x\circ h(x)=h(x)$。

Lagrange 反演公式

令 $f(x),g(x)\in \mathbb{C}[[x]]$ 满足 $f(g(x))=g(f(x))=x$。取 $\Phi (x)\in \mathbb{C}[[x]]$（或 $\Phi (x)\in \mathbb{C}\left(\left(x\right)\right)$），那么

$$\begin{array}{rl}[x^n]\Phi (f(x))& =[x^{n-1}]\Phi (x)\frac{g^{\prime }(x)}{g(x)}{\left(\frac{x}{g(x)}\right)}^n\\ & =[x^{-1}]\frac{\Phi (x)g^{\prime }(x)}{g(x{)}^{n+1}}\end{array}$$

证明：

$$\begin{array}{rl}[x^n]\Phi (f(x))& =\mathrm{res}\left(\frac{\Phi (f(x))}{x^{n+1}}\right)\\ & =\mathrm{res}\left(\frac{\Phi (f(g(x)))g^{\prime }(x)}{g(x{)}^{n+1}}\right)\cdot {\left(\mathrm{ord}(g(x))\right)}^{-1}\\ & =\mathrm{res}\left(\frac{\Phi (x)g^{\prime }(x)}{g(x{)}^{n+1}}\right)\end{array}$$

一些读者可能会更加熟悉下面的版本：对于 $k\in {\mathbb{Z}}_{\ge 0},n\in {\mathbb{Z}}_{>0}$ 有

$$[x^n]f(x{)}^k=\frac{k}{n}[x^{n-k}]{\left(\frac{x}{g(x)}\right)}^n$$

或者

$$\begin{array}{rl}[x^n]\Phi (f(x))& =\frac{1}{n}[x^{n-1}]{\Phi }^{\prime }(x){\left(\frac{x}{g(x)}\right)}^n\\ & =\frac{1}{n}[x^{-1}]\frac{{\Phi }^{\prime }(x)}{g(x{)}^n}\end{array}$$

发现

$$\begin{array}{rl}\mathrm{res}\left(\frac{{\Phi }^{\prime }(x)}{g(x{)}^n}-n\frac{\Phi (x)g^{\prime }(x)}{g(x{)}^{n+1}}\right)& =\mathrm{res}\left({\left(\frac{\Phi (x)}{g(x{)}^n}\right)}^{\prime }\right)\\ & =0\end{array}$$

可以通过我们已经证明的部分导出。

参考文献

1. Richard P. Stanley and Sergey P. Fomin. Enumerative Combinatorics Volume 2 (Edition 1).
2. Ira M. Gessel. Lagrange Inversion.