Lagrange 反演

形式 Laurent 级数

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

C ((x)) := {\sum_{k \geq N} a_{k} x^{k} : N \in Z, a_{k} \in C}

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

若对于 $f := \sum_{k \geq N} f_{k} x^{k}$ 且 $f_{N} \neq 0$ 存在 $g = \sum_{k \geq - N} g_{k} x^{k}$ 满足 $f g = 1$ 那么

g_{k} := {\begin{cases} f_{N}^{- 1}, & if k = - N, \\ - f_{N}^{- 1} \sum_{i > N} f_{i} g_{k - i}, & otherwise \end{cases}

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

ord f := min {k : f_{k} \neq 0}

显然对于 $g \neq 0$ 有

ord (f g) = ord (f) + ord (g)

形式留数

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

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

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

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

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

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

证明：设 $ord f = k$ 那么

\begin{aligned} res (\frac{f^{'}}{f}) & = res (\frac{k f_{k} x^{k - 1} + \dots}{f_{k} x^{k} + f_{k + 1} x^{k + 1} + \dots}) \\ = res (\frac{k f_{k} x^{- 1} + \dots}{f_{k} + f_{k + 1} x + \dots}) \\ = k \end{aligned}

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

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

\begin{aligned} res x^{k} & = 0 \\ res (g^{k} g^{'}) & = res (\frac{1}{k + 1} {(g^{k + 1})}^{'}) \\ = \frac{1}{k + 1} res ({(g^{k + 1})}^{'}) \\ = 0 \end{aligned}

若 $k = - 1$ 那么

\begin{aligned} res f & = res (x^{- 1}) = 1 \\ res (f (g) g^{'}) & = res (g^{'} / g) \\ = ord (g) \\ = res (f) ord (g) \end{aligned}

复合逆

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

命题： $f (x) := \sum_{k \geq 1} f_{k} x^{k}$ 存在复合逆 $f^{⟨ - 1 ⟩} (x)$ 当且仅当 $f (0) = 0 \neq f^{'} (0)$ ，此时 $f^{⟨ - 1 ⟩} (x)$ 是唯一的。进一步说：若 $g (x) = \sum_{k \geq 1} g_{k} x^{k}$ 满足 $f (g (x)) = x$ 或 $g (f (x)) = x$ 那么 $g (x) = f^{⟨ - 1 ⟩} (x)$ 。

证明：考虑

\begin{aligned} g (f (x)) & = g_{1} (f_{1} x + f_{2} x^{2} + f_{3} x^{3} + \dots) \\ + g_{2} (f_{1} x + f_{2} x^{2} + \dots)^{2} \\ + g_{3} (f_{1} x + \dots)^{3} \\ + \dots \\ = g_{1} f_{1} x + (g_{1} f_{2} + g_{2} f_{1}^{2}) x^{2} + (g_{1} f_{3} + 2 g_{2} f_{1} f_{2} + g_{3} f_{1}^{3}) x^{3} + \dots \end{aligned}

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

{\begin{cases} g_{1} f_{1} & = 1 \\ g_{1} f_{2} + g_{2} f_{1}^{2} & = 0 \\ g_{1} f_{3} + 2 g_{2} f_{1} f_{2} + g_{3} f_{1}^{3} & = 0 \\ ⋮ \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 C [[x]]$ 满足 $f (g (x)) = g (f (x)) = x$ 。取 $Φ (x) \in C [[x]]$ （或 $Φ (x) \in C ((x))$ ），那么

\begin{aligned} [x^{n}] Φ (f (x)) & = [x^{n - 1}] Φ (x) \frac{g^{'} (x)}{g (x)} {(\frac{x}{g (x)})}^{n} \\ = [x^{- 1}] \frac{Φ (x) g^{'} (x)}{g (x)^{n + 1}} \end{aligned}

证明：

\begin{aligned} [x^{n}] Φ (f (x)) & = res (\frac{Φ (f (x))}{x^{n + 1}}) \\ = res (\frac{Φ (f (g (x))) g^{'} (x)}{g (x)^{n + 1}}) \cdot {(ord (g (x)))}^{- 1} \\ = res (\frac{Φ (x) g^{'} (x)}{g (x)^{n + 1}}) \end{aligned}

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

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

或者

\begin{aligned} [x^{n}] Φ (f (x)) & = \frac{1}{n} [x^{n - 1}] Φ^{'} (x) {(\frac{x}{g (x)})}^{n} \\ = \frac{1}{n} [x^{- 1}] \frac{Φ^{'} (x)}{g (x)^{n}} \end{aligned}

发现

\begin{aligned} res (\frac{Φ^{'} (x)}{g (x)^{n}} - n \frac{Φ (x) g^{'} (x)}{g (x)^{n + 1}}) & = res ({(\frac{Φ (x)}{g (x)^{n}})}^{'}) \\ = 0 \end{aligned}

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

参考文献

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

本页面最近更新：2024/3/29 23:25:47，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：hly1204, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用