Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!burl!ulysses!gamma!epsilon!zeta!sabre!petrus!bellcore!decvax!decwrl!pyramid!ut-sally!seismo!harvard!h-sc1!moews_b From: moews_b@h-sc1.UUCP (david moews) Newsgroups: net.math Subject: Re: Hairy combinatorics problem. Message-ID: <940@h-sc1.UUCP> Date: Thu, 13-Feb-86 17:39:02 EST Article-I.D.: h-sc1.940 Posted: Thu Feb 13 17:39:02 1986 Date-Received: Sat, 15-Feb-86 04:37:07 EST References: <702@harvard.UUCP> Reply-To: moews@h-sc4.UUCP (david moews) Organization: Harvard Univ. Science Center Lines: 126 Keywords: trees, hydrocarbons Summary: It's hairy, all right. Here's the generating function. In article <702@harvard.UUCP> greg@harvard.UUCP (Greg) writes: >... 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? The easiest way to do this is to first count the number of rooted trees with n nodes and having degree <=4 at all vertices and degree <=3 at the root (this is the number of alkyl groups with n carbons.) Call these trees "Y-trees". If n=0, we set this number to be 1. If we have a Y-tree with n>0 nodes, the root will be connected to between 0 and 3 other vertices; the trees rooted at these vertices will form 0 to 3 Y-trees: each one will have >=1 vertices, and as a group, they will have a total of n-1 vertices. If there are m<3 of these Y-trees, we can add 3-m Y-trees of 0 vertices to bring the total number of Y-trees to 3 (since we have said that there is exactly one Y-tree with 0 vertices.) In this way, we equate every Y-tree with n vertices with a different bag (= set with repetitions) of 3 Y-trees with a total of n-1 vertices. It's easy to see, also, that for each bag of 3 Y-trees with a total of n-1 vertices there is a different Y-tree with n vertices; thus the number of Y-trees with n vertices is in fact equal to the number of bags of 3 Y-trees with a total of n-1 vertices. Now if we let g[i] be the number of Y-trees with i vertices and let h[i] be the number of bags of 3 Y-trees with a total of i vertices, we can 2 3 define the generating functions G(x) = g[0] + g[1]x + g[2]x + g[3]x + ... 2 3 and H(x) = h[0] + h[1]x + h[2]x + h[3]x + ... . Polya's Enumeration Theorem then gives us H(x) = Z(S , G(x)); but by what we have said above, G(x) = 1 + x H(x), so 3 1 3 G(x) = 1 + x Z(S , G(x)). The cycle index for S is - (c + 3 c c + 2 c ) 3 3 6 1 1 2 3 , so this equation reduces to 3 2 3 G(x) = 1 + 1/6 x (G(x) + 3 G(x) G(x ) + 2 G(x )). I don't have a closed-form solution for this equation, but it does at any rate allow us to compute 2 3 4 5 6 7 8 9 10 G(x) = 1 + x + x + 2 x + 4 x + 8 x + 17 x + 39 x + 89 x + 211 x + 507 x + ... Now we need to compute the number of unrooted trees with all vertices of degree <=4. In this case, there is a theorem which states that if we have some variety of trees ("X-trees", say), then the number of unrooted X-trees with n vertices is equal to the number of rooted X-trees with n vertices minus the number of X-trees rooted at an EDGE (instead of a vertex) that are not symmetric about this edge. Let an "X-tree" be a tree with all vertices of degree <=4 (we do *not* allow any X-trees with 0 vertices). A Y-tree is just a rooted X-tree with a root of degree <=3, and we know that the generating function for Y-trees is G(x). Now in the same manner as every Y-tree with >=1 vertices corresponds to a bag of 3 Y-trees with one less vertex, every rooted X-tree with n>=1 vertices corresponds to a bag of 4 Y-trees with a total of n-1 vertices. If the generating function for rooted X-trees is J(x), then, we know from Polya that J(x) = x Z(S , G(x)); the cycle index for S is 4 4 1 4 2 2 --- ( c + 6 c c + 3 c + 8 c c + 6 c ) so this equation reduces to 24 1 2 1 2 3 1 4 , 4 2 2 2 2 3 4 J(x) = 1/24 x ( G(x) + 6 G(x ) G(x) + 3 G(x ) + 8 G(x ) G(x) + 6 G(x )). Now an X-tree rooted at an edge corresponds to a bag of 2 Y-trees, each with >=1 vertex (the edge connects their root vertices.) The generating function for Y-trees with >=1 vertices is G(x)-1, and Polya tells us that the generating function for bags of 2 Y-trees with >=1 vertices each is 1 2 Z(S , G(x) - 1) ; the cycle index of S is - ( c + c ) so this is just 2 2 2 1 2 , 2 2 1/2 ( (G(x) - 1) + G(x ) - 1) = I(x), say. From this function we must subtract the generating function for numbers of X-trees rooted at an edge and symmetric about that edge. The number of X-trees with n>=1 vertices that are rooted at an edge and symmetric about that edge, however, is just the number of pairs of identical Y-trees with a total of n>=1 vertices; this will be equal to the number of Y-trees with n/2 vertices if n is even, or 0 if n is odd. The generating function, then, will be just 2 G(x ) - 1. The number of asymmetric X-trees rooted at an edge then has generating function 2 I(x) - ( G(x ) - 1) = 2 2 2 1/2( (G(x) - 1) + G(x ) - 1) ) - (G(x ) - 1) = 2 2 1/2( (G(x) - 1) - (G(x ) - 1) ) = 2 2 1/2( G(x) - G(x ) ) + 1 - G(x). Putting it all together, the generating function for X-trees is 2 2 J(x) - 1/2( G(x) - G(x ) ) - 1 + G(x) 4 2 2 2 2 3 4 = 1/24 x ( G(x) + 6 G(x ) G(x) + 3 G(x ) + 8 G(x ) G(x) + 6 G(x )) 2 2 + 1/2( G(x ) - G(x) ) - 1 + G(x) 2 3 4 5 6 7 8 9 10 = x + x + x + 2 x + 3 x + 5 x + 9 x + 18 x + 35 x + 75 x + ..., so, for example, there are 75 X-trees with 10 vertices. -- David Moews moews%h-sc4@harvard.ARPA ...!harvard!h-sc4!moews