证明鸽了，所以先开始应用篇。
对于一元多项式 \(F,G\) 我们有 Lagrange 反演公式：
\[n[x^n]F^k=k[w^{-k}]G^{-n} \]绝大多数情况我们都取 \(k=1\)。
其中多项式 \(G\) 为 \(F\) 的复合逆，即其满足 \(G(F(x))=x\)。
例 \(1\)：P2767 树的数量
计算 \(n\) 个点的 \(m\) 叉树的数量。
设 \(i\) 个点的 \(m\) 叉树的数量为 \(f_i\)，则设其对应生成函数为 \(F(x)=\sum f_ix^i\)。
利用简单的生成函数知识可以得到 \(F=x\sum\limits_{i}\binom{m}{i}F^i=x(1+F)^m\)
我们利用该式 \(F=x(1+F)^m\) 求得其复合逆 \(G(w)\)（注意我们无需求得 \(F\) 的封闭形式）
不难发现 \(G=\frac{w}{(1+w)^m}\)，此时 \(G(F)=\frac{F}{(1+F)^m}=\frac{x(1+F)^m}{(1+F)^m}=x\)。
那么取 \(k=1\)，则有对应的 Lagrange 反演：
\[[x^n]F=\frac{[w^{-1}]w^{-n}(1+w)^{nm}}{n}=\frac{[w^{n-1}](1+w)^{nm}}{n}=\frac{\binom{nm}{n-1}}{n} \]刚才我们所涉及的都是对一元函数的 Lagrange 反演。
那么我们如果想对二元函数 \(F(x,y)=\sum\limits_{i,j}f_{i,j}x^iy^j\) 的其中一维（\(x\)）反演，应该怎么办呢？
考虑将一个二元函数看做一个一元函数，将一元多项式中 \(x\) 的系数转变为一个关于 \(y\) 的多项式，即 \(F(x)=\sum\limits_i(\sum\limits_jf_{i,j}y^j)x^i\)。
这样我们再对其应用 Lagrange 反演公式时，左式和右式相等就是两个多项式的相等而非先前系数的相等。
考虑把期望化为总和除以个数，后者显然是卡特兰数，那么我们只需要推出前者即可。
不难发现我们就需要设计一个二元生成函数 \(F(x,y)=\sum f_{i,j}x^iy^j\)，一元（\(x\)）表示此时节点个数，一元（\(y\)）表示此时叶子节点个数。
\(F\) 的转移式我们也不难推出，即 \(F=x(y+2F+F^2)\)，由此解得 \(G=\frac{w}{y+2w+w^2}\)。
还是应用 Lagrange 反演公式，可得当节点数为 \(n\) 时，叶子结点个数的生成函数 \(H(y)\)：
\[H(y)=[x^n]F=\frac{[w^{-1}]G^{-n}}{n}=\frac{[w^{n-1}](y+2w+w^2)^n}{n} \]我们要求什么？不难发现最终我们求的答案等于 \(H'(1)\)（因为求导之后先前只作为方案数的系数便会叶子结点的个数本身，而带入 \(y=1\) 能够求得所有系数之和）。
对 \(\frac{[w^{n-1}](y+2w+w^2)^n}{n}\) 求关于 \(y\) 的偏导数，再带入 \(y=1\) 可得 \([w^{n-1}](1+w)^{2n-2}=\binom{2n-2}{n-1}\)。
最终答案为 \(\frac{\binom{2n-2}{n-1}(n+1)}{\binom{2n}{n}}=\frac{n(n+1)}{4n-2}\)。
标签：frac,多项式,sum,反演,应用,Lagrange,binom From： https://www.cnblogs.com/Miracle-blog/p/17236730.html