# Combinatorial Reasoning: An Introduction to the Art of Counting

###### Duane DeTemple and William Webb
Publisher:
Wiley
Publication Date:
2014
Number of Pages:
470
Format:
Hardcover
Price:
115.00
ISBN:
9781118652183
Category:
Textbook
[Reviewed by
Mark Hunacek
, on
06/9/2014
]

This recently published book is an attractive candidate as a text for an undergraduate course in combinatorics that emphasizes the enumerative aspects of the subject and omits graph theory. It is clearly written, requires minimal prerequisites to understand (just the inevitable “mathematical maturity” and some prior exposure to power series, as well as, in some (easily omitted) sections, a bit of linear or abstract algebra), contains lots of examples, and gives a large collection of exercises (both computational and proof) of varying levels of difficulty.

The topics covered provide for some flexibility in its use; there is more material than can be covered in one semester, so an instructor teaching a fairly sophisticated course can do some of the early chapters quickly if desired and get to some of the more sophisticated material at the end.

In more detail: the first chapter is largely introductory; it discusses some basic combinatorial problems (e.g., tiling problems) to illustrate the flavor of the subject, and also begins the systematic analysis of counting by introducing the sum and product rules. The pigeonhole principle is also introduced and some standard applications (including the Erdős-Szekeres theorem) are provided.

Counting is discussed in considerably more detail in the next chapter, which discusses permutations and combinations, both with and without repetition; the idea of proving binomial coefficient identities using combinatorial arguments is also introduced. Generating functions (ordinary and exponential) are introduced and discussed in some detail in chapter 3. Chapter 4 introduces the Inclusion-Exclusion Principle, which is then combined with generating functions to address the question of enumerating the number of ways in which rooks can be placed on an $$n\times n$$ chessboard with forbidden squares, so that no one rook can attack another. Another interesting feature of this chapter is a statement and prove of a result due to Zeckendorf (that any positive integer can be written uniquely as the sum of non-consecutive Fibonacci numbers), along with an application of this result to a two-person game called Fibonacci Nim.

The discussion of Fibonacci numbers anticipates the subject matter of recurrence relations, which are the subject of chapter 5. Chapter 6 then introduces a variety of special numbers (Stirling, partition, Catalan, etc.) that come up a lot in combinatorics. The various sections in this chapter are largely independent of one another.

The six chapters discussed above constitute Part I (“The Basics of Enumerative Combinatorics”) of the text and comprise about three-quarters of it. Part II of the book, on “additional topics”, consists of two chapters, the first of which revisits recurrence relationships from a linear algebraic point of view, and the second of which discusses group actions and Pólya counting. Part III consists of several Appendices and a section, a bit less than 20 pages long, giving hints (and in some cases complete solutions) to selected odd-numbered problems in the text.

There are a few scattered references to graphs in the book (sometimes in the exercises), but there is no systematic development of the subject per se, so use of this book as a text may present problems at universities that do not offer individual courses in combinatorics and graph theory and like to cover aspects of both subjects in a combined course. (Instructors of such a course might want to look at Brualdi’s Introductory Combinatorics, an extremely well-written book with coverage of graph theory and other topics not mentioned in this text.) Other omissions that may be noticed by people include the lack of any discussion of Hall’s famous Marriage Theorem, and (in keeping with the book’s emphasis on the enumerative aspects of the subject) no discussion of block designs. Of course, every author must make hard choices as to where to draw the line, and the omission of certain pet topics is almost inevitable in any introductory book.

One other potential drawback that should be mentioned is that the Wiley website lists a solutions manual for this book that will be, as of August of this year, available for purchase by the general public. In fact, as I write this, I see that this manual, which looks like a book, is already listed for sale on amazon.com. I think it ill-advised to make solutions so easily available to students, particularly since I, like many of my colleagues, use textbook problems as one source of graded homework assignments. Also, every college mathematics instructor knows that many students lose the incentive to work hard on problems when solutions are easily available, and it is this hard work that is crucial to learning the material properly. Unfortunately this is not the only book for which Wiley is doing this; a book I am using for a geometry class next semester (Classical Geometry by Leonard et al.) also has (or will have in the near future) a book-like solutions manual available for general purchase, a circumstance which gave me pause in selecting the text. I hope Wiley isn’t planning on making a habit of selling solutions manuals to their texts.

These concerns, however, are outweighed by some very positive features of the text. It has obviously been written with the student reader in mind, and the authors have (wisely, in my view) made the deliberate decision to occasionally talk in intuitive terms rather than express everything completely rigorously. Contrast, for example, the way in which the pigeonhole principle is initially stated in this text (“If $$n+1$$ or more objects are placed into $$n$$ boxes, then at least one of the boxes contains two or more of the objects”) with the way in which it is initially stated in Erickson’s Introduction to Combinatorics:

Pigeonhole principle. If $$f: A\to B$$ is a function, with $$A$$ and $$B$$ finite nonempty sets, then the following two statements hold:

(1) There exists $$b\in B$$ with $$|f^{-1}(b)|\geq |A|/|B|$$.

(2) There exists $$b\in B$$ with $$|f^{-1}(b)|\leq |A|/|B|.$$

(To be fair, Erickson does eventually give the intuitive phrasing of the principle. Nevertheless, I can’t help but believe that, for pedagogical purposes, it is better to lead off with the intuitive version.) The explanations in this text are easy to follow and convey insight into the material covered. Instead of giving very abstract derivations or discussions, the authors typically work out small special cases first and then, with this as motivation, give a general, but still fairly concrete, derivation. I suspect students will enjoy reading this text.

All in all, this is, as I noted at the very beginning of this review, a very attractive book, and any instructor of a combinatorics course who is not overly troubled by the potential problems noted above, should certainly look seriously at this text before making a selection.

Mark Hunacek (mhunacek@iastate.edu) teaches mathematics at Iowa State University.

PREFACE ix

PART I THE BASICS OF ENUMERATIVE COMBINATORICS

1 Initial EnCOUNTers with Combinatorial Reasoning 3

1.1 Introduction, 3

1.2 The Pigeonhole Principle, 3

1.3 Tiling Chessboards with Dominoes, 13

1.4 Figurate Numbers, 18

1.5 Counting Tilings of Rectangles, 24

1.6 Addition and Multiplication Principles, 33

1.7 Summary and Additional Problems, 46

References, 50

2 Selections, Arrangements, and Distributions 51

2.1 Introduction, 51

2.2 Permutations and Combinations, 52

2.3 Combinatorial Models, 64

2.4 Permutations and Combinations with Repetitions, 77

2.5 Distributions to Distinct Recipients, 86

2.6 Circular Permutations and Derangements, 100

2.7 Summary and Additional Problems, 109

Reference, 112

3 Binomial Series and Generating Functions 113

3.1 Introduction, 113

3.2 The Binomial and Multinomial Theorems, 114

3.3 Newton’s Binomial Series, 122

3.4 Ordinary Generating Functions, 131

3.5 Exponential Generating Functions, 147

3.6 Summary and Additional Problems, 163

References, 166

4 Alternating Sums, Inclusion-Exclusion Principle, Rook Polynomials, and Fibonacci Nim 167

4.1 Introduction, 167

4.2 Evaluating Alternating Sums with the DIE Method, 168

4.3 The Principle of Inclusion–Exclusion (PIE), 179

4.4 Rook Polynomials, 191

4.5 (Optional) Zeckendorf Representations and Fibonacci Nim, 202

4.6 Summary and Additional Problems, 207

References, 210

5 Recurrence Relations 211

5.1 Introduction, 211

5.2 The Fibonacci Recurrence Relation, 212

5.3 Second-Order Recurrence Relations, 222

5.4 Higher-Order Linear Homogeneous Recurrence Relations, 233

5.5 Nonhomogeneous Recurrence Relations, 247

5.6 Recurrence Relations and Generating Functions, 257

5.7 Summary and Additional Problems, 268

References, 273

6 Special Numbers 275

6.1 Introduction, 275

6.2 Stirling Numbers, 275

6.3 Harmonic Numbers, 296

6.4 Bernoulli Numbers, 306

6.5 Eulerian Numbers, 315

6.6 Partition Numbers, 323

6.7 Catalan Numbers, 335

6.8 Summary and Additional Problems, 345

References, 352

PART II TWO ADDITIONAL TOPICS IN ENUMERATION

7 Linear Spaces and Recurrence Sequences 355

7.1 Introduction, 355

7.2 Vector Spaces of Sequences, 356

7.3 Nonhomogeneous Recurrences and Systems of Recurrences, 367

7.4 Identities for Recurrence Sequences, 378

7.5 Summary and Additional Problems, 390

8 Counting with Symmetries 393

8.1 Introduction, 393

8.2 Algebraic Discoveries, 394

8.3 Burnside’s Lemma, 407

8.4 The Cycle Index and P´olya’s Method of Enumeration, 417

8.5 Summary and Additional Problems, 430

References, 432

PART III NOTATIONS INDEX, APPENDICES, AND SOLUTIONS TO SELECTED ODD PROBLEMS

Index of Notations 435

Appendix A Mathematical Induction 439

A.1 Principle of Mathematical Induction, 439

A.2 Principle of Strong Induction, 441

A.3 Well Ordering Principle, 442

Appendix B Searching the Online Encyclopedia of Integer Sequences (OEIS) 443

B.1 Searching a Sequence, 443

B.2 Searching an Array, 444

B.3 Other Searches, 444

B.4 Beginnings of OEIS, 444

Appendix C Generalized Vandermonde Determinants 445

Hints, Short Answers, and Complete Solutions to Selected Odd Problems 449

INDEX 467