Skip to content

Lagrange 反演定理

Lagrange inversion theorem · Lagrange–Bürmann formula

从隐式方程 T=zφ(T) 直接提取 T 及其复合函数系数的形式幂级数反演公式。

条目类型
定理

形式陈述

设系数环 R 是特征零域,ϕ(u)R[[u]]ϕ(0)0。更一般地,R 可为 Q-代数,但此时须把条件加强为“ϕ(0)R 中的单位”。方程

T(z)=zϕ(T(z))

在满足 T(0)=0形式幂级数中有唯一解。对任意形式级数 H(u)n1,Lagrange–Bürmann 公式为

[zn]H(T(z))=1n[un1]H(u)ϕ(u)n.

H(u)=uk,其中 k1,得到常用形式

[zn]T(z)k=kn[unk]ϕ(u)n.

特别地,

[zn]T(z)=1n[un1]ϕ(u)n.

公式中的 1/n 解释了为何通常在 Q-代数上陈述。若 ϕ 在零点附近全纯且 ϕ(0)0,解析隐函数定理给出同一局部解析解,系数公式保持不变;但收敛性是形式恒等式之外的额外结论。

直觉

隐式方程把一个 T-对象描述成一个外层原子和一份由若干 T-对象组成的局部配置 ϕ(T)。直接递归展开会反复嵌套;反演公式却把“求第 nT 系数”改写成在显式幂 ϕ(u)n 中取一次系数。因子 1/n 可理解为在一棵带根循环展开中选定根的校正,也可从形式留数换元的 Jacobian 得到。

证明机制很短但不只是代入。将系数写成形式留数,使用 z=u/ϕ(u) 换元:

ReszF(z)dz=ResuF(uϕ(u))d(uϕ(u)).

整理导数并作一次形式分部,便产生 H(u)ϕ(u)n/n。条件 T(0)=0 保证复合有定义,ϕ(0) 可逆保证 u/ϕ(u) 具有可逆线性项、可以作形式反演;当 R 是域时,这等价于 ϕ(0)0

例子与边界

标号根树满足经典规格

T(z)=zeT(z).

这里 T(z)=n1tnzn/n!,而 ϕ(u)=eu。因此

[zn]T(z)=1n[un1]enu=1nnn1(n1)!=nn1n!.

于是 tn=nn1,正是 n 个标号顶点上的根树数。以 n=3 检查:三棵无根标号树各可选三个根,共 9=32 棵,和公式一致。这里最后乘回 n! 是 EGF 归一化不可省略的一步。

k=0T0=1 的正次系数全为零,不能把 k/n 形式当作提供常数项;一般复合公式会由 H=0 正确给出 n1 的零。若 ϕ(0)=0,方程可能只有零解或不再具备所需可逆线性项。若隐式方程不是 T=zϕ(T) 形,也应先合法变形或使用更一般的多元反演,不能硬套系数下标。

解析版本还需区分局部解与全局分支。反演保证零点附近的系数,不说明解析延拓能越过哪些分支点,也不直接给出系数渐近;后者要研究隐式解的主导奇点。

推论与应用

Lagrange 反演把递归组合规格转成二项式、指数式或多项式幂的显式系数。平面树、Cayley 根树、停车函数及许多路径类都由此得到闭式。若 T=z(1+T)2,公式立即给出

[zn]T(z)=1n(2nn1),

即 Catalan 序列的移位形式。

多变量对应是 Good 的多元 Lagrange 反演;物种版本则解释标号树状结构的对称性。精确系数取得后,可用 Stirling 公式或奇点分析研究增长。反演负责解开隐式递归,解析方法负责判断哪个复奇点主导大 n 行为,两项任务不能互相替代。

参考资料
  • Richard P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999, §5.4, Lagrange inversion。
  • Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, Appendix A.6 and Chapter I。
  • Ira M. Gessel, “Lagrange inversion,” Journal of Combinatorial Theory, Series A 144, 2016, pp. 212–249。
关系图谱5 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系