Combinatorial Reasoning

DUANE DETEMPLE, 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 PROBLEMSIndex 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