You are here

How to Count: An Introduction to Combinatorics and Its Applications

Robert A. Beeler
Publication Date: 
Number of Pages: 
[Reviewed by
Mark Hunacek
, on

This new textbook offers a competent but fairly standard look at combinatorics at the junior/senior undergraduate level. The topics covered here are generally those that one would not be surprised to find in a book at this level (the addition and multiplication principles for counting, binomial coefficients, combinatorial proofs of certain identities, distribution problems, generating functions, recurrence relations, the principle of inclusion and exclusion, Pólya counting theory, block designs and projective planes, and a one-chapter introduction to graph theory) but there are also things discussed in this book that are not often found in other basic combinatorics books. There is a nice section, for example, that counts the number of possible tic-tac-toe games (actually, I don’t believe I’ve ever seen this in any other textbook); there is an entire chapter on discrete probability; and there are sections on cryptography (including the Enigma machine) and on the classical ménage problem and some of its variations.

At the same time, there are a couple of topics that are sometimes discussed in other books that are not mentioned here at all; Hall’s Marriage theorem, for example, is omitted here, as is the combinatorics of partially ordered sets.

Exponential generating functions are not discussed much. In fact, the author’s treatment of them is fairly curious: in the chapter on generating functions, there is a short chapter on the use of generating functions to solve problems involving ordered arrangements; this leads to exponential generating functions, which are mentioned but not identified as such. Then, later on in the text, in connection with determining a formula for the number of derangements of n objects, exponential generating functions appear again; this time, the term is used, along with the statement that they “are often studied in more advanced texts”, but without any reference to the fact that the reader has in fact already seen them twenty pages earlier.

Of course, difficult decisions always have to be made about what topics to include or exclude in any text, and there is plenty of room for disagreement among reasonable people, for example, as to whether Hall’s theorem and systems of distinct representatives are more likely to be discussed in a combinatorics class than are, say, the various discrete distributions of probability theory.

The author describes this text in the preface as a “problem based” approach to combinatorics. I was afraid, when I first read that, that this was going to be a “Moore method” text in which students were just given lots of problems without solutions, but that turned out not to be the case. (That’s a good thing, in my opinion; I’m not completely sold on the idea of a textbook that leaves it to the student to prove everything.) Presumably, by “problem based”, the author means that there are lots of worked out examples (which, indeed, there are), but, here again, that’s pretty standard fare for all combinatorics texts.

The book under review competes with a number of other textbooks, including one, by Allenby and Slomson, with pretty much the same title as this one. The competition also includes Brualdi’s Introductory Combinatorics, Tucker’s Applied Combinatorics, Mazur’s Combinatorics: A Guided Tour, deTemple and Webb’s Combinatorial Reasoning: An Introduction to the Art of Counting. (There are others, of course, but these are the ones that spring immediately to mind. I could have added Combinatorics and Graph Theory by Harris, Hirst and Mossinghoff to the list, but that text has always struck me as being out of the mainstream for basic undergraduate texts on combinatorics, what with the fact that it covers such topics as axiomatic set theory and Godel’s Incompleteness theorems.)

The remaining books are, I think, for the most part all fairly comparable to the one under review in terms of content and readability, although of course there are some individual differences. In terms of content, for example, Brualdi and Tucker do quite a lot with graph theory, while deTemple/Webb do very little with it; Mazur’s coverage lies between these and is somewhat comparable to Beeler’s. Likewise, Brualdi, Allenby/Slomson and Tucker cover the Marriage theorem; the others do not. All of the books above cover exponential generating functions in somewhat greater detail than does Beeler.

In terms of overall readability, I would probably rank Brualdi at the top of the heap, but all of the books by Allenby/Slomson, Mazur, Tucker and deTemple/Webb are quite clear and readable, as is, also, the book under review.

Beeler’s text, and the five others just mentioned, all contain a good assortment of exercises. Many of the exercises in Beeler tend to be computational, but there are some more theoretical ones as well, including some that might be fairly challenging to undergraduates; in one, for example, Beeler asks the reader to prove (as a consequence of the pigeonhole principle) that any sequence of n2 + 1 distinct integers (actually, real numbers work just as well) contains a monotonic subsequence of length n + 1. This is the famous Erdős-Szekeres theorem (although that name is not given), and is proved in many texts; its proof is easy once you see it, but seeing the trick is not a trivial undertaking. Unlike a number of the books mentioned above, there are no solutions provided in the book, and thankfully the publisher has not, to my knowledge, succumbed to the temptation of selling a separate solutions manual, as is the case with the deTemple/Webb book.

To summarize and conclude: this is certainly a very viable option for a text in undergraduate combinatorics, but does not seem, at least to me, to be dramatically different than some of the other candidates that are available. What differences exist lie primarily in the inclusion or exclusion of a few topics. If, for example, you strongly feel that an introductory course in combinatorics should go fairly deeply into discrete probability, then you might find this book more satisfactory than any of the others mentioned previously; on the other hand, if you want to talk about the marriage theorem or Dilworth’s theorem on partially ordered sets, you might prefer one of the others.

Mark Hunacek ( teaches mathematics at Iowa State University.