Analytic Combinatorics is a self-contained treatment of the mathematics underlying the analysis of discrete structures, which has emerged over the past several decades as an essential tool in the understanding of properties of computer programs and scientific models with applications in physics, biology and chemistry. Thorough treatment of a large number of classical applications is an essential aspect of the presentation. Written by the leaders in the field of analytic combinatorics, this text is certain to become the definitive reference on the topic. The text is complemented with exercises, examples, appendices and notes to aid understanding therefore, it can be used as the basis for an advanced undergraduate or a graduate course on the subject, or for self-study.
Author(s): Philippe Flajolet, Robert Sedgewick
Edition: 1
Publisher: Cambridge University Press
Year: 2009
Language: English
Pages: 828
Cover......Page 1
Title page......Page 5
Abstract......Page 7
Contents......Page 9
Preface......Page 13
An Invitation to Analytic Combinatorics......Page 19
Part A. Symbolic Methods......Page 31
I. Combinatorial Structures and Ordinary Generating Functions......Page 33
I.1. Symbolic enumeration methods......Page 34
I.2. Admissible constructions and specifications......Page 42
I.3. Integer compositions and partitions......Page 57
I.4. Words and regular languages......Page 67
I.5. Tree structures......Page 82
I.6. Additional constructions......Page 101
I.7. Perspective......Page 110
II. Labelled Structures and Exponential Generating Functions......Page 113
II.1. Labelled classes......Page 114
II.2. Admissible labelled constructions......Page 118
II.3. Surjections, set partitions, and words......Page 124
II.4. Alignments, permutations, and related structures......Page 137
II.5. Labelled trees, mappings, and graphs......Page 143
II.6. Additional constructions......Page 154
II.7. Perspective......Page 165
III. Combinatorial Parameters and Multivariate Generating Functions......Page 169
III.1. An introduction to bivariate generating functions (BGFs)......Page 170
III.2. Bivariate generating functions and probability distributions......Page 174
III.3. Inherited parameters and ordinary MGFs......Page 181
III.4. Inherited parameters and exponential MGFs......Page 192
III.5. Recursive parameters......Page 199
III.6. Complete generating functions and discrete models......Page 204
III.7. Additional constructions......Page 216
III.8. Extremal parameters......Page 232
III.9. Perspective......Page 236
Part B. Complex Asymptotics......Page 239
IV. Complex Analysis, Rational and Meromorphic Asymptotics......Page 241
IV.1. Generating functions as analytic objects......Page 243
IV.2. Analytic functions and meromorphic functions......Page 247
IV.3. Singularities and exponential growth of coefficients......Page 256
IV.4. Closure properties and computable bounds......Page 267
IV.5. Rational and meromorphic functions......Page 273
IV.6. Localization of singularities......Page 281
IV.7. Singularities and functional equations......Page 293
IV.8. Perspective......Page 304
V. Applications of Rational and Meromorphic Asymptotics......Page 307
V.1. A roadmap to rational and meromorphic asymptotics......Page 308
V.2. The supercritical sequence schema......Page 311
V.3. Regular specifications and languages......Page 318
V.4. Nested sequences, lattice paths, and continued fractions......Page 336
V.5. Paths in graphs and automata......Page 354
V.6. Transfer matrix models......Page 374
V.7. Perspective......Page 391
VI. Singularity Analysis of Generating Functions......Page 393
VI.1. A glimpse of basic singularity analysis theory......Page 394
VI.2. Coefficient asymptotics for the standard scale......Page 398
VI.3. Transfers......Page 407
VI.4. The process of singularity analysis......Page 410
VI.5. Multiple singularities......Page 416
VI.6. Intermezzo: functions amenable to singularity analysis......Page 419
VI.7. Inverse functions......Page 420
VI.8. Polylogarithms......Page 426
VI.9. Functional composition......Page 429
VI.10. Closure properties......Page 436
VI.11. Tauberian theory and Darboux’s method......Page 451
VI.12. Perspective......Page 455
VII. Applications of Singularity Analysis......Page 457
VII.1. A roadmap to singularity analysis asymptotics......Page 459
VII.2. Sets and the exp–log schema......Page 463
VII.3. Simple varieties of trees and inverse functions......Page 470
VII.4. Tree-like structures and implicit functions......Page 485
VII.5. Unlabelled non-plane trees and Pólya operators......Page 493
VII.6. Irreducible context-free structures......Page 500
VII.7. The general analysis of algebraic functions......Page 511
VII.8. Combinatorial applications of algebraic functions......Page 524
VII.9. Ordinary differential equations and systems......Page 536
VII.10. Singularity analysis and probability distributions......Page 550
VII.11. Perspective......Page 556
VIII. Saddle-point Asymptotics......Page 559
VIII.1. Landscapes of analytic functions and saddle-points......Page 561
VIII.2. Saddle-point bounds......Page 564
VIII.3. Overview of the saddle-point method......Page 569
VIII.4. Three combinatorial examples......Page 576
VIII.5. Admissibility......Page 582
VIII.6. Integer partitions......Page 592
VIII.7. Saddle-points and linear differential equations.......Page 599
VIII.8. Large powers......Page 603
VIII.9. Saddle-points and probability distributions......Page 612
VIII.10. Multiple saddle-points......Page 618
VIII.11. Perspective......Page 624
Part C. Random Structures......Page 627
IX. Multivariate Asymptotics and Limit Laws......Page 629
IX.1. Limit laws and combinatorial structures......Page 631
IX.2. Discrete limit laws......Page 638
IX.3. Combinatorial instances of discrete laws......Page 646
IX.4. Continuous limit laws......Page 656
IX.5. Quasi-powers and Gaussian limit laws......Page 662
IX.6. Perturbation of meromorphic asymptotics......Page 668
IX.7. Perturbation of singularity analysis asymptotics......Page 684
IX.8. Perturbation of saddle-point asymptotics......Page 708
IX.9. Local limit laws......Page 712
IX.10. Large deviations......Page 717
IX.11. Non-Gaussian continuous limits......Page 721
IX.12. Multivariate limit laws......Page 733
IX.13. Perspective......Page 734
Part D. Appendices......Page 737
A.1. Arithmetical functions......Page 739
A.2. Asymptotic notations......Page 740
A.3. Combinatorial probability......Page 745
A.4. Cycle construction......Page 747
A.5. Formal power series......Page 748
A.6. Lagrange inversion......Page 750
A.7. Regular languages......Page 751
A.8. Stirling numbers......Page 753
A.9. Tree concepts......Page 755
B.1. Algebraic elimination......Page 757
B.2. Equivalent definitions of analyticity......Page 759
B.3. Gamma function......Page 761
B.4. Holonomic functions......Page 766
B.5. Implicit Function Theorem......Page 771
B.6. Laplace’s method......Page 773
B.7. Mellin transforms......Page 780
B.8. Several complex variables......Page 785
C.1. Probability spaces and measure......Page 787
C.2. Random variables......Page 789
C.3. Transforms of distributions......Page 790
C.4. Special distributions......Page 792
C.5. Convergence in law......Page 794
Bibliography......Page 797
Index......Page 819
