Combinatorics is an area of mathematics that I am unforgivably weak in, so I am happy to have an opportunity to review the present book. Indeed, I will make it part of my library so that, hopefully in this order of Providence, I might correct this shortcoming.
Indeed, Erickson’s Introduction to Combinatorics is appealing on precisely the count that it is very user-friendly. It’s filled with examples and exercises, and combinatorics is clearly more in need of these than, say, homological algebra — although some might disagree with this appraisal. But I think that my position is defensible on the count that the best (or at least the most canonical) book on homological algebra,the one by Cartan and Eilenberg, is relatively sparing on exercises (about a dozen per chapter, I’d say), and these are generally of the “prove this” variety, whereas it’s inconceivable that combinatorics can be learned without a plethora of problems of the “compute this” sort, with each type of computation repeated many times. After all, there’s a reason why combinatorics is often described, at least in large part, as the art of counting, and mastering such an art requires a huge number of exercises ranging from the elementary and routine to the fruity and sporty. So it is, for instance, that Erickson’s Sec.1.8, on linear recurrence, sports 83 – 69 +1 = 15 exercises, while Sec.1.9, on special recurrence relations, has 92 – 84 +1 = 9 problems, averaging (15 + 9)/2 = 8 problems per section. With Ch.1, Basic Counting Methods, coming in at 10 sections, we should expect 80 problems. Well, no: my sample is obviously too small, since the true count is 108 problems: Erickson is kind enough to number his problems partitioning the collection by chapter.
And the problems are a lot of fun. Here are three, from Sections 1.8, 1.9, and 1.10:
#1.80 — “Find a linear recurrence relation satisfied by all cubic polynomials,”
#1.90 — “Show that the linear recurrence relations for the Stirling numbers of the first and second kinds (allowing for negative values of the arguments) are equivalent,”
and (with Sec.1.10 titled “Counting and number theory”)
#1.100 — “For what n is n!+1 a perfect square?”
The lay-out of Introduction to Combinatorics is as follows: basic counting methods è generating functions è the pigeonhole principle è Ramsey theory è error-correcting codes è combinatorial designs. In the chapter on the pigeonhole principle we encounter graphs and colorings of the plane; in the context of Ramsey theory we meet the theorems of Schur and van der Waerden concerning monochromatic sets of integers. And the last thing in the book, in the chapter on combinatorial designs, is the Leech lattice, following discussions of Latin squares, Hadamard matrices, and sphere packings. This should give a pretty clear picture of what the book under review is all about, as well as its level. It is indeed an excellent introduction, it seems to me, taking the reader from an all but tabula rasa state to a very decent grasp of some serious combinatorial mathematics. It’s an excellent book.
I cannot pass up the chance to end this review with a recollection of two professors of mine, both deceased, God rest their souls, whom I idolized in my undergraduate years at UCLA, namely Ernst Straus and Basil Gordon. I had the great good fortune of learning “elementary” number theory (which is to say number theory sans complex analysis) from Straus and modular forms from Gordon. I was also part of their seminar on transcendental number theory: what a fond memory. Both Straus and Gordon were famous for their acumen in combinatorics, as well as being major players in a number of other areas. Additionally, they were very kind men, to whom I think back very fondly. The book under review reminds me of them.
Michael Berg is Professor of Mathematics at Loyola Marymount University in Los Angeles, CA.