You are here

Introduction to Combinatorics

Martin J. Erickson
Publication Date: 
Number of Pages: 
Wiley Series in Discrete Mathematics and Optimization
[Reviewed by
Michael Berg
, on

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?”

Very cool.

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.

Preface xi

1 Basic Counting Methods 1

1.1 The multiplication principle 1

1.2 Permutations 4

1.3 Combinations 6

1.4 Binomial coefficient identities 10

1.5 Distributions 19

1.6 The principle of inclusion and exclusion 23

1.7 Fibonacci numbers 31

1.8 Linear recurrence relations 33

1.9 Special recurrence relations 41

1.10 Counting and number theory 45

Notes 50

2 Generating Functions 53

2.1 Rational generating functions 53

2.2 Special generating functions 63

2.3 Partition numbers 76

2.4 Labeled and unlabeled sets 80

2.5 Counting with symmetry 86

2.6 Cycle indexes 93

2.7 Pólya’s theorem 96

2.8 The number of graphs 98

2.9 Symmetries in domain and range 102

2.10 Asymmetric graphs 103

Notes 105

3 The Pigeonhole Principle 107

3.1 Simple examples 107

3.2 Lattice points, the Gitterpunktproblem, and SET 110

3.3 Graphs 115

3.4 Colorings of the plane 118

3.5 Sequences and partial orders 119

3.6 Subsets 124

Notes 126

4 Ramsey Theory 131

4.1 Ramsey’s theorem 131

4.2 Generalizations of Ramsey’s theorem 135

4.3 Ramsey numbers, bounds, and asymptotics 139

4.4 The probabilistic method 143

4.5 Sums 145

4.6 Van der Waerden’s theorem 146

Notes 150

5 Codes 153

5.1 Binary codes 153

5.2 Perfect codes 156

5.3 Hamming codes 158

5.4 The Fano Configuration 162

Notes 168

6 Designs 171

6.1 t-designs 171


6.2 Block designs 175

6.3 Projective planes 180

6.4 Latin squares 182

6.5 MOLS and OODs 185

6.6 Hadamard matrices 188

6.7 The Golay code and S(5, 8, 24) 194

6.8 Lattices and sphere packings 197

6.9 Leech’s lattice 199

Notes 201

A Web Resources 205

B Notation 207

Exercise Solutions 211

References 225

Index 227