Counting isomeric n-carbon aliphatic alkanes

Question

An n-carbon A-aliphatic alkane is a tree without a root, consisting of n nodes, where the degree of each node is at most 4. For an example, see this for a list of some low n values.

I am looking for an algorithm to calculate the number of such n-carbon aliphatic alkanes, taking n into account.

I have seen this in stackexchange chemistry already. I also thought about dynamic programming, i.e. Building large graphs from smaller components, but I can not cope with re-reading the same isomers.

Clarification: Carbohydrates are just a metaphor. I don’t want to consider the instabilities of C16 and C17, and I don’t care about stereoisomers

Answer 1

Thus, the standard approach is to use the Redfield-Pólya theorem , also known as the Pólya enumeration theorem. However, this is not very “algorithmic” - you have code like this (Mathematica, Haskell or one of the Python versions).

The rosettacode page also describes a more direct approach, using canonical validation to avoid duplication. An algorithm is a specialized form of ordered generation (I think) that works only for trees without vertex edges and maximum valency 4.