Introduction to Enumerative Combinatorics

I've done about a dozen of these reviews now, and I've liked most of the books at least a little, but this is the first one that made me say "I wish I was teaching from this book right now!" The preface begins "Students interested in Combinatorics in general, and in Enumerative Combinatorics in particular, already have a few choices as to which books to read. However, the overwhelming majority of these books are either on General Combinatorics on the undergraduate level, or on Enumerative Combinatorics on the graduate level. The present book strives to be of a third kind. It focuses on Enumerative Combinatorics, attempts to be reasonably comprehensive, and is meant to be read primarily by undergraduates." In my opinion, Bóna has succeeded admirably.

The book does not assume any previous knowledge of combinatorics. It is divided into three parts, each part comprising three chapters, and there is also a brief appendix on mathematical induction. Chapter 1 has the basics: the first subsection is entitled "When We Add" (counting disjoint sets) and the second "When We Subtract". Section 1.2 discusses multiplication and 1.3 division, leading to binomial coefficients and the binomial theorem. Section 1.4 has applications of the earlier concepts, including lattice paths and multinomial coefficients, and section 1.5 does the pigeonhole principle. As with subsequent chapters, the first concludes with some bibliographical notes, a brief chapter review, an extensive exercise set (34 in the first chapter), solutions to the exercises, and another extensive exercise set (42 in the first chapter) without solutions. One of the latter is the multinomial theorem.

Chapter 2 discusses compositions, set partitions (including Stirling numbers of the second kind and Bell numbers), integer partitions and inclusion-exclusion. The author not only gives a standard proof of the inclusion-exclusion principle via the binomial theorem, but also Doron Zeilberger's proof based on the Garsia-Milne involution principle. Much of the material of the first two chapters is nicely summarized in section 2.5, entitled "The Twelvefold Way". Bóna says this name is due to Gian-Carlo Rota, while Richard Stanley (in Enumerative Combinatorics, volume 1, page 41) says Rota lectured on this collection of problems but attributes the name to Joel Spencer. In any case, this is one of many places in the book where the influence of the MIT school of combinatorics is evident, and yes, that is supposed to be a compliment. In the notes for this chapter, it might have been mentioned that the proof of Euler's pentagonal number theorem in section 2.3 is essentially that of Fabian Franklin in 1881. This was one of the first significant mathematical achievements by an American. The author may be confusing Franklin with Norman Ferrers on page 72: although Sylvester used Ferrers diagrams in his lectures on partitions at Johns Hopkins, Ferrers was not one of his students there, but one of his British contemporaries, and his co-editor at the Quarterly Journal of Pure and Applied Mathematics .

Chapter 3 is on generating functions. In section 3.2 I think it would be better to show once and for all that the solutions of the recurrence relation a_n = pa_n–1 + qa_n–2 (where p and q are constants) have the form a_n = Arⁿ + Bsⁿ for some constants A and B, where r and s are the roots of x² = px + q (assumed to be distinct for now). This is not such a difficult calculation if you do it right: the recurrence implies that the (ordinary) generating function of the a_n's is a linear function of x divided by 1 – px – qx², and 1 – px – qx² = (1 – rx)(1 – sx) with the same r and s as above, so the form falls right out using geometric series and the simplest case of partial fractions. Knowing this would save a lot of trouble in an exercise like number 5 in this chapter. The solution of that exercise given in the middle of page 181 is not quite right either — the author has the reciprocals of his alpha and beta mixed up, and to compensate he should have a multiplicative constant of 1/2i instead of i/2. The mistake is fixed in the middle of the next display, where his i^{j–1< /SUP> is correct, but the previous line would have implied i< SUP> j+1< /SUP> .}

^{The author discusses the general solution of a_n = pa_n–1 + qa_n–2 in the next three exercises from a linear algebra point of view, but I think a generating function approach would be more in the spirit of the book and also more convincing, especially in the case of repeated roots. Here the author is reduced to saying (at the bottom of page 182) that if the associated quadratic has the double root r, then not only is r}n a solution but one can check that nrⁿ is too, and that one might guess this by analogy with the corresponding situation in differential equations. While the comparison to differential equations is undoubtedly worth making, the general solution (A + Bn)rⁿ falls right out of the generating function approach, because now one has a linear function divided by (1 – rx)², and one knows how to expand this, from the bottom of page 129 or from calculus.

There is a brief discussion of formal power series near the beginning of chapter 3 which could be skipped, although a few things later in the chapter are clearer if it is not skipped. Section 3.2 discusses both ordinary and exponential generating functions, section 3.3 treats products of generating functions, and section 3.4 deals with compositions of generating functions. Here the most familiar case is the exponential formula, which tells you what happens combinatorially when you exponentiate an exponential generating function; this is treated at greater length in chapter 3 of Herbert Wilf's outstanding book generatingfunctionology . But Bóna also discusses the combinatorics of the composition of any exponential generating function with any other one. I have not seen this before in a book pitched at undergraduates, and I was very happy to see it here.

This completes part I, whose title is "How: Methods". Part II is entitled "What: Topics", and Part III "What Else: Special Topics". Chapter 4 returns to permutations. Section 4.1, on Eulerian numbers, is nice, but the connection with the sum of n^kxⁿ from n=0 to infinity for positive integer k is missing; in particular, this would explain why Euler studied these numbers. (See for example chapter 7 of Euler's Institutiones Calculi Differentialis, which is volume 10 of his Opera Omnia< /EM> , 1st series; the coefficients of the polynomials in the numerators on page 373 are what we now call the Eulerian numbers. Incidentally, if anyone out there knows who first found the combinatorial interpretation of these numbers, please write to me and tell me.)

Much of chapter 4 is about the cycle structure of permutations. The Stirling numbers of the first kind come in here, and so do derangements (which actually appeared earlier, in exercise 32 of chapter 2; in the solution of that exercise on page 118, the upper limit n is missing on all the sums, and once the binomial coefficient has been broken up it needs to be there), but there are also newer concepts such as desarrangements. The chapter concludes with inversions and the major index, but only for permutations of sets. If we consider permutations of words in a 2 letter alphabet instead then we get q-binomial coefficients. These appear in this guise in exercises 29–31, but only with a combinatorial definition — an explicit formula is not worked out. If we consider permutations of multisets then we get q-multinomial coefficients, and this is worth doing because it shows that Theorem 4.54 and exercise 29 are hinting at a stronger theorem.

How much of the book can be covered in one semester is not clear to me. I would love to teach a course based on the first four chapters, perhaps supplementing chapter 4 in ways I alluded to above. For such a course, the author's earlier book Combinatorics of Permutations  would be an excellent source of additional material, if any were needed. But I would also love to find some time for chapter 5, which is on counting graphs, especially labeled trees. Also in this chapter is the first undergraduate level treatment of parking functions, a very appealing topic. I don't think one could reasonably expect to do more than the first five chapters in any depth, although some of us are quicker than others. There is certainly enough material here for two semesters, especially if one uses some of the exercises as text. Bóna suggests that if the students have already had a semester of combinatorics from some other book, then one could use the last six chapters of his book as a basis for a second course.

His last four chapters are, to me, less interesting than the first five, but I'm sure some other people will feel differently. Chapter 6 is an introduction to extremal combinatorics, including the Erdos-Ko-Rado theorem and Sperner's theorem. Chapter 7 is on symmetric structures, and includes finite projective planes, error-correcting codes and Burnside's Lemma. Chapter 8 is on combinatorics of sequences, in particular log-concavity and unimodality. Finally, chapter 9 is on magic squares and magic cubes. From looking at the bibliography, I have a hunch that these may be the author's first love in mathematics.

There are a few places where one can tell that English is not the author's first language, but his writing is on the whole quite engaging. Many of the problems of enumerative combinatorics can be formulated in attractive ways, and Bóna takes full advantage of this: his examples have people wearing hats (sometimes brown, sometimes red), falling out of canoes, answering phone calls, eating ice cream, carrying boxes, losing their breakfast to raccoons, painting light poles and entering writing competitions, and that's just in part I. The exercise sets are very good, as one would expect of a student of Richard Stanley.

In the acknowledgments Bóna praises the books of Kenneth Bogart and of Richard Wilson and Jacobus van Lint, and the books of Alan Tucker and Richard Brualdi are both good too. This series provides another attractive option for institutions that can offer a full year of combinatorics: one could use this book for one semester and Introduction to Graph Theory, by Gary Chartrand and Ping Zhang, for the other, perhaps coming back to Bóna at the end for counting trees and forests and for parking functions. I found Bóna's book helpful when I was teaching discrete mathematics this past semester, and I hope I will soon have a chance to teach from it more extensively. It has edged ahead of generatingfunctionology  to become my favorite undergraduate combinatorics book.

Warren Johnson (warren.johnson@conncoll.edu) is visiting assistant professor of mathematics at Connecticut College.