3.6: Counting Methods

Last updated
Save as PDF

Page ID: 107215

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

Counting is as easy as 1-2-3, right? You already know how to count, or you wouldn’t be taking a college-level math class! Of course, but what we’ll really be investigating in this section is efficient ways of counting outcomes. Part of that task is learning what to count and what makes something different from something that we have already counted. The ultimate goal of learning to use different counting methods is so that we can integrate these methods into probability. So far the probability experiments we have worked with have had rather small numbers of outcomes. We could easily count the number of outcomes in the sample space and in the events. If there are a larger number of outcomes in the sample space, we need to develop other ways to count the outcomes without listing them all.

The Fundamental Counting Principle

The simplest of the counting methods is the Fundamental Counting Principle (FCP). This method is generally used when there are choices that must be made in succession and there are several options for each choice.

Example 1

Gretchen is remodeling her kitchen. For her kitchen design package, she must choose a type of floor, a type of counter, and a type of sink from the options shown in the table below. Gretchen wants to know how many different kitchen designs she could make with the options she has available.

$Gretchen's Kitchen Design Options Menu showing two choices for floor (tile or wood), two choices for counter (granite or formica), three choices for sink (white, steel, or stone.)$

Solution

A tree diagram is a useful tool to visually see all the possibilities. It can also help you organize the outcomes so that you don’t miss any of them. Start the tree diagram by listing one of the options for the Floor, branching off to each of the two options for the Counter. Make sure each option of Counter repeats for each branch of the Floor. This results in $2 \times 2 = 4$ Floor-Counter patterns.

$Tree diagram showing 4 ways to choose floor and counter.$

Next, make sure that each option for the Sink repeats for each of the 4 Floor-Counter patterns. The completed tree diagram of Gretchen's design choices is shown.

$Tree diagram showing 12 options for choosing floor, counter, and sink.$

We see that there are 12 possible outcomes for the kitchen design, and they are all listed on the right side of the tree diagram above.

While tree diagrams provide a visual layout of choice options and outcomes, they can take time to create -- especially when there are many options for the choices or when there are lots of choices of make. A quicker way to calculate the number of final outcomes when provided different options for at each stage of choice is to multiply together the number of options at each stage. We can use multiplication to calculate the number of different design packages that Gretchen can consider: $2 \times 2 \times 3 = 12$ design packages. This counting technique is called the Fundamental Counting Principle.

Fundamental Counting Principle

If there are $m$ possible outcomes for event $A$ and $n$ possible outcomes for event $B$, then there are a total of $m \times n$ possible outcomes for event $A$ followed by event $B$.

This principle can be generalized for three, four, or even more events.

Example 2

Let’s say that a person walks into a restaurant for a three course dinner. There are four different salads, three different entrees, and two different desserts to choose from. Assuming the person wants to eat a salad, an entree, and a dessert, how many different meals are possible?

Solution

There are three events: choose a salad, choose an entree, and choose a dessert. According to the Fundamental Counting Principle, multiply the number of outcomes possible at each event: $\underline{4} \times \underline{3} \times \underline{2} = 24$.

There are 24 different meals possible.

Try it Now 1

When purchasing a computer, the e-Box laptop computer offers customers several different options for screen, memory, and color as shown below. How many ways can a customer choose to personalize her selection of a new computer?

Screen: small, medium, or large
Memory: standard, 1 GB, or 2 GB
Color: pearl, gray, blue, or black

Answer: 36 ways

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

Example 3

Some license plates in Maryland consist of three letters followed by three digits. How many license plates of this type are possible if

There are 26 letters (A, B, C, ... Z) and 10 digits (0, 1, 2, 3, …, 9). \[\underbrace{(26 \cdot 26 \cdot 26)}_{\text{letters}} \cdot \underbrace{(10 \cdot 10 \cdot 10)}_{\text{digits}}=17,576,000 \text { license plates } \nonumber\]
Letters can be repeated but digits cannot? \[\underbrace{(26 \cdot 26 \cdot 26)}_{\text{letters}} \cdot \underbrace{(\underline{10} \cdot \underline{9} \cdot \underline{8})}_{\text{digits}} =12,654,720\, \text{ license plates} \nonumber\]
Both digits and letters can be repeated but the first digit cannot be zero. \[\underbrace{(26 \cdot 26 \cdot 26)}_{\text{letters}} \cdot \underbrace{(\underline{9} \cdot \underline{10} \cdot \underline{10})}_{\text{digits}} =15,818,400\, \text{ license plates} \nonumber\]
All letters and digits can be used but cannot be repeated. \[\underbrace{(\underline{26} \cdot \underline{25} \cdot \underline{24})}_{\text{digits}} \cdot \underbrace{(\underline{10} \cdot \underline{9} \cdot \underline{8})}_{\text{letters}}=11,232,000 \, \text{ license plates} \nonumber\]

Try it Now 2

How many 3-digit area codes can be formed where the first and last digits are odd, and digits cannot be repeated?

Answer: 180 area codes

Example 4

Four customers arrive at a grocery store checkout at the same time. In how many ways can the four people line up to pay for their items?

Solution:

We can solve this problem by thinking about making four successive choices. Any of the customers can be first so there are 4 options for the first choice. Then, there are 3 people left who can be second. Next, there are 2 customers left who can be third. Finally, there is only 1 person left to be last in the line.

Using the Fundamental Counting Principle there are $\underline{4} \times \underline{3} \times \underline{2} \times \underline{1} = 24$ ways for the four customers to line up.

The multiplication pattern above appears so often in counting that it has its own name, called a factorial, and its own symbol, which is '$!$'. We say “four factorial” and we write "$4!$".

Factorial

If $n$ is a counting number, then $n$ factorial ($n!)$ is defined as

$n! = n(n-1)(n-2)(n-3)...(2)(1)$

$0! = 1$

Example 5

Evaluate $5!$, $8!$, and $12!$.

$\begin{aligned} 5! &= 5 \times 4 \times 3 \times 2 \times 1 \\[4pt] &= 120 \end{aligned}$

$\begin{aligned}8! &= 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 \\[4pt] &= 40,320 \end{aligned}$

$\begin{aligned} 12! &= 12 \times 11 \times 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 \\[4pt] &= 479,001,600 \end{aligned}$

Factorials get very large, very fast. It is not pleasant to type so many factors when $n$ is large. Most scientific calculators have a factorial command. You can find this command on the TI calculator as follows:

$TI graphing calculator screen showing process to find 12 factorial.$

A calculator will express large values of factorials in scientific notation. As shown below, the TI calculator finds $40!$ to be almost $8.16 \times 10^{47}$.

$TI Graphing calculator screen showing result of 40 factorial.$

Examples 4 and 5 illustrate a type of common counting problem and method called a permutation. A permutation is an ordered arrangement of objects. The key to recognizing a permutation is that it is "ordered." For example, using only the three letters C, A, and T, there are six different three-letter permutations or sequences that we can make: ACT, ATC, CAT, CTA, TAC, and TCA.

If we add a fourth letter to the list, say S, then there are exactly 24 different four-letter permutations:

ACST CAST SACT TACS
ACTS CATS SATC TASC
ASCT CSAT SCAT TCAS
ASTC CSTA SCTA TCSA
ATCS CTAS STAC TSAC
ATSC CTSA STCA TSCA

Counting the number of ordered arrangements of the four letters C, A, T, S is the same problem as counting the number of ways four grocery customers can line up at the check out stand. Therefore, when counting how many ways a group of objects can be ordered, we use the factorial of the number of objects to be ordered.

Permutation

A permutation is an arrangement of a set of objects without repetition where a different order of the same set of objects counts as a different arrangement.

The number of permutations of $n$ different objects, taken altogether, is $n!$.

Example 6

The school orchestra is planning to play eight pieces of music at their next concert. In how many different ways can the pieces of music be sequenced in the program?

Solution

This is a permutation because the orchestra is arranging all 8 songs in an order to make the program. We can use the Fundamental Counting Principle or a factorial to count the number of ordered arrangements:

$\underline{8} \cdot \underline{7} \cdot \underline{6} \cdot \underline{5} \cdot \underline{4} \cdot \underline{3} \cdot \underline{2} \cdot \underline{1}=40,320$ or $8!=40,320$

There are 40,320 different ways of sequencing the songs in the program.

Try it Now 3

There are 6 DVD's to be placed on a shelf. In how many ways can they be placed on the shelf from left to right?

Answer: $6!=720$ ways

But what if the orchestra in the previous example has time to only play 5 of the 8 musical pieces. How many ways could the orchestra design the program of music? This is still a permutation but a slightly different question. This type of problem will be explored next.

Permutations

We now consider permutations of a set of objects taken from a larger set.

Example 7

The school orchestra has learned 8 pieces of music to play at their next concert. However, due to time restraints, they can only chose 5 pieces to play. In how many different ways can the pieces of music be chosen and sequenced in the program?

Solution

We can think of this as making 5 choices in a row: There are 8 options for the first song choice, 7 options for the second song choice, 6 options for the third song choice, 5 options for the fourth song choice, and 4 options for the fifth song choice. We can use the Fundamental Counting Principle to calculate the number of ways to choose and arrange the five pieces of music:

$\underline{8} \times \underline{7} \times \underline{6} \times \underline{5} \times \underline{4} = 6,720$ ways.

We say that the number of permutations of 8 songs taken 5 at a time is 6,720.

Notice that in this example of counting the number of ways to select and order only 5 of the 8 songs, we could not quite use $8!$ because not all 8 musical pieces are being used. Notice, however, that

$8 \times 7 \times 6 \times 5 \times 4 = \dfrac{8!}{3!} = \dfrac{8!}{(8-5)!}$.

We can generalize the preceding observation to create a formula for counting the number of permutations of $r$ objects from a group of $n$ objects.

Permutation Formula

The number of permutations of $n$ objects taken $r$ at a time is given by the formula

$_nP_r =\dfrac{n !}{(n-r) !}$.

It should be emphasized that a permutation problem is nothing more than a special case of a Fundamental Counting Principle problem. Using either strategy to count the number of permutations will arrive at the same answer.

Example 8

There are 10 cars in a race. In how many ways can three cars be awarded 1st, 2nd, and 3rd place?

Solution

The order in which the cars finish is important to consider when counting the number of ways the cars can finish. We say this is a "permutation of 10 choose 3" and can write it symbolically as $_{10}P_{3}$.

There are 10 possible cars which can finish first.
Once a car has finished first, there are 9 cars left which can finish second.
After the second car has finished, any of the 8 remaining cars can finish third.

Using the Fundamental Counting Principle, there are $\underline{10} \cdot \underline{9} \cdot \underline{8} = 720$ ways for cars to finish in the top three places.

Alternately, using the permutation formula,

$_{10}P_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} =\dfrac{10 \cdot 9 \cdot 8 \cdot \cancel{7} \cdot \cancel{6} \cdot \cancel{5} \cdot \cancel{4} \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}}{\cancel{7} \cdot \cancel{6} \cdot \cancel{5} \cdot \cancel{4} \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}} = 10 \cdot 9 \cdot 8 = 720 $

It should be noted that most calculators have a permutation command. On a TI calculator, it is found in the same menu as the factorial. To evaluate $_{10}P_3$ on the TI calculator, type the value of $n$, go to the MATH menu and move right to the PRB sub-menu, select the $_nP_r$ command, type the value of $r$, and press ENTER. Here is the sequence of screens.

$TI graphing calculator screen showing process to find 10 permutation 3.$

Example 9

There are 4 hooks in a row on a wall to hang some pictures. You have 7 pictures to display. Find the number of ways can you choose and arrange 4 pictures on the hooks from the group of 7 pictures.

Solution

The order in which the pictures are arranged is important. Choosing the same group of 4 pictures but placing them in a different order creates a different arrangement. This is a permutation of 7 choose 4, or $_{7}P_4$.

Using the Fundamental Counting Principle, there are 4 choices to make with 7 options for the first choice, 6 options for the second choice, 5 options for the third choice, and 4 options for the fourth choice:

$\underline{7} \cdot \underline{6} \cdot \underline{5} \cdot \underline{4} =840$ ways

Using the permutation formula,

$_{7}P_4=\dfrac{n !}{(n-r) !}=\dfrac{7 !}{(7-4) !}=\dfrac{7 !}{3 !}=\dfrac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1}=\dfrac{7 \cdot 6 \cdot 5 \cdot 4 \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}}{\cancel{3} \cdot \cancel{2} \cdot \cancel{1}}=7 \cdot 6 \cdot 5 \cdot 4=840$

There are 840 different ways the to choose and arrange 4 pictures on the hooks.

Example 10

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

Solution

The order in which the officers are chosen matters. Choosing the same three people but assigning them to a different role would make a different way of choosing the officers. That is, A as president, B as vice-president, and C as secretary is different from B as president, C and vice-president, and A as secretary. This is a permutation of 18 choose 3, or $_{18}P_3$.

Using the Fundamental Counting Principle, there are 3 choices to make with 18 options for the first choice, 17 options for the second choice, and 16 options for the third choice:

$\begin{array} {cccccc} {\underline{18}}&{\cdot}&{\underline{17}}&{\cdot}&{\underline{16}}&{ = 4896}\\ {\text{Pres.}}&{}&{\text{V.P.}}&{}&{\text{Sec.}}&{} \end{array}$

Using the permutation formula,

$_{18}P_3=\dfrac{n !}{(n-r) !}=\dfrac{18 !}{(18-3) !}=\dfrac{18 !}{15 !}=\dfrac{18 \cdot 17 \cdot 16 \cdot \cancel{15!}}{\cancel{15!}}=18 \cdot 17 \cdot 16=4,896$

To make the simplification a bit shorter, several of the factors of $18!$ in the numerator cancel with $15!$ in the denominator.

There are 4,896 different ways the three officers can be chosen.

Example 12

How many 5 character passwords can be made using the letters A through Z if letters can be used only once?

Solution

As we all know, the order in which you type the letters in your password matters! Using the correct letters in the password but in the wrong order won't unlock your account. Since a different order of the same five letters makes a different password, this is a permutation of 18 choose 3, or $_{18}P_3$.

Using the Fundamental Counting Principle,

$\underline{26} \cdot \underline{25} \cdot \underline{24} \cdot \underline{23} \cdot \underline{22} =7,893,600$

Using the permutation formula,

$_{26}P_5=\dfrac{n !}{(n-r) !}=\dfrac{26 !}{(26-5) !}=\dfrac{26 !}{21 !}=\dfrac{26 \cdot 25 \cdot 24 \cdot 23 \cdot 22 \cdot \cancel{21!}}{\cancel{21 !}}=26 \cdot 25 \cdot 24 \cdot 23 \cdot 22=7,893,600$

There are 7,893,600 different passwords made of only 5 letters of the alphabet.

Try it Now 4

Twelve actresses are available to be cast in a play that has five female roles. In how many ways could the 5 roles be cast?

Answer: 95,040 ways

Combinations

We have considered the situation where we chose $r$ items from a group of $n$ items where the order of selection is important in distinguishing one group from another. We now consider a similar situation in which the order of selection is not important.

A collection of items, in no particular order, is called a combination. Using our language of sets, a combination is a subset of a set of objects. For example, suppose that in a group of five students — Andy (A), Barry (B), Cheryl (C), Darren (D), and Ellen (E) — three students are to be selected to make a team. Each of the possible three-member teams is a combination. How many such combinations are there? We can answer this question by using our knowledge of permutations and the Fundamental Counting Principle.

If order did matter in the selection of the three students for the team, permutations would be counted as $_5P_3 = \frac{5!}{(5-3)!} = \frac{5!}{2!}=60$ teams. But, since order doesn’t matter in this case, this number of permutations counts more teams than there should be. We need to divide out the number of teams that have been repeated but are in a different order.

When order of team members makes no difference, the permutations ABC, ACB, BAC, BCA, CAB, and CBA are all really the same team, ABC. That is, there are six three-person permutations for each team of three people. This is consistent with the fact that three objects can be rearranged in $3!=6$ different ways.

To compute the number of possible combinations of three students chosen from a group of five students, we can divide the number of permutations by the number of repeated teams. So, one technique for counting the number of combinations of 5 objects chosen 3 at a time is

$_5C_3 = \dfrac{_5P_3}{3!} = \dfrac{60}{6} = 10 $ teams,

which could also be written as

$_5C_3 = \dfrac{_5P_3}{3!} = \dfrac{5!}{(5-3)!\;3!} = \dfrac{5!}{2!\;3!} = = \dfrac{5 \times 4 \times \cancel{3} \times \cancel{2} \times \cancel{1}}{(2 \times 1) \times (\cancel{3} \times \cancel{2} \times \cancel{1})}=10 $ teams.

We can generalize the preceding observations to write a formula for the number of combinations of $r$ objects selected from a group of $n$ objects.

Combination Formula

A combination is a selection of a set of objects without repetition in which the order of selection does not matter.

The number of combinations of $n$ objects is taken $r$ at a time is given by the formula

$_nC_r =\dfrac{_nP_r}{r!} = \dfrac{n !}{(n-r)!\;r!}$.

Example 13

A college class has a reading list of eight books. A student must choose and read five of the books before the end of the course. In how many ways can the student choose five books to read?

Solution

The order of selecting the books is not important, only which books are read. That is, as long as the same 5 books are selected it is the same choice no matter which order they are selected. We say this is a "combination of 8 choose 5" and can write it symbolically as $_{8}C_{5}$.

Using the formula for counting combinations and simplifying,

$C(8,5)=\dfrac{n !}{(n-r)! \;r!}=\dfrac{8 !}{(8-5)! \;5!}=\dfrac{8 !}{3 ! \times 5 !}= \dfrac{8 \times 7 \times 6 \times 5! }{3! \times 5!} = \dfrac{8 \times 7 \times 6 \times \cancel{5!} }{3! \times \cancel{5!}} = \dfrac{8 \times 7 \times 6 }{ 3 \times 2 \times 1} = \dfrac{8 \times 7 \times 6 }{6}= \dfrac{8 \times 7 \times \cancel{6} }{ \cancel{6}} = 8 \times 7 = 56$

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

As with permutations, most calculators have a combination command. On the TI calculator, it is found in the same menu as factorial and permutation. To find $_{8}C_5$ on the TI calculator, type the value of $n$, go to the MATH menu and move right to the PRB sub-menu, select the $_nC_r$ command, type the value of $r$, and press ENTER. Here is the sequence of screens.

$TI graphing calculator screen showing process to find 8 combination 5 is 56.$

Example 14

A child wants to pick three pieces of 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?

Solution

This is a combination because it does not matter in what order the candy is chosen. The same 3 pieces selected in any order gives the child the same candies. This is a combination of 13 choose 3, or $_{13}C_3$.

Using the combination formula,

$ _{13}C_3 =\dfrac{n !}{(n-r)! \; r!} =\dfrac{13 !}{(13-3)! \; 3!} = \dfrac{13 !}{10! \times 3!} = \dfrac{13 \times 12 \times 11 \times 10! }{10! \times 3!} = \dfrac{13 \times 12 \times 11 \times \cancel{10!} }{\cancel{10!} \times 3!} = \dfrac{13 \times 12 \times 11 }{ 3 \times 2 \times 1} = \dfrac{1716 }{6}= 286 $

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

Example 15

The Volunteer Club has 18 members. A committee of members will be selected to plan the annual food drive. How many different 3-person committees can be selected?

Solution

Unlike selecting members for officers where each officer serves a different role, the order in which the members are chosen for a committee is not meaningful. Choosing the same group of three people but in a different order results in the same committee of three people. This is a combination of 18 choose 3, or $_{18}C_3$.

$_{18}C_3 =\dfrac{n !}{(n-r)! \; r!} =\dfrac{18 !}{(18-3)! \; 3!} =\dfrac{18 !}{15 ! \times 3 !} = \dfrac{18 \times 17 \times 16 \times 15! }{15! \times 3!} = \dfrac{18 \times 17 \times 16 \times \cancel{15!}} {\cancel{15!} \times 3!} = \dfrac{18 \times 17 \times 16 }{ 3 \times 2 \times 1} = \dfrac{4896 }{6}= 816 $

You could have also used the result from Example 10:

$_{18}C_3 = \dfrac{_{18}P_3}{3!}=\dfrac{4896}{6}=816$.

There are 816 ways to choose a committee of three members.

Try it Now 5

You have 4 extra tickets to the Nationals game and 9 of your friends want to go. How many ways can you select a group of friends to join you at the game?

Answer: 126 ways

Simplifying permutations and combinations by hand can be tedious for large quantities so most of the time we will want to use technology. The difficulty for most people is knowing whether a problem calls for a permutation, a combination, or only the Fundamental Counting Principle. The table gives a quick summary:

Distinguishing between Fundamental Counting Principle, Permutation, and Combination
Fundamental Counting Principle	Counts the number of ways for event $A$ followed by event $B$ when event $A$ has $m$ outcomes and event $B$ has $n$ outcomes: $m \times n$ Can be used with a sequence of more than 2 events. May be used with or without repetitions. Particularly useful when there are specific placement requirements or conditions to meet (e.g. first digit must be odd.)
Permutation	Counts the number of ways to select $r$ items from a group of $n$ items when the order of items is important $_nP_r = \dfrac{n!}{(n-r)!}$ ABC is different than BAC. Items cannot be repeated. May also be solved using the Fundamental Counting Principle.
Combination	Counts the number of ways to select $r$ items from a group of $n$ items when the order of items is not important $_nC_r = \dfrac{n!}{(n-r)!\; r!}$ ABC is the same as BAC. Items cannot be repeated. May also be solved by dividing the number of permutations by $r!$

In the examples that follow, we concentrate on identifying which method to use and calculate with technology.

Example 16

A jury pool consists of 20 people. How many different 12-person juries can be selected from the jury pool?

Solution

Choosing the same 12 people in a different order for the jury would not result in a different outcome. Order does not make a difference so this is a combination: $_{20}C_{12} = 125,970$ juries.

Example 17

A swimming event has 16 contestants. The swimmers with the five fastest speeds will be listed, in the order of their speed, on the leader board. How many ways are there for the names of five swimmers to be listed?

Solution

Listing the same 5 names in a different order on the leader board would be a different result to the race. Order is important so this is a permutation: $_{16}P_5 = 524,160$ ways.

Example 18

You are completing a four-question survey on your experience at Taco Bell. You can answer Below Average, Average, or Above Average for each question. In how many different ways could you answer this survey?

Solution

Recall that when items can be selected more than once you cannot use the permutation or combination formulas. It is possible to respond "Average" to more than one of the four questions. There are four choices to be made, and there are three options for each choice. Use the Fundamental Counting Principle: $\underline{3} \times \underline{3} \times \underline{3} \times \underline{3} = 81$ ways.

Example 19

When playing poker, players are dealt 5 cards from a regular deck of cards. How many different hands of poker could a player be dealt?

Solution

Receiving the same five cards but in a different order would not mean that you had a different set of cards. Order does not make a difference so this is a combination: $_{52}C_{5} = 2,598,960$ hands.

Try it Now 6

Decide whether the scenario requires permutations, combinations, or the Fundamental Counting Principle. Then, use technology to compute the answer.

Four of 15 people attending a meeting will be selected to receive door prizes. One receives a book, one receives a gift card, one receives a notepad, and another receives a box of candy. In how many ways can the door prizes be awarded?
A serial number is formed using two letters of the alphabet, followed by two digits, followed by another letter of the alphabet. If letters and digits can be repeated, how many different serial numbers can be formed?
There are 12 standby passengers who hope to get on a flight to Hawaii, but only 6 seats are available on the plane. How many different ways can the 6 people be selected?

Answer

permutation: 32,760 ways
Fundamental Counting Principle: 1,757,600 serial numbers
combination: 924 ways

Using More than One Method

Sometimes a counting problem may require more than one counting method. For example, you may need to compute combinations and use the Fundamental Counting Principle together. Let's look at a relatively simple but common example.

Example 20

A sandwich shop offers a special: choose exactly one kind of bread, one kind of protein, and three toppings from the menu below and get a special price. How many ways can a customer select menu items for the special?

$Sandwich menu showing bread choices (white, wheat), protein choices (ham, turkey, roast beef, cheese), and vegetable topics (lettuce, pickle, onion, tomato, hot peppers.)$

Solution

This problem looks very similar to examples where we used the Fundamental Counting Principle. However, in those problems, we chose only one option for each stage of choice. Here, we are choosing one type of bread, one type of protein, but three types of vegetable toppings.

The Fundamental Counting Principle can be applied by multiplying the number of ways a bread can be selected (2), the number of ways a protein can be selected (4), and the number of ways 3 vegetables can be selected from 5 vegetables $(_5C_3=10)$:

$\underline{2} \times \underline{4} \times \underline{_5C_3} = 2 \times 4 \times 10 = 80$.

So, there are 80 different ways of selecting menu items for he special.

Example 21

Brenda will choose 5 movies to rent over the weekend, and she has decided to rent 3 science fiction movies and 2 comedies. She can choose from 6 science fiction movies and 4 comedies. How many different ways can Brenda choose the group of 5 movies?

Solution

There are two different stages to selecting the group of movies.

First, compute how many ways Brenda can select 3 science fiction movies from a group of 6 science fiction movies using $_6C_3=\frac{6!}{(6-3)! \; 3!} = 20$.

Then, compute how many ways Brenda can choose 2 comedies from the group of 4 comedies using $_4C_2= \frac{4!}{(4-2)! \; 2!} = 6$.

Each group of science fiction movies can be paired with each group of the comedies so we use the Fundamental Counting Principle to find how many different groups of 3 science fiction movies and 2 comedies can be selected together:

$_6C_3 \times _4C_2 = 20 \times 6 = 120$.

There are 120 ways for Brenda to choose her group of 5 movies.

Try it Now 7

An art gallery has a total of 11 paintings by a certain artist. Of these paintings, 5 are oil paintings and 6 are watercolor paintings. The art gallery will display a special exhibition of this artist’s work but is restricted to showing only 7 paintings. Calculate the number of ways in which the 7 paintings can be selected for the exhibition if it includes 3 oil paintings and 4 watercolor paintings.

Answer: 150 ways

In the next section we will apply these counting methods when we return to calculating theoretical probability.

Fundamental Counting Principle	Counts the number of ways for event \(A\) followed by event \(B\) when event \(A\) has \(m\) outcomes and event \(B\) has \(n\) outcomes: \(m \times n\) Can be used with a sequence of more than 2 events. May be used with or without repetitions. Particularly useful when there are specific placement requirements or conditions to meet (e.g. first digit must be odd.)
Permutation	Counts the number of ways to select \(r\) items from a group of \(n\) items when the order of items is important \(_nP_r = \dfrac{n!}{(n-r)!}\) ABC is different than BAC. Items cannot be repeated. May also be solved using the Fundamental Counting Principle.
Combination	Counts the number of ways to select \(r\) items from a group of \(n\) items when the order of items is not important \(_nC_r = \dfrac{n!}{(n-r)!\; r!}\) ABC is the same as BAC. Items cannot be repeated. May also be solved by dividing the number of permutations by \(r!\)