*A Course in Enumeration*is a glorious survey of key topics in one of the most engaging areas of mathematics, enumerative combinatorics.

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 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