Counting I: One-To-One Correspondence and Choice TreesSlide 2Addition RuleSuppose I roll a white die and a black die.S Set of all outcomes where the dice show different values. S = ?Slide 8Slide 9S Set of all outcomes where the black die shows a smaller number than the white die. S = ?Slide 11S Set of all outcomes where the black die shows a smaller number than the white die. S = ?“It is clear by symmetry that |S| = |L|.”Pinning down the idea of symmetry by exhibiting a correspondence.Slide 15Let f:A®B be a function from a set A to a set B.Let’s restrict our attention to finite sets. 1-1 f:A®B Þ A £ B onto f:A®B Þ A B 1-1 onto f:A®B Þ A = B1-1 onto Correspondence (just “correspondence” for short)Correspondence PrincipleSlide 23Question: How many n-bit sequences are there?A = a,b,c,d,e has many subsets.Question: How many subsets can be formed from the elements of a 5-element set?Slide 27A = a1, a2, a3,…, an B = set of all n-bit stringsSlide 29Slide 30Slide 31Let f:A®B be a function from a set A to a set B.Slide 33Slide 34Slide 35Slide 36Slide 37A restaurant has a menu with 5 appetizers, 6 entrees, 3 salads, and 7 desserts.A restaurant has a menu with 5 appetizers, 6 entrees, 3 salads, and 7 desserts.Hobson’s restaurant has only 1 appetizer, 1 entree, 1 salad, and 1 dessert.Choice Tree for 2n n-bit sequences2n n-bit sequences2 choices for first bit × 2 choices for second bit × 2 choices for third bit … × 2 choices for the nthLeaf Counting LemmaChoice TreeSlide 46Slide 47Product RuleProduct Rule (rephrased)How many different orderings of deck with 52 cards?A permutation or arrangement of n objects is an ordering of the objects.Slide 52Slide 53Slide 54Slide 55Slide 56If 10 horses race, how many orderings of the top three finishers are there?The number of ways of ordering, permuting, or arranging r out of n objects.Slide 59Ordered Versus UnorderedSlide 61Slide 62A combination or choice of r out of n objects is an (unordered) set of r of the n objects.Slide 64Slide 65How many 8 bit sequences have 2 0’s and 6 1’s?Slide 67Symmetry in the formula:How many hands have at least 3 aces?Slide 70Slide 71Four different sequences of choices produce the same handSlide 73The Sleuth’s CriterionScheme I 1) Choose 3 of 4 aces 2) Choose 2 of the remaining cardsSlide 76Scheme II 1) Choose 3 out of 4 aces 2) Choose 2 out of 48 non-ace cardsScheme II 1) Choose 4 out of 4 aces 2) Choose 1 out of 48 non-ace cardsSlide 79Slide 80Slide 81Counting I: One-To-One Correspondence and Choice Trees Great Theoretical Ideas In Computer ScienceAnupam GuptaCS 15-251 Fall 2006Lecture 6 Sept 14, 2006 Carnegie Mellon UniversityHow many seats in this auditorium?Hint: Count without counting!Addition RuleLet A and B be two disjoint finite sets.The size of AB is the sum of the size of A and the size of B.A B A B Suppose I roll a white die and a black die.S Set of all outcomes where the dice show different values.S = ?S Set of all outcomes where the dice show different values.S = ?Ai set of outcomes where the black die says i and the white die says something else.S A A 5 30i ii=1 i=1 i 16 6 6S Set of all outcomes where the dice show different values.S = ?T set of outcomes where dice agree.| S T | = # of outcomes = 36|S| + |T| = 36 |T| = 6|S| = 36 – 6 = 30.S Set of all outcomes where the black die shows a smaller number than the white die. S = ?S Set of all outcomes where the black die shows a smaller number than the white die. S = ?Ai set of outcomes where the black die says i and the white die says something larger.S A A A A A AS 5 4 3 2 1 0 151 2 3 4 5 6 S Set of all outcomes where the black die shows a smaller number than the white die. S = ?L set of all outcomes where the black die shows a larger number than the white die.It is clear by symmetry that S = L.S + L = 30Therefore S = 15“It is clear by symmetry that |S| = |L|.”Pinning down the idea of symmetry by exhibiting a correspondence.Let’s put each outcome in S in Let’s put each outcome in S in correspondence with an outcome in L correspondence with an outcome in L by by swappingswapping the color of the dice.the color of the dice.S LLet’s put each outcome in S in Let’s put each outcome in S in correspondence with an outcome in L correspondence with an outcome in L by by swappingswapping the color of the dice.the color of the dice.Pinning down the idea of symmetry by exhibiting a correspondence.Each outcome in S gets matched with exactly one outcome in L, with none left over. Thus: S = L.Let f:AB be a function from a set A to a set B.f is 1-1 if and only ifx,yA, xyf(x)f(y)For EveryThere Existsf is onto if and only ifzB xA f(x) = zLet’s restrict our attention to finite sets.A B 1-1 f:AB A BAB onto f:AB A BAB 1-1 onto f:AB A = BAB1-1 onto Correspondence(just “correspondence” for short)A BA = BCorrespondence PrincipleIf two finite sets can be placed into 1-1 onto correspondence, then they have the same size.Correspondence PrincipleIf two finite sets can be placed into 1-1 onto correspondence, then they have the same size.It’s one of the most important mathematical ideas of all time!Question: How many n-bit sequences are there?000000 0000001 1000010 2000011 3...1…11111 2n-1Each sequence corresponds to a uniquenumber from 0 to 2n-1. Hence 2n sequencesA = a,b,c,d,e has many subsets.a, a,b, a,d,e, a,b,c,d,e, e, Ø, …The entire set and the empty set are subsets with all the rights and privileges pertaining thereto.Question: How many subsets can be formed from the elements of a 5-element set?a b c d e0 1 1 0 1b c b c ee1 means “TAKE IT”1 means “TAKE IT”0 means “LEAVE IT”0 means “LEAVE IT”Question: How many subsets can be formed from the elements of a 5-element set?a b c d e0 1 1 0 1Each subset corresponds to a Each subset corresponds to a 5-bit sequence (using the “take 5-bit sequence (using the “take it or
View Full Document