You are here

Analytic Combinatorics

Philippe Flajolet and Robert Sedgewick
Cambridge University Press
Publication Date: 
Number of Pages: 
[Reviewed by
Christopher Hanusa
, on

In Analytic Combinatorics, Flajolet and Sedgewick have written a reference that serves at the same time as a textbook for graduate students learning the subject and as a handbook for researchers. This 800-plus page book is full of fascinating combinatorics presented in a clear and direct manner.

The first part of the book, Chapters I, II, and III, develops techniques in enumerative combinatorics. The authors explain the mechanics of determining ordinary and exponential generating functions for different combinatorial constructions, using ideas from the theory of species, a powerful method that unifies apparently disparate combinatorial objects. By itself, this first part of the book is an very good introduction to enumerative combinatorics. The remaining chapters show what sorts of asymptotic information about the combinatorial objects we can pull from these generating functions and is the analytic of Analytic Combinatorics.

Chapter IV gently introduces the theory of singularities of generating functions by focusing on singularities that are poles, followed by an especially useful Chapter V where these methods are applied to sequences, regular languages, paths in graphs, and the transfer matrix method. Parallel to this, Chapters VI and VII focus on the theory and applications of more complicated singularity analysis. Chapter VIII rounds out the part of the book on complex asymptotics by discussing the saddle-point method. The book closes with a chapter on limit laws which focuses on determining the distributions of parameters of combinatorial structures.

Throughout the book, many areas of combinatorics are covered, including partitions, permutations, graphs, lattice paths, words, and many more. In addition to the wide variety of combinatorial examples, topics in diverse areas such as computer algorithms, algebra, and number theory appear throughout, showing the wide applicability of the methods. It is clear that the authors are working to impart the intuition one needs in the subject by explaining the types of expected results for certain combinatorial questions, and then proceeding to go through examples highlighting these ideas. The authors provide plenty of explanatory graphics to clarify the presented topics and to highlight the conclusions that should be drawn.

The reader is led carefully through the subject with plenty of introduction to each chapter. Throughout each chapter there are plenty of worked and unworked examples along the way with questions to make the reader think more deeply. While there is no explicit problem section at the end of each chapter, the interspersed examples and notes give plenty of opportunity to work closely with the topics at hand. At the end of each chapter is a section on "perspective", where the authors highlight the key messages to be taken away.

This book is not simply a textbook but truly a handbook. The introduction and the introductory sections at the beginning of each chapters explain where in the book to look for a particular example of a situation of interest. In addition, the authors convey a multitude of information clearly and thoroughly and consistently refer to many important works that use the techniques, many of them very recent. For this reason, the book's extensive bibliography is an amazing resource, grouping together key supportive texts and applications of the subject matter. There are more than enough sources to satisfy those readers looking for current areas of study or for researchers looking for in-the-field examples.

While the book may appear imposing at first glance with so much information packed in, the writing style is inviting, the subject material is contemporary and riveting, and I enthusiastically recommend this book for those learning or working in combinatorics.

Christopher Hanusa is an assistant professor of mathematics at Queens College, a City University of New York.


Preface; An invitation to analytic combinatorics; Part A. Symbolic Methods: 1. Combinatorial structures and ordinary generating functions; 2. Labelled structures and exponential generating functions; 3. Combinatorial parameters and multivariate generating functions; Part B. Complex Asymptotics: 4. Complex analysis, rational and meromorphic asymptotics; 5. Applications of rational and meromorphic asymptotics; 6. Singularity analysis of generating functions; 7. Applications of singularity analysis; 8. Saddle-Point asymptotics; Part C. Random Structures: 9. Multivariate asymptotics and limit laws; Part D. Appendices: Appendix A. Auxiliary elementary notions; Appendix B. Basic complex analysis; Appendix C. Concepts of probability theory; Bibliography; Index.