Contents iX 24 The Pigeonhole Principle 205 Cantor's Theorem 208 Recap 210 Exercises 210 25 Composition 211 Identity Function 214 Recap 215 Exercises 215 26 Permutations 216 Cycle Notation 217 Calculations with Permutations 220 Transpositions 221 A Graphical Approach 226 Recap 228 Exercises 228 27 Symmetry 231 Symmetries of a Square 231 Symmetries as Permutations 232 Combining Symmetries 233 Formal Definition of Symmetry 235 Recap 236 Exercises 236 28 Assorted Notation 236 Big oh 236 2 and 239 Little oh 240 Floor and Ceiling 241 Recap 242 Exercises 242 Chapter 5 Self Test 242 6 Probability 245 29 Sample Space 245 Recap 248 Exercises 248 30 Events 249 Combining Events 252 The Birthday Problem 253 Recap 254 Exercises 2556 24 The Pigeonhole Principle Cantor's Theorem 208 Recap 210 Exercises 210 25 Composition 211 Identity Function 214 Recap 215 Exercises 215 26 Permutations 216 Cycle Notation 217 Calculations with Permutations Transpositions 221 A Graphical Apptoach 226 Recap 228 Exercises 228 27 Symmetry 231 Symmetries of a Square Symmetries as Permutations 231 Combining Symmetries 233 Formal Definition of Symmetry Recap 236 Exercises 236 28 Assorted Notation 236 Big oh 236 Q and e 239 Little oh 240 Floor and Ceiling 241 Recap 242 Exercises 242 Chapter 5 Self Test 242 Probability 245 29 Sample Space 245 Recap 248 Exercises 248 30 Events 249 Combining Events The Birthday Problem Recap 254 Exercises 255 252 253 Contents ix 205 220 232 235