You are here

Introduction to Enumerative Combinatorics

Miklós Bóna
Publisher: 
McGraw-Hill
Publication Date: 
2007
Number of Pages: 
524
Format: 
Hardcover
Series: 
The Walter Rudin Student Series in Advanced Mathematics
Price: 
107.81
ISBN: 
0-07-312561-X
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee strongly recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Warren Johnson
, on
05/28/2006
]

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 an = pan–1 + qan–2 (where p and q are constants) have the form an = Arn + Bsn for some constants A and B, where r and s are the roots of x2 = 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 an's is a linear function of x divided by 1 – px – qx2, and 1 – px – qx2 = (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 ij–1< /SUP> is correct, but the previous line would have implied i< SUP> j+1< /SUP> .

The author discusses the general solution of an = pan–1 + qan–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 rn a solution but one can check that nrn 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)rn falls right out of the generating function approach, because now one has a linear function divided by (1 – rx)2, 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 nkxn 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.


 

 

Foreword

Preface

Acknowledgments

I How: Methods

1 Basic Methods

1.1 When We Add and When We Subtract

1.1.1 When We Add
1.1.2 When We Subtract

1.2 When We Multiply

1.2.1 The Product Principle
1.2.2 Using Several Counting Principles
1.2.3 When Repetitions Are Not Allowed

1.3 When We Divide

1.3.1 The Division Principle
1.3.2 Subsets

1.4 Applications of Basic Counting Principles

1.4.1 Bijective Proofs
1.4.2 Properties of Binomial Coefficients
1.4.3 Permutations With Repetition

1.5 The Pigeonhole Principle

1.6 Notes

1.7 Chapter Review

1.8 Exercises

1.9 Solutions to Exercises

1.10 Supplementary Exercises

2 Direct Applications of Basic Methods

2.1 Multisets and Compositions

2.1.1 Weak Compositions
2.1.2 Compositions

2.2 Set Partitions

2.2.1 Stirling Numbers of the Second Kind
2.2.2 Recurrence Relations for Stirling Numbers of the Second Kind
2.2.3 When the Number of Blocks Is Not Fixed

2.3 Partitions of Integers

2.3.1 Nonincreasing Finite Sequences of Integers
2.3.2 Ferrers Shapes and Their Applications
2.3.3 Excursion: Euler’s Pentagonal Number Theorem

2.4 The Inclusion-Exclusion Principle

2.4.1 Two Intersecting Sets
2.4.2 Three Intersecting Sets
2.4.3 Any Number of Intersecting Sets

2.5 The Twelvefold Way

2.6 Notes

2.7 Chapter Review

2.8 Exercises

2.9 Solutions to Exercises

2.10 Supplementary Exercises

3 Generating Functions

3.1 Power Series

3.1.1 Generalized Binomial Coefficients
3.1.2 Formal Power Series

3.2 Warming Up: Solving Recursions

3.2.1 Ordinary Generating Functions
3.2.2 Exponential Generating Functions

3.3 Products of Generating Functions

3.3.1 Ordinary Generating Functions
3.3.2 Exponential Generating Functions

3.4 Excursion: Composition of Two Generating Functions

3.4.1 Ordinary Generating Functions
3.4.2 Exponential Generating Functions

3.5 Excursion: A Different Type of Generating Function

3.6 Notes

3.7 Chapter Review

3.8 Exercises

3.9 Solutions to Exercises

3.10 Supplementary Exercises

II What: Topics

4 Counting Permutations

4.1 Eulerian Numbers

4.2 The Cycle Structure of Permutations

4.2.1 Stirling Numbers of the First Kind
4.2.2 Permutations of a Given Type

4.3 Cycle Structure and Exponential Generating Functions

4.4 Inversions

4.4.1 Counting Permutations with Respect to Inversions

4.5 Notes

4.6 Chapter Review

4.7 Exercises

4.8 Solutions to Exercises

4.9 Supplementary Exercises

5 Counting Graphs

5.1 Counting Trees and Forests

5.1.1 Counting Trees

5.2 The Notion of Graph Isomorphisms

5.3 Counting Trees on Labeled Vertices

5.3.1 Counting Forests

5.4 Graphs and Functions

5.4.1 Acyclic Functions
5.4.2 Parking Functions

5.5 When the Vertices Are Not Freely Labeled

5.5.1 Rooted Plane Trees
5.5.2 Binary Plane Trees

5.6 Excursion: Graphs on Colored Vertices

5.6.1 Chromatic Polynomials
5.6.2 Counting k-colored Graphs

5.7 Graphs and Generating Functions

5.7.1 Generating Functions of Trees
5.7.2 Counting Connected Graphs
5.7.3 Counting Eulerian Graphs

5.8 Notes

5.9 Chapter Review

5.10 Exercises

5.11 Solutions to Exercises

5.12 Supplementary Exercises

6 Extremal Combinatorics

6.1 Extremal Graph Theory

6.1.1 Bipartite Graphs
6.1.2 Tur´an’s Theorem
6.1.3 Graphs Excluding Cycles
6.1.4 Graphs Excluding Complete Bipartite Graphs

6.2 Hypergraphs

6.2.1 Hypergraphs with Pairwise Intersecting Edges
6.2.2 Hypergraphs with Pairwise Incomparable Edges

6.3 Something Is More Than Nothing: Existence Proofs

6.3.1 Property B
6.3.2 Excluding Monochromatic Arithmetic Progressions
6.3.3 Codes Over Finite Alphabets

6.4 Notes

6.5 Chapter Review

6.6 Exercises

6.7 Solutions to Exercises

6.8 Supplementary Exercises

III What Else: Special Topics

7 Symmetric Structures

7.1 Hypergraphs with Symmetries

7.2 Finite Projective Planes

7.2.1 Excursion: Finite Projective Planes of Prime Power Order

7.3 Error-Correcting Codes

7.3.1 Words Far Apart
7.3.2 Codes from Hypergraphs
7.3.3 Perfect Codes

7.4 Counting Symmetric Structures

7.5 Notes

7.6 Chapter Review

7.7 Exercises

7.8 Solutions to Exercises

7.9 Supplementary Exercises

8 Sequences in Combinatorics

8.1 Unimodality

8.2 Log-Concavity

8.2.1 Log-Concavity Implies Unimodality
8.2.2 The Product Property
8.2.3 Injective Proofs

8.3 The Real Zeros Property

8.4 Notes

8.5 Chapter Review

8.6 Exercises

8.7 Solutions to Exercises

8.8 Supplementary Exercises

9 Counting Magic Squares and Magic Cubes

9.1 An Interesting Distribution Problem

9.2 Magic Squares of Fixed Size

9.2.1 The Case of n = 3
9.2.2 The Function Hn(r) for Fixed n

9.3 Magic Squares of Fixed Line Sum

9.4 Why Magic Cubes Are Different

9.5 Notes

9.6 Chapter Review

9.7 Exercises

9.8 Supplementary Exercises

A The Method of Mathematical Induction

A.1 Weak Induction

A.2 Strong Induction

Bibliography

Index

Frequently Used Notation

     
   

Dummy View - NOT TO BE DELETED