Analytic Combinatorics

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