Combinatorics

RUSSELL MERRIS, PhD, is Professor of Mathematics and Computer Science at California State University, Hayward. Among his other books is Graph Theory, also published by Wiley.

“…broad and interesting…” (Zentralblatt Math, Vol.1035, No.10, 2004) “...engagingly written...a robust learning tool...” (American Mathematical Monthly, March 2004)

• Preface ixChapter 1 The Mathematics of Choice 11.1. The Fundamental Counting Principle 21.2. Pascal’s Triangle 10* 1.3. Elementary Probability 21* 1.4. Error-Correcting Codes 331.5. Combinatorial Identities 431.6. Four Ways to Choose 561.7. The Binomial and Multinomial Theorems 661.8. Partitions 761.9. Elementary Symmetric Functions 87* 1.10. Combinatorial Algorithms 100Chapter 2 The Combinatorics of Finite Functions 1172.1. Stirling Numbers of the Second Kind 1172.2. Bells, Balls, and Urns 1282.3. The Principle of Inclusion and Exclusion 1402.4. Disjoint Cycles 1522.5. Stirling Numbers of the First Kind 161Chapter 3 Pólya’s Theory of Enumeration 1753.1. Function Composition 1753.2. Permutation Groups 1843.3. Burnside’s Lemma 1943.4. Symmetry Groups 2063.5. Color Patterns 2183.6. Pólya’s Theorem 2283.7. The Cycle Index Polynomial 241Chapter 4 Generating Functions 2534.1. Difference Sequences 2534.2. Ordinary Generating Functions 2684.3. Applications of Generating Functions 2844.4. Exponential Generating Functions 3014.5. Recursive Techniques 320Chapter 5 Enumeration in Graphs 3375.1. The Pigeonhole Principle 338* 5.2. Edge Colorings and Ramsey Theory 3475.3. Chromatic Polynomials 357* 5.4. Planar Graphs 3725.5. Matching Polynomials 3835.6. Oriented Graphs 3945.7. Graphic Partitions 408Chapter 6 Codes and Designs 4216.1. Linear Codes 4226.2. Decoding Algorithms 4326.3. Latin Squares 4476.4. Balanced Incomplete Block Designs 461Appendix A1 Symmetric Polynomials 477Appendix A2 Sorting Algorithms 485Appendix A3 Matrix Theory 495Bibliography 501Hints and Answers to Selected Odd-Numbered Exercises 503Index of Notation 541Index 547