LINEBURG

 страница 1(всего 24)ОГЛАВЛЕНИЕ След. стр. >>
Asymptotic Enumeration Methods
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
. 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 . 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 .
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 . 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. ) 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 . 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(всего 24)ОГЛАВЛЕНИЕ След. стр. >>