拉格朗日反演
注意，本文不是 _拉格朗日定理_ 。
复合与复合逆
定义：形式幂级数 $F(w) = \sum_{n \ge 0}f_nw^n$ 和 $G(x) = \sum_{n \ge 1} g_nx^n$ 的复合为
由于 $G(x)$ 没有常数项，所以即使 $F(x)$ 有无限多个非零项，这两个函数的复合仍然可以定义。
定义：设 $F(w) = \sum_{n \ge 1}f_nw^n$ 和 $G(x) = \sum_{n \ge 1} g_nx^n$ ，如果 $F(G(x))=x$ ，
那么称 $F(w),G(x)$ 互为复合逆（反函数），易得 $F(G(x)) = G(F(x))$ 。
拉格朗日反演
定理：若 $f(w)$ 是 $g(x)$ 的复合逆，那么
还有一个推论
应用
拉格朗日反演可以帮助我们求出多项式的某一项系数，并且可以用来展开生成函数并得到通项。
例1：推导卡特兰数的通项公式。
我假设你看完了 生成函数与数列 这篇，我们推导出了
令 $F(x) = C(x) - 1$ ，我们要求的是 $[x^n]F(x)\,(n\ge 1)$ 。
注意到 $F(x) = x(F(x) + 1)^2$ ，即 $x = \frac{F(x)}{F(x)+1}$ 。
设 $G(x) = \frac{x}{(x+1)^2}$ ，那么 $G(F(x)) = F(G(x)) = x$ ，显然 $F,G$ 常数项为 $0$ 。
根据拉格朗日反演
注：其中用到了二项式定理，另外最后一步是拆组合数
例2：证明 $n$ 个节点的带标号的有根树的数量为 $n^{n-1}$ 。
设 $t_n$ 为 $n$ 个节点的带标号有根树数量，容易得到递推式
其中 $m$ 是枚举根的子树数量， $k_1,k_2,\cdots,k_m$ 是子树大小，
$\frac{n !}{k_{1} ! k_{2} ! \ldots k_{m} !}$ 是把 $n$ 个点分到各子树上再乘上内部的方案数，由于子树没有顺序，所以还要除以 $\frac{1}{m!}$ 。
设 $T(x)$ 为 $t_n$ 的 EGF ，由卷积的定义得到
那么 $T(x)=x\mathrm{e}^{T(x)}$ ，当然这实际上是 EGF 乘法的组合意义。
注意到 $x = \frac{T(x)}{\mathrm{e}^{T(x)}}$ ，不妨设 $G(x) = \frac{x}{\mathrm{e}^x}$ ，则 $T,G$ 互为复合逆
由泰勒展开可知
因此
参考文献：
