.PH ""
.EQ
delim $$
gsize 10
define pprime % size 10 prime %
define as % roman "as" %
.EN
.ds HP 10 10 10 10 10 10 10
.am DE
.sp
.ls 2
..
.nr Pt 1
.nr Au 0
.ce 99
.B
Asymptotic expansions for the coefficients
of analytic generating functions
.R
.sp
by
.sp
.I
A. M. Odlyzko
.R
Bell Laboratories
Murray Hill, New Jersey 07974
USA
.sp
and
.sp
.I
L. B. Richmond
.R
University of Waterloo
Waterloo, Ontario N2L 3G1
Canada
.sp 1.5
.I
Abstract
.R
.sp 1.5
.ce 0
.P
Pairs $F(x)$, $G(x)$ of analytic
generating functions that satisfy
relations such as
$1+G(x)~=~exp (F(x))$ are studied.
It is shown that if $F(x)$ satisfies
fairly mild regularity conditions,
such as those imposed by Hayman in
his study of coefficients of
some general classes of functions,
then $G(x)$ satisfies the much
stricter conditions
imposed by Harris and Schoenfeld.
This enables one to obtain complete
asymptotic expansions for the
coefficients of $G(x)$.
Applications of this result are made
to enumerations of trees.
.bp
.ce 99
.B
Asymptotic expansions for the coefficients
of analytic generating functions
.R
.sp
by
.sp
.I
A. M. Odlyzko
.R
Bell Laboratories
Murray Hill, New Jersey 07974
USA
.sp
and
.sp
.I
L. B. Richmond
.R
University of Waterloo
Waterloo, Ontario N2L 3G1
Canada
.sp 2
.ce 0
.H 1 Introduction
In enumerative combinatorics one quite
often encounters pairs of generating
functions $F(x)$ and $G(x)$ related by
.nr Eq 1
.DS 3
.EQ (1.1)
1+G(x)~mark =~
exp "{" F(x) "}"
.EN
.sp
.EQ "or by"
~~~
.EN
.sp
.EQ (1.2)
1+G(x)~lineup =~
exp "{" sum from {n >= 1}~ F(x sup n ) /n "}"~.
.EN
.DE
.nr Eq 0
.PH "''- \\\\nP -''"
.nr P 1
(Bender and Goldman [3] present an explanation
of this phenomenon.)
When the radius of convergence of $F(x)$ is 0,
an asymptotic expansion for the coefficients
of $G(x)$ can often be obtained from that of
$F(x)$ by the techniques of Bender [2],
Bender and Richmond [4], or Wright [12].
When the radius of convergence of $F(x)$ is
positive and $F(x)$ has only a finite number of
algebraic
singularities on its circle of convergence,
the method of Darboux can often be successfully
applied [1, Section 6].
When the circle of convergence is a natural
boundary, or when $F(x)$ is an entire function,
these techniques do not apply.
However, the methods of Harris and Schoenfeld [8]
and Hayman [10] can frequently be applied.
Hayman [10] obtained rough asymptotic expansions
for the coefficients of a wide class of analytic
functions satisfying fairly mild regularity
conditions, which he called admissible functions,
and which we will refer to as $H$-admissible
functions.
Harris and Schoenfeld [8] studied analytic
functions satisfying considerably more stringent
regularity conditions (we will refer to them
as $HS$-admissible functions) and obtained for
the coefficients of these functions complete
asymptotic expansions.
Harris-Schoenfeld type expansions do not hold
for all $H$-admissible functions, so that it
was necessary for those authors to impose more
restrictive conditions
in order to obtain their results.
.P
Our first result shows that if $F(x)$ is
$H$-admissible, then $exp ( F(x) )$ is
$HS$-admissible, and so one can obtain complete
asymptotic expansions for the coefficients of
$G(x)~=~exp (F(x))-1$.
This result follows quickly from some results
of Hayman [10].
We give some applications of this result, namely
to the estimation of the Bell numbers and of the
number of idempotent elements in the symmetric
semigroup on $n$ elements [9].
In these examples $F(x)$ is entire.
.P
Our main application is to the estimation of
$t sub h,n$, the number of rooted unlabelled
trees with height $h$ and $n$ vertices, where
$h$ is held fixed and $n$ varies.
(This problem was solved earlier by M. Yamashita [14].)
We also state the analogous results for other
tree-counting problems solved by Po\*'lya
enumeration theory.
In these applications, with generating
functions related by (1.2), the circle of
convergence is typically a natural boundary.
.P
Our results are largely of methodological interest.
We do not state many general results since
we cannot hope to cover all the cases of interest.
Instead, we present several examples which show
how the powerful machinery developed by Hayman
and by Harris and Schoenfeld can be used to
quickly obtain very precise enumeration results
in many interesting combinatorial problems.
.P
Results that are somewhat related to those
of this paper are contained in [6],
which obtains asymptotic estimates for
coefficients of sequences of polynomials
defined by nonlinear recurrences such as
.DS 2
.EQ
B sub h+1 (x)~=~
1+x B sub h (x) sup 2 ~~~for~~h~>=~0 ~,~~~
B sub 0 (x)~=~1~.
.EN
.DE
.B
.H 1 "$H$-admissibility and $HS$-admissibility"
.R
For the sake of completeness and convenience
we state here those results of Hayman [10]
and then of Harris and Schoenfeld [8] that
we require.
(The results we state are slightly weaker
and phrased differently from those of [8,10].)
Hayman defines a function $f(x)$, analytic
for $| x |~<~R~<=~inf$ and real for real $x$,
to be admissible (we say $H$-admissible)
provided there is some
$R sub 0~member~[0,R)$ such that for some
function
$delta (r)$, defined in the range
$R sub 0~<~r~<~R$ to satisfy $0~<~delta (r)~<~pi$,
the conditions
I), II) and III) below are satisfied with
.DS 2
.EQ
a(r)~=~r~{f prime (r)} over f(r)~,~~~
b(r)~=~
r~{f prime (r)} over f(r)~+~
r sup 2~
{f prime prime (r)} over f(r)~-~
r sup 2~
left (
{f prime (r)} over f(r) right ) sup 2~.
.EN
.DE
.nr Eq 1
.DS 2
.EQ I)
f(re sup {i theta} ) ~wig~
f(r)e sup {i theta a(r)- theta sup 2 b(r)/2}~~~~~~
as~~r~->~R
.EN
.DE
uniformly for $| theta |~<=~delta (r)$;
.DS 2
.EQ II)
f(r e sup {i theta } )~=~o
(f (r) b(r) sup {- half} ) ~~~~~~as~~r~->~R
.EN
.DE
uniformly for $delta (r)~<=~| theta |~<=~pi$;
and
.DS 2
.EQ III)
b(r) ~->~inf~~~~~~as~~r~->~R~.
.EN
.DE
.I
Theorem 1
.R
(Hayman).
.I
If $f(x)$ is $H$-admissible,
.DS 2
.EQ
f(x)~=~sum from n=0 to inf~a sub n x sup n~,
.EN
.DE
then
.DS 2
.EQ
a sub n~wig~
{f(r sub n )} over
{r sub n sup n sqrt {2 pi b ( r sub n )}}~~~~~~as~~
n~->~inf~,
.EN
.DE
where $r sub n$ is defined for large $n$ by
$a(r sub n )~=~n$,
$R sub 0~<~r sub n~<~R$.
.R
.P
It is clear that a combinatorial generating
function will be real for real $x$ and by
using the following theorem of Hayman [10]
it is often very easy to show that a
generating function is $H$-admissible.
.sp
.I
Theorem 2
.R
(Hayman).
.I
Let $f(x)$ and $g(x)$
be $H$-admissible in
$| x |~<~R~<=~inf$.
Let $h(x)$ be regular in
$| x |~<~R$ and real for
real $x$.
Let $p(x)$ be a polynomial
with real coefficients.
.sp
i) If the coefficients $a sub n$
of the power series
$exp "{" p(x) "}"$ are positive
real numbers for all sufficiently
large $n$, then $exp ( p(x) )$
is $H$-admissible in $| x |~<~inf$.
.sp
ii) $exp (f (x) )$ and $f(x)$ $g(x)$
are $H$-admissible in $| x |~<~R$.
.sp
iii) If for some $epsilon~>~0$,
$max | h(x) |~=~O (f(r) sup {1- epsilon} )$,
where the maximum is over all $x$ such
that $| x |~=~r~<~R$, then $f(x)~+~h(x)$
is $H$-admissible in $| x | ~<~R$.
In particular $f(x)~+~p(x)$ is $H$-admissible
in $| x |~<~R$ and, if the leading coefficient
of $p(x)$ is positive, $p(f(x))$ is $H$-admissible
in $| x |~<~R$.
.R
.P
Thus it very easily follows from i) that
$e sup x$ is $H$-admissible, from iii) that
so is $e sup x ~-~1$ and finally from ii) that
$exp (e sup x -1)$ is $H$-admissible.
.P
We say a function $f(x)$ is $HS$-admissible
provided it satisfies the following conditions of
Harris and Schoenfeld in addition to being
analytic for $| x |~<~R$,
$0~<~R~<=~inf$ and being real for real $x$.
.sp
A) There exists an
$R sub 0~member~(0,R)$ and a $d(r)$ defined
for all $r ~member~(R sub 0 , R)$ such that
we have
.DS 2
.EQ
0~<~d(r)~<~1,~~~
r "{" 1+d(r) "}"~<~R~;
.EN
.DE
moreover, $f(x)~!=~0$ for each $x$ such
that $| x-r |~<~rd(r)$.
.sp
B) Defining, for $k~>=~1$,
.DS 2
.EQ
A(x)~=~
f prime (x)/f(x) ,~~~
B sub k (x)~=~x sup k over k!~
A sup (k-1) (x) ,~~~
B(x)~=~xB sub 1 sup pprime (x)/2~,
.EN
.DE
we have
.DS 2
.EQ
B(r)~>~0~~for~~R sub 0~<~r~<~R~~and~~
B sub 1 (r)~->~inf~~as~~r~->~R sup -~.
.EN
.DE
(Note the $b(r)$ of Hayman differs
from the $B(r)$ of Harris and Schoenfeld,
although they are very closely related.)
.sp
C) For suitable $R sub 1$ and large $n$,
define $u sub n$ to be the unique solution
of $B sub 1 (r)~=~n+1$ which satisfies
$R sub 1~<~r~<~R$.
Define
.DS 2
.EQ
C sub j (x,r)~=~
- "{" B sub j+2 (x)~+~
(-1) sup j over j+2~
B sub 1 (r) "}" / B(r)~,
.EN
.DE
and suppose that there exist nonnegative
$D sub n$, $E sub n$ and $n sub 0$ such
that for $n~>=~n sub 0$,
.DS 2
.EQ
| C sub j (u sub n , u sub n ) |~<=~
E sub n D sub n sup j ,~~~
j~=~1,2, "..."~.
.EN
.DE
D) As $n~->~inf$,
.DS 2
.EQ
B(u sub n ) "{"
d(u sub n ) "}" sup 2 ~->~inf ,~~~
D sub n E sub n B(u sub n ) "{"
d(u sub n ) "}" sup 3~->~0 ,~~~
D sub n d (u sub n )~->~0~.
.EN
.DE
Harris and Schoenfeld [8] prove
the following theorem.
.sp
.I
Theorem 3
.R
(Harris and Schoenfeld).
.I
If $f(x)$ is $HS$-admissible,
.DS 2
.EQ
f(x)~=~
sum from n=0 to inf~
a sub n x sup n~,
.EN
.DE
and $beta sub n$ is defined by
.DS 2
.EQ
beta sub n~=~B(u sub n )~,
.EN
.DE
then for any $N~>=~0$ we have
.DS 2
.EQ
a sub n~=~
{f(u sub n )}
over
{2u sub n sup n sqrt {pi beta sub n}}~
left {
1~+~
sum from k=1 to N~
F sub k (n)
beta sub n sup -k~+~
O( phi sub N
(n;d) ) right }~~~as~~
n~->~inf~,
.EN
.DE
where
.DS 3
.EQ
F sub k (n)~mark =~
(-1) sup k over sqrt pi~
sum from m=1 to 2k~
{GAMMA (m+k+ half )} over m!~
sum from {size 8 {j sub 1 +
"..." +
j sub m =2k} from size 8 {
j sub 1 , "..." ,
j sub m >= 1} }~ size 10 { gamma sub j sub 1 (n) "..."
gamma sub j sub m (n) }~,
.EN
.sp
.EQ
gamma sub j (n)~lineup =~
C sub j ( u sub n , u sub n )~,
.EN
.DE
$lambda (r;d)~=~$maximum value of
$| f(z) / f(r) |$ for $z$ on the
oriented path $Q(r)$ consisting
of the line segment $L$ from
$r+ird(r)$ to $r sqrt {1- d sup 2 (r)}~+~ird(r)$
and of the circular arc $C$ from the
last point to $ir$ to $-r$,
.DS 3
.EQ
mu ( r,d)~mark =~
max left {
lambda (r;d) sqrt {B(r)}~,~~~
{exp (-B(r)d(r) sup 2 )} over {
d(r) sqrt {B(r)}} right }~,
.EN
.sp
.EQ
E sub n sup pprime~lineup =~
min (1,E sub n )~,~~~
E sub n sup {pprime pprime}~=~max
(1,E sub n )~,
.EN
.sp
.EQ
phi sub N ( n;d)~lineup =~
max left {
mu ( u sub n ; d ) ~~,~~
E sub n sup pprime ( D sub n E sub n sup
{pprime pprime} beta sub n sup {- half} ) sup 2N+2 right }~.
.EN
.DE
.R
.B
.H 1 "Exponentiation of an $H$-admissible function"
.R
We now proceed to show a connection
between $H$-admissibility and $HS$-admissibility.
.sp
.I
Theorem 4.
If $f(x)$ is $H$-admissible then
$exp (f(x))$ is $HS$-admissible.
Furthermore, the error term
$phi sub N (n;d)$ of Theorem 3 is
then $o( beta sub n sup -N )$ as
$n~->~inf$ for every fixed $N~>=~0$.
.R
.sp
.I
Proof.
.R
Suppose $f(x)$ is admissible in
$| x |~<~R~<=~inf$.
We let $a(r)$ and $b(r)$ denote
Hayman's functions computed for
$f(x)$, and $A(r)$, $B(r)$ and
$B sub 1 (r)$ denote the Harris-Schoenfeld
expressions computed for $F(x)~=~exp "{" f(x) "}"$.
.P
We choose
$d(x)~=~f (x) sup -2/5$.
First of all $F(x)$ is analytic in
$| x |~<~R$ and $F(x)$ is real for
$x$.
.P
That $(A)$ holds follows quickly
from Lemmas 1 and 2 of [10].
Lemma 1 gives immediately that if
$R~<~inf$ then
.DS 2
.EQ
(R-r)a(r)~>~10~~~as~~r~->~R sup -~,
.EN
.DE
hence
.DS 2
.EQ
r~<~R~-~10/ a(r)~.
.EN
.DE
Thus
.DS 2
.EQ
r+rd(r)~=~
r+rf(r) sup -2/5 ~<~
R+Rf(r) sup -2/5 ~-~10 a(r) sup -1~.
.EN
.DE
But Lemma 2 of [10] states that
.DS 2
.EQ
a(r)~=~
O( f(r) sup epsilon  )~,~~~oppA epsilon ~>~0~,
.EN
.DE
hence
.DS 2
.EQ
r(1+d(r) )~<~R~.
.EN
.DE
If $R~=~inf$ then $r(1+d(r))~<~inf$ trivially.
Since $F(z)~!=~0$ for any $z$, we have shown
that A) holds.
.P
To see that B) holds, note that
.DS 3
.EQ
B sub 1 (r)~mark =~
rf prime (r)~,
.EN
.sp
.EQ
B(r)~lineup =~
half r [ rf prime prime (r) +
f prime (r) ]~.
.EN
.DE
Now since $f(x)$ is $H$-admissible,
$rf prime (r) / f(r) ~->~inf$ as
$r~->~R$ by [10, Lemma 1], and
since $f(r) r sup -k ~->~inf$ as
$r~->~R$ for any fixed $k$ [10, Lemma 2],
we have $B sub 1 (r)~->~inf$ as
$r~->~R$.
Also, since $b(r)~->~inf$ as $r~->~R$,
[10, Eq. (2.3)] shows that
.DS 2
.EQ
B(r)~>=~
half r sup 2 ( f prime (r) ) sup 2
f(r) sup -1~>~0
.EN
.DE
for $r~>=~R sub 0$, which establishes
B), and even shows that $B(r)~->~inf$
as $r~->~R$.
.P
To prove that C) holds it is convenient
to use [10, Eq. (8.1)], which states
that
.nr Eq 0
.DS 2
.EQ (3.1)
r sup k f sup (k) (r)~=~
O(f(r)k!a(r) sup k )~,
.EN
.DE
where the $O$-constant is
independent of $k$.
Since $A(x)~=~f prime (x)$, it follows that
.DS 2
.EQ (3.2)
B sub k (r)~=~
r sup k over k!~
f sup (k) (r)~=~
O(f(r) a(r) sup k )~,
.EN
.DE
and thus if we take
$E sub n~=~2f(u sub n ) a(u sub n ) sup 2 /B(u sub n ) ,~~~
D sub n~=~a(u sub n )$,
then we obtain from (3.2) that
.DS 2
.EQ
| C sub k (u sub n , u sub n ) |~<=~
E sub n D sub n sup k~,~~~k~>=~1~,
.EN
.DE
if $n$ is large enough.
.P
To 
prove that D) holds, note that [10, Lemma 2] yields
.DS 2
.EQ (3.3)
D sub n~=~
O(f (u sub n ) sup epsilon  )~~~as~~
n~->~inf~,
.EN
.DE
for all $epsilon~>~0$, so that $D sub n d (u sub n )~->~0$
as $n~->~inf$.
Moreover, since
$2B(r)~=~rf prime (r) + r sup 2 f {prime prime} (r)$,
and [10, Theorem III]
states that
.DS 2
.EQ
u sub n sup k f sup (k) (u sub n )~wig~
f(u sub n ) a(u sub n ) sup k~~~as~~
n~->~inf
.EN
.DE
for every fixed $k$, we find that
.DS 2
.EQ (3.4)
B (u sub n )~wig~half f(u sub n ) a
(u sub n ) sup 2~~~as~~
n~->~inf~.
.EN
.DE
Therefore $E sub n ~wig~4$ as $n~->~inf$,
.DS 2
.EQ
B(u sub n ) d (u sub n ) sup 2~wig~half
f(u sub n ) sup 1/5 a sup 2 (u sub n )~->~inf~~~as~~
n~->~inf~,
.EN
.DE
and
.DS 2
.EQ
D sub n E sub n
B(u sub n ) d (u sub n ) sup 3~=~O
( f ( u sub n ) sup {-1/5 + epsilon} )~->~0~~~as~~
n~->~inf~,
.EN
.DE
which completes the proof of D).
.P
We have now shown that
$F(x)~=~exp (f(x))$ is $HS$-admissible.
To complete the proof of Theorem 4, we
need to estimate the term
$phi sub N (n;d)$ for $F(x)$.
However, it is easily seen that
$mu ( u sub n ;d)$ is very small, so
that
.DS 2
.EQ
phi sub N (n;d)~=~E sub n sup pprime
(D sub n E sub n sup {pprime pprime} beta sub n sup {- half} )
sup 2N+2~,
.EN
.DE
from which the last claim of Theorem 4 follows immediately.
.H 1 Applications
.ti 0
.I
Example 1:
.R
Let $B(n)$ denote the number $n$-th Bell number, which equals the number of
partitions of an $n$-element set.
Then it is well known that
.DS 2
.EQ
SIGMA ~ B(n) over n!~ x sup n~=~
exp ( e sup x -1)~.
.EN
.DE
As we have noted, Theorem 2 easily
shows that $e sup x ~-~1$ is $H$-admissible
and hence Theorem 4 gives that
$exp (e sup x -1)$ is $HS$-admissible,
so Theorem 3 gives a complete
asymptotic expansion for $B(n) /n!$.
(See also de Bruijn [5; Chapter 6].)
.sp
.I
Example 2
.R
(Harris and Schoenfeld):
Let $U sub n$ be the number of
idempotent elements in the
symmetric semigroup $T sub n$
on $n$ elements; i.e., $T sub n$
is the class of functions mapping
the set $"{" 1,2, "..." , n "}"$
into itself and multiplication
is defined by function composition.
Then Harris and Schoenfeld [9]
show that
.DS 2
.EQ
1~+~sum from
n=1 to inf~U sub n over
n!~x sup n~=~
exp ( x e sup x )~.
.EN
.DE
Since $xe sup x$ easily seen to be
$H$-admissible, Theorem 4 shows
that
$exp (xe sup x )$ is $HS$-admissible.
Thus Theorem 3 gives a complete
asymptotic expansion for $U sub n /n!$.
(See [8,9] for a discussion of this
expansion and numerical results.).
.sp
.I
Example 3:
.R
Let $t sub h,n$ denote the number of
rooted unlabelled trees with $n$
vertices and height $<=~h$, and let
.DS 2
.EQ
T sub h (x)~=~sum from n=1 to inf~
t sub h,n x sup n~.
.EN
.DE
The asymptotic behavior of the $t sub h,n$ was discovered
by Yamashita [14].
Here we rederive his results using our theorems.
Then from Po\*'lya's theory it
follows (see, for example [7]) that
for $h~>=~2$,
.DS 2
.EQ
T sub h (x)~=~x~exp left {
sum from k=1 to inf~
k sup -1 T sub h-1 (x sup k ) right }~.
.EN
.DE
It is clear that $T sub 1 (x)~=~x /(1-x)$
and since the branches of a rooted tree
of height 2 with $n$ vertices partition
the $n-1$ non-root vertices we have that
.DS 2
.EQ
t sub 2,n~=~
t sub 1,n~+~
p(n-1)~=~
1+p(n-1)~,
.EN
.DE
where $p(n)$ denotes the number of
partitions of $n$.
Hence
.DS 2
.EQ
T sub 2 (x)~=~
x~prod from n=1 to inf~
(1-x sup n ) sup -1 ~+~x (1-x) sup -1~.
.EN
.DE
Thus the radius of convergence of
$T sub 2 (x)$ is 1 and it easily
follows that the radius of convergence
of $T sub h (x)$ is 1 for each $h$.
.P
The function $SIGMA ~p(n)x sup n$
has of course been intensively studied
and the circle-method of Hardy and
Ramanujan shows that $T sub 2 (x)$
is $H$-admissible (see [11]) and that
.DS 2
.EQ (4.1)
T sub 2 (x) ~wig~
sqrt {(1-x)/(2 pi )} ~exp "{"
pi sup 2 ( 6(1-x ) ) sup -1 "}" ~~~as~~x~->~1~.
.EN
.DE
Now for $x~member~(0,1)$,
.DS 3
.EQ
sum from n=2 to inf~
n sup -1
T sub 2 (x sup n ) ~mark <=~
sum from k=1 to {[(1-x) sup -1 ]}~
k sup -1 T sub 2 (x sup 2 ) ~+~
O left (
sum from {k >= [(1-x) sup -1 ]}~k sup -1 x sup k right )
.EN
.sp
.EQ (4.2)
lineup =~
O left ( T sub 2 ( x sup 2 ) log left ( 1 over 1-x right ) right )
~=~O "{"
T sub 2 sup {1/2 + epsilon} (x) "}"
.EN
.DE
for every $epsilon~>~0$,
and so by part iii) of Theorem 2 we
have that $SIGMA~ n sup -1 T sub 2 (x sup n )$
is $H$-admissible.
Hence
$exp "{" SIGMA  n sup -1 T sub 2 ( x sup n ) "}"$
is $HS$-admissible by Theorem 4.
The asymptotic behavior of $t sub 3,n$ is
that of the coefficient of $x sup n-1$ in
$exp ( SIGMA n sup -1 T sub 2 ( x sup n )$ which
may be determined from Theorem 3.
Finally $T sub 3 (x)$ is $H$-admissible by
Theorem 2.
Clearly this argument may be repeated and
we find by induction that
.DS 2
.EQ
exp left (
sum from n=1 to inf~n sup -1 T sub h-1 (x sup n ) right )
.EN
.DE
is $HS$-admissible for all $h~>=~3$ and $T sub h (x)$
is $H$-admissible for all $h~>=~2$.
From Theorem 3 we have the first part of the
following result.
.sp
.I
Proposition:
Let $u sub n$ be defined by
.DS 2
.EQ
u sub n~
{T sub h sup pprime (u sub n )} over
{T sub h (u sub n )} ~=~n+1~.
.EN
.DE
Then
.DS 2
.EQ
t sub 2,n~wig~
1 over {4n sqrt 3}~
exp "{" pi sqrt 2n/3 "}"
.EN
.DE
and if $h~>=~3$ then
.DS 2
.EQ
t sub h,n~wig~
{T sub h (u sub n ) u sub n sup -n} over
{2 sqrt {pi B(u sub n )}} ~
left {
1~+~sum from {k >= 1} ~{F sub k (n)} over
{B sup k (u sub n )} right }~,
.EN
.DE
where $B(x)~=~half x ( x T sub h sup pprime (x) / T sub h ( x ) ) prime$,
and so
.DS 2
.EQ
log~t sub h,n ~wig~
{pi sup 2 n} over {6~log sub h-2 n}~,
.EN
.DE
where $log sub h n$ denotes
the natural logarithm iterated $h$ times.
.R
.sp
.I
Remark.
.R
It follows from this Proposition that the
number of trees of height exactly $h$
with $n$ vertices, which equals $t sub h,n~-~t sub h-1,n$,
is asymptotic to $t sub h,n$ as $n~->~inf$ if
$h$ is held fixed.
Note that if only the first term of the expansion
is required the concepts and results of Harris and
Schoenfeld need not be introduced, but a little
additional work is required to obtain complete
asymptotic expansions.
.sp
.I
Proof:
.R
The expression for $t sub 2,n$ is the well known
asymptotic expression for $p(n-1)$
(see [11]).
In view of previous results it only remains
to derive the result stated for $log~t sub h,n ,~~h~>=~3$.
.P
First of all, since
.DS 2
.EQ (4.3)
log~T sub h (x)~=~log~x~+~
sum from n=1 to inf~
n sup -1 T sub h-1 (x sup n )~,
.EN
.DE
we find from (4.2) that for every $epsilon~>~0$,
.DS 2
.EQ
log~T sub 3 (x)~=~
T sub 2 (x)~+~O ( T sub 2 (x) sup {half + epsilon} )~.
.EN
.DE
Thus the argument proving (4.2) shows that
.DS 2
.EQ
sum from n=1 to inf~
n sup -1
T sub 3 (x sup n ) ~=~
T sub 3 (x)~+~O(T sub 3 (x) sup epsilon )
.EN
.DE
for every $epsilon~>~0$,
and an easy induction shows that
for all $h~>=~3$,
.DS 2
.EQ (4.4)
sum from n=1 to inf~
n sup -1
T sub h (x sup n )~=~
T sub h (x)~+~O (T sub h (x) sup epsilon )~.
.EN
.DE
Moreover it follows from (4.3) that
.DS 2
.EQ (4.5)
{T sub h sup pprime (x)} over
{T sub h (x)}~=~1/x ~+~
sum from n=1 ~x sup n-1
T sub h-1 sup pprime (x sup n )~.
.EN
.DE
Now for $0~<~x~<~1$ and $h~>=~3$,
$m~>=~2$,
.DS 2
.EQ
T sub h-1 sup pprime (x sup m )~<=~
T sub h-1 sup pprime (x sup 2 )~=~
1 over {2 pi i}~
int from {
| z - x sup 2 | = t}~
{T sub h-1 (z)} over
{(z-x sup 2 ) sup 2} ~dz ~,
.EN
.DE
for any $t~member~(0,1-x sup 2 )$.
We choose $t~=~(1-x ) sup 2$,
which
leads to
.DS 3
.EQ
T sub h-1 sup pprime
(x sup 2 )~mark <=~
(1-x) sup -4 T sub h-1
(x sup 2 +(1-x) sup 2 )~,
.EN
.sp
.EQ
lineup =~
O( T sub h-1 (x) sup 3/4  )~.
.EN
.DE
This shows that
.DS 2
.EQ
{T sub h sup pprime (x)} over {T sub h (x)}~wig~
T sub h-1 sup pprime (x)~~~as~~x~->~1~.
.EN
.DE
Thus if $h~>=~3$,
.DS 2
.EQ (4.6)
{T sub h  (x)} over {T sub h (x)} ~wig~
T sub h-1  (x) T sub h-2  (x) "..."
T sub 3  (x) T sub 2 sup pprime (x)~~~
as~~x~->~1~.
.EN
.DE
.P
The defining relation for $u sub n$ gives
.DS 2
.EQ
log sub h-2 n~wig~
log sub h-2 (T sub h-1 (u sub n ) )~wig~
pi sup 2 over {6 ( 1- u sub n ) } ~,
.EN
.DE
so that
.DS 2
.EQ
u sub n~wig~1~-~pi sup 2 over {6~log sub h-2 n}~.
.EN
.DE
Also, (4.6) shows that
.DS 2
.EQ
log~T sub h (u sub n ) ~wig~
T sub h-1 ( u sub n )~=~O( n ( log sub h-2 n ) sup -2 )~.
.EN
.DE
Similarly one obtains
.DS 2
.EQ
log sub h-2 B (u sub n )~=~O
(n ( log sub h-1 n ) sup -2 )~,
.EN
.DE
and the result for $log~t sub h,n$ follows.
.P
This method applies to other related tree
problems.
If $w sub h,p$ denotes the number of
homeomorphically irreducible trees of height $<=~h$
and
.DS 2
.EQ
W sub h (x)~=~sum from n=0 to inf~
w sub h,n x sup n~,
.EN
.DE
then, as Read [12] shows, Po\*'lya theory gives
.DS 2
.EQ
W sub h+1 (x)~=~x~exp
left {
sum from n=1 to inf~n sup -1 W sub h (x sup n ) right } ~-~
x W sub h (x)~.
.EN
.DE
Hence
.DS 2
.EQ
W sub 2 (x)~=~x ~prod from n=1 to inf~
(1-x sup n ) sup {-w sub 1,n} ~-~x W sub 1 (x)
.EN
.DE
and since $W sub 1 ( x)~=~x+x sup 3 + "..."$,
.DS 2
.EQ
W sub 2 (x)~=~x(1-x sup 2 )~
prod from n=1 to inf~
(1-x sup n ) sup -1 ~-~x W sub 1 (x)~.
.EN
.DE
Now $W sub 2 (x)$ and then $W sub n (x)$
may be shown to be $H$-admissible and it's
easily seen that $w sub h+1,n$ is asymptotic
to the coefficient of $x sup n-1$ in $x$
$exp "{" SIGMA n sup -1 W sub h (x sup n ) "}"$.
The result is that the $T$'s may be replaced
by $W$'s in the Proposition.
The asymptotic result shows that
$w sub h,m~=~O ( t sub h,n )$ which is not
apparent from the result $log~W sub h,m~wig~pi sup 2 n / (6~log sub h-2 n)$.
.P
The operation of simultaneously
removing all vertices of degree 1
from a tree will, if repeated,
result in either a single vertex
or two adjacent vertices.
In the first case the tree is
said to be central and in the
second case bicentral.
In the following the root
shall be the centre or one of
the bicentres.
Read [12] shows that if $b sub h,p$
denotes the number of rooted bicentral
homeomorphically irreducible trees of
height $h$ with $p$ vertices, then
.DS 2
.EQ
B sub h (x)~=~
sum from n=1 to inf~
b sub h,n x sup n~=~
half [
W sub h (x) sup 2
-2W sub h (x)
W sub h-1 (x) +
W sub h-1 (x) sup 2
+W sub h (x sup 2 ) -W sub h-1
(x) sup 2 ]~.
.EN
.DE
The asymptotic behavior of
$b sub h,n$ is that of the
coefficient of $x sup n$
in $half~W sub h  (x) sup 2$,
and so the previous analysis
applies to give
.DS 2
.EQ
log~b sub h,n~wig~left {
matrix {
lcol {2~log~w sub 2,n above log~w sub h,n}
ccol {, above ,}
lcol {if ~h~=~2 above if~h~>=~3}
}
.EN
.DE
.P
Finally, Read [12] shows that if $c sub h,n$
denotes the number of rooted central
homeomorphically irreducible trees of height
$h$ and with $n$ points then
.DS 2
.EQ
C sub h (x)~=~
sum from n=1 to inf~
c sub h,n x sup n~=~
W sub h (x) + x W sub h-1 (x) -
[ mark 1+ v sub h-1 (x) ][W sub h-1 (x) +
.EN
.sp
.EQ
lineup x W sub h-2 (x) ] - half x [V sub h-1 (x) sup 2
+ v sub h-1 (x sup 2 ) ]~,
.EN
.DE
where $V sub h (x)~=~W sub h (x)-W sub h-1 (x)$.
It easily follows that $c sub h,n~wig~w sub h,n$,
hence our previous results apply to $c sub h,n$.
.PH ""
.bp
.ce
.B
References
.R
.sp
.AL 1
.LI
E. A. Bender,
Asymptotic methods in enumeration,
SIAM Review, 16 (1974), pp. 485-515.
.PH "''R-\\\\nP''"
.nr P 1
.LI
E. A. Bender, An asymptotic expansion
for the coefficients of some formal
power series,
J. London Math. Soc., \f29\f1 (1975),
451-458.
.LI
E. A. Bender and J. R. Goldman,
Enumerative uses of generating
functions, Indiana Univ. Math. J.,
20(1971), pp. 753-765.
.LI
E. A. Bender and L. B. Richmond,
An asymptotic expansion for the
coefficients of some formal power
series,
to be published.
.LI
N. G. deBruijn,
.ul
Asymptotic Methods in Analysis,
North-Holland, Amsterdam, 1958.
.LI
P. Flajolet and A. M. Odlyzko,
Limit distributions for coefficients
of iterates of polynomials with
applications to combinatorial
enumerations,
to be published.
.LI
F. Harary and E. M. Palmer,
.ul
Graphical Enumeration,
Academic Press, New York and London, 1973.
.LI
B. Harris and L. Schoenfeld,
Asymptotic expansions for the
coefficients of analytic functions,
Illinois J. Math., 12(1968), 264-277.
.LI
B. Harris and L. Schoenfeld,
The number $H sub n$ of idempotent
elements in the symmetric semigroup
on $n$ elements and the asymptotic
expansion of $H sub n$, Mathematics
Research Center Technical Summary
Report #607, Feb. 1966, Univ. of
Wisconsin.
.LI
W. K. Hayman,
A generalization of Stirling's
formula, J. reine angew. Math.,
196(1956), 67-95.
.LI
H. Rademacher,
.ul
Topics in Analytic Number Theory,
Springer-Verlag, 1973.
.LI
R. C. Read,
On the generation and enumeration of
homeomorphically irreducible trees,
Combinatorics and Optimization
Research Report, CORR 82-1, 1982,
Univ. of Waterloo.
.LI
E. M. Wright, Asymptotic relation between
enumerative functions in graph theory,
Proc. London Math. Soc. (3), 20(1970),
558-572.
.LI
M. Yamashita, Asymptotic estimation of the number
of trees, Trans. IECE Japan, 62-A (1979), 128-135 (in Japanese).
.LE