Contents vii Cartesian Product 73 Recap 74 Exercises 74 12 Combinatorial Proof:Two Examples 76 Recap 80 Exercises 80 Chapter 2 Self Test 80 3 Counting and Relations 83 13 Relations 83 Properties of Relations 86 Recap 87 Exercises 87 14 Equivalence Relations 89 Equivalence Classes 92 Recap 95 Exercises 96 15 Partitions 98 Counting Classes/Parts 100 Recap 102 Exercises 102 16 Binomial Coefficients 104 Calculating ( 107 Pascal's Triangle 109 A Formula for() 111 Recap 113 Exercises 113 17 Counting Multisets 117 Multisets 117 Formulas for()） 119 Recap 122 Exercises 122 18 Inclusion-Exclusion 123 How to Use Inclusion-Exclusion 126 Derangements 129 A Ghastly Formula 132 Recap 132 Exercises 132 Chapter 3 Self Test 133Contents vii Cartesian Product 73 Recap 74 Exercises 7 4 12 Combinatorial Proof: Two Examples 76 Recap 80 Exercises 80 Chapter 2 Self Test 80 3 Counting and Relations 83 13 Relations 83 Properties of Relations 86 Recap 87 Exercises 87 14 Equivalence Relations 89 Equivalence Classes 92 Recap 95 Exercises 96 15 Partitions 98 Counting Classes/Parts 100 Recap 102 Exercises 102 16 Binomial Coefficients 104 Calculating G) 107 Pascal's Triangle 109 A Formula for G) 111 Recap 113 Exercises 113 17 Counting Multisets 117 Multisets 117 Formulas for (G)) 119 Recap 122 Exercises 122 18 Inclusion-Exclusion 123 How to Use Inclusion-Exclusion 126 Derangements 129 A Ghastly Formula 132 Recap 132 Exercises 132 Chapter 3 Self Test 133