Notes in Counting: An Introduction to Enumerative Combinatorics

When I went to undergraduate school at UCLA way back in the 1970s, combinatorics was rather prominently represented among the mathematics faculty, something I was soon aware of given my focus on number theory. Many of the regular faculty teaching the undergraduate as well as graduate courses in elementary number theory, algebraic number theory, and modular forms, for example, were also very prominent in combinatorics, with Ramsey theory well represented. Certainly Bruce Rothschild comes to mind right away, of course, and also the late Basil Gordon and the late Ernst Straus. Moreover there was a very active seminar program in place, with a lot of visitors, and I recall that when I was a raw rookie in the first (three quarters long) introductory number theory sequence taught by Straus, we were treated to a lecture by Paul Erdős, Straus’ very close friend, and so I was exposed to yet another master of The Art of Counting, arguably the most famous one of all.

That said I am afraid that despite my being aware of the magic that these mathematicians performed, and even with my having seen Straus in action along these lines any number of times in the aforementioned elementary course, I was drawn in another direction, specifically algebraic number theory, and then analytic methods in that area. So I really did not make use of the huge benefit afforded us in those days with Straus, Gordon, and Rothschild on the faculty: one of those “woulda, coulda, shoulda” things, I guess. It is nice, therefore, and a bit nostalgic, at least to get to write about the book under review, Notes on Counting: An Introduction to Enumerative Combinatorics.

The book is not about graph theory (at least not per se — see below), or about Ramsey theory, these certainly being things that might come to mind most easily when thinking about combinatorics, even if one were, like me, only a tangential player of the game: after all, you really can’t do number theory at all without running into these things. The book is about enumerative combinatorics, which the author, Peter Cameron, describes as dealing with generating functions and recurrence relations, to be followed “[in] later chapters [by] more specialized topics, including permanents, SDRs, group actions and the Redfield-Pólya theory of cycle indices, Möbius inversion, the Tutte polynomial, and species.”

An SDR is a system of distinct representatives (cf. p. 107 of the book), and is defined thus: given an \(n\)-tuple of subsets of a set, pick exactly one element from each subset such that no two of these \(n\) chosen elements are the same. The context for this definition is Cameron’s discussion of the permanent (a sort of sibling to Laplace’s definition of the determinant: just strike out the signs of the permutations). The pièce de resistance already appears on p. 107 where we encounter (Philip, not Marshall) Hall’s Theorem that says that a family \(\{A_i\}_i\) of\(n\)subsets of a given set has an SDR iff, for all subsets \(I\) of the interval \(\{1,2,\dots,n\}\) of natural numbers, the relation \(|A(I)|\geq |I|\) holds, where \(A(I)\) is the union of the \(A_i\) for \(i\in I\) (and, of course, \(|A|\) is just the number of elements of \(A\)). Cameron’s proof (of sufficiency, necessity having been done already) is by induction on \(n\). Right after this material we get the van der Waerden conjecture (proven by Egorychev and Falikman in 1981: Cameron gives a reference), Latin squares, and Latin rectangles. The next chapter is about so called \(q\)-analogues of the foregoing (five chapters’ worth of material) with finite fields playing a big role in it all.

But this is only a small sample of the things in this book. As already indicated above, there’s a lot more, some of it evidently quite familiar across the subject’s borders, such as Möbius inversion, other material being more idiosyncratic, shall we say. What is a Tutte polynomial, for example? Well, it’s a generalization of the chromatic polynomial from (yes) graph theory. To wit, the chromatic polynomial, say \(P(q)\), attached to a given graph, measures the number of ways of coloring the vertices of the graph with \(q\) colors (and of course there are immediate shades of the Four-color Theorem to be discerned). Then “Tutte generalized the notion of the chromatic polynomial to a two-variable polynomial …” The idea is that if an \(n\)-vertex graph has \(E\) as its set of edges, and if \(F\) is any subset of \(E\), let the rank of \(F\) be the difference \(n- \neg c(F)\), where \(\neg c(F)\) is the number of connected components of the graph with \(F\) as its set of edges. Says Cameron, “[s]aid otherwise, [the rank] is the size of the largest subgraph … which is a forest (that is, contains no cycles).” The Tutte polynomial is the two-variable generating function of the number \(t_{ij}\) of “spanning trees of [the graph] whose internal activity is \(i\) and whose external activity is \(j\)” (from Wolfram Mathworld). And presently Cameron goes on to do very cool things with the group of automorphisms of the graph, the matrix-tree theorem.

The foregoing is intended to give a fair idea of the things Cameron is up to in this book. It’s indeed a very good introduction to enumerative combinatorics and has all the trappings of a pedagogically sound enterprise, in the old-fashioned sense: exercises, good explanations (not too terse, but certainly not too wordy), and mathematically serious (nothing namby-pamby here). It’s an excellent book.

Michael Berg is Professor of Mathematics at Loyola Marymount University in Los Angeles, CA.