本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。
本节目标我们常常能写出一个生成函数（generating function）所满足的方程，比如 \(T(x)=x\mathrm{e}^{T(x)}\)，却解不出 \(T(x)\) 的显式表达式。拉格朗日反演公式（Lagrange Inversion Formula）专门解决这种困境：只要知道 \(T(x)\) 是某个已知幂级数的复合逆，就能直接把 \(T(x)\) 的第 \(n\) 个系数算出来——而无需真正解出 \(T(x)\)。本节先用它数清几类树，最后得到“\([n]\) 上有根树共有 \(n^{n-1}\) 棵”这一著名结论。
我们已经见过这样几类树的例子：一类是每个顶点都带标号的树，一类是没有任何顶点带标号的树。现在我们要考虑只有叶子带标号的树。一棵 \(k\)-系统发生树（\(k\)-phylogenetic tree）是一棵有根、非平面（rooted non-plane）的树，它的叶子用集合 \([n]=\{1,2,\cdots,n\}\) 中的元素一一对应地标号，并且每个非叶子顶点恰好有 \(k\) 个孩子。标号集 \([3]\) 上全部三棵 \(2\)-系统发生树见图 5.44。
图 5.44：叶子集 \([3]\) 上的三棵 \(2\)-系统发生树。小实心点是根与非叶子顶点（不带标号），带圈数字是叶子（带标号）。因为树是“非平面”的，左右孩子的顺序不计，三棵树的区别只在于“哪两片叶子先合并”。
设 \(t_{k,n}\) 为叶子集 \([n]\) 上 \(k\)-系统发生树的棵数，并约定 \(t_{k,0}=0\)。令
\[T_k(x)=\sum_{n\ge 0} t_{k,n}\frac{x^n}{n!}\]
为这一数列的指数型生成函数（exponential generating function）。
去掉这种树的根，我们要么得到空集，要么得到一个由 \(k\) 棵同类树组成的无序集合，于是得到函数方程
\[\tag{5.16} T_k(x)=x+\frac{T_k^k(x)}{k!}.\]
下面这种形式对我们的目的尤其有用：
\[\tag{5.17} T_k(x)-\frac{T_k^k(x)}{k!}=x.\]
方程 (5.16) 的来历：根本身对应生成函数中的 \(x\)；剩下 \(k\) 棵子树构成一个无序的 \(k\) 元集合，对应 \(T_k(x)^k\) 再除以排列数 \(k!\)（因为指数型生成函数中“无序集合”要除以 \(k!\)）。
若 \(k=2\)，则 (5.16) 是二次方程 \(T_2(x)=x+\dfrac{T_2^2(x)}{2}\)。解这个方程，得到公式
\[T_2(x)=1-\sqrt{1-2x},\]
它蕴含
\[t_{2,n}=(2n-3)!!.\]
然而，当 \(k>2\) 时，要找到 \(t_{k,n}\) 的显式公式，就需要更强的工具了。
例：验证 \(k=2\) 的解 我们把 \(T_2(x)=1-\sqrt{1-2x}\) 代回方程 \(T_2=x+\tfrac12 T_2^2\) 检验：
- 记 \(s=\sqrt{1-2x}\)，则 \(T_2=1-s\)，于是 \(T_2^2=(1-s)^2=1-2s+s^2=1-2s+(1-2x)=2-2x-2s\)。
- 因此 \(\tfrac12 T_2^2=1-x-s\)。
- 相加：\(x+\tfrac12 T_2^2=x+(1-x-s)=1-s=T_2\)。两边相等，验证通过。♦
这里 \((2n-3)!!=1\cdot 3\cdot 5\cdots(2n-3)\) 是“双阶乘”（约定 \((-1)!!=1\)）。例如 \(t_{2,3}=3!!=3\)，正好对应图 5.44 中的三棵树。
为此，我们首先定义幂级数的复合逆（compositional inverse）这一概念。
定义 5.58（复合逆） 设 \(F(x)\) 是一个形式幂级数（formal power series）。若形式幂级数 \(G(x)\) 满足 \(F(G(x))=G(F(x))=x\)，则称 \(G(x)\) 是 \(F(x)\) 的复合逆。此时记 \(F^{\langle-1\rangle}(x)=G(x)\)。
例 5.59 若 \(F(x)=3x+2\)，则 \(F^{\langle-1\rangle}(x)=(x-2)/3\)。
解：确实，\(F\!\left(\dfrac{x-2}{3}\right)=\left(x-2\right)+2=x\)。同样地，\(F^{\langle-1\rangle}(3x+2)=3x/3=x\)。♦
注意：要使形式幂级数的复合 \(F(G(x))\) 与 \(G(F(x))\) 有定义，只需假设 \(F\) 与 \(G\) 的常数项都为 \(0\)。在下文中，我们将处理满足这一条件的形式幂级数。我们要指出：若 \(F\) 有无穷多个非零系数，而 \(G\) 有非零常数项，则 \(F(G(x))\) 没有定义。
为什么常数项要为 0计算 \(F(G(x))\) 时，要把 \(G(x)\) 代进 \(F\) 的每一项 \(f_i x^i\) 得到 \(f_i\,G(x)^i\) 再相加。如果 \(G\) 有非零常数项 \(g_0\)，那么 \(G(x)^i\) 的常数项是 \(g_0^i\)；当 \(F\) 有无穷多项时，最终 \(x^0\) 的系数会是无穷级数 \(\sum_i f_i g_0^i\)，可能根本不收敛、无法写成形式幂级数。把常数项设为 \(0\) 就避免了这种“无穷次相加”的麻烦。
例 5.60 若 \(F(x)=\sum_{n\ge 1}x^n=x/(1-x)\)，则 \(F^{\langle-1\rangle}(x)=\sum_{n\ge 0}(-1)^{n-1}x^n=x/(1+x)\)。
解：我们有
\[\tag{5.18}F\!\left(\frac{x}{1+x}\right)=\frac{x/(1+x)}{1-[x/(1+x)]}=\frac{x}{1+x-x}=x.\]♦
例 5.61 若 \(F(x)=\ln(1+x)\)，则 \(F^{\langle-1\rangle}(x)=\mathrm{e}^x-1\)。
讲解：验证只需注意 \(F(\mathrm{e}^x-1)=\ln\big(1+(\mathrm{e}^x-1)\big)=\ln(\mathrm{e}^x)=x\)；反过来 \(F^{\langle-1\rangle}(\ln(1+x))=\mathrm{e}^{\ln(1+x)}-1=(1+x)-1=x\)。可见 \(\ln(1+x)\) 与 \(\mathrm{e}^x-1\) 互为复合逆——它们都以 \(0\) 为常数项。
复合逆 \(F^{\langle-1\rangle}\) 的作用就是“撤销” \(F\) 的作用：两者依次复合得到恒等映射 \(x\mapsto x\)。
下面这条引理表明，对于以 \(0\) 为常数项的幂级数，判断其逆是否存在非常容易。
引理 5.62 设 \(F(x)=f_1x+f_2x^2+\cdots\) 是形式幂级数。则 \(F^{\langle-1\rangle}(x)\) 存在当且仅当 \(f_1\neq 0\)。在此情形下，\(F^{\langle-1\rangle}(x)\) 唯一。
证明. 若 \(f_1=0\)，则 \(G(F(x))\) 的一次项系数将为 \(0\)，于是 \(G(F(x))\neq x\)。现在假设 \(f_1\neq 0\)。我们来看能否找到幂级数 \(G(x)=\sum_{n\ge 1}g_nx^n\) 使得 \(G(F(x))=x\)。（请读者自行验证：这样的幂级数 \(G(x)\) 必有 \(0\) 常数项。）令 \(G(F(x))\) 与 \(x\) 中 \(x^n\)（\(n=1,2,3,\cdots\)）的系数相等，由
\[G(F(x))=g_1F(x)+g_2F^2(x)+g_3F^3(x)+\cdots,\]
可知 \(G(F(x))=x\) 当且仅当
\[\begin{aligned}
g_1f_1&=1,\\
g_1f_2+g_2f_1^2&=0,\\
g_1f_3+g_2f_1f_2+g_3f_1^3&=0,
\end{aligned}\]
依此类推。由于 \(f_1\neq 0\)，可由第一式解出 \(g_1\)。此后，可由第二式解出 \(g_2\)，由第三式解出 \(g_3\)，如此继续。永远不会遇到除以 \(0\) 的问题，因为在上面数组的第 \(n\) 个方程中，\(g_n\) 的系数总是 \(f_1^n\neq 0\)。♦
把引理 5.62 的证明拆成最小步子：
- 必要性（\(f_1=0\) 不行）：\(G(F(x))\) 的最低次项来自 \(g_1F(x)\)，其一次项系数是 \(g_1f_1\)。若 \(f_1=0\)，这一项就消失，无法凑出 \(x\) 的一次项，故无逆。
- 充分性（\(f_1\neq 0\) 可行）：把 \(G(F(x))=x\) 按 \(x\) 的幂逐次比较系数，得到一串方程，第 \(n\) 个方程形如“\(f_1^n\,g_n + (\text{只含 }g_1,\dots,g_{n-1}\text{ 的已知量})=0\)”。
- 逐个求解：第 \(1\) 个方程定出 \(g_1=1/f_1\)；代入第 \(2\) 个定出 \(g_2\)；再代入第 \(3\) 个定出 \(g_3\)……每一步只需除以 \(f_1^n\neq 0\)。
- 唯一性：每个 \(g_n\) 都被前面的量唯一确定，没有选择余地，所以逆唯一。♦
一个形式洛朗级数（formal Laurent series）是只含有限多个负指数的幂级数。也就是说，复系数的形式洛朗级数形如 \(\sum_{i\ge m}a_ix^i\)，其中 \(m\in\mathbb{Z}\)。现在我们可以陈述并证明本节的主要结果了。
定理 5.63（拉格朗日反演公式） 设 \(n\) 与 \(\ell\) 为正整数，并设 \(F^{\langle-1\rangle}(x)\) 是幂级数 \(F(x)=\sum_{i\ge 1}f_ix^i\) 的复合逆。则
\[\tag{5.19} n\,[x^n]\big(F^{\langle-1\rangle}(x)\big)^\ell=\ell\,[x^{n-\ell}]\left(\frac{x}{F(x)}\right)^n.\]
注意，特别地，\(\ell=1\) 的情形给出 \(F^{\langle-1\rangle}(x)\) 的系数。这是拉格朗日反演公式最常用的特例。下面的证明出自约瑟夫–路易·拉格朗日（Joseph-Louis Lagrange）本人。有兴趣的读者可参阅 [72] 的第 5 章以了解更多证法。
符号说明：\([x^n]\) 是什么意思记号 \([x^n]A(x)\) 表示幂级数 \(A(x)\) 中 \(x^n\) 项的系数。例如 \([x^2](1+3x+5x^2+\cdots)=5\)。公式 (5.19) 的妙处在于：左边是未知级数 \(F^{\langle-1\rangle}\) 的系数，右边却只用到已知级数 \(F\)——把右边那个分式展开取系数即可，根本不必先解出 \(F^{\langle-1\rangle}\)。
证明. 设
\[\big(F^{\langle-1\rangle}(x)\big)^\ell=\sum_{i\ge\ell}h_ix^i.\]
在上式两边把 \(x\) 替换为 \(F(x)\)（左边因 \(F^{\langle-1\rangle}(F(x))=x\) 而变成 \(x^\ell\)），得到
\[x^\ell=\sum_{i\ge\ell}h_iF(x)^i.\]
注意，最后这个式子含有 \(\big(F^{\langle-1\rangle}(x)\big)^\ell\) 的系数 \(h_i\)，但不含 \(F^{\langle-1\rangle}(x)\) 本身。这是把这些系数用 \(F(x)\) 表示出来的关键一步。
对两边求导，得到
\[\ell x^{\ell-1}=\sum_{i\ge\ell}i\,h_iF(x)^{i-1}F'(x).\]
整理后给出
\[\tag{5.20}\frac{\ell x^{\ell-1}}{F(x)^n}=\sum_{i\ge\ell}i\,h_iF(x)^{i-1-n}F'(x).\]
让我们比较 (5.20) 两边 \(x^{-1}\) 的系数。注意，若 \(i\neq n\)，则
\[F(x)^{i-1-n}F'(x)=\left(\frac{F(x)^{i-n}}{i-n}\right)'.\]
换句话说，当 \(i\neq n\) 时，\(h_iF(x)^{i-1-n}F'(x)\) 是某个洛朗级数导数的常数倍，因而它 \(x^{-1}\) 项的系数为 \(0\)（因为 \(x^{-1}\) 的原函数不是幂函数）。所以，(5.20) 右边唯一对 \(x^{-1}\) 系数有贡献的，是下标 \(i=n\) 的那一项。该系数为
\[[x^{-1}]\,n h_n\,F(x)^{-1}F'(x)=[x^{-1}]\,n h_n\,\frac{f_1+2f_2x+3f_3x^2+\cdots}{f_1x+f_2x^2+\cdots}=[x^{-1}]\,n h_n\left(\frac1x+\cdots\right)=n h_n,\]
这正是 (5.19) 待证的左边（因为 \(h_n=[x^n]\big(F^{\langle-1\rangle}(x)\big)^\ell\)）。
现在回到 (5.20)，注意
\[[x^{-1}]\,\frac{\ell x^{\ell-1}}{F(x)^n}=\ell\,[x^{n-\ell}]\,\frac{x^n}{F(x)^n}=\ell\,[x^{n-\ell}]\left(\frac{x}{F(x)}\right)^n,\]
这正是 (5.19) 的右边。♦
把这条证明的脉络理顺：
- 换元：在 \(\big(F^{\langle-1\rangle}\big)^\ell=\sum h_ix^i\) 中令 \(x\to F(x)\)，左边塌缩成简单的 \(x^\ell\)，于是 \(x^\ell=\sum h_iF^i\)——未知系数 \(h_i\) 被装进了已知的 \(F\) 里。
- 求导：对 \(x^\ell=\sum h_iF^i\) 求导得到 \(\ell x^{\ell-1}=\sum i h_iF^{i-1}F'\)。这是为了凑出 \(F'\)，从而后面能识别出“某个东西的导数”。
- 除以 \(F^n\)：得到 (5.20)。这样做的目的，是让右边出现 \(F^{i-1-n}F'\)。
- 取 \(x^{-1}\) 系数（留数思想）：除 \(i=n\) 外，每一项都是“某洛朗级数的导数”，而导数的 \(x^{-1}\) 系数恒为 \(0\)（\(x^{-1}\) 没有幂函数原函数）。于是只剩 \(i=n\) 一项存活。
- 两边对账：存活项给出左边 \(n h_n\)；把左边的 \(\dfrac{\ell x^{\ell-1}}{F^n}\) 取 \(x^{-1}\) 系数，平移指数即得 \(\ell[x^{n-\ell}](x/F)^n\)。两者相等就是 (5.19)。♦
应用一：回到 \(k\)-系统发生树
现在我们可以回到 \(k\)-系统发生树了。公式 (5.17) 表明 \(F(T_k(x))=x\)，所以 \(T_k(x)=F^{\langle-1\rangle}(x)\)，其中
\[F(x)=x-\frac{x^k}{k!}.\]
因此，我们可以用定理 5.63 计算 \(T_k(x)\) 的系数。该定理给出（对一般的 \(\ell\)，即取 \(T_k(x)\) 的 \(\ell\) 次幂）
\[n\,[x^n]\big(T_k(x)\big)^\ell=\ell\,[x^{n-\ell}]\left(\frac{x}{\,x-\dfrac{x^k}{k!}\,}\right)^n.\]
由此，我们计算
\[\begin{aligned}
[x^n]\big(T_k(x)\big)^\ell
&=\frac{\ell}{n}\,[x^{n-\ell}]\left(1-\frac{x^{k-1}}{k!}\right)^{-n}\\
&=\frac{\ell}{n}\,[x^{n-\ell}]\sum_{s\ge 0}\binom{-n}{s}\left(-\frac{x^{k-1}}{k!}\right)^s\\
&=\frac{\ell}{n}\,[x^{n-\ell}]\sum_{s\ge 0}\binom{n+s-1}{s}\frac{x^{s(k-1)}}{k!^{\,s}}.
\end{aligned}\]
于是，令 \(n-\ell=s(k-1)\)，即 \(n=s(k-1)+\ell\)，上面这串等式蕴含
\[\tag{5.21}[x^n]\big(T_k(x)\big)^\ell=\frac{\ell}{s(k-1)+\ell}\binom{ks+\ell-1}{s}\frac{1}{k!^{\,s}}.\]
特别地，对 \(\ell=1\)，我们得到
\[\tag{5.22}[x^n]T_k(x)=\frac{1}{s(k-1)+1}\binom{ks}{s}\frac{1}{k!^{\,s}}.\]
例：用 (5.22) 数 \(k=2\) 的树 取 \(k=2\)，则 \(n=s(k-1)+1=s+1\)，即 \(s=n-1\)。代入 (5.22)：
\[[x^n]T_2(x)=\frac{1}{(n-1)\cdot 1+1}\binom{2(n-1)}{n-1}\frac{1}{2!^{\,n-1}}=\frac1n\binom{2n-2}{n-1}\frac1{2^{n-1}}.\]
由于 \(T_2\) 是指数型生成函数，\(t_{2,n}=n!\cdot[x^n]T_2(x)\)。代入 \(n=3\)：
\[[x^3]T_2(x)=\frac13\binom{4}{2}\frac1{2^2}=\frac13\cdot 6\cdot\frac14=\frac12,\qquad t_{2,3}=3!\cdot\frac12=3.\]
与图 5.44 的三棵树以及前面 \(t_{2,n}=(2n-3)!!\) 给出的 \(t_{2,3}=3!!=3\) 完全吻合。♦
展开中用到的两件事(1) 广义二项式：\((1-u)^{-n}=\sum_{s\ge0}\binom{-n}{s}(-u)^s=\sum_{s\ge0}\binom{n+s-1}{s}u^s\)，这里用到恒等式 \(\binom{-n}{s}(-1)^s=\binom{n+s-1}{s}\)。(2) 取系数要对齐次数：\(\big(1-x^{k-1}/k!\big)^{-n}\) 里只出现 \(x^{s(k-1)}\) 这种次数，要它等于目标次数 \(n-\ell\)，就必须 \(s(k-1)=n-\ell\)；否则系数为 \(0\)。
上一个例子讲的是非平面树，用的是指数型生成函数。下一个例子表明，拉格朗日反演公式也可用于出现普通生成函数（ordinary generating function）的情形。
例 5.64 在 \(n\) 个顶点上、每个顶点要么有 \(0\) 个孩子、要么有 \(k\) 个孩子的有根平面无标号树（plane rooted unlabeled trees）有多少棵？
解：设 \(U_k(x)\) 是计数这类树的普通生成函数，即 \(U_k(x)=\sum_{n\ge 1}u_{n,k}x^n\)，其中 \(u_{n,k}\) 是 \(n\) 个顶点上这类树的棵数。则
\[\tag{5.23}U_k(x)=x+xU_k(x)^k=x\big(1+U_k(x)^k\big),\]
因为去掉这种多于一个顶点的树的根，会得到一个由 \(k\) 棵同类树组成的序列（即有序的 \(k\) 元组，因为是平面树）。整理 (5.23)，得到
\[\frac{U_k(x)}{1+U_k(x)^k}=x,\]
所以
\[U_k(x)=\left(\frac{x}{1+x^k}\right)^{\langle-1\rangle}.\]
取 \(\ell=1\)，拉格朗日反演公式给出
\[\begin{aligned}
[x^n]U_k(x)
&=\frac1n\,[x^{n-1}]\left(\frac{x}{\,x/(1+x^k)\,}\right)^n
=\frac1n\,[x^{n-1}]\big(1+x^k\big)^n\\
&=\frac1n\,[x^{n-1}]\sum_{s\ge 0}\binom ns x^{ks}
=\frac1n\binom ns\,[x^{n-1}]x^{ks}.
\end{aligned}\]
所以，若 \(n-1\) 不被 \(k\) 整除，则 \(u_{n,k}=0\)；而当 \(n=ks+1\) 时，
\[\tag{5.24}u_{n,k}=\frac1n\binom ns.\]
注意，对 \(k=2\) 而言，这意味着：当 \(n\) 为偶数时不存在这样的树；当 \(n=2m+1\) 时，这样的树有
\[\frac{\binom{2m+1}{m}}{2m+1}=\frac{\binom{2m}{m}}{m+1}\]
棵。请把这个结果与定理 5.28 比较。♦
平面 vs 非平面：为什么一个除 \(k!\)、一个不除系统发生树是非平面的，去根后子树构成无序集合，故 (5.16) 里出现 \(T_k^k/k!\)；而例 5.64 的树是平面的，去根后子树构成有序序列，故 (5.23) 里出现的是 \(U_k^k\)（不除 \(k!\)）。\(k=2\) 时得到的 \(\dfrac{1}{m+1}\binom{2m}{m}\) 正是卡塔兰数（Catalan number）——这与定理 5.28 中由其他途径数出的有根平面二叉树个数一致。
例 5.64 在 \(k=2,\ n=5\) 的具体情形：实心点是有 \(2\) 个孩子的内部顶点，空心点是叶子（\(0\) 个孩子）。因为是平面树，左右有别，恰好 \(2\) 棵——与公式 \(\dfrac{1}{m+1}\binom{2m}{m}=\dfrac13\binom42=2\) 一致。
应用二：有根树的棵数
当我们讨论定理 5.55 时，还无法从等式 \(T(x)=x\mathrm{e}^{T(x)}\) 推导出顶点集 \([n]\) 上全部有根树的棵数公式。现在，有了拉格朗日反演公式，我们可以做到这一点了。
例 5.65 顶点集 \([n]\) 上有根树的棵数是 \(n^{n-1}\)。
解：设 \(t_n\) 为 \(n\) 个顶点上有根树的棵数，\(t_0=0\)，并设 \(T(x)=\sum_{n\ge 1}t_n\dfrac{x^n}{n!}\) 为数列 \(t_n\) 的指数型生成函数。正如我们在定理 5.55 的证明中所提到的，一棵有根树自然地分解为它的根（生成函数为 \(x\)）与一个有根树的集合（生成函数为 \(\mathrm{e}^{T(x)}\)）。因此，乘积公式（Product Formula）给出
\[\tag{5.25}T(x)=x\mathrm{e}^{T(x)}.\]
所以 \(T(x)/\mathrm{e}^{T(x)}=x\)，从而
\[T(x)=\left(\frac{x}{\mathrm{e}^x}\right)^{\langle-1\rangle}.\]
取 \(\ell=1\)，拉格朗日反演公式给出
\[\begin{aligned}
[x^n]T(x)
&=\frac1n\,[x^{n-1}]\,\mathrm{e}^{nx}
=\frac1n\,[x^{n-1}]\sum_{m\ge 0}\frac{(nx)^m}{m!}\\
&=\frac1n\cdot\frac{n^{\,n-1}}{(n-1)!}
=\frac1n\cdot\frac{n^{\,n}}{n!}
=\frac{n^{\,n-1}}{n!}.
\end{aligned}\]
所以 \(t_n=n!\cdot[x^n]T(x)=n^{n-1}\)，正如所断言。♦
数字验证 \(n=3\) 公式说 \([3]\) 上有根树共 \(3^{3-1}=9\) 棵。我们直接数：先选无标号的有根树形（\(3\) 个顶点的有根树只有两种树形——“一条链”和“根带两个孩子”），再把标号 \(1,2,3\) 分配上去。
- 树形一：根带两个孩子（根在上，两叶子在下）。两个孩子无序，所以只需选哪个标号当根：\(3\) 种（根为 \(1\)、\(2\) 或 \(3\)）。
- 树形二：一条链（根—中—叶）。三个位置各不相同，是 \(3\) 个标号的全排列：\(3!=6\) 种。
- 两类不相交，合计 \(3+6=9\) 棵，正好 \(=3^{2}\)。♦
这步“取系数”为什么这么顺关键是 \(\left(\dfrac{x}{x/\mathrm{e}^x}\right)^n=(\mathrm{e}^x)^n=\mathrm{e}^{nx}\)，把复杂的复合逆问题化成了对指数函数取系数。而 \([x^{n-1}]\mathrm{e}^{nx}=\dfrac{n^{n-1}}{(n-1)!}\)，因为 \(\mathrm{e}^{nx}=\sum_m \dfrac{n^m}{m!}x^m\)，取 \(m=n-1\) 即可。这正体现了拉格朗日反演公式的威力：方程 \(T=x\mathrm{e}^T\) 解不出，但 \(T\) 的系数照样能算。
本节末的“即时自测”练习第 1、2 题，以及补充练习第 39 题，涵盖了 \(\ell>1\) 时拉格朗日反演公式的应用。
即时自测
- 用拉格朗日反演公式计算顶点集 \([n]\) 上、恰有两个连通分支的有根非平面森林的个数。
- 设 \(k\ge 2\) 为固定整数。用拉格朗日反演公式计算这样的有序对的个数：每一对由两棵“每个顶点要么有 \(k\) 个孩子、要么有 \(0\) 个孩子”的有根平面无标号树组成。
- 证明下述命题与拉格朗日反演公式等价：若 \(x=f(x)/G(f(x))\)，其中 \(G\) 是常数项非零的形式幂级数，而 \(f\) 是常数项为零的形式幂级数，则
\[\tag{5.26}n\,[x^n]f(x)^k=k\,[x^{n-k}]G(x)^n.\]
返回 全书目录