LINEBURG


<< . .

 21
( 24)



. . >>


Sharper estimates for L(k, n) have been obtained through more powerful and complicated
methods by Godsil and McKay [163]. They obtain an asymptotic relation for L(k, n) that is
valid for k = o(n6/7 ), and improved estimates for other k. (It is known that for any ¬xed k,
the sequence L(k, n) satis¬es a linear recurrence with polynomial coe¬cients [160].)
 




There are problems in which inequalities for permanents give the correct asymptotic esti-
mates. One such example is presented in [318] which discusses a variation on the “probl`me
e
des rencontres.”

16.2. Probability theory and branching process methods

Many combinatorial enumeration results can be phrased in probabilistic language, and
a few probabilistic techniques have appeared in the preceding sections. However, the stress
throughout this chapter has been on elementary and generating function approaches to asymp-
totic enumeration problems. Probabilistic methods provide another way to approach many of

155
these problems. This has been appreciated more in the former Soviet Union than in the West,
as can be seen in the books [240, 241, 338].
The last few years have seen a great increase in the applications of probabilistic methods
to combinatorial enumeration and analysis of algorithms. Many powerful tools, such as mar-
tingales, branching processes, and Brownian motion asymptotics have been brought to bear
on this topic. General introductions and references to these topics can be found in Chapter ?
as well as in [5, 11, 20, 21, 27, 92, 93, 108, 258, 260, 262, 270].

16.3. Statistical physics

There is an extensive literature in mathematical physics concerned with asymptotic enu-
meration, especially in Ising models of statistical mechanics and percolation methods. Many
of the methods are related to combinatorial enumeration. For an introduction to them, see
Chapter ? or the books [30, 226].

16.4. Classical applied mathematics

There are many techniques, such as the ray method and the WKB method, that have
been developed for solving di¬erential and integral equations in what we might call classical
applied mathematics. An introduction to them can be found in [31]. They are powerful, but
they have the disadvantage that most of them are not rigorous, since they make assumptions
about the form or the stability of the solution that are likely to be true, but have not been
established. Therefore we have not presented such methods in this survey. For some examples
of the nonrigorous applications of these methods to asymptotic enumeration, see the papers
of Knessl and Keller [231, 232]. It is likely that with additional work, more of these methods
will be rigorized, which will increase their utility.

17. Algorithmic and automated asymptotics

Deriving asymptotic expansions often involves a substantial amount of tedious work. How-
ever, much of it can now be done by computer symbolic algebra systems such as Macsyma,
Maple, and Mathematica. There are many widely available packages that can compute Taylor
series expansions. Several can also compute certain types of limits, and some have implemented
Gosper™s inde¬nite hypergeometric summation algorithm [171]. They ease the burden of car-
rying out the necessary but uninteresting parts of asymptotic analysis. They are especially



156
useful in the exploratory part of research, when looking for identities, formulating conjectures,
or searching for counterexamples.
Much more powerful systems are being developed. Given a sequence, there are algorithms
that attempt to guess the generating function of that sequence [46, 162]. It is possible to
go much further than that. Many of the asymptotic results in this chapter are stated in
explicit forms. As an example, the asymptotics of a linear recurrence is derived easily from the
characteristic polynomial and the initial conditions, as was shown in Section 9.1. One needs
to compute the roots of the characteristic polynomial, and that is precisely what computer
systems do well. It is therefore possible to write programs that will derive the asymptotics
behavior from the speci¬cation of the recurrence. More generally, one can analyze asymptotics
of a much greater variety of generating functions. Flajolet, Salvy, and Zimmermann [124, 139]
have written a powerful program for just such computations. Their system uses Maple to carry
out most of the basic analytic computations. It contains a remarkable amount of automated
expertise in recognizing generating functions, computing their singularities, and extracting
asymptotic information about their coe¬cients. For example, if

f (z) = ’ log[1 + z log(1 ’ z 2 )] + (1 ’ z 3 )’5 + exp(zez ) , (17.1)

then the Flajolet-Salvy-Zimmermann system can determine that the singularity of f (z) that
is closest to the origin is at z = ρ, where ρ is the smallest positive root of

1 = ’ρ log(1 ’ ρ2 ) , (17.2)

and then can deduce that

[z n ]f (z) = n’1 ρ’n + O(n’2 ρ’n ) as n ’ ∞ . (17.3)

The Flajolet-Salvy-Zimmermann system is even more powerful than indicated above, since
it does not always require an explicit presentation of the generating function. Instead, often
it can accept a formal description of an algorithm or data structure, derive the generating
function from that, and then obtain the desired asymptotic information. For example, it can
show that the average path length in a general planar tree with n nodes is
1 1/2 3/2 1
π n + n + O(n1/2 ) as n ’ ∞ . (17.4)
2 2
What makes systems such as that of [139] possible is the phenomenon, already mentioned in
Section 6, that many common combinatorial operations on sets, such as unions and permuta-
tions, correspond in natural ways to operations on generating functions.

157
Further work extending that of [139] is undoubtedly going to be carried out. There are
some basic limitations coming from the undecidability of even simple problems of arithmetic,
which are already known to impose a limitation on the theories of inde¬nite integration. If we
approximate a sum by an integral
b
x’± dx , (17.5)
a

then as a next step we need to decide whether ± = 1 or not, since if ± = 1, this integral
is log(b/a) (assuming 0 < a < b < ∞), whereas if ± = 1, it is (b 1’± ’ a1’± )/(1 ’ ±).
Deciding whether ± = 1 or not, when ± is given implicitly or by complicated expressions, can
be arbitrarily complicated. However, such di¬culties are infrequent, and so one can expect
substantial increase in the applicability of automated systems for asymptotic analysis.
The question of decidability of asymptotic problems and generic properties of combinatorial
structures that can be speci¬ed in various logical frameworks has been treated by Compton in a
series of papers [77, 78, 79]. There is the beautiful recent theory of 0-1 laws for random graphs,
which says that certain (so-called ¬rst-order) properties are true with probability either 0 or 1
for random graphs. Compton proves that certain classes of asymptotic theories also have 0-1
laws, and describes general properties that have to hold for almost all random structures in
certain classes. His analysis uses Tauberian theorems and Hayman admissibility to determine
asymptotic behavior. For some further developments in this area, see also [35].

18. Guide to the literature

This section presents additional sources of information on asymptotic methods in enumer-
ation and analysis of algorithms. It is not meant to be exhaustive, but is intended to be used
as a guide in searching for methods and results. Many references have been presented already
throughout this chapter. Here we describe only books that cover large areas relevant to our
subject.
An excellent introduction to the basic asymptotic techniques is given in [175]. That book,
intended to be an undergraduate textbook, is much more detailed than this chapter, and
assumes no knowledge of asymptotics, but covers fewer methods. A less comprehensive and
less elementary book that is oriented towards analysis of algorithms, but provides a good
introduction to many asymptotic enumeration methods, is [177].
The best source from which to learn the basics of more advanced methods, including many
of those covered in this chapter, is de Bruijn™s book [63]. It was not intended particularly

158
for those interested in asymptotic enumeration, but almost all the methods in it are relevant.
De Bruijn™s volume is extremely clear, and provides insight into why and how various methods
work.
General presentations of asymptotic methods, although usually with emphasis on applica-
tions to applied mathematics (di¬erential equations, special functions, and so on) are available
in the books [54, 100, 114, 115, 315, 344, 354, 372, 382, 385]. Integral transforms are treated
extensively in [89, 95, 116, 299, 365]. Books that deal with asymptotics arising in the analysis
of algorithms or probabilistic methods include [11, 55, 108, 209, 223, 240, 241, 270, 338].
Nice general introductions to combinatorial identities, generating functions, and related
topics are presented in [81, 351, 377]. Further material can be found in
[13, 88, 99, 173, 188, 335, 336].
A very useful book is the compilation [168]. While it does not discuss methods in too much
detail, it lists a wide variety of enumerative results on algorithms and data structures, and
gives references where the proofs can be found.
Last, but not least in our listing, is Knuth™s three-volume work [235, 236, 237]. While it
is devoted primarily to analysis of algorithms, it contains an enormous amount of material on
combinatorics, especially asymptotic enumeration.

Acknowledgements

The author thanks R. Arratia, E. A. Bender, E. R. Can¬eld, H. Cohen, P. Flajolet, Z. Gao,
D. E. Knuth, V. Privman, L. B. Richmond, E. Schmutz, N. J. A. Sloane, D. Stark, S. Tavar´,
e
H. S. Wilf, D. Zagier and D. Zeilberger for their helpful comments on preliminary drafts of
this chapter.




159
References

[1] J. Acz´l, Lectures on Functional Equations and Their Applications, Academic Press,
e
1966.

[2] C. R. Adams, On the irregular cases of linear ordinary di¬erence equations, Trans. Am.
Math. Soc., 30 (1928), pp. 507“541.

[3] A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quart.,
11 (1973), 429“437.

[4] J. A. Aizenberg and A. P. Yuzhakov, Integral Representations and Residues in Multi-
dimensional Complex Analysis, Trans. Math. Monographs, No. 58, Amer. Math. Soc.,
1983.

[5] D. Aldous, Probability approximations via the Poisson clumping heuristic, Springer-
Verlag, 1989.

[6] J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Comp. Science,
98 (1992), 163“197.

[7] G. Almkvist, Proof of a conjecture about unimodal polynomials, J. Number Theory, 32
(1989), 43“57.

[8] G. Almkvist, Exact asymptotic formulas for the coe¬cients of nonmodular functions, J.
Number Theory, 38 (1991), 145“160.

[9] G. Almkvist, A rather exact formula for the number of plane partitions, A Tribute to
Emil Grosswald, M. Knapp and M. Sheingorn, eds., Amer. Math. Soc., to appear.

[10] G. Almkvist and G. E. Andrews, A Hardy-Ramanujan-Rademacher formula for restricted
partitions, J. Number Theory, 38 (1991), 135“144.

[11] N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, 1992.

[12] G. E. Andrews, Applications of basic hypergeometric functions, SIAM Review, 16 (1974),
pp. 441“484.

[13] G. E. Andrews, The Theory of Partitions, Addison“Wesley, 1976.


160
[14] T. M. Apostol, Mathematical Analysis, Addison Wesley, 1957.

[15] T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1976.

[16] J. Arney and E. D. Bender, Random mappings with constraints on coalescence and
number of origins, Paci¬c J. Mathematics, 103 (1982), pp. 269“294.

[17] R. Arratia, L. Goldstein, and L. Gordon, Poisson approximation and the Chen-Stein
method, Statistical Science 5 (1990), 402“423.

[18] R. Arratia, L. Gordon, and M. S. Waterman, The Erd¨s-R´nyi law in distribution for
oe
coin tossing and sequence matching, Ann. Statist. 18 (1990), 539“570.

[19] R. Arratia and S. Tavar´, The cycle structure of random permutations, Ann. Prob., 20
e
(1992), 1567“1591.

[20] R. Arratia and S. Tavar´, Limit theorems for combinatorial structures via discrete process
e
approximation, Random Structures Alg., 3 (1992), 321“345.

[21] R. Arratia and S. Tavar´, Independent process approximations for random combinatorial
e
structures, Adv. Math. (1993), in press.

[22] F. C. Auluck and C. B. Haselgrove, On Ingham™s Tauberian theorem for partitions, Proc.
Cambridge Philos. Soc., 48 (1952), pp. 566“570.

[23] R. Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963.

[24] R. Baeza-Yates, R. Casas, J. Diaz, and C. Martinez, On the average size of the intersec-
tion of binary trees, SIAM J. Comp. 21 (1992), 24“32.

[25] R. A. Baeza-Yates, A trivial algorithm whose analysis is not: a continuation, BIT, 29
(1989), 378“394.

[26] T. Bang, Om matrixfunktioner som med et numerisk lille de¬cit viser v. d. Waerdens
permanenthypotese, Proc. 1976 Turku Scand. Math. Congress.

[27] A. D. Barbour, L. Holst, and S. Janson, Poisson Approximation, Oxford University Press,
1992.

[28] E. W. Barnes, On the homogeneous linear di¬erence equation of the second order with
linear coe¬cients, Messenger Math., 34 (1904), pp. 52“71.

161
[29] P. M. Batchelder, An Introduction to Linear Di¬erence Equations, Harvard Univ. Press,
1927. Dover reprint, 1967.

[30] R. J. Baxter, Exactly Solved Models in Statistical Mechanics, Academic Press, 1982.

[31] C. M. Bender and S. A. Orszag, Applied Mathematical Methods for Scientists and Engi-
neers, McGraw-Hill, 1978.

[32] E. A. Bender, Central and local limit theorem applied to asymptotic enumeration, J.
Comb. Theory Ser. A., 15 (1973), pp. 91“111.

[33] E. A. Bender, Asymptotic methods in enumeration, SIAM Review, 16 (1974), pp. 485“
515.

[34] E. A. Bender, An asymptotic expansion for the coe¬cients of some formal power series,
J. London Math. Soc., 9 (1975), pp. 451“458.

[35] E. A. Bender, Z.-C. Gao, and L. B. Richmond, Submaps of maps. I. General 0-1 laws, J.
Comb. Theory, B 55 (1992), 104“117.

[36] E. A. Bender and J. R. Goldman, Enumerative uses of generating functions, Indiana
Univ. Math. J., 20 (1971), pp. 753“765.

[37] E. A. Bender, A. M. Odlyzko, and L. B. Richmond, The asymptotic number of irreducible
partitions, European J. Combinatorics, 6 (1985), pp. 1“6.

[38] E. A. Bender and L. B. Richmond, Central and local limit theorems applied to asymptotic
enumeration. II: Multivariate generating functions, J. Comb. Theory B, 34 (1983), 255“
265.

[39] E. A. Bender and L. B. Richmond, An aymptotic expansion for the coe¬cients of analytic
generating functions, Discrete Math., 50 (1984), pp. 135“141.

[40] E. A. Bender and L. B. Richmond, An asymptotic expansion for the coe¬cients of some
power series II: Lagrange inversion, Discrete Mathematics, 50 (1984), pp. 135“141.

[41] E. A. Bender and L. B. Richmond, A survey of the asymptotic behaviour of maps, J.
Comb. Theory, Ser. B, 40 (1986), pp. 297“329.



162
[42] E. A. Bender, L. B. Richmond, and S. G. Williamson, Central and local limit theorems
applied to asymptotic enumeration. III. Matrix recursions, J. Comb. Theory (A) 35
(1983), 263“278.

[43] E. A. Bender and S. G. Williamson, Foundations of Applied Combinatorics, Addison-
Wesley, 1991.

[44] F. Bergeron and G. Cartier, Darwin: Computer algebra and enumerative combinatorics,
STACS“88, R. Cori and M. Wirsing, eds., LNCS, 294 (1988), pp. 393“394.

[45] F. Bergeron and G. Labelle and P. Leroux, Functional equations for data structures,
STACS“88, R. Cori and M. Wirsing, eds., LNCS, 294 (1988), pp. 73“80.

[46] F. Bergeron and S. Plou¬e, Computing the generating function of a series given its ¬rst
few terms, Experimental Math. 1 (1992), 307“312.

[47] B. C. Berndt and L. Schoenfeld, Periodic analogues of the Euler-Maclaurin and Poisson
summation formulas with applications to number theory, Acta Arith. 28 (1975/76), 23“
68.

[48] M. V. Berry and C. J. Howls, Hyperasymptotics, Proc. Royal Soc. London A, 430 (1990),
653“667.

[49] A. Bertozzi and J. McKenna, Multidimensional residues, generating functions, and their
application to queueing networks, SIAM Review 35 (1993), 239“268.

[50] P. Billingsley, Probability and Measure, Wiley, 1979.

[51] G. D. Birkho¬, General theory of linear di¬erence equations, Trans. Amer. Math. Soc.,
12 (1911), pp. 243“284.

[52] G. D. Birkho¬, Formal theory of irregular linear di¬erence equations, Acta Math., 54
(1930), pp. 205“246.

[53] G. D. Birkho¬ and W. J. Trjitzinsky, Analytic theory of singular di¬erence equations,
Acta Math., 60 (1932), pp. 1“89.

[54] N. Bleistein and R. A. Handelsman, Asymptotic Expansions of Integrals, 2nd edition,
Holt, Rinehart and Winston, New York, 1975.

163
[55] B. Bollob´s, Random Graphs, Academic Press, 1985.
a

[56] F. Brenti, Unimodal, Log-concave, and P´lya Frequency Sequences in Combinatorics,
o
Memoirs Amer. Math. Soc., no. 413 (1989).

[57] F. Brenti, G. F. Royle, and D. G. Wagner, Location of zeros of chromatic and related
polynomials of graphs, to be published.

[58] N. A. Brigham, A general asymptotic formula for partition functions, Proc. Amer. Math.
Soc., 1 (1950), pp. 182“191.

[59] T. I™a. Bromwich, An Introduction to the Theory of In¬nite Series, 2nd rev. ed., Macmil-
lan, London, 1955.

[60] G. G. Brown and B. O. Shubert, On random binary trees, Math. Oper. Res., 9 (1984),
pp. 43“65.

[61] N. G. de Bruijn, On Mahler™s partition problem, Indagationes Math., 10 (1948), pp. 210“
220.

[62] N. G. de Bruijn, The di¬erence“di¬erential equation F (x) = e±x+β F (x’1), Indagationes
Math., 15 (1953), pp. 449“458.

[63] N. G. de Bruijn, Asymptotic Methods in Analysis, North“Holland, Amsterdam, 1958.

[64] N. G. de Bruijn, D. E. Knuth, and S. O. Rice, The average height of planted plane trees,
in Graph Theory and Computing, R.“C. Read, ed., Academic Press, New York, 1972,
pp. 15“22.

[65] E. R. Can¬eld, Central and local limit theorems for the coe¬cients of polynomials of
binomial type, J. Comb. Theory, Series A, 23 (1977), pp. 275“290.

[66] E. R. Can¬eld, The asymptotic behavior of the Dickman“de Bruijn function, Congressus
Numerantium, 35 (1982), pp. 139“148.

[67] E. R. Can¬eld, Remarks on an asymptotic method in combinatorics, J. Comb. Theory,
Series A, 37 (1984), pp. 348“352.

[68] M. Car, Factorisation dans Fq [X], C. R. Acad. Sci. Paris S´rie I, 294 (1982), pp. 147“
e
150.

164
[69] M. Car, Ensembles de polynˆmes irr´ductibles et th´r`mes de densit´, Acta Arith, 44
o e ee e
(1984), pp. 323“342.

[70] L. Carlitz, Permutations, sequences and special functions, SIAM Review, 17 (1975),
pp. 298“322.

[71] R. Casas, D. Diaz, and C. Martinez, Statistics on random trees, in Automata, Languages,
and Programming (Proc. 18th ICALP, Madrid, 1991), J. Leach Albert, B. Monien, and
M. Rodriguez Artalejo, eds., Springer LNCS #510, 1991, pp. 186“203.

[72] J. W. S. Cassels, On the representation of integers as the sums of distinct summands

<< . .

 21
( 24)



. . >>

Copyright Design by: Sunlight webdesign