Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site harvard.UUCP
Path: utzoo!linus!decvax!genrad!panda!talcott!harvard!greg
From: greg@harvard.UUCP (Greg)
Newsgroups: net.math
Subject: Hairy combinatorics problem.
Message-ID: <702@harvard.UUCP>
Date: Tue, 11-Feb-86 10:57:50 EST
Article-I.D.: harvard.702
Posted: Tue Feb 11 10:57:50 1986
Date-Received: Thu, 13-Feb-86 19:08:47 EST
Organization: Harvard
Lines: 19
Keywords: acyclic graphs, hydrocarbons

For the combinatorics whizzes out there, I have a rather ugly combinatorics
problem; I would be interested in knowing whether or net there are any
good techniques for tackling such problems.  Anyway, here goes:

I wish to count the number of acyclic, saturated hydrocarbons with n carbons.
These molecules can be thought of as acyclic, undirected, connected graphs,
in which the carbons are nodes, the carbon-carbon bonds are edges, and the
hydrogens are ignored.  So, stated mathematically, the question is:  How many
non-isomorphic, acyclic, undirected, connected graphs are there with n nodes,
in which each node has at most four edges leaving it? 

Plus points are awarded for taking into account stereocenters; a stereocenter
in an organic molecule is a carbon atom with four different chemical groups
leading from it, so one should assign an orientation to every carbon with
either three or four non-isomorphic subgraphs leaving it.  Note that whether
or not the subgraphs leaving the carbon are isomorphic may depend on the
orientations in the subgraphs.
-- 
gregregreg