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
Commentary: Final version with bookmarks added
Pages: 826
PREFACE
•AN INVITATION TO ANALYTIC COMBINATORICS
•Part A. SYMBOLIC METHODS
I. COMBINATORIAL STRUCTURES AND ORDINARY GENERATING FUNCTIONS
I.1. Symbolic enumeration methods I.2. Admissible constructions and specifications I.3. Integer compositions and partitions I.4. Words and regular languages I.5. Tree structures I.6. Additional constructions I.7. Perspective
II. LABELLED STRUCTURES AND EXPONENTIAL GENERATING FUNCTIONS
II.1. Labelled classes II.2. Admissible labelled constructions II.3. Surjections, set partitions, and words II.4. Alignments, permutations, and related structures II.5. Labelled trees, mappings, and graphs II.6. Additional constructions II.7. Perspective
III. COMBINATORIAL PARAMETERS AND MULTIVARIATE GENERATING FUNCTIONS
III.1. An introduction to bivariate generating functions (BGFs) III.2. Bivariate generating functions and probability distributions III.3. Inherited parameters and ordinary MGFs III.4. Inherited parameters and exponential MGFs III.5. Recursive parameters III.6. Complete generating functions and discrete models III.7. Additional constructions III.8. Extremal parameters III.9. Perspective
•Part B. COMPLEX ASYMPTOTICS
IV. COMPLEX ANALYSIS, RATIONAL AND MEROMORPHIC ASYMPTOTICS
IV.1. Generating functions as analytic objects IV.2. Analytic functions and meromorphic functions IV.3. Singularities and exponential growth of coefficients IV.4. Closure properties and computable bounds IV.5. Rational and meromorphic functions IV.6. Localization of singularities IV.7. Singularities and functional equations IV.8. Perspective
V. APPLICATIONS OF RATIONAL AND MEROMORPHIC ASYMPTOTICS
V.1. A roadmap to rational and meromorphic asymptotics V.2. The supercritical sequence schema V.3. Regular specifications and languages V.4. Nested sequences, lattice paths, and continued fractions V.5. Paths in graphs and automata V.6. Transfer matrix models V.7. Perspective
VI. SINGULARITY ANALYSIS OF GENERATING FUNCTIONS
VI.1. A glimpse of basic singularity analysis theory VI.2. Coefficient asymptotics for the standard scale VI.3. Transfers VI.4. The process of singularity analysis VI.5. Multiple singularities VI.6. Intermezzo: functions amenable to singularity analysis VI.7. Inverse functions VI.8. Polylogarithms VI.9. Functional composition VI.10. Closure properties VI.11. Tauberian theory and Darboux's method VI.12. Perspective
VII. APPLICATIONS OF SINGULARITY ANALYSIS
VII.1. A roadmap to singularity analysis asymptotics VII.2. Sets and the exp-log schema VII.3. Simple varieties of trees and inverse functions VII.4. Tree-like structures and implicit functions VII.5. Unlabelled non-plane trees and Polya operators VII.6. Irreducible context-free structures VII.7. The general analysis of algebraic functions VII.8. Combinatorial applications of algebraic functions VII.9. Ordinary differential equations and systems VII.10. Singularity analysis and probability distributions VII.11. Perspective
VIII. SADDLE-POINT ASYMPTOTICS
VIII.1. Landscapes of analytic functions and saddle-points VIII.2. Saddle-point bounds VIII.3. Overview of the saddle-point method VIII.4. Three combinatorial examples VIII.5. Admissibility VIII.6. Integer partitions VIII.7. Saddle-points and linear differential equations VIII.8. Large powers VIII.9. Saddle-points and probability distributions VIII.10. Multiple saddle-points VIII.11. Perspective
•Part C. RANDOM STRUCTURES
IX. MULTIVARIATE ASYMPTOTICS AND LIMIT LAWS
IX.1. Limit laws and combinatorial structures IX.2. Discrete limit laws IX.3. Combinatorial instances of discrete laws IX.4. Continuous limit laws IX.5. Quasi-powers and Gaussian limit laws IX.6. Perturbation of meromorphic asymptotics IX.7. Perturbation of singularity analysis asymptotics IX.8. Perturbation of saddle-point asymptotics IX.9. Local limit laws IX.10. Large deviations IX.11. Non-Gaussian continuous limits IX.12. Multivariate limit laws IX.13. Perspective
•Part D. APPENDICES
Appendix A. AUXILIARY ELEMENTARY NOTIONS
A.1. Arithmetical functions A.2. Asymptotic notations A.3. Combinatorial probability A.4. Cycle construction A.5. Formal power series A.6. Lagrange inversion A.7. Regular languages A.8. Stirling numbers A.9. Tree concepts
Appendix B. BASIC COMPLEX ANALYSIS
B.1. Algebraic elimination B.2. Equivalent definitions of analyticity B.3. Gamma function B.4. Holonomic functions B.5. Implicit Function Theorem B.6. Laplace's method B.7. Mellin transforms B.8. Several complex variables
Appendix C. CONCEPTS OF PROBABILITY THEORY
C.1. Probability spaces and measure C.2. Random variables C.3. Transforms of distributions C.4. Special distributions C.5. Convergence in law
•BIBLIOGRAPHY
•INDEX
