12.2: Permutations and Combinations
- Page ID
- 92814
Consider the following counting problems:
- In how many ways can three runners finish a race?
- 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.
A permutation is an arrangement of a set of items. The number of permutations of n items taking r at a time is given by:
\[P(n, r)=\frac{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)\)
Let’s look at a simple example to understand the formula for the number of permutations of a set of objects. Assume that 10 cars are in a race. In how many ways can three cars finish in first, second and third place? The order in which the cars finish is important. Use the multiplication principle. There are 10 possible cars to finish first. Once a car has finished first, there are nine cars to finish second. After the second car is finished, any of the eight remaining cars can finish third. 10 x 9 x 8 = 720. This is a permutation of 10 items taking three at a time.
Using the permutation formula:
\[P(10,3)=\frac{10 !}{(10-3) !}=\frac{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\]
Using the 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.
The school orchestra is planning to play six pieces of music at their next concert. How many different programs are possible?
Solution
This is a permutation because they are arranging the songs in order to make the program. Using the permutation formula:
\[P(6,6)=\frac{6 !}{(6-6) !}=\frac{6 !}{0 !}=\frac{720}{1}=720 \nonumber\]
Using the fundamental counting principle:
\[\underline{6} \cdot \underline{5} \cdot \underline{4} \cdot \underline{3} \cdot \underline{2} \cdot \underline{1}=720 \nonumber\]
There are 720 different ways of arranging the songs to make the program.
The Volunteer Club has 18 members. An election is held to choose a 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 so this is a permutation.
Using the permutation formula:
\[P(18,3)=\frac{18 !}{(18-3) !}=\frac{18 !}{15 !}=18 \cdot 17 \cdot 16=4896 \nonumber\]
Note: All digits in 18! in the numerator from 15 down to one will cancel with the 15! in the denominator.
Using the fundamental principle:
\(\begin{array} {cccccc} {\underline{18}}&{\cdot}&{\underline{17}}&{\cdot}&{\underline{16}}&{ = 4896}\\ {\text{Pres.}}&{}&{\text{V.P.}}&{}&{\text{Sec.}}&{} \end{array}\)
There are 4896 different ways the three officers can be chosen.
Another notation for permutations is \(_nP_r\). So, \(P(18,3)\) can also be written as \(_{18}P_3\). Most scientific calculators have an \(_nP_r\) button or function.
Combinations are when the order does not even matter. We are just collecting objects together.
Choose a committee of two people from persons A, B, C, D and E. By the multiplication principle 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 taking 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}
\frac{n !}{\# \text { ways to arrange r items }} &=\frac{P(n, r)}{r !}=\frac{(n-r) !}{\frac{r !}{1}} \\
&=\frac{n !}{(n-r) !} \cdot \frac{1}{r !} \\
&=\frac{n !}{(n-r) ! r !}
\end{aligned}\]
A combination is a selection of objects in which the order of selection does not matter. The number of combinations of n items taking r at a time is:
\[C(n, r)=\frac{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)\).
A student has a summer reading list of eight books. The student must read five of the books before the end of the summer. In how many ways can the student read five of the eight books?
Solution
The order of the books is not important, only which books are read. This is a combination of eight items taking five at a time.
\[C(8,5)=\frac{8 !}{5 !(8-5) !}=\frac{8 !}{5 ! 3 !}= \dfrac{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{5 \times 4 \times 3 \times 2 \times 1 \times 3 \times 2 \times 1} = \dfrac{8 \times 7 \times 6}{3 \times 2 \times 1} = 8 \times 7 = 56\]
There are 56 ways to choose five of the books to read.
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?
Solution
This is a combination because it does not matter in what order the candy is chosen.
\[\begin{align*} C(13,3) &=\frac{13 !}{3 !(13-3) !}=\frac{13 !}{3 ! 10 !} \\[4pt] &= \dfrac{13 \times 12 \times 11 \times 10 \times 9\times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1)(10 \times 9\times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1)} \\[4pt] &=\frac{13 \times 12 \times 11}{3 \times 2 \times 1} \\[4pt] =\frac{1716}{6}=286 \end{align*}\]
There are 286 ways to choose the three pieces of candy to pack in her lunch.
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.
Now here are a couple examples where we have to figure out whether it is a permuation or a combination.
A serial number for a particular model of bicycle consists of a letter followed by four digits and ends with two letters. Neither letters nor numbers can be repeated. How many different serial numbers are possible?
Solution
This is a permutation because the order matters.
Use the multiplication principle to solve this. There are 26 letters and 10 digits possible.
\[26 \cdot 10 \cdot \underline{9} \cdot \underline{8} \cdot \underline{7} \cdot \underline{25} \cdot \underline{24}=78,624,000\]
There are 78,624,000 different serial numbers of this form.
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 the order in which the people is chosen is not important.
Choose two men:
\[C(15,2)=\frac{15 !}{2 !(15-2) !}=\frac{15 !}{2 ! 13 !}=105 \nonumber\]
Choose two women:
\[C(12,2)=\frac{12 !}{2 !(12-2) !}=\frac{12 !}{2 ! 10 !}=66 \nonumber\]
We want 2 men and 2 women so multiply these results.
\[105(66)=6930 \nonumber\]
There are 6930 ways to choose two men and two women to participate.