15 251 Great Theoretical Ideas in Computer Science Counting I One To One Correspondence and Choice Trees Lecture 6 January 29 2009 If I have 14 teeth on the top and 12 teeth on the bottom how many teeth do I have in all 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 i 1 i 1 A A i i Addition Rule 2 Possibly Overlapping Sets Let A and B be two finite sets A B A B A B 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 Inclusion Exclusion 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 To count the elements of a finite set S partition the elements into non overlapping subsets A1 A2 A3 An n n i 1 i 1 A A i i Partition Method S all possible outcomes of one white die and one black die Partition Method S all possible outcomes of one white die and one black die Partition S into 6 sets A1 the A2 the A3 the A4 the A5 the A6 the Each of set of outcomes where set of outcomes where set of outcomes where set of outcomes where set of outcomes where set of outcomes where 6 disjoint set have size the white die is 1 the white die is 2 the white die is 3 the white die is 4 the white die is 5 the white die is 6 6 36 outcomes Partition Method S all possible outcomes where the white die and the black die have different values 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 Ai i 1 5 30 i 1 S Set of all outcomes where the dice show different values S B set of outcomes where dice agree S B of outcomes 36 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 then 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 15 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 15 It is clear by symmetry that S L 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 Each outcome in S gets matched with exactly one outcome in L with none left over Thus S L 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 For Every Let s Restrict Our Attention to Finite Sets A B injective 1 1 f A B A B A B surjective onto f A B A B A B bijective f A B A B A bijective f means the inverse f 1 is well defined bijective f A B A B B Correspondence Principle If two finite sets can be placed into bijection 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 000001 000010 000011 111111 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 a a b a d e a b c d e e The entire set and the empty set are subsets with all the rights and privileges pertaining thereto Question How Many Subsets Can Be Made From The Elements of a 5 Element Set 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 b1 b2 b3 b4 b5 For bit string b b1b2b3 bn let f b ai bi 1 Claim f is injective Any two distinct binary sequences b and b have a position i at which they differ Hence f b is not equal to f b because they disagree on element ai S a1 a2 a3 an T all subsets of S B set of all n bit strings a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 For bit string b b1b2b3 bn let f b ai bi 1 Claim f is surjective 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 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 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 How many ways to order a meal if I am allowed to skip some or all of the courses 6 7 4 8 1344 Leaf Counting Lemma Let T be a depth n tree when each node at depth 0 i n 1 has Pi 1 children The …
View Full Document
Unlocking...