LINEBURG


<< . .

 19
( 24)



. . >>

Mellin transforms are useful in dealing with problems that combine combinatorial and
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

<< . .

 19
( 24)



. . >>

Copyright Design by: Sunlight webdesign