This preview shows page 1-2-3-4-5-6-7-8-9-10-67-68-69-70-71-72-73-74-75-136-137-138-139-140-141-142-143-144-145 out of 145 pages.
15-251Great Theoretical Ideas in Computer ScienceLecture 6, September 11, 2008Counting I: One-To-One Correspondence and Choice Trees2Addition 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 B3Addition 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 B3Addition Rule(2 possibly overlapping sets)Let A and B be two finite sets|A∪B| = |A| + |B| - |A∩B|4Addition of multiple disjoint sets:Let A1, A2, A3, …, An be disjoint, finite sets.5Partition MethodTo count the elements of a finite set S, partition the elements into non-overlapping subsets A1, A2, A3, …, An .. |s| =6S = all possible outcomes of one white die and one black die.Partition Method7S = all possible outcomes of one white die and one black die.Partition S into 6 sets:Partition Method8S = 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.8S = 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. 8S = 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.8S = 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 has size 6 = 36 outcomes 8S = all possible outcomes where the white die and the black die have different values Partition Method9Ai ≡ set of outcomes where black die says i and the white die says something else.S ≡ Set of all outcomes where the dice show different values. S = ?10Ai ≡ set of outcomes where black die says i and the white die says something else.S ≡ Set of all outcomes where the dice show different values. S = ?10S ≡ Set of all outcomes where the dice show different values. S = ?11S ≡ 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 ∪ T | = # of outcomes = 36S ≡ 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 ∪ T | = # of outcomes = 36|S| + |T| = 36S ≡ 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 ∪ T | = # of outcomes = 36|S| + |T| = 36|T| = 6S ≡ 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 ∪ 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>}11S ≡ Set of all outcomes where the black die shows a smaller number than the white die. S = ?12S ≡ 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.12S ≡ 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 ∪ A612S ≡ 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 = 1512S ≡ 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.13S + L = 30S ≡ 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.13It is clear by symmetry that | S | = | L |.S + L = 30S ≡ 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.13It 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.13“It is clear by symmetry that |S| = |L|?”14S 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.15S 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.Each outcome in S gets matched with exactly one outcome in L, with none left over.15S 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.15f is 1-1 if and only if & & ∀x,y∈A, x ≠ y ⇒ f(x) ≠ f(y)For EveryThere Existsf is onto if and only if &∀z∈B ∃x∈A f(x) = zLet f : A → B Be a Function From a Set …
View Full Document