#### Analytic Combinatorics

by Robert Sedgewick and Philippe Flajolet

**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.

Excerpts from review by Robin Pemantle:

This is one of those books that marks the emergence of a subfield. The “Flajolet School” of combinatorics emerged in the 1980s and subsequent decades from a group of researchers at the Institut National de Recherche en Informatique et en Automatique (INRIA) in Rocquencourt, west of Paris. One of their principal aims was the mathematical analysis of algorithms. Most of these algorithms were already in use, sans rigorous analysis, by computer scientists. While the bulk of this group’s research is published in mathematics journals, it is the intimate connection with computer science that has given this research purpose and depth.

A review is supposed to be balanced, but, for the most part, I have nothing but praise for this book.

**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.