1 29 2009 15 251 Great Theoretical Ideas in Computer Science If I have 14 teeth on the top and 12 teeth on the bottom how many teeth do I have in all Counting I One To One Correspondence and Choice Trees Lecture 6 January 29 2009 Addition Rule Let A and B be two disjoint finite sets A B A B Addition of Multiple Disjoint Sets Let A1 A2 A3 An be disjoint finite sets n n A i 1 i Ai Addition Rule 2 Possibly Overlapping Sets Let A and B be two finite sets A B A B A B i 1 1 1 29 2009 Inclusion Exclusion If 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 Partition Method To count the elements of a finite set S partition the elements into non overlapping subsets A1 A2 A3 An If 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 Method S all possible outcomes of one white die and one black die n n A i i 1 Ai i 1 Partition Method S all possible outcomes of one white die and one black die Partition S into 6 sets A1 the set of A2 the set of A3 the set of A4 the set of A5 the set of A6 the set of Inclusion Exclusion Partition Method S all possible outcomes where the white die and the black die have different values outcomes where the white die is 1 outcomes where the white die is 2 outcomes where the white die is 3 outcomes where the white die is 4 outcomes where the white die is 5 outcomes where the white die is 6 Each of 6 disjoint set have size 6 36 outcomes 2 1 29 2009 S Set of all outcomes where the dice show different values S Ai set of outcomes where black die says i and the white die says something else 6 S 6 A 5 30 S Set of all outcomes where the dice show different values S B set of outcomes where dice agree S B of outcomes 36 i i 1 i 1 S B 36 B 6 S 36 6 30 Difference Method To count the elements of a finite set S find two sets A and B such that S and B are disjoint and S B A 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 then S A B S Set of all outcomes where the black die shows a smaller number than the white die S S 5 4 3 2 1 0 15 It is clear by symmetry that S L 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 15 3 1 29 2009 Pinning Down the Idea of Symmetry by Exhibiting a Correspondence Put each outcome in S in correspondence with an outcome in L by swapping color of the dice S L Let f A B Be a Function From a Set A to a Set B f is injective if and only if x y A x y f x f y f is surjective if and only if z B x A f x z There Exists Each outcome in S gets matched with exactly one outcome in L with none left over For Every Thus S L Let s Restrict Our Attention to Finite Sets A A B B injective 1 1 f A B A B A B bijective f A B A B surjective onto f A B A B A bijective f means the inverse f 1 is well defined B bijective f A B A B 4 1 29 2009 Correspondence Principle Question How many n bit sequences are there If two finite sets can be placed into bijection then they have the same size 000000 000001 000010 000011 111111 It s one of the most important mathematical ideas of all time Question How Many Subsets Can Be Made From The Elements of a 5 Element Set a a b a d e a b c d e e S a1 a2 a3 an T all subsets of S B set of all n bit strings 0 1 2 3 2n 1 Each sequence corresponds to a unique number from 0 to 2n 1 Hence 2n sequences S a b c d e has Many Subsets The entire set and the empty set are subsets with all the rights and privileges pertaining thereto a b c d e 0 1 1 0 1 b c e 1 means TAKE IT 0 means LEAVE IT Each subset corresponds to a 5 bit sequence using the take it or leave it code S a1 a2 a3 an T all subsets of S B set of all n bit strings a1 a2 a3 a4 a5 a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 b1 b2 b3 b4 b5 For bit string b b1b2b3 bn let f b ai bi 1 For bit string b b1b2b3 bn let f b ai bi 1 Claim f is injective Claim f is surjective Any two distinct binary sequences b and b have a position i at which they differ Let X be a subset of a1 an Define bk 1 if ak in X and bk 0 otherwise Note that f b1b2 bn X Hence f b is not equal to f b because they disagree on element ai 5 1 29 2009 The number of subsets of an n element set is 2n Let f A B Be a Function From Set A to Set B f is a 1 to 1 correspondence bijection iff z B exactly one x A such that f x z f is a k to 1 correspondence iff z B exactly k x A such that f x z A B 3 to 1 function To count the number of horses in a barn we can count the number of hoofs and then divide by 4 If a finite set A has a k to 1 correspondence to finite set B then B A k I own 3 beanies and 2 ties How many different ways can I dress up in a beanie and a tie 6 1 29 2009 A Restaurant Has a Menu With 5 Appetizers 6 Entrees 3 Salads and 7 Desserts How many items on the menu 5 6 3 7 21 How many ways to choose a complete meal 5 6 3 7 630 Leaf Counting Lemma Let T be a depth n tree when each node at depth 0 i n 1 has Pi 1 …
View Full Document
Unlocking...