Counting I: One To One Correspondence and Choice TreesSlide 2If I have 14 teeth on the top and 12 teeth on the bottom, how many teeth do I have in all?Addition RuleCorollary (by induction)Suppose I roll a white die and a black die.S Set of all outcomes where the dice show different values. S = ?Slide 8S 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 13Let f:A®B be a function from a set A to a set B.Slide 15Let’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 22Question: 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 26S = a1, a2, a3,…, an b = b1b2b3…bnSlide 28Slide 29Slide 30Slide 31Slide 32A 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 41Slide 42Product RuleSlide 44How many different orderings of deck with 52 cards?Slide 46A permutation or arrangement of n objects is an ordering of the objects.Slide 48Slide 49Slide 50A formalizationObject property QSlide 53Slide 54If 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 57Ordered Versus UnorderedSlide 59A combination or choice of r out of n objects is an (unordered) set of r of the n objects.Slide 61How many 8 bit sequences have 2 0’s and 6 1’s?Slide 63Symmetry in the formula:How many hands have at least 3 aces?Slide 66Slide 67Four different sequences of choices produce the same handSlide 69The Sleuth’s Criterion1) Choose 3 of 4 aces 2) Choose 2 of the remaining cardsSlide 721) Choose 3 of 4 aces 2) Choose 2 non-ace cards1) Choose 4 of 4 aces 2) Choose 1 non-aceHow many shortest routes from A to B?Slide 76Counting I: One To One Correspondence and Choice Trees Great Theoretical Ideas In Computer ScienceSteven RudichCS 15-251 Spring 2004Lecture 9 Feb 10, 2004 Carnegie Mellon UniversityHow many seats in this auditorium?Hint: Count without counting!If I have 14 teeth on the top and 12 teeth on the bottom, how many teeth do I have in all?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 Corollary (by induction)Let A1, A2, A3, …, An be disjoint, finite sets.A Ai ii=1nin1Suppose I roll a white die and a black die.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 Each subset corresponds to a 5-bit
View Full Document