LINEBURG


<< . .

 24
( 24)



u

[320] G. P´lya, Kombinatorische Anzahlbestimmungen f¨ r Gruppen, Graphen und chemische
o u
Verbindungen, Acta Math., 68 (1937), pp. 145“254.

[321] G. P´lya, On the number of certain lattice polygons, J. Combinatorial Theory 6 (1969),
o
102“105.

[322] G. P´lya and R. C. Read, Combinatorial Enumeration of Groups, Graphs, and Chemical
o
Compounds, Springer, 1987.

[323] G. P´lya and G. Szeg¨, Problems and Theorems in Analysis, 2 volumes, English trans-
o o
lation, Springer, 1972 and 1976.

[324] A. Popken, Asymptotic expansions from an algebraic standpoint, Indagationes Math.,
15 (1953), pp. 131“143.

[325] A. G. Postnikov, Tauberian theory and its applications, Proc. Steklov Inst. Math., 144;
English translation, Amer. Math. Soc. Transl. (1980).

[326] V. Privman and N. M. Svrakic, Di¬erence equations in statistical mechanics: I. Cluster
statistics models and II. Solid-on-solid models in two dimensions, J. Stat. Phys. 51 (1988),
1091“1110 and 1111“1126.


183
[327] V. Privman and N. M. Svrakic, Directed Models of Polymers, Interfaces, and Clusters:
Scaling and Finite-Size Properties, Lecture Notes in Physics #338, Springer, 1989.

[328] H. Rademacher, On the partition function, Proc. London Math. Soc., 43 (1937), pp. 241“
254.

[329] A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Ad-
vances Math., 41 (1981), 115“136.

[330] A. R´nyi, Three more proofs and a generalization of a theorem of Irving Weiss, Magyar
e
Tud. Akad. Mat. Kutat´ Int. K¨zl., 7 (1962), 203“214.
o o

[331] A. R´nyi and G. Szekeres, On the height of trees, J. Austral. Math. Soc., 7 (1967),
e
pp. 497“507.

[332] L. B. Richmond, Asymptotic relations for partitions, J. Number Theory, 4 (1975), 389“
405.

[333] L. B. Richmond, The moments of partitions. II, Acta Arith., 28 (1975), 229“243.

[334] L. B. Richmond, Asymptotic relations for partitions, Trans. Amer. Math. Soc., 219
(1976), 379“385.

[335] J. Riordan, Introduction to Combinatorial Analysis, John Wiley, New York, 1958.

[336] J. Riordan, Combinatorial Identities, Wiley, 1968.

[337] K. F. Roth and G. Szekeres, Some asymptotic formulae in the theory of partitions, Quart.
J. Math. Oxford Ser., 5 (1954), pp. 241“259.

[338] V. N. Sachkov, Probabilistic Methods in Combinatorial Analysis (in Russian), Nauka,
Moscow, 1978.

[339] E. Schmutz, Asymptotic expansions for the coe¬cients of e P (z) , Bull. London Math. Soc.
21 (1989), pp. 482“486.

[340] A. Schrijver, A short proof of Minc™s conjecture, J. Comb. Theory (A), 25 (1978), 80“83.

[341] R. Sedgewick, Data movement in odd“even merging, SIAM J. Comput., 7 (1978),
pp. 239“272.


184
[342] L. A. Shepp and S. P. Lloyd, Ordered cycle lengths in a random permutation, Trans.
Amer. Math. Soc., 121 (1966), pp. 340“357.

[343] J. A. Shohat and J. D. Tamarkin, The Problem of Moments, Amer. Math. Soc., 1943.

[344] L. Sirovich, Techniques of Asymptotic Analysis, Springer Verlag, 1971.

[345] N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973. A revised and
expanded edition is in press.

[346] N. J. A. Sloane, The New Book of Integer Sequences, Freeman, 1994, to be published.

[347] I. N. Sneddon, The Uses of Integral Transforms, McGraw, 1972.

[348] J. Spencer, Ten Lectures on the Probabilistic Method, SIAM, 1987.

[349] R. P. Stanley, Generating Functions, in Studies in Combinatorics, M.A.A. Studies in
Mathematics, Vol. 17., G“C. Rota, ed., Math. Ass. of America, 1978, pp. 100“141.

[350] R. P. Stanley, Di¬erentiably ¬nite power series, European J. Combinatorics, 1 (1980),
175“188.

[351] R. P. Stanley, Enumerative Combinatorics, Wadsworth and Brooks/Cole, Monterey,
1986.

[352] R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and ge-
ometry, pp. 500“535 in Graph Theory and its Applications: East and West, Annals New
York Acad. Sci., no. 576, 1989.

[353] K. B. Stolarsky, Power and exponential sums of digital sums related to binomial coe¬-
cient parity, SIAM J. Appl. Math., 32 (1977), 717“730.

[354] G. Szeg¨, Orthogonal Polynomials, Amer. Math. Soc. Coll. Publ., vol. 23, rev. ed., Amer.
o
Math. Soc., New York, 1959.

[355] G. Szekeres, Some asymptotic formulae in the theory of partitions. II Quart. J. Math.
Oxford, Ser. 2, 4 (1953), pp. 96“111.

[356] G. Szekeres, Regular iteration of real and complex functions, Acta Math., 100 (1958),
pp. 103“258.


185
[357] G. Szekeres, Distribution of labelled trees by diameter, pp. 392“397 in Combinatorial
Mathematics X, Proc. 10-th Australian Conf. Comb. Math., Lecture Notes in Mathe-
matics, Springer, 1982.

[358] G. Szekeres, Asymptotic distribution of the number and size of parts in unequal parti-
tions, Bull. Australian Math. Soc. 36 (1987), 89“97.

[359] G. Szekeres, Asymptotic distribution of partitions by number and size of parts, pp. 527“
538 in Number Theory, vol. I, K. Gy¨ry and G. Hal´sz, eds., Colloq. Math. Soc. J. Bolyai,
o a
No. 51, North-Holland, 1990.

[360] W. Szpankowski, The evaluation of an alternative sum with applications to the analysis
of some data structures, Inform. Proc. Letters, 28 (1988), 13“19.

[361] L. Tak´cs, On the number of distinct forests, SIAM J. Discr. Math., 3 (1990), 574“581.
a

[362] L. Tak´cs, A Bernoulli excursion and its various applications, Adv. Appl. Prob., 23
a
(1991), 557“585.

[363] N. M. Temme, Asymptotic estimates of Stirling numbers, Studies Appl. Math. 89 (1993),
233“243.

[364] E. C. Titchmarsh, The Theory of Functions, 2nd ed., Oxford University Press, London,
1939.

[365] E. C. Titchmarsh, Fourier Integrals, 2nd ed., Oxford Univ. Press, 1948.

[366] W. J. Trjitzinsky, Analytic theory of linear q-di¬erence equations, Acta Math., 61 (1933),
1“38.

[367] W. J. Trjitzinsky, Analytic theory of linear di¬erential equations, Acta math., 62 (1933),
167“226.

[368] V. S. Varadarajan, Meromorphic di¬erential equations, Expositiones Math.. 9 (1991),
97“188.

[369] R. C. Vaughan, The Hardy-Littlewood Method, Cambridge Univ. Press, 1981.




186
[370] A. M. Vershik and C. V. Kerov, Asymptotics of the Plancherel measure of the symmetric
group and a limiting form for Young tableau, Dokl. Akad. Nauk USSR, 233 (1977), 1024“
1027. (In Russian.)

[371] J. Vitter and P. Flajolet, Analysis of algorithms and data structures, Handbook of The-
oretical Computer Science, Vol. A: Algorithms and Complexity, Ch. 9, pp. 432“524, J.
Van Leeuwen, ed., North Holland, 1990.

[372] W. Wasow, Asymptotic Expansions for Ordinary Di¬erential Equations, Wiley, 1965.

[373] W. D. Wei, Y. Z. Cai, C. L. Liu, and A. M. Odlyzko, Balloting labelling and personnel
assignment, SIAM J. Alg. Discr. Methods, 7 (1986), pp. 150“158

[374] E. A. Whitehead, Jr., Four-discordant permutations, J. Austral. Math. Soc. (Ser. A) 28
(1979), 369“377.

[375] E. T. Whittaker and G. N. Watson, A Course of Modern Analysis, 4th ed., Cambridge
University Press, Cambridge, 1927.

[376] H. S. Wilf, The asymptotics of e P (z) and the number of elements of each order in S n ,
Bull. Am. Math. Soc., 15 (1986), pp. 228“232.

[377] H. S. Wilf, Generatingfunctionology, Academic Press, 1990.

[378] H. S. Wilf, The asymptotic behavior of the Stirling numbers of the ¬rst kind, J. Comb.
Theory Ser. A, to appear.

[379] H. S. Wilf and D. Zeilberger, Rational functions certify combinatorial identities, J. Amer.
Math. Soc., 3 (1990), pp. 147“158.

[380] H. S. Wilf and D. Zeilberger, An algorithmic proof theory for hypergeometric (ordinary
and “q”) multisum/integral identities, Inventiones math., 108 (1992), 575“633.

[381] R. Wilson, The coe¬cient theory of integral functions with dominant exponential parts,
Quart. J. Math. Oxford, ser. 2, 4 (1953), 142“149.

[382] J. Wimp, Computation with Recurrence Relations, Pitman, Boston, 1984.

[383] J. Wimp, Current trends in asymptotics: some problems and some solutions, J. Compu-
tational Appl. Math., 35 (1991), 53“79.

187
[384] J. Wimp and D. Zeilberger, Resurrecting the asymptotics of linear recurrences, J. Math.
Anal. Appl., 111 (1985), pp. 162“176.

[385] R. Wong, Asymptotic Approximations of Integrals, Academic Press, 1989.

[386] R. Wong and M. Wyman, The method of Darboux, J. Approx. Theory, 10 (1974),
pp. 159“171.

[387] E. M. Wright, Asymptotic partition formulae, I: Plane partitions, Quart. J. Math. Oxford
Ser., 2 (1931), pp. 177“189.

[388] E. M. Wright, The coe¬cients of a certain power series, J. London Math. Soc., 7 (1932),
pp. 256“262.

[389] E. M. Wright, On the coe¬cients of power series having exponential singularities, J.
London Math. Soc., 24 (1949), pp. 304“309.

[390] E. M. Wright, Partitions of large bipartities, Amer. J. Math., 80 (1958), 643“658.

[391] E. M. Wright, The asymptotic behavior of the generating functions of partitions of multi-
partities, Quart. J. Math. Oxford (2) 10 (1959), 60“69.

[392] E. M. Wright, Partitions into k parts, Math. Annalen, 142 (1961), pp. 311“316.

[393] E. M. Wright, A relationship between two sequences, Proc. London Math. Soc. 17 (1967),
296“304, 547“552.

[394] E. M. Wright, Asymptotic relations between enumerative functions in graph theory, Proc.
London Math. Soc. (3), 20 (1970) pp. 558“572.

[395] E. M. Wright, Graphs on unlabelled nodes with a given number of edges, Acta Math.,
126 (1971), pp. 1“9.

[396] E. M. Wright, The number of strong digraphs, Bull. London Math. Soc., 3 (1971), 348“
350.

[397] E. M. Wright, Graphs on unlabelled nodes with a large number of edges, Proc. London
Math. Soc. (3), 28 (1974), 577“594.

[398] E. M. Wright and B. G. Yates, The asymptotic expansion of a certain integral, Quarterly
J. Mathematics Oxford, 1 (1950) pp. 41“53.

188
[399] R. A. Wright, L. B. Richmond, A. M. Odlyzko, and B. D. McKay, Constant time gener-
ation of free trees, SIAM J. Comp., 15 (1986), pp. 540“548.

[400] M. Wyman, The asymptotic behavior of the Laurent coe¬cients, Canad. J. Math., 11
(1959), pp. 534“555.

[401] M. Wyman, The method of Laplace, Trans. Royal Soc. Canada, 2 (1964), pp. 227“256.

[402] D. Zeilberger, Solutions of exponential growth to systems of partial di¬erential equations,
J. Di¬erential Eq., 31 (1979), pp. 287“295.

[403] D. Zeilberger, The algebra of linear partial di¬erence operators and its applications,
SIAM J. Math. Analysis, 11 (1980), pp. 919“932.

[404] D. Zeilberger, Six etudes in generating functions, Intern. J. Computer Math., 29 (1989),
pp. 201“215.

[405] D. Zeilberger, A holonomic approach to special function identities, J. Comput. Appl.
Math., 32 (1990), 321“368.




189
Fig. 1. Domain ∆(r, φ, ·) of Section 11.1 and the integration contour “.




190
Contents

1 Introduction 1

2 Notation 8

3 Identities, inde¬nite summations, and related approaches 9

4 Basic estimates: factorials and binomial coe¬cients 12

5 Estimates of sums and other basic techniques 13
5.1 Sums of positive terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.2 Alternating sums and the principle of inclusion-exclusion . . . . . . . . . . . . . 23
5.3 Euler-Maclaurin and Poisson summation formulas ................ 27
5.4 Bootstrapping and other basic methods . . . . . . . . . . . . . . . . . . . . . . 29
5.5 Estimation of integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

6 Generating functions 32
6.1 A brief overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6.2 Composition and inversion of power series . . . . . . . . . . . . . . . . . . . . . 42
6.3 Di¬erentiably ¬nite power series .......................... 46
6.4 Unimodality and log-concavity . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.5 Moments and distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

7 Formal power series 51

8 Elementary estimates for convergent generating functions 55
8.1 Simple upper and lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
8.2 Tauberian theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

9 Recurrences 70
9.1 Linear recurrences with constant coe¬cients . . . . . . . . . . . . . . . . . . . . 70
9.2 Linear recurrences with varying coe¬cients . . . . . . . . . . . . . . . . . . . . 74
9.3 Linear recurrences in several variables . . . . . . . . . . . . . . . . . . . . . . . 78
9.4 Nonlinear recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
9.5 Quasi-linear recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
10 Analytic generating functions 87
10.1 Introduction and general estimates . . . . . . . . . . . . . . . . . . . . . . . . . 87
10.2 Subtraction of singularities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
10.3 The residue theorem and sums as integrals . . . . . . . . . . . . . . . . . . . . . 99
10.4 Location of singularities, Rouch´™s theorem, and unimodality . . . . . . . . . . 100
e
10.5 Implicit functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

11 Small singularities of analytic functions 106
11.1 Transfer theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
11.2 Darboux™s theorem and other methods . . . . . . . . . . . . . . . . . . . . . . . 112

12 Large singularities of analytic functions 114
12.1 The saddle point method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
12.2 Admissible functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
12.3 Other saddle point applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
12.4 The circle method and other techniques . . . . . . . . . . . . . . . . . . . . . . 128

13 Multivariate generating functions 130

14 Mellin and other integral transforms 135

15 Functional equations, recurrences, and combinations of methods 139
15.1 Implicit functions, graphical enumeration, and related topics . . . . . . . . . . 139
15.2 Nonlinear iteration and tree parameters . . . . . . . . . . . . . . . . . . . . . . 143
15.3 Di¬erential and integral equations . . . . . . . . . . . . . . . . . . . . . . . . . 150
15.4 Functional equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

16 Other methods 154
16.1 Permanents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
16.2 Probability theory and branching process methods . . . . . . . . . . . . . . . . 155
16.3 Statistical physics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
16.4 Classical applied mathematics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

17 Algorithmic and automated asymptotics 156

18 Guide to the literature 158

<< . .

 24
( 24)



Copyright Design by: Sunlight webdesign