topic badge

8.03 Permutations and combinations

Lesson

Concept summary

To find the number of ways a set of r objects can be chosen or arranged from a set of n objects, we can use the fundamental counting principle, factorials, combinations or permutations as appropriate.

Fundamental Counting Principle

To find the number of ways multiple events can happen one after the other, multiply the number of ways each event can happen together.

To find the number of ways that event A, then event B, then event C, \ldots can happen, we multiply the number outcomes of each event together.

\displaystyle n(A, B, C, ...)=n(A) \cdot n(B) \cdot n(C) \cdot ...
\bm{A}
is one event, where n(A) is the number of outcomes that event has
\bm{B}
is another event, where n(B) is the number of outcomes that event has
\bm{C}
is another event, where n(C) is the number of outcomes that event has
Factorial

The number of ways in which a set of n objects can be ordered or arranged. The notation is n!, where n is a positive integer greater or equal to zero. It is calculated by multiplying n by every positive integer less than n all the way down to 1.

Example:

\begin{aligned} 4! &= 4\cdot 3\cdot 2 \cdot 1 \\ &= 24\end{aligned}

\displaystyle n!=n \cdot (n-1) \cdot (n-2) \cdot \ldots 2 \cdot 1
\bm{n}
a positive integer greater or equal to zero

An important property of factorial notation is 0!=1. This property makes it possible to perform more complex calculations.

Permutation

The number of ways in which a set of r objects can be ordered or arranged from a set of n objects. The notation is \text{}_n P_r.

Example:

\begin{aligned} \text{}_5 P_3 &= \dfrac{5!}{(5-3)!} \\ &= 60 \end{aligned}

\displaystyle \text{}_n P_r = \dfrac{n!}{(n-r)!}
\bm{r}
the number of objects that are being chosen
\bm{n}
the number of objects that are being chosen from
Combination

The number of ways in which a set of r objects can be chosen from a set of n objects. The notation is \text{}_n C_r.

Example:

\begin{aligned} \text{}_5 C_3 &= \dfrac{5!}{3!(5-3)!} \\ &= 10 \end{aligned}

For combinations we do not care about the order or arrangement of the objects. So we calculate the number of combinations by dividing the number of permutations by r!.

\displaystyle \text{}_n C_r = \dfrac{n!}{r!(n-r)!}
\bm{r}
the number of objects that are being chosen
\bm{n}
the number of objects that are being chosen from

n!, \text{}_n P_r and \text{}_n C_r can be calculated by either the above formulas or by using your calculator. Example 1 below will use the formulas, while Example 2 will use a calculator.

Worked examples

Example 1

For each of the following scenarios, use either a permutation, a combination, or the counting principle to solve the problem.

a

A bakery has a selection of 10 different cupcakes, 8 different donuts, and 6 different muffins. If you want to buy one of each, how many different choices do you have?

Approach

This problem requires finding the number of ways multiple events can happen. The fundamental counting principle is appropriate for solving the problem.

To find the number of different choices we multiply the number of outcomes for each event.

Solution

\begin{aligned} n(\text{cupcakes})\cdot n(\text{donuts})\cdot n(\text{muffins}) &= 10\cdot 8 \cdot 6 \\ &=480 \end{aligned}

Therefore, there are 480 different choices.

b

Suppose that 7 people enter a marathon. Assuming that there are no ties, determine the number of ways that a gold, silver, and bronze medal could be awarded.

Approach

This problem requires finding the number of ways to order or arrange 3 objects from 7, so it is a permutation problem.

The order matters in this problem because a particular runner getting the gold medal is a different outcome than that same runner getting the silver medal. So the order in which they get the medals matters, making it a permutation problem rather than a combination problem.

Solution

The formula {}_{7} P_{3} can be used to represent the number of permutation of 7 people taking 3 different medals (gold, silver, and bronze).

\displaystyle {}_{7} P_{3}\displaystyle =\displaystyle \dfrac{7!}{\left(7-3\right)!}Substitution into formula
\displaystyle \text{ }\displaystyle =\displaystyle \dfrac{7\cdot 6\cdot 5\cdot4\cdot 3\cdot 2\cdot 1}{4 \cdot3 \cdot 2 \cdot 1}Expand factorials
\displaystyle \text{ }\displaystyle =\displaystyle 7\cdot 6 \cdot 5Cancel 4\cdot 3\cdot 2\cdot 1
\displaystyle \text{ }\displaystyle =\displaystyle 210Evaluate

There are 210 ways that the gold, silver and bronze medals can be awarded in a marathon with 7 people.

Reflection

Alternatively, this problem could have been solved using the counting principle. If there are three medals to win, 7 people could win gold, then there are 6 people left to win silver, then there are 5 people left to win bronze.

\displaystyle n(\text{gold}) \cdot n(\text{silver}) \cdot n(\text{bronze})\displaystyle =\displaystyle 7\cdot 6 \cdot 5
\displaystyle \text{ }\displaystyle =\displaystyle 210
c

The manager of a company wants to create a group of 5 people from his 20 employees. How many different groups are possible?

Approach

This problem involves choosing 5 people from a group of 20. The order does not matter because there are no arrangements or positions within the group of 5. Therefore, this is a combination problem.

Solution

There are n=20 employees and we want to choose r=5 members.

We can use the formula {}_{n} C_{r}.

\displaystyle {}_{20} C_{5}\displaystyle =\displaystyle \dfrac{20!}{5!\left(20-5\right)!}Substitution into formula
\displaystyle \text{ }\displaystyle =\displaystyle \dfrac{20\cdot 19\cdot 18\cdot17\cdot 16\cdot 15!}{5\cdot 4\cdot 3 \cdot2 \cdot 1 \cdot 15!}Expand factorials
\displaystyle \text{ }\displaystyle =\displaystyle \dfrac{20\cdot 19\cdot 18\cdot17\cdot 16\cdot}{5\cdot 4\cdot 3 \cdot2 \cdot 1 }Cancel out 15!
\displaystyle \text{ }\displaystyle =\displaystyle 15\,504Evaluate

There are 15\, 504 possible groups.

Example 2

4 letters are chosen at random from the word TRAMPOLINE. Find the probability that the selection includes 2 vowels.

Approach

The probability of an event is defined as: P\left(\text{event}\right)=\dfrac{\text{number of outcomes resulting in event}}{\text{total possible number of outcomes}}

So we need to determine:

  • The number of ways 4 letters that can be selected with 2 of them being vowels.

  • The total number of ways in which 4 letters can be selected from 10 the letters without restriction.

  • Then divide the first result by the second.

In order for the selection to contain 2 vowels, we need to choose 2 letters from the 4 vowels in TRAMPOLINE, and 2 letterns from the 6 consonants in TRAMPOLINE.

Solution

\displaystyle \text{}_4 C_2\displaystyle =\displaystyle 6Number of ways to choose two letters from the vowels
\displaystyle \text{}_6 C_2\displaystyle =\displaystyle 15Number of ways to choose two letters from the consonants
\displaystyle \text{}_4 C_2 \cdot \text{}_6 C_2\displaystyle =\displaystyle 6\cdot 15Use the counting principle to find the number of ways to choose the 4 letters with 2 vowels
\displaystyle \text{}\displaystyle =\displaystyle 90Evaluate
\displaystyle \text{ }_{10} C_4\displaystyle =\displaystyle 210Number of ways to choose any 4 letters from the 10 letters in TRAMPOLINE
\displaystyle P(2 \text{ vowels})\displaystyle =\displaystyle \dfrac{90}{210}Probability formula
\displaystyle \text{ }\displaystyle =\displaystyle \dfrac{3}{7}Simplify

Therefore, the probability that the selection includes 2 vowels is \dfrac{3}{7}.

Outcomes

A2.S.CP.B.2

Apply statistical counting techniques.*

A2.S.CP.B.2.A

Use the Fundamental Counting Principle to compute probabilities of compound events and solve problems.

A2.S.CP.B.2.B

Use permutations and combinations to compute probabilities of compound events and solve problems.

A2.MP2

Reason abstractly and quantitatively.

A2.MP3

Construct viable arguments and critique the reasoning of others.

A2.MP4

Model with mathematics.

A2.MP5

Use appropriate tools strategically.

A2.MP6

Attend to precision.

A2.MP7

Look for and make use of structure.

What is Mathspace

About Mathspace