Combinatorial Reasoning

DUANE De TEMPLE, PHD, is Professor Emeritus in the Department of Mathematics at Washington State University (WSU). He is the recipient of the 2007 WSU Sahlin Faculty Excellence Award for Instruction as well as the Distinguished Teaching Award from the Pacific Northwest Section of the Mathematical Association of America.WILLIAM WEBB, PHD, is Professor in the Department of Mathematics at Washington State University and President of the Fibonacci Association. His research interests include the properties of recurrence sequences and binomial coefficients. He is the author of numerous research publications on combinatorics, number theory, fair division, and cryptography.

• Preface ixPart I The Basics of Enumerative Combinatorics1 Initial EnCOUNTers with Combinatorial Reasoning 31.1 Introduction, 31.2 The Pigeonhole Principle, 31.3 Tiling Chessboards with Dominoes, 131.4 Figurate Numbers, 181.5 Counting Tilings of Rectangles, 241.6 Addition and Multiplication Principles, 331.7 Summary and Additional Problems, 46References, 502 Selections, Arrangements, and Distributions 512.1 Introduction, 512.2 Permutations and Combinations, 522.3 Combinatorial Models, 642.4 Permutations and Combinations with Repetitions, 772.5 Distributions to Distinct Recipients, 862.6 Circular Permutations and Derangements, 1002.7 Summary and Additional Problems, 109Reference, 1123 Binomial Series and Generating Functions 1133.1 Introduction, 1133.2 The Binomial and Multinomial Theorems, 1143.3 Newton’s Binomial Series, 1223.4 Ordinary Generating Functions, 1313.5 Exponential Generating Functions, 1473.6 Summary and Additional Problems, 163References, 1664 Alternating Sums, Inclusion-Exclusion Principle, Rook Polynomials, and Fibonacci Nim 1674.1 Introduction, 1674.2 Evaluating Alternating Sums with the DIE Method, 1684.3 The Principle of Inclusion–Exclusion (PIE), 1794.4 Rook Polynomials, 1914.5 (Optional) Zeckendorf Representations and Fibonacci Nim, 2024.6 Summary and Additional Problems, 207References, 2105 Recurrence Relations 2115.1 Introduction, 2115.2 The Fibonacci Recurrence Relation, 2125.3 Second-Order Recurrence Relations, 2225.4 Higher-Order Linear Homogeneous Recurrence Relations, 2335.5 Nonhomogeneous Recurrence Relations, 2475.6 Recurrence Relations and Generating Functions, 2575.7 Summary and Additional Problems, 268References, 2736 Special Numbers 2756.1 Introduction, 2756.2 Stirling Numbers, 2756.3 Harmonic Numbers, 2966.4 Bernoulli Numbers, 3066.5 Eulerian Numbers, 3156.6 Partition Numbers, 3236.7 Catalan Numbers, 3356.8 Summary and Additional Problems, 345References, 352Part II Two Additional Topics in Enumeration7 Linear Spaces and Recurrence Sequences 3557.1 Introduction, 3557.2 Vector Spaces of Sequences, 3567.3 Nonhomogeneous Recurrences and Systems of Recurrences, 3677.4 Identities for Recurrence Sequences, 3787.5 Summary and Additional Problems, 3908 Counting with Symmetries 3938.1 Introduction, 3938.2 Algebraic Discoveries, 3948.3 Burnside’s Lemma, 4078.4 The Cycle Index and Pólya’s Method of Enumeration, 4178.5 Summary and Additional Problems, 430References, 432Part III Notations Index, Appendices, and Solutions to Selected Odd Problems Index of Notations 435Appendix A Mathematical Induction 439A.1 Principle of Mathematical Induction, 439A.2 Principle of Strong Induction, 441A.3 Well Ordering Principle, 442Appendix B Searching the Online Encyclopedia of Integer Sequences (OEIS) 443B. 1 Searching a Sequence, 443B. 2 Searching an Array, 444B. 3 Other Searches, 444B. 4 Beginnings of OEIS, 444Appendix C Generalized Vandermonde Determinants 445Hints, Short Answers, and Complete Solutions to Selected Odd Problems 449Index 467