You are here

A Course in Enumeration

Springer Verlag
Number of Pages: 

As most people who are beyond their teenage years know, it is a truism that the more you learn about a subject the more you realize how much you don't know about the subject in the first place. Take counting, for example.

We all learn how to count things in grade school, and for much of our elementary education we think that this is the end of the story. Then, as we get older, we start to see things such as Gauss' formula for the sum of the first n integers and techniques to count the number of poker hands and balls in urns and socks in drawers. We start to learn that there are often subtleties involved in counting. Students who go further and pick up books such as Proofs That Really Count, by Benjamin and Quinn, or A Path To Combinatorics for Undergraduates, by Andreescu and Feng, will see more of these issues and really start to understand the beauty as well as the difficulty that counting can sometimes pose. But even that is not the end of the story.

It would likely come as a huge surprise to those grade school students first "mastering" the art of counting to learn that there was a 550 page (and several pounds heavy) book for graduate students to learn about counting, but Martin Aigner's A Course in Enumeration is exactly such a book. The book is divided into three parts: the first part is about "Basics" and actually starts at a very elementary level, discussing the inclusion-exclusion principle and binomial coefficients. But the basics soon get much less basic as Aigner delves into Stirling numbers, lattice paths, generating functions, and infinite matrices.

The second part of the book is about "Methods" and goes into greater depth on generating functions, hypergeometric summations, and sieve methods. This part is a bit dry to read, but is important in order to move on to what comes next.

The third part of the book is entitled "Topics"; it applies the methods of the previous parts to investigate a series of results about other topics in enumerative combinatorics. The first chapter in this part of the book defines Catalan numbers (in six different ways!) and explores their connections to a variety of other parts of mathematics such as orthogonal polynomials and operator calculus. Another chapter defines symmetric functions and examines their relationship with homogeneous functions and standard tableaux. The final chapter looks at models which arise in statistical physics, such as the Dimer problem, which is a generalization of the famous question asking how many ways one can cover a chessboard with dominoes. This chapter is not as self-contained as most of the book, requiring a little more sophistication and background in graph theory than many readers might have.

One nice feature of the book is that each chapter concludes with a (mostly self-contained) "Highlight" which looks at one example in depth. One of these investigates how the Catalan number Cn counts the number of ways that 2n points on a circle can be connected into n chords none of which intersect with each other. Another looks in depth at the Aztec Diamonds developed by Elkies, Kupperberg, Larsen, and Propp, which have a very nice way of counting tilings and a surprising connection to the alternating matrix theorem. Yet another looks at some of Ramanujan's number theoretic identities in terms of counting partitions of various types.

As mentioned above, the topics in this book get complicated in a hurry, and Aigner's style of writing doesn't include as many details as one might like (although I hesitate to ask how heavy the book would have been if it did!) Furthermore, there are quite a few typos in the book, and some of these held up my reading quite a bit. On the flip side, the structure and topics of this book are well-designed, and there are nearly 700 exercises sprinkled throughout — many with hints and solutions in the back — which make the book far more appealing. I think it would be a good, if not a great, textbook for any graduate student wishing to learn about enumerative combinatorics. However, if you are just looking for a casual book to learn a new area, there are better choices on the market.

Darren Glass is an assistant professor of mathematics at Gettysburg College. His main mathematical interests include number theory, algebraic geometry, and cryptography.

Date Received: 
Monday, August 27, 2007
Include In BLL Rating: 
Martin Aigner
Graduate Texts in Mathematics 238
Publication Date: 
Darren Glass
BLL Rating: 
Publish Book: 
Modify Date: 
Monday, January 17, 2011