LINEBURG


<< . .

 20
( 24)



. . >>

eh+1 (z) = (1 ’ (z))eh (z)(1 ’ eh (z)) , e0 (z) = 1/2 . (15.41)

Extensive analysis of this relation yields an approximation to e h (z) of the form

(z)(1 ’ (z))h
eh (z) ≈ , (15.42)
1 ’ (1 ’ (z))h

146
valid for | (z)| su¬ciently small, |Arg (z)| < π/4 + δ for a ¬xed δ > 0. (The precise error
terms in this approximation are complicated, and are given in [133].) This then leads to an
expansion for H(z) in a sector |z ’ 1/4| < ±, π/2 ’ β < |Arg(z ’ 1/4)| < π/2 + β of the form

H(z) = ’2 log(1 ’ 4z) + K + O(|1 ’ 4z|v ) , (15.43)

where v is any constant, v < 1/4, and K is a ¬xed constant. Transfer theorems of Section 11.1
now yield the asymptotic estimate

Hn ∼ 2n’1 4n as n ’ ∞ . (15.44)

When we combine (15.44) with (15.27), we obtain the desired result that the average height
of a binary tree of size n is ∼ 2(πn)1/2 as n ’ ∞.
Distribution results about heights of binary trees can be obtained by investigating the
generating functions
hr (B(z) ’ bh (z)) . (15.45)
h≥0

This procedure, carried out in [133] by using modi¬cations of the approach sketched above for
the average height, obtains asymptotics of the moments of heights. The method mentioned in
Section 6.5 then leads to a determination of the distribution. However, the resulting estimates
do not say much about heights far away from the mean. A more careful analysis of the behavior
of eh (z) can be used [126] to show that if x = h/(2n 1/2 ), then

Bh,n ’ Bh’1,n 2 x2
∼ 2xn’1/2 m2 (2m2 x2 ’ 3)e’m (15.46)
Bn
m=1

as n, h ’ ∞, uniformly for x = o((log n) 1/2 ), x’1 = o((log n)1/2 ).
For extremely small and large heights, di¬erent methods are used. It follows from [126]
that
Bh,n ’ Bh’1,n
¤ exp(’c(h2 /n + n/h2 )) (15.47)
Bn
for a constant c > 0, which shows that extreme heights are infrequent. (The estimates in [126]
are more precise than (15.47).) Bounds of the above form for small heights are obtained in
[126] by studying the behavior of the b h (z) almost on the boundary between convergence and
divergence, using the methods of [399]. Let x h be the unique positive root of bh (z) = 2. Note
that B(1/4) = 2, and each coe¬cient of the b h (z) is nondecreasing as h ’ ∞. Therefore
x2 > x3 > · · · > 1/4. More e¬ort shows [126] that x h is approximately 1/4 + ±h’2 for a certain

147
± > 0. This leads to an upper bound for B h,n by Lemma 8.1. Bounds for trees of large heights
are even easier to obtain, since they only involve upper bounds for the b h (z) ’ bh’1 (z) inside
the disk of convergence |z| < 1/4.
 




In addition to the methods of [132, 133, 126] that were mentioned above, there are also other
techniques for studying heights of trees, such as those of [60, 331]. However, there are problems
about obtaining fully rigorous proofs that way. (See the remarks in [126] on this topic.) Most
of these methods can be extended to study related problems, such as those of diameters of
trees [357].
The results of Example 15.3 can be extended to other families of trees (cf. [132, 133, 126]).
What matters in obtaining results such as those of the above example are the form of the
recurrences, and especially the positivity of the coe¬cients.

Example 15.4. Enumeration of 2,3-trees [300]. Height-balanced trees satisfy di¬erent func-
tional equations than unrestricted trees, which results in di¬erent analytic behavior of the
generating functions, and di¬erent asymptotics. Consider 2, 3-trees; i.e., rooted, oriented trees
such that each nonleaf node has either two or three successors, and in which all root-to-leaf
paths have the same length. If an is the number of 2, 3-trees with exactly n leaves, then
a1 = a2 = a3 = a4 = 1, a5 = 2, . . ., and the generating function

an z n
f (z) = (15.48)
n=1

satis¬es the functional equation

f (z) = z + f (z 2 + z 3 ) . (15.49)

Iteration of the recurrence (15.49) leads to

f (z) = Qk (z) , (15.50)
k=0

where Q0 (z) = z, Qk+1 (z) = Qk (z 2 + z 3 ), provided the series (15.50) converges. The Taylor
series (15.48) converges only in |z| < φ ’1 , where φ = (1 + 51/2 )/2 is the “golden ratio.” Study
of the polynomials Qk (z) shows that the expansion (15.50) converges in a region

D = {z : |z| < φ’1 + δ, |Arg(z ’ φ’1 )| > π/2 ’ } (15.51)



148
for certain δ, > 0, and that inside D,

f (z) = ’c log(φ’1 ’ z) + w(log(φ’1 ’ z)) + O(|φ’1 ’ z|) , (15.52)

where c = [φ log(4 ’ φ)]’1 , and w(t) is a nonconstant function, analytic in a strip |Im (t)| < ·
for some · > 0, such that w(t + log(4 ’ φ)) = w(t). The expression (15.52) only has to be
proved in a small vicinity of φ’1 (intersected with D, of course). Since

Q(φ’1 + ν) = φ’1 + (4 ’ φ)ν + O(|ν|2 ) (15.53)

(so that φ’1 is a repelling ¬xed point of Q), behavior like that of (15.52) is to be expected,
and with additional work can be rigorously shown to hold. Once the expansion (15.52) is
established, singularity analysis techniques can then be applied to deduce that

φn
an ∼ u(log n) as n’∞, (15.54)
n

where u(t) is a positive nonconstant continuous function that satis¬es u(t) = u(t + log(4 ’ φ)),
and has mean value (φ log(4 ’ φ))’1 . For details, see [300].
The same methods can be applied to related families of trees, such as those of B-trees.
 




The results of Example 15.3 and the generalizations mentioned above all apply only to
the standard counting models, in which all trees with a ¬xed value of some simple property,
such as size or height, are equally likely. Often, especially in computer science applications,
it is necessary to study trees produced by some algorithm, and consider all outputs of this
algorithm as equally likely. For example, in sorting it is natural to consider all permutations
of n elements as equally probable. If random permutations are used to construct binary search
trees, then the distribution of heights will be di¬erent from that in the standard model, and
the two trees of maximal height will have probability of 2/n! of occurring. The average height
turns out to be ∼ c log n as n ’ ∞, for c = 4.311 . . . a certain constant given as a solution to
a transcendental equation. This was shown by Devroye [92] (see also [93]) by an application
of the theory of branching processes. For a detailed exposition of this method and other
applications to similar problems, see [270]. The basic generating function approach that we
have used in most of this chapter leads to functional iterations which have not been solved so
far.




149
15.3. Di¬erential and integral equations

Section 9.2 showed that di¬erential equations arise naturally in analyzing linear recurrences
of ¬nite order with rational coe¬cients. There are other settings when they arise even more
naturally. As is true of nonlinear iterations in the previous section and the functional equations
of the next one, di¬erential and integral equations are typically used to extract information
about singularities of generating functions. We have already seen in Example 9.3 and other
cases that di¬erential equations can yield an explicit formula for the generating function, from
which it is easy to deduce what the singularities are and how they a¬ect the asymptotics of
the coe¬cients. Most di¬erential equations do not have a closed-form solution. However, it
is often still possible to derive the necessary information about analytic behavior even when
there is no explicit formula for the solution. We demonstrate this with a brief sketch of a
recent analysis of this type [131]. Other examples can be found in [270].

Example 15.5. Search costs in quadtrees [131]. Quadtrees are a well-known data structure
for multidimensional data storage [168]. Consider a d-dimensional data space, and let n points
be drawn independently from the uniform distribution in the d-dimensional unit cube. We
take d ¬xed and n ’ ∞. Suppose that the ¬rst n ’ 1 points have already been inserted into
the quadtree, and let Dn be the search cost (de¬ned as the number of internal nodes traversed)
in inserting the n-th item. The result of Flajolet and La¬orgue [131] is that D n converges in
distribution to a Gaussian law when n ’ ∞. If µ n and σn denote the mean and standard
deviation of Dn , respectively, then

µn ∼ 2d’1 log n, σn ∼ d’1 (2 log n)1/2 as n’∞, (15.55)

and for all real ± < β, as n ’ ∞,
β
’1/2
exp(’x2 /2)dx .
P r(±σN < Dn ’ µn < βσn ) ∼ (2π) (15.56)
±

The results for µn and σn had been known before, and required much simpler techniques
for their solution, see [270]. It was only necessary to study asymptotics of ordinary di¬erential
equations in a single variable. To obtain distribution results for search costs, it was necessary
to study bivariate generating functions. The basic relation is

P r{Dn = k}uk = (2d u ’ 1)’1 (φn (u) ’ φn’1 (u)) , (15.57)
k



150
where the polynomials φn (u) have the bivariate generating function

φn (u)z n .
¦(u, z) = (15.58)
n=0

which satis¬es the integral equation
z x1 x2
dx1 dx2 dx3
2d u
¦(u, z) = 1 + ···
x1 (1 ’ x1 ) x2 (1 ’ x2 ) x3 (1 ’ x3 )
0 0 0
(15.59)
xd’2 xd’1
dxd’1 dxd
¦(u, xd ) .
xd’1 (1 ’ xd’1 ) 1 ’ xd
0 0

This integral equation can easily be reduced to an equivalent di¬erential equation, which is
what is used in the analysis. For d = 1 there is an explicit solution

¦(u, z) = (1 ’ z)’2u , (15.60)

which shows that Dn can be expressed in terms of Stirling numbers. This is not surprising, since
for d = 1 the quadtree reduces to the binary search tree, for which these results were known
before. For d = 2, ¦(u, z) can be expressed in terms of standard hypergeometric functions.
However, for d ≥ 3 there do not seem to be any explicit representations of ¦(u, z). Flajolet
and La¬orgue use a singularity perturbation method to study the behavior of ¦(u, z). They
start out with the di¬erential system derivable in standard way from the di¬erential equation
associated to (15.59) (i.e., a system of d linear di¬erential equations in z with coe¬cients that
are rational in z). Since only values of u close to 1 are important for the distribution results,
they regard u as a perturbation parameter of this system. For every ¬xed u, they determine
the dominant singularity of the linear di¬erential system in the variable z, using the indicial
equations that are standard in this setting. It turns out that the dominant singularity is a
regular one at z = 1, and
1/d
¦(u, z) ≈ c(u)(1 ’ z)’2u , (15.61)

at least for z and u close to 1. This behavior of ¦(u, z) is then used (in its more precise
form, with explicit error terms) to deduce, through the transfer theorem methods explained in
Section 11, the behavior of φn (u):

1/d ’1
φn (u) ≈ c(u)“(2u1/d )’1 n2u . (15.62)

This form, again in a more precise formulation, is then used to deduce that the behavior of
Dn is normal near its peak, and that the tails of the distribution are small.
 




151
15.4. Functional equations

One area that needs and undoubtedly will receive much more attention is that of com-
plicated nonlinear relations for generating functions. Even in a single variable our knowledge
is limited. Some of the work of Mahler [267, 268, 269], devoted to functions f (z) satisfying
equations of the form p(f (z), f (z g )) = 0, where p(u, v) is a polynomial, shows that it is possible
to extract information about the analytic behavior of f (z) near its singularities. This can then
be used to study the coe¬cients.
Sometimes seemingly complicated functional equations do have easy solutions.

Example 15.6. A pebbling game. In a certain pebbling game [76], minimal con¬gurations of
size n are counted by Tn (0), where Tn (x) is a polynomial that satis¬es Tn (x) = 0 for 0 ¤ n ¤ 2,
T3 (x) = 4x + 2x2 , and for n ≥ 3,

Tn+1 (x) = x’1 (1 + x)2 Tn (x) ’ x’1 Tn (0) + xTn (0) + nxn . (15.63)

The coe¬cients of Tn (x) are ≥ 0, and

Tn+1 (1) ¤ 4Tn (1) + Tn (1) + 1 ¤ 6Tn (1) , (15.64)

so clearly each coe¬cient of Tn (x) is ¤ 6n , say. Let

Tn (x)y n .
f (x, y) = (15.65)
n=0

The bound on Tn (1) shows that f (x, y) is analytic in x and y for |x| < 1, |y| < 1/6, say, with
x and y complex. Then the recurrence (15.63) leads to the functional equation

(x ’ y(1 + x)2 )f (x, y) = 2x2 (2 + x)y 3 + x2 y 2 (1 ’ 2x2 y 2 )(1 ’ xy)’2
(15.66)
x2 yf
’ yf (0, y) + x (0, y) ,

where fx (x, y) is the partial derivative of f (x, y) with respect to x. We now di¬erentiate the
equation (15.66) with respect to x and set x = 0. We ¬nd that

(1 ’ 2y)f (0, y) = yfx (0, y) , (15.67)

and therefore
(x ’ y(1 + x)2 )f (x, y) = 2x2 (2 + x)y 3 + x2 y 2 (1 ’ 2x2 y 2 )(1 ’ xy)’2
(15.68)
1)x2 ]f (0, y)
’ [y + (2y ’ .

152
When
x = y(1 + x)2 , (15.69)

the left side of Eq. (15.68) vanishes, and Eq. (15.68) yields the value of f (0, y). Now Eq. (15.69)
holds for
x = (2y)’1 (1 ’ 2y ± (1 ’ 4y)1/2 ) .

To ensure that (15.69) holds for x and y both in a neighborhood of 0, we set

g(y) = (2y)’1 (1 ’ 2y ’ (1 ’ 4y)1/2 ) . (15.70)

Then g(y) = y(1 + g(y))2 , g(y) is analytic for |y| small, and so substituting x = g(y) in
Eq. (15.68) yields

[y + (2y ’ 1)g(y)2 ]f (0, y) = 2g(y)2 (2 + g(y))y 3
(15.71)
+ y 2 g(y)2 (1 ’ 2y 2 g(y)2 )(1 ’ yg(y))’2 .

Thus f (0, y) is an algebraic function of y. Eq. (15.71) was proved only for |y| small, but it can
now be used to continue f (0, y) analytically to the entire complex plane with the exception of
a slit from 1/4 to in¬nity along the positive real axis. There is a ¬rst order pole at y = 1/r,
with r = 4.1478990357 . . . the positive root of

r 3 ’ 7r 2 + 14r ’ 9 = 0 , (15.72)

and no other singularities in |y| < 1/4. Hence we obtain

Tn (0) = [y n ]f (0, y) = cr n + O((4 + )n ) (15.73)

as n ’ ∞, for every > 0, where c is an algebraic number that can be given explicitly in
terms of r.

The value of f (0, y) is determined by Eq. (15.71), and together with Eq. (15.68) gives
f (x, y) explicitly as an algebraic function of x and y. The resulting expression can then be
used to determine other coe¬cients of the polynomials T n (x).
 




Example 15.6 was easy to present because of the special structure of the functional equation.
The main trick was to work on the variety de¬ned by Eq. (15.69), on which the main term
vanishes, so that one can analyze the remaining terms. The same basic approach also works



153
in more complicated situations. The analysis of certain double queue systems leads to two-
variable generating functions for the equilibrium probabilities that satisfy equations such as
the following one, obtained by specializing the problem treated in [145]:

Q(z, w)f (z, w) = 2z(w ’ 1)f (z, 0) + 3w(z ’ 1)f (0, w) , (15.74)

valid for complex z and w with |z|, |w| ¤ 1, where

Q(z, w) = 6zw ’ 3w ’ 2z ’ z 2 w2 . (15.75)

The generating function f (z, w) is analytic in z and w. What makes this problem tractable
is that on the algebraic curve in two-dimensional complex space de¬ned by Q(z, w) = 0,
the quantity on the right-hand side of Eq. (15.74) has to vanish, and this imposes stringent
conditions on f (z, 0) and f (0, w), which leads to their determination. Once f (z, 0) and f (0, w)
are found, f (z, w) is de¬ned by Eq. (15.74), and one can determine the asymptotics of its
coe¬cients. Treatment of functional equations of the type (15.74) was started by Malyshev
[274]. For recent work and references to other papers in this area, see [144, 145]. This approach
has so far been successful only for two-variable problems with Q(z, w) of low degree. Moreover,
the mathematics of the solution is far deeper than that used in Example 15.6.

16. Other methods

This section mentions a variety of methods that are not covered elsewhere in this chapter
but are useful in asymptotic enumeration. Most are discussed brie¬‚y, since they belong to
large and well developed ¬elds that are beyond the scope of this survey.

16.1. Permanents

Van der Waerden™s conjecture, proved by Falikman [113] and Egorychev [98], can be used
to obtain lower bounds for certain enumeration problems. It states that if A is an n — n matrix
that is doubly stochastic (entries ≥ 0, all row and column sums equal to 1) then the permanent
of A satis¬es per(A) ≥ n’n n!. (For most asymptotic problems it is su¬cient to rely on an
earlier result of T. Bang [26] and S. Friedland [148] which gives a lower bound of per(A) ≥ e ’n
that is worse only by a factor of n1/2 .) There is also an upper bound for permanents. Minc™s
conjecture, proved ¬rst by Bragman and in a simpler way by Schrijver [340] states that an




154
n — n matrix A with 0, 1 entries and row sums r 1 , . . . , rn has
n
(rj !)1/rj .
per(A) ¤
j=1

We now show how these results can be applied.

Example 16.1. Latin rectangles. Suppose we are given a k —n Latin rectangle, k < n, so that
the symbols are 1, 2, . . . , n, and no symbol appears twice in any row or column. In how many
ways can we extend this rectangle to a (k + 1) — n Latin rectangle? To get a lower bound, form
an n — n matrix B = (bij ), with bij = 1 if i does not appear in column j of the rectangle, and
bij = 0 otherwise. Then the row and column sums of B are all equal to n ’ k, so (n ’ k) ’1 B
is doubly stochastic. Therefore per(B), which equals the desired number of ways of extending
the rectangle, is ≥ (n ’ k)n n’n n! by van der Waerden™s conjecture. By Minc™s conjecture,
we also have per(B) ¤ ((n ’ k)!)n/(n’k) . If we let L(k, n) denote the number of k — n Latin
rectangles, then L(1, n) = n!, and the bounds derived above for the number of ways to extend
any given rectangle give
k’1
{(n ’ j)n n’n n!} = n’kn (n!)2n ((n ’ k)!)’n ,
L(k, n) ≥ (16.1)
j=0
k’1
{(n ’ j)!}n/(n’j) .
L(k, n) ¤ (16.2)
j=0

<< . .

 20
( 24)



. . >>

Copyright Design by: Sunlight webdesign