Analytic Combinatorics aims to enable precise quantitative predictions of the properties of large combinatorial structures. The theory has emerged over recent decades as essential both for the analysis of algorithms and for the study of scientific models in many disciplines, including probability theory, statistical physics, computational biology, and information theory. With a careful combination of symbolic enumeration methods and complex analysis, drawing heavily on generating functions, results of sweeping generality emerge that can be applied in particular to fundamental structures such as permutations, sequences, strings, walks, paths, trees, graphs and maps. This account is the definitive treatment of the topic. The authors give full coverage of the underlying mathematics and a thorough treatment of both classical and modern applications of the theory. The text is complemented with exercises, examples, appendices and notes to aid understanding. The book can be used for an advanced undergraduate or a graduate course, or for self-study.

Part A. SYMBOLIC METHODS

I. COMBINATORIAL STRUCTURES AND ORDINARY GFS

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 GFS

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 GFS

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 specification 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 of singularity analysis class
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. Non-plane unlabelled trees and Pólya 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. Large powers
VIII.8. Saddle points and probability distributions
VIII.9. Multiple saddle points
VIII.10. 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

ANALYTIC COMBINATORICS aims at predicting precisely the properties of large structured combinatorial configurations, through an approach based extensively on analytic methods. Generating functions are the central objects of study of the theory.
     Analytic combinatorics starts from an exact enumerative description of combinatorial structures by means of generating functions: these make their first appearance as purely formal algebraic objects. Next, generating functions are interpreted as analytic objects, that is, as mappings of the complex plane into itself. Singularities determine a function’s coefficients in asymptotic form and lead to precise estimates for counting sequences. This chain of reasoning applies to a large number of problems of discrete mathematics relative to words, compositions, partitions, trees, permutations, graphs, mappings, planar configurations, and so on. A suitable adaptation of the methods also opens the way to the quantitative analysis of characteristic parameters of large random structures, via a perturbational approach.

THE APPROACH to quantitive problems of discrete mathematics provided by analytic combinatorics can be viewed as an operational calculus for combinatorics organized around three components:

Symbolic Methods develops systematic relations between some of the major constructions of discrete mathematics and operations on generating functions that exactly encode counting sequences.
Complex Asymptotics elaborates a collection of methods by which one can extract asymptotic counting information from generating functions, once these are viewed as analytic transformations of the complex domain. Singularities then appear to be a key determinant of asymptotic behaviour.
Random Structures concerns itself with probabilistic properties of large random structures. Which properties hold with high probability? Which laws govern randomness in large objects? In the context of analytic combinatorics, these questions are treated by a deformation (adding auxiliary variables) and a perturbation (examining the effect of small variations of such auxiliary variables) of the standard enumerative theory.

The present book expounds this view by means of a very large number of examples concerning classical objects of discrete mathematics and combinatorics. The eventual goal is an effective way of quantifying metric properties of large random structures.
     Given its capacity of quantifying properties of large discrete structures, Analytic Combinatorics is susceptible to many applications, not only within combinatorics itself, but, perhaps more importantly, within other areas of science where discrete probabilistic models recurrently surface, like statistical physics, computational biology, electrical engineering, and information theory. Last but not least, the analysis of algorithms and data structures in computer science has served and still serves as an important incentive for the development of the theory.

Part A: Symbolic Methods. This part specifically develops Symbolic Methods, which constitute a unified algebraic theory dedicated to setting up functional relations between counting generating functions. As it turns out, a collection of general (and simple) theorems provide a systematic translation mechanism between combinatorial constructions and operations on generating functions. This translation process is a purely formal one. In fact, with regard to basic counting, two parallel frameworks coexist—one for unlabelled structures and ordinary generating functions, the other for labelled structures and exponential generating functions. Furthermore, within the theory, parameters of combinatorial configurations can be easily taken into account by adding supplementary variables. Three chapters then form Part A—Chapter I deals with unlabelled objects; Chapter II develops in a parallel way labelled objects; Chapter III treats multivariate aspects of the theory suitable for the analysis of parameters of combinatorial structures.

Part B: Complex Asymptotics. This part specifically expounds Complex Asymptotics, which is a unified analytic theory dedicated to the process of extracting asymptotic information from counting generating functions. A collection of general (and simple) theorems now provide a systematic translation mechanism between generating functions and asymptotic forms of coefficients. Five chapters form this part. Chapter IV serves as an introduction to complex-analytic methods and proceeds with the treatment of meromorphic functions, that is, functions whose singularities are poles, rational functions being the simplest case. Chapter V develops applications of rational and meromorphic asymptotics of generating functions, with numerous applications related to words and languages, walks and graphs, as well as permutations. Chapter VI develops a general theory of singularity analysis that applies to a wide variety of singularity types, such as square-root or logarithmic, and has consequences regarding trees as well as other recursively-defined combinatorial classes. Chapter VII presents applications of singularity analysis to 2-regular graphs and polynomials, trees of various sorts, mappings, context-free languages, walks, and maps. It contains in particular a discussion of the analysis of coefficients of algebraic functions. Chapter VIII explores saddle-point methods, which are instrumental in analysing functions with violent growth at a singularity, as well as many functions with a singularity only at infinity (i.e., entire functions).

Part C: Random Structures. This part is comprised of Chapter IX, which is dedicated to the analysis of multivariate generating functions viewed as deformation and perturbation of simple (univariate) functions. Many known laws of probability theory, either discrete or continuous, from Poisson to Gaussian and stable distributions, are found to arise in combinatorics, by a process combining symbolic methods and complex asymptotics. As a consequence, many important characteristics of classical combinatorial structures can be precisely quantified in distribution.

Part D: Appendices. Appendix A summarizes some key elementary concepts of combinatorics and asymptotics, with entries relative to asymptotic expansions, languages, and trees, amongst others. Appendix B recapitulates the necessary background in complex analysis. It may be viewed as a self-contained mini-course on the subject, with entries relative to analytic functions, the Gamma function, the implicit function theorem, and Mellin transforms. Appendix C recalls some of the basic notions of probability theory that are useful in analytic combinatorics.

THIS BOOK is meant to be reader-friendly. Each major method is abundantly illustrated by means of concrete examples treated in detail—there are scores of them spanning from a fraction of a page to several pages—offering a complete treatment of a specific problem. These are borrowed not only from combinatorics itself but also from neighbouring areas of science. With a view to addressing not only mathematicians of varied profiles but also scientists of other disciplines, Analytic Combinatorics is self-contained, including ample appendices that recapitulate the necessary background in combinatorics and complex function theory. A rich set of short notes—there are more than 250 of them—are inserted in the text and can provide exercises meant for selfstudy or for student practice, as well as introductions to the vast body of literature that is available. We have also made every effort to focus on core ideas rather than technical details, supposing a certain amount of mathematical maturity but only basic prerequisites on the part of our gentle readers. The book is also meant to be strongly problem-oriented, and indeed it can be regarded as a manual, or even a huge algorithm, guiding the reader to the solution of a very large variety of problems regarding discrete mathematical models of varied origins. In this spirit, many of our developments connect nicely with computer algebra and symbolic manipulation systems.

COURSES can be (and indeed have been) based on the book in various ways. Chapters I-III on Symbolic Methods serve as a systematic yet accessible introduction to the formal side of combinatorial enumeration. As such it organizes transparently some of the rich material found in treatises like those of Bergeron-Labelle-Leroux, Comtet, Goulden-Jackson, and Stanley. Chapters IV-VIII relative to Complex Asymptotics provide a large set of concrete examples illustrating the power of classical complex analysis and of asymptotic analysis outside of their traditional range of applications. This material can thus be used in courses of either pure or applied mathematics, providing a wealth of non-classical examples. In addition, the quiet but ubiquitous presence of symbolic manipulation systems provides a number of illustrations of the power of these systems while making it possible to test and concretely experiment with a great many combinatorial models. Symbolic systems allow, for instance, for fast random generation, close examination of non-asymptotic regimes, efficient experimentation with analytic expansions and singularities, and so on.
     Our initial motivation when starting this project was to build a coherent set of methods useful in the analysis of algorithms, a domain of computer science now well developed and presented in books by Knuth, Hofri, Mahmoud, and Szpankowski, in the survey by Vitter-Flajolet, as well as in our earlier Introduction to the Analysis of Algorithms published in 1996. This book can then be used as a systematic presentation of methods that have proved immensely useful in this area; see in particular the Art of Computer Programming by Knuth for background. Studies in statistical physics (van Rensburg and others), statistics (e.g., David and Barton) and probability theory (e.g., Billingsley, Feller), mathematical logic (Burris’s book), analytic number theory (e.g., Tenenbaum), computational biology (Waterman’s textbook), as well as information theory (e.g., the books by Cover-Thomas, MacKay, and Szpankowski) point to many startling connections with yet other areas of science. The book may thus be useful as a supplementary reference on methods and applications in courses on statistics, probability theory, statistical physics, finite model theory, analytic number theory, information theory, computer algebra, complex analysis, or analysis of algorithms.

Acknowledgements. This book would be substantially different and much less informative without Neil Sloane’s Encyclopedia of Integer Sequences, Steve Finch’s Mathematical Constants, Eric Weisstein’s MathWorld, and the MacTutor History of Mathematics site hosted at St Andrews. All are (or at least have been at some stage) freely available on the Internet. Bruno Salvy and Paul Zimmermann have developed algorithms and libraries for combinatorial structures and generating functions that are based on the MAPLE system for symbolic computations and that have proven to be extremely useful. We are deeply grateful to the authors of the free software Unix, Linux, Emacs, X11, TEX and LATEX as well as to the designers of the symbolic manipulation system MAPLE for creating an environment that has proved invaluable to us. We also thank students in courses at Barcelona, Berkeley (MSRI), Bordeaux, Caen, Paris ( École Polytechnique, École Normale, University), Princeton, Santiago de Chile, Udine, and Vienna whose reactions have greatly helped us prepare a better book. Thanks finally to numerous colleagues for their contributions to this book project. In particular, we wish to acknowledge the support, help, and interaction provided at a high level by members of the Analysis of Algorithms (AofA) community, with a special mention for Nicolas Broutin, Michael Drmota, Éric Fusy, Hsien-Kuei Hwang, Svante Janson, Don Knuth, Guy Louchard, Andrew Odlyzko, Daniel Panario, Helmut Prodinger, Bruno Salvy, Michèle Soria, Wojtek Szpankowski, Brigitte Vallée, Mark Ward, and Mark Wilson. In addition, Stan Burris, Svante Janson, Philippe Robert, Loïc Turban, and Brigitte Vallée have provided insightful suggestions and generous feedback that have led us to revise the presentation of several sections of this book and correct many errors. We were also extremely lucky to work with David Tranah, the mathematics editor of Cambridge University Press, who has been an exceptionally supportive (and patient) companion of this book project, throughout all these years. Finally, support of our home institutions (INRIA and Princeton University) as well as various grants (French government, European Union, and NSF) have contributed to making our collaboration possible.

Philippe Flajolet, INRIA-Rocquencourt, France
Robert Sedgewick, Princeton University, USA

An extensive amount of content associated with this book is available online, most of it freely available. The introduction to the COURSES page and the essay on online learning on this website tell the full story of the types of content, relationships, and how it may best be used by students and teachers of all sorts. The COURSES page for this book gives specific details. Here are some brief descriptions and quick links to this material.

Booksite. Our Analytic Combinatorics website contains hundreds of files, fully coordinated with our textbook and also useful as a standalone resource. It consists of the following elements:

Excerpts. A condensed version of the text narrative, for reference while online.
Exercises. Selected exercises from the book and “web exercises” developed since its publication, along with solutions to selected exercises.
Assignments. Creative assignments that we have used at Princeton.

This is a living resource that is constantly being improved and updated.

Online lectures. A complete set of curated studio-produced lecture videos that can be used in conjunction with this text are available online via the cubits platform. This platform applies modern machine-learning models to build searchable transcripts, indexing, and other features that enhance the experience of learning from the videos.

Lecture slides. The lectures are based on hundreds of detailed, carefully prepared slides that are useful for reviewing the lecture content. These are available at the websites just listed, and on the COURSES page for this book, which provides a convenient interface for browsing through them.

MOOC. The Coursera course Analytic Combinatorics is a massive open online course based on the lecture videos that includes exercises, auto-assessed programming assignments, and other features encouraging coordinated study of the material in the book.

Princeton course. You can find details on how we conduct our course at Princeton on our course website. Our students watch lectures online and complete weekly programming assignments. We ensure loose synchronization via the booksite and regular e-mail for authoritative communication from faculty to students.