5

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

Community
  • 1
  • 1
Agnishom Chattopadhyay
  • 1,971
  • 14
  • 32
  • 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. – Gene Apr 24 '16 at 16:40
  • @Gene 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? – Agnishom Chattopadhyay Apr 24 '16 at 16:48
  • 2
    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. – Gene Apr 24 '16 at 17:00
  • Do you want to exclude C16 and C17 configurations which are [unfavourable](http://www-jmg.ch.cam.ac.uk/data/isomercount/)? I suppose you have seen the elaborate (not elegant) code found [here](http://www-jmg.ch.cam.ac.uk/data/isomercount/isojava.html)? – trincot Apr 24 '16 at 18:16
  • @trincot No, I do not want to exclude C16 and C17. And thanks for the link, I hadn't seen that. – Agnishom Chattopadhyay Apr 24 '16 at 18:43
  • Can you describe the problem in CS terms? What are the properties of the trees you are looking for? – Stefan Haustein Apr 24 '16 at 22:27
  • 1
    https://cs.uwaterloo.ca/journals/JIS/cayley.html – גלעד ברקן Apr 25 '16 at 00:59
  • @StefanHaustein I just want to count the number of such possible trees for a given n. – Agnishom Chattopadhyay Apr 25 '16 at 01:22
  • 2
    http://oeis.org/A000602 (OEIS listings usually have some ideas about how to program generation) – גלעד ברקן Apr 25 '16 at 01:26
  • It doesn't look simple, but you can probably recreate the sequences [generated here](http://oeis.org/A000602/a000602_1.txt). – Jared Goguen Apr 25 '16 at 02:09
  • Or, if you have an `n` less than 60, you might just want to hard-code the values [from here](http://oeis.org/A000602/a000602.txt). – Jared Goguen Apr 25 '16 at 02:11
  • @StefanHaustein For given n, he's looking for the number of unique unlabeled, unrooted, undirected trees where all vertices have degree 1 to 4. – Gene Apr 25 '16 at 23:55
  • @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. – collapsar Apr 26 '16 at 13:49
  • @Gene also, n doesn't occur in your description? – Stefan Haustein Apr 26 '16 at 15:17
  • @StefanHaustein "all vertices" -> "all n vertices" – Gene Apr 27 '16 at 02:16

1 Answers1

3

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.

gilleain
  • 621
  • 3
  • 11
  • 24