15 251 Great Theoretical Ideas in Computer Science Counting I One To One Correspondence and Choice Trees Lecture 6 September 13 2007 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 The size of A B is the sum of the size of A and the size of B A B A B Addition Rule 2 possibly overlapping sets Let A and B be two finite sets A B 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 Partition Method To count the elements of a finite set S partition the elements into non overlapping subsets A1 A2 A3 An s 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 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 Each of 6 disjoint set have size 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 6 6 i 1 i 1 i 1 S A i A i 5 30 S Set of all outcomes where the dice show different values S T set of outcomes where dice agree 1 1 2 2 3 3 4 4 5 5 6 6 S T of outcomes 36 S T 36 T 6 S 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 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 1 1 if and only if x y A x y f x f y f is onto 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 1 1 f A B A B B A onto f A B A B A 1 1 onto f A B A B B f being 1 1 onto means f 1 is well defined and unique f is a way of pairing up elements A B Correspondence Principle If 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 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 A 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 A a1 a2 a3 an 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 1 1 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 A a1 a2 a3 an 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 onto Let S be a subset of a1 an Define bk 1 if ak in S and bk 0 otherwise Note that f b1b2 bn S 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 1 1 if and only if x y A x y f x f y f is onto if and only if z B x A such that f x z Let f A B Be a Function From Set A to Set B f is a 1 to 1 correspondence 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 How many seats in this auditorium Count without Counting The auditorium can be partitioned into n rows with k seats each Thus we have nk seats in the room 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 Hobson s Restaurant Has Only 1 Appetizer 1 Entree 1 Salad …
View Full Document
Unlocking...