Slide 1Slide 2If I have 14 teeth on the top and 12 teeth on the bottom, how many teeth do I have in all?Slide 4Slide 5Addition of multiple disjoint sets:Partition MethodSlide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21f 1-1 onto means f^{-1) is unique f is a way of pairing up elementsSlide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77COMPSCI 102Introduction to Discrete MathematicsLecture 6 (September 17, 2007)Counting I: One-To-One Correspondence and Choice TreesIf I have 14 teeth on the top and 12 teeth on the bottom, how many teeth do I have in all?A B A B Addition RuleLet A and B be two disjoint finite setsThe size of (A B) is the sum of the size of A and the size of BAddition Rule(2 possibly overlapping sets)Let A and B be two finite sets|AB| = |A| + |B| - |AB|Addition of multiple disjoint sets:Let A1, A2, A3, …, An be disjoint, finite sets.A Ai ii=1nin1Partition MethodTo count the elements of a finite set S, partition the elements into non-overlapping subsets A1, A2, A3, …, An .. |s| =A Ai ii=1nin1S = all possible outcomes of one white die and one black die.Partition MethodS = all possible outcomes of one white die and one black die.Partition S into 6 sets:Partition MethodA1 = 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 sets have size 6 = 36 outcomesS = all possible outcomes where the white die and the black die have different values Partition MethodAi set of outcomes where black die says i and the white die says something else.S A A 5 30i ii=1 i=1 i 16 6 6S Set of all outcomes where the dice show different values. S = ?| S T | = # of outcomes = 36|S| + |T| = 36|T| = 6|S| = 36 – 6 = 30S 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>}How many seats in this auditorium?Count without Counting:The auditorium can bePartitioned into n rows with k seats eachThus, we have nk seat in the roomS 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 = 15It is clear by symmetry that | S | = | L |.S + L = 30Therefore | S | = 15S 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.“It is clear by symmetry that |S| = |L|?”S LPinning Down the Idea of Symmetry by Exhibiting a CorrespondencePut each outcome in S in correspondence with an outcome in L by swapping color of the dice.Thus: S = LEach outcome in S gets matched with exactly one outcome in L, with none left over.f is 1-1 if and only ifx,yA, xyf(x)f(y)For EveryThere Existsf is onto if and only ifzB xA f(x) = zLet f : A B Be a Function From a Set A to a Set BA BLet’s Restrict Our Attention to Finite Sets 1-1 f : A B | A | ≤ | B |BA onto f : A B | A | ≥ | B |AB 1-1 onto f : A B | A | = | B |f 1-1 onto means f^{-1) is uniquef is a way of pairing up elementsA BCorrespondence PrincipleIf two finite sets can be placed into 1-1 onto correspondence, then they have the same sizeIt’s one of the most important mathematical ideas of all time!Each sequence corresponds to a uniquenumber from 0 to 2n-1. Hence 2n sequences.Question: How many n-bit sequences are there?000000000001000010000011111111 2n-1::0123:The entire set and the empty set are subsets with all the rights and privileges pertaining theretoA = { a,b,c,d,e } Has Many Subsets{a}, {a,b}, {a,d,e}, {a,b,c,d,e}, {e}, Ø, …Question: How Many Subsets Can Be Made From The Elements of a 5-Element Set?{ b c e }1 means “TAKE IT”0 means “LEAVE IT”a b c d e0 1 1 0 1Each subset corresponds to a 5-bit sequence (using the “take it or leave it” code)For bit string b = b1b2b3…bn, let f(b) = { ai | bi=1} A = {a1, a2, a3,…, an}B = set of all n-bit stringsa1a2a3a4a5b1b2b3b4b5Claim: f is 1-1Any two distinct binary sequences b and b have a position i at which they differHence, f(b) is not equal to f(b) because they disagree on element aiFor bit string b = b1b2b3…bn, let f(b) = { ai | bi=1} A = {a1, a2, a3,…, an}B = set of all n-bit stringsa1a2a3a4a5b1b2b3b4b5Let S be a subset of {a1,…,an}.Define bk = 1 if ak in S and bk = 0 otherwise.Note that f(b1b2…bn) = S.Claim: f is ontoThe number of subsets of an n-element set is 2nLet f : A B Be a Function From Set A to Set Bf is 1-1 if and only if x,y A, x y f(x) f(y)f is onto if and only if zB xA such that f(x) = zLet f : A B Be a Function From Set A to Set Bf is a 1 to 1 correspondence iffzB exactly one xA such that f(x) = zf is a k to 1 correspondence iffzB exactly k xA such that f(x) = zAB3 to 1 functionTo count the number of horses in a barn, we can count the number of hoofs and then divide by 4If a finite set A has a k-to-1 correspondence to finite set B, then |B| = |A|/kI 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 With5 Appetizers, 6 Entrees, 3 Salads, and 7 DessertsHow many items on the menu?5 + 6 + 3 + 7 = 21How many ways to choose a complete meal?5 × 6 × 3 × 7 = 6306 × 7 × 4 × 8 = 1344How many ways to order a meal if I am allowed to skip some (or all) of the courses?Hobson’s Restaurant Has Only 1 …
View Full Document
Unlocking...