LINEBURG

ńņšąķčöą 1 |

A. M. Odlyzko

AT&T Bell Laboratories

Murray Hill, New Jersey 07974

1. Introduction

Asymptotic enumeration methods provide quantitative information about the rate of

growth of functions that count combinatorial objects. Typical questions that these meth-

ods answer are: (1) How does the number of partitions of a set of n elements grow with n?

(2) How does this number compare to the number of permutations of that set?

There do exist enumeration results that leave nothing to be desired. For example, if a n

denotes the number of subsets of a set with n elements, then we trivially have a n = 2n . This

answer is compact and explicit, and yields information about all aspects of this function. For

example, congruence properties of a n reduce to well-studied number theory questions. (This

is not to say that all such questions have been answered, though!) The formula a n = 2n also

provides complete quantitative information about a n . It is easy to compute for any value

of n, its behavior is about as simple as possible, and it holds uniformly for all n. However,

such examples are extremely rare. Usually, even when there is a formula for the function we

are interested in, it is a complicated one, involving summations or recurrences. The purpose

of asymptotic methods is to provide simple explicit formulas that describe the behavior of a

sequence for large values of indices. There is no satisfactory deļ¬nition of what is meant by

āsimpleā or by āexplicit.ā However, we can illustrate this concept by some examples. The

number of permutations of n letters is given by b n = n!. This is a compact notation, but only

in the sense that factorials are so widely used that they have a special symbol. The symbol n!

stands for n Ā· (n ā’ 1) Ā· (n ā’ 2) Ā· . . . Ā· 2 Ā· 1, and it is the latter formula that has to be used to answer

questions about the number of permutations. If one is after arithmetic information, such as the

highest power of 7, say, that divides n!, one can obtain it from the product formula, but even

then some work has to be done. For most quantitative purposes, however, n! = nĀ·(nā’1)Ā·. . .Ā·2Ā·1

is inadequate. Since this formula is a product of n terms, most of them large, it is clear that

n! grows rapidly, but it is not obvious just how rapidly. Since all but the last term are ā„ 2, we

have n! ā„ 2nā’1 , and since all but the last two terms are ā„ 3, we have n! ā„ 3 nā’2 , and so on.

On the other hand, each term is ā¤ n, so n! ā¤ n n . Better bounds can clearly be obtained with

greater care. The question such estimates raise is just how far can one go? Can one obtain an

estimate for n! that is easy to understand, compute, and manipulate? One answer provided by

asymptotic methods is Stirlingā™s formula: n! is asymptotic to (2Ļn) 1/2 (n/e)n as n ā’ ā, which

means that the limit as n ā’ ā of n!(2Ļn) ā’1/2 (n/e)ā’n exists and equals 1. This formula is

concise and gives a useful representation of the growth rate of n!. It shows, for example, that

for n large, the number of permutations on n letters is considerably larger than the number of

1

subsets of a set with 2 n log n elements.

Another simple example of an asymptotic estimate occurs in the āprobl`me des rencontresā

e

[81]. The number dn of derangements of n letters, which is the number of ways of handing

back hats to n people so that no person receives his or her own hat, is given by

n

n!

(ā’1)k

dn = . (1.1)

k!

k=0

This is a nice formula, yet to compute d n exactly with it requires substantial eļ¬ort, since the

summands are large, and at ļ¬rst glance it is not obvious how large d n is. However, we can

obtain from (1.1) the asymptotic estimate

dn

ā’ eā’1 as nā’ā. (1.2)

n!

To prove (1.2), we factor out n! from the sum in (1.1). We are then left with a sum of rapidly

decreasing terms that make up the initial segment of the series

ā

(ā’1)k

ā’1

e = ,

k!

k=0

and (1.2) follows easily. It can even be shown that d n is the nearest integer to eā’1 n! for all

n ā„ 1, see [81]. The estimate (1.2) does not allow us to compute d n , but combined with the

estimate for n! cited above it shows that d n grows like (2Ļn)1/2 nn eā’nā’1 . Further, (1.2) shows

that the fraction of all ways of handing out hats that results in every person receiving somebody

elseā™s hat is approximately 1/e. Results of this type are often exactly what is desired.

Asymptotic estimates usually provide information only about the behavior of a function

as the arguments get large. For example, the estimate for n! cited above says only that the

ratio of n! to (2Ļn)1/2 (n/e)n tends to 1 as n gets large, and says nothing about the behavior

of this ratio for any speciļ¬c value of n. There are much sharper and more precise bounds

for n!, and they will be presented in Section 3. However, it is generally true that the simpler

the estimate, the weaker and less precise it is. There seems to be an unavoidable tradeoļ¬

2

between conciseness and precision. Just about the simplest formula that exactly expresses n!

is n Ā· (n ā’ 1) Ā· . . . Ā· 2 Ā· 1. (We have to be careful, since there is no generally accepted deļ¬nition

of simplicity, and in many situations it is better to use other exact formulas for n!, such as the

ā n ā’t

integral formula n! = 0 t e dt for the Ī“-function. There are also methods for evaluating

n! that are somewhat more eļ¬cient than the straightforward evaluation of the product.) Any

other formula is likely to involve some loss of accuracy as a penalty for simplicity.

Sometimes, the tradeoļ¬s are clear. Let p(n) denote the number of partitions of an integer

n. The Rademacher convergent series representation [13, 23] for p(n) is valid for any n ā„ 1:

ā

d ā’1

p(n) = Ļ ā’1 2ā’1/2 Am (n)m1/2 (Ī»v sinh(Cmā’1 Ī»v )) , (1.3)

dv v=n

m=1

where

C = Ļ(2/3)1/2 , Ī»v = (v ā’ 1/24)1/2 , (1.4)

and the Am (n) satisfy

A1 (n) = 1, A2 (n) = (ā’1)n for all n ā„ 1 ,

|Am (n)| ā¤ m, for all m, n ā„ 1 ,

and are easy to compute. Remarkably enough, the series (1.3) does yield the exact integer

value of p(n) for every n, and it converges rapidly. (Although this is not directly relevant, we

note that using this series to compute p(n) gives an algorithm for calculating p(n) that is close

to optimal, since the number of bit operations is not much larger than the number of bits of

p(n).) By taking more and more terms, we obtain better and better approximations. The ļ¬rst

term in (1.3) shows that

d ā’1

p(n) = Ļ ā’1 2ā’1/2 +O(nā’1 exp(Cn1/2 /2)) ,

(Ī» sinh(CĪ»v )) (1.5)

dv v v=n

and if we donā™t like working with hyperbolic sines, we can derive from (1.5) the simpler (but

less precise) estimate

1 + O(nā’1/2 ) Cn1/2

p(n) = e , (1.6)

4 Ā· 31/2 n

valid for all n ā„ 1. Unfortunately, exact and rapidly convergent series such as (1.3) occur

infrequently in enumeration, and in general we have to be content with poorer approximations.

The advantage of allowing parameters to grow large is that in surprisingly many cases, even

when there do exist explicit expressions for the functions we are interested in, this procedure

does yield simple asymptotic approximations, when the inļ¬‚uence of less important factors falls

3

oļ¬. The resulting estimates can then be used to compare numbers of diļ¬erent kinds of objects,

decide what the most common objects in some category are, and so on. Even in situations

where bounds valid for all parameter values are needed, asymptotic estimates can be used to

suggest what form those bounds should take. Usually the error terms in asymptotic estimates

can be made explicit (although good bounds often require substantial work), and can be used

together with computations of small values to obtain universal estimates. It is common that

already for n not much larger than 10 (where n is the basic parameter) the asymptotic estimate

is accurate to within a few percent, and for n ā„ 100 it is accurate to within a fraction of a

percent, even though known proofs do not guarantee results as good as this. Therefore the

value of asymptotic estimates is much greater than if they just provided a picture of what

happens at inļ¬nity.

Under some conditions, asymptotic results can be used to prove completely uniform results.

For example, if there were any planar maps that were not four-colorable, then almost every large

planar map would not be four-colorable, as it would contain one of those small pathological

maps. Therefore if it could be proved that most large planar maps are four-colorable, we would

obtain a new proof of the four-color theorem that would be more satisfactory to many people

than the original one of Haken and Appel. Unfortunately, while this is an attractive idea, no

proof of the required asymptotic estimate for the normal chromatic number of planar maps

has been found so far.

Asymptotic estimates are often useful in deciding whether an identity is true. If the growth

rates of the two functions that are supposed to be equal are diļ¬erent, then the coincidence of

initial values must be an accident. There are also more ingenious ways, such as that of Exam-

ple 13.1, for deducing nonexistence of identities in a wide class from asymptotic information.

Sometimes asymptotics is used in a positive way, to suggest what identities might hold.

Simplicity is an important advantage of asymptotic estimates. They are even more useful

when no explicit formulas for the function being studied are available, and one has to deal

with indirect relations. For example, let T n be the number of rooted unlabeled trees with n

vertices, so that T0 = 0, T1 = T2 = 1, T3 = 2, T4 = 4, . . . . No explicit formula for the T n is

known. However, if

ā

Tn z n

T (z) = (1.7)

n=1

4

is the ordinary generating function of T n , then Cayley and PĀ“lya showed that

o

ā

T (z k )/k

T (z) = z exp . (1.8)

k=1

This functional equation can be derived using the general PĀ“lya-Redļ¬eld enumeration method,

o

an approach that is sketched in Section 15. Example 15.1 shows how analytic methods can be

used to prove, starting with Eq. (1.8), that

Tn ā¼ Cr ā’n nā’3/2 as nā’ā, (1.9)

where

C = 0.4399237 . . . , r = 0.3383219 . . . , (1.10)

are constants that can be computed eļ¬ciently to high precision. For n = 20, T n = 12, 826, 228,

whereas Cr ā’20 20ā’3/2 = 1.274 . . . Ć— 107 , so asymptotic formula (1.9) is accurate to better than

1%. Thus this approximation is good enough for many applications. It can also be improved

easily by adding lower order terms.

Asymptotic enumeration methods are a subļ¬eld of the huge area of general asymptotic anal-

ysis. The functions that occur in enumeration tend to be of restricted form (often nonnegative

and of regular growth, for example) and therefore the repertoire of tools that are commonly

used is much smaller than in general asymptotics. This makes it possible to attempt a concise

survey of the most important techniques in asymptotic enumeration. The task is not easy,

though, as there has been tremendous growth in recent years in combinatorial enumeration

and the closely related ļ¬eld of asymptotic analysis of algorithms, and the sophistication of the

tools that are commonly used has been increasing rapidly.

In spite of its importance and growth, asymptotic enumeration has seldom been presented

in combinatorial literature at a level other than that of a research paper. There are several

books that treat it [43, 81, 175, 177, 235, 236, 237, 377], but usually only brieļ¬‚y. The only

comprehensive survey that is available is the excellent and widely quoted paper of Bender [33].

Unfortunately it is somewhat dated. Furthermore, the last two decades have also witnessed

a ļ¬‚owering of asymptotic analysis of algorithms, which was pioneered and popularized by

Knuth. Combinatorial enumeration and analysis of algorithms are closely related, in that both

deal with counting of particular structures. The methods used in the two ļ¬elds are almost

the same, and there has been extensive cross-fertilization between them. The literature on

theoretical computer science, especially on average case analysis of algorithms, can therefore

5

be used fruitfully in asymptotic enumeration. One notable survey paper in that area is that

of Vitter and Flajolet [371]. There are also presentations of relevant methods in the books

[177, 209, 235, 236, 237, 223]. Section 18 is a guide to the literature on these topics.

The aim of this chapter is to survey the most important tools of asymptotic enumeration,

point out references for the results and methods that are discussed, and to mention additional

relevant papers that have other techniques that might be useful. It is intended for a reader

who has already used combinatorial, algebraic, or probabilistic methods to reduce a problem to

that of estimating sums, coeļ¬cients of a generating function, integrals, or terms in a sequence

satisfying some recursion. How such a reduction is to be accomplished will be dealt with

sparingly, since it is a large subject that is already covered extensively in other chapters,

especially [?]. We will usually assume that this task has been done, and will discuss only the

derivation of asymptotic estimates.

The emphasis in this chapter is on elementary and analytic approaches to asymptotic

problems, relying extensively on explicit generating functions. There are other ways to solve

some of the problems we will discuss, and probabilistic methods in particular can often be

used instead. We will only make some general remarks and give references to this approach in

Section 16.

The only methods that will be discussed in detail are fully rigorous ones. There are also

methods, mostly from classical applied mathematics (cf. [31]) that are powerful and often give

estimates when other techniques fail. However, we do not treat them extensively (aside from

some remarks in Section 16.4) since many of them are not rigorous.

Few proofs are included in this chapter. The stress is on presentation of basic methods, with

discussions of their range of applicability, statements of general estimates derivable from them,

and examples of their applications. There is some repetitiveness in that several functions,

such as n!, are estimated several times. The purpose of doing this is to show how diļ¬erent

methods compare in their power and ease of use. No attempt is made to present derivations

starting from ļ¬rst principles. Some of the examples are given with full details of the asymptotic

analysis, to explain the basic methods. Other examples are barely more than statements of

results with a brief explanation of the method of proof and a reference to where the proof can

be found. The reader might go through this chapter, possibly in a random order, looking for

methods that might be applicable to a speciļ¬c problem, or can look for a category of methods

that might ļ¬t the problem and start by looking at the corresponding sections.

6

There are no prerequisites for reading most of this chapter, other than acquaintance with

advanced calculus and elementary asymptotic estimates. Many of the results are presented

so that they can be used in a cookbook fashion. However, many of the applications require

knowledge of complex variables.

Section 2 presents the basic notation used throughout the chapter. It is largely the standard

one used in the literature, but it seemed worthwhile summarizing it in one place. Section 3 is

devoted to a brief discussion of identities and related topics. While asymptotic methods are

useful and powerful, they can often be either augmented or entirely replaced by identities, and

this section points out how to use them.

Section 4 summarizes the most important and most useful estimates in combinatorial enu-

meration, namely those related to factorials and binomial coeļ¬cients. Section 5 is the ļ¬rst

one to feature an in-depth discussion of methods. It deals with estimates of sums in terms

of integrals, summation formulas, and the inclusion-exclusion principle. However, it does not

present the most powerful tool for estimation of sums, namely generating functions. These are

introduced in Section 6, which presents some of the basic properties of, and tools for dealing

with generating functions. While most generating functions that are used in combinatorial

enumeration converge at least in some neighborhood of the origin, there are also many non-

convergent ones. Section 7 discusses some estimates that apply to all formal series, but are

especially useful for nonconvergent ones.

Section 8 is devoted to estimates for convergent power series that do not use complex

variables. While not as powerful as the analytic methods presented later, these techniques are

easy to use and suļ¬ce in many applications.

Section 9 presents a variety of techniques for determining the asymptotics of recurrence

relations. Many of these methods are based on generating functions, and some use analytic

methods that are discussed later in the chapter. They are presented at this point because they

are basic to combinatorial enumeration, and they also provide an excellent illustration of the

power of generating functions.

Section 10 is an introduction to the analytic methods for estimating generating functions.

Many of the results mentioned here are common to all introductory complex analysis courses.

However, there are also many, especially those in Sections 10.4 and 10.5, are not as well known,

and are of special value in asymptotics.

Sections 11 and 12 present the main methods used in estimation of coeļ¬cients of analytic

7

functions in a single variable. The basic principle is that the singularities of the generating

function that are closest to the origin determine the growth rate of the coeļ¬cients. If the func-

tion does not grow too fast as it approaches those singularities, the methods of Section 11 are

usually applicable, while if the growth rate is high, methods of Section 12 are more appropriate.

Sections 13ā“15 discuss extensions of the basic methods of Sections 10ā“12 to multivariate

generating functions, integral transforms, and problems that involve a combination of methods.

Section 16 is a collection of miscellaneous methods and results that did not easily ļ¬t into any

other section, yet are important in asymptotic enumeration. Section 17 discusses the extent

to which computer algebra systems can be used to derive asymptotic information. Finally,

Section 18 is a guide to further reading on asymptotics, since this chapter does not provide

complete coverage of the topic.

2. Notation

The symbols O, o, and ā¼ will have the usual meaning throughout this paper:

f (z) = O(g(z)) as z ā’ w means f (z)/g(z) is bounded as z ā’ w ;

f (z) = o(g(z)) as z ā’ w means f (z)/g(z) ā’ 0 as z ā’ w ;

f (z) ā¼ g(z) as z ā’ w means f (z)/g(z) ā’ 1 as z ā’ w .

When an asymptotic relation is stated for an integer variable n instead of z, it will implicitly

be taken to apply only for integer values of n ā’ w, and then we will always have w = ā or

w = ā’ā. An introduction to the use of this notation can be found in [175]. Only a slight

acquaintance with it is assumed, enough to see that (1 + O(n ā’1/3 ))n = exp(O(n2/3 )) and

log(n + n1/2 ) = log(n) + nā’1/2 ā’ (2n)ā’1 + O(nā’3/2 ).

The notation x ā’ w ā’ for real w means that x tends to w only through values x < w.

Some asymptotic estimates refer to uniform convergence. As an example, the statement

that f (z) ā¼ (1 ā’ z)ā’2 as z ā’ 1 uniformly in |Arg(1 ā’ z)| < 2Ļ/3 means that for every > 0,

there is a Ī“ < 0 such that

|f (z)(1 ā’ z)2 ā’ 1| ā¤

for all z with 0 < |1 ā’ z| < Ī“, |Arg(1 ā’ z)| < 2Ļ/3. This is an important concept, since lack

of uniform convergence is responsible for many failures of asymptotic methods to yield useful

results.

8

Generating functions will usually be written in the form

ā

fn z n ,

f (z) = (2.1)

n=0

and we will use the notation [z n ]f (z) for the coeļ¬cient of z n in f (z), so that if f (z) is deļ¬ned

by (2.1), [z n ]f (z) = fn . For multivariate generating functions, [x m y n ]f (x, y) will denote the

coeļ¬cient of xm y n , and so on. If an denotes a sequence whose asymptotic behavior is to be

studied, then in combinatorial enumeration one usually uses either the ordinary generating

function f (z) deļ¬ned by (2.1) with f n = an , or else the exponential generating function f (z)

deļ¬ned by (2.1) with fn = an /n!. In this chapter we will not be concerned with the question

of which type of generating function is best in a given context, but will assume that a gener-

ating function is given, and will concentrate on methods of extracting information about the

coeļ¬cients from the form we have.

Asymptotic series, as deļ¬ned by PoincarĀ“, are written as

e

ā

ak nā’k ,

fn ā¼ (2.2)

k=0

and mean that for every K ā„ 0,

K

ak nā’k + O(nā’Kā’1 )

fn = as nā’ā. (2.3)

k=0

The constant implied by the O-notation may depend on K. It is unfortunate that the same

symbol is used to denote an asymptotic series as well as an asymptotic relation, deļ¬ned in

the ļ¬rst paragraph of this section. Confusion should be minimal, though, since asymptotic

relations will always be written with an explicit statement of the limit of the argument.

The notation f (z) ā g(z) will be used to indicate that f (z) and g(z) are in some vague

sense close together. It is used in this chapter only in cases where a precise statement would

be cumbersome and would not help in explaining the essence of the argument.

All logarithms will be natural ones to base e unless speciļ¬ed otherwise, so that log 8 =

2.0794 . . ., log 2 8 = 3. The symbol x denotes the greatest integer ā¤ x. The notation x ā’ 1 ā’

means that x tends to 1, but only from the left, and similarly, x ā’ 0 + means that x tends to

0 only from the right, through positive values.

3. Identities, indeļ¬nite summations, and related approaches

Asymptotic estimates are useful, but often they can be avoided by using other methods.

n

2k as k and n vary,

For example, the asymptotic methods presented later yield estimates for k

9

n

2k for n ļ¬xed and k running over the

which can be used to estimate accurately the sum of k

full range from 0 to n. That is a general and eļ¬ective process, but somewhat cumbersome. On

the other hand, by the binomial theorem,

n

nk

2 = (1 + 2)n = 3n . (3.1)

k

k=0

This is much more satisfactory and simpler to derive than what could be obtained from applying

asymptotic methods to estimate individual terms in the sum. However, such identities are

seldom available. There is nothing similar that can be applied to

nk

2, (3.2)

k

kā¤n/5

and we are forced to use asymptotic methods to estimate this sum.

Recognizing when some combinatorial identity might apply is not easy. The literature on

this subject is huge, and some of the references for it are [172, 174, 186, 216, 336]. Many of the

books listed in the references are useful for this purpose. Generating functions (see Section 6)

are one of the most common and powerful tools for proving identities. Here we only mention

two recent developments that are of signiļ¬cance for both theoretical and practical reasons. One

is Gosperā™s algorithm for indeļ¬nite hypergeometric summation [171, 175]. Given a sequence

a1 , a2 , . . ., Gosperā™s algorithm determines whether the sequence of partial sums

n

bn = ak , n = 1, 2, . . . (3.3)

k=1

ńņšąķčöą 1 |

Copyright © Design by: Sunlight webdesign