What if you were picked to judge the pie contest at your local fair? You can pick three to move on to the finals from 10 entries. How many ways could you pick your three favorites? After completing this Concept, you'll be able to calculate permutations like this one using factorials.
Watch This
CK-12 Foundation: Permutations
Guidance
In this lesson we’ll be looking at ways of arranging things. To illustrate what we mean by this, let’s look at a simple example. Think about choosing your favorite color from the following list of choices; red, blue, green, yellow, pink, purple, orange, brown, black. Clearly there are nine different colors, so there are nine possible choices you could make.
Now think about choosing your top three colors in order of preference. There are many different ways you can choose the top three. You might choose red as your favorite, followed by black, then green. Someone else might choose the same three colors as you, but in a different order! When you are choosing items from a list and the order in which you choose them is important, the arrangement is called a permutation. How many different permutations do you think there are in this situation?
In this lesson, we’ll use counting methods to determine how many permutations a given situation has. We’ll also discover a formula to calculate permutations when counting alone is impractical.
Counting Permutations
In simple cases, sometimes it’s easiest to calculate permutations by just listing all the possibilities and counting them. Let’s examine a situation where it is relatively straightforward to do that.
Example A
Nadia and Peter are going to watch two movies on a rainy Saturday. Nadia will choose the first movie, and Peter gets to choose the second. The four movies they have to choose from are The Lion King, Aladdin, Toy Story and Pinocchio. Given that Peter will choose a different movie than Nadia, how many permutations are there for the movies they watch?
Solution
Since the order in which they watch the movies is important, and they don’t plan to choose the same movie twice, we can list all the different possibilities in a table:
First Movie | Second Movie |
---|---|
Lion King | Aladdin |
Lion King | Toy Story |
Lion King | Pinocchio |
Aladdin | Lion King |
Aladdin | Toy Story |
Aladdin | Pinocchio |
Toy Story | Lion King |
Toy Story | Aladdin |
Toy Story | Pinocchio |
Pinocchio | Lion King |
Pinocchio | Aladdin |
Pinocchio | Toy Story |
You can see that this table contains all the possibilities for the situation. There are four movies for Nadia to choose from. For every movie that Nadia chooses first, Peter has three choices left for his movie. By simply counting the rows in the table you can see that there are 12 permutations in this situation.
Example B
I have 5 cards with the numbers 1 through 5 on them. I take three cards and arrange them to form a 3-digit number. How many 3-digit numbers can I make?
Since the numbers we can make fit a numerical ordering pattern, we can list the possibilities in increasing order:
\begin{align*}& 123 \ 124 \ 125 \ 132 \ 134 \ 135 \ 142 \ 143 \ 145 \ 152 \ 153 \ 154\\ & 213 \ 214 \ 215 \ 231 \ 234 \ 235 \ 241 \ 243 \ 245 \ 251 \ 253 \ 254\\ & 312 \ 314 \ 315 \ 321 \ 324 \ 325 \ 341 \ 342 \ 345 \ 351 \ 352 \ 354\\ & 412 \ 413 \ 415 \ 421 \ 423 \ 425 \ 431 \ 432 \ 435 \ 451 \ 452 \ 453\\ & 512 \ 513 \ 514 \ 521 \ 523 \ 524 \ 531 \ 532 \ 534 \ 541 \ 542 \ 543\end{align*}
By arranging the table this way, you can see how the number of remaining choices decreases as we choose numbers. There are five choices for the first number, four choices for the second number and three choices for the third number. Counting the table entries gives a total of 60 permutations.
If we look closely at the last two examples we can see a pattern start to appear. Mathematicians love patterns—they tend to lead to formulas, which make life much easier! After all, why spend hours counting possibilities when a formula can calculate them in seconds?
In example A, Nadia had four choices and Peter had three. The number of permutations was \begin{align*}4 \times 3 = 12.\end{align*}
In example B there were 5 choices for the first digit, followed by 4 for the second digit, and then 3 for the third digit. The total number of permutations was \begin{align*}5 \times 4 \times 3 = 60\end{align*}.
In the introduction, we thought about picking our top three choices from a list of nine colors. You should now be able to do that. Even without listing all the possibilities, you can see that you have 9 choices for your favorite, 8 choices for your second favorite, and 7 choices for your third. The number of permutations is thus \begin{align*}9 \times 8 \times 7 = 504\end{align*}.
Factorial Notation
Look again at the color list in the introduction, and think this time about writing down every color in order of preference. You would have 9 choices for your favorite, followed by 8 choices for your second favorite, then 7, then 6, then 5, and so on. To determine the number of permutations for any possible list, we would perform the following calculation:
\begin{align*}\text{Color Permutations} = 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1\end{align*}
This sort of pattern crops up a great deal in statistics, probability and number theory. It’s so common that it has its own notation: \begin{align*}4 \times 3 \times 2 \times 1\end{align*} is written as 4! and is called four factorial. So the number of color permutations above is nine factorial = 9! = 362,880.
So what happens when we only want the first few terms in a factorial? For example, the number of permutations for arranging ALL the colors is 362,880, but the number of permutation for the top three is 504.
One way to get this result is to divide one factorial by another. Look at nine factorial divided by six factorial:
\begin{align*}\frac{9!}{6!} = \frac{9 \times 8 \times 7 \times \cancel{6} \times \cancel{5} \times \cancel{4} \times \cancel{3} \times \cancel{2} \times \cancel{1}}{\cancel{6} \times \cancel{5} \times \cancel{4} \times \cancel{3} \times \cancel{2} \times \cancel{1}} = 9 \times 8 \times 7 = 504\end{align*}
The terms in six factorial cancel out all but the first three terms in nine factorial. You should see that if we wanted the first four terms we would divide by 5!, or for only the first two terms we would divide by 7!. In general, however many terms we want to keep, we divide by the factorial of the quantity:
\begin{align*}(number \ of \ items \ in \ list) - (number \ of \ items \ we \ are \ choosing)\end{align*}
So to get the first five terms in twelve factorial we would use the formula \begin{align*}\frac{12!}{(12-5)!} = \frac{12!}{7!}\end{align*}.
Formulas like this are useful if you have a calculator that can handle factorials: you can just type in \begin{align*}\frac{12!}{7!}\end{align*} instead of \begin{align*}12 \times 11 \times 10 \times 9 \times 8\end{align*}. However, some factorials are too big for some calculators to handle, so in those cases you would need to simplify the fraction and do the multiplication by hand.
Example C
How many ways can Dale choose his favorite 5 songs from the current Billboard Hot \begin{align*}100^{TM}\end{align*}?
Solution
To find the answer, consider how many choices he has at each stage. For his first choice he has 100 songs to choose from, then 99, then 98 and so on. We need the first 5 terms only, so our calculation is:
\begin{align*}\text{Permutations} = \frac{100!}{(100-5)!} = \frac{100!}{95!} &= 100 \times 99 \times 98 \times 97 \times 96 \\ &= 9,034,502,400\end{align*}
Notice that that’s a pretty big number – far too large to count in a table! This is why we need formulas to help us count permutations.
Finding Permutations Using a Formula
We’ve just seen that a formula for determining the number of permutations for choosing 3 objects from a list of 9 objects is:
\begin{align*}\frac{9!}{6!} = \frac{9 \times 8 \times 7 \times \cancel{6} \times \cancel{5} \times \cancel{4} \times \cancel{3} \times \cancel{2} \times \cancel{1}}{\cancel{6} \times \cancel{5} \times \cancel{4} \times \cancel{3} \times \cancel{2} \times \cancel{1}} = 9 \times 8 \times 7 = 504 \ \text{permutations}\end{align*}
Now we’re ready to come up with a general formula for determining permutations. When we are choosing \begin{align*}r\end{align*} ordered items from a group of \begin{align*}n\end{align*} items, the number of permutations is given by the first \begin{align*}r\end{align*} terms in \begin{align*}n!\end{align*} We use the notation \begin{align*}_nP_r\end{align*} for this, and the general form for calculating permutations is:
\begin{align*}{_n}P_r = \frac{n!}{(n-r)!}\end{align*}
Example D
How many ways are there to choose a 5-song mix from a CD containing 12 tracks?
Solution
Choosing 5 from 12: \begin{align*}_{12}P_5 =\frac{12!}{(12-5)!}=\frac{12!}{7!} =12 \times 11 \times 10 \times 9 \times 8 = 95,040 \ ways\end{align*}
Watch this video for help with the Examples above.
CK-12 Foundation: Permutations
Vocabulary
- A permutation is when we are choosing \begin{align*}r\end{align*} ordered items from a group of \begin{align*}n\end{align*} items, where the order chosen matters. The number of permutations is given by the formula:
\begin{align*}{_n}P_r = \frac{n!}{(n-r)!}\end{align*}
Guided Practice
How many 3-letter “words” can be made from the letters in “computer”? (The words do NOT need to be real, or even pronounceable – for example “rtp” would count as a word)
Solution
Choosing 3 from 8: \begin{align*}_8P_3 =\frac{8!}{(8-3)!}=\frac{8!}{5!} =8 \times 7 \times 6 = 336 \ words\end{align*}
Practice
- In how many ways can the letters \begin{align*}a, b, c, d, e\end{align*} be arranged?
- In how many ways can the digits 1, 2, 3, 4, 5, 6, 7, 8, 9 be arranged?
- From a collection of 12 books, 5 are to be selected and placed in a particular order on a shelf. How many arrangements are possible?
- 3 cards are taken at random from a deck of 52 cards and laid in a row. How many possible outcomes are there for the card arrangements?
- How many distinct 3-letter permutations can you make from the letters in the word HEXAGON?
- How many distinct 2-letter permutations can you make from the letters in the word GEESE?
- A jukebox has 50 songs on it. If $1.00 pays for three songs, how many permutations are there for choosing 3 different songs?
For problems 8-16, evaluate the following:
- \begin{align*}_3P_1\end{align*}
- \begin{align*}_7P_1\end{align*}
- \begin{align*}_6P_2\end{align*}
- \begin{align*}_8P_8\end{align*}
- \begin{align*}_9P_3\end{align*}
- \begin{align*}_7P_3\end{align*}
- \begin{align*}_{19}P_7\end{align*}
- \begin{align*}_{99}P_3\end{align*}
- \begin{align*}_3P_0\end{align*}