Lagrange 反演
形式 Laurent 級數
我們已經知道形式冪級數環 \(\mathbb{C}\lbrack\lbrack x\rbrack\rbrack\) 了，定義形式 Laurent 級數環：
\[
\mathbb{C}\left(\left(x\right)\right):=\left\lbrace \sum_{k\geq N}a_kx^k : N\in\mathbb{Z},a_k\in \mathbb{C}\right\rbrace
\]
我們可以仿照形式冪級數的乘法逆元定義來定義 \(\mathbb{C}\left(\left(x\right)\right)\) 上元素的乘法逆元：
若對於 \(f:=\sum_{k\geq N}f_kx^k\) 且 \(f_N\neq 0\) 存在 \(g=\sum_{k\geq -N}g_kx^k\) 滿足 \(fg=1\) 那麼
\[
g_k:=
\begin{cases}
f_N^{-1}, &\text{ if }k=-N\text{,} \\
-f_N^{-1}\sum_{i> N}f_ig_{k-i}, &\text{ otherwise}
\end{cases}
\]
與形式冪級數類似的，我們也對非零的 \(f(x)=\sum_{k\geq N}f_kx^k\) 定義：
\[
\operatorname{ord} f:=\min\lbrace k:f_k\neq 0\rbrace
\]
顯然對於 \(g\neq 0\) 有
\[
\operatorname{ord} (fg)=\operatorname{ord}(f)+\operatorname{ord}(g)
\]
形式留數
形式留數是形式 Laurent 級數中 \(x^{-1}\) 項的係數。記 \(\operatorname{res} f:=\lbrack x^{-1}\rbrack f\)。
引理：對於任何形式 Laurent 級數 \(f\) 有 \(\operatorname{res} f'=0\)。
證明：考慮形式導數的定義 \(\left(x^k\right)'=kx^{k-1}\)。
引理：對於任何形式 Laurent 級數 \(f,g\) 有 \(\operatorname{res}(f'g)=-\operatorname{res}(fg')\)。
證明：考慮乘法法則 \((fg)'=f'g+fg'\) 所以 \(0=\operatorname{res}((fg)')=\operatorname{res}(f'g)+\operatorname{res}(fg')\)。
引理：對於形式 Laurent 級數 \(f(x)\neq 0\) 有 \(\operatorname{res}(f'/f)=\operatorname{ord}f\)。
證明：設 \(\operatorname{ord}f=k\) 那麼
\[
\begin{aligned}
\operatorname{res}\left(\frac{f'}{f}\right)&=\operatorname{res}\left(\frac{kf_kx^{k-1}+\cdots}{f_kx^k+f_{k+1}x^{k+1}+\cdots}\right) \\
&=\operatorname{res}\left(\frac{kf_kx^{-1}+\cdots}{f_k+f_{k+1}x+\cdots}\right) \\
&=k
\end{aligned}
\]
引理：對於形式 Laurent 級數 \(f\) 和形式冪級數 \(g\neq 0\) 有 \(\operatorname{res}(f)\operatorname{ord}(g)=\operatorname{res}(f(g)g')\)。
證明：考慮線性性，我們只需證明 \(f=x^k\) 其中 \(k\in\mathbb{Z}\) 的情況即可，若 \(k\neq -1\) 那麼
\[
\begin{aligned}
\operatorname{res}x^k&=0 \\
\operatorname{res}(g^kg')&=\operatorname{res}\left(\frac{1}{k+1}\left(g^{k+1}\right)'\right) \\
&=\frac{1}{k+1}\operatorname{res}\left(\left(g^{k+1}\right)'\right) \\
&=0
\end{aligned}
\]
若 \(k=-1\) 那麼
\[
\begin{aligned}
\operatorname{res}f&=\operatorname{res}\left(x^{-1}\right)=1 \\
\operatorname{res}(f(g)g')&=\operatorname{res}(g'/g) \\
&=\operatorname{ord}(g) \\
&=\operatorname{res}(f)\operatorname{ord}(g)
\end{aligned}
\]
複合逆
記 \(A(x)\circ B(x):=A(B(x))\)。
命題：\(f(x):=\sum_{k\geq 1}f_kx^k\) 存在複合逆 \(f^{\langle -1\rangle}(x)\) 當且僅當 \(f(0)=0\neq f'(0)\)，此時 \(f^{\langle -1\rangle}(x)\) 是唯一的。進一步説：若 \(g(x)=\sum_{k\geq 1}g_kx^k\) 滿足 \(f(g(x))=x\) 或 \(g(f(x))=x\) 那麼 \(g(x)=f^{\langle -1\rangle}(x)\)。
證明：考慮
\[
\begin{aligned}
g(f(x))&=g_1(f_1x+f_2x^2+f_3x^3+\cdots ) \\
&+g_2(f_1x+f_2x^2+\cdots )^2 \\
&+g_3(f_1x+\cdots )^3 \\
&+\cdots \\
&=g_1f_1x+(g_1f_2+g_2f_1^2)x^2+(g_1f_3+2g_2f_1f_2+g_3f_1^3)x^3+\cdots
\end{aligned}
\]
因為 \(g(f(x))=x\) 所以有下面的方程組
\[
\begin{cases}
g_1f_1&=1 \\
g_1f_2+g_2f_1^2&=0 \\
g_1f_3+2g_2f_1f_2+g_3f_1^3&=0 \\
\vdots
\end{cases}
\]
我們只能在 \(f_1\neq 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}\lbrack\lbrack x\rbrack\rbrack\) 滿足 \(f(g(x))=g(f(x))=x\)。取 \(\Phi(x)\in\mathbb{C}\lbrack\lbrack x\rbrack\rbrack\)（或 \(\Phi(x)\in\mathbb{C}\left(\left(x\right)\right)\)），那麼
\[
\begin{aligned}
\lbrack x^n\rbrack\Phi(f(x))&=\lbrack x^{n-1}\rbrack\Phi(x)\frac{g'(x)}{g(x)}\left(\frac{x}{g(x)}\right)^n \\
&=\lbrack x^{-1}\rbrack\frac{\Phi(x)g'(x)}{g(x)^{n+1}}
\end{aligned}
\]
證明：
\[
\begin{aligned}
\lbrack x^n\rbrack\Phi(f(x))&=\operatorname{res}\left(\frac{\Phi(f(x))}{x^{n+1}}\right) \\
&=\operatorname{res}\left(\frac{\Phi(f(g(x)))g'(x)}{g(x)^{n+1}}\right)\cdot \left(\operatorname{ord}(g(x))\right)^{-1} \\
&=\operatorname{res}\left(\frac{\Phi(x)g'(x)}{g(x)^{n+1}}\right)
\end{aligned}
\]
一些讀者可能會更加熟悉下面的版本：對於 \(k\in\mathbb{Z}_{\geq 0},n\in\mathbb{Z}_{>0}\) 有
\[
\lbrack x^n\rbrack f(x)^k=\frac{k}{n}\lbrack x^{n-k}\rbrack\left(\frac{x}{g(x)}\right)^n
\]
或者
\[
\begin{aligned}
\lbrack x^n\rbrack \Phi(f(x))&=\frac{1}{n}\lbrack x^{n-1}\rbrack \Phi'(x)\left(\frac{x}{g(x)}\right)^n \\
&=\frac{1}{n}\lbrack x^{-1}\rbrack\frac{\Phi'(x)}{g(x)^n}
\end{aligned}
\]
發現
\[
\begin{aligned}
\operatorname{res}\left(\frac{\Phi'(x)}{g(x)^n}-n\frac{\Phi(x)g'(x)}{g(x)^{n+1}}\right)&=\operatorname{res}\left(\left(\frac{\Phi(x)}{g(x)^n}\right)'\right) \\
&=0
\end{aligned}
\]
可以通過我們已經證明的部分導出。
參考文獻
- Richard P. Stanley and Sergey P. Fomin. Enumerative Combinatorics Volume 2 (Edition 1).
- Ira M. Gessel. Lagrange Inversion.
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用