6.4: Counting Methods

Learning Objectives

• Use the Fundamental Counting Principle
• Compute factorials, permutations and combinations
• Find probabilities using counting methods

Recall that

\[P(A)=\frac{\text { number of ways for } A \text { to occur }}{\text { total number of outcomes }}\]

for theoretical probabilities. So far the problems we have looked at had rather small total number of outcomes. We could easily count the number of elements in the sample space. If there are a large number of elements in the sample space we can use counting techniques such as permutations or combinations to count them.

Fundamental Counting Rule and Tree Diagrams

The simplest of the counting techniques is the Fundamental Counting Principle. A tree diagram is a useful tool for visualizing the counting rule. It uses branches to represent the outcomes in a multiple-step experiment.

Example \(\PageIndex{1}\)

Let’s say that a person walks into a restaurant for a three course dinner. There are 4 different salads, 3 different entrées, and 2 different desserts to choose from. Assuming the person wants to eat a salad, an entrée and a dessert, how many different meals are possible?

Solution

Looking at the tree diagram we can see that the total number of meals is \(4 \cdot 3 \cdot 2 = 24\, \text{meals}\).

In general, if there are two independent events, and the first event has \(n\) outcomes and the second event has \(m\) outcomes, then the total number of outcomes for both events is \(n \cdot m\). This the Fundamental Counting Principle or Multiplication Rule.

Fundamental Counting Principle

If event #1 can be done in \(n_1\) ways, event #2 can be done in \(n_2\) ways, and so forth to event #\(k\) being done in \(m_k\) ways, then the number of ways to do event #1, followed by event #2, ... followed by event #\(k\) together is:

\[n_1 \cdot n_2 \cdot n_3 \cdot ... \cdot n_k. \label{Fundamental Counting Principle}\]

The Fundamental Counting Principle is used when you have independent events, or if the same event occurs multiple times but outcomes can be repeated.

The Fundamental Counting Principle is used when you have independent events, of is the same event occurs multiple times but outcomes can be repeated. An example of independent events would be choosing a salad, entree, and desert as above. An example, where repeats are allowed is choosing a pin number, where after the first choice of digit, a repeat of the first choice is allowed for the second digit. Here the choices are also independent.

Example \(\PageIndex{2}\)

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

Solution

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

The Fundamental Counting Principle may seem like a very simple idea but it is very powerful. Many complex counting problems can be solved using the Fundamental Counting Principle.

Example \(\PageIndex{3}\)

Some license plates in Arizona consist of 3 digits followed by 3 letters. How many license plates of this type are possible if:

1. there are no restrictions on digits or letters?
2. letters can be repeated but digits cannot?
3. the first digit cannot be zero and both digits and letters can be repeated?
4. neither digits nor numbers can be repeated.

Solution

1. There are 10 digits (0, 1, 2, 3, …, 9) and 26 letters. \[\underbrace{(\underline{10} \cdot \underline{10} \cdot \underline{10})}_{\text{digits}} \cdot \underbrace{(\underline{26} \cdot \underline{26} \cdot \underline{26})}_{\text{letters}}=17,576,000 \text { license plates } \nonumber\]
2. There are 26 letters but the number of choices for digits will decrease by 1 after each chosen digit. \[\underbrace{(\underline{10} \cdot \underline{9} \cdot \underline{8})}_{\text{digits}} \cdot \underbrace{(\underline{26} \cdot \underline{26} \cdot \underline{26})}_{\text {letters}}=12,654,720\, \text{license plates} \nonumber\]
3. There are 9 choices for the first digit, and 10 choices for the second and third digits. There are 26 choices for letters. \[\underbrace{(\underline{9} \cdot \underline{10} \cdot \underline{10})}_{\text{digits}} \cdot \underbrace{(\underline{26} \cdot \underline{26} \cdot \underline{26})}_{\text{letters}}=15,818,400\, \text{license plates} \nonumber\]
4. The number of choices for digits and letters will decrease by 1 after each choice. \[\underbrace{(\underline{10} \cdot \underline{9} \cdot \underline{8})}_{\text{digits}} \cdot \underbrace{(\underline{26} \cdot \underline{25} \cdot \underline{24})}_{\text{letters}}=11,232,000 \, \text{license plates} \nonumber\]

Try It \(\PageIndex{1}\)

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

Answer

We can choose any of the 4 letters to be first. Then there are 3 choices for the second letter and 2 choices for the third. At this point there is only 1 letter left to be last. Using the Fundamental Counting Principle there are

\[4 \cdot 3 \cdot 2 \cdot 1 = 24\, \text{ways} \nonumber\]

for to form a 4-letter code word from the letters of MATH.

This type of calculation occurs frequently in counting problems so we have some notation to simplify the problem.

Factorial

The factorial of \(n\), read “n factorial” is

\[n! = n\cdot (n-1)\cdot (n-2)\cdot ... \cdot 3 \cdot 2 \cdot 1.\nonumber\]

By this definition, \(0! = 1.\)

Some examples of calculations of factorials:

\( 5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120\)

\( 8! = 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 40,320\)

Factorials get very large very fast.

\(20! \approx 2.43 \cdot 10^{18} \) and \(40! \approx 8.16 \cdot 10^{47}.\)

Look for the '"!" factorial button on your calculator. Note that 70! is larger than most calculators can handle.

Try It \(\PageIndex{2}\)

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 \cdot 4 \cdot 3 \cdot 2 \cdot 1=120\) ways.

Permutations

Consider the following counting problems:

1. In how many ways can three runners finish a race?
2. In how many ways can a group of three people be chosen to work on a project?

What is the difference between these two problems? In the first problem the order that the runners finish the race matters. In the second problem the order in which the three people are chosen is not important, only which three people are chosen matters.

Permutation

A permutation is an arrangement of a set of items in which repeats are not allowed and order matters.

The number of permutations of \(n\) total items taken \(r\) at a time is given by:​​​

\[_{n} P_{r} = P(n, r) =\dfrac{n !}{(n-r) !} \label{permutation}\]

Note: Many calculators can calculate permutations directly. Look for a function that looks like \(_nP_r\) or \(P(n,r)\)

Example \(\PageIndex{4}\)

Assume that 10 cars are in a race. In how many ways can three cars finish in first, second and third place?

Solution

Repeats are not allowed and the order in which the cars finish is important. This is a permutation of 10 items taken 3 at a time.

Using the permutation formula (Equation \ref{permutation}):

\[P(10,3)=\dfrac{10 !}{(10-3) !}=\dfrac{10 !}{7 !}= \dfrac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 10 \cdot 9 \cdot 8 = 720 \nonumber\]

Note that all of the numbers from 7 down to 1 will cancel in the numerator and denominator, which leaves us with just \(10 \cdot 9 \cdot 8\). The calculation starts at \(n\) (which is 10) and you multiply \(r\) (which is 3) descending numbers, starting from \(n\).

You could have also used the Fundamental Counting Principle (Equation \ref{Fundamental Counting Principle}):

\[\underline{10} \cdot \underline{9} \cdot \underline{8} = 720 \nonumber\]

There are 720 different ways for cars to finish in the top three places.

Example \(\PageIndex{5}\)

The Circle K International Club has 18 members. An election is held to choose a president, vice-president and secretary. In how many ways can the 3 officers be chosen?

Solution

Repeats are not allowed and the order in which the officers are chosen matters, so this is a permutation.

Using the permutation formula (Equation \ref{permutation}):

\[P(18,3)=\dfrac{18 !}{(18-3) !}=\dfrac{18 !}{15 !}=18 \cdot 17 \cdot 16=4896 \nonumber\]

There are 4896 different ways the three officers can be chosen.

Try It \(\PageIndex{3}\)

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?

Answer

Since we are choosing 4 paintings out of 9 where repeats are not allowed and the order matters, there are \(_9 P_{4}=9 \cdot 8 \cdot 7 \cdot 6=3,024\) ways to display 4 out of 9 paintings on a wall.

Combinations

Choose a committee of two people from persons A, B, C, D and E. By the Fundamental Counting Rule there are \(5 \cdot 4 = 20\) ways to arrange the two people.

AB AC AD AE BA BC BD BE CA CB

CD CE DA DB DC DE EA EB EC ED

Committees AB and BA are the same committee. Similarly for committees CD and DC. Every committee is counted twice.

\[\frac{20}{2}=10 \nonumber\]

so there are 10 possible different committees.

Now choose a committee of three people from persons A, B, C, D and E. There are \(5 \cdot 4 \cdot 3 = 60\) ways to pick three people in order. Think about the committees with persons A, B and C. There are \(3! =6\) of them.

ABC ACB BAC BCA CAB CBA

Each of these is counted as one of the 60 possibilities but they are the same committee. Each committee is counted six times so there are

\[\frac{60}{6}=10 \, \text{different committees}. \nonumber\]

In both cases we divided the number of permutations by the number of ways to rearrange the people chosen.

The number of permutations of \(n\) people taken \(r\) at a time is \(P(n,r)\) and the number of ways to rearrange the people chosen is \(r!\). Putting these together we get

\[\begin{aligned}
\dfrac{n !}{\# \text { ways to arrange r items }} &=\dfrac{P(n, r)}{r !}=\dfrac{\dfrac{n!}{(n-r) !}}{\frac{r !}{1}} \\
&=\dfrac{n !}{(n-r) !} \cdot \dfrac{1}{r !} \\
&=\dfrac{n !}{(n-r) ! r !}
\end{aligned}\]

Combination

A combination is an arrangement of a set of items in which repeats are not allowed and the order does not matter. The number of combinations of \(n\) items taken \(r\) at a time is is given by:

\[_nC_r\ = C(n, r)=\dfrac{n !}{r !(n-r) !} \label{combination}\]

Note: Many calculators can calculate combinations directly. Look for a function that looks like \(_nC_r\) or \(C(n,r)\).

Example \(\PageIndex{6}\)

A student has a summer reading list of 8 books. The student must read 5 of the books before the end of the summer. In how many ways can the student read 5 of the 8 books?

Solution

Repeats are not allowed, and the order of the books is not important, only which books are read. This is a combination of 8 items taken 5 at a time.

\[C(8,5)=\dfrac{8 !}{5 !(8-5) !}=\dfrac{8 !}{5 ! 3 !}= \dfrac{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \dfrac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 8 \cdot 7 = 56\]

There are 56 ways to choose 5 of the books to read.

Try It \(\PageIndex{4}\)

A child wants to pick three pieces of Halloween candy to take in her school lunch box. If there are 13 pieces of candy to choose from, how many ways can she pick the three pieces?

Answer

This is a combination because it does not matter in what order the candy is chosen.

\[\begin{align*} C(13,3) &=\dfrac{13 !}{3 !(13-3) !}=\dfrac{13 !}{3 ! 10 !} \\[4pt] &= \dfrac{13 \cdot 12 \cdot 11 \cdot 10 \cdot 9\cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(3 \cdot 2 \cdot 1)(10 \cdot 9\cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1)} \\[4pt] &=\dfrac{13 \cdot 12 \cdot 11}{3 \cdot 2 \cdot 1} \\[4pt] &=\dfrac{1716}{6}=286 \end{align*}\]

There are 286 ways to choose the three pieces of candy to pack in her lunch.

Example \(\PageIndex{7}\)

A class consists of 15 men and 12 women. In how many ways can two men and two women be chosen to participate in an in-class activity?

Solution

This is a combination since repeats are not allowed and the order in which the people is chosen is not important.

Choose two men:

\[C(15,2)=\dfrac{15 !}{2 !(15-2) !}=\dfrac{15 !}{2 ! 13 !}=105 \nonumber\]

Choose two women:

\[C(12,2)=\dfrac{12 !}{2 !(12-2) !}=\dfrac{12 !}{2 ! 10 !}=66 \nonumber\]

We want 2 men and 2 women so by the Fundamental Counting Rule, we multiply these results.

\[105 \cdot 66 =6930 \nonumber\]

There are 6930 ways to choose two men and two women to participate.

Note: The difference between a combination and a permutation is whether order matters or not. If the order of the items is important, use a permutation. If the order of the items is not important, use a combination.

The following flow chart below may help with deciding which counting rule to use. Start at the top: ask yourself if the same item can be repeated. For instance, a person on a committee cannot be counted as two distinct people; however, a number on a car license plate may be used twice. If repeats are not allowed, then ask, does the order in which the item is chosen matter? If it does not, then use a combination. If it does, then ask if you are ordering the entire group. If so, use a factorial. If only ordering some from the total, use a permutation.

Probabilities Involving Permutations and Combinations

Now that we can calculate the number of permutations or combinations, we can use that information to calculate probabilities.

Example \(\PageIndex{8}\)

There are 20 students in a class. 12 of the students are women. The names of the students are put into a hat and 5 names are drawn. What is the probability that all of the chosen students are women?

Solution

This is a combination because repeats are not allowed and the order of the students is not important.

\[P(\text { all females })=\dfrac{\# \text { ways to pick } 5 \text { women }}{\# \text { ways to pick } 5 \text { students }}\]

The number of way to choose 5 women is

\[C(12,5)=792 \nonumber\]

The number of ways to choose 5 students is

\[C(20,5)=15,504 \nonumber\]

\[P(\text { all females })=\dfrac{\# \text { ways to pick } 5 \text { women }}{\# \text { ways to pick } 5 \text { students }}=\dfrac{792}{15,504}=0.051 \nonumber\]

The probability that all the chosen students are women is 0.051 or 5.1%.

Example \(\PageIndex{9}\)

The local Boys and Girls Club holds a duck race to raise money. Community members buy a rubber duck marked with a numeral between 1 and 30, inclusive. The box of 30 ducks is emptied into a creek and allowed to float downstream to the finish line. What is the probability that ducks numbered 5, 18 and 21 finish in first, second and third, respectively?

Solution

This is a permutation since repeats are not allowed and the order of finish is important.

\[P(\text{5, 18 & 21 finish 1st, 2nd & 3 rd})=\dfrac{\# \text { ways 5, 18 & 21 finish 1st, 2nd & 3rd}}{\# \text { ways any ducks can finish 1st, 2nd & 3rd }} \nonumber\]

There is only one way that the ducks can finish with #5 in first, #18 in second and #21 in third.

The number of ways any ducks can finish in first, second and third is

\[P(30,3)=24,360 \nonumber\]

\[ \begin{align*} P(\text{5, 18 & 21 finish 1st, 2nd & 3rd}) &=\dfrac{\# \text { ways 5, 18 & 21 finish 1st, 2nd & 3rd }}{\# \text { ways any ducks can finish 1st, 2nd & 3rd}} \\[4pt] &=\dfrac{1}{24,360} \approx 4.10 \times 10^{-5} \end{align*}\]

The probability that ducks numbered 5, 18 and 21 finish in first, second and third, respectively, is approximately 0.000041 or 0.0041%.

Try It \(\PageIndex{5}\)

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

Answer

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 \(10 \cdot 10 \cdot 10 \cdot 10=10^{4}=10,000\) total possible PIN numbers.

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

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 \(P(\text{no repeated digits in 4 digit PIN}) = \dfrac{_{10} P_{4}}{10^{4}}=\dfrac{5040}{10,000}=0.504\).

Example \(\PageIndex{10}\)

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.

Solution

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 be in any particular order, the number of possible outcomes of the lottery drawing is \(_{48} C_{6}=12,271,512\). Of these possible outcomes, only one would match all 6 numbers on the player’s ticket, so the probability of winning the grand prize is:

\(P(\text{win grand prize}) = \dfrac{_6 C_{6}}{_{48} C_{6}}=\frac{1}{12,271,512} \approx 0.0000000815\)

Try It \(\PageIndex{6}\)

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.

Answer

As above, the number of possible outcomes of the lottery drawing is \(_{48} C_{6}=12,271,512\). 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 one of the 42 losing numbers. The number of ways to choose 5 out of the 6 winning numbers is given by \(_{6} C_{5}=6\) and the number of ways to choose 1 out of the 42 losing numbers is given by \(_{42} C_{1}=42\). Thus the number of favorable outcomes is then given by the Fundamental Counting Rule: \(_{6} C_{5} \cdot_{42} C_{1}=6 \cdot 42=252\). So the probability of winning the second prize is:

\(P(\text{win second prize}) = \dfrac{\left(_{6} C_{5}\right)\left(_{42} C_{1}\right)}{_{48} C_{6}}=\dfrac{252}{12,271,512} \approx 0.0000205\)

Example \(\PageIndex{11}\)

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

Solution

In many card games (such as poker) repeats are not allowed and 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). Thus we use combinations to compute the possible number of 5-card hands, \(_{52} C_{5}\). 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 one Ace and 4 other cards (none of them Aces) from the deck. Since there are 4 Aces and we want exactly one of them, there will be \(_4 C_{1}\) ways to select one Ace; since there are 48 non-Aces and we want 4 of them, there will be \(_{48} C_{4}\)\) ways to select the four non-Aces. Now we use the multiplication principle to calculate that there will be \(_{4} C_{1} \cdot _{48} C_{4}\) ways to choose one Ace and 4 non-Aces.

Putting this all together, we have

\[P(\text {one Ace} )=\dfrac{\left(_{4} C_{1}\right)\left(_{48} C_{4}\right)}{_{52} C_{5}}=\dfrac{778,320}{2,598,960} \approx 0.29947 \nonumber\]

The probability of getting exactly one Ace in a 5-card hand is approximately 0.29947 or 29.95%.

Try It \(\PageIndex{7}\)

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

Answer

\[P(\text {3 Aces and 2 Kings})=\dfrac{\left(_{4} C_{3}\right)\left(_{4} C_{2}\right)}{_{52} C_{5}}=\dfrac{24}{2,598,960} \approx 0.0000092 \nonumber\]