正碳烷烃同分异构体计数

Question

n -碳烷烃是由n个节点组成的无根树，其中每个节点的次数最多为4。例如，see this表示n的一些低值的枚举列表。

我正在寻找一种算法来计算这种n -碳脂肪族烷烃的数量，给定一个n。

我已经在化学堆栈交换中使用了seen this。我也考虑过动态编程，即从较小的组件构建较大的图形，但我无法处理过多计算相同的异构体。

澄清:碳只是一个比喻。我不希望考虑C16和C17的不稳定性，也不关心立体异构体

Answer 1

因此，标准的方法是使用Redfield–Pólya Theorem，也称为Pólya枚举定理。然而，它不是非常“算法”的--你有代码like this (数学，哈斯克尔，或者Python版本之一)。

rosettacode页面还描述了一种使用canonical checking避免重复的更直接的方法。该算法是有序生成的一种特殊形式(我认为)，它只适用于没有边颜色顶点和最大价为4的树。