拉格朗日反演
注意，本文不是 拉格朗日定理 。
复合与复合逆
定义：形式幂级数 \(F(w) = \sum_{n \ge 0}f_nw^n\) 和 \(G(x) = \sum_{n \ge 1} g_nx^n\) 的复合为 \[ F(G(x)) = \sum_{i \ge 0} f_i(G(x))^i \] 由于 \(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)\) 的复合逆，那么 \[ [x^n]g(x) = \frac{1}{n}[w^{n-1}]\left(\frac{w}{f(w)}\right)^n \] 还有一个推论 \[ [x^n]h(g(x)) = \frac{1}{n}[w^{n-1}]h^{\prime}(w)\left(\frac{w}{f(w)}\right)^n \]
应用
拉格朗日反演可以帮助我们求出多项式的某一项系数，并且可以用来展开生成函数并得到通项。
例1：推导卡特兰数的通项公式。
我假设你看完了 生成函数与数列 这篇，我们推导出了 \[ C(x) = 1 + xC^2(x) \] 令 \(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\) 。
根据拉格朗日反演 \[ \begin{aligned} c_n &= \left[x^n\right] F(x)=\frac{1}{n}\left[x^{n-1}\right]\left(\frac{x}{G(x)}\right)^n \\[6pt]&=\frac{1}{n}\left[x^{n-1}\right](x+1)^{2 n}=\frac{1}{n}\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n} \end{aligned} \] 注：其中用到了二项式定理，另外最后一步是拆组合数
例2：证明 \(n\) 个节点的带标号的有根树的数量为 \(n^{n-1}\) 。
设 \(t_n\) 为 \(n\)
个节点的带标号有根树数量，容易得到递推式 \[
t_n=\sum_{m>0} \frac{1}{m !} \sum_{k_1+k_2+\ldots k_m=n-1} \frac{n
!}{k_{1} ! k_{2} ! \cdots k_{m} !} t_1t_2 \cdots t_m
\] 其中 \(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 ，由卷积的定义得到 \[ \frac{t_n}{n !}=\left[x^{n-1}\right] \sum_{m>0} \frac{1}{m !} T(x)^m=\left[x^{n-1}\right] \mathrm{e}^{T(x)}=\left[x^n\right] x \mathrm{e}^{T(x)} \] 那么 \(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\) 互为复合逆 \[ \left[x^n\right] T(x)=\frac{1}{n}\left[x^{n-1}\right]\left(\frac{x}{G(x)}\right)^n=\frac{1}{n}\left[x^{n-1}\right] \mathrm{e}^{n x} \] 由泰勒展开可知 \[ \left[x^m\right] \mathrm{e}^{n x}=\left[x^m\right] \frac{(n x)^m}{m !}=\frac{n^m}{m !} \] 因此 \[ t_n = n !\left[x^n\right] T(x)=n ! \cdot \frac{1}{n} \cdot \frac{n^{n-1}}{(n-1) !}=n^{n-1} \]
参考文献：
