Skip to main content

Section 8.2 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 8.2.1.

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

Solution.

This problem is a bit different. Instead of choosing one item from each of several different categories, we are repeatedly choosing items from the same category (the category is: the letters of the word MATH) and each time we choose an item we do not replace it, so there is one fewer choice at the next stage: we have 4 choices for the first letter (say we choose A), then 3 choices for the second (M, T and H; say we choose H), then 2 choices for the next letter (M and T; say we choose M) and only one choice at the last stage (T). Thus there are \(4 \cdot 3 \cdot 2 \cdot 1=24\) ways to spell a code worth with the letters MATH.

In this example, we needed to calculate \(n \cdot \left(n - 1 \right) \cdot \left( n - 2 \right) \ldots 3 \cdot 2 \cdot 1\text{.}\) This calculation shows up often in mathematics, and is called the factorial, and is notated \(n!\)

Definition 8.2.2. Factorial.
\begin{equation*} n! = n \cdot \left(n - 1\right) \cdot \left(n - 2 \right) \cdot \cdots 3 \cdot 2 \cdot 1 \end{equation*}
Example 8.2.3.

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

Solution.
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.

Now we will consider some slightly different examples.

Example 8.2.4.

A charity benefit is attended by 25 people and three gift certificates are given away as door prizes: one gift certificate is in the amount of $100, the second is worth $25 and the third is worth $10. Assuming that no person receives more than one prize, how many different ways can the three gift certificates be awarded?

Solution.

Using the Basic Counting Rule, there are 25 choices for the person who receives the $100 certificate, 24 remaining choices for the $25 certificate and 23 choices for the $10 certificate, so there are \(25\cdot 24 \cdot 23=13,800\) ways in which the prizes can be awarded.

Example 8.2.5.

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?

Solution.

Using the Basic Counting Rule, there are 8 choices for the gold medal winner, 7 remaining choices for the silver, and 6 for the bronze, so there are \(8 \cdot 7 \cdot 6=336\) ways the three medals can be awarded to the 8 runners.

Note that in these preceding examples, the gift certificates and the Olympic medals were awarded without replacement; that is, once we have chosen a winner of the first door prize or the gold medal, they are not eligible for the other prizes. Thus, at each succeeding stage of the solution there is one fewer choice (25, then 24, then 23 in the first example; 8, then 7, then 6 in the second). Contrast this with the situation of a multiple choice test, where there might be five possible answers — A, B, C, D or E — for each question on the test.

Note also that the order of selection was important in each example: for the three door prizes, being chosen first means that you receive substantially more money; in the Olympics example, coming in first means that you get the gold medal instead of the silver or bronze. In each case, if we had chosen the same three people in a different order there might have been a different person who received the $100 prize, or a different goldmedalist. (Contrast this with the situation where we might draw three names out of a hat to each receive a $10 gift certificate; in this case the order of selection is not important since each of the three people receive the same prize. Situations where the order is not important will be discussed in the next section.)

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

\begin{equation*} n \cdot \left(n - 1 \right) \cdot \left(n - 2 \right) \cdots \left(n - r + 1\right) \end{equation*}

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

Definition 8.2.6. Permutations.

We say that there are \(_{n} P_{r}\) permutations of size \(r\) that may be selected from among \(n\) choices without replacement when order matters.

\begin{equation*} _{n} P_{r} = n \cdot \left(n - 1 \right) \cdots \left(n - r + 1\right) \end{equation*}

It turns out that we can express this result more simply using factorials.

\begin{equation*} _{n} P_{r} = \frac{n!}{\left(n - r\right)!} \end{equation*}

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

Example 8.2.7.

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

Solution.

Since we are choosing 4 paintings out of 9 without replacement where the order of selection is important there are \(_9 P_4 = 9 \cdot 8 \cdot 7 \cdot 6 = 3,024\) permutations.

Example 8.2.8.

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

Solution.

We want to choose 4 people out of 16 without replacement and where the order of selection is important. So the answer is \(_{16} P_{4} = 16 \cdot 15 \cdot 14 \cdot 13 = 43,680\text{.}\)

Problem 8.2.9. Try It Now.

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

Answer.

  1. \(\displaystyle 26^5=11,881,376\)

  2. \(\displaystyle _{26}P_5 = 26 \cdot 25 \cdot 24 \cdot 23 \cdot 22 = 7,893,600\)