形式陈述
设系数环 是特征零域, 且 。更一般地, 可为 -代数,但此时须把条件加强为“ 是 中的单位”。方程
在满足 的形式幂级数公理库形式幂级数Formal power series以系数序列为本体并按 Cauchy 卷积运算、不预设解析收敛的无穷级数。中有唯一解。对任意形式级数 和 ,Lagrange–Bürmann 公式为
取 ,其中 ,得到常用形式
特别地,
公式中的 解释了为何通常在 -代数上陈述。若 在零点附近全纯且 ,解析隐函数定理给出同一局部解析解,系数公式保持不变;但收敛性是形式恒等式之外的额外结论。
直觉
隐式方程把一个 -对象描述成一个外层原子和一份由若干 -对象组成的局部配置 。直接递归展开会反复嵌套;反演公式却把“求第 个 系数”改写成在显式幂 中取一次系数。因子 可理解为在一棵带根循环展开中选定根的校正,也可从形式留数换元的 Jacobian 得到。
证明机制很短但不只是代入。将系数写成形式留数,使用 换元:
整理导数并作一次形式分部,便产生 。条件 保证复合有定义, 可逆保证 具有可逆线性项、可以作形式反演;当 是域时,这等价于 。
例子与边界
标号根树满足经典规格
这里 ,而 。因此
于是 ,正是 个标号顶点上的根树数。以 检查:三棵无根标号树各可选三个根,共 棵,和公式一致。这里最后乘回 是 EGF 归一化不可省略的一步。
若 , 的正次系数全为零,不能把 形式当作提供常数项;一般复合公式会由 正确给出 的零。若 ,方程可能只有零解或不再具备所需可逆线性项。若隐式方程不是 形,也应先合法变形或使用更一般的多元反演,不能硬套系数下标。
解析版本还需区分局部解与全局分支。反演保证零点附近的系数,不说明解析延拓能越过哪些分支点,也不直接给出系数渐近;后者要研究隐式解的主导奇点。
推论与应用
Lagrange 反演把递归组合规格转成二项式、指数式或多项式幂的显式系数。平面树、Cayley 根树、停车函数及许多路径类都由此得到闭式。若 ,公式立即给出
即 Catalan 序列的移位形式。
多变量对应是 Good 的多元 Lagrange 反演;物种版本则解释标号树状结构的对称性。精确系数取得后,可用 Stirling 公式或奇点分析研究增长。反演负责解开隐式递归,解析方法负责判断哪个复奇点主导大 行为,两项任务不能互相替代。
参考资料
- 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。