Flajolet P., Sedgewick R. Analytic Combinatorics

Cambridge University Press, 2009. - 824 p.
ISBN10: 0521898064 ISBN13: 978-0521898065.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.An invitation to Analytic Combinatorics.
A. Symbolic methods.
Combinatorial Structures and Ordinary Generating Functions.
Symbolic enumeration methods.
Admissible constructions and specifications.
Integer compositions and partitions.
Words and regular languages.
Tree structures.
Additional constructions.
Perspective.
Labelled Structures and Exponential Generating Functions.
Labelled classes.
Admissible labelled constructions.
Surjections, set partitions, and words.
Alignments, permutations, and related structures.
Labelled trees, mappings, and graphs.
Additional constructions.
Perspective.
Combinatorial Parameters and Multivariate Generating Functions.
An introduction to bivariate generating functions (Bgfs).
Bivariate generating functions and probability distributions.
Inherited parameters and ordinary Mgfs.
Inherited parameters and exponential Mgfs.
Recursive parameters.
Complete generating functions and discrete models.
Additional constructions.
Extremal parameters.
Perspective.
B. Complex asymptotics.
Complex Analysis, Rational and Meromorphic Asymptotics.
Generating functions as analytic objects.
Analytic functions and meromorphic functions.
Singularities and exponential growth of coefficients.
Closure properties and computable bounds.
Rational and meromorphic functions.
Localization of singularities.
Singularities and functional equations.
Perspective.
Applications of Rational and Meromorphic Asymptotics.
A roadmap to rational and meromorphic asymptotics.
Regular specification and languages.
Nested sequences, lattice paths, and continued fractions.
The supercritical sequence and its applications.
Paths in graphs and automata.
Transfer matrix models.
Perspective.
Singularity Analysis of Generating Functions.
A glimpse of basic singularity analysis theory.
Coefficient asymptotics for the basic scale.
Transfers.
The process of singularity analysis.
Multiple singularities.
Intermezzo: functions of singularity analysis class.
Inverse functions.
Polylogarithms.
Functional composition.
Closure properties.
Tauberian theory and Darboux's method.
Perspective.
Applications of Singularity Analysis.
A roadmap to singularity analysis asymptotics.
Sets and the exp-­log schema.
Simple varieties of trees and inverse functions.
Tree-like structures and implicit functions.
Nonplane unlabelled trees and Polya operators.
Irreducible context-free structures.
The general analysis of algebraic functions.
Combinatorial applications of algebraic functions.
Ordinary differential equations and systems.
Perspective.
Saddle Point Asymptotics.
Landscapes of analytic functions and saddle points.
Saddle point bounds.
Overview of the saddle point method.
Three combinatorial examples.
Admissibility.
Integer partitions.
Large powers.
Saddle points and probability distributions.
Multiple saddle points.
Perspective.
C. Random structures.
Multivariate Asymptotics and Limit Distributions.
Limit laws and combinatorial structures.
Discrete limit laws.
Combinatorial instances of discrete laws.
Continuous limit laws.
Quasi-powers and Gaussian limits.
Perturbation of meromorphic asymptotics.
Perturbation of singularity analysis asymptotics.
Perturbation of saddle point asymptotics.
Local limit laws.
Large deviations.
Non-Gaussian continuous limits.
Multivariate limit laws.D. Appendices.
Appendix A. Auxiliary Elementary Notions.
Appendix B. Basic Complex Analysis.
Appendix C. Complements of Probability Theory.