Unlocking Probability: Calculating with Permutations and Combinations

In this lesson, the concepts of permutation and combination will be introduced and connected to the computation of probabilities of compound events.

Catch-Up and Review

Here are a few recommended readings before getting started with this lesson.

Probability
Compound Event
Multiplication Rule of Probability
Fundamental Counting Principle

Discussion

Defining Permutations and the Permutation Formula

Many situations involve the rearrangement of a specific set of objects. These are called permutation problems. Below, the definition of permutation and its corresponding formula are discussed.

Rule

Permutation Formula

The number of permutations of $n$ different objects arranged $r$ at a time — denoted as $_{n} P_{r}$ — is given by the following formula.

$_{n} P_{r} = \frac{n !}{( n - r ) !}, r \leq n$

The exclamation sign in the formula indicates that the factorial of a value must be calculated. As a direct consequence, since $0! = 1,$ when $n = r$ the number of permutations is given by the factorial of $n .$

$_{n} P_{n} = n!$

An alternative notation for $_{n} P_{r}$ is $P (n, r) .$

Proof

Permutation Formula

The formula can be proven by using the Fundamental Counting Principle. In an arrangement with $r$ elements, there are $n$ choices for the first element, $n - 1$ choices for the second element, $n - 2$ choices for the third element, and so on.

Position	Number of Choices
$1$	$n$
$2$	$n - 1$
$3$	$n - 2$
$⋮$	$⋮$
$r$	$(n - r + 1)$

By the Fundamental Counting Principle, the product of the choices for each element is equal to the number of different arrangements of

n

objects chosen

r

at a time.

_{n} P_{r} = n (n - 1) \dots (n - r + 1)

The right-hand side of this equation consists of the first

r

factors of the factorial of

n .

The Multiplication Property of Equality can be used to multiply both sides by the last

n - r

factors of the factorial of

n .

The product of these factors can be written as

(n - r)!

_{n} P_{r} = n (n - 1) \dots (n - r + 1)

MultEqn

$LHS \cdot (n - r)! = RHS \cdot (n - r)!$

_{n} P_{r} (n - r)! = n (n - 1) \dots (n - r + 1) (n - r)!

It is important to remember how to write

(n - r)!

as a product.

(n - r)! = (n - r) \cdot (n - r - 1) \cdot \dots 2 \cdot 1

This expression will be substituted for

(n - r)!

on the right-hand side of the equation.

_{n} P_{r} (n - r)! = n (n - 1) \dots (n - r + 1) (n - r)!

Write as a product

_{n} P_{r} (n - r)! = n (n - 1) \dots (n - r + 1) (n - r) (n - r - 1) \dots (2) (1)

Write as a factorial

_{n} P_{r} (n - r)! = n!

DivEqn

$LHS / (n - r)! = RHS / (n - r)!$

_{n} P_{r} = \frac{n !}{( n - r ) !}

Example

Investigating Permutations in Real-Life Situations

The following cities are the ten most visited cities in Europe.

Rank	City
$1$	London, UK
$2$	Paris, France
$3$	Istanbul, Turkey
$4$	Antalya, Turkey
$5$	Rome, Italy
$6$	Prague, Czech Republic
$7$	Amsterdam, Netherlands
$8$	Barcelona, Spain
$9$	Vienna, Austria
$10$	Milan, Italy

a Dominika and her friend Heichi are planning to go to Europe next summer. How many different ways can they arrange their trip to see all ten cities?

b Suppose that they can only visit

3

of the ten places. In how many ways can they do it?

Hint

a The number of permutations of

n

out of

n

is given by the factorial of

n .

b Consider the permutation formula for

r

objects out of

n .

Solution

a Because the order in which the cities will be visited is important, the problem can be solved by using permutations. The number of permutations when taking

n

items out of

n

is given by the factorial of

n .

_{n} P_{n} = n!

In this case, since there are ten cities to be visited, the factorial of

10

needs to be calculated.

_{n} P_{n} = n!

Substitute

$n = 10$

_{10} P_{10} = 10!

Write as a product

_{10} P_{10} = 10 \cdot 9 \cdot 8 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1

Multiply

_{10} P_{10} = 3628800

Therefore, Dominika and Heichi have

3628800

different ways to visit all ten most visited cities of Europe.

b Now suppose that Heichi and Dominika will visit only three places. Since the order of the cities they visit is important, permutations can be used again. The number of permutations when taking

r

items out of

n

is given by the following formula.

_{n} P_{r} = \frac{n !}{( n - r ) !}

Of the

10

places, only

3

can be visited. Therefore, the number of permutations of

3

out of

10

needs to be calculated.

_{n} P_{r} = \frac{n !}{( n - r ) !}

SubstituteII

$n = 10$ , $r = 3$

_{10} P_{3} = \frac{1 0 !}{( 1 0 - 3 ) !}

Evaluate right-hand side

SubTerm

Subtract term

_{10} P_{3} = \frac{1 0 !}{7 !}

Write as a product

_{10} P_{3} = \frac{1 0 \cdot 9 \cdot 8 \cdot 7 !}{7 !}

CancelCommonFac

Cancel out common factors

_{10} P_{3} = \frac{1 0 \cdot 9 \cdot 8 \cdot 7 !}{7 !}

SimpQuot

Simplify quotient

_{10} P_{3} = \frac{1 0 \cdot 9 \cdot 8}{1}

DivByOne

$\frac{a}{1} = a$

_{10} P_{3} = 10 \cdot 9 \cdot 8

Multiply

_{10} P_{3} = 720

There are

720

ways of visit

3

of the ten cities.

Example

Finding Probabilities Using Permutations

In the $2020$ Olympic Games, the competitors of the men's $100$ meter freestyle swimming finals came from the following countries.

Men’s $100$ Meter Freestyle Swimming Finals
United States	Australia
Russia	France
South Korea	Italy
Hungary	Romania

a If there were no ties, in how many different ways could the gold, silver, and bronze medals have been awarded?

b If all athletes have the same athletic ability, what is the probability that the Italian swimmer wins the gold medal, the French swimmer the silver medal, and the Australian swimmer the bronze medal? Approximate the answer to three decimals.

Hint

a The order in which the medals are awarded is essential.

b The probability of an event is the ratio of the number of favorable outcomes to the number of possible outcomes.

Solution

a Because the order in which the medals are awarded is essential, the problem can be solved by using permutations. The number of permutations when taking

r

items out of

n

is given by the following formula.

_{n} P_{r} = \frac{n !}{( n - r ) !}

Of the

8

swimmers, only

3

can be on the podium and be awarded medals. Therefore, the number of permutations of

3

out of

8

needs to be calculated.

_{n} P_{r} = \frac{n !}{( n - r ) !}

SubstituteII

$n = 8$ , $r = 3$

_{8} P_{3} = \frac{8 !}{( 8 - 3 ) !}

Evaluate right-hand side

SubTerm

Subtract term

_{8} P_{3} = \frac{8 !}{5 !}

Write as a product

_{8} P_{3} = \frac{8 \cdot 7 \cdot 6 \cdot 5 !}{5 !}

CancelCommonFac

Cancel out common factors

_{8} P_{3} = \frac{8 \cdot 7 \cdot 6 \cdot 5 !}{5 !}

SimpQuot

Simplify quotient

_{8} P_{3} = \frac{8 \cdot 7 \cdot 6}{1}

DivByOne

$\frac{a}{1} = a$

_{8} P_{3} = 8 \cdot 7 \cdot 6

Multiply

_{8} P_{3} = 336

There are

336

different ways in which the gold, silver, and bronze medals can be awarded.

b Recall that the probability of an event is the ratio of the number of favorable outcomes to the number of possible outcomes.

The number of favorable outcomes is the number of ways the Italian, French, and Australian athletes can win the gold, silver, and bronze medals, respectively. Although there is only one way for the order of the first three positions, there are several ways for the order of the remaining five positions. All these are favorable outcomes.

Example Favorable Outcomes
Italy	Italy	Italy
France	France	France
Australia	Australia	Australia
United States	Hungary	South Korea
Russia	Romania	Russia
South Korea	Russia	United States
Hungary	United States	Hungary
Romania	South Korea	Romania

If the medals are awarded to the Italian, French, and Australian swimmers in this order, then the number of permutations of the last five positions must be calculated.

Favorable Outcomes_{5} P_{5} = 5! \Leftrightarrow_{5} P_{5} = 120

The number of possible outcomes is the number of all possible ways in which the medals can be awarded. This is found by calculating the permutations of

8

swimmers taken from a group of

8 .

Possible Outcomes_{8} P_{8} = 8! \Leftrightarrow_{8} P_{8} = 40320

With this information, the probability that the Italian swimmer wins the golden medal, the French swimmer the silver medal, and the Australian swimmer the bronze medal can be calculated.

P (A) = \frac{Number of favorable outcomes}{Number of possible outcomes}

SubstituteValues

Substitute values

P (A) = \frac{1 2 0}{4 0 3 2 0}

ReduceFrac

$\frac{a}{b} = \frac{a / 1 2 0}{b / 1 2 0}$

P (A) = \frac{1}{3 3 6}

FracToDiv

$\frac{a}{b} = a \div b$

P (A) = 0.002976 \dots

RoundDec

Round to $3$ decimal place(s)

P (A) \approx 0.003

Discussion

Defining Combinations and the Combination Formula

In other situations, only the selected objects are important, not the order in which they come. These problems are called combination problems. Below, the definition of combination and its corresponding formula are developed.

Concept

Combination

A combination is a selection of objects in which the order is not important. Combinations focus on the selected objects. For example, consider choosing two different ingredients for a salad from five unique options in a salad bar.

Because the order of the items does not matter, two combinations are different from each other if they do not have the same objects. The number of combinations can be found by listing every possible combination. However, this method is not helpful when considering a large number of objects. The Combination Formula should be used instead.

Rule

Combination Formula

The number of combinations of $n$ different objects taken $r$ at a time — denoted as $_{n} C_{r}$ — is given by the following formula.

_{n} C_{r} = \frac{n !}{r ! ( n - r ) !}, r \leq n

The exclamation mark in the formula indicates that the factorial of the value should be calculated. As a direct consequence of the above formula, since $0! = 1,$ when $n = r$ the number of combinations is $1 .$

_{n} C_{n} = 1

An alternative notation for $_{c} C_{r}$ is $C (n, r) .$

Proof

The formula can be proven by using the Permutation Formulas.

_{n} P_{r} = \frac{n !}{( n - r ) !} and_{r} P_{r} = r!

Let

_{n} C_{r}

be the number of combinations of

n

objects chosen

r

at a time. By the Fundamental Counting Principle, the product of

_{n} C_{r}

_{r} P_{r}

equals the number of permutations of

r

objects out of

n .

_{n} C_{r} \cdot_{r} P_{r} =_{n} P_{r} ⇓_{n} C_{r} \cdot r! = \frac{n !}{( n - r ) !}

Finally, by applying the Division Property of Equality, the Combination Formula is obtained.

_{n} C_{r} \cdot r! = \frac{n !}{( n - r ) !} ⇕_{n} C_{r} = \frac{n !}{r ! ( n - r ) !}

Example

Investigating Combinations in Real-Life Situations

Kriz is going on vacation next month and wants to pack $4$ books from their must-read list. Each of the books belongs to one of the following genres.

Kriz’s List of Books By Genres
Fantasy	Romance
Mystery	Fiction
Biography	Graphic Novel
Drama	History
Western	Poetry

In how many ways can they select

4

different books?

Hint

The order in which the books are selected is not crucial.

Solution

As long as

4

books are selected, the order is not important. Therefore, the different ways in which Kriz can select

4

books can be found by using combinations. The number of combinations when selecting

r

items out of

n

is given by the following formula.

_{n} C_{r} = \frac{n !}{r ! ( n - r ) !}

By substituting

10

for

n

and

4

for

r,

the number of combinations can be calculated.

_{n} C_{r} = \frac{n !}{r ! ( n - r ) !}

SubstituteII

$n = 10$ , $r = 4$

_{10} C_{4} = \frac{1 0 !}{4 ! ( 1 0 - 4 ) !}

Evaluate right-hand side

SubTerm

Subtract term

_{10} C_{4} = \frac{1 0 !}{4 ! \cdot 6 !}

Write as a product

_{10} C_{4} = \frac{1 0 \cdot 9 \cdot 8 \cdot 7 \cdot 6 !}{4 ! \cdot 6 !}

CancelCommonFac

Cancel out common factors

_{10} C_{4} = \frac{1 0 \cdot 9 \cdot 8 \cdot 7 \cdot 6 !}{4 ! \cdot 6 !}

SimpQuot

Simplify quotient

_{10} C_{4} = \frac{1 0 \cdot 9 \cdot 8 \cdot 7}{4 !}

Write as a product

_{10} C_{4} = \frac{1 0 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1}

Multiply

_{10} C_{4} = \frac{5 0 4 0}{2 4}

CalcQuot

Calculate quotient

_{10} C_{4} = 210

There are

210

ways in which Kriz can select

4

books to pack from their must-read list.

Example

Finding Probabilities Using Combinations

Kriz has decided that they will select $5$ of their books at random instead of $4 .$ However, they would prefer to bring at least one book from the fantasy, mystery, and drama genres. What is the probability of them choosing these three genres if the selection pool consists of $10$ books from $10$ different genres? Write the answer in percentage form rounded to $1$ decimal place.

Hint

The probability of an event is the ratio of the number of favorable outcomes to the number of possible outcomes.

Solution

The probability of an event is the ratio of the number of favorable outcomes to the number of possible outcomes.

The order in which the books are selected is not important. Therefore, the number of possible outcomes can be found by calculating the combinations when taking

5

books out of

10 .

The number of combinations when selecting

r

items out of

n

is given by the following formula.

_{n} C_{r} = \frac{n !}{r ! ( n - r ) !}

By substituting

10

for

n

and

5

for

r,

the number of possible outcomes can be calculated.

_{n} C_{r} = \frac{n !}{r ! ( n - r ) !}

SubstituteII

$n = 10$ , $r = 5$

_{10} C_{5} = \frac{1 0 !}{5 ! ( 1 0 - 5 ) !}

Evaluate right-hand side

SubTerm

Subtract term

_{10} C_{5} = \frac{1 0 !}{5 ! \cdot 5 !}

Write as a product

_{10} C_{5} = \frac{1 0 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 !}{5 ! \cdot 5 !}

CancelCommonFac

Cancel out common factors

_{10} C_{5} = \frac{1 0 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 !}{5 ! \cdot 5 !}

SimpQuot

Simplify quotient

_{10} C_{5} = \frac{1 0 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{5 !}

Write as a product

_{10} C_{5} = \frac{1 0 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}

Multiply

_{10} C_{5} = \frac{3 0 2 4 0}{1 2 0}

CalcQuot

Calculate quotient

_{10} C_{5} = 252

There are

252

ways of selecting

5

books out of

10 .

This is the number of possible outcomes.

Possible Outcomes : 252

Since the order does not matter, there is only one way of selecting a fantasy, a mystery, and a drama book. The other

2

books need to be selected from the remaining

7 .

Therefore, the combinations of

2

out of

7

books will be calculated.

_{n} C_{r} = \frac{n !}{r ! ( n - r ) !}

SubstituteII

$n = 7$ , $r = 2$

_{7} C_{2} = \frac{7 !}{2 ! ( 7 - 2 ) !}

Evaluate right-hand side

SubTerm

Subtract term

_{7} C_{2} = \frac{7 !}{2 ! \cdot 5 !}

Write as a product

_{7} C_{2} = \frac{7 \cdot 6 \cdot 5 !}{2 ! \cdot 5 !}

CancelCommonFac

Cancel out common factors

_{7} C_{2} = \frac{7 \cdot 6 \cdot 5 !}{2 ! \cdot 5 !}

SimpQuot

Simplify quotient

_{7} C_{2} = \frac{7 \cdot 6}{2 !}

$2! = 2$

_{7} C_{2} = \frac{7 \cdot 6}{2}

Multiply

_{7} C_{2} = \frac{4 2}{2}

CalcQuot

Calculate quotient

_{7} C_{2} = 21

There is

1

way to select the first three books and

21

ways to select the other two books. By the Fundamental Counting Principle, the number of favorable outcomes is the product between

1

and

21 .

Favorable Outcomes : 1 \cdot 21 = 21

There are

21

favorable outcomes and

252

possible outcomes. Let

A

be the event that

3

of the

5

books selected are a fantasy, a mystery, and a drama. By substituting the number of favorable outcomes and the number of possible outcomes into the Probability Formula,

P (A)

can be found.

P (A) = \frac{Number of favorable outcomes}{Number of possible outcomes}

SubstituteII

$Number of favorable outcomes = 21$ , $Number of possible outcomes = 252$

P (A) = \frac{2 1}{2 5 2}

ReduceFrac

$\frac{a}{b} = \frac{a / 2 1}{b / 2 1}$

P (A) = \frac{1}{1 2}

FracToDiv

$\frac{a}{b} = a \div b$

P (A) = 0.08 \overline{3}

RoundDec

Round to $3$ decimal place(s)

P (A) \approx 0.083

WritePercent

Convert to percent

P (A) \approx 8.3 %

The probability of getting a fantasy, a mystery, and a drama in the five selected books is about

8.3 % .

Closure

Creating Arrangements

Permutations and combinations can be used in many situations. Understanding these mathematical concepts can help solve many intricate problems. With this in mind, reconsider the problem in which Vincenzo wants to create arrangements by using the following letters.

How many different arrangements with

3

vowels and

4

consonants can be created?

Hint

Begin by calculating the number of ways of selecting $3$ vowels and $4$ consonants. The order of the arrangements is essential.

Solution

Because the arrangements consist of $3$ vowels and $4$ consonants, they have $7$ letters. An example arrangement is shown.

Note that

3

vowels must be selected out of

5,

which means that the number of possible combinations must be calculated. To do so, the combination formula can be used. The number of combinations of

n

objects taken

r

at a time is given by the following formula.

_{n} C_{r} = \frac{n !}{r ! ( n - r ) !}

Therefore, the number of possible combinations can be calculated by substituting

5

for

n

and

3

for

r

into the formula.

_{n} C_{r} = \frac{n !}{r ! ( n - r ) !}

SubstituteII

$n = 5$ , $r = 3$

_{5} C_{3} = \frac{5 !}{3 ! ( 5 - 3 ) !}

Evaluate right-hand side

SubTerm

Subtract term

_{5} C_{3} = \frac{5 !}{3 ! \cdot 2 !}

Write as a product

_{5} C_{3} = \frac{5 \cdot 4 \cdot 3 !}{3 ! \cdot 2 !}

CancelCommonFac

Cancel out common factors

_{5} C_{3} = \frac{5 \cdot 4 \cdot 3 !}{3 ! \cdot 2 !}

SimpQuot

Simplify quotient

_{5} C_{3} = \frac{5 \cdot 4}{2 !}

Multiply

_{5} C_{3} = \frac{2 0}{2 !}

$2! = 2$

_{5} C_{3} = \frac{2 0}{2}

CalcQuot

Calculate quotient

_{5} C_{3} = 10

In a similar way, the number of combinations when taking

4

out of

6

constants can be found.

_{n} C_{r} = \frac{n !}{r ! ( n - r ) !}

SubstituteII

$n = 6$ , $r = 4$

_{6} C_{4} = \frac{6 !}{4 ! ( 6 - 4 ) !}

Evaluate right-hand side

SubTerm

Subtract term

_{6} C_{4} = \frac{6 !}{4 ! \cdot 2 !}

Write as a product

_{6} C_{4} = \frac{6 \cdot 5 \cdot 4 !}{4 ! \cdot 2 !}

CancelCommonFac

Cancel out common factors

_{6} C_{4} = \frac{6 \cdot 5 \cdot 4 !}{4 ! \cdot 2 !}

SimpQuot

Simplify quotient

_{6} C_{4} = \frac{6 \cdot 5}{2 !}

Multiply

_{6} C_{4} = \frac{3 0}{2 !}

$2! = 2$

_{6} C_{4} = \frac{3 0}{2}

CalcQuot

Calculate quotient

_{6} C_{4} = 15

There are

10

ways of selecting three vowels and

15

ways of selecting four consonants. By the Fundamental Counting Principle, the number of ways of selecting three vowels and four consonants is given by the product of

10

and

15 .

10 \cdot 15 = 150

Now, keep in mind that a different arrangement of each possible combination is different. This means that the order is important, and the number of possible permutations of the seven letters must to be calculated. Recall that the factorial of

n

gives the number of permutations of

n

out of

n .

_{7} P_{7} = 7! \Leftrightarrow_{7} P_{7} = 5040

Finally the Fundamental Counting Principle will be used one more time. For each of the

150

ways of selecting three vowels and four consonants, there are

5040

permutations.

Possible Arrangements 150 \cdot 5040 = 756000

	{{ 'ml-lesson-number-slides' \| message : article.intro.bblockCount}}
	{{ 'ml-lesson-number-exercises' \| message : article.intro.exerciseCount}}
	{{ 'ml-lesson-time-estimation' \| message }}

{{ article.displayTitle }}

Catch-Up and Review

Proof

Hint

Solution

Hint

Solution

Proof

Hint

Solution

Hint

Solution

Hint

Solution