P6598 烷烃计数题解

0x00 有机物

不会化学？没关系哦你只需要知道：

键：链接两个原子的东西，对应 OI 中的边。XY 键就是连接 X 原子和 Y 原子的键，可以同时链几根键，变成 XY 双键、三键等。
碳原子：必须要连 $4$ 根键，不能连自己但是两个碳原子可以连多根键。
氢原子：只能连 $1$ 根键。
烷烃：每个碳原子都连了 $4$ 根键，所有的碳碳都是单键。实际上有环的也叫烷烃，但是这次我们只考虑链状烷烃，形态是 OI 里面的一棵树，那么烷烃的通式为 $C_{n}H_{2n+2}$ 。
烷基：去掉一个碳的一个氢原子，烷基的通式为 $C_{n}H_{2n+1}$ 。
烯烃：有一个碳碳双键，这两个碳原子又分别链接了两个烷基。
同分异构体：有相同分子式，但是结构不同的有机物，对应 OI 中的无标号树同构问题。

想一下去掉了一个氢原子的那个碳给我们带来了什么？答案是，把一个无根树变成一个有根树。我们把这个有机物从这个没连接的碳键拎起来，那么这个无根树就变成了每个非叶子点都链接了三个儿子。

设 $F(x)$ 是答案的生成函数，考虑每次把三个儿子填进去的方案数，要考虑是否同构所以用 Burnside 引理。枚举 $6$ 种置换：

全部加起来取平均数：

F(x)=\frac{x}{6}(F^3(x)+3F(x^2)F(x)+2F(x^3))+1

使用牛顿迭代求解，首先令

G(x,F(x))=F(x)-\frac{x}{6}(F^3(x)+3F(x^2)F(x)+2F(x^3))-1

那么已知 $G(x,F(x))\equiv 0 \pmod{x^n}$ ，那么可知：

F_1=F(x)-\frac{G(x,F(x))}{\frac{\partial G}{\partial F(x)}G(x,F(x))} \bmod{x^{2n}}

注意这里的求导是形势求导，把 $F(x)$ 当做变量求导， $F^3(x),F(x^2),F(x^3)$ 都当做常量，整理一下：

\begin{align*} F_1&=F(x)-\frac{F(x)-\frac{x}{6}(F^3(x)+3F(x^2)F(x)+2F(x^3))-1}{1-\frac{x}{6}(3F^2(x)+3F(x^2))}\\ &=\frac{F(x)-\frac{x}{6}(3F^3(x)+3F(x^2)F(x))-F(x)+\frac{x}{6}(F^3(x)+3F(x^2)F(x)+2F(x^3))+1}{1-\frac{x}{6}(3F^2(x)+3F(x^2))}\\ &=\frac{1-\frac{x}{3}(F^3(x)-F(x^3))}{1-\frac{x}{2}(F^2(x)+F(x^2))} \end{align*}

倍增迭代即可得到烷基计数的生成函数，我们记为 $A(x)$ 。

从碳碳双键的地方把这个有机物拎起来，那么这两个碳原子再链接两个烷基就行，先用 Burnside 引理对一个碳原子进行计数：

F(x)=x\frac{A^2(x)+A(x^2)}{2}

继续用 Burnside 引理对两个碳原子进行计数：

G(x)=\frac{F^2(x)+F(x^2)}{2}

得到答案。

把重心钦定为根变成一个有根树。实际上这里已经可以通过容斥方法，暴力卷一个式子来做了，但是这样太不优雅了，而且不能求出烷烃计数的生成函数。

烷烃是无根树怎么办，考虑把未知化为已知，强制钦定某一个点为根，那么就只需要考虑树上点的等价类就行，而点等价类就是有根数的计数，然后发现重心这个点很特殊，分类讨论一下：

只有一个重心：首先重心不与其他任何一个点等价，那么两个点等价意味着两个点的父亲边（以重心为根）等价，因为以这个点为根的有根树，到大小大于 $\frac{n}{2}$ 儿子的边是唯一的。设点等价类数量为 $p$ ，边等价类数量为 $q$ ，那么 $p-q=1$ 。
有两个重心，两个重心不等价：同理可得 $p-q=1$ 。
两个重心等价： $p-q=0$ 。

那么对于一棵树计算 $p,q,s$ ，当有两个重心，且两个重心等价时 $s=1$ ，否则 $s=0$ ，对于任意一棵树有 $p-q+s=1$ 恒等式。对三个部分分别生成函数 $P,Q,S$ 。

点等价就是根上加 $4$ 个烷基儿子，使用 Burnside 引理进行计数 $P(x)$ ：

P(x)=x\frac{A^4(x)+6A(x^2)A^2(x)+3A(x^2)^2+8A(x^3)A(x)+6A(x^4)}{24}

边等价就是两个烷基连起来，并且不能是单个氢原子，继续 Burnside：

Q(x)=\frac{(A(x)-1)^2+A(x^2)-1}{2}

然后是重心等价，就是相同的两个烷基连起来：

S(x)=A(x^2)

那么 $P-Q+S$ 就是烷烃计数的生成函数。