WIWIIHIIWWHWWIWHWWWWWI‘ *J LIBRARY Michigan State University This is to certify that the dissertation entitled ENUMERATION 0F SYMMETRIES IN LOCALLY-RESTRICTED TREES presented by KATHLEEN A. MCKEON has been accepted towards fulfillment of the requirements for Ph.D. Mathematics degree in (figs? 53%- Date 12 August 1987 MSU is an Affirmative Action/Equal Opportunity Institution 0-12771 MSU RETURNING MATERIALS: Place in book drop to Lian/truss remove this checkout from ‘- your record. FINES will be charged if book is returned after the date stamped below. ENUMERATION OF SYMMETRIES IN LOCALLY-RESTRICTED TREES By Kathleen A. McKeon A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1 987 ABSTRACT _ ENUMERATION OF SYMMETRIES LOCALLY-RESTBIIRICTED TREES By Kathleen A. McKeon In this thesis, symmetries are enumerated in unlabeled trees with certain restrictions on their degrees. The vertices of a d-tree have degree at most d. The vertices of a (1,d)-tree have degree 1 or d. Trees of these types give rise to significant examples in polymer chemistry. For example, (1,4)-trees represent the alkanes and 4-trees represent the carbon. skeletons of alkanes. A two-variable generating function is used to determine both exact and asymptotic formulas for the number of symmetries in d-trees and (1,d)-trees for d =- 3,4. Tables containing the exact and asymptotic number of symmetries are provided for all four types of trees. To my parents for their love and support, my love and thanks. ACKNOWLEDGEMENTS I would like to thank Professor E. M. Palmer for the encouragement and guidance he provided throughout my education as a graph theorist and mathematician - from my first course in graph theory at Michigan State University to the completion of this thesis. I would also like to thank Professor R. W. Robinson for his many helpful suggestions. TABLE OF CONTENTS LIST OF TABLES ............................................................................................ vi INTRODUCTION ............................................................................................... 1 CHAPTER1 ENUMERATION OF SYMMETRIES ..................................... 5 1.1 Generating functions ................................................................. 5 1.2 Functional Relations .............................................................. 7 1.3 Recurrence Relations ................................................................. 15 1.4 Numerical Results ....................................................................... 20 CHAPTER 2 ASYMPTOTIC BEHAVIOR ................................................. 32 2.1 Asymptotic Analysis ............................................................... 32 2.2 Asymptotic Formulas .............................................................. 35 2.3 Numerical Analysis ................................................................. 37 2.4 Numerical Results .................................................................... 44 CONCLUSION ....................................................................................................... 51 BIBLIOGRAPHY ................................................................................................... 53 A—L—L—L—L—L—L—L N939???) T‘PSOQNSJ’QPPNT‘ LIST OF TABLES Coefficients of T(x,y) for Planted (1,3)-trees .......................... 21 Coefficients of T(x,2) and t(x,2) for (1 ,3)-trees ..................... 23 Coefficients of T(x,y) for Planted 3-trees ................................. 24 Coefficients of T(x,2) and t(x,2) for 3-trees ............................. 25 Coefficients of T(x,y) for Planted (1 ,4)-trees .......................... 26 Coefficients of T(x,2) and t(x,2) for (1 ,4)-trees ...................... 28 Coefficients of T(x,y) for Planted 4-trees .................................. 29 Coefficients of T(x,2) and t(x,2) for 4-trees ............................. 31 Radii and Constants ................................................................................ 45 Number of Symmetries in Planted (1,3)-trees ........................... 46 Number of Symmetries in Free (1 ,3)-trees .................................. 46 Number of Symmetries in Planted 3-trees .................................. 47 Number of Symmetries in Free 3-trees ........................................ 47 Number of Symmetries in Planted (1,4)-trees ........................... 48 Number of Symmetries in Free (1,4)-trees .................................. 48 Number of Symmetries in Planted 4-trees ................................... 49 Number of Symmetries in Free 4-trees ......................................... 49 vi INTRODUCTION The enumeration of trees is an important problem in graph theory with a distinguished history as well as applications to theoretical chemistry. The first major work in this area was performed by Cayley who determined exact formulas for the number of labeled trees [089], the number of rooted trees [057] and the number of free trees [075,081]. These results were extended and an asymptotic analysis of the numbers was provided by Polya [P37] and Otter [048]. In this thesis, both exact and asymptotic formulas are determined for the number of symmetries in unlabeled trees with certain restrictions on their degrees. The definitions and notation used in this thesis follow those of Palmer [Pa85] and are given below. A graph 6 consists of a finite nonempty set V of vertices and a set E of edges which are unordered pairs of distinct vertices. The cardinality of V is called the order of 6 while the cardinality of E is called the size of G. An edge e joining the vertices u and v is denoted by uv and the vertices u and v are said to be adjacent. The degree of a vertex v is the number of vertices adjacent to v. An end-vertex has degree one. A walk in a graph G is a sequence of vertices w1,w2, ,w m such that wi is adjacent to w for i - 1 to m - 1. A path is a walk 1 i+1 .2 in which no vertices are repeated. The length of a path is the number of edges used. The distance between a pair of vertices u and v is the length of the shortest u - v path. A cycle is a walk with at least 3 different vertices that has no repeated vertices except the first and last. A graph is connnected if every pair of vertices is joined by a path. A tree is a connected,acyclic graph. A rooted tree has one vertex, called the root, distinguished from the others. Similarly, an edge-rooted tree has one edge, called the root edge, distinguished from the others. A planted tree is a rooted tree in which the root has degree one. An unrooted tree is also called a free tree. In a d-tree, all vertices have degree at most d. In a (1,d)-tree, the vertices have degree 1 or d. The eccentricity of a vertex v is the distance to a vertex farthest from v. The center of a graph consists of all vertices of minimum eccentricity. The center of a tree contains either one or two vertices. . The complete graph of order n, denoted Kn, has all possible edges present. The complete graph on two vertices, K2, consists of two vertices which are joined by an edge. Two graphs G1 and 62 are isomorphic if there is a one-to-one function (i) from the vertex set of G1 onto the vertex set of stuch that for any two vertices u and v of G1 we have u and v adjacent in G1 if and only if (Mu) and ¢(v) are adjacent in 62- The function (j) is called an isomorphism and is said to preserve adjacency. In unlabeled graph enumeration, isomorphic graphs are considered equivalent and are counted as one graph. 3 An isomorphism from a graph G to itself is an automorphism or symmetry of G. The set of automorphisms of G forms a permutation group denoted by I‘(G) and is called the automorphism or symmetry group of G. An automorphism of a rooted tree must leave the rooted fixed and an automorphism of an edge-rooted tree must leave the vertices of the root edge fixed. Cayley's work [075] was motivated by the problem of enumerating isomers of alkanes, compounds of carbon and hydrogen atoms which have. valencies of 4 and 1 respectively. The alkanes have the general formula CkH2k+2 and can be represented by (1,4)-trees. They are the best documented family of chemical compounds and provide a model for much of chemical theory [GoK73]. Generalizing (1,4)-trees, we have (1,d)-trees which give rise to other meaningful examples in polymer chemistry. There is a correspondence between (1,d)-trees and d-trees that also has chemical significance. While 4-trees correspond to the carbon skeletons of alkanes [GoK73]. d-trees in general correspond to skeleton polymers, i.e., polymer molecules that have been stripped of their reactive end-groups [GoT76]. The problem addressed in this thesis, the enumeration of symmetries in (1,d)-trees and d-trees for d - 3,4, is also motivated by chemistry. In the study of collections of molecular species, it is almost always the average of some property over an appropriate class of trees that is required. In computing such an average, it is necessary to assign weights to the various trees in the class so as to reflect the (not usually equal) proportions in which they are 4 formed by the chemical process involved. The proper assignment of weights to the trees often involves the orders of their automorphism groups [GoL75]. Consequently, chemists are interested in the orders of the automorphism groups of large trees of various species such as (1,d)-trees and d-trees. The tool used to do the counting is a two-variable logarithmic generating function, an approach that seems to have originated in the work of Etherington [Et38]. For a given class C of trees, let t(x,y) be the generating function in the two variables x and y such that the coefficient of ymxn is the number of trees T in C of order n in which m is the logarithm base 2 of the order of the automorphism group of T. In t(x,2), the coefficent of xn is the sum of the orders of the automorphism groups of all such trees. The technique used to do the counting was developed by P6lya in [P37], perfected by Otter [048] and described as a twenty step algorithm for counting various types of trees by Harary, Robinson and Schwenk [HRS75]. The generating functions t(x,y) and t(x,2) satisfy functional equations from which recurrence relations for their coefficients are determined. By applying an adaption of the twenty-step algorithm and treating t(x,2) as an analytic function, the asymptotic behavior of these coefficients is determined. CHAPTER I ENUMERATION OF SYMMETRIES 1 r in F Symmetries are enumerated in four types of trees : d-trees and (1,d)-trees for d =- 3,4. Throughout this thesis the type of tree will be specified only when the statement being made does not appy to all four types. For the planted trees of each type, a two-variable logarithmic generating function is defined as follows: (1.1.1) T(x,y) - 2 2 Tm'nymxn_ [131 m For d-trees, Tm," is the number of planted trees T of order n + 1 in which m =- logZIF(T)|. Every (1 ,3)-tree, planted or free, has an even number of vertices and the order of a (1 ,4)-tree, planted or free, is equal to 2 modulo 3. This is taken into account in the definition of T(x,y) for (1,d)-trees. For (1,3)-trees, Tm,n counts planted trees on 2n vertices with 2"1 symmetries while for (1,4)-trees Tm,n counts planted trees on 3n - 1 vertices with 2'“ symmetries. The values which m may assume in the sum (1.1.1) depend on 5 6 both d and the type of tree. Since an automorphism of a rooted tree must leave the root fixed, the order of the automorphism group of a planted (1,3)-tree or 3-tree is of the form 2'“ where m is an integer. In the case of (1,3)-trees, m ranges from 0 to n - 1. ln 3-trees, m ranges from 0 to (n - 1)/2. Similarly, the order of the automorphism group of a planted (1,4)-tree or 4—tree has the form 2i(3!)i. Thus in these two types of trees, m corresponds to an ordered pair of integers (i,j). The ranges of i and j are as follows. For (1,4)-trees, O s i s n-2 and Os j s n -1-i while 0 s i s (n -1)/2 and 0 S] s (n -1- 2i)/3 for 4-trees. Note that when y - 1 is substituted in (1.1.1), T(x,1) counts planted trees of the specified type. Substituting y - 2 in (1.1.1) results in a one-variable generating function which counts symmetries in planted trees of the specified type. Define m (1.1.2) sn - atm’nz and (1.1.3) T(x,2) - Z snx". n31 Then for (1,3)-trees, for example, Sn is the total number of symmetries in all planted (1,3)-trees on 2n vertices. Similarly, t(x,y) can be defined for free trees. However, we actually only work with t(x,2). Thus, we define I (1.1.4) t(x,2) - Z snxn I131 which counts symmetries in free, i.e., unrooted, trees. For d-trees, sn is the number of symmetries in all such trees on n vertices. For (1,d)-trees, the relationship between n and the number of vertices is the same as in T(x,y). | 2 E I' I B I I' To obtain formulas for the number of symmetries in these trees, functional relations satisfied by T(x,y), T(x,2) and t(x,2) are now derived. First observe that rooted and planted trees of a specified type can be formed from planted trees of that type. A rooted tree in which the root has degree k is formed by taking a collection of k planted trees and identifying their roots to form the root of the new tree. Adding a new vertex adjacent to the root of this rooted tree results in a planted tree in which the degree of the vertex adjacent to the root is k + 1. Based on this observation, relations expressing T(x,y) in terms of T(x,y), T(x2,y2) and T(x3,y3) are denved. W The generating functions T(x,y) and T(x,2) which count symmetries in planted (1 ,3)-trees satisfy (1.2.1) T(x,y) = x +-;- T(x,y)2 + (y '13) T(x2,y2) and (1.2.2) T(x,2) a x +15 T(x,2)2 + %- T(x2,4). Emmi: The vertex adjacent to the root of a planted (1,3)-tree has degree 1 or 3. The term x counts the symmetries in a planted K2,the only planted (1,3)-tree in which the vertex adjacent to the root has degree 1. To count symmetries in those trees in which the vertex adjacent to the root has degree 3, two cases must be considered. Suppose T is the planted (1,3)-tree formed from the planted (1,3)—trees T1 and T2 in the manner described above. If T1: T2, then we have |I‘(T)| - |I‘(T1)| |I‘(T2)|. Then 1/2(T(x,y)2- T(x2,y2)) counts symmetries in this case. If T1 - T2, then we have |F(T)| - 2|1"(T1)|2. This case is handled by yT(x2,y2) with the factor of y accounting for the additional factor of 2 in the group order. Now (1.2.2) is obtained by substituting y - 2 in (1.2.1). // The same techinique is used to derive the following functional relations which are satisfied by T(x,y) and T(x,2) for d-trees and (1,4)-trees. W The generating functions T(x,y) and T(x,2) which count symmetries in planted 3-trees satisfy (1.2.3) T(x,y) . x tug T(x,y)2 + x T(x,y) + x (y - -;—)T(x2,y2) and (1.2.4) T(x,2) x +§- T(x,2)2 + xT(x,2) + 32—x T(x2,4). mm The generating functions T(x,y) and T(x,2) which count symmetries in planted (1,4)-trees satisfy (1.2.5) T(x.y) - x + ~1— Tlx.y>" + l (y - l) may?) T(x.y) 6x x 2 1. 109231- 1— 3 3 +x(y y+3)T(x.y) and 1_ 3 i 2 1.3; 3 (1.2.6) T(x,2) - x + 6x T(x,2) + 2x T(x ,4)T(x,2) + 3x T(x ,8). W The generating functions T(x,y) and T(x,2) which count symmetries in planted 4—trees satisfy (1.2.7) T(x,y) - x .1? T(x,y)3 + 2;- T(x,y)2 + x (y - é) T(x2,y2) + x <1 + (11-13) T(xzf) > Tom I093! 3 3 up ’-y+%-)T(x.y) and 10 (1.2.8) T(x,2) .. x +% T(x,2)3 +§ T(x,2)2 + -32—x-T(x2,4) + x (1 + g-T(x2,4)) T(x,2) + 153le3,8). Using the following lemma which relates the order of the automorphism group of a free tree to the orders of the automorphism groups of the vertex and edge-rooted versions of the tree, t(x,2) is expressed in terms of T(x,2), T(x2,4), T(x3,8) and T(x4,16). M For any tree T. (12.9) mm - 2.1me - 2. 1111211 + (1113)] 1 2 where the first sum is taken over all different vertex-rooted versions T1 of T and the second sum is taken over all different edge-rooted versions T2 of T. If T has a symmetry edge, an edge whose vertices are interchanged by some automorphism of T, then T:3 - T. If T does not have a symmetry edge, then T3 is the empty graph and |I‘(T3)| =- 0. am: Let n*(T) be the number of different ways to root T at a vertex, i.e., the number of orbits of the vertices as determined by the automorphism group of T and let q*(T) be the number of different ways to root T at an edge. Let s(T) be the number of symmetry edges in T. Note that since T is a tree, s(T) is 0 or 1. 11 Lemma 1.2.5 is a variation of a lemma due to Otter [048]: For any tree T, (1.2.10) 1 = n*(T) - q*(T) + s(T) . As in'the proof of (1.2.10), the vertex and edge-rooted versions of T can be paired up such that the paired vertex and edgewooted versions of T have the same automorphism group. Recall that an automorphism of a rooted graph must leave the root fixed while an automorphism of an edge-rooted graph must leave the vertices of the root edge fixed. For each vertex v that is not in the center of T, match the version of T that is rooted at the vertex v with the edge-rooted version that is rooted at the first edge on the path from v to the center of T. If T has a symmetry edge, the center of T consists of two vertices, u and v. Since the edge uv is a symmetry edge, rooting T at v is equivalent to rooting T at u. Hence if the version of T that is rooted at the vertex v is paired with the version of T that is rooted at the edge uv, then the difference of the two sums in (1.2.9) is 0 and T3 :- T. Thus, (1.2.9) holds in this case. If T does not have a symmetry edge two cases must be considered. If the center of T consist of two vertices u and v, match the version of T that is rooted at the vertex v with the version of T that is rooted at the edge uv. In this case and the case that the center of T consist of just one vertex u, there is one vertex-rooted version of T that cannot be paired with an edge-rooted version. This is the tree that results from rooting T at 12 the vertex u which is in the center of T. Since T does not have a symmetry edge, the vertices in the center of T are all fixed points of the automorphisms of the unrooted tree T. Hence this extra vertex-rooted version of T has the same automorphism group as T and (1.2.9) holds in this case also. // This lemma can be extended to a statement about the generating functions that count symmetries by multiplying (1.2.9) by x" and summing over all trees of the appropriate order. Summing the result over all n 2 1 gives t(x,2) on the left side. The first sum on the right side gives the series that counts symmetries in rooted trees and the second sum gives the series that counts symmmetries in edge-rooted trees while |1"(T3)|xn sums to the series that counts symmetries in trees with a symmetry edge. The equations satisfied by t(x,y) can now be stated. Ihggrem 1,2,5 The generating function t(x,2) for symmetries in free (1,3)-trees is given by (1.2.11) t(x,2) . 3‘; T(x,2)2 - 5‘;- T(x,2)3 + 51’— T(x2,4) + 151- T(x3,8). 2x 3x Em: First we determine an expression for the series that counts symmtries in rooted trees. As previously described, this expression can be found by using planted (1,3)-trees to build rooted 13 (1,3)-trees. The series for rooted (1,3)-trees is equal to (1.2.12) T(x,2) +9”?! T(x3,8) + [f- (T(x2,4) T(x,2) - T(x3,8))] {-3-};- (T(x,2)3 - 3 T(x2,4) T(x,2) + 2 T(x3,8))] Symmetries in rooted (1,3)-trees in which the root has degree 1, i.e., in planted (1,3)-trees, are counted by T(x,2). To count symmetries in rooted (1,3)-trees in which the root has degree 3, three cases must be considered. Suppose T is the rooted tree formed from the planted (1 ,3)-trees T1, T2 and T3. The second term of (1.2.12) counts symmetries in the case that all three trees are the same. The case that exactly two of the three trees are the same and the case that all three are different are handled by the first and second bracketed terms of (1.2.12) respectively. A tree rooted at an edge can be formed by identifying the edges incident to the roots of two planted trees. That edge is the root edge of the edge-rooted tree. When the two trees which are combined are the same, that edge is a symmetry edge. Thus, (1.2.13) 1— (T(x,2)2 + T(x2,4)) . 2x counts symmetries in edge-rooted (1,3)-trees and 14 (1.2.14) 3- T(x2,4) X counts symmetries in (1,3)-trees that have a symmetry edge. Combining (1.2.12),(1.2.13) and (1.2.14) as in lemma 1.2.5 and using the functional relation (1.2.2) to. simplify gives equation (1.2.11).// The following theorems give the functional equations satisfied by t(x,2) for d-trees and (1,4)-trees. W The generating function t(x,2) for symmetries in free 3-trees is given by (1.2.15) t(x,2) - T(x,2) Hg- T(x,2)3 + 33-25- T(x2,4) T(x,2) 3 2 13x 3 1 2 —T ’4 _ T ’8 o — T x’2 . + 2 (X )+ 3 (X ) 2 ( ) W The generating function t(x,2) for symmetries in free (1,4)-trees is given by .3. 2 - .1- 2 (1.2.16) t(x,2) .. T(x,2) + 2x T(x ,4) 2x T(x,2) + I 2 T(x,2)“ +3-3- T(x2.4) 11x2)2 24 x 4 x +—9 T(xz.4)‘*+—71 T(x‘.16) 2 2 8x 4x +—13 T(x3,8) T(x,2). 2 3x 15 Ihegrem 1,2,9 The generating function t(x,2) for symmetries in free 4-trees is given by (1.2.17) t(x,2) =- T(x,2) 4.3- T(x2,4) - jlf T(x,2)2 x 4 3x 2 2 + 24 (x 2) + 4 (x ) (x 2) “7‘3 + %‘- T(x2,4)2 + 414 T(x4,16) in nun :‘lquna + lg!- T(x3,8) T(x,2). Wines From the functional equations (1.2.1), (1.2.3), (1.2.5) and (1.2.7), recurrence relations for Tmm, the coefficient of ymx" in T(x,y), can now be determined. Let 8", 0n and Dn be the coefficients of x2", x3" and x4" in T(x2,4), T(x3,8) and T(x4,16) respectively. That is, 2m (1.3.1) en - 2 Tmz , m 3m (1.3.2) on =- 2"; Tm’n2 and 16 4m (1.3.3) Dn . Z Tmm2 . m Then as a consequence of equations (1.2.11),(1.2.15),(1.2.16) and (1.2.17), 5", the coefficient of x" in t(x,2), can be expressed in terms of Sn, 8,1,0n and D". Note that throughout this section the subscripts on the variables are always non-negative integers. Otherwise one can assume the value of the variable is zero. First the formulas for Tm," and sn will be given for (1,3)-trees. For n 2 2 and O s m s n - 1, Tm," is expressed in terms of Am, where A is defined as follows. n m,n r 0, if m = n -1 (1.3.4) Am," a < -1 1.: - _ ZTi'kTm_i’n.k,1fm¢n 1. (1.3.5) T =A +T _ - For n 2 2, 17 ' .1-1 1 1 “'35) Sn'EéskSn-k+1'§:28isiSn-i-l+1 Isl ISI 3 13 —B — . +2 m+3 CALL 2 3 Next the equations for Tm," and sn are given for 3-trees. Here To.1 and T02 are both equal to 1 and for n 2 2 and O s m s (n - 1)/2. I 21 (1.3.7) Tm." + 1 ' E k.1 2i TLk Tm - i,n - k + Tm." +T -lT LIP—L, D. 2 111,-”- 2 2 2 2 - n-'-2 -1 1 1 (1.3.3) 5 =8 +— 33.3 .. -—'233 n n 61-1 j-l l ] n-l-j-l 2k:1 k n-k +§B4J3C +§D 2 fl. 3 n-1 2 n-1 2 3 And now we have the equations for Tm," and sn for (1,4)-trees. Recall that the group order of a planted (1,4)-tree has the form 2i(3!)l' and in Tm’n, m corresponds to the ordered pair of integers (i,j). Hence, we write Tm," as TM,n where 0 s i s n - 2 18 andosjsn-1-i. ThenTo,1=To'o’, =1 andforn22, - 1 - k (1-3-9) Ti.i.n " g2 2 Z z z Edi Ta,b,ch,d,lTl-a-c,j-b-d,n-k-|-1 k-1la1 a b - "1'2 23 2b Ta.b,kTi - 28.1 - va" ' 2" T 1 2 1sks-"— 2 1sksl a 2 +T,, -T, .. 4.11,. . I_|-1n+1 I-th+1 3L.L"+1 3'3'3 3’3'3 3'3’3 To write the formula for smwe first define .1 (1.3.10) Un - E Sk Sn _k for n 2 2. Then for n 2 2, .1. .22 (1.3.11) sn=Sn—2UnH-1-4kZUan.k+2 " 2 -1 - i n - ' - ' +1 1 “—3 2 Si SjSkSn-i-j-k+2 24 i=1 i=1 k=1 19 Finally, the equations for Tm,n and sn are given for 4-trees. As in planted (1,4)-trees, the group order of a planted 4-tree has the form 2‘(3!)I. Thus, Tm," :- Ti”jn where O s i< (n - 1)/2, O s j s (n -1 -2i)/3. Both To,o,1 and To.o.2 are equal to 1 and forn22, (1-3-12) Ti,j,n+1' 1:12: 2222 a,,Tbk 0,,le i--,acjbd,--nk1 1 T —T + 121,2,24'3 1.1.2“ Liv—1,2 2 22 333 3 3 3 2:22 -1--r a,,bk Tbs—1.13mi 2 Lin. 2 2’2 2’2’2 1?. +2....1gg1-ab'k Iajbnk Ijn 1.2 - '2, 2221:.than 2.1-1.3. '1 a 2 2’2 3’3'3 Forn25, --3n (1.3.13) Sn=Sn+-'4':: XZSiSjSSk n-i-j--k1 4ia1 III-1 +—:UkB__ +13128|pmg+—:BB ”211 8I=--1 3 71 '-2-Un+'§28£+—4—Dn_ . 2 4 20 LALNumeLlQaLBfiulIs For each type of tree, values of Tmm, Sn and sn were computed using the CDC Cyber 750 in the Computer Laboratory at Michigan State University. The computation of these numbers was limited by the available accuracy of 14 single precision and 29 double precision floating point digits and by storage restrictions. Another limiting factor was the time required to compute the values using the recurrence relations. For example, in the case of (1,3)-trees, the Fortran programs used to compute Sn for n s 50 took 52 seconds while an additional 300 seconds were required to compute See- The effect of these limiting factors is seen in the maximum value of n for which the numbers could be computed. Due to the difference in the number of possible group orders for the four types of trees, this maximum value of n varies greatly among the different types of trees. For (1,3)-trees, the maximum value of n was 50 while for 3-trees, it was 70. In both these cases, the available accuracy was the most significant limiting factor. For (1,4)-trees, the maximum value of n was 22 while it was 36 for 4-trees. In these two cases, the most significant limiting factor was the storage restriction. Values of Tm’n, Sn and sn appear in the following tables. 21 Coefficients of T(x,y) for Planted (1,3)-trees. Table 1. Tm,n 101 123 111 1221 123 1234 1433 1677101 1234 1234567 1944.611 12881431 11 1222 1234567 12345678 22 Table 1. (cont'd.). 11 12 1 20 85 126 61 27 .3 _L (O ...L 4N0 13 135 239 273 187 —L AOCDQVGUI-bwmé GOODNCDUI-hwmé omooxlowuswm-s ooxlownpwru-s N 01 14 580 500 246 112 33 11 —L.—l Table 2. 23 Coefficients of T(x,2) and t(x,2) for (1,3)-trees. n Sn sn 4 10 8 5 14 56 6 42 24 7 90 168 3 354 240 9 758 608 10 2290 920 11 6002 5680 12 18410 6104 13 51310 18416 14 154106 43008 15 449322 148152 16 1384962 325608 17 4089174 980840 18 12475862 2421096 19 37746786 7336488 20 116037642 19769312 21 355367310 58192608 22 1097869386 164776248 23 3393063162 502085760 24 10546081122 1427051544 25 32810171382 4261678656 26 102465452754 12615722288 27 320522209490 37914214232 28 1005428474218 113567513528 29 3159128678510 343641240328 30 9947763312410 1039134670952 31 31374858270154 3164525151512 32 99133809899138 9638997662848 33 313680433887702 29494412007120 34 994070600867778 90400450050120 35 3154447132624578 278010905513408 Table 3. Coefficients of T(x,y) for Planted 3-trees. 24 n m Tm,n 4 0 2 1 1 5 0 3 1 3 6 0 6 1 5 7 O 11 1 11 3 1 8 O 22 1 22 2 1 3 1 9 O 43 1 48 2 4 3 3 10 O 88 1 101 2 13 3 5 11 0 179 1 221 , 2 37 3 13 4 1 12 0 372 1 480 2 103 3 25 4 Table 4. 25 Coefficients of T(x,2) and t(x,2) for 3-trees. n Sn Sn 4 4 8 5 9 4 6 16 14 7 41 21 8 78 35 9 179 49 10 382 158 11 889 191 12 1992 425 13 4648 828 14 10749 1864 15 25462 3659 16 59891 8324 17 142793 17344 18 340761 39601 19 819533 87407 20 1975109 199984 21 4784055 453361 22 11617982 1053816 23 28316757 2426228 24 69185852 5672389 25 169516558 13270695 26 416268547 31277150 27 1024543728 73874375 28 2526631078 175419550 29 6242969248 417535487 30 15452300967 997758788 31 38310417739 2390172398 32 95126958081 5743235470 33 236548880263 13832781125 34 589014148511 33401381861 35 1468545756633 80825852570 26 Coefficients of T(x,y) for Planted (1, )-trees. Table 5. Ti,j,n 1224 3120 ._. . . nallllillfl 122111 122334 423121 14.213321 12233345 53412320 16343413531 12233344456 64523412311 27 Table 5 (cont'd.). Ti,j,n 193157172882122 1244606622173666531 11 1 221 231 2 122333444455666 1223334444555566678 756345123423012 8674562345123412311 TaerG. 28 Coefficients of T(x,2) and t(x,2) for (1,4)-trees. n Sn sn 4 96 144 5 1560 1584 6 4848 32544 7 28848 30528 8 248352 188928 9 1446240 4030848 10 12905664 12029184 11 99071040 66104064 12 649236480 524719872 13 4924099200 2364433920 14 49007023872 28794737664 15 304778309376 194617138176 16 2301818168832 962354727936 17 18389782387200 6901447938048 18 138110895596544 112061234884608 19 1094304243348480 366020989931520 20 8691945066848256 2592919032274944 21 68039592521668608 19913392024584192 22 541189487303208960 140498248288886784 29 Coefficients of T(x,y) for Planted 4-trees. Table 7. Ti,j,n 010 6812 0001 0.120 282151 11 000011 0.123041 000011 012301 52 00004112 0123011 30 Ti,j,n (cont'd.). Table 7 34941101112 1171 53 12 00000111122 01234012301 10 00000111122 01234012301 11 542 1 180 612 127 22 270 243 28 1 1 000001111222 012340123012 12 TaerB. 31 Coefficients of T(x,2) and t(x,2) for 4-trees. n Sn sn 4 10 8 5 17 28 6 38 20 7 106 43 8 253 143 9 716 249 10 1903 546 11 5053 1223 12 13786 2703 13 39293 8107 14 107641 18085 15 302807 44013 16 860099 114919 17 2450684 327712 18 7038472 800937 19 20316895 2146066 20 58849665 5827711 21 171217429 15923828 22 499926666 43886143 23 1464276207 121888966 24 4301706250 340209504 25 12671810107 955859391 26 37419912977 2700771322 27 110759884262 7652412896 28 328525197554 21784431688 29 976350258323 62248194140 30 178463482459 2906960957827 CHAPTER II ASYMPTOTIC BEHAVIOR An adaptation of the Monty-step algorithm [HRS75] is used to study the behavior of the coefficients of T(x,2) and t(x,2) for large values of n. In the asymptotic analysis, the generating functions T(x,2) and t(x,2) are regarded as power series in the complex variable x. For each type of tree, let p be the radius of convergence of T(x,2). Observe that in a planted d-tree or (1,d)-tree, the maximum possible group order for each n is ((d - 1)!) Mn“) where a ist for (1,d)-trees and (d -1)'1 for d-trees. This maximum group order is attained by a planted (1,d)-tree in which every end-vertex except the root .is at the same level in the tree. While such trees do not exist for all values of n, they do exist for infinitely many values of n. This observation leads to the following lemmas concerning p. M For all four types of trees, the radius of convergence p of T(x,2) satisfies 0 < p < 1. Em: Note that as previously stated, T(x,1) is the series 32 33 that counts the planted trees of the specified type. It follows from the above observation that the coefficients of T(x,2) are bounded above by the coefficients of T(((d - 1)!)“x,1), which has a positive radius of convergence [P37], [048]. Hence p > 0. The upper bound on p is obtained by considering the behavior of T(x,2) as x approaches p from below. As in step 4 of the twenty-step algorithm, the functional equation for T(x,2) and the monotonicity of T(x,2) show that T(p,2) < co. This together with the fact that Sn 2 1 for infinitely many n shows that p < 1. // W T(xk,2k) has radius of convergence ok > p for all k _>. 2. 15.9.0.1: Let M - logz((d - 1)!)“. By the earlier observation, for infinitely many n, Sn 2 2M(" ' 1). Thus, p < 2"“. For k - 2, T(x2,22) s T(2Mx2,2) which converges when x s (p2'M)‘/2. This shows <32 2 (p2‘M)"2. Hence since p < 2'”, we may conclude that 02 > p. The result is then shown for k 2 3 by induction on k. // As a result of the functional relations for t(x,2) and lemma 2.1.2, we can conclude that p is also the radius of convergence of t(x,2) and that t(p,2) is finite. In step 5 of the twenty-step algorithm a new function F(x,y) is defined by replacing each occurrence of T(x,2) in its functional relation by the variable y. The appropriate definitions of F for each type of tree are as follows. 34 For (1 ,3)-trees, (2.1.1) F(x,y) = x + 1- y2 + 1 T(x2,4) - 2 2 For 3-trees, (2.1.2) F(x,y) :- x + '15 xy2 + xy + %T(x2,4) - For (1 ,4)-trees, (2.1.3) F(x,y) - x + L3 y + — T(x2 ,4) y +— 3T(x3 ,-8) 6x 2x 3x For 4-trees, (2.1.4) F(x,y) = x + g- xya +13 xyz + xy(1 + g- T(x2,4)) +32-’-‘-T(x2 ,4) + L—g" T(x3,8) - W F(x,y) satisfies the following conditions: (i) F(x,y) is analytic for all y and for all x in a neighborhood of x = 0 which contains x - p. (ii) F(x,T(x,2)) .. 0 for all x with |x| 5 p. (iii) The first partial derivative of F with respect to y, Fy(x,y) satisfies Fy(p,T(p,2)) a 0 and if |x| 5 p but x at p, then Fy(x,T(x,2)) at 0. 35 (W) Fyy(p.T(p.2)) 1* 0- (v) x - p is the unique singularity of T(x,2) on its circle of convergence. Em: Part (i) is a consequence of lemma 2.1.2 since T(x",2k) is analytic at x - p for k 2 2. That F(x,T(x,2)) - 0 for |x| < p follows directly from the definition of F and the functional equation for T(x,2). That Fy(x,T(x,2)) a: 0 if |x| 5 p but x a: p can be shown by combining the techniques of Otter [048] and step 10 of the twenty-step algorithm [HRS75]. The justification of the remaining statements of this lemma is described in steps 6 through 13 of the twenty-step algorithm. // As a consequence of lemma 2.1.3, x - p is a branch point of order 2 of T(x,2) and therefore, as in step 14 of the twenty-step algorithm, T(x,2) and t(x,2) both have expansions in (p - x)"2 near x =- 0. 1. 2 (2.1.5) T(x,2) =- T(p,2) - b1(p - x)2 + b2(p - x) + b3(p - x)2 + 1. 2 (2.1.6) t(x,2) - t(p,2) + a1(p - x)2 + a2(p - x) + a3(p - x)2 + fr I The asymptotic formulas for the coefficients of T(x,2) and t(x,2) are found by evaluating the contribution of (p - X)“ in the above expansions (2.1.5) and (2.1.6). Note that by the binomial 36 theorem and the definition of the gamma function, if s at 0, -1, «2,... then the coefficient of xn in (1 - x)'8 is (22.1) Us + n) [(3) F(n + 1) From Stirling's formula, this latter expression is equal to s-1 (2.2.2) l}_(s,T (1 + gig—)- + 0(1/n2)). Lemma 2.1.3 allows the application of P6lya's lemma, step 17 of the twenty-step algorithm, which uses the above observations to give the asymptotic formulas for the coefficients of T(x,2) and t(x,2). Inegrem 2,2,1 The asymptotic behavior of the number of symmetries in planted d or (1,d)-trees is given by b .1. :9. (2.2.3) sn ~ -‘- (2)2 n 2 p‘". 1C 2 W The asymptotic behavior of the number of symmetries in free d or (1,d)-trees is given by :5. 2 1 3a 35'” 2.2.4 —L ‘n. ( ) sn~ 4 (1‘)!) p 37 Formula (2.2.3) accounts for the contribution of -b1(p - x)"2 to the coefficient of x". For the free trees, it will be shown that a1 - 0. Thus formula (2.2.4) accounts for the contribution of a3(p - x)"’2 to the coefficient of x". As can be seen by (2.2.2), in both cases the relative error in the asymptotic approximation is 0(1/n). Note that for planted trees, the asymptotic number of symmetries is of the form cn'3/2p'" where c is a constant. For free trees, the asymptotic number of symmetries has the form cn'5/2p°". Formulas (2.2.3) and (2.2.4) can be refined by taking into account the contribution of additional terms of the expansions (2.1.5) and (2.1.6). When the contribution of one additional term is added, -3 "'_ b 12b p+3b (2.2.5) 8 ~\/En2p"(—L+ 3 1) n 11: 2 16n and é. 3 3a 45a - 60ap 2 -n 2.2. ... L _§. _3___5... (6) Snfiw‘w" 32n ) 23 [I i I E ! . Evaluation of these asymptotic formulas requires computation of p, b1, b3, a3 and as. The relations F(p,T(p,2)) - 0 and Fy(p,T(p,2)) a 0 combine to provide equations from which p and T(p,2) can be computed. The corresponding equations for the four types of trees are as follows. 38 For (1 ,3)-trees, (2.3.1) p 4% (1 - 3 T(p2,4)). For 3-trees, (2.3.2) p (T(p,2) + 1) = 1. For (1 ,4)-trees, (2.3.3) p =35 (T(p,2)2 + 3 T(p2,4)). For 4-trees, (2.3.4) p( %- T(p,2)2 + T(p,2) + % T(p2,4) + 1) = 1. The following method is used to obtain equations for the bi's and the ai's. Using both the functional relation for T(x,2) and its expansion in (p - x)“2 to evaluate Tx(x,2)(T(p,2) - T(x,2)) provides the means for determining the bi's. To illustrate, from equation (1.2.2) for (1,3)-trees, after a bit of work, we have (2.3.5) Tx(x,2) (T(p,2) - T(x,2)) = 1 + 3xTx(x2,4). When the expansion (2.1.5) is used to substitute for T(x,2) 39 and Tx(x,2) and the Taylor series expansion about x = p is used to substitute for 3xTx(x2,4) in (2.3.5), coefficients of (p -x)"/2, (p - x)°, (p - x)"2,... can be compared to express the bi's in terms of T(pk,2k) and Tx(pk,2k) for various values of k. In a similar manner, tx(x,2) is evaluated to obtain expressions for the ai's in terms of the bi's and to show a1 = 0. The equations for b1 and a3 are given below. Since the equations for b3 and a5 are much more complicated, they are omitted. In the expansions of T(x,2) and t(x,2) for (1 ,3)-trees, (2.3.6) b1 - \/2(1 + 39Tx(pz.4)) and 2 37) b? . a = -— - ( 3 3p In the expansions of T(x,2) and t(x,2) for 3-trees, 3 2 (2.3.8) b, - -‘p-\/ 2(T(p.2) + an up .4)) and 3 b p 1 (2.3.9) as =—3- . In the expansions of T(x,2) and t(x,2) for (1,4)-trees, 40 b \/ T(P.2)(69Tx(9214) ' 2) 1' 4p + 26p2Tx(p3,8) 1 (2.3.10) T032) and 3 b T ,2 (2.3.11) 8 I i)- . 3 2 3p In the expansions of T(x,2) and t(x,2) for 4-trees, b 1 \/ 2 (NM) + ap"T,(p2.4)(1 + T(p,2)) + 131141311335» 1 ._ (2.3.12) 9 1 + T(p,2) and (2313) a bfprTrp.2)+1> 3 3 The numerical methods necessary to actually compute values of p, T(p",2") and Tx(pk,2k) for various k depend on d. First we will deal with the case that d - 3. Note that the functional equations (1.2.1) and (1.2.3) are actually quadratics in T(x,y) which can be extended to quadratics in T(x",2k) for k 2 1. Thus, applying the quadratic formula and the mononicity of T(x“,2") results in the following equations for T(x",2") when |x| 3 p. For (1,3)-trees, (2.3.14) T(x",2") = 1 - J1 - (2k * ‘- 1)T(x2k,22k) - 2x". 41 For 3-trees, (2315) T(x",2") .. 1 - x" - \[1 - 2xk - x2k(1 + (2k * ‘- 1)T(x2k,22k))_ k X In each of the above equations, T(x",2") is expressed in terms of T(x2k,22k). Thus for |x| 5 p, if T(x‘6,2‘5) is estimated by a partial sum, then equation (2.3.14) or (2.3.15) can be used repeatedly to determine T(x3,23), T(x4,24), T(x2,22) and T(x,2). Similarly, from equations (1.2.1) and (1.2.3) Tx(xk,2k) can be expressed in terms of T(x",2"), T(x2k,22k) and Tx(x2k,22k). Again by starting with a partial sum for Tx(xk,2") for k 2 16, Tx(x",2k) can then be calculated for k < 16 and IX] < p. Note that p is actually significantly less than 2'M where M - ((d - 1)!)“. Calculation of successive terms of T(x‘6,2‘6) and Tx(x‘6,2‘5) indicate that their nth terms are less than 10'27 when x s p and n is about 20. The exact value of n for which this is true depends on d and the type of tree. To estimate the error in the partial sum approximation of T(x‘6,2‘6) note that the twenty-step algorithm can be applied to determine the asymptotic behavior of the coefficients of T(x‘6,2‘6). The coefficient of x16" is asymptotic to C(o16)"6“ n '3’2 where C is a constant and 915 is the radius of convergence of T(x‘6,2‘6). Thus if we disregard the factor of n‘3’2 then T(x‘6,2‘6) behaves like the geometric series 2 Cr'1 where r = (x/o16)‘6. If x s p, then r < 1 and by comparing 016 with the radius of T(x‘6,1), it can be seen that r is in fact closer to 0 than to 1. This provides a bound on the error in the partial sum 42 approximation. Equations (2.3.1) and (2.3.2) provide the means for calculating p. For (1,3)-trees, p is the unique solution of (2.3.16) g(x) .. x +13 (3 T(x2,4) - 1) = 0. While for 3-trees, p is the unique solution of (2.3.17) g(x) - x(T(x,2) + 1) - 1 . 0. The following iterative method can then be used to compute p. Given initial lower and upper bounds for p, In < p < hn, then 90 ) 2.3.18 I = l -l " ( ) n +1 n 11 9'0") and l (2.3.19) h =1 -951. n +1 11 g'(| ) Note that (2.3.19) is just Newton's Method applied to g and In. Since 9 is increasing and concave up for |x| < p,each iteration produces a new upper bound hn +1 such that p < hn +1< hn. Formula ' (2.3.18) is a modification of Newton's Method : the line with slope g'(|n)/ln is used rather than the tangent line to estimate g(x). For i these particular functions, each iteration of (2.3.18) provides a new lower bound In +1 such that In < ln +1< p. Note that since T(x,2) 43 is not defined for x < p, the lower bound is modified each time to give a new lower bound and a new upper bound for p. When d =- 4 the functional equations (1.2.5) and (1.2.7) are cubics in T(x,y). Hence a numerical method is required to compute T(xk,2") for |x| < p. For (1,4)-trees, the cubic with root T(xk,2k) is 2k 22k k )-x)z +(6" -"2 +—)T(x3" .23")+x2". (2.3.20) G (2) - éza + ((2" -—)T(x For 4-trees, the cubic with root T(x",2k) is k k (2.3.21) G(z)'%23+£2’22 +(x" (1 + (2" -—)T(x 2" .22")) - 1) z +x"<1+(2"- -)T(x2" 2+2") (6"-2"_)1(3"23")) If 0 < x < p and z < T(x",2"), then Gk is decreasing and concave up. Therefore application of Newton's method to the function Gk starting with 20, a partial sum of T(xk,2"), produces 21 such that 20 < 21 < T(x",2"). Consequently, T(x",2") can be estimated by a partial sum for k 2 16 and Newton's method can then be applied to Gk to calculate T(x",2") for k < 16. As with 3 and (1,3)-trees, the functional relations (1.2.5) and (1.2.7) supply equations for Tx(x",2") in terms of T(xk,2"), T(x2k,22"), T(x3",23"), Tx(x2k,22k) and Tx(x3k’23k). Here the functions with unique root x = p are 44 (2.3.22) g(x) . T(x,2)2 + 3T(x2,4) - 2x for (1 ,4)-trees and (2.3.23) g(x) . x(%T(x,2)2 + T(x,2) +%T(x2,4) + 1) - 1 for 4-trees. In these two cases g(x) is increasing and concave up. However, the modified Newton's method which worked when d = 3 does not provide a new lower bound for p. Instead the bisection method is used to determine bounds for p. Given ln < p < hn, let xn - (In + hn)/2. The following criteria was used to determine the relationship between p and xn. First estimate T(xn",2") for k > 1 as described earlier. When k . 1 and Newton's method is applied to G1 with initial guess 20, a partial sum of T(xn,2), an estimate zm such that G1'(z,n) > 0 indicates xn > p. 2.4—W In the computations, T(x",2") was calculated to at least 20 digits and p to at least 12 digits. The computed values of p, b1,b3,a3 and a5 appear in the following table. 45 Table 9. Radii and Constants. Type of Tree (1.3) 3 (1 .4) 4 p .301398653 .384173339 .116663460 .319078317 b1 2.403442218 5.076889680 1.544582575 3.844874351 a3 15.354599582 16.757111017 37.009971072 13.381537712 b3 3.588139413 14.591292087 a5 -17.824935398 ~341.927657398 Formulas (2.2.3) and (2.2.4) were used to determine the asymptotic number of symmetries in planted and free d-trees while the refinements (2.2.5) and (2.2.6) gave significantly better results for the asymptotic number of symmetries in planted and free (1 ,d)-trees. The exact number of symmetries is compared to the asymptotic number in Tables 10 - 17. 46 Table 10. Number of Symmetries in Planted (1,3)-trees. Vertices Exact Asymptotic Relative Error 48 10546081122 104637 E05 -.007808 52 102465452754 101826 E06 -.006241 56 1005428474218 100021 E07 -.005186 60 9947763312410 990417 E07 -.004383 64 99133809899138 987582 E08 -.003788 68 994070600867778 990798 E09 -.003292 72 10023140394172682 999410 E10 -.002897 76 101556839584864874 101296 E12 -.002571 80 1033496930259584098 103112 E13 -.002299 84 10558761198762257586 105369 E14 -.002068 88 108257452313403277290 108055 E15 -.001871 92 1113533377484472278586 111164 E16 -.001701 96 11487547694267472245250 114697 E17 -.001554 100 118829269415696976059298 118660 E18 -.001425 Table 11. Number of Symmetries in Free (1,3)-trees. Vertices Exact Asymptotic Relative Error 48 1427051544 134470 504 - 057708 52 12615722288 120224 E05 -.047033 56 113567513528 109211 E06 -.038356 60 1039134670952 100573 E07 -.032148 64 9638997662848 937220 E07 -.027679 68 90400450050120 882491 E08 -.023798 72 856418820307400 838609 E09 -.020796 76 8184345855878800 808432 E10 -.018331 80 78821355356607416 775368 E11 -.016297 84 764368300213840728 753216 E12 -.014590 88 7458653276030440720 736061 E13 -.013145 92 73191173128569457416 723197 E14 -.011907 96 721899672085668985128 714074 E15 -.010840 100 7153568644231221969760 708266 E16 - 009912 47 Table 12. Number of Symmetries in Planted 3-trees. Vertices Exact Asymptotic Relative Error 15 10749 11109 E00 .033511 20 819533 839670 E00 .024572 25 69185852 706783 E02 .021572 30 6242969248 635872 E04 .018542 35 589014148511 598567 E06 .016218 40 57398241292347 582234 E08 .014377 45 5732097451950746 580603 E10 .012899 50 583553860753045319 590376 E12 .011690 55 60336483976084984447 609812 E14 .010685 60 6318602632078649428839 638076 E16 .009837 65 668812989635611814991086 674907 E18 .009112 -m' Table 13. Number of Symmetries in Free 3-trees. Vertices Exact Asymptotic Relative Error 15 3659 3306 E00 -.096398 20 199984 192467 E00 -.037587 25 13270695 131658 E02 -.007908 30 997758788 997370 E03 -.000389 35 80825852570 810687 E05 .003005 40 6907362937687 693805 E07 .004443 45 614475723485527 617618 E09 .005114 50 56409655488848540 567140 E11 .005395 55 5311321843821516910 534038 E13 .005471 60 510635048525607184087 513411 E15 .005435 65 49958747518253245317394 502254 E17 .005338 48 Table 14. Number of Symmetries in Planted (1,4)-trees. Vertices Exact Asymptotic Relative Error 32 99071040 886729 E02 -.104957 35 649236480 658419 E03 .014143 38 4924099200 494957 E04 .005172 41 49007023872 375966 E05 -.232832 44 304778309376 288131 E06 -.054621 47 2301818168832 222519 E07 -.033291 50 18389782387200 173004 E08 -.059241 53 138110895596544 135302 509 -.020335 56 1094304243348480 106372 E10 -.027947 59 8691945066848256 840194 E10 -.033365 62 68039592521668608 666426 E11 -.020531 65 541189487303208960 . 530604 E12 -.019560 Table 15. Number of Symmetries in Free (1,4)-trees. Vertices Exact Asymptotic Relative Error 32 66104064 403949 502 -.388920 35 524719872 271748 .503 -.482109 38 2364433920 186644 E04 -.210619 41 28794737664 130459 E05 -.546935 44 194617138176 925649 E05 -.524374 47 962354727936 665358 E06 -.308615 50 6901447938048 483710 507 -.299118 53 112061234884608 355181 E08 -.683047 56 366020989931520 263123 E09 -.281125 59 2592919032274944 196473 E10 -.242271 62 19913392024584192 147751 E11 -.258030 65 140498248288886784 111827 E12 -.204070 49 Table 16. Number of Symmetries in Planted 4-trees. Vertices Exact Asymptotic Relative Error 14 39293 36783 E00 -.063881 16 302807 291494 500 -.037361 18 2450684 237300 E01 -.031697 20 20316895 197264 502 -.029066 22 171217429 166745 503 -.026119 24 1464276207 142888 504 -.024172 26 12671810107 123846 505 -.022662 28 110759884262 108381 506 -.021478 30 976350258323 956329 E06 -.020506 32 8669904767404 849899 507 -.019714 34 77481380765038 760054 508 -.019050 36 696342460242332 683469 509 -.018488 Table 17. Number of Symmetries in Free 4-trees. Vertices Exact Asymptotic Relative Error 14 18085 12273 500 -.321363 16 114919 86334 500 -.248741 18 800937 631693 E00 -.211308 20 5827711 476779 501 -.181875 22 43886143 369013 502 -.159159 24 340209504 291592 503 -.142906 26 2700771322 234464 504 -.131865 28 21784431688 191346 505 -.121640 30 178463482459 158167 E06 -.113728 32 1480989441806 132206 507 -.107315 34 12424948660563 111592 508 -.101872 36 105244459584049 950122 E08 -.097224 50 The limited range of numbers for which the exact values could be computed for (1,4)-trees is not large enough to exhibit the nice decline in the relative error found in the other types of trees. In fact, for free (1,4)-trees there are large jumps in the relative error at various points in Table 15. The explanation of this can be found by comparing the ratio of consecutive coefficients, sn+1lsn for both the exact and asymptotic numbers. The ratio of the asymptotic values is steadily approaching p'1 while the ratio of the exact values jumps around as the relative error does. This is caused by the free (1,4)-trees that have a factor of 4! in their group order. Examples of such (1,4)-trees are those in which the number of vertices is of the form 5 + 6(3‘- 1). The existence of these trees is not reflected in the asymptotic formula (2.2.4) or its refinement (2.2.6). A similar phenomenon occurs in the case of (1,3)-trees; however, the jumps are much smaller and their effect is only seen when the number of vertices is less than 40. CONCLUSION The results presented in this thesis can be combined with formulas for the asymptotic number of trees of the specified type to give an asymptotic formula for the expected group order of these trees. The relevant formulas for the number of these trees appear in [048] and [BaKP81]. Since the number of such trees is asymptotic to CB'"n'5’2 where B is the radius of convergence of the series that counts the trees and C is a constant, the expected group order is asymptotic to A(B/p)" where A is a constant. In other words, the expected group order is asymptotic to an exponential function of the ratio of the two radii. Generally when the twenty-step algorithm is applied, the planted trees simply provide a means for getting at the results for the free trees. But removing the root from a planted (1,3)-tree of order 2n produces a binary tree of order 2n - 1. Since these trees have the same automorphism group, Table 10 provides values for the number of symmetries in binary trees. Thus the results for planted trees are also of interest. Note that this application of the twenty-step algorithm is independent of the value of d. Thus the solution of this problem is theoretically possible for larger values of d. However, it becomes unmanagable since the functional relations for the generating 51 52 functions become more complex and the number of possible group orders increases greatly as d increases. The success of the techinique used here relies heavily on the degree restrictions of these trees. Significant modifications would be required to apply this method to the problem of estimating the group order of an arbitrary tree of large order. This is due to the fact that for each n, there is a tree on n vertices which has (n - 1)! symmetries. Thus the series that counts symmetries in trees does not converge. BIBLIOGRAPHY [BaKP81] [BaKP83] [B74] [C57] [C75] [C81] [C89] [Et38] [GoK73] [GoK75] BIBLIOGRAPHY C. K. Bailey, J. W. Kennedy and E. M. Palmer, Points by degree and orbit size in chemical trees I, mm mm; (G. Chartrand et al, eds.) Wiley, New York (1981) 2 - 43. C. K. Bailey, J. W. Kennedy and E. M. Palmer, Points by degree and orbit size in chemical trees Il, placate MS (1983) 157 - 164. E. A. Bender, As mptotic methods in enumeration, SLAM M16 (1974) 85 - 515. A. Cayle , On the theory of the anal tical forms called trees. M (4) 13 (1857) 1 2 -176 - Math. E32915. Vol. 3, 242 - 246. A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, WW“ (1875) 257 - 305 = MafiLEapfls, Vol. 9, 427 - 460. A. Cayley, On the analytical forms called trees, Amer. W316; (1881) 266 - 268 - M Vol. 11, A. Cayley, A theorem on trees, W 13463111582 (1889) 376 - 378 - W, Vol. 13, I. M. H. Etherington, On non-associative combinations, ' 59 (1938/39) 153 - 162. M. Gordon and J. W. Kennedy, The grafih-Iike stateof matter, Part 2, LGCI schemes for the t ermod namlcs of alkanes and the theor of inductive in erence, , Farady II 69 1973) 484 - 504. M. Gordon and J. W. Kenned , The counting and coding7 of trees of fixed diameter, W28 (19 5) 376 - 398. 53 [GoL75] [GoT76] [H P73] [HRS75] [H59] [048] [Pa85] [P37] Anni Academic, London (1976). 54 M. Gordon andOC. G. Leonis, Combinatorial short-cuts to statlstlcal weights and enumeration of chemical Isomers, WWUWS) 231 - 238. M. Gordon and W. B. Temple, The gra h-like state of matter and polymer science, Cha ter 1 in W ' ' A. T. Balaban, ed.), F. Haray and E. M. Palmer, W, Academic, New York (1973). F. Haray, R. W. Robinson and. A. J. Schwenk, Twenty-step algorithm for determining the as m totic number of trees of various 5 ecies, Mn. W20 (1975) 483 - 5 3. E. Hille, MW, Vol. I, Ginn, Boston (1959). R. Otter, The number of trees, W49 (1948) 583 - 599. E. M. Palmer, Wm, Wiley, New York (1985). G. P6Iya, Kombinatorische Anzahlbestimmungen fijr Gruppen, Graphen und chemische Verbindungen, A5213 543111.68 (1937) 145 - 254. if? .-.—“--.?!