Loading... ## 0x00 有机物 不会化学？没关系哦，我也不会。本人在化学月考和期中考试中分别获得了 37/100 和 61/100 的成绩。你只需要知道： 1. 键：链接两个原子的东西，对应 OI 中的边。XY 键就是连接 X 原子和 Y 原子的键，可以同时链几根键，变成 XY 双键、三键等。 2. 碳原子：必须要连 4 根键，不能连自己但是两个碳原子可以连多根键。 3. 氢原子：只能连 1 根键。 4. 烷烃：每个碳原子都连了 4 根键，所有的碳碳都是单键。实际上有环的也叫烷烃，但是这次我们只考虑链状烷烃，形态是 OI 里面的一棵树，那么烷烃的通式为 $C_{n}H_{2n+2}$。 5. 烷基：去掉一个碳的一个氢原子，烷基的通式为 $C_{n}H_{2n+1}$。 6. 烯烃：有一个碳碳双键，这两个碳原子又分别链接了两个烷基。 7. 同分异构体：有相同分子式，但是结构不同的有机物，对应 OI 中的无标号树同构问题。 ## 0x01 烷基计数 想一下去掉了一个氢原子的那个碳给我们带来了什么？答案是，把一个无根树变成一个有根树。我们把这个有机物从这个没连接的碳键拎起来，那么这个无根树就变成了每个非叶子点都链接了三个儿子。 设 $F(x)$ 是答案的生成函数，考虑每次把三个儿子填进去的方案数，要考虑是否同构所以用 Burnside 引理。枚举 6 种置换： 1. $(1,2,3)$：三个置换环，三个都任意，答案 $xF^3(x)+1$。 2. $(1,3,2),(2,1,3),(3,2,1)$：有两个儿子相同，一个任意，答案 $3(xF(x^2)F(x)+1)$。 3. $(2,3,1),(3,1,2)$：三个都相同，答案 $2(xF(x^3)+1)$。 全部加起来取平均数： $$ 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)$。 ## 0x02 烯烃计数 从碳碳双键的地方把这个有机物拎起来，那么这两个碳原子再链接两个烷基就行，先用 Burnside 引理对一个碳原子进行计数： $$ F(x)=x\frac{A^2(x)+A(x^2)}{2} $$ 继续用 Burnside 引理对两个碳原子进行计数： $$ G(x)=\frac{F^2(x)+F(x^2)}{2} $$ 得到答案。 ## 0x03 烷烃基数 把重心钦定为根变成一个有根树。实际上这里已经可以通过容斥方法，暴力卷一个式子来做了，但是这样太不优雅了，而且不能求出烷烃计数的生成函数。 烷烃是无根树怎么办，考虑把未知化为已知，强制钦定某一个点为根，那么就只需要考虑树上点的等价类就行，而点等价类就是有根数的计数，然后发现重心这个点很特殊，分类讨论一下： 1. 只有一个重心：首先重心不与其他任何一个点等价，那么两个点等价意味着两个点的父亲边（以重心为根）等价，因为以这个点为根的有根树，到大小大于 $\frac{n}{2}$ 儿子的边是唯一的。设点等价类数量为 $p$，边等价类数量为 $q$，那么 $p-q=1$。 2. 有两个重心，两个重心不等价：同理可得 $p-q=1$。 3. 两个重心等价：$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$ 就是烷烃计数的生成函数。 最后修改：2025 年 05 月 01 日 © 允许规范转载 赞 如果觉得我的文章对你有用，使用点这里使用虚拟货币进行赞赏