### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Discrete Math for Computer Science Students CS 201 intro into computer science

UNM

GPA 4.0

### View Full Document

## Popular in CS 201 intro into computer science

## Popular in ComputerScienence

This 344 page Class Notes was uploaded by Beatriz Mitchell on Monday November 2, 2015. The Class Notes belongs to CS 201 intro into computer science at University of New Mexico taught by Mr. Burns in Fall 2015. Since its upload, it has received 115 views. For similar materials see CS 201 intro into computer science in ComputerScienence at University of New Mexico.

## Similar to CS 201 intro into computer science at UNM

## Popular in ComputerScienence

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 11/02/15

Discrete Math for Computer Science Students Cliﬀ Stein Ken Bogart Scot Drysdale Dept. of Industrial Engineering Dept. of Mathematics Dept. of Computer Science and Operations Research Dartmouth College Dartmouth College Columbia University ii ▯Kenneth P. Bogart, Scot Drysdale, and Cliﬀ Stein, 2004 Contents 1 Counting 1 1.1 Basic Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1. . The Sum Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 . . Summing Consecutive Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 The Product Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 . Two element subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7. . . 1.2 Counting Lists, Permutations, and Subsets. . . . . . . . . . . . . . . . . . . . . .9 Using the Sum and Product Principles . . . . . . . . . . . . . . . . . . . . . . . .9 Lists and functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 . . The Bijection Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12 . . k-element permutations of a set . . . . . . . . . . . . . . . . . . . . . . . . . .13 . Counting subsets of a set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13. . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 15 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16. . . 1.3 Binomial Coeﬃcients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19 . Pascal’s Triangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19 . . A proof using the Sum Principle . . . . . . . . . . . . . . . . . . . . . . . . . .20 The Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22. . Labeling and trinomial coeﬃcients . . . . . . . . . . . . . . . . . . . . . . . . .23 Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 24 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25. . . 1.4 Equivalence Relations and Counting (Optional) . . . . . . . . . . . . . . . . . . .27 The Symmetry Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27. iii iv CONTENTS Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .28 . The Quotient Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29. . Equivalence class counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30. . Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31. . . The bookcase arrangement problem. . . . . . . . . . . . . . . . . . . . . . . . . .32 The number of k-element multisets of an n-element set. . . . . . . . . . . . . . . 33 Using the quotient principle to explain a quotient . . . . . . . . . . . . . . . . 34. Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 34 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35. . . 2 Cryptography and Number Theory 39 2.1 Cryptography and Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . .39 Introduction to Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . 39. Private Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40. Public-key Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42. Arithmetic modulo n ............................43.... Cryptography using multiplication mod n .....................7 Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 48 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49. . . 2.2 Inverses and GCDs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52 . Solutions to Equations and Inverses mod n ..................2.. Inverses mod n ..............................53..... Converting Modular Equations to Normal Equations . . . . . . . . . . . . . . . . 55 Greatest Common Divisors (GCD) . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Euclid’s Division Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56 . The GCD Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .58 Extended GCD algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Computing Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61. . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 62 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63. . . 2.3 The RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Exponentiation mod n ............................66... The Rules of Exponents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66. Fermat’s Little Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .68 . CONTENTS v The RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . .72 Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 73 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74. . . 2.4 Details of the RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . .76 Practical Aspects of Exponentiation mod n ....................6 How long does it take to use the RSA Algorithm? . . . . . . . . . . . . . . . . . .77 How hard is factoring? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78. . Finding large primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78. . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 81 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81. . . 3 Reﬂections on Logic and Proof 83 3.1 Equivalence and Implication . . . . . . . . . . . . . . . . . . . . . . . . . . . .83 . Equivalence of statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83 . Truth tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85. . . DeMorgan’s Laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .88 . Implication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .89 . . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 92 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94. . . 3.2 Variables and Quantiﬁers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96. Variables and universes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96. . Quantiﬁers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97. . . Standard notation for quantiﬁcation . . . . . . . . . . . . . . . . . . . . . . . .98 Statements about variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99. Rewriting statements to encompass larger universes . . . . . . . . . . . . . . . .100 Proving quantiﬁed statements true or false . . . . . . . . . . . . . . . . . . . .101. Negation of quantiﬁed statements . . . . . . . . . . . . . . . . . . . . . . . . .101. Implicit quantiﬁcation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .103. . Proof of quantiﬁed statements . . . . . . . . . . . . . . . . . . . . . . . . . . 104 . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . .105 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .106. . . 3.3 Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 . . . Direct Inference (Modus Ponens) and Proofs . . . . . . . . . . . . . . . . . . 108 vi CONTENTS Rules of inference for direct proofs . . . . . . . . . . . . . . . . . . . . . . . 109 . Contrapositive rule of inference. . . . . . . . . . . . . . . . . . . . . . . . . .110. . Proof by contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 114 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 . . 4 Induction, Recursion, and Recurrences 117 4.1 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Smallest Counter-Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . .117 The Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . . . 120 Strong Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 . Induction in general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 125 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 . . 4.2 Recursion, Recurrences and Induction . . . . . . . . . . . . . . . . . . . . . . . 128 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .128. . First order linear recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . 129 . Iterating a recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 . Geometric series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .131. . First order linear recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . 133 . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 136 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 . . 4.3 Growth Rates of Solutions to Recurrences . . . . . . . . . . . . . . . . . . . . . 139 Divide and Conquer Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . .139 Recursion Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .140. . Three Diﬀerent Behaviors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 148 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 . . 4.4 The Master Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 Master Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 Solving More General Kinds of Recurrences . . . . . . . . . . . . . . . . . . . . .152 More realistic recurrences (Optional) . . . . . . . . . . . . . . . . . . . . . . .154. Recurrences for general n (Optional) . . . . . . . . . . . . . . . . . . . . . . . 155 Appendix: Proofs of Theorems (Optional) . . . . . . . . . . . . . . . . . . . . . .157 CONTENTS vii Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 159 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 . . 4.5 More general kinds of recurrences . . . . . . . . . . . . . . . . . . . . . . . . .163. Recurrence Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .163. . AW rinkle with Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 Further Wrinkles in Induction Proofs . . . . . . . . . . . . . . . . . . . . . . . 165 Dealing with Functions Other Than n ......................7. 1 Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 171 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 . . 4.6 Recurrences and Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . .174. The idea of selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .174. . A recursive selection algorithm . . . . . . . . . . . . . . . . . . . . . . . . . .174. Selection without knowing the median in advance . . . . . . . . . . . . . . . . . .175 An algorithm to ﬁnd an element in the middle half . . . . . . . . . . . . . . . . .177 An analysis of the revised selection algorithm . . . . . . . . . . . . . . . . . . 179 Uneven Divisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 182 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 . . 5 Probability 185 5.1 Introduction to Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . .185. Why do we study probability? . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 Some examples of probability computations . . . . . . . . . . . . . . . . . . . . .186 Complementary probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . .187 Probability and hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .188. The Uniform Probability Distribution . . . . . . . . . . . . . . . . . . . . . . . 188 Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 191 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 . . 5.2 Unions and Intersections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 . The probability of a union of events . . . . . . . . . . . . . . . . . . . . . . . 194 Principle of inclusion and exclusion for probability . . . . . . . . . . . . . . . 196 The principle of inclusion and exclusion for counting . . . . . . . . . . . . . . .200 Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 201 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 . . viii CONTENTS 5.3 Conditional Probability and Independence . . . . . . . . . . . . . . . . . . . . . 204 Conditional Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .204. Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 . Independent Trials Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 Tree diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .209. . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 212 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 . . 5.4 Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 What are Random Variables? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 Binomial Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 . Expected Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 . Expected Values of Sums and Numerical Multiples . . . . . . . . . . . . . . . . . 220 The Number of Trials until the First Success . . . . . . . . . . . . . . . . . . .222 Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 224 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 . . 5.5 Probability Calculations in Hashing . . . . . . . . . . . . . . . . . . . . . . . 227 Expected Number of Items per Location . . . . . . . . . . . . . . . . . . . . . . .227 Expected Number of Empty Locations . . . . . . . . . . . . . . . . . . . . . . . . 228 Expected Number of Collisions . . . . . . . . . . . . . . . . . . . . . . . . . . .228 Expected maximum number of elements in a slot of a hash table (Optional) . . . 230 Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 234 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 . . 5.6 Conditional Expectations, Recurrences and Algorithms . . . . . . . . . . . . . . . 237 When Running Times Depend on more than Size of Inputs . . . . . . . . . . . . 237 Conditional Expected Values . . . . . . . . . . . . . . . . . . . . . . . . . . . .238 Randomized algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .240 A more exact analysis of RandomSelect . . . . . . . . . . . . . . . . . . . . . . .245 Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 247 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 . . 5.7 Probability Distributions and Variance . . . . . . . . . . . . . . . . . . . . . . 251 Distributions of random variables . . . . . . . . . . . . . . . . . . . . . . . . .251. Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 . . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 258 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 . . CONTENTS ix 6 Graphs 263 6.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 . . The degree of a vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 . Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .267. . Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 . . Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .269. . . Other Properties of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . .270. Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 272 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 . . 6.2 Spanning Trees and Rooted Trees . . . . . . . . . . . . . . . . . . . . . . . . . .276 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 . Breadth First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 . Rooted Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 283 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 . . 6.3 Eulerian and Hamiltonian Paths and Tours . . . . . . . . . . . . . . . . . . . . . 288 Eulerian Tours and Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . .288. Hamiltonian Paths and Cycles . . . . . . . . . . . . . . . . . . . . . . . . . .291. NP-Complete Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 297 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 . . 6.4 Matching Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .300. The idea of a matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 . Making matchings bigger . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 . Matching in Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 Searching for Augmenting Paths in Bipartite Graphs . . . . . . . . . . . . . . . . 306 The Augmentation-Cover algorithm . . . . . . . . . . . . . . . . . . . . . . . 307 Good Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .309. Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 310 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 . . 6.5 Coloring and planarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 . The idea of coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .313. . Interval Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .315. . Planarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 . . x CONTENTS The Faces of a Planar Drawing . . . . . . . . . . . . . . . . . . . . . . . . 318 . . The Five Color Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . .321. . . Important Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . .323. Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .324. . . . . Chapter 1 Counting 1.1 Basic Counting The Sum Principle We begin with an example that illustrates a fundamental principle. Exercise 1.1-1 The loop below is part of an implementation of selection sort, which sorts a list of items chosen from an ordered set (numbers, alphabet characters, words, etc.) into non-decreasing order. (1) for i =1 to n − 1 (2) for j = i +1 to n (3) if (A[i] >A [j]) (4) exchange A[i] and A[j] How many times is the comparison A[i] >A [j] made in Line 3? In Exercise 1.1-1, the segment of code from lines 2 through 4 is executed n − 1 times, once for each value of i between1 and n − 1 inclusive. The ﬁrst time, it makes n − 1 comparisons. The second time, it makes n − 2 comparisons. The ith time, it makes n − i comparisons. Thus the total number of comparisons is (n − 1) + (n − 2) + ··· +1 . (1.1) This formula is not as important as the reasoning that lead us to it. In order to put the reasoning into a broadly applicable format, we will describe what we were doing in the language of sets. Think about the set S containing all comparisons the algorithm in Exercise 1.1-1 makes. We divided set S into n−1 pieces (i.e. smaller sets), t1e set S of comparisons made when i =1, the set 2 of comparisons made when i =2 , and so on through then−1tof comparisons made when i = n−1. We were able to ﬁgure out the number of comparisons in each of these pieces by observation, and added together the sizes of all the pieces in order to get the size of the set of all comparisons. 1 2 CHAPTER 1. COUNTING in order to describe a general version of the process we used, we introduce some set-theoretic terminology. Two sets are called disjoint when they have no elements in common. Each of the sets Siwe described above is disjoint from each of the others, because the comparisons we make for one value of i are diﬀerent from those we make with another value of i.W es the set of sets {S1,...,S m} (above, m was n − 1) is a family of mutually disjoint sets, meaning that it is a family (set) of sets, any two of which are disjoint. With this language, we can state a general principle that explains what we were doing without making any speciﬁc reference to the problem we were solving. Principle 1.1 (Sum Principle) The size of a union of a family of mutually disjoint ﬁnite sets is the sum of the sizes of the sets. Thus we were, in eﬀect, using the sum principle to solve Exercise 1.1-1. We can describe the sum principle using an algebraic notation. Let |S| denote the size of the set S.F or example, |{a,b,c}| =3 and |{a,b,a}| =2. 1 Using this notation, we can state the sum principle as: if S 1 S , ... S are disjoint sets, then 2 m |S1 ∪ S2∪···∪ Sm| = |S 1 + |S2| + ··· + |m | . (1.2) To write this without the “dots” that indicate left-out material, we write ▯ ▯m | S i = |Si|. i=1 i=1 When we can write a set S as a union of disjoint sets S 1, S2,. .., k we say that we have partitioned S into the sets S , S , ..., S , and we say that the sets S , S , ..., S form a partition 1 2 k 1 2 k of S.Tus {{1},{3,5},{2,4}} is a partition of the set {1,2,3,4,5} and the set {1,2,3,4,5} can be partitioned into the sets {1}, {3,5}, {2,4}.I ti s clumsy to say we are partitioning a set into sets, so instead we call the sets Siinto which we partition a set S the blocks of the partition. Thus the sets {1}, {3,5}, {2,4} are the blocks of a partition of {1,2,3,4,5}.I n this language, we can restate the sum principle as follows. Principle 1.2 (Sum Principle) If a ﬁnite set S has been partitioned into blocks, then the size of S is the sum of the sizes of the blocks. Abstraction The process of ﬁguring out a general principle that explains why a certain computation makes sense is an example of the mathematical process of abstraction.W ew on’t try to give a precise deﬁnition of abstraction but rather point out examples of the process as we proceed. In a course in set theory, we would further abstract our work and derive the sum principle from the axioms of 1It may look strange to have |{a,b,a}| =2 , but an element either is or is not in a set. It cannot be in a set multiple times. (This situation leads to the idea of multisets that will be introduced later on in this section.) We gave this example to emphasize that the notation {a,b,a} means the same thing as {a,b}.W hy would someone even contemplate the notation {a,b,a}Suppose we wrote S = {x|x is the ﬁrst letter of Ann, Bob, or Alice}. Explicitly following this description of S would lead us to ﬁrst write down {a,b,a} and the realize it equals {a,b}. 1.1. BASIC COUNTING 3 set theory. In a course in discrete mathematics, this level of abstraction is unnecessary, so we will simply use the sum principle as the basis of computations when it is convenient to do so. If our goal were only to solve this one exercise, then our abstraction would have been almost a mindless exercise that complicated what was an “obvious” solution to Exercise 1.1-1. However the sum principle will prove to be useful in a wide variety of problems. Thus we observe the value of abstraction—when you can recognize the abstract elements of a problem, then abstraction often helps you solve subsequent problems as well. Summing Consecutive Integers Returning to the problem in Exercise 1.1-1, it would be nice to ﬁnd a simpler form for the sum given in Equation 1.1. We may also write this sum as n▯1 n − i. i=1 Now, if we don’t like to deal with summing the values of (n − i), we can observe that the values we are summing are n − 1,n − 2,..., 1, so we may write that n▯1 ▯−1 n − i = i. i=1 i=1 A clever trick, usually attributed to Gauss, gives us a shorter formula for this sum. We write 1+2+ ··· + n − 2+ n − 1 + n − 1+ n − 2+ ··· +2+1 n + n + ··· + n + n The sum below the horizontal line has n−1 terms each equal to n, and thus it is n(n−1). It is the sum of the two sums above the line, and since these sums are equal (being identical except for being in reverse order), the sum below the line must be twice either sum above, so either of the sums above must be n(n − 1)/2. In other words, we may write n−1 n−1 ▯ ▯ n(n − 1) n − i = i = 2 . i=1 i=1 This lovely trick gives us little or no real mathematical skill; learning how to think about things to discover answers ourselves is much more useful. After we analyze Exercise 1.1-2 and abstract the process we are using there, we will be able to come back to this problem at the end of this section and see a way that we could have discovered this formula for ourselves without any tricks. The Product Principle Exercise 1.1-2 The loop below is part of a program which computes the product of two matrices. (You don’t need to know what the product of two matrices is to answer this question.) 4 CHAPTER 1. COUNTING (1) for i =1 to r (2) for j =1 to m (3) S =0 (4) for k =1 to n (5) S = S + A[i,k] ∗ B[k,j] (6) C[i,j]= S How many multiplications (expressed in terms of r, m, and n)d oes this code carry out in line 5? Exercise 1.1-3 Consider the following longer piece of pseudocode that sorts a list of num- bers and then counts “big gaps” in the list (for this problem, a big gap in the list is a place where a number in the list is more than twice the previous number: (1) for i =1 to n − 1 (2) minval = A[i] (3) minindex = i (4) for j = i to n (5) if (A[j] < minval) (6) minval = A[j] (7) minindex = j (8) exchange A[i] and A[minindex] (9) (10) for i =2 to n (11) if (A[i] > 2 ∗ A[i − 1]) (12) bigjump = bigjump +1 How many comparisons does the above code make in lines 5 and 11 ? In Exercise 1.1-2, the program segment in lines 4 through 5, which we call the “inner loop,” takes exactly n steps, and thus makes n multiplications, regardless of what the variables i and j are. The program segment in lines 2 through 5 repeats the inner loop exactly m times, regardless of what i is. Thus this program segment makes n multiplications m times, so it makes nm multiplications. Why did we add in Exercise 1.1-1, but multiply here? We can answer this question using the abstract point of view we adopted in discussing Exercise 1.1-1. Our algorithm performs a certain set of multiplications. For any given i, the set of multiplications performed in lines 2 through 5 can be divided into the set1S of multiplications performed when j =1, the set2S of multiplications performed when j =2 , and, in general, the setjS of multiplications performed for any given j value. Each set S consists of those multiplications the inner loop carries out j for a particular value of j, and there are exactly n multiplications in this seti Let T set of multiplications that our program segment carries out for a certain i value. The sit T is the union of the sets j ; restating this as an equation, we get m ▯ Ti= Sj. j=1 1.1. BASIC COUNTING 5 Then, by the sum principle, the size of the sei T is the sum of the sizes of thejsets S , and a sum of m numbers, each equal to n,is mn. Stated as an equation, ▯ ▯ ▯m |Ti| = | Sj| = |Sj| = n = mn. (1.3) j=1 j=1 j=1 Thus we are multiplying because multiplication is repeated addition! From our solution we can extract a second principle that simply shortcuts the use of the sum principle. Principle 1.3 (Product Principle) The size of a union of m disjoint sets, each of size n,si mn. We now complete our discussion of Exercise 1.1-2. Lines 2 through 5 are executed once for each value of i from 1 to r. Each time those lines are executed, they are executed with a diﬀerent i value, so the set of multiplications in one execution is disjoint from the set of multiplications in any other execution. Thus the set of all multiplications our program carries out is a union of r disjoint setsiTof mn multiplications each. Then by the product principle, the set of all multiplications has size rmn,s o our program carries out rmn multiplications. Exercise 1.1-3 demonstrates that thinking about whether the sum or product principle is appropriate for a problem can help to decompose the problem into easily-solvable pieces. If you can decompose the problem into smaller pieces and solve the smaller pieces, then you either add or multiply solutions to solve the larger problem. In this exercise, it is clear that the number of comparisons in the program fragment is the sum of the number of comparisons in the ﬁrst loop in lines 1 through 8 with the number of comparisons in the second loop in lines 10 through 12 (what two disjoint sets are we talking about here?). Further, the ﬁrst loop makes n(n +1) /2 − 1 comparisons , and that the second loop has n − 1 comparisons, so the fragment makes n(n +1) /2 − 1+ n − 1= n(n +1) /2+ n − 2 comparisons. Two element subsets Often, there are several ways to solve a problem. We originally solved Exercise 1.1-1 by using the sum principal, but it is also possible to solve it using the product principal. Solving a problem two ways not only increases our conﬁdence that we have found the correct solution, but it also allows us to make new connections and can yield valuable insight. Consider the set of comparisons made by the entire execution of the code in this exercise. When i =1, j takes on every value from 2 to n. When i =2, j takes on every value from 3 to n.Th us, for each two numbers i and j,w e compare A[i] and A[j] exactly once in our loop. (The order in which we compare them depends on whether i or j is smaller.) Thus the number of 3 comparisons we make is the same as the number of two element subsets of the set {1,2,...,n } . In how many ways can we choose two elements from this set? If we choose a ﬁrst and second element, there are n wayst oc hoose a ﬁrst element, and for each choice of the ﬁrst element, there are n−1w ayst oc hoose a second element. Thus the set of all such choices is the union of n sets 2To see why this is true, ask yourself ﬁrst where the n(n +1) /2 comes from, and then why we subtracted one. 3The relationship between the set of comparisons and the set of two-element subsets of {1,2,...,n } is an example of a bijection, an idea which will be examined more in Section 1.2. 6 CHAPTER 1. COUNTING of size n − 1, one set for each ﬁrst element. Thus it might appear that, by the product principle, there are n(n − 1) ways to choose two elements from our set. However, what we have chosen is an ordered pair, namely a pair of elements in which one comes ﬁrst and the other comes second. For example, we could choose 2 ﬁrst and 5 second to get the ordered pair (2,5), or we could choose 5 ﬁrst and 2 second to get the ordered pair (5,2). Since each pair of distinct elements of {1,2,...,n } can be ordered in two ways, we get twice as many ordered pairs as two element sets. Thus, since the number of ordered pairs is n(n − 1), the number of two element subsets of {1,2,...,n } is n(n − 1)/2. Therefore the answer to Exercise 1.1-1 is n(n − 1)/2. This number comes up so often▯ ▯at it has its own▯ ▯me and notation. We call this number “n choose 2” and denote it by 2 .T o summarize, 2 stands for the number of two element subsets of an n element set and equals n(n − 1)/2. ▯ ▯ce one answer to Exercise 1.1-1 is 1 + 2 + ··· + n − 1 and a second answer to Exercise 1.1-1 is2 , this shows that ▯ ▯ n n(n − 1) 1+2+ ··· + n − 1= = . 2 2 Important Concepts, Formulas, and Theorems 1. Set. A set is a collection of objects. In a set order is not important. Thus the set {A,B,C} is the same as the set {A,C,B}.A n element either is or is not in a set; it cannot be in a set more than once, even if we have a description of a set which names that element more than once. 2. Disjoint. Two sets are called disjoint when they have no elements in common. 3. Mutually disjoint sets. A set of sets {S ,...,S} is a family of mutually disjoint sets,fi 1 n each two of the sets i are disjoint. 4. Size of a set. Given a set S, the size of S, denoted |S|,i s the number of distinct elements in S. 5. Sum Principle. The size of a union of a family of mutually disjoint sets is the sum of the sizes of the sets. In other words, 1f S2, S Snare disjoint sets, then |S1∪ S 2···∪ Sn| = |S1| + |2 | + ··· +n|S |. To write this without the “dots” that indicate left-out material, we write n n ▯ ▯ | Si| = |Si|. i=1 i=1 6. Partition of a set. A partition of a set S is a set of mutually disjoint subsets (sometimes called blocks) of S whose union is S. 7. Sum of ﬁrst n − 1 numbers. ▯n ▯−1 n(n − 1) n − i = i = . i=1 i=1 2 8. Product Principle. The size of a union of m disjoint sets, each of size n,is mn. ▯n▯ 9. Two element subsets. 2▯ ▯ands for the number of two element subsets of an n element set and equals n(n − 1)/2. n is read as “n choose 2.” 2 1.1. BASIC COUNTING 7 Problems 1. The segment of code below is part of a program that uses insertion sort to sort a list A for i =2 to n j=i while j ≥ 2 and A[j] <A [j − 1] exchange A[j] and A[j − 1] j −− What is the maximum number of times (considering all lists of n items you could be asked to sort) the program makes the comparison A[j] <A [j − 1]? Describe as succinctly as you can those lists that require this number of comparisons. 2. Five schools are going to send their baseball teams to a tournament, in which each team must play each other team exactly once. How many games are required? 3. Use notation similar to that in Equations 1.2 and 1.3 to rewrite the solution to Exercise 1.1-3 more algebraically. 4. In how many ways can you draw a ﬁrst card and then a second card from a deck of 52 cards? 5. In how many ways can you draw two cards from a deck of 52 cards. 6. In how many ways may you draw a ﬁrst, second, and third card from a deck of 52 cards? 7. In how many ways may a ten person club select a president and a secretary-treasurer from among its members? 8. In how many ways may a ten person club select a two person executive committee from among its members? 9. In how many ways may a ten person club select a president and a two person executive advisory board from among its members (assuming that the president is not on the advisory board)? ▯ ▯ 10. By using the formula forn is is straightforward to show that 2 ▯ ▯ ▯ ▯ n − 1 n n 2 = 2 (n − 2). However this proof just uses blind substitution and simpliﬁcation. Find a more conceptual explanation of why this formula is true. 11. If M is an m element set and N is an n-element set, how many ordered pairs are there whose ﬁrst member is in M and whose second member is in N? 12. In the local ice cream shop, there are 10 diﬀerent ﬂavors. How many diﬀerent two-scoop cones are there? (Following your mother’s rule that it all goes to the same stomach, a cone with a vanilla scoop on top of a chocolate scoop is considered the same as a cone with a a chocolate scoop on top of a vanilla scoop.) 8 CHAPTER 1. COUNTING 13. Now suppose that you decide to disagree with your mother in Exercise 12 and say that the order of the scoops does matter. How many diﬀerent possible two-scoop cones are there? 14. Suppose that on day 1 you receive 1 penny, and, for i> 1, on day i you receive twice as many pennies as you did on day i − 1. How many pennies will you have on day 20? How many will you have on day n? Did you use the sum or product principal? 15. The “Pile High Deli” oﬀers a “simple sandwich” consisting of your choice of one of ﬁve diﬀerent kinds of bread with your choice of butter or mayonnaise or no spread, one of three diﬀerent kinds of meat, and one of three diﬀerent kinds of cheese, with the meat and cheese “piled high” on the bread. In how many ways may you choose a simple sandwich? 16. Do you see any unnecessary steps in the pseudocode of Exercise 1.1-3? 1.2. COUNTING LISTS, PERMUTATIONS, AND SUBSETS. 9 1.2 Counting Lists, Permutations, and Subsets. Using the Sum and Product Principles Exercise 1.2-1 A password for a certain computer system is supposed to be between 4 and 8 characters long and composed of lower and/or upper case letters. How many passwords are possible? What counting principles did you use? Estimate the percentage of the possible passwords that have exactly four characters. Ag ood way to attack a counting problem is to ask if we could use either the sum principle or the product principle to simplify or completely solve it. Here that question might lead us to think about the fact that a password can have 4, 5, 6, 7 or 8 characters. The set of all passwords is the union of those with 4, 5, 6, 7, and 8 letters so the sum principle might help us. To write the problem algebraically, let P be the set of i-letter passwords and P be the set of all possible i passwords. Clearly, P = P ∪ P ∪ P ∪ P ∪ P . 4 5 6 7 8 The P i are mutually disjoint, and thus we can apply the sum principal to obtain ▯8 |P| = |Pi| . i=4 We still need to compute |P i|.r an i-letter password, there are 52 choices for the ﬁrst letter, 52 choices for the second and so on. Thus by the product principle, |P |,ithe number of passwords i with i letters is 52 . Therefore the total number of passwords is 524 +52 5 +52 6+52 7 +52 . Of these, 524 have four letters, so the percentage with 54 letters is 4 100 · 52 52 +52 5 +52 6+52 7 +52 . Although this is a nasty formula to evaluate by hand, we can get a quite good estimate as follows. Notice that 52 is 52 times as big as 52 , and even more dramatically larger than any other term in the sum in the denominator. Thus the ratio thus just a bit less than 100 · 524 8 52 , which is 100/52 ,o r approximately .000014. Thus to ﬁve decimal places, only .00001% of the passwords have four letters. It is therefore much easier guess a password that we know has four letters than it is to guess one that has between 4 and 8 letters—roughly 7 million times easier! In our solution to Exercise 1.2-1, we casually referred to the use of the product principle in computing the number of passwords with i letters. We didn’t write any set as a union of sets of equal size. We could have, but it would have been clumsy and repetitive. For this reason we will state a second version of the product principle that we can derive from the version for unions of sets by using the idea of mathematical induction that we study in Chapter 4. Version 2 of the product principle states: 10 CHAPTER 1. COUNTING Principle 1.4 (Product Principle, Version 2) If a set S of lists of length m has the proper- ties that 1. There are 1 diﬀerent ﬁrst elements of lists in S, and 2. For each j> 1 and each choice of the ﬁrst j − 1 elements of a list in S there are ices j of elements in position j of those lists, ▯ m then there are 1 2···mi = k=1iklists in S. Let’s apply this version of the product principle to compute the number of m-letter passwords. Since an m-letter password is just a list of m letters, and since there are 52 diﬀerent ﬁrst elements of the password and 52 choices for each other position of the password, we have 1hat ii 2 = 52,...,im = 52. Thus, this version of the product principle tells us immediately that the number of passwords of length m is1 2i ··m =52 m. In our statement of version 2 of the Product Principle, we have introduced a new notation, the use of Π to stand for product. This no▯ation is called the product notation, and it is used just like summation notation. In particular,k=1 k is read as “The product from k =1to m of ▯ m ik.” Thus k=1ikmeans the same thing as i 1 i2··· m . Lists and functions We have left a term undeﬁned in our discussion of version 2 of the product principle, namely the word “list.” A list of 3 things chosen from a set T consists of a ﬁrst member 1 of T,a second member t of T, and a third member t of T.I fw e rewrite the list in a diﬀerent order, 2 3 we get a diﬀerent list. A list of k things chosen from T consists of a ﬁrst member of T through a kth member of T.W e can use the word “function,” which you probably recall from algebra or calculus, to be more precise. Recall that a function from a set S (called the domain of the function) to a set T (called the range of the function) is a relationship between the elements of S and the elements of T that relates exactly one element of T to each element of S.W e use a letter like f to stand for a function and use f(x)t o stand for the one and only one element of T that the function relates to the element x of S.Y ou are probably used to thinking of functions in terms of formulas like 2 f(x)= x .W e need to use formulas like this in algebra and calculus because the functions that you study in algebra and calculus have inﬁnite sets of numbers as their domains and ranges. In discrete mathematics, functions often have ﬁnite sets as their domains and ranges, and so it is possible to describe a function by saying exactly what it is. For example f(1) = Sam,f (2) = Mary,f (3) = Sarah is a function that describes a list of three people. This suggests a precise deﬁnition of a list of k elements from a set T:A list of k elements from a set T is a function from {1,2,...,k } to T. Exercise 1.2-2 Write down all the functions from the two-element set {1,2} to the two- element set {a,b}. Exercise 1.2-3 How many functions are there from a two-element set to a three element set? 1.2. COUNTING LISTS, PERMUTATIONS, AND SUBSETS. 11 Exercise 1.2-4 How many functions are there from a three-element set to a two-element set? In Exercise 1.2-2 one thing that is diﬃcult is to choose a notation for writing the functions down. We will use f , f , etc., to stand for the various functions we ﬁnd. To describe a function 1 2 fifrom {1,2} to {a,b} we have to specify f (1) ani f (2). Weican write f1(1) = af 1 (2) = b f 2(1) = bf 2 (2) = a f3(1) = af 3 (2) = a f (1) = bf (2) = b 4 4 We have simply written down the functions as they occurred to us. How do we know we have all of them? The set of all functions from {1,2} to {a,b} is the union of the functions f i that have fi(1) = a and those that have f (1) i b. The set of functions with f (1) = a his two elements, one for each choice of f i2). Therefore by the product principle the set of all functions from {1,2} to {a,b} has size 2 · 2=4. To compute the number of functions from a two element set (say {1,2})t oa three element set, we can again think of using f i to stand for a typical function. Then the set of all functions is the union of three sets, one for each choice of f (1i. Each of these sets has three elements, one for each choice of f (i). Thus by the product principle we have 3 · 3=9 functions from a two element set to a three element set. To compute the number of functions from a three element set (say {1,2,3})t oat wo element set, we observe that the set of functions is a union of four sets, one for each choice of f (1) and i fi(2) (as we saw in our solution to Exercise 1.2-2). But each of these sets has two functions in it, one for each choice of f (i). Then by the product principle, we have 4 · 2=8 functions from a three element set to a two element set. A function f is called one-to-one or an injection if whenever x ▯= y, f(x) ▯= f(y). Notice that the two functions f 1 and f 2e gave in our solution of Exercise 1.2-2 are one-to-one, but f and 3 f are not. 4 A function f is called onto or a surjection if every element y in the range is f(x) for some x in the domain. Notice that the functions f 1 and f 2n our solution of Exercise 1.2-2 are onto functions but f 3 and f 4re not. Exercise 1.2-5 Using two-element sets or three-element sets as domains and ranges, ﬁnd an example of a one-to-one function that is not onto. Exercise 1.2-6 Using two-element sets or three-element sets as domains and ranges, ﬁnd an example of an onto function that is not one-to-one. Notice that the function given by f(1) = c, f(2) = a is an example of a function from {1,2} to {a,b,c} that is one-to one but not onto. Also, notice that the function given by f(1) = a, f(2) = b, f(3) = a is an example of a function from {1,2,3} to {a,b} that is onto but not one to one. 12 CHAPTER 1. COUNTING The Bijection Principle Exercise 1.2-7 The loop below is part of a program to determine the number of triangles formed by n points in the plane. (1) trianglecount = 0 (2) for i =1 to n (3) for j = i +1 to n (4) for k = j +1 to n (5) if points i, j, and k are not collinear (6) trianglecount = trianglecount +1 How many times does the above code check three points to see if they are collinear in line 5? In Exercise 1.2-7, we have a loop embedded in a loop that is embedded in another loop. Because the second loop, starting in line 3, begins with j = i +1 and j increase up to n, and because the third loop, starting in line 4, begins with k = j +1 and increases up to n, our code examines each triple of values i, j, k with i<j<k exactly once. For example, if n is 4, then the triples (i,j,k) used by the algorithm, in order, are (1,2,3), (1,2,4), (1,3,4), and (2,3,4). Thus one way in which we might have solved Exercise 1.2-7 would be to compute the number of such triples, which we will call increasing triples.A s with the case of two-element subsets earlier, the number of such triples is the number of three-element subsets of an n-element set. This is the second time that we have proposed counting the elements of one set (in this case the set of increasing triples chosen from an n-element set) by saying that it is equal to the number of elements of some other set (in this case the set of three element subsets of an n-element set). When are we justiﬁed in making such an assertion that two sets have the same size? There is another fundamental principle that abstracts our concept of what it means for two sets to have the same size. Intuitively two sets have the same size if we can match up their elements in such a way that each element of one set corresponds to exactly one element of the other set. This description carries with it some of the same words that appeared in the deﬁnitions of functions, one-to-one, and onto. Thus it should be no surprise that one-to-one and onto functions are part of our abstract principle. Principle 1.5 (Bijection Principle) Two sets have the same size if and only if there is a one-to-one function from one set onto the other. Our principle is called the bijection principle because a one-to-one and onto function is called a bijection. Another name for a bijection is a one-to-one correspondence.A bijection from a set to itself is called a permutation of that set. What is the bijection that is behind our assertion that the number of increasing triples equals the number of three-element subsets? We deﬁne the function f to be the one that takes the increasing triple (i,j,k)t o the subset {i,j,k}. Since the three elements of an increasing triple are diﬀerent, the subset is a three element set, so we have a function from increasing triples to three element sets. Two diﬀerent triples can’t be the same set in two diﬀerent orders, so diﬀerent triples have to be associated with diﬀerent sets. Thus f is one-to-one. Each set of three integers can be listed in increasing order, so it is the image under f of an increasing triple. Therefore f is onto. Thus we have a one-to-one correspondence, or bijection, between the set of increasing triples and the set of three element sets. 1.2. COUNTING LISTS, PERMUTATIONS, AND SUBSETS. 13 k-element permutations of a set Since counting increasing triples is equivalent to counting three-element subsets, we can count increasing triples by counting three-element subsets instead. We use a method similar to the one we used to compute the number of two-element subsets of a set. Recall that the ﬁrst step wast o compute the number of ordered pairs of distinct elements we could chose from the set {1,2,...,n }.S ow en ow ask in how many ways may we choose an ordered triple of distinct elements from {1,2,...,n },o r more generally, in how many ways may we choose a list of k distinct elements from {1,2,...,n }.A list of k-distinct elements chosen from a set N is called a k-element permutation of N. 4 How many 3-element permutations of {1,2,...,n } can we make? Recall that a k-element permutation is a list of k distinct elements. There are n choices for the ﬁrst number in the list. For each way of choosing the ﬁrst element, there are n−1c hoices for the second. For each choice of the ﬁrst two elements, there are n − 2 wayst oc hoose a third (distinct) number, so by version 2o f the product principle, there are n(n − 1)(n − 2) ways to choose the list of numbers. For example, if n is 4, the three-element permutations of {1,2,3,4} are L = {123,124,132,134,142,143,213,214,231,234,241,243, 312,314,321,324,341,342,412,413,421,423,431,432}. (1.4) There are indeed 4 · 3 · 2= 24 lists in this set. Notice that we have listed the lists in the order that they would appear in a dictionary (assuming we treated numbers as we treat letters). This ordering of lists is called the lexicographic ordering. A general pattern is emerging. To compute the number of k-element permutations of the set {1,2,...,n },w e recall that they are lists and note that we have n choices for the ﬁrst element of the list, and regardless of which choice we make, we have n − 1c hoices for the second element of the list, and more generally, given the ﬁrst i−1 elements of a list we have n−(i−1) = n−i+1 choices for the ith element of the list. Thus by version 2 of the product principle, we have n(n −1)··· (n −k +1) (which is the ﬁrst k terms of n!) ways to choose a k-element permutation of {1,2,...,n }. There is a very handy notation for this product ﬁrst suggested by Don Knuth. k ▯ k−1 We use n to stand for n(n − 1)··· (n − k +1)= i=0 n − i, and call it the kth falling factorial power of n.W e can summarize our observations in a theorem. Theorem 1.1 The number k-element permutations of an n-element set is k−1 k ▯ n = n − i = n(n − 1)··· (n − k +1)= n!/(n − k)! . i=0 Counting subsets of a set We now return to the question of counting the number of three element subsets of a {1,2,...,n }. ▯n▯ We use 3 , which we read as “n choose 3” to stand for the number of three element subsets of 4 In particular a k-element permutation of {1,2,...k } is a list of k distinct elements of {1,2,...,k }, which, by our deﬁnition of a list is a function from {1,2,...,k } to {1,2,...,k }. This function must be one-to-one since the elements of the list are distinct. Since there are k distinct elements of the list, every element of {1,2,...,k } appears in the list, so the function is onto. Therefore it is a bijection. Thus our deﬁnition of a permutation of a set is consistent with our deﬁnition of a k-element permutation in the case where the set is {1,2,...,k }. 14 CHAPTER 1. COUNTING {1,2,...,n },o r more generally of any n-element set. We have just carried out the ﬁrst step of ▯n▯ computing 3 by counting the number of three-element permutations of {1,2,...,n }. Exercise 1.2-8 Let L be the set of all three-element permutations of {1,2,3,4},a si Equation 1.4. How many of the lists (permutations) in L are lists of the 3 element set {1,3,4}? What are these lists? We see that this set appears in L as 6 diﬀerent lists: 134, 143, 314, 341, 413, and 431. In general given three diﬀerent numbers with which to create a list, there are three ways to choose the ﬁrst number in the list, given the ﬁrst there are two ways to choose the second, and given the ﬁrst two there is only one way to choose the third element of the list. Thus by version 2 of the product principle once again, there are 3 · 2 · 1=6 ways to make the list. Since there are n(n − 1)(n − 2) permutations of an n-element set, and each three-element subset appears in exactly 6 of these lists, the number of three-element permutations is six times ▯n▯ the number of three element subsets. That is, n(n − 1)(n − 2) = 3 · 6. Whenever we see that one number that counts something is the product of two other numbers that count something, we should expect that there is an argument using the product principle that explains why. Thus we should be able to see how to break the set of all 3-element permutations of {1,2,...,n } into either 6 disjoint sets of size ▯or into ▯n▯ subsets of size six. Since we argued that each 3 3 three element subset corresponds to six lists, we have described how to get a set of six lists from one three-element set. Two diﬀerent subsets could never give us the same lists, so our sets of three-element li▯ ▯ are disjoint. In other words, we have divided the set of all three-element permutations into n mutually sets of size six. In this way the product principle does explain 3 ▯n▯ why n(n − 1)(n − 2) = 3 · 6. By division we get that we have ▯ ▯ n = n(n − 1)(n − 2)/6 3 three-element subsets of {1,2,...,n }.r n =4 , the number is 4(3)(2)/6=4 . These sets are {1,2,3}, {1,2,4}, {1,3,4}, and {2,3,4}.I ti s straightforward to verify that each of these sets appears 6 times in L,a s6 diﬀerent lists. Essentially the same argument gives us the number of k-element subsets of {1,2,...,n }.W e ▯n▯ denote this number by k , and read it as “n choose k.” Here i▯n▯he argument: the set of all k-element permutations of {1,2,...,n } can be partitioned into k disjoint blocks , each block consisting of all k-element permutations of a k-element subset of {1,2,...,n }. But the number of k-element permutations of a k-element set is k!, either by version 2 of the product principle or by Theorem

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.