You are here

Analytic Combinatorics in Several Variables

Robin Pemantle and Mark C. Wilson
Cambridge University Press
Publication Date: 
Number of Pages: 
Cambridge Studies in Advanced Mathematics
[Reviewed by
Miklós Bóna
, on

This is a high-level and well-timed book. It is well-timed because it comes just a few years after its natural prequel, Analytic Combinatorics by Flajolet and Sedgewick, a book in which most generating functions have only one variable. How and why it is high-level will be explained below.

The book has four parts. The first part is a quick overview of what the reader is expected to know about generating functions. Advanced graduate students from the field will be able to understand this part. The generating functions that are discussed here both from an algebraic and an analytic perspective are mostly, but not exclusively, one-variable functions.

After this relatively digestible first part, the second part is a list of the heavy artillery that will be needed later. This part, “Mathematical Background,” has little classic combinatorics, and a lot of analytical topological, geometric and algebraic tools. They will be necessary to understand the combinatorial results later, because the description of the singularities of a multivariate generating function is much more complicated than that of a univariate one. Similarly, just what we mean by asymptotics for the coefficients of such a generating function is a non-trivial question.

Part three, “Multivariate Enumeration,” is where the fruit of the hard work of the Part two is harvested. A separate chapter is devoted to each main kind of singularity. The results are not easy to understand, but fortunately, the last two chapters, “Worked Examples,” and “Extensions” (which contains, among other things, “Diagonals”), are helpful for the reader who wants to see applications of the covered general theorems.

Finally, Part Four is an appendix that contains more background information on subjects such as Morse Theory and Algebraic Topology.

Most of the book contains reserch-level material that was discovered in the last 15 years. Therefore, it is not surprising that the book does not contain too many exercises, maybe five per chapter. If you endeavor to teach a class from the book, make sure your students have a good knowledge of both the Flajolet-Sedgewick book mentioned above, and Stanley’s Enumerative Combinatorics. Also make sure that your students are really good. If you read the book yourself, you may read Part 1 first, then Chapters 12 and 13, and then slowly work your way back through Part 2 as you need more and more notions and theorems.

Miklós Bóna is Professor of Mathematics at the University of Florida.

Part I. Combinatorial Enumeration:
1. Introduction
2. Generating functions
3. Univariate asymptotics

Part II. Mathematical Background:
4. Saddle integrals in one variable
5. Saddle integrals in more than one variable
6. Techniques of symbolic computation via Grobner bases
7. Cones, Laurent series and amoebas

Part III. Multivariate Enumeration:
8. Overview of analytic methods for multivariate generating functions
9. Smooth point asymptotics
10. Multiple point asymptotics
11. Cone point asymptotics
12. Worked examples
13. Extensions

Part IV. Appendices:
Appendix A. Manifolds

Appendix B. Morse theory
Appendix C. Stratification and stratified Morse theory.