「营业日志 2020.11.30」连通图的一个内卷方程的代数解释
Elegia
·
·
个人记录
今有 uoj 群友提及这样一个连通图的方程：
n\ge 2, \quad f_n = \sum_k \binom{n-2}{k-1} f_kf_{n-k} (2^k-1)
其组合意义是考虑删去 2 号点后，1 号点所在连通块大小为 k，再考虑去掉这个连通块之后剩下的连通块必然只有 2 号点向其连边。
考虑图的方程 \displaystyle G(x) = \sum_{n\ge 0} 2^{\binom n 2} \frac{x^n}{n!}，注意到有
\begin{aligned}
G'(x)& = \sum_{n\ge 0} 2^{\binom {n+1} 2} \frac{x^n}{n!}\\
&=\sum_{n\ge 0} 2^{\binom n 2} \frac{(2x)^n}{n!}\\
&= G(2x)
\end{aligned}
这种 G'=G(2x) 的形式，问了问懂行的人表示它属于延迟微分方程的范畴，暂不清楚能否有所应用，但是我们接下来需要熟用这一等式来完成推导。根据 F = \ln G，我们开始进行运算：
\begin{aligned}
G &= \mathrm{e}^F\\
G' &= \mathrm{e}^F F'\\
&= G F'\\
G'' &= G'F'+GF''\\
&= GF'^2+GF''\\
F'' &= \frac{G''}G - F'^2\\
&= \frac{2G'(2x)}G - F'^2\\
&= \frac {2G(2x)F'(2x)}G - F'^2\\
&= \frac{2G'F'(2x)}G - F'^2\\
&= F'(2F'(2x)-F')
\end{aligned}
不难验证最终式子与对应的递推式等价。