问题来源与适用范围
原笔记未记录具体出处,保留形式反演及 Catalan 数、有根树两个例子。以下系数公式在特征零的域上使用,;写围道积分证明时,另需相关幂级数在零点附近收敛,不能把纯形式级数直接当成解析函数。
Lagrange 反演公式 (Lagrange Inversion Formula)
1. 简介
Lagrange 反演公式 (Lagrange Inversion Theorem, LIT) 是组合数学和复变函数中的一个核心工具。它主要用于解决以下两类问题:
- 求逆函数的系数:已知函数 ,求其逆函数 的幂级数展开系数。
- 求解隐含方程:从形如 的方程中提取 的各项系数。
2. 核心公式
设 和 是互逆的形式幂级数(即 ),且满足 。
标准形式
若要求逆函数 的第 项系数 :
复合形式 (扩展)
若要求复合函数 的系数,其中 是任意形式幂级数:
组合学常用形式
若函数 满足隐式方程 (其中 ),则有:
3. 推导思路
下面只给解析情形的证明思路,使用柯西积分公式和变量代换;纯形式情形可用形式留数证明,不以解析收敛为前提。在解析情形, 保证存在局部解析逆。
- 积分表示:利用围道积分表示系数 。
- 变量代换:令 ,则 ,积分变为对 的积分。
- 整理项:通过分部积分或留数计算,将关于 的复杂分式转化为提取 中 系数的形式。
4. 典型应用例子
例 1:卡特兰数 (Catalan Numbers)
卡特兰数生成函数满足 ( 为偏移后的生成函数)。
令 ,则由组合学常用形式:
例 2:Cayley 公式 (有根树计数)
有标号有根树的指数生成函数满足 。
令 ,则:
还原为有标号有根树的计数(指数生成函数的系数乘 ),得到 ;这不是在计数排列。
5. 总结
- 关键作用:将“解方程求函数”的难题转化为“计算已知函数幂次系数”的计算题。
- 适用场景:树的计数、格路计数、解析函数求逆。
相关笔记