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

如果有 \(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))\)

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