LINEBURG

ńņšąķčöą 20 |

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 |

Copyright © Design by: Sunlight webdesign