Analytic Combinatorics – Philippe Flajolet, Robert Sedgewick – 1st Edition

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

vi CONTENTS
C.4. Special distributions
C.5. Convergence in law

BIBLIOGRAPHY
INDEX 801