This book is an encyclopedic treatment of the mathematics known as analytic combinatorics. Analytic combinatorics is a combination of enumerative combinatorics and the art and science of approximation. The goal of enumerative combinatorics is, for the most part, the extraction of a generating function coefficient. In many cases, there is a closed form expression for the coefficient. In other cases, the combinatorialist hopes to find an asymptotic solution. The book explores techniques for both.
The first part of the book is a survey of problems, issues, techniques, and theorems in enumerative combinatorics, including generating functions of many flavors. The second part delves into analysis, focusing on complex asymptotics. Whereas the first part treats generating functions as formal power series, the second part contains results that involve assigning values to the generating function variables. The third part concerns random structures and explores results for multivariate generating functions.
Chapter 1 proceeds through classical enumeration problems, introducing ordinary generating functions, integer compositions and partitions, words (or strings), trees, and the Lagrange inversion theorem. Chapter 2 discusses labeled objects and explores exponential generating functions, permutations, set partitions, and labeled trees. Chapter 3 moves on to multivariate generating functions, considering the fundamental question of what a random object of large size looks like and deriving the moments of combinatorial parameters. Chapter 3 concludes the first part of the book.
The ground covered in the first part is similar to the ground covered by Comtet [1], Goulden and Jackson [2], Wilf [3], and Stanley [4]. It is valuable to retread this section, however, as it provides the foundation for Parts 2 and 3.
Part 2 moves on to complex analysis, exploring generating functions as analytic objects that take complex values. From this perspective, the generating function may be made to surrender all sorts of useful information, but this approach is particularly useful when the generating function coefficients do not have a simple closed form expression. Instead, the analytic approach yields nice asymptotic estimates of the coefficients.
Chapter 4 introduces two principles of coefficient asymptotics and surveys a number of fundamental results, such as Cauchy’s coefficient formula that expresses the generating function coefficient as an integral of the generating function, considered as a complex function. From there, it details more complex analysis theory and considers application to combinatorial objects such as denumerants, derangements, and several variations on patterns in words.
Chapter 5 uses the machinery developed in chapter 4 to solve problems involving supercritical sequences, regular specification and languages, lattice paths and continued fractions, paths in graphs and automata, and transfer matrices.
Chapter 6 looks at singularity analysis of generating functions, focusing on the fundamental relationship “between the asymptotic expansion of a function near its dominant singularities and the asymptotic expansion of the function’s coefficients.” This relationship is exploited to produce coefficients. Various tree problems and combinatorial sums are considered. Chapter 7 continues the applications of singularity analysis with a tour through yet more tree problems, noncrossing configurations, random walks, maps, and urn models.
Chapter 8, on saddle point asymptotics, applies the saddle point method to estimate the contour integral that, as is known from Cauchy’s coefficient formula, provides the generating function coefficient. Most of the chapter is dedicated to the theory’s development; applications appear in the form of problems that involve, for example, integer partitions, increasing subsequences in permutations, and random forests.
Chapter 9 marks the transition to Part 3. This part is characterized by an investigation of combinatorial parameters and, necessarily, multivariate generating functions (since the parameters are marked by additional variables). Then, the multivariate object is regarded as a deformation of the univariate one, which leads to perturbation of the univariate singularity analysis. This chapter develops the theory required, including probabilistic methods and limit laws. It revisits a number of combinatorial objects, such as cycles in permutations, initial runs in random walks, and tilings, but from a multivariate perspective.
The structure of each chapter is particularly nice. The authors introduce a topic and then discuss how they will treat it. At the end of each, they put the chapter in perspective and point out the highlights.
The book has very much the same flavor as Goulden and Jackson’s classic text [2]; the authors themselves acknowledge the similarity in style. One key difference is that Flajolet and Sedgewick lead more by example, or rather by exercise, as the exercises are integrated into the text. The book is complementary to many of the other classic texts in enumerative combinatorics. While the familiar topics are included in this book, they are set in a different, complex analysis context.
The book is suitable for a graduate course in enumeration and as a reference book for combinatorialists and computer scientists. Even though the area is important and useful to computer science, it is underrepresented. My only criticism is that the solutions to the exercises aren’t given; on the other hand, since the book is already over 800 pages long, the decision to omit the solutions was undoubtedly the right one. Overall, this is a valuable, comprehensive treatment.
