### Permutations and Combinations

Let's start by looking at an example that can be calculated using the Multiplication Rule for Counting:

#### Using the Multiplication Rule for Counting

Suppose there are 30 candidates that are competing for three executive positions. How many different ways can you fill the three positions?

Since there are three executive positions and 30 candidates, let \begin{align*}n_1 =\end{align*} the number of candidates that are available to fill the first position, \begin{align*}n_2 =\end{align*} the number of candidates remaining to fill the second position, and \begin{align*}n_3 =\end{align*} the number of candidates remaining to fill the third position.

Hence, we have the following:

\begin{align*}n_1& =30\\ n_2& =29\\ n_3& =28\end{align*}

The number of different ways to fill the three executive positions with the given candidates is \begin{align*}(n_1)(n_2)(n_3)=(30)(29)(28)=24,360.\end{align*}

The arrangement of elements in a distinct order, as the example above shows, is called a **permutation**. Thus, from the example above, there are 24,360 possible permutations of three elements drawn from a set of 30 elements.

**Counting Rule for Permutations**

The **Counting Rule for Permutations** states the following:

The number of ways to arrange \begin{align*}n\end{align*} different objects in order within \begin{align*}r\end{align*} positions is \begin{align*}P^n_r=\frac{n!}{(n-r)!}\end{align*}.

#### Using the Counting Rule for Permutations

1. Let’s compute the number of ordered seating arrangements we have with 8 people and only 5 seats.

In this case, we are considering a total of \begin{align*}n=8\end{align*} people, and we wish to arrange \begin{align*}r=5\end{align*} of these people to be seated. Substituting into the permutation equation, we get the following:

\begin{align*}P^n_r& =\frac{n!}{(n-r)!}\\ & =\frac{8!}{(8-5)!}\\ & =\frac{8!}{3!}\\ & =\frac{40,320}{6}\\ & =6,720\end{align*}

Another way of solving this problem is to use the Multiplicative Rule of Counting. Since there are only 5 seats available for 8 people, for the first seat, there are 8 people available. For the second seat, there are 7 remaining people available, since one person has already been seated. For the third seat, there are 6 people available, since two people have already been seated. For the fourth seat, there are 5 people available, and for the fifth seat, there are 4 people available. After that, we run out of seats. Thus, \begin{align*}(8)(7)(6)(5)(4) = 6,720\end{align*}.

#### Exceptions of the Counting Rule for Permutations

The board of directors at The Orion Foundation has 13 members. Three officers will be elected from the 13 members to hold the positions of a provost, a general director, and a treasurer. How many different slates of three candidates are there if each candidate must specify which office he or she wishes to run for?

Each slate is a list of one person for each of three positions: the provost, the general director, and the treasurer. If, for example, Mr. Smith, Mr. Hale, and Ms. Osborn wish to be on the slate together, there are several different slates possible, depending on which one will run for provost, which one will run for general director, and which one will run for treasurer. This means that we are not just asking for the number of different groups of three names on the slate, but we are also asking for a specific order, since it makes a difference which name is listed in which position.

When computing the answer, \begin{align*}n = 13\end{align*} and \begin{align*}r = 3\end{align*}.

Using the permutation formula, we get the following:

\begin{align*}P^n_r& =\frac{n!}{(n-r)!}\\ & =\frac{13!}{(13-3)!}\\ & =\frac{(13)(12)(11)(10!)}{10!}\\ & =(13)(12)(11)\\ & =1,716\end{align*}

Thus, there are 1,716 different slates of officers possible.

Notice that in our previous examples, the order of people or objects was taken into account. What if the order is not important? For example, in the previous example for electing three officers, what if we wish to choose 3 members of the 13 member board to attend a convention. Here, we are more interested in the group of three, but we are not interested in their order. In other words, we are only concerned with different **combinations** of 13 people taken 3 at a time. The permutation formula will not work here, since, in this situation, order is not important. However, we have a new formula that will compute different combinations.

**Counting Rule for** Combinations

The **Counting Rule for Combinations** states the following:

The number of combinations of \begin{align*}n\end{align*} objects taken \begin{align*}r\end{align*} at a time is \begin{align*}C^n_r=\frac{n!}{r!(n-r)!} \end{align*}.

It is important to notice the difference between permutations and combinations. When we consider grouping and order, we use permutations, but when we consider grouping with no particular order, we use combinations.

#### Using the Counting Rule for Combinations

How many different groups of 3 are possible when taken out of 13 people?

Here, we are interested in combinations of 13 people taken 3 at a time. To find the answer, we can use the combination formula: \begin{align*}C^n_r=\frac{n!}{r!(n-r)!}.\end{align*}

\begin{align*}C^{13}_3=\frac{13!}{3!(13-3)!} = 286\end{align*}

This means that there are 286 different groups of 3 people to go to the convention.

In the above computation, you can see that the difference between the formulas for \begin{align*}_nC_r\end{align*} and \begin{align*}_nP_r\end{align*} is the factor \begin{align*}r!\end{align*} in the denominator of the fraction. Since \begin{align*}r!\end{align*} is the number of different orders of \begin{align*}r\end{align*} objects, and combinations ignore order, we divide by the number of different orders.

### Technology Notes

*Computing Factorials, Permutations and Combination on the TI-83/84 Calculator*

Press **[MATH]**, and then scroll to the right and choose **PRB**. You will see the following choices, among others: '2:nPr', '3:nCr'. and '4:!'. The screenshots below show the menu and the proper uses of these commands.

*Technology Note: Using EXCEL to Computer Factorials, Permutations and Combinations*

In Excel, the commands shown above are entered as follows:

\begin{align*}=\end{align*}PERMUT(10,2)

\begin{align*}=\end{align*}COMBIN(10,2)

\begin{align*}=\end{align*}FACT(10)

### Example

#### Example 1

You are taking a philosophy course that requires you to read 5 books out of a list of 10 books. You are free to select any 5 books and read them in whichever order that pleases you. How many different combinations of 5 books are available from a list of 10?

Since consideration of the order in which the books are selected is not important, we compute the number of combinations of 10 books taken 5 at a time. We use the combination formula as is shown below:

\begin{align*}C^n_r & = \frac{n!}{r!(n-r)!}\\ C^{10}_5 & =\frac{10!}{5!(10-5)!} = 252\end{align*}

This means that there are 252 different groups of 5 books that can be selected from a list of 10 books.

### Review

- How many different 5-card hands can be chosen from a 52-card deck?
- Evaluate the following:
- \begin{align*}_5C_4\end{align*}
- \begin{align*}_5P_4\end{align*}
- \begin{align*}_9C_3\end{align*}
- \begin{align*}_{16}C_{5}\end{align*}

- How many ways can you plant a rose bush, a lavender bush and a hydrangea bush in a row?
- How many ways can you pick 4 people out of 28 for the prom committee?
- How many ways can you pick a president, a vice president, a secretary and a treasurer out of 28 people for student council?
- Janine has 10 different songs on a playlist. If her music program randomly shuffles the songs, how many ways can the songs be ordered?
- In the New Jersey ``Pick Six" lotto game, a player chooses six different numbers from 1 to 49. The six winning numbers for the lottery are chosen at random. If the player matches all six numbers, she wins the jackpot, which starts at $2 million. Is this a permutation or a combination? Express the number of sets of 6 numbers using the notation you learned in this Concept. You do not have to calculate what the number is.
- Suppose you have a jar with 10 different colored marbles. How many ways are there to:
- draw 5 marbles out, one at a time?
- draw 3 marbles out at the same time?

- In North America, phone numbers have the form XXX-XXX-XXXX. The first three digits give the area code, and the second three digits indicate the exchange.
- Nick lives in North Carolina where the area code is 828. If there were no restrictions on the remaining seven digits, how many phone numbers would be possible in the 828 area code?
- In fact, exchanges cannot begin with 0 or 1. How many possible numbers are there in the 828 area code, subject to this restriction?

- Explain the differences and similarities between permutations and combinations.

### Review (Answers)

To view the Review answers, open this PDF file and look for section 3.7.