Analytic Combinatorics (book)

Analytic Combinatorics is a book on the mathematics of combinatorial enumeration, using generating functions and complex analysis to understand the growth rates of the numbers of combinatorial objects. It was written by Philippe Flajolet and Robert Sedgewick, and published by the Cambridge University Press in 2009. It won the Leroy P. Steele Prize in 2019.

The main part of the book is organized into three parts. The first part, covering three chapters and roughly the first quarter of the book, concerns the symbolic method in combinatorics, in which classes of combinatorial objects are associated with formulas that describe their structures, and then those formulas are reinterpreted to produce the generating functions or exponential generating functions of the classes,^[1][2] in some cases using tools such as the Lagrange inversion theorem as part of the reinterpretation process.^[2] The chapters in this part divide the material into the enumeration of unlabeled objects, the enumeration of labeled objects, and multivariate generating functions.^[2][3]

The five chapters of the second part of the book, roughly half of the text^[3] and "the heart of the book",^[1] concern the application of tools from complex analysis to the generating function, in order to understand the asymptotics of the numbers of objects in a combinatorial class.^[3] In particular, for sufficiently well-behaved generating functions, Cauchy's integral formula can be used to recover the power series coefficients (the real object of study) from the generating function, and knowledge of the singularities of the function can be used to derive accurate estimates of the resulting integrals.^[1] After an introductory chapter and a chapter giving examples of the possible behaviors of rational functions and meromorphic functions, the remaining chapters of this part discuss the way the singularities of a function can be used to analyze the asymptotic behavior of its power series, apply this method to a large number of combinatorial examples, and study the saddle-point method of contour integration for handling some trickier examples.^[1][3]

The final part investigates the behavior of random combinatorial structures, rather than the total number of structures, using the same toolbox. Beyond expected values for combinatorial quantities of interest, it also studies limit theorems and large deviations theory for these quantities. Three appendices provide background on combinatorics and asymptotics, in complex analysis, and in probability theory.^[3]

The combinatorial structures that are investigated throughout the book range widely over sequences, formal languages, integer partitions and compositions, permutations, graphs and paths in graphs, and lattice paths. With these topics, the analysis in the book connects to applications in other areas including abstract algebra, number theory, and the analysis of algorithms.^[2][4]

Analytic Combinatorics is not primarily a textbook; for instance, it has no exercises.^[4] Nevertheless, it can be used as the textbook for an upper-level undergraduate elective,^[5] graduate course,^[4] or seminar,^[3] although reviewer Miklós Bóna writes that some selection is needed, as it "has enough material for three or more semesters".^[2] It can also be a reference for researchers in this subject.^[3]

Reviewer Toufik Mansour calls it not only "a comprehensive theoretical treatment" but "an interesting read".^[3] Reviewer Christopher Hanusa writes that "the writing style is inviting, the subject material is contemporary and riveting", and he recommends the book to anyone "learning or working in combinatorics".^[4]

Analytic Combinatorics won the Leroy P. Steele Prize for Mathematical Exposition of the American Mathematical Society in 2019 (posthumously for Flajolet). The award citation called the book "an authoritative and highly accessible compendium of its subject, which demonstrates the deep interface between combinatorial mathematics and classical analysis".^[5] Although the application of analytic methods in combinatorics goes back at least to the work of G. H. Hardy and Srinivasa Ramanujan on the partition function,^[1] the citation also quoted a review by Robin Pemantle stating that "This is one of those books that marks the emergence of a subfield," the subfield of analytic combinatorics.^[1][5] Similarly, Bóna concludes, "Analytic Combinatorics is now defined. The authors wrote the book on it."^[2]

• Analytic Combinatorics author web site, including a full-text downloadable copy of the book