One of the appealing features of combinatorics is that many of its motivating problems are simply stated, and that is certainly the case here. To give just a few examples: chapter two ends with a look at the probability that a random walk on a d-dimensional integer lattice eventually returns to the origin; chapter six considers questions such as how many different necklaces can be created with n beads of r possible colours, and chapter ten begins by asking how many tilings of a chessboard with dominoes are possible. Some problems like this can be solved using only simple methods, though the solutions may be hard to find, but A Course in Enumeration develops tools that allow them to be solved systematically and generally.

Chapter one covers elementary counting principles, binomial coefficients, Stirling numbers, permutations, number partitions and lattice paths, with fundamental coefficients as a kind of unifying idea. Chapter two then covers formal series, infinite sums and matrices, and connections to probability generating functions and random walks.

Chapter three explores the use of generating functions, in solving recurrences and evaluating sums, in capturing connected "substructure" through composition, and in studying number partitions. Chapter four, on hypergeometric summation, feels like something of a digression and could easily be skipped. Chapter five covers sieve methods, looking at inclusion-exclusion, its generalisation to Möbius inversion on partially ordered sets, and the Lemma of Gessel-Viennot, connecting matrix determinants with lattice paths. And chapter six considers counting problems involving symmetries and group theory, centering on the theorem of Pólya-Redfield and generalisation of that.

Chapter seven looks at connections of the Catalan numbers to lattice paths, generating functions, binomial formulas, and chord diagrams. Chapter eight explores symmetric polynomials and functions, building up to the RSK algorithm, "a remarkable combinatorial correspondence between integer matrices and pairs of semistandard tableaux". Chapter nine (my personal favourite) looks at graphs: the Tutte polynomial of graphs, interlace polynomials and Eulerian cycles, plane and medial graphs and transition polynomials, and knot polynomials. And chapter ten looks at some topics inspired by statistical physics: the dimer problem, the Ising problem, "hard" models (particles on a lattice without adjacent sites occupied), "square ice" and, spectacularly, a derivation of the Rogers-Ramanujan identities from a "hard hexagon" model.

A Course in Enumeration doesn't assume much, only basic linear algebra, calculus, probability, group theory, and so forth. And though individual chapters do draw on earlier ones, that is usually only for core methods and a few results. Some of the proofs are quite involved, however, and Aigner presents his material concisely, typically with just one or two illustrative examples of a concept or method, and assumes a general mathematical competence. Which is presumably why this is in Springer's "Graduate Texts" series, even if it makes no direct assumption of material that wouldn't be covered relatively early in a typical undergraduate degree.

I bought A Course in Enumeration because I loved Martin Aigner's Proofs from THE BOOK, a showcase of some of the most elegant and appealing proofs from across mathematics, and it has a similar feel to that. The presentations of ideas and proofs have the kind of clarity and luminousness which makes one feel, after reading them, that they are the natural if not the only ones. Each chapter also ends with a "highlight", tackling a famous and attractive problem using the tools developed.

There are almost seven hundred problems in A Course in Enumeration, with a set accompanying each section, divided into easier and harder; solutions, or at least sufficient hints, are given for around a quarter of them. Many of these problems are difficult to let go of, and I'm going back to have another go at some of them.

July 2018

External links:

- buy from Bookshop.org
- buy from Amazon.com or Amazon.co.uk
- share this review on Facebook or Twitter

Related reviews:

- Martin Aigner - Proofs from THE BOOK
- books about mathematics
- books published by Springer