← 全部笔记

数学分析

Lagrange 反演公式

文章目录

问题来源与适用范围 原笔记未记录具体出处,保留形式反演及 Catalan 数、有根树两个例子。以下系数公式在特征零的域上使用,n≥1n\ge1;写围道积分证明时,另需相关幂级数在零点附近收敛,不能把纯形式级数直接当成解析函数。

Lagrange 反演公式 (Lagrange Inversion Formula)

1. 简介

Lagrange 反演公式 (Lagrange Inversion Theorem, LIT) 是组合数学和复变函数中的一个核心工具。它主要用于解决以下两类问题:

  1. 求逆函数的系数:已知函数 F(x)F(x),求其逆函数 G(x)G(x) 的幂级数展开系数。
  2. 求解隐含方程:从形如 G(x)=xϕ(G(x))G(x) = x \phi(G(x)) 的方程中提取 G(x)G(x) 的各项系数。

2. 核心公式

设 F(x)F(x) 和 G(x)G(x) 是互逆的形式幂级数(即 F(G(x))=xF(G(x))=x),且满足 F(0)=0,F′(0)≠0F(0)=0, F'(0) \neq 0。

标准形式

若要求逆函数 G(x)G(x) 的第 nn 项系数 [xn]G(x)[x^n]G(x):

[xn]G(x)=1n[xn−1](xF(x))n[x^n] G(x) = \frac{1}{n} [x^{n-1}] \left( \frac{x}{F(x)} \right)^n

复合形式 (扩展)

若要求复合函数 H(G(x))H(G(x)) 的系数,其中 HH 是任意形式幂级数:

[xn]H(G(x))=1n[xn−1]H′(x)(xF(x))n[x^n] H(G(x)) = \frac{1}{n} [x^{n-1}] H'(x) \left( \frac{x}{F(x)} \right)^n

组合学常用形式

若函数 G(x)G(x) 满足隐式方程 G(x)=xϕ(G(x))G(x) = x \phi(G(x))(其中 ϕ(0)≠0\phi(0) \neq 0),则有:

[xn]G(x)=1n[xn−1](ϕ(x))n[x^n] G(x) = \frac{1}{n} [x^{n-1}] (\phi(x))^n


3. 推导思路

下面只给解析情形的证明思路,使用柯西积分公式和变量代换;纯形式情形可用形式留数证明,不以解析收敛为前提。在解析情形,F′(0)≠0F'(0)\ne0 保证存在局部解析逆。

  1. 积分表示:利用围道积分表示系数 [zn]G(z)=12πi∮G(z)zn+1dz[z^n] G(z) = \frac{1}{2\pi i} \oint \frac{G(z)}{z^{n+1}} dz。
  2. 变量代换:令 z=F(w)z = F(w),则 G(z)=wG(z) = w,积分变为对 ww 的积分。
  3. 整理项:通过分部积分或留数计算,将关于 F(w)F(w) 的复杂分式转化为提取 (wF(w))n\left(\frac{w}{F(w)}\right)^n 中 wn−1w^{n-1} 系数的形式。

4. 典型应用例子

例 1:卡特兰数 (Catalan Numbers)

卡特兰数生成函数满足 B(x)=x(1+B(x))2B(x) = x (1 + B(x))^2(B(x)B(x) 为偏移后的生成函数)。 令 ϕ(t)=(1+t)2\phi(t) = (1+t)^2,则由组合学常用形式: [xn]B(x)=1n[tn−1](1+t)2n=1n(2nn−1)=1n+1(2nn)\begin{aligned} [x^n] B(x) &= \frac{1}{n} [t^{n-1}] (1+t)^{2n} \\ &= \frac{1}{n} \binom{2n}{n-1} = \frac{1}{n+1} \binom{2n}{n} \end{aligned}

例 2:Cayley 公式 (有根树计数)

有标号有根树的指数生成函数满足 T(x)=xeT(x)T(x) = x e^{T(x)}。 令 ϕ(t)=et\phi(t) = e^t,则: [xn]T(x)=1n[tn−1](et)n=1n[tn−1]ent=1n⋅nn−1(n−1)!=nn−1n!\begin{aligned} [x^n] T(x) &= \frac{1}{n} [t^{n-1}] (e^t)^n = \frac{1}{n} [t^{n-1}] e^{nt} \\ &= \frac{1}{n} \cdot \frac{n^{n-1}}{(n-1)!} = \frac{n^{n-1}}{n!} \end{aligned} 还原为有标号有根树的计数(指数生成函数的系数乘 n!n!),得到 nn−1n^{n-1};这不是在计数排列。


5. 总结

相关笔记