What do you think?
Rate this book
Analytic Combinatorics
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.
826 pages, Hardcover
First published December 31, 2008
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 1 of 1 review
February 15, 2026
Philippe Flajolet and Robert Sedgewick's Analytic Combinatorics is one of the major mathematical treatments of enumerative combinatorics to appear in the early twenty-first century. Published by Cambridge University Press in 2009, the 810-page volume presents a unified framework for obtaining precise quantitative information about large discrete structures. Its central idea is both simple and powerful: combinatorial objects can be translated into generating functions by systematic symbolic rules, and the asymptotic behaviour of those generating functions can then be analysed using complex analysis. The resulting synthesis provides a remarkably effective way of moving from the structural description of a discrete object to precise statements about its size, growth, distribution, and limiting behaviour. The book has subsequently acquired an unusually distinguished reputation. The American Mathematical Society awarded Flajolet and Sedgewick the 2019 Leroy P. Steele Prize for Mathematical Exposition, recognizing Analytic Combinatorics for combining combinatorial mathematics with classical analysis and for organizing the subject into a coherent and accessible body of theory. The award citation described the book as a work that helped establish analytic combinatorics as a thriving mathematical subdiscipline as well as an important component of the analysis of algorithms.
From combinatorial structure to quantitative prediction
The distinctive achievement of Analytic Combinatorics is the systematic nature of its methodology. Classical enumerative combinatorics often asks how many objects of a particular size exist. Analytic combinatorics goes further: it seeks to understand the asymptotic behaviour of those numbers and, where appropriate, the statistical properties of randomly selected objects as their size becomes large. The book's basic philosophy is expressed through a two-stage process. First comes symbolic enumeration. Combinatorial constructions are described formally, and these descriptions are translated into generating functions. Operations on combinatorial classes correspond to algebraic operations on generating functions. Thus, rather than deriving a separate generating function from scratch for every new problem, the reader learns a systematic dictionary connecting combinatorial constructions with their analytic counterparts. The first three chapters of the book develop this symbolic framework. Chapter I treats combinatorial structures and ordinary generating functions, including words, regular languages, integer compositions and partitions, and tree structures. Chapter II turns to labelled structures and exponential generating functions, treating subjects such as permutations, labelled trees, mappings, and graphs. Chapter III introduces combinatorial parameters and multivariate generating functions. This organization is pedagogically important. It teaches readers to regard generating functions not merely as clever algebraic devices but as a language for describing combinatorial structure. The second stage is complex asymptotic analysis. Once a generating function has been obtained, the central question becomes: what can its analytic behaviour tell us about its coefficients? Here the authors develop the machinery of singularity analysis, transfer theorems, and related methods. Singularities of generating functions frequently govern the asymptotic growth of their coefficients, allowing local information about a function near its dominant singularities to be converted into precise coefficient estimates. This is the point at which the book's two mathematical traditions—combinatorics and complex analysis—become genuinely inseparable. The combinatorial specification supplies the generating function; complex analysis extracts the large-scale quantitative information encoded within it.
Symbolic methods
Part A, “Symbolic Methods,” is the foundation of the entire work. Its treatment of ordinary and exponential generating functions provides the reader with a reusable vocabulary for constructing models. The discussion of ordinary generating functions encompasses such fundamental objects as sequences, words, trees, compositions, partitions, and regular languages. The labelled setting then introduces exponential generating functions and their applications to permutations, mappings, graphs, and other labelled structures. Multivariate generating functions subsequently allow individual combinatorial parameters to be tracked simultaneously. One of the strengths of this approach is that it makes apparently unrelated examples look structurally similar. Trees, for example, cease to be isolated objects requiring ad hoc enumeration techniques: their recursive descriptions can be translated into functional equations, which can subsequently be subjected to systematic analytic treatment. The method also provides a natural bridge to probability. Marking a parameter with an additional variable turns a generating function into a vehicle for studying distributions and moments. This becomes particularly important in Part C, where the authors investigate random combinatorial structures.
Complex asymptotics and singularity analysis
If the symbolic half of the book explains how to construct generating functions, Part B explains how to read them. The theory of asymptotics is developed in considerable depth, including rational and meromorphic asymptotics, singularity analysis, and the transfer principles that connect singular expansions with coefficient estimates. The book's contents include chapters devoted specifically to rational and meromorphic asymptotics and to singularity analysis of generating functions. Singularity analysis is arguably the conceptual centrepiece of the book. The basic principle is that the behaviour of a generating function near its dominant singularity often determines the asymptotic form of its coefficients. This turns complex-analytic information into combinatorial information. The importance of this principle is difficult to overstate. Instead of calculating an enormous sequence of exact coefficients and attempting to guess its behaviour, one can frequently study the analytic structure of the generating function and derive an asymptotic formula directly. In favourable circumstances, the method yields not merely the dominant exponential growth but also polynomial factors and lower-order corrections. This gives the subject a distinctive character: complex analysis is not being applied to combinatorics merely as an auxiliary technique. It becomes a systematic engine for extracting quantitative information from combinatorial models.
Random structures
Part C, “Random Structures,” extends the framework from enumeration to probability. Once combinatorial parameters are encoded by multivariate generating functions, one can investigate means, variances, higher moments, concentration phenomena, and limiting distributions. This is an important transition. Counting tells us how many objects exist; probabilistic analytic combinatorics asks what a typical large object looks like. The framework has applications to a remarkable variety of structures, including permutations, trees, strings, paths, graphs, and maps. The authors' official description emphasizes precisely this range, noting that the methods can be applied to fundamental structures across combinatorics as well as to problems arising in probability, statistical physics, computational biology, and information theory. The breadth of these applications demonstrates that the theory is not tied to a particular class of examples. What matters is whether a combinatorial model admits an appropriate symbolic specification and whether its generating functions have an analytically tractable structure.
A bridge to the analysis of algorithms
One of the book's most important connections is with computer science. The methods of analytic combinatorics have played a major role in the mathematical analysis of algorithms, particularly when algorithms operate on recursively generated or probabilistically distributed structures. This connection is partly historical. Flajolet's research at INRIA and Sedgewick's work in algorithms helped establish a close relationship between combinatorial mathematics and computer-science analysis. The mathematical framework developed in the book allows questions about algorithms to be reformulated as questions about generating functions and then treated with rigorous asymptotic techniques. The Princeton account of the 2019 Steele Prize notes that the authors' original motivation included applying classical mathematical analysis to the performance of computer programs, before the broader applicability of the methods became apparent. Consequently, the book occupies a productive position between mathematics and theoretical computer science. It is sufficiently mathematical to serve as a substantial reference in analysis and combinatorics, while many of its motivating problems arise naturally from algorithms and computation.
From combinatorial structure to quantitative prediction
The distinctive achievement of Analytic Combinatorics is the systematic nature of its methodology. Classical enumerative combinatorics often asks how many objects of a particular size exist. Analytic combinatorics goes further: it seeks to understand the asymptotic behaviour of those numbers and, where appropriate, the statistical properties of randomly selected objects as their size becomes large. The book's basic philosophy is expressed through a two-stage process. First comes symbolic enumeration. Combinatorial constructions are described formally, and these descriptions are translated into generating functions. Operations on combinatorial classes correspond to algebraic operations on generating functions. Thus, rather than deriving a separate generating function from scratch for every new problem, the reader learns a systematic dictionary connecting combinatorial constructions with their analytic counterparts. The first three chapters of the book develop this symbolic framework. Chapter I treats combinatorial structures and ordinary generating functions, including words, regular languages, integer compositions and partitions, and tree structures. Chapter II turns to labelled structures and exponential generating functions, treating subjects such as permutations, labelled trees, mappings, and graphs. Chapter III introduces combinatorial parameters and multivariate generating functions. This organization is pedagogically important. It teaches readers to regard generating functions not merely as clever algebraic devices but as a language for describing combinatorial structure. The second stage is complex asymptotic analysis. Once a generating function has been obtained, the central question becomes: what can its analytic behaviour tell us about its coefficients? Here the authors develop the machinery of singularity analysis, transfer theorems, and related methods. Singularities of generating functions frequently govern the asymptotic growth of their coefficients, allowing local information about a function near its dominant singularities to be converted into precise coefficient estimates. This is the point at which the book's two mathematical traditions—combinatorics and complex analysis—become genuinely inseparable. The combinatorial specification supplies the generating function; complex analysis extracts the large-scale quantitative information encoded within it.
Symbolic methods
Part A, “Symbolic Methods,” is the foundation of the entire work. Its treatment of ordinary and exponential generating functions provides the reader with a reusable vocabulary for constructing models. The discussion of ordinary generating functions encompasses such fundamental objects as sequences, words, trees, compositions, partitions, and regular languages. The labelled setting then introduces exponential generating functions and their applications to permutations, mappings, graphs, and other labelled structures. Multivariate generating functions subsequently allow individual combinatorial parameters to be tracked simultaneously. One of the strengths of this approach is that it makes apparently unrelated examples look structurally similar. Trees, for example, cease to be isolated objects requiring ad hoc enumeration techniques: their recursive descriptions can be translated into functional equations, which can subsequently be subjected to systematic analytic treatment. The method also provides a natural bridge to probability. Marking a parameter with an additional variable turns a generating function into a vehicle for studying distributions and moments. This becomes particularly important in Part C, where the authors investigate random combinatorial structures.
Complex asymptotics and singularity analysis
If the symbolic half of the book explains how to construct generating functions, Part B explains how to read them. The theory of asymptotics is developed in considerable depth, including rational and meromorphic asymptotics, singularity analysis, and the transfer principles that connect singular expansions with coefficient estimates. The book's contents include chapters devoted specifically to rational and meromorphic asymptotics and to singularity analysis of generating functions. Singularity analysis is arguably the conceptual centrepiece of the book. The basic principle is that the behaviour of a generating function near its dominant singularity often determines the asymptotic form of its coefficients. This turns complex-analytic information into combinatorial information. The importance of this principle is difficult to overstate. Instead of calculating an enormous sequence of exact coefficients and attempting to guess its behaviour, one can frequently study the analytic structure of the generating function and derive an asymptotic formula directly. In favourable circumstances, the method yields not merely the dominant exponential growth but also polynomial factors and lower-order corrections. This gives the subject a distinctive character: complex analysis is not being applied to combinatorics merely as an auxiliary technique. It becomes a systematic engine for extracting quantitative information from combinatorial models.
Random structures
Part C, “Random Structures,” extends the framework from enumeration to probability. Once combinatorial parameters are encoded by multivariate generating functions, one can investigate means, variances, higher moments, concentration phenomena, and limiting distributions. This is an important transition. Counting tells us how many objects exist; probabilistic analytic combinatorics asks what a typical large object looks like. The framework has applications to a remarkable variety of structures, including permutations, trees, strings, paths, graphs, and maps. The authors' official description emphasizes precisely this range, noting that the methods can be applied to fundamental structures across combinatorics as well as to problems arising in probability, statistical physics, computational biology, and information theory. The breadth of these applications demonstrates that the theory is not tied to a particular class of examples. What matters is whether a combinatorial model admits an appropriate symbolic specification and whether its generating functions have an analytically tractable structure.
A bridge to the analysis of algorithms
One of the book's most important connections is with computer science. The methods of analytic combinatorics have played a major role in the mathematical analysis of algorithms, particularly when algorithms operate on recursively generated or probabilistically distributed structures. This connection is partly historical. Flajolet's research at INRIA and Sedgewick's work in algorithms helped establish a close relationship between combinatorial mathematics and computer-science analysis. The mathematical framework developed in the book allows questions about algorithms to be reformulated as questions about generating functions and then treated with rigorous asymptotic techniques. The Princeton account of the 2019 Steele Prize notes that the authors' original motivation included applying classical mathematical analysis to the performance of computer programs, before the broader applicability of the methods became apparent. Consequently, the book occupies a productive position between mathematics and theoretical computer science. It is sufficiently mathematical to serve as a substantial reference in analysis and combinatorics, while many of its motivating problems arise naturally from algorithms and computation.
Displaying 1 - 1 of 1 review