THCSI’L

This is to certify that the
thesis entitled
THE DISTRIBUTION OF POINTS BY DEGREE
AND ORBIT SIZE IN VARIOUS SPECIES OF TREES

presented by

Craig Kinder Bailey

has been accepted towards fulfillment
of the requirements for

Ph . D . degree in Mathematics

 

 

(giaanJSZ?fi‘ 721é§uzc,’e

Major professor

Date I; Ml“? qu‘

0-7639

 

 

 

OVERDUE FINES:
25¢ per day per item
RETURNING LIBRARY MATERIALS:

PIace in book return to remve
charge from ctrcuIetion records

 

 

 

 

 

THE DISTRIBUTION OF POINTS BY DEGREE
AND ORBIT SIZE IN VARIOUS SPECIES OF TREES

BY

Craig Kinder Bailey

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Mathematics

1981

ABSTRACT

THE DISTRIBUTION OF POINTS BY DEGREE
AND ORBIT SIZE IN VARIOUS SPECIES OF TREES

BY

Craig Kinder Bailey

Using generating functions and asymptotic techniques,
the probability that in a large random tree a point is of

degree r and in an orbit of size s is calculated.

Functional relations are derived for the enumeration
of d-trees, whose points have maximum degree d. An
asymptotic analysis of these equations enables us to
determine the distribution of points by degree and orbit
size in a large random d-tree. Results for d-trees are
readily converted to corresponding results for (l,d)—trees,

whose points only have degree 1 or d.

AC KNOWLEDGME NTS

I wish to thank my thesis advisor, Dr. E.M. Palmer,
for his time, patience, and most of all, for teaching me the

art of graphical enumeration.

I also wish to thank my wife, Trish, for her support

and encouragement in this endeavor.

ii

TABLE OF CONTENTS

INTRODUCTION 0 C O 0 C O O O O O O O O O Q 0

CHAPTER 1 ENUMERATION OF POINTS BY DEGREE
AND ORBIT SIZE IN TREES . . . .

1.1 Generating functions . . . . . . . . . .
1.2 Functional relations . . . . . . . . . .
1.3 Numerical values . . . . . . . . . . .
1.4 Arbitrary orbit sizes . . . . . . . . .

1.5 Asymptotic formulas . . . . . . . . .

CHAPTER 2 ENUMERATION OF POINTS BY DEGREE
AND ORBIT SIZE IN d-TREES . . . .

2.1 Introduction . . . . . . . . . . . . .
2.2 Trees of maximum degree d . . . . . .

2.3 Enumeration of points by degree and orbit
Size 0 O O O O O O O O O O O O O O O O O

2.4 Asymptotic formulas . . . . . . . . .

2.5 The correspondence between d-trees and
(l,d)-trees o o e e e e o o e I o o e

2.6 Asymptotic results for d = 3 and d = 4
CONCLUSION . . . . . . . . . . . . . . . . .

BIBLIOGRAPHY O O 0 O O O O O O O O O 0 O O O 0

iii

Table

Table

Table

Table

Table

Table

Table

LIST OF TABLES

Fixed points of degree r in rooted
trees.

Fixed points of degree r in unrooted
trees.

Asymptotic proportion of points in trees.

Asymptotic proportions of points in trees
of maximum degree 3.

Asymptotic proportion of points in
(l,3)-trees.

Asymptotic proportion of points in trees
of maximum degree 4.

Asymptotic proportion of points in

iv

14

15

22

43

44

45

46

INTRODUCTION

The enumeration of trees began with the work of
Cayley, who found exact formulas for the number of labeled
trees [C89], the number of rooted trees [C57], and the
number of unrooted trees [C75,C81]. Also motivated by
chemical applications, Polya [P37] extended these results
and studied the asymptotic behavior of these numbers.

In this thesis, the results of Cayley, Polya, and others
are refined to determine the proportion of points of

degree r and orbit size s in various species of trees.

The definitions used in this thesis are based on

Harary [H69], with the essential terms defined below.

A graph G of order p consists of a finite nonempty

set V of p points together with a specified set X

of q unordered pairs of distinct points. A pair

x = {u,v] of points in X is called a line of G

and x is said to lgig u and v. The points u and

v are adjacent; u and x are incident as are v and

x. The degree of a point is the number of lines incident
to it. It is standard practice to represent a graph as a

diagram and to refer to it as the graph.

A walk in a graph is an alternating sequence of
points and lines beginning and ending with points, in
which each line is incident with the two points
immediately preceding and following it. A walk is a
path if all the points, hence the lines, are distinct.
A walk is a cycle if the first and last points are the
same, all other points are distinct from these two and
each other, and all lines are distinct. A graph is
connected if every pair of points are connected by a

path.

A £323 is a connected graph with no cycles.
Alternatively, a tree is a connected graph in which
the number of lines is one less than the number of
points. A rooted tree has one point, called the £925,

distinguished from the others. Similarly, a line-rooted

 

tree has one line, called the root line, distinguished

 

from the others.

Two graphs, G1 and G2, 1

and V2 and edge sets X1 and X2 are isomorphic

with point sets V

 

if there exists a 1-l onto map w :V1 4 V such that

2
{u,v} 6 X1 e {¢u,¢v} 6 X2. Such a map ¢ is said to
ppreserve adjacency. In the counting of graphs, two

graphs which are isomorphic are considered the same

and therefore counted only once.

An automorphism of a graph G is a 1-l map
a from the point set of G onto itself that preserves
adjacency. The collection of all automorphisms of G
form a group, called the group of the graph and denoted

by T(G). The orbit size of a point u of G is the

 

cardinality of the set [du\d 6 F(G)].

All of the counting that follows uses the idea of

generating functions. Given a sequence al,a2,a3,---,

the formal power series

n
ax
n

EGB

A’x) =

n l

is said to be the generating function for the sequence

 

{an}. The generating functions for trees satisfy functional
equations, which permit the computation of the coefficients
using recurrence relations. The asymptotic analysis of
these coefficients is accomplished using Polya's lemma
[P37], and the twenty step algorithm in the paper by

Harary, Robinson, and Schwenk [HRS75].

CHAPTER I

ENUMERATION OF POINTS BY DEGREE
AND ORBIT SIZE IN TREES

1.1. Generating functions

Let Tp be the number of rooted trees on p
points and tp be the number of trees on p points.
Then the generating functions for rooted trees and for

trees are

(1.1.1) T(X) = '2': T xp
p=l p

(1.1.2) t(x) = '2: t xp .
p=l p

Cayley was the first to count rooted trees, he gave

the formula

m T
(1.1.3) T(X) = x n (1+xp+x2p+°°°) p
p=l
Each factor on the right corresponds to the selection of
any number of c0pies of a given rooted tree. The variable

x outside the product incorporates the new root point

to which all the roots of the trees selected are attached.

The cycle index of the symmetric group Sn is a
polynomial in the variables 31'52'°"'sn defined by
n jk

l .
2(sn> = 3—.- 33“” kI=Ilsk

where (j) = (j1,---,jn) and h(j) is the number of
permutations in Sn whose cycle decomposition determines
the partition (j). By Z(Sn,f(x)), I will mean the
result of substituting f(xi) for each variable si

in Z(Sn). New Z(Sn,f(x)) is the generating function
which counts combinations with repetition from the
objects counted by f(x). For example, Z(82,T(x))
counts unordered pairs of rooted trees and xZ(82,T(x))
counts trees rooted a point of degree 2. In general,

T(r)

define to be the number of rooted trees whose

root point has degree r, then

m (r) p
Z) T x
p=l p

(1.1.4) T(r)(x)

and we get

(1.1.5) T(r)(X)

XZ(Sr,T(x))

Then as observed by Polya [P37],

a:

T‘r’(x) = x 2 2(5 .T(x))
O r=O r

M8

(1.1.6) T(X) =

r

In 1948, Otter discovered the short formula for

trees

(1.1.7) t(X) = T(x)-z(s2,T(x))+T(x2)

Now Z(82,T(x)) counts unordered pairs of rooted

trees and hence line—rooted trees (simply join the

two roots by a line, making it the root line). The
series T(x2) counts pairs of rooted trees in which the
two parts are identical. These correspond to trees

with a symmetry line. Thus Otter's formula says that
the number of trees is equal to the number of rooted
trees minus the number of line-rooted trees plus the

number with a symmetry line.

Define Tp,j to be the number of rooted trees
of order p containing exactly j fixed points of
degree r, and tp,j to be the corresponding number for
unrooted trees. The generating functions for trees with
fixed points of degree r as an extra enumeration

parameter are

G)

p p j
(1.1.8) T(x.y) = Z) T -X y .
p=l i=0 p'3
m p p j
(1.1.9) t(x.y) = Z) Z) t -X y

p=l i=0 p'J

Note that T(x,l) = T(x) and t(x,l) = t(x). The

number of such rooted trees whose root point has degree

. (r)
d t d b T .
r 18 eno e y p 3

I

and the corresponding generating

function is

on p .
(1.1.10) T(r)(x,y) = Z Z T(rlxpyj .
p=l j=0 p'3

(r)(

Once again we have T(r)(x,1) = T x).

Define Fp to be the total number of fixed points

of degree r in all rooted trees of order p and f

P
to be the total for unrooted trees of order p.
p - d f 2% d
= T . an = 't . a
Note that Fp jEO 3 p.) p j=o j p.) n

therefore taking the partial derivative of T(x,y) with
respect to y and then setting y = 1 will yield

F(x), that is
(1.1.11) F(x) = Ty(X.l) .
and similarly

(1.1.12) f(X) = t (X.l) .

1.2. Functional relations

 

We seek formulas for T(x,y) and t(x,y) in order

to obtain F(x) and f(X) by differentiation.

Lemma 1.2.1 The series for rooted trees with fixed

 

points of degree r as an extra enumeration parameter

satisfies

 

(1.2.1) T(x,y) _T(r)(x,y) +1.(r),x'y)/y
F" T(r-.l)-1
m P ' p0]
= X 1'1 11 (1+XPYJ+1+XZP+ ...)
P=l i=0 31
:- (r)
p -_ T .
j=l ,j
fp . 2 T ._T(r-.l)_T(r).
II (1+Xpyj+x p+ ...) 9'3 PI] p.)
j=0

 

Proof. Equation (1.2.1) is an extension of Cayley's
formula for rooted trees (see [HP73],p.54). Inside the
first pair of square brackets, each factor represents the
selection of a set of isomorphic rooted trees with p
points and j fixed points of degree r whose root point
has degree r-l. When a single copy is chosen and the
old root is attached to the new root point, its degree is
increased by one to become r. Thus this unique branch
contributes j4—l fixed points of degree r. If more
than one copy is selected, none of its fixed points remain

fixed.

Inside the second pair of square brackets, each
factor represents the selection of a set of isomorphic
rooted trees with p points and j fixed points of
degree r whose root point has degree r. When a single
copy is chosen and the old root is attached to the new
root point, its degree is increased by one to become

r+-1. Thus this unique branch contributes only j-1

fixed points of degree r. If more than one c0py
is selected, none of its fixed points remain

fixed.

Inside the third pair of square brackets, each
factor represents the selection of a Set of isomorphic
rooted trees having p points and j fixed points
of degree r whose root degree is neither r nor
r-l. When the old root is attached to the new root

point, the number of fixed points of degree r is not

 

changed.

The new root point is accounted for by multiplying

the outside product by X.

The left hand side of flJZ.1) is not just T(x,y)
because while the new root point is fixed, its degree
is not known, and therefore not counted even in the

case when it has degree r. The prOper adjustment is

made by subtracting T(r)(x,y) and adding T(r)(x,y)/y. \\

The series t(x,y) for unrooted trees is conveniently

expressed if we define

(r-l) (r-l) (r) (r)

Q(X.y) =T(X.y)-T (x.y)-—T (X.y)+T

(x,y)+yT (X:Y)/Y -

The series Q(x,y) counts the root of degree r—l of
a rooted tree as a fixed point of degree r because when

such a rooted tree is attached to a new root point or root

10

line, the root degree is increased by one to r.
For a similar reason, it does not count a root point of

degree r as a fixed point of degree r.

Lemma 1.2.2 The series for unrooted trees satisfies

 

(1.2.2) t(X.y) = T(X.y)-Z(SZ.Q(X.y))+T(X2) .

31:29:. Following the idea of Otter [O48] , unrooted
trees can be counted by subtracting trees rooted at a
line from trees rooted at a point and then adding back
trees with a symmetry line. A tree rooted at a line can
be thought of as an unordered pair of rooted trees with
their root points joined to form the root line. NOw
Z(SZ,Q(x,y)) counts unordered pairs of rooted trees
keeping track of fixed points of degree r. In trees with
symmetry lines there are no fixed points, thus T(x2) is

sufficient to count these.

For reasons that will become clear later, define

(r-l) (r)

(1.2.3) 01(x) = Qy(x,l) = F(x)4—T (x)-T (x)

Note again that the r is suppressed.

Using the results of Lemmas 1.2.1 and 1.2.2 and
equations (1.1.11) and (1.1.12), the following two

theorems are obtained.

11

Theorem 1.2.1. The generating function for fixed

 

points of degree r in rooted trees is given by

(1.2.4) F(x) = T(r)(X)+T(X)[Ol(X) '01(X2”

Egggf. Formula (1.2.4) can be verified directly by
differentiation of (1.2.1) along with much algebraic
manipulation. On the other hand, an interpretive
argument such as we used in [BaKP—A] serves the same purpose.
On the right hand side of (1.2.4), T(r)(x) counts the
roots of degree r, which are fixed. Now 01(x) counts
fixed points of degree r in rooted trees, adjusting
for the cases when the root has degree r-l or r, as
has been explained before. Thus the product of T(x)
with 01(x) counts fixed points in individual branches
of rooted trees regardless of whether or not the branch
occurs elsewhere at the root. If the branch does occur
more than once, none of its fixed points remain fixed
and this contribution must be eliminated. Since 01(x2)
counts fixed points in one of two duplicate branches,
the product T(x) times 01(X2) is precisely that which

must be excluded. (\

Theorem 1.2.2. The generating function for fixed

 

points of degree r in unrooted trees is given by

(1.2.5) f(x) = T(r)(X)-(1+T(X))(01(X2)) .

12

Proof. Differentiation of (1.2.2) with respect

to y and setting y = 1 yields
(1.2.6) f(X) = F(x)-(T(x)Ol(x)4-Ol(x2)) .

Use of the formula for F(X) in (1.2.4) gives (1.2.5). (I

The form of f(x) in (1.2.6) lends itself to inter-
pretation in the following way. The number of fixed
points in rooted trees is counted by F(x). Now
T(x)Ol(x) counts fixed points on one side of the root
line in a line-rooted tree. The addition of 01(x2)
counts fixed points on the other side of the root line
when the two sides are identical. In this case, since
both endpoints of the root line are fixed, the fixed points
on both sides remain fixed. Note that there are no fixed
points in trees with a symmetry line. This alternative
proof is a refinement of Otter's method for counting

trees.

1.3. Numerical values

 

We can use formulas (1.2.4) and (1.2.5) to derive
recurrence relations for F and fp. Define Ak to be

P
the coefficient of xk in 01(X)-Ol(x2), that is

r (01) k odd
k

(1.3.1) Ak = <

 

) k even .

13

Then Fp can be expressed in terms of the Ak' k < p,
and the coefficients of T(r)(x) and T(x), both known

series, in the following equation
(1.3.2) F = T'

The recurrence relation for fp is expressed by first

defining Bk as follows

0 k odd

(1.3.3) Bk =<

 

(0 ) k even
L. 1 k/2

Then fp takes the following form

( 1 ) f ( pil
.3.4 = T - T B .
p p n=o n p-n

Results of the computations are contained in Tables 1 and 2.

l4

 

 

 

mmmmmo mmamama kmmmmmm ooOmmeeH Hmmmmaom mmmmmonm mmsvaame 0m
mamm mmmm mmovm oovmo amoeba hemmem onmvmm ma
ma mm mHH mmm 0mm mmma weed 0H
0 o o m e Ha Ha m
o o o o m e m e
o o o o o m m m
o o o o o o m m
o o o o o o o H
n o m e m m H u/m
.mmwuu owuoou CH H mmumwo mo quHOm omxflm .H mHQMB

15

 

 

omens mkNOHH mHHmmm HmHmmm mkanmm mmmnmov cmmekom cm
mmm mmm mmmm coco emmmH memom mmomH mH
m n mH me moH emH an 0H
0 o o H H m H m

o o o o H o o v

o o o o o H o m

o o o o o o o m

o o o o o o o H

k m m a m m H e/m

.momuu omuooucs CH H mmummo mo mucHom omxflh .N mHQMB

16

1.4. Arbitrary orbit sizes

For 5.2 2, let Os(x) be the generating function
for points of degree r in orbits of size s in rooted
trees. Note that O (x) does not count points of orbit

1

size 1 in rooted trees (see (1.2.3)).

Theorem 1.4.1. The generating function for points

 

in orbits of size s 2.2 in rooted trees is

(1.4.1) os(x) = T(xn 2 (ko k+l))1

k
—]<
k\s s/‘k(X ) Os/k(x

Proof. The essence of the proof is evident in the
case s = 4. The formula for s = 4 is
o (x) = T(x)[4O (x4)-4o (x5)+2o (x2)
4 l l 2

-202(x3) + 04(x) -O4(x2)] .

Consider each term separately. The product T(x)(4Ol(x4))
counts fixed points in one of a collection of four duplicate
branches at the root and multiplies this number by four
because these points will move in orbits of size four.

If five or more of these branches are present,
-T(x)(4Ol(x5)) subtracts the contribution. Similarly,
T(x)(202(x2)) counts points in orbits of size 2 in a set

of two duplicate branches and —T(x)(202(x3)) subtracts

them if the branch occurs three or more times. Finally,

l7

T(x)(O4(x)) counts points in orbits of size 4 in
individual branches and -T(x)(04(x2)) subtracts them

if the branch occurs more than once. 1)

For 5.2 l, the generating function for points
of degree r in orbits of size s in unrooted trees
is denoted by os(x). Note that ol(x) = f(x) is

already described in equation (1.2.5).

Theorem 1.4.2. The generating function for points

in orbits of size s 2_2 in unrooted trees is

(1.4.2) os(x) = os(x) - [T(x)os(x) +os(x2)]

O 5 odd ,
+

2
205/2(X ) 5 even

Proof. The idea of the proof is similar to that of
Theorem 1.2.2. By definition, Os(x) counts points of
orbit size s in rooted trees. Furthermore, it can be
seen that T(x)Os(x)4-Os(x2) counts points of orbit
size s in trees rooted at a line. Finally the last
term counts points in orbit size s in trees with a

symmetry line. )1

1.5. Asymptotic formulas
In this section asymptotic formulas for the expected
percentage of points of degree r in orbits of size s

are determined. For example, in orbit size 1, a formula

18

is needed for fp/ptp for large p, where fp is the
number of fixed points of degree r. The method used

here is based on the work of Otter [048] and Polya [P37].

Theorem 1.5.1. The limiting probability for fixed

 

points of degree r in trees is

 

2 2
(1.5.1) fp/ptp ~ “blz [nZ(Sr_l.T(n))-Ol(n )1

Proof. Robinson and Schwenk [R0875] observed that

th (I)

the p coefficient of T (x) is given by

(1.5.2) T(r)(x) ~ T(x)nZ(Sr_l,T(n))

Therefore it follows from the formula (1.2.5) for

f(x) in Theorem 1.2.2 that
(1.5.3) f(X) ~ T(X)[nZ(Sr_l.T(n))-01(n2)] .

Note that we are using the fact that 01(x2) is analytic

at x = n.

It follows from Otter's asymptotic formulas for

T and t that
P P

 

2
(1.5.4) T /pt ~
p p anZ

On combining (1.5.3) and (1.5.4) we have (1.5.1) (1.

19

P

The coefficient of x in the generating function

os(x) is denoted by (os)p.

Theorem 1.5.2. The limiting probability for points

 

of orbit size s 2_2 and degree r in trees is

 

2 _ k
(1.5.5) (os)p/ptp “1’12 {Enos/kw)
k+1 2
-Os/k(n )]-Os(n H

where the sum is over all divisors k of s with k # 1.

Proof. We begin by replacing the first appearance
of Os(x) on the right side of (1.4.2) by the alternate
expression (1.4.1) of Theorem 1.4.1. On simplifying

the results we find
(1.5.6) o (x) = T(x)g(x)4—h(x)

where g(x) and h(x) are both analytic at n and

 

k 2

(1.5.7) g(x) =Zk[OS/k(xk)-OS/k(x +1)]—Os(x)

where the sum is over all divisors k of s with k # 1.

It follows that

(1.5.8) os(x) ~ T(x)g(n) .

Once again, using (1.5.4), we have (1.5.5). I)

20

To get the asymptotic values from the formula
in Theorem 1.5.2, the coefficients of the Os(x) series
were calculated using recursive relations derived from
equation (1.4.1). The constant 2/nbl2 was calculated
using the known value of n from [R0875]. These values
are contained in Table 3. It is not hard to show that
these asymptotic values are exactly the same for rooted

trees, see, for example, [HP79, R0875].

Remember that the series os(x) has r, the degree
of the points being counted, implicit in its definition.

So define

(1.5.9) 65(x) = 230501) 5 = 1.2,...
Then
(1 5 10) E (f /pt ) = ——2— (1-6(n2)1
° ' r p p b 2 l
T] 1
and

(1.5.11) Erlms) /ptp

P

2

= —2-5 [2: HES/(Mk) -55/k(nk+l] 565(1) )

nbl
where the sum is over all divisors k of s with k # 1.
Then the sum of the right hand sides (1.5.10) and (1.5.11)
above for s = 2,3,... should equal 1. It can be verified

that this sum is

21

[1+5(n2) +5(n3) + ---l .

 

(1.5.12) 2

where

Now 6(x) counts the number of points of all degrees and
all orbit sizes in all rooted trees of order p, but this
is just pr. Thus 'O(x) = xT'(x). Thus (1.5.12) is equal

to

(1.5.13) 22 [1+ 2 T’mkmk]

T‘bl k=2

 

This eXpression equals 1 because the quantityzinside the
nb

bracket is the formula used to calculate 2; , (see

 

(9.5.27).p.213, (1113731).

22

 

 

Houm mommmo. co m eHHmmH. co m mmmmmm. co m «enema. Hmuop
~H1m mommkm. moum mmemmh. moum HomHmH. Noun HommmH. k
oHum mmvmmm. norm mmommH. worm mmmmHH. Norm okvnHo. o
mouu HoommH. worm mmmsvm. worm cmmmmk. Houm memHmH. m
woum 0mmmHH. moum mmmmvm. moum kmoHom. Houm mmooam. 4
menu «Nmmmm. more «OHOmH. moum monmm. Houm memHoo. m
moum cmmmkm. ~o(m omko~m. Houm Homkmm. oo+m kmmva. m
Houm weHmmo. oo+m kekmmH. oo+m mammom. oo+m kmkaH. H

e m m H mNHm

/anuo

.moouu cH mpcfiom mo COHDHOQOHQ UHuoumE>m<

.m OHQMB

23

 

 

oonm ommomm. Neum evkam. Norm cmmmmm. Houm mkmoom. Hmuop
Norm mmqmmH. mmum mkmmme. mHum mmmHmm. mHum mmmmmH. h
”cum okomHm. mHum qumkm. oHum ammmom. mHnm memoev. o
Houm mmmHmH. mHum ommmmH. mHim okHva. HHum mmkook. m
Heum mmHmmm. mH1m ekokmm. oHum onomH. moum mHomvH. a
Heum ommmmo. ocum nmmOmm. moum okmmom. worm mmommm. m
00 m mmomkH. ocum nmmmom. moum mkamv. voum cmmmme. m
00 m mmmnmo. Nona kmomHm. moum qummm. Houm ommmmm. H

Hmuop k m m mNHm

/anuo

1.6.ucoov

m OHQMB

.mwQ

CHAPTER 2

ENUMERATION OF POINTS BY DEGREE
AND ORBIT SIZE IN d-TREES

2.1. Introduction

The enumeration of trees constitutes an especially
important problem in the combinatorial aspects of
chemistry. The earliest molecular graph enumeration
occurs in the work of Cayley [C75] and concerns the
number of isomers of chemical compounds known as alkanes.
These are compounds of hydrogen and carbon which, for
chemical reasons have valencies l and 4 respectively.
The alkanes have the general formula CnH2n+2 and can
be represented by trees in which every point has degree
one or four, i.e. (1,4)-trees. The alkanes are significant
in chemistry because they are the best documented family of
compounds and provide a paradigm for much of chemical
theory [GoK73]. The (1,4)-trees are generalized to
(1,d)-trees, whose points have degree 1 or d, and these
find meaningful examples in polymer chemistry since, for
many problems, the detailed structure of a chemical unit

can be eliminated and the unit depicted simply as a point.

Closely related to (1,d)-trees are d-trees, whose
points have maximum degree d. For example, 4-trees

correspond to the carbon skeletons of alkanes [GoK73], and

d-trees, in general, to skeleton polymers, that is,

24

25

polymer molecules which have been stripped of their
reactive end-groups [GoT76]. In this chapter d—trees
will be analyzed since the correspondence between these
two types of trees observed in [GoK75] will, with some
refinements, yield results for (1,d)-trees from the

corresponding results for d-trees.

First, asymptotic formulas for the number of d—trees
of order p will be derived. Then the procedure of
chapter 1 for determining the number of points with both
specified degree and orbit size is applied. Finally, our

conclusions for d—trees are converted to (l,d)—trees.

In the averaging procedures used here, each tree
of order p receives equal weight. A more realistic
model for chemical reaction processes requires unequal
distribution of weights to reflect the not necessarily
equal proportions in which various trees are formed during

the process.

2.2 Trees of maximum degree d

Functional relations for the enumeration of trees
whose points have maximum degree d 2_3 are now determined.
The key steps are indicated in the twenty step algorithm
[HRS75] which produces an asymptotic estimate for the

number of these trees.

26

For fixed d.2 3, define three ordinary generating
functions to enumerate d-trees. Let R(x) count those
which are rooted at a point of degree g_d-l, and let
T(X) and t(x) count those which are rooted and unrooted

respectively.

Theorem 2.2.1. The generating functions for planted

(xR(x)), rooted (T(x)) and unrooted (t(x)) d-trees
satisfy
(2.2.1) R(x) = xZ(Sd_l,l4-R(x))
(2.2.2) T(X) = R(X)4-xZ(Sd,R(x))
2 2
(2.2.3) t(x) = T(X)-“5 (R(x) -R(x ))

Proof. Formulas (2.2.1) and (2.2.2) follow quickly
from Polya's Theorem [HP73,p.42] and (2.2.3) from Otter's

Theorem [HP73,p.56]. [[

The series for ordinary rooted trees has radius
of convergence n = .3383219... and its coefficients
bound those of R(x). Hence the radius of convergence
p of R(x) is at least as big as n. Furthermore it
follows from (2.2.1) that R(p) < w (Steps 3 and 4 of

[HRS75].

27

On carrying out Steps 5 — 7 of the twenty step
algorithm [HRS75] two important equations are obtained

which can be used to calculate p and R(p):

(2.2.4) R(p) pZ(Sd_1.l+-R(p))

(2.2.5) 1 = p2(sd_2.l+-R(p)) .

It follows from (2.2.4) and (2.2.5) that

Rm)< w-lLMd-2)S2-

After completing Step 13, p is a branch point
of order 2 for R(x) and R(x) can be expressed in the

form

1/2

(ZJJH Rm)=15—blm-x) +bflp—xfl4...

O

Of course bO = R(p).

The next objective is the determination of b by

1

means of Step 15. The process is simplified substantially

by the following identity.
Lemma 2.2.1.

d

k .
a; Z(Sk,1+R(x)) = Z; R'(x )x ' 2(s

k_i.l+R(X))

Proof. The result follows from the fact that for

i = 1 to k

28

 

Since R(x) can be written in the form of (2.2.6),
so can Z(Sm,14-R(x)). The next lemma to smooth the path
gives the coefficient of (p-—x)1/2 in Z(Sm,l4-R(x)).

The idea was used on trees in [RoS75, formula 30 p.368].

1/2

Lemma 2.2.2. If R(x) = R(p)-bl(p-x) + ...,

 

then the coefficient of (p-—x)l/2 in Z(Sm,l+-R(x))

is -b Z(S
m

l .l4—R(p)).

-l

jk

Proof. Consider a typical term Hsk

in Z(S ). If
j m
j = O, on substitution of l4-R(x) in n s
1 j k=2 k
H (la—R(xk)) k which is analytic at x = p and hence
k=2
there is no contribution to the coefficient. But if jl # O,

jl—l

we have

3
11(1+Ru}))k.
k=2

Therefore the total contribution from Z(Sm) is

the contribution is -bljl(l4-R(p))

a k . .
—bl(S;-]:'Z(Sm))[sk 4 l4-R(p )] which equals the expre531on
in the lemma. ((

Now we obtain two expressions for the derivative

of R(x). The first comes from (2.2.6):

'l/Z-b +...

(2.2.7) R'(x) =-21-b1(p-x) 2

where the terms omitted involve non-negative powers of

(p-x).

29

The second form of R’(x) is derived from (2.2.1)
and the process is facilitated by using Lemma 2.2.1.

After some simplification we find

(2 2.9) R’(x)E(x) = %(R(x)/x

d-l
+ Z) R'(xk)XkZ(S
k=2

d_1_k.l+R(X))]

where

E(x) = l/x-Z( l4-R(x))

Sd-2’

It follows directly from (2.2.5) that E(p) = 0. Therefore

when E(X) is expressed in powers of (p-x), we have
(2.2.9) E(X) = el(P-X)l/2+e2(p-x)+... ,
and from Lemma 2.2.2 we find

(2.2.10) = blZ(S l4—R(P))

e1 d-3'

On multiplying (2.2.9) and (2.2.7), R'(x)E(x) =

1
E'blel+ °'°

, where the terms omitted involve (p-x)k, k > 0.
Therefore %-b

lel must also be obtained by taking the

limit as x 4 p- on the right side of (2.2.8). Replace

e by the right side of (2.2.10) to get

1

30

2

.1
2 1

(2.2.11)

Z(S 1+R(P))

d-3'

l (1.1 I k k
= '5{R(p)/p+k2;2 p. (p )p 2(sd_l_k.1+R(p))) .

Once p has been calculated from (2.2.4) and (2.2.5),

bl can be obtained from (2.2.11).

Now we are ready to estimate the coefficients of
T(x) asymptotically (step 17). No particular difficulties

are encountered here. Lemma 2.2.2 is again employed to find
(2.2.12) T(X) = (l-x/p)l/2gl(x)+hl(x)

where gl(x) and hl(x) are analytic at x = p and

gl(p) = -blR(p)pl/2

and h1(p) = T(p). The next theorem
follows from applying Polya's lemma [HRS75,p.489] to

(2.2.12).

Theorem 2.2.2. The asymptotic behavior of the

number Tn of rooted d-trees is given by

b p1/2 -3/2

Tn ~ _l_. R(p)p—n n .
2 W

Note that the form of this result is almost identical
to that for ordinary rooted trees (recall that T(n) = l

for these [HP73,p.213]).

31

By similar means, it is found that

1/2
b P _
Rn ~ 1 p n n 3/2 .
24/7?
Finally, consider unrooted trees (step 18). The

process of preparing t(x) for an application of Polya's
lemma is similar to that for ordinary trees but the

details are substantially more complicated. Here both the
first and second derivatives of t(x) are required. Lemmas
(2.2.1) and (2.2.2) play an important role and several

key substitutions are made using formulas (2.2.4),

(2.2.5), (2.2.10) and (2.2.11). When the analytic

verifications are completed we find

(2.2.13) t(x) = (l-x/p)3/Zgz(x)4-h2(x)
where g2(x) and h2(x) are analytic at x = p, h2(p) = t(p)
and
b3
(2.2.14) 92(9) = 7%'PS/ZZ(Sd_3.14-R(p))

Now Polya's lemma can be applied to (2.2.13).

Theorem 2.2.3. The asymptotic behavior of the
number tn of d—trees is given by
bi
(2.2.15) tn ~ -——-p
w

5/2 5/2

Z(Sd__3,l-(-R(p))p—n n- .

32

The form of this result compares favorably with the
asymptotic formula for ordinary trees [HP73,p.214] because

for large d, xZ( ,l4-R(x)) is much like T(X) and

Sd-3
T(p) will be nearly equal to l.

2.3. Enumeration of points by degree and orbit size
The techniques developed for trees, with some
modifications, can be applied to calculate the number

of points of degree r and orbit size s in d-trees.

Define F(x) to be the generating function for
the number of fixed points of degree r = O to d in
d-trees rooted at a point of degree g_d-1. Note that
the parameter r is suppressed. Also define for

r=O to d-ll

(2.3.1) 01(x) = F(x).-T(r)(x)+-T(r‘l)(x) ,
and for r = d,
(2.3.2) 01(x) = F(x)4—T(d—l)(x).

(r)

In the definition of 01(x), T (x) is subtracted
and T(r-l)(x) is added because the degree of the root

goes up by one when it is attached to a new root point.

33

Lemma 2.3.1. The generating function for fixed

 

points of degree r = O to d-1 in d-trees rooted

at a point of degree g_d-l satisfies

(2.3.3) F(x) = T(r)(x)+Ol(X)[R(X) -T(d'“(x)]

- 01(x2) [R(X) - T(d'l) (X) - T(d—Z) (X)]

and for r = d,

(2.3.4) F(x) = ol(x)[R(x) -T‘d’l)(x)1
- 01(x2)[R(x) -T‘d'1’(x) -T‘d'2)(x)1
(r)

Proof. The term T (x) counts the roots of

degree r which are fixed. The product 01(x)[R(x)-T(d—l)(x)]
counts fixed points in individual branches. The factor
R(x)-—T(d-l)(x) counts d—trees rooted at a point of
degree g_d-2 and is needed to keep the degree of the
root g_d-—l when a line is attached to the root. If the
branch occurs elsewhere at the root, no points are fixed.
The term 01(x2)[R(x)-T(d-1)(x)-T(d-2)(x)] counts
fixed points in one of two duplicate branches and this

is exactly what must be eliminated. \(

*
Define F (x) to be the generating function for
the number of fixed points of degree r = O to d in d-trees

*
rooted at a point of degree g_d. Then F (x) satisfies

34
(2.3.5) F*(x) = T‘r)(x)+01(x)[R(x)]
-0 (x2) [R(x) -T(d-l)(X)]

1

Lemma 2.3.1. The series ol(x) which enumerates

 

fixed points of degree r in d—trees satisfies

(2.3.6) ol(x) = fun - [01(x)R(x) +01(X2”

nggf. Using the method of Otter [O48], observe
that F*(x) counts fixed points in rooted d-trees.
The term Ol(x)R(x) counts fixed points on one side
of the root line in line-rooted trees. When both sides
of the root line are the same, 01(x2) counts the fixed
points on the other side. Points on both sides of the root
line can be fixed in this case because the endpoints of the
root line are always fixed. There are no fixed points in

trees with a symmetry line. i]

 

Theorem 2.3.1. The series Os(x) which counts points
of degree r and orbit size s 2_2 in d-trees rooted at

a point of degree g_d-—l satisfies

(2.3.7) Os(x) = Z)[[xZ(Sd_l_k,l+R(X))]kOS/k(xk)

1

k(s

k+1

- [xZ( l+R(x))kO )]

Sd—Z-k' s/k(x

35

2399:. The proof is analagous to the proof of
Theorem 1.4.1 for rooted trees. The change here is that
the degree of the root to which the branches are attached
must be limited so that the root degree reamins g_d-l

after counting the contributions made by the branches. [1

*
Define Os(x) to be the series for points of degree
r and orbit size s 2.2 in d-trees rooted at a point of
degree ng. This series satisfies
9:
(2.3.8) Os(x) — k§;([xZ(Sd_k

,l+—R(x)]sOS/k(xk)

k+l)}

- [xZ(Sd_l_k,14-R(x)]kOs/k(x

Theorem 2.3.2. The series os(x) for points of

degree r and orbit size s 2.2 in d—trees satisfies
239) )-o*) 0 )R()0(2
( . . os(x — s(x -[ S(x x 4- s x )]

O 5 odd
+

2
205/2(x ) 5 even .

Proof. The proof is the same as for Lemma 2.3.2
except for the last term. In trees with a symmetry line,
there are no points of odd orbit size. Points of orbit
size s for 5 even arise from points of orbit size
s/2 in each of the identical rooted trees on both sides

of the symmetry line.

36

2.4. Asymptotic formulas
In order to determine the asymptotic formulas for
points of degree r and orbit size s in d-trees, the

following observations are useful, they follow from Lemma

2.2.2.

 

(2.4.1) xZ(Sn,14-R(x)) ~ R(x)pZ(Sn_l,l+-R(p))
2 l l
o o R t ~ — o . —

Theorem 2.4.1. The limiting probability for fixed
points of degree r is
__L_. 1
(2.4.3) (ol)p/'pt -

P pblz Z(Sd_3.l+R(P))

[Z(Sr_l.l+R(p) -Z(Sd_3.1+R(p)) '01("2”

Proof. Using (2.4.1), an asymptotic formula for

ol(x) can be derived from (2.3.6). Then divide both

sides by Rp and multiply by the constant Rp/ptp (2.4.2)

to obtain (2.4.3). ((

The next theorem extends this result to all higher

orbit sizes.

Theorem 2.4.2. The limiting probability for

points of degree r and orbit s 2_2 is

37

 

2
(2.4.4) (o ) /pt '~---
s p p pbl2
1 [ZJ([z<s 1+R( ))1ko (pk)
Z(Sd_3.1+R(p) d-l-k' p s/k

k+l
[Z(Sd_2_k,l+R(p)]kOs/k(p )}

_ 2(sd_3.1+R(p))os(p2)1 .
where the sum is over all divisors k:of s Mdth.k # l.
nggf, The term 0;(x) in (2.3.9) is first replaced
by (2.3.8), then (2.4.1) is applied to find the asymptotic
formula for (os) . The final form is found by dividing
both sides by RPp and multiplying by the constant

R t (2.4.2 . I)

It can also be shown that the sum of the asymptotic
expressions (2.4.3) and (2.4.4) over all r and s is 1.

The proof is similar to the one given for trees.

2.5. The correspondence between d-trees and (1,d)-trees
The correspondence between d-trees and (1,d)-trees

observed in [GoK75] is given and then a refinement of this

matching is used to transform the results of Sections 2.2,

2.3, and 2.4 to (1,d) trees.

Let T* be a (1,d)-tree of order m. Then

(2.5.1) m

ml+md

*
where mi is the number of points in T of degree i l,d.

Since ml-I-dmd = 2(m-1), we also have

38

QJLZ) ml=(mm-2)+N/wel)

on eliminating md in (5.1), and similarly
(2.5.3) m. = (m-—2)/(d-1)

Thus the asymptotic probability that a random

point in a (1,d)—tree has degree 1 is (d-2)/(d-1).

*
Each (1,d)-tree T of order m corresponds to
the d—tree T obtained by deleting all m end-points
*
of T . Hence, if we denote the order of T by n, then

n = md. On substitution in (2.5.3) we have

(2.5.4) m = (d-1)n4-2

Thus the number tn of d-trees of order n equals

*
the number tm of (1,d)-trees of order m = (d-1)n4-2,

o * - I e
i.e. tm - t(m-2)/(d-1)' If we abbrev1ate equation (2.2.15)

-n n-5/2

of Theorem (2.2.3) as t ~ cp , then an asymptotic

n
I * I
eXpre551on for tm can be written as

* 2 Cp-(m-2)/(d—l) )-5/2

(m-2
m d-l

(2.5.5) t

Polya derived (2.5.5) for d = 4 in his pioneering

paper on chemical compounds [P37].

39

Now we let ni be the number of points of degree 1
d
in the d-tree T for i = l to d. Then n = Z) ni
i=1
and therefore

(2.5.6) md = .21 ni
i=1

Furthermore, it is easy to see that

d—l
(2.5.7) m = E (d-i)n.
1 i=1 1
because each point of degree i in T must have had

d-i end lines deleted from T*.

Equations (2.5.6) and (2.5.7) can be refined to

convert the numbers by orbit size as well as degree. Let
ni j be the number of points in T of degree 1 and
orbit size j. Similarly ml j and md j are the numbers

*
of points in T of orbit size j, and degree 1 and
d respectively.

*
The points of degree d and orbit size j in T

are precisely those of orbit size j in T. Therefore
for j = l to m
(2.5.8) m. . =

d,j i

ni..
1 '3

d
As for ml j' consider any point v of T with

deg v = d-k in T so that k end points are adjacent

*
to v in T . If these end points are in an orbit of size

40

'k
j in T , then ki = j where i is the size of the

orbit of v in T. Therefore each point v of T

in an orbit of size 1 = j/k contributes k to m1 j'
On summing over the divisors of j we have j = l to
m1

(2.5.9) ml,j = kgg knd-k,j/k .

Now let Ni j be the total number of points of degree

I

i and orbit size j in all d-trees of order n and
similarly Mi,j stands for the same number in the (1,d)-trees
of order m = (d-l)n4-2. Then equations (2.5.8) and

(2.5.9) hold when m and n are replaced by M and N.

By definition the asymptotic probability Bi,j that

a random point in a d-tree has degree i and orbit

size j is

(2.5.10) ni,j = ii: Ni,j/ntn .
Similarly
..... '1:
(2.5.11) mi,j = ii: Mi'j/mtm
The relations between the 'Ei j and 'Ei,j are

summarized in the follow1ng theorem.

41

Theorem 2.5.1. The asymptotic probabilities

 

m for points of degree i and orbit size j in

i,j
(1,d)-trees are expressed in terms of the corresponding

probabilities lhi j for d-trees by the equations

(2.5.12) m . = -——- Z} n. .
and
(2.5.13) '5 . = —l—- Z) k—

n . .
1, d-l -. d-k,
J R(J J/k

Proof. The proof is just a matter of substitution.
*
Begin with (2.5.11), recall that tm = tn where m = (d-l)n+-2
and apply (2.5.8) with M,N to get (2.5.12), or (2.5.9)

to get (2.5.13). ((

2.6 Asymptotic results for d = 3 and d = 4

The coefficients of R(x) were calculated using a
recurrence relation derived from (2.2.1). Then the values
of p and R(p) were determined from (2.2.4) and (2.2.5),
with R(pz) and R(p3) being evaluated directly because

p2 and p3, being less than p, are inside the radius

2 1

pblz Z(Sd_3'l+R(p))
was evaluated as the reciprocal of the right hand side

of convergence. The expression

of the expression (2.2.11). The coefficients of the
series 01(x), 02(x),... , were calculated from recurrence

relations derived from (2.3.1), (2.3.2), and (2.3.7).

42

Note that for d = 3, Os(x) = 0 unless s = 2m,

m = 0,1,... ; for d = 4, Os(x) = 0 unless s = 2 3 ,
m,n = O,l,2,... . These facts are reflected in Tables
4, 5, 6, and 7 giving the asymptotic results for d—trees

and (1—d) trees.

43

 

 

Ho+m oooooH. oo+m memoOm. oo+m mmmomm. oo+m mOmoOm. Houoe
meta Noemoe. HHnm mmmoom. more ammomm. more mHmmoe. m
Noun mmOeom. monm ommmom. mosm mHoooH. moum mHeHmm. o
oo+m oooONH. Norm Hoomem. Houm oonON. Honm vmmeoo. N
oo+m Hmwmem. oo+m neOmOm. oo+m mmmoom. oo+m mNNeON. H
Houoe m m H oNHm
/anno

.m omhmwo EDEHxME mo

moouu CH mucflom mo mcofluuomoum Ufluoumewmd

.w mHDMB

44

 

 

Ho+m oooooH. oo+m ooOOOm. oo+m OOOOOm. Houop
mere mHmmoe. moum mHmmoe. oH
Norm monmm. norm Hemmmm. Norm onHmm. m
Honm omoooo. Norm ommmmm. Heum HOmmoo. o
oo+m mmookm. Houm mnemoo. oo+m ommeHN. m
oo+m omHONo. oo+m mHoomo. oo+m oommmH. H
Hmoop m H oNHm
.ooo/oHnno

.momuule.Hv CH mucHom mo cofluuomoum UfluouQENmfi .m magma

45

 

 

Ho+m OOOOOH. HOIm mmommm. oo+m mmmhma. oo+m mmbomm. oo+m mmOmmm. Hmuoa
noun vapomm. mmlm omhmhm. balm mmavva. «Him mmohmm. helm Ombmmm. NH
celm moboOH. hHIm mOmohh. mHIm mammom. mOIm mommmm. voum mmoooH. m
mOIm oommmm. oHIm mmmmwm. «Him Hmmmam. mOIm mmmmvm. mOIm Hoommm. m
NOIm vaHNH. Halm ommgmm. mOIm Ommmmv. mOIm ommowm. Noun thHmH. 0
meta mmmomm. hOIm omohom. moum HOmhoH. monm mmhmOH. NOIm mummmm. v
HOIm Nmomog. mOIm Common. worm wmgvmm. Nonm hmhmma. Helm hmammm. m
oo+m NmmabH. mOIm wmmmHo. NOIm NHHth. HOIm hmvmvm. oo+m mmOmVH. N
OO+m Hobomh. HOIm hHfiVNm. OO+m mommma. oo+m mmmOOm. OO+m mOvaH. H
HMUOB v m N H muwm
.ooo/anno
.v omummo EDEHXME mo mommy CH mucflom mo Goauuomoum oauoumfi>m¢ .o magma

46

 

 

OO+m Nmmmmm. oo+m mmmmmm. oo+m mmmmoo. Hmuoe
monm mbHHNH. mH
Noun mvHohm. helm mammmm. Noum mvHOhm. NH
HOIm mmmmmm. mOIm hmommm. HOIm bmHmmm. m
monm womHOm. mOIm mHmmOH. mOIm mmmHmo. m
OO+m NwhvoH. moum Omhvow. oo+m hmmva. o
HOIm vthmH. NOIm mOmmmH. HOIm mmmMOH. w
oo+m mmthN. Helm OHNoMH. oo+fi hMvaH. m
oo+m mommmm. HOIm hOHHbm. oo+m mmNHON. N
oo+m mHmwmm. OO+m hmmoom. HOIm momooo. H
Hmuoe o H mNHm
.mmn/HHQHO
.mmmHuIH¢.HV :H mucHom mo COHuuomoum UHuoumfimmd .h mHnme

CONC LUS ION

It is hOped that the methods and results developed
in this thesis can be applied to a much wider range of
problems than those treated here. Of course, the
degree and orbit size distribution of points can be
found for many other species of trees (see [HPr59]),
but the asymptotics for centered and bicentered trees

may also yield to a similar analysis.

47

BIBLIOGRAPHY

[ BaKP-A]

[Ba-S]

[C57]

[C75]

[C81]

[C89]

[GoK73]

[GoK75]

BIBLIOGRAPHY

C.K. Bailey, J4W. Kennedy and E.M. Palmer,
Points by degree and orbit size in chemical
trees I, Proc. 4th Int. Conf. on the Theory
and Applications of Graphs (Y. Alavi 33 31.,
eds.) Wiley, New York, to appear.

C.K. Bailey, Distribution of points by degree
and orbit size in a large random tree, g;_
Graph Theory, submitted.

A. Cayley, On the theory of the analytical forms
called trees, Philos. Mag. (4) 13 (1857)
172-176 = Math. Papers, Vol. 3, 242-246.

A. Cayley, On the analytical forms called trees,
with application to the theory of chemical
combinations, Rep. Brit. Assoc. Advance. Sci.

45 (1875) 257—305 = Math. Papers, Vol. 9,
427-460.

 

A. Cayley, On the analytical forms called trees,
Amer. J. Math. 4 (1881) 266-268 = Math. Papers,
Vol. 11. 365-367.

A. Cayley, A theorem on trees, Qpart. J. Pure.
Appl. Math. 23 (1889) 376-378 = Math. Papers,
V01. 13’ 26-28.

M. Gordon and J. W. Kennedy, the graph-like
state of matter, Part 2, LCGI schemes for the
thermodynamics of alkanes and the theory of
inductive inference, J. Chem. Soc., Farady II
69 (1973) 484-504.

M. Gordon and J.W. Kennedy, The counting and

coding of trees of fixed diameter, SIAM J.
Appl. Math. 28 (1975) 376-397.

48

[GOL75]

[GoT76]

[H6 9]

[HP73]

[HP-A]

[HP7 9]

[HPr59]

[HRS75]

[048]

[P37]

[RoS75]

49

M. Gordon and C.G. Leonis, Combinatorial

short-cuts to statistical weights and enumeration

of chemical isomers, Proc. 5th British Combinatorial
Conf. (1975) 231-238.

M. Gordon and W.B. Temple, The graph-like state

of matter and polymer science, Chapter 10 in
Chemical Applications of Graph Theory (A.T. Balaban,
ed.) Academic, London, 1976.

F. Harary, Graph Theory, Addison-Wesley, Reading,
Mass. (1969).

F. Harary and E.M. Palmer, Graphical Enumeration,
Academic, New York, 1973.

F. Harary and E.M. Palmer, Orbits in random
trees, Ann. N.Y. Acad. Sci., to appear.

F. Harary and E.M. Palmer, The probability that
a point of a tree is fixed, Math. Proc. Cambridge
Philos. Soc. 85 (1979) 407-415.

F. Harary and G. Prins, The number of homeo-
morphically irreducible trees, and other species,
Acta Math. 101 (1959) 141-162.

F. Harary, R.W. Robinson and A.J. Schwenk,
Twenty-step algorithm for determining the
asymptotic number of trees of various species,
J. Austral. Math. Soc. Ser. A 20 (1975) 483-503.

R. Otter, The number of trees, Ann. of Math.
49 (1948) 583-599.

 

G. Polya, Kombinatorische Anzahlbestimmungen
fur Gruppen, Graphen und chemische Verbindungen,
Acta Math. 68 (1937) 145-254.

R.W. Robinson and A.J. Schwenk, The distribution
of degrees in a large random tree, Discrete Math.
12 (1975) 359-372.