LINEBURG

arithmetic aspects. For example, if S(n) denotes the total number of 1™s in the binary repre-

sentations of 1, 2, . . . , n ’ 1, then it was shown by Delange that

1

S(n) = n log2 n + nu(log 2 n) + o(n) as n ’ ∞ , (14.19)

2

where u(x) is a continuous, nowhere di¬erentiable function that satis¬es u(x) = u(x + 1). The

Fourier coe¬cients of u(x) are known explicitly. Perhaps the best way to obtain these results

is by using Mellin transforms. See [129, 353] for further information and references.

138

Mellin transforms are often combined with other techniques. For example, sums of the

n

form sn = ak with oscillating ak lead to generating functions

k

ak w(z)k .

s(z) = (14.20)

k

The asymptotic behavior of s(z) near its dominant singularity can sometimes be determined by

applying Mellin transforms. For a detailed explanation of the approach, see [137]. Examples

of the application of this technique can be found in [13, 280].

15. Functional equations, recurrences, and combinations of methods

Most asymptotic enumeration results are obtained from combinations of techniques pre-

sented in the previous sections. However, it is only rarely that the basic asymptotic techniques

can be applied directly. This section describes a variety of methods and results that are not

easy to categorize. They use combinations of methods that have been presented before, and

sometimes develop them further. In most of the examples that will be presented, some relations

for generating functions are available, but no simple closed-form formulas, and the problem is

to deduce where the singularities lie and how the generating functions behave in their neigh-

borhoods. Once that task is done, previous methods can be applied to obtain asymptotics of

the coe¬cients.

15.1. Implicit functions, graphical enumeration, and related topics

Example 15.1. Rooted unlabeled trees. We sketch a proof that T n , the number of rooted

unlabeled trees with n vertices, satis¬es the asymptotic relation (1.9). The functional equation

(1.8) holds with T (z) regarded as a formal power series. The ¬rst step is to show that T (z)

is analytic in a neighborhood of 0. This can be done by working exclusively with Eq. (1.8).

(There is an argument of this type in Section 9.5 of [188].) Another way to prove analyticity

of T (z) is to use combinatorics to obtain crude upper bounds for T n . We use a combination

of these approaches. If a tree with n ≥ 2 vertices has at least two subtrees at the root, we can

decompose it into two trees, the ¬rst consisting of one subtree at the root, the other of the

root and the remaining subtrees. This shows that

n’1

Tn ¤ Tn’1 + Tk Tn’k , n≥2. (15.1)

k=1

139

Therefore, if we de¬ne a1 = 1, and

n’1

an = an’1 + ak an’k , n≥2, (15.2)

k=1

then we have Tn ¤ an . Now if

∞

an z n ,

A(z) =

n=1

then the de¬ning relation (15.2) yields the functional equation

A(z) ’ z = zA(z) + A(z)2 , (15.3)

so that

A(z) = (1 ’ z ’ (1 ’ 6z + z 2 )1/2 )/2 . (15.4)

√

Since A(z) is analytic in |z| < 3 ’ 2 2 = 0.17157 . . . , we have

0 ¤ Tn ¤ an = O(6n ) . (15.5)

It will also be convenient to have an exponential lower bound for T n . Let bn be the number

of rooted unlabeled trees in which every internal vertex has ¤ 2 subtrees. Then b 1 = 1, b2 = 1,

and

(n’1)/2

bn ≥ bk bn’k’1 for n≥3. (15.6)

k=1

(6/5)n

We use this to show that bn ≥ for n ≥ 7. Direct computation establishes this lower

bound for 7 ¤ n ¤ 14, and for n ≥ 15 we use induction and b n ≥ bk bn’k’1 with k = (n’1)/2 .

Since Tn ≥ bn ≥ (6/5)n , T (z) converges only in |z| < r for some r with r < 1. Since

T (0) = 0, |T (z)| ¤ Cδ |z| in |z| ¤ r ’ δ for every δ > 0, and therefore

∞

T (z k )/k

u(z) = (15.7)

k=2

is analytic in |z| < r 1/2 , and in particular at z = r. Therefore, although we know little about

r and u(z), we see that T (z) satis¬es G(z, T (z)) = T (z), where

G(z, w) = z exp(w + u(z)) (15.8)

is analytic in z and w for all w and for |z| < r 1/2 .

We will apply Theorem 10.6. First, though, we need to establish additional properties of

T (z). We have

T (z) exp(’T (z)) = z exp(u(z)) ’ r exp(u(r)) as z ’ r ’ , (15.9)

140

and 0 < r exp(u(r)) < ∞. Since T (z) is positive and increasing for 0 < z < r, T (r), the limit

of T (z) as z ’ r ’ must exist and be ¬nite.

We next show that T (r) = 1. We have

‚

G(z, w) = G(z, w) . (15.10)

‚w

We know that G(z, T (z)) = T (z) for |z| < r, and in particular for some z arbitrarily close to

r. If T (r) = 1, then by (15.10)

‚

(G(z, w) ’ w) =0 (15.11)

‚w w=T (z)

in a neighborhood of z = r, and therefore T (z) could be continued analytically to a neighbor-

hood of z = r. This is impossible, since r is the radius of convergence of T (z), and T n ≥ 0

implies by Theorem 10.3 that T (z) has a singularity at z = r. Therefore we must have T (r) = 1,

and Gw (r, T (r)) = 1.

We have now shown that conditions (i) and (ii) of Theorem 10.6 hold with the r of that

theorem the same as the r we have de¬ned and s = T (r) = 1, δ = r 1/2 ’ r. Condition (iii)

is easy to verify. Finally, the conditions on the coe¬cients of T (z) and G(z, w) are clearly

satis¬ed.

Since Theorem 10.6 applies, we do obtain an asymptotic expansion for T n of the form (1.9),

with C given by the formula (10.64). It still remains to determine r and C. No closed-form

expressions are known for these constants. They are conjectured to be transcendental and

algebraically independent of standard constants such as π and e, but no proof is available.

Numerically, however, they are simple to compute. Note that

Gz (r, 1) = exp(1 + u(r))(1 + ru (r))

= r ’1 + u (r) , (15.12)

Gww (r, 1) = 1 , (15.13)

so we only need to compute r and u (r). These quantities can be computed along with u(r) in

the same procedure. The basic numerical procedure is to determine r as the positive solution

to T (r) = 1. To determine T (x) for any positive x, we take any approximation to the T (x k ),

k ≥ 1 (starting initially with xk as an approximation to T (xk ), say), and combine it with (1.8)

(applied with z = xm , m ≥ 1) to obtain improved approximations. This procedure can be

made rigorous. Upper bounds for r, u(r), and u (r) are especially easy. Since T1 = 1, T (x) ≥ x

141

for 0 < x < 1, and therefore, T (xk ) ≥ xk for k ≥ 1. Suppose that we start with a ¬xed value of

(1)

x and derive some lower bounds of the form T (x k ) ≥ uk ≥ 0 for k ≥ 1. Then the functional

equation (1.8) implies

∞

m

u(2)

T (x ) ≥ = x exp ukm /k m≥1. (15.14)

m

k=1

This process can be iterated several more times, and to keep the computation manageable, we

(j)

can always set uk = 0 for k ≥ k0 . If we ever ¬nd a lower bound T (x) > 1 by this process, then

we know that r < x, since T (r) = 1. Lower bounds for r are slightly more complicated.

We mention here that if Un denotes the number of unlabeled trees, then the ordinary

Un z n satis¬es

generating function U (z) =

U (z) = T (z) ’ T (z)2 /2 + T (z 2 )/2 . (15.15)

Using the results from Example 15.1 about the analytic behavior of T (z), it can be shown that

Un ∼ C r ’n n’5/2 , (15.16)

where r = 0.3383219 . . . is the same as before, while C = 0.5349485 . . . .

Example 15.2. Leftist trees. Let an denote the number of leftist trees of size n (i.e., rooted

planar trees with n leaves, such that in any subtree S, the leaf nearest to the root of S is in the

right subtree of S [237]). Then a1 = a2 = a3 = 1, a4 = 2, a5 = 4. No explicit formula for an is

known. Even the recurrences for the a n are complicated, and involve auxiliary sequences. If

∞

an z n

f (z) = (15.17)

n=1

denotes the ordinary generating function of a n , then the combinatorially derived recurrences

for the an show that [224]

∞

1 1

f (z) = z + f (z)2 + gm (z)2 , (15.18)

2 2

m=1

where the auxiliary generating functions g m (z) (which enumerate leftist trees with the leftmost

leaf at distance m ’ 1 from the root) satisfy

®

m’1

g1 (z) = z, g2 (z) = zf (z), gm+1 (z) = gm (z) °f (z) ’ gj (z)» , m ≥ 2 , (15.19)

j=1

142

and

∞

f (z) = gm (z) . (15.20)

m=1

These generating function relations might not seem promising. If r is the smallest singularity

gm (z)2 is not analytic at r, so we cannot apply Theorem 10.6 in the way it was

of f (z), then

used in Example 15.1. However, Kemp [224] has sketched a proof that the analytic behavior

of f (z) is of the same type as that involved in functions covered by Theorem 10.6, so that it

has a dominant square root singularity, and therefore

an = ±cn n’3/2 + O(cn n’5/2 ) , (15.21)

where

± = 0.250363429 . . . , c = 2.749487902 . . . . (15.22)

The constants ± and c are not known explicitly in terms of other standard numbers such as π or

e, but they can be computed e¬ciently. The ±c n n’3/2 term in (15.21) gives an approximation

to an that is accurate to within 4% for n = 10, and within 0.4% for n = 100. Thus asymptotic

methods yield an approximation to a n which is satisfactory for many applications. Further

results about leftist trees can be found in [225].

15.2. Nonlinear iteration and tree parameters

Example 15.3. Heights of binary trees. A binary tree [DEK] is a rooted tree with unlabeled

nodes, in which each node has 0 or 2 successors, and left and right successors are distinguished.

The size of a binary tree is the number of internal nodes, i.e., the number of nodes with two

successors. We let Bn denote the number of binary trees of size n, so that B 0 = 1 (by

convention), B1 = 1, B2 = 2, B3 = 5, . . . . Let

∞

Bn z n .

B(z) = (15.23)

n=0

Since each nonempty binary tree consists of the root and two binary trees (the left and right

subtrees), we obtain the functional equation

B(z) = 1 + zB(z)2 . (15.24)

This implies that

1 ’ (1 ’ 4z)1/2

B(z) = , (15.25)

2z

143

so that

1 2n

Bn = , (15.26)

n+1 n

and the Bn are the Catalan numbers. The formula (4.4) (easily derivable from Stirling™s

formula (4.1)) shows that

Bn ∼ π ’1/2 n’3/2 4n as n’∞. (15.27)

The height of a binary tree is the number of nodes along the longest path from the root to

a leaf. The distribution of heights in binary trees of a given size does not have exact formulas

like that of (15.26) for the number of binary trees of a given size. There are several problems

on heights that have been answered only asymptotically, and with varying degrees of success.

The most versatile approach is through recurrences on generating functions. Let B h,n be the

number of binary trees of size n and height ¤ h, and let

∞

Bh,n z n .

bh (z) = (15.28)

n=0

Then

b0 (z) = 0, b1 (z) = 1 , (15.29)

and an extension of the argument that led to the relation (15.24) yields

bh+1 (z) = 1 + zbh (z)2 , h≥0. (15.30)

The bh (z) are polynomials in z of degree 2h’1 ’ 1 for h ≥ 1. Unfortunately there is no simple

formula for them like Eq. (15.25) for B(z), and one has to work with the recurrence (15.30)

to obtain many of the results about heights of binary trees. Di¬erent problems involve study

of the recurrence in di¬erent ranges of values of z, and the behavior of the recurrence varies

drastically.

For any ¬xed z with |z| ¤ 1/4, bh (z) ’ B(z) as h ’ ∞. For |z| > 1/4 the behavior of b h (z)

is more complicated, and is a subject of of nonlinear dynamics [91]. (It is closely related to the

study of the Mandelbrot set.) For any real z with z > 1/4, b h (z) ’ ∞ as h ’ ∞. To study

the distribution of the Bh,n as n varies for h ¬xed, but large, it is necessary to investigate this

range of rapid growth. It can be shown [133] that for any » 1 and »2 with 0 < »1 < »2 < 1/2,

exp(2h’1 (β(r) ’ rβ (r) log r))

(1 + O(2’h/2 ))

Bh,n = (h’1)/2 (15.31)

2 β (r) + rβ (r)))1/2

2 (2π(r

144

uniformly as h, n ’ ∞ with

»1 < n/2h < »2 , (15.32)

where the function β(x) is de¬ned for 1/4 < x < ∞ by

∞

1

2’j log 1 +

β(x) = log x + , (15.33)

bj (x) ’ 1

j=1

and r is the unique solution in (1/4, ∞) to

rβ (r) = n2’h+1 . (15.34)

The formula (15.31) might appear circular, in that it describes the behavior of the coe¬-

cients βh,n of the polynomial bh (z) in terms of the function β(z), which is de¬ned by b h (z) and

all the other bj (z). However, the series (15.33) for β(z) converges rapidly, so that only the ¬rst

few of the bh (z) matter in obtaining approximate answers, and computation using (15.33) is

e¬cient. The function β(z) is analytic in a region containing the real half-line x > 1/4, so the

behavior of the Bh,n is smooth. It is also known [133] that the behavior of B h,n as a function

of n is Gaussian near the peak, which occurs at n ∼ 2 h’1 · 0.628968 . . . . The distribution of

Bh,n is not Gaussian throughout the range (15.32), though.

The proof of the estimate (15.31) is derived from the estimate

bh (z) = exp(2h’1 β(z) ’ log z)(1 + O(exp(’ 2h ))) , (15.35)

valid in a region along the half-axis x > 1/4. The estimates for the coe¬cients B h,n are

obtained by applying the saddle point method. Because of the doubly-exponential rate of

growth of bh (z) for z close to the real axis, it is easy to show that on the circle of integration,

the region away from the real axis contributes a negligible amount to B h,n . The relation (15.35)

is su¬cient, together with the smoothness properties of β(z), to estimate the contribution of

the integral near the real axis. To prove (15.35), one proceeds as in Example 9.7. However,

greater care is required because of the complex variables that occur and the need for estimates

that are uniform in the variables. The basic recurrence (15.30) shows that

1

log bh+1 (z) = 2 log bh (z) + log z + log 1 +

zbh (z)2

(15.36)

1

= 2 log bh (z) + log z + log 1 + .

bh+1 (z) ’ 1

145

Iterating this relation, we ¬nd that for h ≥ 1,

h’1

1

2k log 1 +

2h+1 log b + (2h

log bh+1 (z) = 1 (z) ’ 1) log z +

bh+1’k (z) ’ 1

k=0

(15.37)

±

h+1

1

2’j log 1 +

2h

= log z + ’ log z .

bj (z) ’ 1

j=1

The basic equation (15.35) then follows. The technical di¬culty is in establishing rigorous

bounds for the error terms in the approximations. Details are presented in [133].

Most of the binary trees of a given height h are large, with about 0.3 · 2 h internal nodes.

This might give the misleading impression that most binary trees are close to the full binary

tree of a similar size. However, if we consider all binary trees of a given size n, the average

height is on the order of n1/2 , so that they are far from the full balanced binary trees. The

methods that are used to study the average height are di¬erent from those used for trees of a

¬xed height. The basic approach of [133] is to let

Hn = ht(T ) ,

T

|T |=n

where the sum is over the binary trees T of size n, and ht(T ) is the height of T . Then the

average height is just Hn /Bn .

The generating function for the Hn is

∞

Hn z n =

H(z) = (B(z) ’ bh (z)) , (15.38)

n=0 h≥0

and the analysis of [133] proceeds by investigating the behavior of H(z) in a wedge-shaped

region of the type encountered in Section 11.1. If we let

(z) = (1 ’ 4z)1/2 , (15.39)

eh (z) = (B(z) ’ bh (z))/(2B(z)) , (15.40)

then the recurrence (15.30) yields

Copyright Design by: Sunlight webdesign