拉格朗日反演及扩展拉格朗日反演

如果有 \(F(G(x))=x\)，即 \(F,G\) 互为复合逆，同时一定有 \(G(F(x))=x\)，可以称 \(G(x)=F^{-1}(x),F(x)=G^{-1}(x)\)。

在这种情况下，有这样的式子：

拉格朗日反演

\[[x^n]F(x)=\frac{1}{n}[x^{-1}](\frac{1}{G(x)})^n=\frac{1}{n}[x^{n-1}](\frac{x}{G(x)})^n \]

扩展拉格朗日反演

\[[x^n]H(F(x))=\frac{1}{n}[x^{-1}]H'(x)(\frac{1}{G(x)})^n=\frac{1}{n}[x^{n-1}]H'(x)(\frac{x}{G(x)})^n \]

 
 

大朋友和多叉树

设 \(F(x)\) 为答案的普通生成函数，那么有

\[F(x)=x+\sum \limits_{i=0}^{\infty}[i \in D] F^i(x) \]
\[x=F(x)-\sum \limits_{i=0}^{\infty}[i \in D] F^i(x) \]

这样的话就构造出了 \(G(x)=F^{-1}(x)=x-\sum \limits_{i=0}^{\infty}[i \in D]x^i\)。

对 \(G\) 进行拉格朗日反演即可求出 \(F\)。

注意要求的是 \((\frac{x}{G(x)})^n\)，然而 \(G(x)\) 常数项一定为 \(0\)。

解决方法很简单，把式子化成 \((\cfrac{1}{\frac{G(x)}{x}})^n\) 即可。
 

边双图计数

首先一般图的指数生成函数为 \(H(x)=\sum \limits_{i=0}^\infty 2^{\binom{i}{2}}\frac{x^i}{i!}\)。

可以求出一般连通图的指数生成函数 \(P(x)\)，\(e^{P(x)}=H(x),P(x)=\ln H(x)\)。

给 \(P(x)\) 的第 \(i\) 项系数乘上 \(i\)，即可得到有根一般连通图的指数生成函数 \(D(x)\)。

设有根边双图的生成函数为 \(B(x)\)，考虑枚举一般图中根所在的边双大小，接着把有根连通图挂在边双上的点上，那么有：

\[D(x)=\sum \limits_{i=1}^\infty b_ie^{iD(x)}\frac{x^i}{i!} \]
\[D(x)=\sum \limits_{i=1}^\infty b_i\frac{(xe^{D(x)})^i}{i!}=B(xe^{D(x)}) \]

令 \(C(x)=xe^{D(x)}\)，可得 \(D(x)=B(C(x))\)。

对 \(C(x)\) 取复合逆，可得 \(B(x)=D(C^{-1}(x))\)。

然后直接扩展拉格朗日反演冲上去：

\[[x^n]B(x)=[x^n]D(C^{-1}(x))=\frac{1}{n}[x^{n-1}]D'(x)(\frac{x}{C(x)})^n=\frac{1}{n}[x^{n-1}]D'(x)e^{-nD(x)} \]

 

点双图计数

同上题可以求出 \(D(x)\)。

设无根点双图的生成函数为 \(B(x)\)，考虑一般图中根所在若干个无关的点双，可以直接 \(\exp\) 起来，所以只需要考虑每个点双的生成函数。

对于每个点双，只要枚举大小然后在点双的每个点上挂一个有根连通图即可。

所以每个点双大概是这样的 \(\sum \limits_{i=1}^{\infty}b_{i+1}\frac{D^i(x)}{i!}\)。

可以给 \(B\) 左移一位，使书写方便一些，有 \(D(x)=xe^{B(D(x))}\)。

这里用的点双生成函数是无根的，大概是因为这样就可以直接钦定编号最小的点是根节点，不去给根节点分配编号同时还保证用到的方案数是正确的。

对式子同取 \(\ln\)，可得 \(\ln \frac{D(x)}{x}=B(D(x))\)。

用 \(D^{-1}(x)\) 替换掉 \(x\)，可得 \(\ln \frac{x}{D^{-1}(x)}=B(x)\)。

构造 \(H(x)\) 为 \(\ln \frac{D(x)}{x}\) 即可发现要求的就是 \(B(x)=H(D^{-1}(x))\)。

仍然是套一个扩展拉格朗日反演即可解决。