15 251 Great Theoretical Ideas in Computer Science Counting I One To One Correspondence and Choice Trees Lecture 6 September 11 2008 2 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 3 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 3 Addition Rule 2 possibly overlapping sets Let A and B be two finite sets A B A B A B 4 Addition of multiple disjoint sets Let A1 A2 A3 An be disjoint finite sets 5 Partition Method To count the elements of a finite set S partition the elements into non overlapping subsets A1 A2 A3 An s 6 Partition Method S all possible outcomes of one white die and one black die 7 Partition Method S all possible outcomes of one white die and one black die Partition S into 6 sets 8 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 8 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 8 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 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 8 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 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 sets has size 6 36 outcomes 8 Partition Method S all possible outcomes where the white die and the black die have different values 9 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 10 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 10 S Set of all outcomes where the dice show different values S 11 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 11 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 11 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 11 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 11 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 11 S Set of all outcomes where the black die shows a smaller number than the white die S 12 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 12 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 12 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 12 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 13 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 13 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 13 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 13 It is clear by symmetry that S L 14 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 15 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 Each outcome in S gets matched with exactly one outcome in L with none left over 15 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 Each outcome in S gets matched with exactly one outcome in L with none left over Thus S L 15 Let f A B Be a Function From a Set A to a Set B f is 1 1 if and only if …
View Full Document
Unlocking...