Great Theoretical Ideas In Computer Science Anupam Gupta Lecture 6 CS 15 251 Sept 14 2006 Fall 2006 Carnegie Mellon University Counting I One To One Correspondence and Choice Trees How many seats in this auditorium Hint Count without counting 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 Suppose I roll a white die and a black die S Set of all outcomes where the dice show different values S S Set of all outcomes where the dice show different values S Ai set of outcomes where the 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 S T of outcomes 36 S T 36 S 36 6 30 T 6 S Set of all outcomes where the black die shows a smaller number than the white die S 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 A 1 A 2 A 3 A 4 A 5 A 6 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 Let s put each outcome in S in correspondence with an outcome in L by swapping the color of the dice S L Pinning down the idea of symmetry by exhibiting a correspondence Let s put each outcome in S in correspondence with an outcome in L by swapping the color of the dice Each outcome in S gets matched with exactly one outcome in L with none left over Thus S 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 B A 1 1 f A B A B A B onto f A B A B A 1 1 onto f A B A B B 1 1 onto Correspondence just correspondence for short A A B B Correspondence Principle If two finite sets can be placed into 1 1 onto correspondence then they have the same size 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 0 1 2 3 1 11111 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 formed from the elements of a 5 element set a 0 b 1 c 1 d 0 b c e e 1 1 means TAKE IT 0 means LEAVE IT Question How many subsets can be formed from the elements of a 5 element set a 0 b 1 c 1 d 0 e 1 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 Let s construct a correspondence f B A a a a 1 2 3 b b b a n b 1 bit 2 3 b For the string b1b2nb3 bn Let f b ai bi 1 a1 a2 a3 an b1 b2 b3 bn 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 a1 a2 a3 an b1 b2 b3 bn 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 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 Let f A B be a function from a set A to a set B f is a 1 to 1 correspondence iff z B exactly one x2A s t f x z f is a k to 1 correspondence iff z B exactly k elements x2A s t f x z 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 A restaurant has a menu with 5 appetizers 6 entrees 3 salads and 7 desserts 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 and 1 dessert 24 ways to order a meal if I might not have some of the courses Same as number of subsets of the set Appetizer Entr e Salad Dessert Choice Tree for 2n n bit sequences 0 0 0 1 1 1 0 0 1 0 1 1 0 We can use a choice tree to represent the construction of objects of the desired type 1 2n n bit sequences 0 0 0 1 000 001 1 1 0 0 1 010 011 0 1 100 101 1 0 1 110 111 Label each leaf with the object constructed by the choices along the path 0 0 0 1 1 1 0 …
View Full Document
Unlocking...