Counting
Learning Outcomes
- Compute a conditional probability for an event
- Use Baye’s theorem to compute a conditional probability
- Calculate the expected value of an event
Basic Counting
We will start, however, with some more reasonable sorts of counting problems in order to develop the ideas that we will soon need.example
Suppose at a particular restaurant you have three choices for an appetizer (soup, salad or breadsticks) and five choices for a main course (hamburger, sandwich, quiche, fajita or pizza). If you are allowed to choose exactly one item from each category for your meal, how many different meal options do you have? Solution 1: One way to solve this problem would be to systematically list each possible meal: soup + hamburger soup + sandwich soup + quiche soup + fajita soup + pizza salad + hamburger salad + sandwich salad + quiche salad + fajita salad + pizza breadsticks + hamburger breadsticks + sandwich breadsticks + quiche breadsticks + fajita breadsticks + pizza Assuming that we did this systematically and that we neither missed any possibilities nor listed any possibility more than once, the answer would be 15. Thus you could go to the restaurant 15 nights in a row and have a different meal each night. Solution 2: Another way to solve this problem would be to list all the possibilities in a table:hamburger | sandwich | quiche | fajita | pizza | |
soup | soup+burger | ||||
salad | salad+burger | ||||
bread | etc |
Basic Counting Rule
If we are asked to choose one item from each of two separate categories where there are m items in the first category and n items in the second category, then the total number of available choices is m · n. This is sometimes called the multiplication rule for probabilities.example
There are 21 novels and 18 volumes of poetry on a reading list for a college English course. How many different ways can a student select one novel and one volume of poetry to read during the quarter?Answer: There are 21 choices from the first category and 18 for the second, so there are 21 · 18 = 378 possibilities.
example
Suppose at a particular restaurant you have three choices for an appetizer (soup, salad or breadsticks), five choices for a main course (hamburger, sandwich, quiche, fajita or pasta) and two choices for dessert (pie or ice cream). If you are allowed to choose exactly one item from each category for your meal, how many different meal options do you have?Answer: There are 3 choices for an appetizer, 5 for the main course and 2 for dessert, so there are 3 · 5 · 2 = 30 possibilities.
Example
A quiz consists of 3 true-or-false questions. In how many ways can a student answer the quiz?Answer: There are 3 questions. Each question has 2 possible answers (true or false), so the quiz may be answered in 2 · 2 · 2 = 8 different ways. Recall that another way to write 2 · 2 · 2 is 23, which is much more compact.
Permutations
In this section we will develop an even faster way to solve some of the problems we have already learned to solve by other means. Let's start with a couple examples.example
How many different ways can the letters of the word MATH be rearranged to form a four-letter code word?Answer: This problem is a bit different. Instead of choosing one item from each of several different categories, we are repeatedly choosing items from the same category (the category is: the letters of the word MATH) and each time we choose an item we do not replace it, so there is one fewer choice at the next stage: we have 4 choices for the first letter (say we choose A), then 3 choices for the second (M, T and H; say we choose H), then 2 choices for the next letter (M and T; say we choose M) and only one choice at the last stage (T). Thus there are 4 · 3 · 2 · 1 = 24 ways to spell a code worth with the letters MATH.
Factorial
n! = n · (n – 1) · (n – 2) ··· 3 · 2 · 1
example
How many ways can five different door prizes be distributed among five people?Answer: There are 5 choices of prize for the first person, 4 choices for the second, and so on. The number of ways the prizes can be distributed will be 5! = 5 · 4 · 3 · 2 · 1 = 120 ways.
examples
A charity benefit is attended by 25 people and three gift certificates are given away as door prizes: one gift certificate is in the amount of $100, the second is worth $25 and the third is worth $10. Assuming that no person receives more than one prize, how many different ways can the three gift certificates be awarded?Answer: Using the Basic Counting Rule, there are 25 choices for the person who receives the $100 certificate, 24 remaining choices for the $25 certificate and 23 choices for the $10 certificate, so there are 25 · 24 · 23 = 13,800 ways in which the prizes can be awarded.
Example
Eight sprinters have made it to the Olympic finals in the 100-meter race. In how many different ways can the gold, silver and bronze medals be awarded?Answer: Using the Basic Counting Rule, there are 8 choices for the gold medal winner, 7 remaining choices for the silver, and 6 for the bronze, so there are 8 · 7 · 6 = 336 ways the three medals can be awarded to the 8 runners. Note that in these preceding examples, the gift certificates and the Olympic medals were awarded without replacement; that is, once we have chosen a winner of the first door prize or the gold medal, they are not eligible for the other prizes. Thus, at each succeeding stage of the solution there is one fewer choice (25, then 24, then 23 in the first example; 8, then 7, then 6 in the second). Contrast this with the situation of a multiple choice test, where there might be five possible answers — A, B, C, D or E — for each question on the test. Note also that the order of selection was important in each example: for the three door prizes, being chosen first means that you receive substantially more money; in the Olympics example, coming in first means that you get the gold medal instead of the silver or bronze. In each case, if we had chosen the same three people in a different order there might have been a different person who received the $100 prize, or a different goldmedalist. (Contrast this with the situation where we might draw three names out of a hat to each receive a $10 gift certificate; in this case the order of selection is not important since each of the three people receive the same prize. Situations where the order is not important will be discussed in the next section.)
Factorial examples are worked in this video. https://youtu.be/9maoGi5fd_Mn · (n – 1) · (n – 2) ··· (n – r + 1)
If you don't see why (n — r + 1) is the right number to use for the last factor, just think back to the first example in this section, where we calculated 25 · 24 · 23 to get 13,800. In this case n = 25 and r = 3, so n — r + 1 = 25 — 3 + 1 = 23, which is exactly the right number for the final factor. Now, why would we want to use this complicated formula when it's actually easier to use the Basic Counting Rule, as we did in the first two examples? Well, we won't actually use this formula all that often; we only developed it so that we could attach a special notation and a special definition to this situation where we are choosing r items out of n possibilities without replacement and where the order of selection is important. In this situation we write:Permutations
nPr = n · (n – 1) · (n – 2) ··· (n – r + 1)
We say that there are nPr permutations of size r that may be selected from among n choices without replacement when order matters. It turns out that we can express this result more simply using factorials.[latex]{}_{n}{{P}_{r}}=\frac{n!}{(n-r)!}[/latex]
example
I have nine paintings and have room to display only four of them at a time on my wall. How many different ways could I do this?Answer: Since we are choosing 4 paintings out of 9 without replacement where the order of selection is important there are 9P4 = 9 · 8 · 7 · 6 = 3,024 permutations.
Example
How many ways can a four-person executive committee (president, vice-president, secretary, treasurer) be selected from a 16-member board of directors of a non-profit organization?Answer: We want to choose 4 people out of 16 without replacement and where the order of selection is important. So the answer is 16P4 = 16 · 15 · 14 · 13 = 43,680.
View this video to see more about the permutations examples. https://youtu.be/xlyX2UJMJQITry It
How many 5 character passwords can be made using the letters A through Z- if repeats are allowed
- if no repeats are allowed
Combinations
In the previous section we considered the situation where we chose r items out of n possibilities without replacement and where the order of selection was important. We now consider a similar situation in which the order of selection is not important.Example
A charity benefit is attended by 25 people at which three $50 gift certificates are given away as door prizes. Assuming no person receives more than one prize, how many different ways can the gift certificates be awarded?Answer: Using the Basic Counting Rule, there are 25 choices for the first person, 24 remaining choices for the second person and 23 for the third, so there are 25 · 24 · 23 = 13,800 ways to choose three people. Suppose for a moment that Abe is chosen first, Bea second and Cindy third; this is one of the 13,800 possible outcomes. Another way to award the prizes would be to choose Abe first, Cindy second and Bea third; this is another of the 13,800 possible outcomes. But either way Abe, Bea and Cindy each get $50, so it doesn't really matter the order in which we select them. In how many different orders can Abe, Bea and Cindy be selected? It turns out there are 6: ABC ACB BAC BCA CAB CBA How can we be sure that we have counted them all? We are really just choosing 3 people out of 3, so there are 3 · 2 · 1 = 6 ways to do this; we didn't really need to list them all. We can just use permutations! So, out of the 13,800 ways to select 3 people out of 25, six of them involve Abe, Bea and Cindy. The same argument works for any other group of three people (say Abe, Bea and David or Frank, Gloria and Hildy) so each three-person group is counted six times. Thus the 13,800 figure is six times too big. The number of distinct three-person groups will be 13,800/6 = 2300.
Combinations
[latex]{}_{n}{{C}_{r}}=\frac{{}_{n}{{P}_{r}}}{{}_{r}{{P}_{r}}}[/latex]
We say that there are nCr combinations of size r that may be selected from among n choices without replacement where order doesn’t matter. We can also write the combinations formula in terms of factorials:[latex]{}_{n}{{C}_{r}}=\frac{n!}{(n-r)!r!}[/latex]
Example
A group of four students is to be chosen from a 35-member class to represent the class on the student council. How many ways can this be done?Answer: Since we are choosing 4 people out of 35 without replacement where the order of selection is not important there are [latex]{}_{35}{{C}_{4}}=\frac{35\cdot34\cdot33\cdot32}{4\cdot3\cdot2\cdot1}[/latex] = 52,360 combinations.
View the following for more explanation of the combinations examples. https://youtu.be/W8kd4YosbzETry It
The United States Senate Appropriations Committee consists of 29 members; the Defense Subcommittee of the Appropriations Committee consists of 19 members. Disregarding party affiliation or any special seats on the Subcommittee, how many different 19-member subcommittees may be chosen from among the 29 Senators on the Appropriations Committee?Example
The United States Senate Appropriations Committee consists of 29 members, 15 Republicans and 14 Democrats. The Defense Subcommittee consists of 19 members, 10 Republicans and 9 Democrats. How many different ways can the members of the Defense Subcommittee be chosen from among the 29 Senators on the Appropriations Committee?Answer: In this case we need to choose 10 of the 15 Republicans and 9 of the 14 Democrats. There are 15C10 = 3003 ways to choose the 10 Republicans and 14C9 = 2002 ways to choose the 9 Democrats. But now what? How do we finish the problem? Suppose we listed all of the possible 10-member Republican groups on 3003 slips of red paper and all of the possible 9-member Democratic groups on 2002 slips of blue paper. How many ways can we choose one red slip and one blue slip? This is a job for the Basic Counting Rule! We are simply making one choice from the first category and one choice from the second category, just like in the restaurant menu problems from earlier. There must be 3003 · 2002 = 6,012,006 possible ways of selecting the members of the Defense Subcommittee.
This example is worked through below. https://youtu.be/Xqc2sdYN7xoLicenses & Attributions
CC licensed content, Original
- Revision and Adaptation. Provided by: Lumen Learning License: CC BY: Attribution.
CC licensed content, Shared previously
- Math in Society. Authored by: Lippman, David. Located at: http://www.opentextbookstore.com/mathinsociety/. License: CC BY-SA: Attribution-ShareAlike.