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 = ?S 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 14Let f:A®B be a function from a set A to a set B.Slide 16Let’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?S = a,b,c,d,e has many subsets.Question: How many subsets can be formed from the elements of a 5-element set?Slide 27S = a1, a2, a3,…, an b = b1b2b3…bnSlide 29Slide 30Slide 31Slide 32Slide 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.Leaf Counting LemmaChoice Tree for 2n n-bit sequences2n n-bit sequences2 choices for first bit X 2 choices for second bit X 2 choices for third bit … X 2 choices for the nthChoice TreeSlide 46Slide 47Product RuleSlide 49How many different orderings of deck with 52 cards?Slide 51A permutation or arrangement of n objects is an ordering of the objects.Slide 53Slide 54Slide 55A formalizationObject property Q on object space SSlide 58Slide 59If 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 62Ordered Versus UnorderedSlide 64Slide 65A combination or choice of r out of n objects is an (unordered) set of r of the n objects.Slide 67How many 8 bit sequences have 2 0’s and 6 1’s?Slide 69Symmetry in the formula:How many hands have at least 3 aces?Slide 72Slide 73Four different sequences of choices produce the same handSlide 75The Sleuth’s Criterion1) Choose 3 of 4 aces 2) Choose 2 of the remaining cardsSlide 781) Choose 3 of 4 aces 2) Choose 2 non-ace cards1) Choose 4 of 4 aces 2) Choose 1 non-aceSlide 81Counting I: One To One Correspondence and Choice Trees Great Theoretical Ideas In Computer ScienceJohn Lafferty CS 15-251 Fall 2005Lecture 6 Sept 15, 2005 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 36S T 36 T 6S 36 6 30 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.S + L = 30 It is clear by symmetry that S = L.Therefore S = 15It 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 correspondence with an outcome in L by in L by swapping swapping the color of the the color of the dice.dice.S LLet’s put each outcome in S in Let’s put each outcome in S in correspondence with an outcome correspondence with an outcome in L by in L by swappingswapping the color of the the color of the dice.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)f is onto if and only ifzB xA f(x) = zLet 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)f is onto if and only ifzB xA f(x) = zFor EveryThere ExistsLet’s restrict our attention to finite sets.A B 1-1 f:AB A BA B onto f:AB A BA B 1-1 onto f:AB A BA B1-1 Onto Correspondence(just “correspondence” for short)A 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-12n sequencesS = a,b,c,d,e has many subsets.a, a,b, a,d,e, a,b,c,d,e, e, Ø, …The empty set is a set 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 5-bit sequence (using the “take it or leave it” code)“take it or leave it” code)S = a1, a2, a3,…, an b = b1b2b3…bna1a2a3…anb1b2b3…bnf(b)
View Full Document
Unlocking...