Chapter 6 Probability

6.3 Counting

Learning Objectives

By the end of this section, you will be able to:

  • Understand basic counting techniques
  • Use the basic counting rule to find probability
  • Find probability using permutations and combinations

Counting? You already know how to count or you wouldn't be taking a college-level math class, right? Well, yes, but what we'll really be investigating here are ways of counting efficiently. When we get to the probability situations a bit later in this chapter, we will need to count some very large numbers, like the number of possible winning lottery tickets. One way to do this would be to write down every possible set of numbers that might show up on a lottery ticket, but believe me, you don't want to do this.

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 1

Suppose at a particular restaurant you have 3 choices for an appetizer (soup, salad, or breadsticks) and 5 choices for a main course (hamburger, sandwich, quiche, fajita, or pizza). If you are allowed to choose exactly 1 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:

[latex]\begin{array} {|c|c|c|c|c|c|} \hline \text{}& \textbf{hamburger} &\textbf{sandwich} & \textbf{quiche} & \textbf{fajita} & \textbf{pizza}\\ \hline \textbf{soup} & \text{soup+burger} \\ \hline \textbf{salad} & \text{salad+burger}\\ \hline \textbf{bread} & \textit{etc.}\\ \hline \end{array}[/latex]

In each of the cells in the table, we could list the corresponding meal: soup + hamburger in the upper left corner, salad + hamburger below it, etc. But if we didn't really care what the possible meals are, only how many possible meals there are, we could just count the number of cells and arrive at an answer of 15, which matches our answer from the first solution. (It's always good when you solve a problem two different ways and get the same answer!)

Solution 3: We already have two perfectly good solutions. Why do we need a third? The first method was not very systematic, and we might easily have made an omission. The second method was better, but suppose that in addition to the appetizer and the main course, we further complicated the problem by adding desserts to the menu: we've used the rows of the table for the appetizers and the columns for the main courses—where will the desserts go? We would need a third dimension, and since drawing 3-D tables on a 2-D page or computer screen isn't terribly easy, we need a better way in case we have 3 categories to choose from instead of just 2.

So back to the problem in the example. What else can we do? Let's draw a tree diagram:

Tree diagram showing five categories: hamburger, sandwich, fajita, quiche, and pizza; each separated into three options: soup, salad, bread.
Figure 1. Tree diagram

This is called a "tree" diagram because at each stage we branch out, like the branches on a tree.  In this case, we first drew 5 branches (1 for each main course) and then for each of those branches, we drew 3 more branches (1 for each appetizer).  We count the number of branches at the final level and get (surprise, surprise!) 15.

If we wanted, we could instead draw 3 branches at the first stage for the 3 appetizers and then 5 branches (1 for each main course) branching out of each of those 3 branches.

OK, so now we know how to count possibilities using tables and tree diagrams.  These methods will continue to be useful in certain cases, but imagine a game where you have 2 decks of cards (with 52 cards in each deck) and you select 1 card from each deck.  Would you really want to draw a table or tree diagram to determine the number of outcomes of this game?

Let's go back to the previous example that involved selecting a meal from 3 appetizers and 5 main courses and look at the second solution that used a table.  Notice that one way to count the number of possible meals is simply to number each of the appropriate cells in the table, as we have done above.  But another way to count the number of cells in the table would be to multiply the number of rows (3) by the number of columns (5) to get 15.

Notice that we could have arrived at the same result without making a table at all by simply multiplying the number of choices for the appetizer (3) by the number of choices for the main course (5). We generalize this technique as the basic counting rule.

Basic Counting Rule

If we are asked to choose 1 item from each of 2 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 [latex]m \cdot n[/latex].

This is sometimes called the multiplication rule for counting.

 

 Example 2

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 1 novel and 1 volume of poetry to read during the quarter?

There are 21 choices from the first category and 18 for the second, so there are [latex]21 \cdot 18 = 378[/latex] possibilities.

The basic counting rule can be extended when there are more than two categories by applying it repeatedly, as we see in the next example.

Example 3

Suppose at a particular restaurant you have 3 choices for an appetizer (soup, salad, or breadsticks), 5 choices for a main course (hamburger, sandwich, quiche, fajita, or pasta), and 2 choices for dessert (pie or ice cream). If you are allowed to choose exactly 1 item from each category for your meal, how many different meal options do you have?

There are 3 choices for an appetizer, 5 for the main course, and 2 for dessert, so there are [latex]3 \cdot 5 \cdot 2 = 30[/latex] possibilities.

Example 4

A quiz consists of 3 true-or-false questions.  In how many ways can a student answer the quiz?

There are 3 questions.  Each question has 2 possible answers (true or false), so the quiz may be answered in [latex]2 \cdot 2 \cdot 2 = 8[/latex] different ways.  Recall that another way to write [latex]2 \cdot 2 \cdot 2[/latex] is [latex]2^{3}[/latex], which is much more compact.

Exercise 1

Suppose at a particular restaurant you have 8 choices for an appetizer, 11 choices for a main course, and 5 choices for dessert. If you are allowed to choose exactly 1 item from each category for your meal, how many different meal options do you have?

Solution

440 menu combinations

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 5

How many different ways can the letters of the word MATH be rearranged to form a 4-letter code word?

This problem is a bit different.  Instead of choosing 1 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 1 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 1 choice at the last stage (T).  Thus there are [latex]4 \cdot 3 \cdot 2 \cdot 1 = 24[/latex] ways to spell a code word with the letters MATH.

In this example, we needed to calculate [latex]n \cdot (n – 1) \cdot (n – 2) \cdot \cdot \cdot 3 \cdot 2 \cdot 1[/latex].  This type of calculation occurs often in mathematics.  It is an example of a factorial problem, and it is notated [latex]n![/latex].

Factorial

[latex]n! = n \cdot (n – 1) \cdot (n – 2) \cdot \cdot \cdot 3 \cdot 2 \cdot 1[/latex]

[latex]0!=1[/latex]

 

Example 6

How many ways can 5 different door prizes be distributed among 5 people?

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 [latex]5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120[/latex] ways.

Now we will consider some slightly different examples.

Example 7

A charity benefit is attended by 25 people, and 3 gift certificates are given away as door prizes: the first 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 1 prize, how many different ways can the 3 gift certificates be awarded?

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 [latex]25 \cdot 24 \cdot 23 = 13,800[/latex] ways in which the prizes can be awarded.

Example 8

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?

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 [latex]8 \cdot 7 \cdot 6 = 336[/latex] ways the 3 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 1 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 5 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 3 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 3 people in a different order, there might have been a different person who received the $100 prize or a different gold medalist. (Contrast this with the situation where we might draw 3 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 3 people receive the same prize.  Situations where the order is not important will be discussed later in the section.)

We can generalize the situation in the two examples above to any problem without replacement where the order of selection is important. If we are arranging in order r items out of n possibilities (instead of 3 out of 25 or 3 out of 8 as in the previous examples), the number of possible arrangements will be given by

[latex]n \cdot (n-1) \cdot (n-2) \cdot \cdot \cdot (n-r+1)[/latex]

If you don't see why [latex](n-r+1)[/latex] is the right number to use for the last factor, just think back to the first example in this section, where we calculated [latex]25 \cdot 24 \cdot 23[/latex] to get 13,800.  In this case [latex]n = 25[/latex] and [latex]r = 3[/latex], so [latex]n - r + 1 = 25 - 3 + 1 = 23[/latex], 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

[latex]_n P_r = n \cdot (n-1) \cdot (n-2) \cdot \cdot \cdot (n-r+1)[/latex]

We say that there are [latex]_nP_r[/latex] 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]

In practicality, we usually use technology rather than factorials or repeated multiplication to compute permutations.

Example 9

I have 9 paintings and have room to display only 4 of them at a time on my wall.  How many different ways could I do this?

Since we are choosing 4 paintings out of 9 without replacement where the order of selection is important, there are [latex]_9P_4 = 9 \cdot 8 \cdot 7 \cdot 6 = 3,024[/latex] permutations.

Example 10

How many ways can a 4-person executive committee (president, vice president, secretary, treasurer) be selected from a 16-member board of directors of a nonprofit organization?

We want to choose 4 people out of 16 without replacement and where the order of selection is important. So the answer is [latex]_{16} P_4 = 16 \cdot 15 \cdot 14 \cdot 13 = 43,680[/latex].

Exercise 2

How many 5-character passwords can be made using the letters A through Z

  1. if repeats are allowed
  2. if no repeats are allowed
Solution
  1. [latex]25^{5}=11,881,376[/latex]
  2. [latex]_{26} P_5 = 26 \cdot 25 \cdot 24 \cdot 23 \cdot 22 = 7,893,600[/latex]

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 11

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 1 prize, how many different ways can the gift certificates be awarded?

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 [latex]25 \cdot 24 \cdot 23 = 13,800[/latex] ways to choose 3 people.  Suppose for a moment that Abe is chosen first, Bea second, and Cindy third; this is 1 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 [latex]3 \cdot 2 \cdot 1 = 6[/latex] 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, 6 of them involve Abe, Bea and Cindy.  The same argument works for any other group of 3 people (say Abe, Bea, and David or Frank, Gloria, and Hildy), so each 3-person group is counted 6 times.  Thus the 13,800 figure is 6 times too big.  The number of distinct 3-person groups will be [latex]\frac{13800}{6} = 2300[/latex].

We can generalize the situation in this example above to any problem of choosing a collection of items without replacement where the order of selection is not important. If we are choosing r items out of n possibilities (instead of 3 out of 25 as in the previous examples), the number of possible choices will be given by [latex]\frac{_n P_r}{_rP_r}[/latex], and we could use this formula for computation.  However, this situation arises so frequently that we attach a special notation and a special definition to this situation where we are choosing r items out of n possibilities without replacement where the order of selection is not important.

Combinations

[latex]_n C _r = \frac{_n P_r}{_rP_r}[/latex]

We say that there are [latex]_n C _r[/latex] 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 12

A group of 4 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?

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 \cdot 34 \cdot 33 \cdot 32}{4 \cdot 3 \cdot 2 \cdot 1} = 52,360[/latex] combinations.

Exercise 3

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?

Solution

20,030,010 possible subcommittees

In the preceding exercise, we assumed that the 19 members of the Defense Subcommittee were chosen without regard to party affiliation.  In reality, this would never happen: if Republicans are in the majority, they would never let a majority of Democrats sit on (and thus control) any subcommittee.  The same, of course, would be true if the Democrats were in control.  Let's consider the problem again in a slightly more complicated form.

Example 13

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?

In this case we need to choose 10 of the 15 Republicans and 9 of the 14 Democrats.  There are [latex]_{15}C_{10} = 3003[/latex] ways to choose the 10 Republicans and [latex]_{14}C_9 = 2002[/latex] 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 3,003 slips of red paper and  all of the possible 9-member Democratic groups on 2,002 slips of blue paper.  How many ways can we choose 1 red slip and 1 blue slip?  This is a job for the basic counting rule!  We are simply making 1 choice from the first category and 1 choice from the second category, just like in the restaurant menu problems from earlier.

There must be [latex]3003 \cdot 2002 = 6,012,006[/latex] possible ways of selecting the members of the Defense Subcommittee.

Probability Using Permutations and Combinations

We can use permutations and combinations to help answer more complex probability questions.

Example 14

A 4-digit PIN number is selected.  What is the probability that there are no repeated digits?

There are 10 possible values for each digit of the PIN (namely, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9), so there are [latex]10 \cdot 10 \cdot 10 \cdot 10 = 10^{4} = 10000[/latex] total possible PIN numbers.

To have no repeated digits, all 4 digits would have to be different, which is selecting without replacement.  We could either compute [latex]10 \cdot 9 \cdot 8 \cdot 7[/latex] or notice that this is the same as the permutation [latex]_{10}P_4 = 5040[/latex].

The probability of no repeated digits is the number of 4-digit PIN numbers with no repeated digits divided by the total number of 4-digit PIN numbers.  This probability is [latex]\frac{_{10} P_4}{10^{4}} = \frac{5040}{10000}=0.504[/latex].

Example 15

In a certain state's lottery, 48 balls numbered 1 through 48 are placed in a machine and 6 of them are drawn at random. If the 6 numbers drawn match the numbers that a player had chosen, the player wins $1,000,000.    In this lottery, the order the numbers are drawn in doesn’t matter.  Compute the probability that you win the million-dollar prize if you purchase a single lottery ticket.

In order to compute the probability, we need to count the total number of ways 6 numbers can be drawn and the number of ways the 6 numbers on the player’s ticket could match the 6 numbers drawn from the machine. Since there is no stipulation that the numbers will be in any particular order, the number of possible outcomes of the lottery drawing is [latex]_{48}C_6 = 12,271,512[/latex].  Of these possible outcomes, only 1 would match all 6 numbers on the player’s ticket, so the probability of winning the grand prize is  [latex]\frac{_6 C_6}{_{48}C_6} = \frac{1}{12271512} \approx{0.0000000815}[/latex].

Example 16

In the state lottery from the previous example, if 5 of the 6 numbers drawn match the numbers that a player has chosen, the player wins a second prize of $1,000. Compute the probability that you win the second prize if you purchase a single lottery ticket.

As above, the number of possible outcomes of the lottery drawing is [latex]_{48} C_6 = 12,271,512[/latex]. In order to win the second prize, 5 of the 6 numbers on the ticket must match 5 of the 6 winning numbers; in other words, we must have chosen 5 of the 6 winning numbers and 1 of the 42 losing numbers. The number of ways to choose 5 out of the 6 winning numbers is given by [latex]_6C_5 = 6[/latex], and the number of ways to choose 1 out of the 42 losing numbers is given by [latex]_{42}C_1 = 42[/latex]. Thus the number of favorable outcomes is then given by the basic counting rule: [latex]_6C_5 \cdot _{42}C_1 = 6 \cdot 42 = 252[/latex]. So the probability of winning the second prize is [latex]\frac{(_6 C_5)(_{42} C_1)}{_{48} C _6} = \frac{252}{12271512} \approx{0.0000205}[/latex].

Exercise 4

A multiple-choice question on an economics quiz contains 10 questions with 5 possible answers each.  Compute the probability of randomly guessing the answers and getting 9 questions correct.

Solution

There are [latex]5^{10} = 9,765,625[/latex] different ways the exam can be answered. There are 9 possible locations for the 1 missed question, and in each of those locations there are 4 wrong answers, so there are 36 ways the test could be answered with 1 wrong answer. [latex]P(\text{9 answers correct}) = \frac{36}{5^{10}} \approx{0.0000037}[/latex]

Example 17

Compute the probability of randomly drawing 5 cards from a deck and getting exactly 1 Ace.

In many card games (such as poker), the order in which the cards are drawn is not important (since the player may rearrange the cards in his hand any way he chooses); in the problems that follow, we will assume that this is the case unless otherwise stated.  Thus we use combinations to compute the possible number of 5-card hands, [latex]_{52}C_5[/latex].  This number will go in the denominator of our probability formula, since it is the number of possible outcomes.

For the numerator, we need the number of ways to draw 1 Ace and 4 other cards (none of them Aces) from the deck.  Since there are 4 Aces and we want exactly 1 of them, there will be [latex]_4 C_1[/latex] ways to select 1 Ace; since there are 48 non-Aces and we want 4 of them, there will be [latex]_{48}C_4[/latex] ways to select the 4 non-Aces.  Now we use the basic counting rule to calculate that there will be [latex]_4C_1 \cdot _{48}C_4[/latex] ways to choose 1 Ace and 4 non-Aces.

Putting this all together, we have [latex]P(\text{1 Ace})=\frac{(_4 C_1)(_{48} C_4)}{_{52} C _5} = \frac{778320}{2598960} \approx{0.299}[/latex].

Example 18

Compute the probability of randomly drawing 5 cards from a deck and getting exactly 2 Aces.

The solution is similar to the previous example, except now we are choosing 2 Aces out of 4 and 3 non-Aces out of 48; the denominator remains the same:

[latex]P(\text{2 Aces}) = \frac{(_4 C_2)(_{48} C_3)}{_{52} C _5} = \frac{103776}{2598960} \approx{0.0399}[/latex].

It is useful to note that these card problems are remarkably similar to the lottery problems discussed earlier.

Exercise 5

Compute the probability of randomly drawing 5 cards from a deck of cards and getting 3 Aces and 2 Kings.

Solution

[latex]P(\text{3 Aces and 2 Kings})=\frac{(_4 C_3)(_4 C_2)}{_{52} C _5} = \frac{24}{2598960} \approx{0.0000092}[/latex]

Birthday Problem

Let's take a pause to consider a famous problem in probability theory.

Suppose you have a room full of 30 people.  What is the probability that there is at least 1 shared birthday?

Take a guess at the answer to the above problem.  Was your guess fairly low, like around 10%?  That seems to be the intuitive answer ([latex]\frac{30}{365}[/latex], perhaps?).  Let's see if we should listen to our intuition.  Let's start with a simpler problem, however.

Example 19

Suppose 3 people are in a room.  What is the probability that there is at least 1 shared birthday among these 3 people?

There are a lot of ways there could be at least 1 shared birthday.  Fortunately, there is an easier way.  We ask ourselves, “What is the alternative to having at least 1 shared birthday?”  In this case, the alternative is that there are no shared birthdays.  In other words, the alternative to “at least 1 ” is having none.  In other words, since this is a complementary event,

[latex]P(\text{at least 1}) = 1 – P(\text{none})[/latex]

We will start, then, by computing the probability that there is no shared birthday.  Let's imagine that you are 1 of these 3 people.  Your birthday can be anything without conflict, so there are 365 choices out of 365 for your birthday.  What is the probability that the second person does not share your birthday?  There are 365 days in the year (let's ignore leap years), and removing your birthday from contention, there are 364 choices that will guarantee that you do not share a birthday with this person, so the probability that the second person does not share your birthday is 364/365.  Now we move to the third person.  What is the probability that this third person does not have the same birthday as either you or the second person?  There are 363 days that will not duplicate your birthday or the second person's, so the probability that the third person does not share a birthday with the first 2 is 363/365.

We want the second person not to share a birthday with you and the third person not to share a birthday with the first 2 people, so we use the multiplication rule:

[latex]P(\text{no shared birthday})=\frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \approx{0.9918}[/latex]

and then subtract from 1 to get

[latex]P(\text{shared birthday })= 1 – P(\text{no shared birthday}) = 1 – 0.9918 = 0.0082[/latex].

This is a pretty small number, so maybe it makes sense that the answer to our original problem will be small.  Let's make our group a bit bigger.

Example 20

Suppose 5 people are in a room.  What is the probability that there is at least 1 shared birthday among these 5 people?

Continuing the pattern of the previous example, the answer should be [latex]P(\text{shared birthday})=1-\frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdot \frac{361}{365} \approx{0.0271}[/latex]

Note that we could rewrite this more compactly as [latex]P(\text{shared birthday}) = 1- \frac{_{365} P_5}{365^{5}} \approx{0.0271}[/latex]

which makes it a bit easier to type into a calculator or computer and which suggests a nice formula as we continue to expand the population of our group.

Example 21

Suppose 30 people are in a room.  What is the probability that there is at least 1 shared birthday among these 30 people?

Here we can calculate [latex]P(\text{shared birthday})=1- \frac{_{365} P_{30}}{365^{30}} \approx{0.706}[/latex]

which gives us the surprising result that when you are in a room with 30 people there is a 70% chance that there will be at least 1 shared birthday!

If you like to bet, and if you can convince 30 people to reveal their birthdays, you might be able to win some money by betting a friend that there will be at least 2 people with the same birthday in the room anytime you are in a room of 30 or more people.  (Of course, you would need to make sure your friend hasn't studied probability!)  You wouldn't be guaranteed to win, but you should win more than half the time.

Exercise 6

Suppose 10 people are in a room. What is the probability that there is at least 1 shared birthday among these 10 people?

Solution

[latex]P(\text{shared birthday})=1- \frac{_{365} P_{10}}{365^{10}} \approx{0.117}[/latex]

Extra Practice

Answer the following questions using basic counting techniques.

  1. An ice-cream parlor sells 26 different flavors of ice cream. A basic sundae has one scoop of any flavor of ice cream, your choice of one of 3 sauces, and any one of 8 different toppings.
    1. How many different basic sundaes are possible?
    2. The ice-cream parlor also sells a medium sundae. The options are the same except it starts with 2 scoops of ice cream, which can be the same flavor or different flavors. How many different medium sundaes are there?
    3. The ice-cream parlor also sells a large sundae. The choice of a large sundae allows you to choose any 3 scoops of ice cream, any 2 sauces (they can be the same, or you can choose 2 different ones), and any 3 toppings (that might be 3 servings of the same topping, or 2 servings of one topping and a single serving of another, or 3 different toppings). How many different large sundaes are possible?
  2. A company that builds custom computers offers 4 hard drive sizes, 4 memory sizes, 3 graphics cards, and 3 display options. How many computer configurations do they offer, if customers choose one of each customization?
  3. A video game allows users to customize their avatars. There are 12 hair styles that users may choose from, as well as 5 hair colors, 8 skin tones, 24 shirts, 12 pants, and 8 shoes. How many different avatars are possible?
  4. A small company has 3 divisions: Sales, Research and Development, and Manufacturing. One person from each division will be chosen to create an advisory board for the management group. If there are 8 people in Sales, 15 in Research and Development, and 48 in Manufacturing, how many different compositions of the advisory board are possible?
  5. A multiple-choice quiz has 5 questions, each of which has 4 possible answers. How many different ways are there to respond to this quiz?
  6. The teacher decides to make the quiz from above a little harder by offering 5 responses on each of the 5 questions. How many ways are there to respond to this quiz?
  7. In the United States, radio and television broadcast stations are assigned unique identifiers known as call signs. Call signs consist of 4 letters. The first is either K or W (generally speaking, stations with a K call sign are west of the Mississippi River and stations with a W call sign are east of the river, though there are several exceptions to this rule); the remaining 3 letters can be anything. How many possible call signs are there under this system?
  8. Little sister has asked big brother to play a new game she’s invented. It uses a modified deck of cards with 3 suits and only the numbered cards (those with rank 2 through 10). How many cards are in her deck?
  9. The board game Mastermind has 2 players. One of them is designated the codemaker who creates a code that consists of a series of 4 colors (indicated in the game with 4 colored pegs), which may contain repeats. The other player, who is the codebreaker, tries to guess the code. If there are 6 colors that the codemaker can use to make the code, how many possible codes can be made?
For the following exercises, give a whole number that’s equal to the given expression.
  1. [latex]3![/latex]
  2. [latex]9![/latex]
  3. [latex]\frac{7!}{2!2!3!}[/latex]
  4. [latex]\frac{8!}{5!2!}[/latex]
  5. [latex]\frac{21!}{18!2!}[/latex]
  6. [latex]\frac{28!}{26!2!}[/latex]
  7. [latex]\frac{34!}{30!3!}[/latex]
  8. [latex]\frac{17!}{12!5!}[/latex]

Find the following permutations.

  1. [latex]_4⁢𝑃_3[/latex]
  2. [latex]_7⁢𝑃_5[/latex]
  3. [latex]_{12}⁢𝑃_{10}[/latex]
  4. [latex]_{14}⁢𝑃_{10}[/latex]
  5. [latex]_{10}⁢𝑃_{⁢8}[/latex]
  6. [latex]_{15}⁢𝑃_{11}[/latex]
The following exercises are about the card game euchre, which uses a partial standard deck of cards: It only has the cards with ranks 9, 10, J, Q, K, and A for a total of 24 cards. Some variations of the game use the 8s or the 7s and 8s, but we’ll stick with the 24-card version.
  1. A euchre hand contains 5 cards. How many ways are there to receive a 5-card hand (where the order in which the cards are received matters, i.e., 9 of hearts, J of hearts, K of clubs, 9⁢ of spades, 10⁢ of spades is different from 9⁢of spades, J of hearts, 9 of hearts, K of clubs, 10⁢ of spades?
  2. After all 4 players get their hands, the remaining 4 cards are placed facedown in the center of the table. How many arrangements of 4 cards are there from this deck?
  3. Euchre is played with partners. How many ways are there for 2 partners to receive 5-card hands (where the order in which the cards are received matters)?
  4. How many different arrangements of the full euchre deck are possible (i.e., how many different shuffles are there)?
  5. The following exercises involve a horse race with 13 entrants.
    1. How many possible complete orders of finish are there?
    2. An exacta bet is one where the player tries to predict the top two finishers in order. How many possible exacta bets are there for this race?
    3. A trifecta bet is one where the player tries to predict the top three finishers in order. How many possible trifecta bets are there for this race?
    4. A superfecta bet is one where the player tries to predict the top four finishers in order. How many possible superfecta bets are there for this race?
For the following exercises, express your answers as whole numbers.
  1. [latex]_5⁢𝐶_3[/latex]
  2. [latex]_8⁢𝐶_2[/latex]
  3. [latex]_{12}⁢𝐶_3[/latex]
  4. [latex]_{14}⁢𝐶_{10}[/latex]
  5. [latex]_{15}⁢𝐶_5[/latex]
  6. [latex]_{18}⁢𝐶_6[/latex]

Solve the following combination problems.

  1. In most variations of the card game poker, a hand consists of 5 cards, where the order doesn’t matter. How many different poker hands are there?
  2. A professor starts each class by choosing 3 students to present solutions to homework problems to the class. If there are 41 students in the class, in how many different ways can the professor make those selections?
  3. An election for at-large members of a school board has 7 candidates; 3 will be elected. How many different ways can those 3 seats be filled?
  4. There are 20 contestants on a reality TV show; at the end of the first episode, 10 are eliminated. How many different groups of eliminated contestants are possible?
  5. At a horse race, bettors can place a bet called an exacta box. For this bet, the player chooses 2 horses; if those horses finish first and second (in either order), the player wins. In a race with 12 horses in the field, how many possible exacta box bets are there?
  6. You and 5 of your friends are at an amusement park, and are about to ride a roller coaster. The cars have room for 6 people arranged in 3 rows of 2, so you and your friends will perfectly fill one car.
    1. How many ways are there to choose the 2 people in the front row?
    2. Assuming the front row has been selected, how many ways are there to choose the 2 people in the middle row?
    3. Assuming the first 2 rows have been selected, how many ways are there to choose the 2 people in the back row?
    4. Using the Multiplication Rule for Counting and your answers to the earlier parts of this exercise, how many ways are there for your friends to sort yourselves into rows to board the roller coaster?
  7. The University Combinatorics Club has 18 members. Four of them will be selected to form a committee.
    1. How many different committees of 4 are possible, assuming all of the duties are shared equally?
    2. Instead of sharing responsibility equally, one person will be chosen to be the committee chair. How many different committees are possible? Count these by selecting a chair first, then selecting the remaining 3 members of the committee from the remaining club members and use the Multiplication Rule for Counting. Show your work.
    3. Let’s count the number of committees with chairs a different way: First, choose 4 people for the committee (as in the first question), then choose 1 of the 4 to be chair. Show your work. Do you get the same number?
  8. Powerball® is a multistate lottery game, which costs $2 to play. Players fill out a ticket by choosing 5 numbers between 1 and 69 (these are the white balls) and then a single number between 1 and 26 (this is the Powerball).
    1. How many different ways are there to choose the white balls? Players who match these 5 numbers exactly (but not the Powerball) win $1 million.
    2. How many ways are there to choose the Powerball? Players who correctly pick the Powerball win $4.
    3. How many ways are there to play the game altogether? Players who match all 5 white balls and the Powerball win (or share) the grand prize. (The grand prize starts at $40 million; if no players win the grand prize, the value goes up for the next drawing. The highest value it has ever reached is $1.586 billion!) How many ways are there to fill out a single Powerball ticket?
  9. You are in charge of programming for a music festival. The festival has a main stage, a secondary stage, and several smaller stages. There are 40 bands confirmed for the festival. Five of those will play the main stage, and 8 will play the secondary stage. How many ways are there for you to allocate bands to these 2 stages?
For the following exercises, decide whether the situation describes a permutation or a combination.
  1. You’re packing for vacation, and you need to pick 5 shirts.
  2. You and your friends are about to play a game, and you need to decide who will have the first turn, second turn, and so on.
  3. You are watching your favorite reality show, and you want to know how many possibilities there are for the order of finish for the top three.
  4. You are going to be working in groups of 4 with your classmates, and you want to know how many possibilities there are for the composition of your group.

Media Attributions

definition

License

Icon for the Creative Commons Attribution-ShareAlike 4.0 International License

Finite Mathematics Copyright © 2024 by LOUIS: The Louisiana Library Network is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License, except where otherwise noted.

Share This Book