Counting isomeric n-carbon aliphatic alkanes

Question

An n-carbon aliphatic alkane is an unrooted tree consisting of n nodes where the degree of each node is atmost 4. As an example, see this for a list of the enumeration of some low values of n.

I am looking for an algorithm to compute the number of such n-carbon aliphatic alkanes, given an n.

I have seen this in chemistry stackexchange already. I have also thought of dynamic programming, i.e, building larger graphs from smaller components, but I cannot deal with overcounting the same isomers.

Clarification: The Carbons are just a metaphor. I do not wish to take into account the instability of C16 and C17, nor do I care about stereoisomers

Centriole

This is a very cool algorithm problem. But there's an element here that will down-vote your question because it's not directly about code and you haven't done much to explain what you've already tried. You should consider the math exchange, too. – Hampshire

@Hampshire It is not about code but about algorithms. I thought algorithm questions are acceptable in StackOverflow. Do you think I would benefit by moving this to cs.stackexchange? – Centriole

I agree with you that algorithms have a (big) place here. Just saying there recently seems to be a trend of down-voting algorithm-only questions that don't include code. See what happens. I'll post something if if I can come up with a useful answer. – Hampshire

Do you want to exclude C16 and C17 configurations which are unfavourable? I suppose you have seen the elaborate (not elegant) code found here? – Instrumentalism

@Instrumentalism No, I do not want to exclude C16 and C17. And thanks for the link, I hadn't seen that. – Centriole

Can you describe the problem in CS terms? What are the properties of the trees you are looking for? – Eluvium

cs.uwaterloo.ca/journals/JIS/cayley.html – Mokas

@StefanHaustein I just want to count the number of such possible trees for a given n. – Centriole

oeis.org/A000602 (OEIS listings usually have some ideas about how to program generation) – Mokas

It doesn't look simple, but you can probably recreate the sequences generated here. – Gourd

Or, if you have an n less than 60, you might just want to hard-code the values from here. – Gourd

@StefanHaustein For given n, he's looking for the number of unique unlabeled, unrooted, undirected trees where all vertices have degree 1 to 4. – Hampshire

@Gene: I think the suggested CS model is wrong: aliphatic alkanes have a single axis with C atoms, while unrooted,undirected,unlabeled trees do not follow this restriction (necessarily, since they are unlabelled). Eg. merge 2 'alkane trees' by merging two arbitrary nodes of degree 2,1 from each tree, to stay within the tree class while arriving at a structure not modelling an aliphatic alkane. – Proof

@Hampshire also, n doesn't occur in your description? – Eluvium

@StefanHaustein "all vertices" -> "all n vertices" – Hampshire

Answer 1

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

The rosettacode page also describes a more direct approach using canonical checking to avoid duplicates. The algorithm is a specialised form of orderly generation (I think) that only works for trees without vertex of edge colors and a maximum valence of 4.

Host