拉格朗日反演

· · 算法·理论

::::info[广] 所有人都应该去玩《东方冰之勇者记》！

我太菜了全避不了，只能无伤了。 ::::

突然意识到自己快退役了。稍微放纵一下学些自己想学的。

参考资料：

https://www.cnblogs.com/gsjz/p/16187813.html

https://www.luogu.com.cn/article/qqwukp35

https://xyix.github.io/posts/?searchfor=%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5&postname=lagrange-inv-bij

https://x-yi-x.blog.uoj.ac/blog/6511

index-0：基础

首先是建立函数复合理论。千万别想当然。

注意不是所有函数都可以复合的，譬如常函数 I=\sum x^k=\frac{1}{1-x}，I \circ I 是什么呢？

理论上来说是 \frac{1}{1-\frac{1}{1-x}}=1-\frac{1}{x}。但你转念一想，什么牛鬼蛇神的生成函数是 \frac{1}{x}？它都不能在 0 点泰勒展开。

研究一下常系数就发现端倪了：[x^0]I \circ I(x)=[x^0]\sum_{k=0}^{\infty}I^k(x)=\sum_{k=0}^{\infty}1。

这玩意发散的你算个集贸啊。

反过来不难证明，内部函数常系数为 0 的系数就不会发散。

继续探讨复合逆。

诚然，常系数非 0 也可能有复合逆（x+1 和 x-1），但没有普适性，复合的时候需要时刻保证不发散。故接下来我们只研究常系数为 0 的幂级数。

关于复合逆：F(G(x))=x，由于函数复合有结合律，假设 H(F(x))=x，那么有 H=H\circ F\circ G=G，所以复合逆同时是左逆和右逆。

注意 F 有逆还得满足一次项非 0，不然显然复合不出一个 x 来。

index-1：分式域

简单来说，定义分式域的幂级数 $H(x)=\frac{F(x)}{G(x)}$，上下各为整式。好像叫形式洛朗级数，太难打了算了。 虽然分式无法展开，但可以作为计算中间商，表示方便。 一般负指数有限的分式可以写作 $H(x)=x^{-n}\sum_{i=0}^{\infty}h_{i-n}x^{i}$。 其中 $n$ 是最小负指数的相反数。如此一来计算规则也和整数一样了。 基于上述式子的分式计算与整式无异。 --- 分式也可以求导。一个好玩的点是 $(a_0x^0)'=0$，即 $[x^{-1}]F'(x)=0$ 对任一分式成立。 对这个特殊的系数 $[x^{-1}]$ 称作**形式留数**。 --- 考虑一个最低次为 $1$ 的 $F$，满足 $$ [x^{-1}]F'F^{k}(x)=[k=-1] $$ 称其为**判别式**。 这个比较好证，$k\ne -1$ 时就是求导所以形式留数是 $0$。 $k=-1$ 时相当于说 $\frac{F'(x)}{F(x)}=\frac{A(x)+xA'(x)}{xA(x)}=\frac{1}{x}+\frac{A'(x)}{A(x)}

注意后者 [x^0] 系数不为 0，故是整式，提取 [x^{-1}] 就是 0，而前者是 1，加起来就是 1。

index-2：拉格朗日反演

n[x^n]F^k(x)=k[x^{-k}](G(x))^{-n}

其中 F 最低次 1，F,G 互为复合逆。

为了防止推导过程中复合与乘法容易看混，复合部分统一写作 \circ。

证明考虑：

(F\circ G)(x)=x \Rightarrow (F^k\circ G)(x)=x^k

导之。

对函数的求导我都会写在函数上。

\begin{aligned} G'(x)((F^k)'\circ G)(x)&=kx^{k-1} \\ \sum_{i=0}^{\infty}i([x^i]F^k(x))(G^{i-1}(x)G'(x))&=kx^{k-1} \end{aligned}

结合判别式，考虑形式留数。

定理要提取 n 次项，两边同乘 G^{-n}(x) 即可。

\begin{aligned} \sum_{i=0}^{\infty}i([x^i]F^k(x))(G^{i-n-1}(x)G'(x))&=kx^{k-1}G^{-n}(x) \\ \sum_{i=0}^{\infty}i([x^i]F^k(x))[x^{-1}](G^{i-n-1}(x)G'(x))&=[x^{-1}]kx^{k-1}G^{-n}(x) \\ n[x^n]F^k(x)&=k[x^{-k}]G^{-n}(x) \end{aligned}

于是我们有拉格朗日反演：

n[x^n]F^k(x)=k[x^{-k}]G^{-n}(x)

为便于区分，我们简称拉反之一。

对不同幂次求和。

\begin{aligned} \sum_{k=0}^{\infty}h_k n[x^n]F^k(x)&=\sum_{k=0}^{\infty}h_k k[x^{-k}]G^{-n}(x) \\ n[x^n]H(F(x))&=\sum_{k=0}^{\infty}h_k k[x^{n-k}](\frac{x}{G(x)})^{n} \\ n[x^n]H(F(x))&=[x^{n-1}](\sum_{k=0}^{\infty}h_k kx^{k-1})(\frac{x}{G(x)})^{n} \\ [x^n]H(F(x))&=\frac{1}{n}[x^{n-1}]H'(x)(\frac{x}{G(x)})^n \end{aligned}

此为拉反之二。

这个是比较常用的式子。

譬如 v=u\Phi(v) 时，将 G(v)=\frac{v}{\Phi(v)},F(u)=v，就有

[u^n]H(v)=\frac{1}{n}[v^{n-1}]H'(v)\Phi^n(v)

可以用来提取某些系数。

从拉反之一换个方式推导。

\begin{aligned} n[x^n]F^k(x)&=k[x^{-k}]G^{-n}(x) \\ [x^n]F^k(x)&=-\frac{1}{n}[x^{-k-1}](G^{-n})'(x) \\ [x^n]F^k(x)&=[x^{-k-1}]G'(x)G^{-n-1}(x) \end{aligned}

此为拉反之三。

同理尝试对其不同次幂求和。

\begin{aligned} \sum_{k=0}^{\infty}h_k[x^n]F^k(x)&=\sum_{k=0}^{\infty}h_k[x^{-k-1}]G'(x)G^{-n-1}(x) \\ [x^n]H(F(x))&=\sum_{k=0}^{\infty}h_k[x^{-k-1}]G'(x)x^{-n-1}(\frac{x}{G(x)})^{n+1} \\ [x^n]H(F(x))&=[x^n]H(x)G'(x)(\frac{x}{G(x)})^{n+1} \end{aligned}

此为拉反之四。

这个看着也比较能用。

综上推完了四种拉反形式，其中二四较为通用，值得记忆。

求复合逆有个小技巧：在 F(x) 的通项式中，将 F(x) 替换为 x，x 替换为 G(x)。

如果不考虑多项式的话，拉反更多的作用就是提取系数了。具体应用后面说，接下来咱搞个喜闻乐见的东西。

index-3：拉格朗日反演的组合意义

叉义叉老师强得可怕。

从这里大致可以窥探出一些拉反的形式。

考虑这样一个式子：f,g 是关于 x 的形式幂级数，且 f=xg(f)，则

[x^n]f^k=\frac{k}{n}[x^{n-k}]g^n

用之前的拉反之一容易证明。

先给出左式的组合意义。

观察 f=xg(f)，这种自递归的形式容易想到树。

用组合类描述一下。一个树的大小定义为节点个数，g 的作用类似一种 \text{SEQ} 构造，只是转移中带和儿子个数有关的系数。

故可以诠释组合意义为：

由 0 到 n 组成的树，定义 d_u 为以 0 为根时 u 的儿子数。

一棵树的权值是所有节点权值积，左式就是所有合法的树的权值和。 值得一提的是这里的树儿子顺序是要区分的。 然后考虑右式的组合意义。 这个看着是线性的，用序列描述。 $[x^{n-k}]g^n$ 可以描述成长为 $n$ 的非负整数序列，且总和为 $n-k$，一个序列 $c_i$ 权值定义为 $\prod [x^{c_i}]g$，所有合法序列的权值和。 将树映射到序列上，容易往 prufer 序列的方向想。 直接令 $c_i+1$ 是度数序列，由 prufer 序列有标号无根树数量 $\binom{n-1}{k-1,c_1,c_2,...}$。 最终式子要区分儿子顺序，所以下面还有乘阶乘。 最终得出其对应的值应该是 $(n-1)!k=\frac{k}{n}n!$。发现左式乘上 $n!$ 即为区分儿子顺序的有标号树权值和，立即得证。 对所有指数求和得到一般形式： $$ [x^n]h(f)=\frac{1}{n}[x^{n-1}]h'g^n $$ 综上可以看出，拉反和 prufer 计树原理本质一样。 # index-4：拉格朗日反演的解析证明 你觉得我会？ [仙人指路](https://www.luogu.com.cn/article/nn4kvg8x)。 # index-5：多元拉格朗日反演 我的数学功底不支持我抵达这里。 [组合证明](https://x-yi-x.blog.uoj.ac/blog/6511)。 [解析证明](https://www.luogu.com.cn/article/nn4kvg8x)。 相信你们能学会。 # index-6：习题 从参考资料里爬的。**保证不含多项式科技**。 ## [P2767 树的数量](https://www.luogu.com.cn/problem/P2767) 题意： > $n$ 个点的无标号**区分子树顺序** $k$ 叉树（儿子数不过 $k$）计数。 什么 dp 我不懂，菜就用菜的方法。 组合对象的大小就是点数。组合类为 $f$ 的话，容易写出 $$ f=x(1+f)^k $$ 这玩意不好解方程，考虑直接拉反提取系数。 $$ [x^n]f=\frac{1}{n}[x^{n-1}]\Phi^n(x) $$ 其中 $\Phi(x)=(1+x)^k$。 得到： $$ \begin{aligned} [x^n]f&=\frac{1}{n}[x^{n-1}](1+x)^{kn} \\ &=\frac{1}{n}[x^{n-1}]\sum_{i=0}^{kn}\binom{kn}{i}x^{i} \\ &=\frac{1}{n}\binom{nk}{n-1} \end{aligned} $$ ## [P3978 [TJOI2015] 概率论](https://www.luogu.com.cn/problem/P3978) 题意： > $n$ 个点的无标号**区分子树顺序** $2$ 叉树叶子数期望。 什么组合意义我不懂，菜就用菜的方法。 你怎么知道我刚才瞎推一通才意识到这题既要记节点数又要记叶子数。 刚才那道题给出了大小为 $n$ 的总方案是 $\frac{1}{n}\binom{2n}{n-1}$，我们只需要求叶子数。 学会使用形式变元。$x^iy^j$ 表示大小为 $i$、叶子数为 $j$ 的子树。方案记作 $f$。 $$ f=x(f^2+2f+y) $$ 实际要求 $\sum_{j=0}^{\infty}j[x^ny^j]f(x,y)$，相当于 $[x^n](\frac{\partial f}{\partial y}f)(x,1)$，就是在 $y$ 上导一下取 $y=1$。 提取 $x^n$ 项的系数。 $$ \begin{aligned} [x^n]f&=\frac{1}{n}[x^{n-1}](x^2+2x+y)^{n} \\ \left. [x^n]\frac{\partial f}{\partial y}\right|_{t=1}&=[x^{n-1}](x+1)^{2n-2} \\ &=\binom{2n-2}{n-1} \end{aligned} $$ 于是答案就是 $$ \frac{\binom{2n-2}{n-1}}{\frac{1}{n}\binom{2n}{n-1}}=\frac{n(n+1)}{2(2n-1)} $$ 由此看出拉反在消除形式变元上的作用。 ## 一个练习 $$ \frac{1}{\sqrt{1-4x}}(\frac{1-\sqrt{1-4x}}{2x})^{m}=\sum_{n=0}^{\infty}\binom{m+2n}{n}x^n $$ 别用卡特兰数去推，太恶心了。 考虑前面用过的 $F=x(1+F)^2 \Rightarrow \frac{1-2x-\sqrt{1-4x}}{2x}$，改写为： $$ \frac{1}{\sqrt{1-4x}}(\frac{1-\sqrt{1-4x}}{2x})^{m}=\frac{1}{\sqrt{1-4\frac{F}{(1+F)^2}}}(1+F)^m=\frac{(1+F)^{m+1}}{1-F} $$ ~~好漂亮天哪真漂亮是啊这也太漂亮了。~~ 为了避免复杂求导我们使用拉反之四。 $$ \begin{aligned} [x^n]\frac{(1+F)^{m+1}}{1-F}&=[x^n]\frac{(1+x)^{m+1}}{1-x}(\frac{x}{(1+x)^2})'(1+x)^{2n+2} \\ &=[x^n]\frac{(1+x)^{m+1}}{1-x}\frac{1-x}{(1+x)^{3}}(1+x)^{2n+2} \\ &=[x^n](1+x)^{m+2n} \\ &=\binom{m+2n}{n} \end{aligned} $$ 确实比较方便蛤。 ## [P7592 数树（2021 CoE-II E）](https://www.luogu.com.cn/problem/P7592) 题意： > 一棵有根有序无标号树合法当且仅当每个点儿子数量 $\in \{0,k_1,k_2\}$。 > $k_1$ 个儿子的点点权为 $a$，$k_2$ 个儿子的点点权为 $b$。 > 树权值是点权和。 > 求树权期望。 分两部分：求多少棵树合法，求总权值。前者容易先求前者。 $$ F=x(1+F^{k_1}+F^{k_2}) $$ 感觉已经不需要推导了…… $$ \begin{aligned} [x^n]F&=\frac{1}{n}[x^{n-1}](1+x^{k_1}+x^{k_2})^{n} \\ &=\frac{1}{n}[x^{n-1}]\sum_{i+j\le n}\binom{n}{i,j,n-i-j}x^{k_1i+k_2j} \end{aligned} $$ 提取 $k_1i+k_2j=n-1$ 的项即可。 然后求总权值。$y$ 表示 $k_1$ 的占位元，$z$ 表示 $k_2$ 的占位元。 $$ G=x(1+yF^{k_1}+zF^{k_2}) $$ 同样提取。 $$ [x^n]G=\frac{1}{n}[x^{n-1}]\sum_{i+j\le n}\binom{n}{i,j,n-i-j}y^{i}z^{j}x^{k_1i+k_2j} $$ 其实不需要那么复杂了。既然可以 $O(n)$ 枚举直接计算即可。 ## [AT_wtf22_day2_d Cat Jumps](https://www.luogu.com.cn/problem/AT_wtf22_day2_d) [敬请参阅](https://www.luogu.com.cn/article/2p7idegr)。 组合意义天地灭，代数推导保平安！ 经典组合意义推导好题的代数解法。 想了想反正我来也是抄一遍写得也没有世界机器大神那么好你们就自己看吧（