问题引入

相信每一位高中学了化学的同学，在最开始学烷烃时，都会像我一样产生这样的疑问：饱和烷烃$C_{n}H_{2n+2}$有多少种结构异构体？每一位老师在讲同分异构体时，估计都是从烷烃的碳链异构讲起的，然后就是一些痛苦的计算，什么分主碳链的长度、把各种分支碳链移来移去，一不小心就重复计算或者少考虑了[doge]。当然大部分例子都只局限在$n\le8$的情况，此时同分异构体已有18种，再往下就多得不适于课堂教学了。所以一个自然的问题就出现了：是否存在一个通项公式描述$C_{n}H_{2n+2}$的同分异构体数目？记得当时我们班上还试图通过找前几项的规律或者直接用讨论碳链的方式求这样的通项公式，但自然最后都失败了。

虽然高中时没有能够解决这样的问题，但这个问题一直藏着我心里。在上学期学集图时，讲到树这一节的时候，我突然想到，这烷烃的碳链不就是无向树嘛！于是接下来的整节课我都竖起耳朵专心致志地听讲，希望老师能讲讲怎么算树的个数，从而解决这个困扰了好几年的问题。可惜老师在讲我感兴趣的互不同构的无向树的计数问题的时候也只是讲了在n比较小的时候如何枚举出来，而没有讲一般的通项公式，这让我十分扫兴。但是PPT上一闪而过了一个无向树计数的生成函数，重新勾起了我的好奇，于是我下课就去找老师问这个生成函数是怎么推导出来的，但是老师只是轻描淡写地说是“查手册找到的”！于是我只好扫兴而归，也没有进一步探究。

这个学期，由于我们在代组课详细地讨论了组合计数方法，（真是把之前高中数学竞赛的组合部分全覆盖了！之前好多没有理解的问题都理了一遍！）所以在学期最后一节课之后，我在复习PPT时突然又想到了这个无向树的计数问题，满怀自信掌握了这么多新方法的我随机开始探究起来。最后果然自己还是不会，但根据之前的生成函数追根溯源，找到了两篇80年前的论文，也算是大体解决了上面所说的问题。

问题叙述

**问题1: **如何计算饱和烷烃$C_{n}H_{2n+2}$的结构异构体数目？

问题2: 如何计算有n个顶点的互不同构的无向树的数目？

显然问题1可以归为限制顶点最大度数为4(碳原子最多只能接4个东西)的不同构无向树计数问题.

解决上面的问题，有两种思路，一种是数学的，另一种是化学的：

1. 数学方法：利用组合计数的方法计数无向树，此处我们探讨的方法主要是生成函数；
2. 化学方法：思路和化学老师们的讨论碳链没有本质区别，只不过需要一些技巧；

第一种方法可以参考Otter Richard在1947年发表于Annals of Mathematics的论文：The Number of Trees.

第二种方法则是化学家Henze, Henry R 在他们1931年的论文THE NUMBER OF ISOMERIC HYDROCARBONS OF THE METHANE SERIES 中提出的，事实上他俩一口气发表了好多类似的论文，比如计算醇、烯烃、炔烃同分异构体的计算方法.感兴趣的读者不妨去阅读原文.

既然是Otter的tree计数公式，那么有请本期特邀嘉宾 Otter tree(水獭 树)镇楼：

xs，我也没见过水獭，网上随便找的图，错了请提醒一下。图片来源

生成函数导出

都说了是数学随笔，那这里就主要讲讲如何用生成函数刻画无向树的数目，但为了达到这一目标，我们需要从根树入手.

以下的讨论中，我们恒假定每个顶点度数(根树的跟节点除外)不超过m，当m=$\infty$时，表示没有限制.

Rooted trees

符号定义：

记$A_n^{(r)}$表示n个节点的不同构的根树的数目，其中根的子节点数目不超过r，并且用$A_n$简记$A_n^{(m-1)}$，对于n=0，定义$A_0=1$；

定义形式幂级数如下：

$\varphi(x)=A_0+A_1x+A_2x^2+\dots$

$\psi_r(x)=A_1^{(r)}+A_2^{(r)}x+A_3^{(r)}x^2+\dots$ （for r>0）

$\psi_0(x)=1$

$G(t,x)=\prod_{v=0}^\infty(1-tx^v)^{-A_v}$

**推导: **

展开$G(t,x)$为关于t的幂级数：$G(t,x)=\sum_{r=0}^\infty g_r(x)t^r$，其中$g_0(x)=1$.

命题1：$g_r(x)=\psi_r(x)$

​ 证明方法是直接展开，然后用递推法对$A_{n+1}^{(r)}$计数，发现恰好是展开式的第n次项系数，参见原文.

命题2：$G(t,x)=\exp(\sum_{\mu=1}^\infty \dfrac{t^\mu}{\mu}\varphi{(x^\mu)})$

​ 对$G(t,x)$取对数展开即可，参见原文.

命题3：

$$\begin{aligned} G(t,x)&=\sum_{n=0}^\infty\frac1{n!}\Bigl(\sum_{\mu=1}^\infty \dfrac{t^\mu}{\mu}\varphi{(x^\mu)}\Bigr)^n \\ &=\sum_{n=0}^\infty\biggl(\sum_{\sum\mu_i=n}\frac1{\mu_1!\mu_2!\ldots}\Bigl(\frac{\varphi(x)}1\Bigr)^{\mu_1}\Bigl(\frac{\varphi(x^2)}2\Bigr)^{\mu_2}\ldots\biggr)t^{\mu_1+2\mu_2+\ldots} \end{aligned}$$

​ 继续展开得到：

推论3：

$$\tag{1}\psi_r(x)=\sum_{\sum i\mu_i=r}\frac1{\mu_1!\mu_2!\ldots}\Bigl(\frac{\varphi(x)}1\Bigr)^{\mu_1}\Bigl(\frac{\varphi(x^2)}2\Bigr)^{\mu_2}\ldots$$

特别的，

$$\begin{aligned} \psi_1(x)&=\varphi(x)\\ \psi_2(x)&=\frac12\varphi(x^2)+\frac12(\varphi(x))^2\\ \psi_3(x)&=\frac13\varphi(x^3)+\frac12\varphi(x^2)\varphi(x)+\frac16(\varphi(x))^3\\ \end{aligned}$$

​ 注意到由定义有 $\psi_{m-1}(x)=\dfrac1x\varphi(x)-\dfrac1x$，因此我们得到一个关于$\varphi(x)$的等式：

$$\tag{2}\dfrac1x\varphi(x)-\dfrac1x=\sum_{\sum i\mu_i=m-1}\frac1{\mu_1!\mu_2!\ldots}\Bigl(\frac{\varphi(x)}1\Bigr)^{\mu_1}\Bigl(\frac{\varphi(x^2)}2\Bigr)^{\mu_2}\ldots$$

对于m无穷的情况，我们记$\psi(x)=\psi_\infty(x)$ 同样有$\psi(x)=\dfrac1x\varphi(x)-\dfrac1x$

在$G(t,x)$的定义式两端乘上$1-t$，得到 $(1-t)G(t,x)=\prod_{v=1}^\infty(1-tx^v)^{-A_v}$.

将$\varphi(x)=1+x\psi(x)$代入命题二式子可得：

$$G(t,x)=\dfrac1{1-t}\exp\Big(\sum_{v=1}^\infty\dfrac{(tx)^v}v\psi(x^v)\Big)$$

其中利用了$\log(1-t)=-\sum_{n=1}^\infty\dfrac{t^n}n$.

再注意到$G(t,x)=\sum_{r=0}^\infty\psi_r(x)t^r$，因此$(1-t)G(t,x)=1+\sum_{r=1}^\infty\big(\psi_r(x)-\psi_{r-1}(x)\big)t^r$.

代入$t=1^-$ 可见右边趋于 $\psi_\infty(x)=\psi(x)$.

综合以上三式，我们最终得到：

$$\tag{3}\psi(x)=\exp\Big(\sum_{v=1}^\infty\dfrac{(tx)^v}v\psi(x^v)\Big)$$

其实也可以直接在$(1-t)G(t,x)=\prod_{v=1}^\infty(1-tx^v)^{-A_v}$中代入$t=1$，得到：

$$\tag{4}\psi(x)=\sum_{v=1}^\infty A_{v+1}x^v =\prod_{v=1}^\infty(1-x^v)^{-A_v}$$

总结：

在以上推导中，我们得到了关于各种情况下根树计数的生成函数关系式：

$$\tag{1}\psi_r(x)=\sum_{\sum i\mu_i=r}\frac1{\mu_1!\mu_2!\ldots}\Bigl(\frac{\varphi(x)}1\Bigr)^{\mu_1}\Bigl(\frac{\varphi(x^2)}2\Bigr)^{\mu_2}\ldots$$

$$\tag{2}\dfrac1x\varphi(x)-\dfrac1x=\sum_{\sum i\mu_i=m-1}\frac1{\mu_1!\mu_2!\ldots}\Bigl(\frac{\varphi(x)}1\Bigr)^{\mu_1}\Bigl(\frac{\varphi(x^2)}2\Bigr)^{\mu_2}\ldots$$

$$\tag{3}\psi(x)=\exp\Big(\sum_{v=1}^\infty\dfrac{(tx)^v}v\psi(x^v)\Big)$$

$$\tag{4}\psi(x)=\sum_{v=1}^\infty A_{v+1}x^v =\prod_{v=1}^\infty(1-x^v)^{-A_v}$$

其中$\psi_r(x)$是限制根节点分支树不超过r时的根树生成函数，由(1)式给出；

$\varphi(x)=\psi_{m-1}(x)$是有桥梁作用的生成函数，由(2)式给出；

当$m=\infty$时，不限制任何节点度数的根树生成函数是$\psi(x)$，由(3)或(4)式确定；

Trees

这一节中，我们将导出无向树和根树的数量关系，记n个顶点互不同构的无向树有$T_n$个。

定义1：对任意一棵无向树T，定义顶点集上的等价关系 $\sim$ 由其自同构群的群作用导出，同一轨道中的顶点互相称为相似的，同理可以导出边集上的等价关系，同一轨道中的边也称为相似的。

引理1：(欧拉公式推广)

设任何一棵无向树的在相似关系下，顶点集等价类(轨道)的数目为v，边集(如果树中有对称边需要除去)等价类的数目为u，则有$v-u=1$.

注释：对于树，由欧拉公式有$|V|-|E|=1$，因此此引理可以视作其推广.

证明：参见原文

利用引理1，我们可以考虑所有顶点数为n的互不同构的无向树组成的集合$S$，我们只需要对其中所有不相似的顶点以及不相似的边计数，然后作差。因为每棵树对差的贡献是1，因此这个差就是无向树的个数。

命题1：S中互不相似的顶点数目为$A_n^{(m)}$

解释：对于每棵无向树，提出一个顶点作为根，得到一棵根树，而且在同一棵无向树中提出相似的两个顶点，得到的根树同构，反之，若对于不同的无向树或者同一棵无向树不相似的顶点，得到的根树不同构

命题2：S中互不相似且非对称边的边数为：

$$\frac12\sum_{\substack{i+j=n\\i\ne j;i,j>0}}A_i^{(m-1)}A_j^{(m-1)}+\binom{A_{n/2}^{(m-1)}}{2}=\frac12\sum_{\substack{i+j=n\\i,j>0}}A_iA_j-\frac12A_{n/2}$$

其中对于奇数n，$A_{n/2}=0$.

解释：切断无向树的某条边，可以得到一对根树，而且切断不同边得到的两对根树同构当且仅当这两条切断的边是同一棵无向树的相似边。因此不同相似边的数目是不都同构的根树对的数目，而且每对中的两棵根树不能相互同构，否则就是对称边了。左式第一项是计数不同顶点数的根树对，第二项是计数顶点数相同的根树个数，等式是恒等变形。

由命题1和命题2我们可以立即得到：

$$T_n=A_n^{(m)}-\frac12\sum_{\substack{i+j=n\\i,j>0}}A_iA_j+\frac12A_{n/2}$$

因此设$\{T_n\}$的生成函数为$\phi(x)=T_1+T_2x+T_3x^2+\ldots$，则有：

$$\tag{5}\phi(x)=\psi_m(x)-\frac12x(\psi_{m-1}(x))^2+\frac12x\psi_{m-1}(x^2)$$

使用上一节根树的生成函数，我们已经完成了对无向树生成函数的刻画。

同分异构体计数

好啦，经过如此冗长的铺垫，我们得到了蕴藏着各种树数目的生成函数，那么接下来我们来看看如何解决最开始提出的问题。

烷烃一卤代物的同分异构体计数

问题：$C_nH_{2n+1}X$的结构异构体有多少个？

分析：这个问题等价于n个节点的根树的数目（将接了X的碳原子视作根节点）

我们考虑m=4时的限制根节点分支数不超过m-1=3的根树生成函数$\varphi(x)$，利用推论3有：

$$\tag{*}\dfrac1x\varphi(x)-\dfrac1x=\frac13\varphi(x^3)+\frac12\varphi(x^2)\varphi(x)+\frac16(\varphi(x))^3$$

我们只需要解这个函数方程，然后得到$\varphi(x)$的幂级数表示就行了，这样一来，问题的答案就是$x^n$前面的系数！

不管你会不会，反正我是不会解，但是我有答案：

$$\varphi(x)=1+x+x^2+2x^3+4x^4+8x^5+17x^6+39x^7+\ldots$$

怎么得到的呢？当然你可以在(*)式两边不断求导，用Taylor公式展开，但显然作者是直接用了化学家已经算好的结果——谁没事去求那么多导数啊QwQ

烷烃同分异构体计数

问题：$C_nH_{2n+2}$的结构异构体有多少个？

分析：这个问题等价于n个节点的无向树的数目

考虑m=4时的无向树生成函数$\phi(x)=\psi_m(x)-\frac12x(\psi_{m-1}(x))^2+\frac12x\psi_{m-1}(x^2)$. 可见我们需要求出$\psi_4(x)$以及$\psi_3(x)$，其中$\psi_3(x)=\varphi(x)$已经由上一问给出了，因此只需计算$\psi_4(x)$. 利用(1)式可得：

$$\psi_4(x)=\frac14\varphi(x^4)+\frac13\varphi(x^3)\varphi(x)+\frac18(\varphi(x^2))^2+\frac14\varphi(x^2)(\varphi(x))^2+\frac1{24}(\varphi(x))^4$$

因此也不难得到$\psi_4(x)$，把它们代入$\phi(x)$的表达式即可，当然计算过于复杂，此处也只贴一个化学家的结果：

$$\phi(x)=1+x+x^2+x^3+2x^4+3x^5+5x^6+9x^7+18x^8+\ldots$$

后记

其实otter导出生成函数的原意自然不是让我们在这里求那么多导，而是希望用生成函数给出无向树/根树的数目的渐进阶数。原论文的后半部分都在用各种各样的微积分技术估计生成函数的系数，最后还用了复变函数里面的解析开拓、柯西积分公式等手法估计出了$A_n$和$T_n$的渐进表达式：

对于$3\leq M\leq\infty$：

$$A_n^{(r)}\sim\frac{\beta a_{r-1}\alpha^{3/2}}{2\sqrt\pi}\centerdot\frac{\alpha^{-n}}{n^{3/2}}$$

对于$3\leq m\leq\infty$：

$$\begin{aligned} A_n&\sim\frac{\beta\alpha^{1/2}}{2\sqrt\pi}\centerdot\frac{\alpha^{-n}}{n^{3/2}}\\ T_n&\sim\frac{\beta^3a_{m-3}\alpha^{5/2}}{4\sqrt\pi}\frac{\alpha^{-n}}{n^{5/2}} \end{aligned}$$

对于$m=\infty$：

$$\begin{aligned} A_n^{(r)}&\sim\frac{\beta\alpha^{3/2}}{2\sqrt\pi}\centerdot\frac{\alpha^{-n}}{n^{3/2}}\\ T_n&\sim\frac{\beta^3\alpha^{9/2}}{4\sqrt\pi}\frac{\alpha^{-n}}{n^{5/2}} \end{aligned}$$

其中$\alpha,\beta,a_k$是在求解过程中出现的关于生成函数的一些参数，例如m=3时有$\alpha=1/\sqrt[24]{2090918}=0.4026975$，$\beta=6.1603212$.

最后贴一下第二篇论文分类讨论得到的烷烃同分异构体数目的结果：

碳原子数	同分异构体数	碳原子数	同分异构体数
1	1	11	159
2	1	12	355
3	1	13	802
4	2	14	1858
5	3	15	4347
6	5	16	10359
7	9	17	24894
8	18	18	60523
9	35	19	147284
10	75	20	366319

以后可以让化学老师在黑板上画一画所有癸烷的同分异构体[不过分吧doge]