18.05 S22 Class 1: Counting and Sets

Counting and Sets Class 1, 18.05 1 Learning Goals 1. Know the definitions and notation for sets, intersection, union, complement. 2. Be able to visualize set operations using Venn diagrams. 3. Understand how counting is used computing probabilities. 4. Be able to use the rule of product, inclusion-exclusion principle, permutations and combinations to count the elements in a set. 2 Counting 2.1 Motivating questions Example 1. A coin is fair if it comes up heads or tails with equal probability. You flip a fair coin three times. What is the probability that exactly one of the flips results in a head? Solution: With three flips, we can easily list the eight possible outcomes: {𝑇 𝑇 𝑇 , 𝑇 𝑇 𝐻, 𝑇 𝐻𝑇 , 𝑇 𝐻𝐻, 𝐻𝑇 𝑇 , 𝐻𝑇 𝐻, 𝐻𝐻𝑇 , 𝐻𝐻𝐻} Three of these outcomes have exactly one head: {𝑇 𝑇 𝐻, 𝑇 𝐻𝑇 , 𝐻𝑇 𝑇 } Since all outcomes are equally probable, we have 𝑃 (1 head in 3 flips) = number of outcomes with 1 head 3 = . total number of outcomes 8 Think: Would listing the outcomes be practical with 10 flips? A deck of 52 cards has 13 ranks (2, 3, … , 9, 10, J, Q, K, A) and 4 suits (♡, ♠, ♢, ♣,). A poker hand consists of 5 cards. A one-pair hand consists of two cards having one rank and three cards having three other ranks, e.g., {2♡, 2♠, 5♡, 8♣, K♢} Test your intuition: the probability of a one-pair hand is: (a) less than 5% (b) between 5% and 10% (c) between 10% and 20% (d) between 20% and 40% (e) greater than 40% 1 18.05 Class 1, Counting and Sets, Spring 2022 2 At this point we can only guess the probability. One of our goals is to learn how to compute it exactly. To start, we note that since every set of five cards is equally probable, we can compute the probability of a one-pair hand as 𝑃 (one-pair) = number of one-pair hands total number of hands So, to find the exact probability, we need to count the number of elements in each of these sets. And we have to be clever about it, because there are too many elements to simply list them all. We will come back to this problem after we have learned some counting techniques. Several times already we have noted that all the possible outcomes were equally probable and used this to find a probability by counting. Let’s state this carefully in the following principle. Principle: Suppose there are 𝑛 possible outcomes for an experiment and each is equally probable. If there are 𝑘 desirable outcomes then the probability of a desirable outcome is 𝑘/𝑛. Of course we could replace the word desirable by any other descriptor: undesirable, funny, interesting, remunerative, … Concept question: equally probable? Can you think of a scenario where the possible outcomes are not Here’s one scenario: on an exam you can get any score from 0 to 100. That’s 101 different possible outcomes. Is the probability you get less than 50 equal to 50/101? 2.2 Sets and notation Our goal is to learn techniques for counting the number of elements of a set, so we start with a brief review of sets. (If this is new to you, please come to office hours). 2.2.1 Definitions A set 𝑆 is a collection of elements. We use the following notation. Element: We write 𝑥 ∈ 𝑆 to mean the element 𝑥 is in the set 𝑆. Subset: We say the set 𝐴 is a subset of 𝑆 if all of its elements are in 𝑆. We write this as 𝐴 ⊂ 𝑆. Complement:: The complement of 𝐴 in 𝑆 is the set of elements of 𝑆 that are not in 𝐴. We write this as 𝐴𝑐 or 𝑆 − 𝐴. Union: The union of 𝐴 and 𝐵 is the set of all elements in 𝐴 or 𝐵 (or both). We write this as 𝐴 ∪ 𝐵. Intersection: The intersection of 𝐴 and 𝐵 is the set of all elements in both 𝐴 and 𝐵. We write this as 𝐴 ∩ 𝐵. Empty set: The empty set is the set with no elements. We denote it ∅. Disjoint: 𝐴 and 𝐵 are disjoint if they have no common elements. That is, if 𝐴 ∩ 𝐵 = ∅. Difference: The difference of 𝐴 and 𝐵 is the set of elements in 𝐴 that are not in 𝐵. We write this as 𝐴 − 𝐵. 18.05 Class 1, Counting and Sets, Spring 2022 3 Let’s illustrate these operations with a simple example. Example 2. Start with a set of 10 animals 𝑆 = {Antelope, Bee, Cat, Dog, Elephant, Frog, Gnat, Hyena, Iguana, Jaguar}. Consider two subsets: 𝑀 = the animal is a mammal = {Antelope, Cat, Dog, Elephant, Hyena, Jaguar} 𝑊 = the animal lives in the wild = {Antelope, Bee, Elephant, Frog, Gnat, Hyena, Iguana, Jaguar}. Our goal here is to look at different set operations. Intersection: 𝑀 ∩ 𝑊 contains all wild mammals: 𝑀 ∩ 𝑊 = {Antelope, Elephant, Hyena, Jaguar}. Union: 𝑀 ∪ 𝑊 contains all animals that are mammals or wild (or both). 𝑀 ∪ 𝑊 = {Antelope, Bee, Cat, Dog, Elephant, Frog, Gnat, Hyena, Iguana, Jaguar}. Complement: 𝑀 𝑐 means everything that is not in 𝑀 , i.e. not a mammal. 𝑀 𝑐 = {Bee, Frog, Gnat, Iguana}. Difference: 𝑀 − 𝑊 means everything that’s in 𝑀 and not in 𝑊 . So, 𝑀 − 𝑊 = {Cat, Dog}. There are often many ways to get the same set, e.g. 𝑀 𝑐 = 𝑆 − 𝑀 , 𝑀 − 𝑊 = 𝑀 ∩ 𝑊 𝑐. The relationship between union, intersection, and complement is given by DeMorgan’s laws: (𝐴 ∪ 𝐵)𝑐 = 𝐴𝑐 ∩ 𝐵𝑐 (𝐴 ∩ 𝐵)𝑐 = 𝐴𝑐 ∪ 𝐵𝑐 In words the first law says everything not in (𝐴 or 𝐵) is the same set as everything that’s (not in 𝐴) and (not in 𝐵). The second law is similar. 2.2.2 Venn Diagrams Venn diagrams offer an easy way to visualize set operations. In all the figures 𝑆 is the region inside the large rectangle, 𝐿 is the region inside the left circle and 𝑅 is the region inside the right circle. The shaded region shows the set indicated underneath each figure. 𝑆 𝐿 𝐿∪𝑅 𝐿∩𝑅 𝑅 𝐿𝑐 𝐿−𝑅 18.05 Class 1, Counting and Sets, Spring 2022 4 Proof of DeMorgan’s Laws (𝐿 ∪ 𝑅)𝑐 𝐿𝑐 𝑅𝑐 𝐿𝑐 ∩ 𝑅𝑐 (𝐿 ∩ 𝑅)𝑐 𝐿𝑐 𝑅𝑐 𝐿𝑐 ∪ 𝑅𝑐 Example 3. Verify DeMorgan’s laws for the subsets 𝐴 = {1, 2, 3} and 𝐵 = {3, 4} of the set 𝑆 = {1, 2, 3, 4, 5}. Solution: For each law we just work through both sides of the equation and show they are the same. 1. (𝐴 ∪ 𝐵)𝑐 = 𝐴𝑐 ∩ 𝐵𝑐 : Right hand side: 𝐴 ∪ 𝐵 = {1, 2, 3, 4} ⇒ (𝐴 ∪ 𝐵)𝑐 = {5}. Left hand side: 𝐴𝑐 = {4, 5}, 𝐵𝑐 = {1, 2, 5} ⇒ 𝐴𝑐 ∩ 𝐵𝑐 = {5}. The two sides are equal. QED 2. (𝐴 ∩ 𝐵)𝑐 = 𝐴𝑐 ∪ 𝐵𝑐 : Right hand side: 𝐴 ∩ 𝐵 = {3} ⇒ (𝐴 ∩ 𝐵)𝑐 = {1, 2, 4, 5}. Left hand side: 𝐴𝑐 = {4, 5}, 𝐵𝑐 = {1, 2, 5} ⇒ 𝐴𝑐 ∪ 𝐵𝑐 = {1, 2, 4, 5}. The two sides are equal. QED Think: Draw and label a Venn diagram with 𝐴 the set of Brain and Cognitive Science majors and 𝐵 the set of sophomores. Shade the region illustrating the first law. Can you express the first law in this case as a non-technical English sentence? 2.2.3 Products of sets The product of sets 𝑆 and 𝑇 is the set of ordered pairs: 𝑆 × 𝑇 = {(𝑠, 𝑡) | 𝑠 ∈ 𝑆, 𝑡 ∈ 𝑇 }. In words the right-hand side reads “the set of ordered pairs (𝑠, 𝑡) such that 𝑠 is in 𝑆 and 𝑡 is in 𝑇 . The following diagrams show two examples of the set product. 18.05 Class 1, Counting and Sets, Spring 2022 5 4 × 1 2 3 1 (1,1) (2,1) (3,1) 2 (1,2) (2,2) (3,2) 3 (1,3) (2,3) (3,3) 4 (1,4) (2,4) (3,4) 3 1 {1, 2, 3} × {1, 2, 3, 4} 1 4 5 [1, 4] × [1, 3] ⊂ [0, 5] × [0, 4] The right-hand figure also illustrates that if 𝐴 ⊂ 𝑆 and 𝐵 ⊂ 𝑇 then 𝐴 × 𝐵 ⊂ 𝑆 × 𝑇 . 2.3 Counting If 𝑆 is finite, we use |𝑆| or #𝑆 to denote the number of elements of 𝑆. Two useful counting principles are the inclusion-exclusion principle and the rule of product. 2.3.1 Inclusion-exclusion principle The inclusion-exclusion principle says |𝐴 ∪ 𝐵| = |𝐴| + |𝐵| − |𝐴 ∩ 𝐵|. We can illustrate this with a Venn diagram. 𝑆 is all the dots, 𝐴 is the dots in the blue circle, and 𝐵 is the dots in the red circle. 𝑆 𝐵 𝐴∩𝐵 𝐴 |𝐴| is the number of dots in 𝐴 and likewise for the other sets. The figure shows that |𝐴|+|𝐵| double-counts |𝐴 ∩ 𝐵|, which is why |𝐴 ∩ 𝐵| is subtracted off in the inclusion-exclusion formula. Example 4. In a band of singers and guitarists, seven people sing, four play the guitar, and two do both. How big is the band? 18.05 Class 1, Counting and Sets, Spring 2022 6 Solution: Let 𝑆 be the set singers and 𝐺 be the set guitar players. The inclusion-exclusion principle says size of band = |𝑆 ∪ 𝐺| = |𝑆| + |𝐺| − |𝑆 ∩ 𝐺| = 7 + 4 − 2 = 9. 2.3.2 Rule of Product The Rule of Product says: If there are 𝑛 ways to perform action 1 and then by 𝑚 ways to perform action 2, then there are 𝑛 ⋅ 𝑚 ways to perform action 1 followed by action 2. We will also call this the multiplication rule. Example 5. If you have 3 shirts and 4 pants then you can make 3 ⋅ 4 = 12 outfits. Think: An extremely important point is that the rule of product holds even if the ways to perform action 2 depend on action 1, as long as the number of ways to perform action 2 is independent of action 1. To illustrate this: Example 6. There are 5 competitors in the 100m final at the Olympics. In how many ways can the gold, silver, and bronze medals be awarded? Solution: There are 5 ways to award the gold. Once that is awarded there are 4 ways to award the silver and then 3 ways to award the bronze: answer 5 ⋅ 4 ⋅ 3 = 60 ways. Note that the choice of gold medalist affects who can win the silver, but the number of possible silver medalists is always four. 2.4 2.4.1 Permutations and combinations Permutations A permutation of a set is a particular ordering of its elements. For example, the set {𝑎, 𝑏, 𝑐} has six permutations: 𝑎𝑏𝑐, 𝑎𝑐𝑏, 𝑏𝑎𝑐, 𝑏𝑐𝑎, 𝑐𝑎𝑏, 𝑐𝑏𝑎. We found the number of permutations by listing them all. We could also have found the number of permutations by using the rule of product. That is, there are 3 ways to pick the first element, then 2 ways for the second, and 1 for the third. This gives a total of 3 ⋅ 2 ⋅ 1 = 6 permutations. In general, the rule of product tells us that the number of permutations of a set of 𝑘 elements is 𝑘! = 𝑘 ⋅ (𝑘 − 1) ⋯ 3 ⋅ 2 ⋅ 1. We also talk about the permutations of 𝑘 things out of a set of 𝑛 things. We show what this means with an example. Example 7. List all the permutations of 3 elements out of the set {𝑎, 𝑏, 𝑐, 𝑑}. Solution: This is a longer list, 𝑎𝑏𝑐 𝑎𝑏𝑑 𝑎𝑐𝑑 𝑏𝑐𝑑 𝑎𝑐𝑏 𝑎𝑑𝑏 𝑎𝑑𝑐 𝑏𝑑𝑐 𝑏𝑎𝑐 𝑏𝑎𝑑 𝑐𝑎𝑑 𝑐𝑏𝑑 𝑏𝑐𝑎 𝑏𝑑𝑎 𝑐𝑑𝑎 𝑐𝑑𝑏 𝑐𝑎𝑏 𝑑𝑎𝑏 𝑑𝑎𝑐 𝑑𝑏𝑐 𝑐𝑏𝑎 𝑑𝑏𝑎 𝑑𝑐𝑎 𝑑𝑐𝑏 18.05 Class 1, Counting and Sets, Spring 2022 7 Note that 𝑎𝑏𝑐 and 𝑎𝑐𝑏 count as distinct permutations. That is, for permutations the order matters. There are 24 permutations. Note that the rule of product would have told us there are 4 ⋅ 3 ⋅ 2 = 24 permutations without bothering to list them all. 2.4.2 Combinations In contrast to permutations, in combinations order does not matter: permutations are lists and combinations are sets. We show what we mean with an example Example 8. List all the combinations of 3 elements out of the set {𝑎, 𝑏, 𝑐, 𝑑}. Solution: Such a combination is a collection of 3 elements without regard to order. So, 𝑎𝑏𝑐 and 𝑐𝑎𝑏 both represent the same combination. We can list all the combinations by listing all the subsets of exactly 3 elements. {𝑎, 𝑏, 𝑐} {𝑎, 𝑏, 𝑑} {𝑎, 𝑐, 𝑑} {𝑏, 𝑐, 𝑑} There are only 4 combinations. Contrast this with the 24 permutations in the previous example. The factor of 6 comes because every combination of 3 things can be written in 6 different orders. 2.4.3 Formulas We’ll use the following notations. 𝑛 𝑃𝑘 = number of permutations (lists) of 𝑘 distinct elements from a set of size 𝑛 𝑛 𝐶𝑘 = (𝑛𝑘) = number of combinations (subsets) of 𝑘 elements from a set of size 𝑛 We emphasize that by the number of combinations of 𝑘 elements we mean the number of subsets of size 𝑘. These have the following notation and formulas: Permutations: 𝑛 𝑃𝑘 Combinations: 𝑛 𝐶𝑘 𝑛! = 𝑛(𝑛 − 1) ⋯ (𝑛 − 𝑘 + 1) (𝑛 − 𝑘)! 𝑛! 𝑃 = =𝑛 𝑘 𝑘!(𝑛 − 𝑘)! 𝑘! = The notation 𝑛 𝐶𝑘 is read “𝑛 choose 𝑘”. The formula for 𝑛 𝑃𝑘 follows from the rule of product. It also implies the formula for 𝑛 𝐶𝑘 because a subset of size 𝑘 can be ordered in 𝑘! ways. We can illustrate the relation between permutations and combinations by lining up the results of the previous two examples. 𝑎𝑏𝑐 𝑎𝑏𝑑 𝑎𝑐𝑑 𝑏𝑐𝑑 𝑎𝑐𝑏 𝑎𝑑𝑏 𝑎𝑑𝑐 𝑏𝑑𝑐 𝑏𝑎𝑐 𝑏𝑎𝑑 𝑐𝑎𝑑 𝑐𝑏𝑑 𝑏𝑐𝑎 𝑏𝑑𝑎 𝑐𝑑𝑎 𝑐𝑑𝑏 𝑐𝑎𝑏 𝑑𝑎𝑏 𝑑𝑎𝑐 𝑑𝑏𝑐 Permutations: 4 𝑃3 𝑐𝑏𝑎 𝑑𝑏𝑎 𝑑𝑐𝑎 𝑑𝑐𝑏 {𝑎, 𝑏, 𝑐} {𝑎, 𝑏, 𝑑} {𝑎, 𝑐, 𝑑} {𝑏, 𝑐, 𝑑} Combinations: 4 𝐶3 Notice that each row in the permutations list consists of all 3! permutations of the corresponding set in the combinations list. 18.05 Class 1, Counting and Sets, Spring 2022 2.4.4 8 Examples Example 9. Count the following: (i) The number of ways to choose 2 out of 4 things (order does not matter). (ii) The number of ways to list 2 out of 4 things. (iii) The number of ways to choose 3 out of 10 things. Solution: (i) This is asking for combinations: (42) = (ii) This is asking for permuations: 4 𝑃2 = 4! 2! (iii) This is asking for combinations: (10 3) = 4! 2! 2! = 6. = 12. 10! 3! 7! = 10⋅9⋅8 3⋅2⋅1 = 120. Example 10. (i) Count the number of ways to get 3 heads in a sequence of 10 flips of a coin. (ii) If the coin is fair, what is the probability of exactly 3 heads in 10 flips? Solution: (i) This asks for the number sequences of 10 flips (heads or tails) with exactly 3 heads. That is, we have to choose exactly 3 out of 10 flips to be heads. This is the same question as in the previous example. 10! 10 10 ⋅ 9 ⋅ 8 ( )= = = 120. 3 3! 7! 3⋅2⋅1 (ii) Each flip has 2 possible outcomes (heads or tails). So the rule of product says there are 210 = 1024 sequences of 10 flips. Since the coin is fair each sequence is equally probable. So the probability of 3 heads is 120 = 0.117 . 1024