Slide 1Slide 2If I have 14 teeth on the top and 12 teeth on the bottom, how many teeth do I have in all?Slide 4Addition of Multiple Disjoint Sets:Slide 6Inclusion-ExclusionSlide 8Partition MethodSlide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 7815-251Great Theoretical Ideas in Computer ScienceLecture 6 (January 29, 2009)Counting I: One-To-One Correspondence and Choice TreesIf I have 14 teeth on the top and 12 teeth on the bottom, how many teeth do I have in all?A B A B Addition RuleLet A and B be two disjoint finite setsAddition of Multiple Disjoint Sets:Let A1, A2, A3, …, An be disjoint, finite sets:A Ai ii=1nin1Addition Rule(2 Possibly Overlapping Sets)Let A and B be two finite sets:|A| + |B| - |AB||AB| =Inclusion-ExclusionIf A, B, C are three finite sets, what is the size of (A B C) ?|A| + |B| + |C| - |A B| - |A C| - |B C| + |A B C|Inclusion-ExclusionIf A1, A2, …, An are n finite sets, what is the size of (A1 A2 … An) ?∑i |Ai| - ∑i < j |Ai Aj| + ∑i < j < k |Ai Aj Ak| … + (-1)n-1 |A1 A2 … An|Partition MethodA Ai ii=1nin1To count the elements of a finite set S, partition the elements into non-overlapping subsets A1, A2, A3, …, An.S = all possible outcomes of one white die and one black die.Partition MethodEach of 6 disjoint set have size 6 = 36 outcomesPartition S into 6 sets:S = all possible outcomes of one white die and one black die.Partition MethodA1 = the set of outcomes where the white die is 1.A2 = the set of outcomes where the white die is 2. A3 = the set of outcomes where the white die is 3.A4 = the set of outcomes where the white die is 4.A5 = the set of outcomes where the white die is 5. A6 = the set of outcomes where the white die is 6.S = all possible outcomes where the white die and the black die have different values Partition MethodAi set of outcomes where black die says i and the white die says something else.S Set of all outcomes where the dice show different values. S = ?| S | =i = 16| Ai |=i = 165= 30| S B | = # of outcomes = 36|S| + |B| = 36|B| = 6|S| = 36 – 6 = 30B set of outcomes where dice agree.S Set of all outcomes where the dice show different values. S = ?Difference MethodTo count the elements of a finite set S, find two sets A and B such that S and B are disjointand S B = Athen |S| = |A| - |B|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 = A1 A2 A3 A4 A5 A6|S| = 5 + 4 + 3 + 2 + 1 + 0 = 15It is clear by symmetry that | S | = | L |.S + L = 30Therefore | S | = 15S 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 LPinning Down the Idea of Symmetry by Exhibiting a CorrespondencePut each outcome in S in correspondence with an outcome in L by swapping color of the dice.Thus: S = LEach outcome in S gets matched with exactly one outcome in L, with none left over.f is injective if and only ifFor EveryThere Existsf is surjective if and only ifLet f : A B Be a Function From a Set A to a Set Bx,yA, xyf(x)f(y)zB xA f(x) = zA BLet’s Restrict Our Attention to Finite Sets injective (1-1) f : A B | A | ≤ | B |BA surjective (onto) f : A B | A | ≥ | B |AB bijective f : A B | A | = | B |AB bijective f : A B | A | = | B |bijective f means theinverse f-1 is well-definedCorrespondence PrincipleIf two finite sets can be placed into bijection, then they have the same sizeIt’s one of the most important mathematical ideas of all time!Each sequence corresponds to a uniquenumber from 0 to 2n-1. Hence 2n sequences.Question: How many n-bit sequences are there?000000000001000010000011111111 2n-1::0123:The entire set and the empty set are subsets with all the rights and privileges pertaining theretoS = { a,b,c,d,e } has Many Subsets{a}, {a,b}, {a,d,e}, {a,b,c,d,e}, {e}, Ø, …Question: How Many Subsets Can Be Made From The Elements of a 5-Element Set?{ b c e }1 means “TAKE IT”0 means “LEAVE IT”a b c d e0 1 1 0 1Each subset corresponds to a 5-bit sequence (using the “take it or leave it” code)For bit string b = b1b2b3…bn, let f(b) = { ai | bi=1} S = {a1, a2, a3,…, an}, T = all subsets of SB = set of all n-bit stringsa1a2a3a4a5b1b2b3b4b5Claim: f is injectiveAny two distinct binary sequences b and b have a position i at which they differHence, f(b) is not equal to f(b) because they disagree on element aiFor bit string b = b1b2b3…bn, let f(b) = { ai | bi=1} a1a2a3a4a5b1b2b3b4b5Let X be a subset of {a1,…,an}.Define bk = 1 if ak in X and bk = 0 otherwise.Note that f(b1b2…bn) = X.Claim: f is surjectiveS = {a1, a2, a3,…, an}, T = all subsets of SB = set of all n-bit stringsThe number of subsets of an n-element set is 2nLet f : A B Be a Function From Set A to Set Bf is a 1 to 1 correspondence (bijection) iffzB exactly one xA such that f(x) = zf is a k to 1 correspondence iffzB exactly k xA such that f(x) = zAB3 to 1 functionTo count the number of horses in a barn, we can count the number of hoofs and then divide by 4If a finite set A has a k-to-1 correspondence to finite set B, then |B| = |A|/kI own 3 beanies and 2 ties. How many different ways can I dress up in a beanie and a tie?A Restaurant Has a Menu With5 Appetizers, 6 Entrees, 3 Salads, and 7 DessertsHow many items on the menu?5 + 6 + 3 + 7 = 21How many ways to choose a complete meal?5 × 6 × 3 × …
View Full Document