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.Slide 34Leaf 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 nthSlide 39Slide 40Slide 41Product RuleSlide 43How many different orderings of deck with 52 cards?Slide 45A permutation or arrangement of n objects is an ordering of the objects.Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57If 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 60Ordered Versus UnorderedSlide 62A combination or choice of r out of n objects is an (unordered) set of r of the n objects.Slide 64How many 8 bit sequences have 2 0’s and 6 1’s?Slide 66Symmetry in the formula:How many hands have at least 3 aces?Slide 69Slide 70Four different sequences of choices produce the same handSlide 72The Sleuth’s Criterion1) Choose 3 of 4 aces 2) Choose 2 of the remaining cardsSlide 751) 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 79Counting 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 A B 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, eb c, e1 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 corresponds to a 5-bit sequence sequenceS = a1, a2, a3,…, an b = b1b2b3…bna1a2a3…anb1b2b3…bnf(b) = ai | bi=1
View Full Document
Unlocking...