You are here

Handbook of Enumerative Combinatorics

Miklós Bóna
Chapman & Hall/CRC
Publication Date: 
Number of Pages: 
Discrete Mathematics and Its Applications
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Mark Hunacek
, on

CRC Press’s Discrete Mathematics and its Applications series now numbers well over 70 books, covering just about any area of mathematics that could reasonably be considered discrete mathematics, including combinatorics, graph theory, number theory, cryptography, linear algebra, applied abstract algebra and even mathematical logic. Among these titles are a handful of books denominated “Handbooks”, which include (just to mention the ones that I have some personal knowledge of) The Handbook of Linear Algebra, Second Edition (HLA), The Handbook of Discrete and Combinatorial Mathematics (HDCM), and The Handbook of Graph Theory, Second Edition (HGT). (Full disclosure: my wife Leslie Hogben is the editor of HLA, and I contributed a chapter to it.) And now we have the book under review (HEC), the newest Handbook in this series.

These Handbooks will surprise any reader who imagines a “handbook” to be a short, easily portable, volume, like an instruction manual. These books, by contrast, might reasonably be described as encyclopedias of their respective subjects, arranged to provide quick information in an easily accessible manner. They are all oversized books, the size of telephone books; HLA, for example, clocks in at almost 2000 pages; HEC, the book now under review, is shorter, only about 1050 pages long.

The three handbooks (HLA, HDCM, HGT) listed in the first paragraph above follow a fairly formal structure: the book is divided into chapters, written by different authors; each chapter is subdivided into sections, each of which consists of Definitions, Examples and Facts, labeled as such and separately grouped. The “facts” are theorems and are given without proof, but with references to where proofs may be found. The “examples” sometimes contain some degree of justification, but do not always do so.

HEC doesn’t quite follow this rigid format; it does, however, follow one that is similar to it in that statements of theorems, definitions and examples are emphasized. There are fewer (in this case, 15) chapters, but they are much longer.

Instead of listing “definitions”, “facts” and “examples” in separate categories, the text has a more narrative, textbook, feel to it, with theorems labeled as such and, in another departure from the formal Handbook format, occasionally proved. There were even a few times when exercises appeared, though not in any kind of formal way.

A link above this review gives the table of contents of this book, so it seems unnecessary to specify here the topics that are covered. Suffice it to say that a great many topics in enumerative combinatorics are discussed, by authors who are recognized authorities in their respective areas. I am not, by any stretch of the imagination, an expert in combinatorics, but I did study it at the graduate level and teach it at the undergraduate, and at least on the basis of that limited experience, I cannot think of any topic that I would like to have seen presented here that the book omits. The chapters discuss not only methods (algebraic, geometric and analytic) in the study of enumerative combinatorics, but also objects that lend themselves to study along these lines. Some of these objects (e.g., trees, planar maps) are fairly well-known to a general audience, but as the book progresses, more specialized objects (e.g., parking functions, Young tableaux) are discussed.

The first chapter is quite long, about 175 pages (essentially the size of a slim book by itself), and surveys algebraic and geometric methods in enumerative combinatorics: generating functions, linear algebra (especially determinants), partially ordered sets, hyperplanes, matroids. The remaining chapters are shorter, ranging generally from 50 to 70 pages each.

The book is written so as to be accessible to a wide audience: each chapter eventually ventures into fairly specialized results, but starts at a point where non-specialists should be able to understand the various ideas. (The first chapter, for example, even includes, in passing, a definition of the binomial coefficients.) Other topics that one might encounter in an introductory course in combinatorics — Stirling numbers, for example — are also defined here, so a prior course in combinatorics is not necessary for understanding a reasonable amount of material here. However, because combinatorics intersects a number of other areas of mathematics (examples: abstract algebra, linear algebra and knot theory are mentioned in chapter 1; complex analysis in chapter 2; representation theory in chapter 14; commutative algebra in chapter 15), it would be advisable for a reader to have a reasonably broad understanding of mathematics, say at the level of early graduate work.

Needless to say, this is not a book that will likely be read cover-to-cover by most people; it is intended as a resource for people needing quick facts about a subject. In this regard, it succeeds admirably; this will clearly be a book that anybody with a serious interest in combinatorics will want to have on his or her bookshelf, and of course it belongs in any self-respecting university library. Having seen firsthand what it takes to edit a Handbook like this, I know that Miklós Bóna must have invested a great deal of time and effort in the creation of this volume, as did the authors of the individual chapters. Their efforts have not been in vain; this is a valuable book.

Mark Hunacek ( teaches mathematics at Iowa State University.


Algebraic and Geometric Methods in Enumerative Combinatorics
What is a Good Answer?
Generating Functions
Linear Algebra Methods
Hyperplane Arrangements

Analytic Methods; Helmut Prodinger
Combinatorial Constructions and Associated Ordinary Generating Functions
Combinatorial Constructions and Associated Exponential Generating Functions
Partitions and Q-Series
Some Applications of the Adding a Slice Technique
Lagrange Inversion Formula
Lattice Path Enumeration: The Continued Fraction Theorem
Lattice Path Enumeration: The Kernel Method
Gamma and Zeta Function
Harmonic Numbers and Their Generating Functions
Approximation of Binomial Coefficients
Mellin Transform and Asymptotics of Harmonic Sums
The Mellin-Perron Formula
Mellin-Perron Formula: Divide-and-Conquer Recursions
Rice’s Method
Approximate Counting
Singularity Analysis of Generating Functions
Longest Runs in Words
Inversions in Permutations and Pumping Moments
Tree Function
The Saddle Point Method
Hwang’s Quasi-Power Theorem


Asymptotic Normality in Enumeration; E. Rodney Canfield
The Normal Distribution
Method 1: Direct Approach
Method 2: Negative Roots
Method 3: Moments
Method 4: Singularity Analysis
Local Limit Theorems
Multivariate Asymptotic Normality
Normality in Service to Approximate Enumeration

Trees; Michael Drmota
Basic Notions
Generating Functions
Unlabeled Trees
Labeled Trees
Selected Topics on Trees

Planar maps; Gilles Schaeffer
What is a Map?
Counting Tree-Rooted Maps
Counting Planar Maps
Beyond Planar Maps, an Even Shorter Account

Graph Enumeration; Marc Noy
Graph Decompositions
Connected Graphs with Given Excess
Regular Graphs
Monotone and Hereditary Classes
Planar Graphs
Graphs on Surfaces and Graph Minors
Unlabelled Graphs

Unimodality, Log-Concavity, Real–Rootedness and Beyond; Petter Brándén
Probabilistic Consequences of Real–Rootedness
Unimodality and G-Nonnegativity
Log–Concavity and Matroids
Infinite Log-Concavity
The Neggers–Stanley Conjecture
Preserving Real–Rootedness
Common Interleavers
Multivariate Techniques
Historical Notes

Words; Dominique Perrin and Antonio Restivo
Lyndon words
Eulerian Graphs and De Bruijn Cycles
Unavoidable Sets
The Burrows-Wheeler Transform
The Gessel-Reutenauer Bijection
Suffix Arrays

Tilings; James Propp
Introduction and Overview
The Transfer Matrix Method
Other Determinant Methods
Representation-Theoretic Methods
Other Combinatorial Methods
Related Topics, and an Attempt at History
Some Emergent Themes

Lattice Path Enumeration; Christian Krattenthaler
Lattice Paths Without Restrictions
Linear Boundaries of Slope 1
Simple Paths with Linear Boundaries of Rational Slope, I
Simple Paths with Linear Boundaries with Rational Slope, II
Simple Paths with a Piecewise Linear Boundary
Simple Paths with General Boundaries
Elementary Results on Motzkin and Schroder Paths
A continued Fraction for the Weighted Counting of Motzkin Paths
Lattice Paths and Orthogonal Polynomials
Motzkin Paths in a Strip
Further Results for Lattice Paths in the Plane
Non-Intersecting Lattice Paths
Lattice Paths and Their Turns
Multidimensional Lattice Paths
Multidimensional Lattice Paths Bounded by a Hyperplane
Multidimensional Paths With a General Boundary
The Reflection Principle in Full Generality
Q-Counting Of Lattice Paths and Rogers–Ramanujan Identities
Self-Avoiding Walks

Catalan Paths and q; t-enumeration; James Haglund
Introduction to q-Analogues and Catalan Numbers
The q; t-Catalan Numbers
Parking Functions and the Hilbert Series
The q; t-Schrӧder Polynomial
Rational Catalan Combinatorics

Permutation Classes; Vincent Vatter
Growth Rates of Principal Classes
Notions of Structure
The Set of All Growth Rates

Parking Functions; Catherine H. Yan
Parking Functions and Labeled Trees
Many Faces of Parking Functions
Generalized Parking Functions
Parking Functions Associated with Graphs
Final Remarks

Standard Young Tableaux; Ron Adin and Yuval Roichman
Formulas for Thin Shapes
Jeu de taquin and the RS Correspondence
Formulas for Classical Shapes
More Proofs of the Hook Length Formula
Formulas for Skew Strips
Truncated and Other Non-Classical Shapes
Rim Hook and Domino Tableaux
Counting Reduced Words
Appendix 1: Representation Theoretic Aspects
Appendix 2: Asymptotics and Probabilistic Aspects

Computer Algebra; Manuel Kauers
Computer Algebra Essentials
Counting Algorithms
Symbolic Summation
The Guess-and-Prove Paradigm