1/29/2009115-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?ABAB∪=+Addition RuleLet A and B be two disjoint finite setsAddition of Multiple Disjoint Sets:Let A1, A2, A3, …, Anbe disjoint, finite sets:A Ai ii=1nin==∑1∪Addition Rule(2 Possibly Overlapping Sets)Let A and B be two finite sets:|A| + |B| - |A∩B||A∪B| =1/29/20092Inclusion-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, …, Anare 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=1nin==∑1∪To 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 Method1/29/20093Ai≡ 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 disjointandS ∪ 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|?”1/29/20094S 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 B∀x,y∈A, x ≠ y ⇒ f(x) ≠ f(y)∀z∈B ∃x∈A 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-1is well-defined1/29/20095Correspondence 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 2nsequences.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 akin 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 strings1/29/20096The 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) iff∀z∈B ∃ exactly one x∈A such that f(x) = zf is a k to 1 correspondence iff∀z∈B ∃ exactly k x∈A 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?1/29/20097A 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 × 7 = 6306 × 7 × 4 × 8 = 1344How many ways to order a meal if I am allowed to skip some (or all) of the courses?Leaf Counting LemmaLet T be a depth-n tree when each node at depth 0 ≤ i ≤ n-1 has Pi+1childrenThe number of leaves of T is given by:P1P2…PnChoice TreeA choice tree is a rooted, directed tree with an object called a “choice” associated with each edge and a label on each leafA choice tree provides a “choice tree representation” of a set S, if1. Each leaf label is in S, and each element of S is some leaf label2. No two leaf labels are the sameWe will now combine the correspondence principle with the leaf counting lemma to make a powerful
View Full Document