拉格朗日反演

拉格朗日反演

拉格朗日反演用于从隐式生成函数中提取系数

拉格朗日反演定理

如果生成函数(A(z))满足函数方程(z=f(A(z))),其中(f(z))满足(f(0)=0),且(f’(0) eq 0)，则$$a_n = [z^n]A(z) = frac{1}{n}u^{n-1}^n$$ $$z^n^m = frac{m}{n} u^{n-m}^n$$ $$[z^n]g(A(z)) =frac{1}{n}[u^{{n-1}]g’(u)(frac{u}{f(u)})}n $$

比如标号树计数生成函数(C(z))满足：$$C(z) = ze^{C(z)}$$ 令(f(u) = frac{u}{e^u}),则$$[z^n]C(z) = frac{1}{n} [u^{n-1}]e{un} = frac{1}{n} frac{n^{{n-1}}{(n-1)!}=frac{n}{n-1}}{n!}$$