Explainer: Counting Using Permutations

In this explainer, we will learn how to use permutations to solve counting problems.

A permutation is a rearrangement of a collection of items. For example, say we have the letters A, B, and C. We can arrange them as ABC, BCA, BAC, and so on. Each different arrangement is an example of a permutation. Notice that for permutations:

  • order matters: BCA is not the same as BAC,
  • we do not allow repetition: AAB is not a valid permutation of ABC.

Hence, a permutation represents counting without replacement in which order matters.

If we would like to know how many permutations there are of a set of ๐‘› items, we think about the number of choices we have for each position. For the first position, we have ๐‘› choices. Then, for the second position, we have ๐‘›โˆ’1 choices because we have one less item. Similarly, for the third position, we have ๐‘›โˆ’2 choices. Continuing this process, we can enumerate the number of choices for each position. Then we can apply the fundamental counting principle to get that the total number or permutations will be ๐‘›ร—(๐‘›โˆ’1)ร—(๐‘›โˆ’2)ร—โ‹ฏร—2ร—1. Using factorial notation, we can write this more succinctly as ๐‘›!.

We would like to generalize this idea to counting the number of permutations of length ๐‘˜ taken from a set of ๐‘›. This is equivalent to the question of how many ways we can order ๐‘˜ elements from a set of ๐‘› elements with no repetition. We will begin by looking at one motivating example.

Example 1: Permutations of Different Sizes

Consider the collection of numbers 2, 4, 6, and 8.

  1. How many different ways can we form a one-digit number from the collection of numbers?
  2. How many different ways can we form a two-digit number from the collection of numbers?
  3. How many different ways can we form a three-digit number from the collection of numbers?
  4. How many different ways can we form a four-digit number from the collection of numbers?

Answer

Part 1

Since we are forming a one-digit number, we simply have four possible choices for that one digit, represented by the figure below.

Hence, the total number of ways we can form a one-digit number from the collection of number is 4.

Part 2

We begin by considering how many options we have for the first digit. Since there are four number to choose from, the first digit could be one of four different possibilities. Once we have chosen this number, we are left with three numbers. From this collection of three numbers, we can choose our second digit.

Hence, by the fundamental counting principle, the total number of two-digit numbers we can form is given by 4ร—3=12.

Part 3

Similarly, to form a three-digit number, we think of the number of possibilities for each digit. We have four choices for the first, three for the second, and two for the third.

Hence, the total number of three-digit numbers we can form is given by 4ร—3ร—2=24.

Part 4

Finally, for a four-digit number, we can choose one of four numbers for the first digit, one of three for the second, and one of two for the third. For the fourth there is only one number left, so we only have one choice.

Hence, the total number of four-digit numbers we can form is given by 4ร—3ร—2ร—1=24.

Using the answers to the previous example, we introduce the notation ๏Š๏Ž๐‘ƒ such that the answer to part 1 is represented by ๏Šช๏Šง๐‘ƒ, part 2 by ๏Šช๏Šจ๐‘ƒ, part 3 by ๏Šช๏Šฉ๐‘ƒ, and part 4 by ๏Šช๏Šช๐‘ƒ. Using this notation, we have ๏Šช๏Šง๏Šช๏Šจ๏Šช๏Šฉ๏Šช๏Šช๐‘ƒ=4,๐‘ƒ=4ร—3,๐‘ƒ=4ร—3ร—2,๐‘ƒ=4ร—3ร—2ร—1.

We would like to try to find a generalized formula for ๏Š๏Ž๐‘ƒ in terms of ๐‘› and ๐‘Ÿ. To help us arrive at a general formula, we represent each one as a fraction with the same numerator equal to 4ร—3ร—2ร—1=๐‘›!: ๏Šช๏Šง๏Šช๏Šจ๏Šช๏Šฉ๏Šช๏Šช๐‘ƒ=4ร—3ร—2ร—13ร—2ร—1,๐‘ƒ=4ร—3ร—2ร—12ร—1,๐‘ƒ=4ร—3ร—2ร—11,๐‘ƒ=4ร—3ร—2ร—11.

Considering the first three equations, we can rewrite each one using factorial notation as follows: ๏Šช๏Šง๏Šช๏Šจ๏Šช๏Šฉ๐‘ƒ=4!3!,๐‘ƒ=4!2!,๐‘ƒ=4!1!.

Since we would like to connect our general form to the ๐‘› and ๐‘˜ in ๏Š๏Ž๐‘ƒ, we can rewrite this as ๏Šช๏Šง๏Šช๏Šจ๏Šช๏Šฉ๐‘ƒ=4!(4โˆ’1)!,๐‘ƒ=4!(4โˆ’2)!,๐‘ƒ=4!(4โˆ’3)!.

So it appears to indicate that a general form is given by ๏Š๏‡๐‘ƒ=๐‘›!(๐‘›โˆ’๐‘˜)!.

However, does this work for ๏Šช๏Šช๐‘ƒ? Using the general formula, we get ๏Šช๏Šช๐‘ƒ=4!(4โˆ’4)!=4!0!.

Recall that when we define factorial, we define the factorial of zero to be equal to one. Hence, our general formula holds for this case; in fact, this formula holds for any ๐‘› and ๐‘˜ and forms the basis of the following definition.

Definition: Permutations

The number of ways we can order ๐‘˜ elements from a set of ๐‘› elements with no repetition is given by ๏Š๏Ž๐‘ƒ (read as ๐‘›-๐‘ƒ-๐‘Ÿ) which is defined as ๏Š๏Ž๐‘ƒ=๐‘›!(๐‘›โˆ’๐‘Ÿ)!.

The permutations ๏Š๏Ž๐‘ƒ are sometimes referred to as ๐‘Ÿ-permutations of ๐‘›, variations, partial permutations, or sequences without repetition. Various forms of notation are used for ๏Š๏Ž๐‘ƒ; the following are some of the most common: ๏Š๏Ž๐‘ƒ, ๐‘ƒ๏Š๏Ž, ๐‘ƒ๏Š๏Ž•๏Ž, and ๐‘ƒ(๐‘›,๐‘Ÿ).

Example 2: Permutations

In how many ways can 11 books be arranged on a shelf?

Answer

We begin by considering how many choices we have for each position on the shelf. For the first position on the shelf, we have 11 choices of books. For the second position, we have 10 choices since we have one less book to choose from. Similarly, for the third position, we have 9 choices. Continuing in a similar way, we can consider the number of options for each position on the shelf. We can represent this in the following diagram.

Using the fundamental counting principle, the number of choices will be 11ร—10ร—9ร—8ร—7ร—6ร—5ร—4ร—3ร—2ร—1=11!=39,916,800.

An alternative way to solve this problem is to simply apply the formula for permutations. We are looking for the number of ways we can order 11 books from a set of 11 books. This number will be given to us by ๏Šง๏Šง๏Šง๏Šง๐‘ƒ. We can either evaluate this using the formula ๏Šง๏Šง๏Šง๏Šง๐‘ƒ=11!0! or using the permutation function on our calculator. Either way, we conclude that the number of arrangements of 11 books on a shelf are ๏Šง๏Šง๏Šง๏Šง๐‘ƒ=39,916,800.

Example 3: Using Permutations to Count the Number of Possible Passwords

Which of the following represents the number of ways we can form a password of length of 13 characters using different English letters?

  1. ๏Šง๏Šฉ๏Šง๏Šฉ๐‘ƒ
  2. ๏Šจ๏Šฌ๏Šง๏Šฉ๐‘ƒ
  3. ๏Šง๏Šฉ๏Šง๐‘ƒ
  4. ๏Šจ๏Šฌ๏Šง๏Šช๐‘ƒ

Answer

The total number of letters in the English alphabet is 26. From this collection we can choose 13 different letters and arrange them to make a password. Therefore, we are looking for the number of ways that we can order 13 characters from a set of 26 characters without repetition. This is exactly what the permutations formula is for. Hence, we get that the total number of 13-character passwords is given by ๏Šจ๏Šฌ๏Šง๏Šฉ๐‘ƒ. Therefore, the correct answer is B.

Example 4: Using Permutations to Count

A company labels their products with codes that start with three English letters followed by eight non-zero digits. Which of the following represents the number of codes that can be created with no repetition of any letter or digit?

  1. ๏Šจ๏Šฌ๏Šฉ๏Šฏ๏Šฎ๐‘ƒ+๐‘ƒ
  2. ๏Šฉ๏Šฉ๏Šฎ๏Šฎ๐‘ƒร—๐‘ƒ
  3. ๏Šจ๏Šฌ๏Šฉ๏Šฏ๏Šฎ๐‘ƒร—๐‘ƒ
  4. ๏Šฉ๏Šฉ๏Šฎ๏Šฎ๐‘ƒ+๐‘ƒ

Answer

We will focus on each part of the code separately; then we will apply the fundamental counting principle to get an expression for the total number, starting with the alphabetical part. There are 26 letters in the English alphabet; from this collection we can choose 3 different letters. Hence, we are looking for the number of ways that we can order 3 characters from a set of 26 characters without repetition. Using the definition of permutations, the total number of possibilities is given by ๏Šจ๏Šฌ๏Šฉ๐‘ƒ.

Next we focus on the numerical part of the code. There are a total of nine non-zero digits from which we need to choose 8 different ones. Once again, we can use permutations to get that the total number of possibilities is given by ๏Šฏ๏Šฎ๐‘ƒ.

The fundamental counting principle states that the total number of possibilities will be the product of these. Hence, the total number of different codes is given by the expression ๏Šจ๏Šฌ๏Šฉ๏Šฏ๏Šฎ๐‘ƒร—๐‘ƒ.

Therefore, the correct answer is C.

Example 5: Using Permutations to Count the Number of Different Role Assignments

Isabella, Benjamin, and Daniel are playing a game, where one of them needs to be a sheriff and one needs to be an outlaw. They write each of their names on a piece of paper and place them in a bowl. If two names are picked at random where the first will be a sheriff and the second will be an outlaw, how many different combinations are there?

Answer

There are total of three people playing the game, and we need to pick two people: one to be the sheriff and the other to be the outlaw. Hence we are looking for the number of ways that we can order 2 people from a group of three. Hence, the total number will be given by the permutations formula ๏Šฉ๏Šจ๐‘ƒ. We can evaluate this using the formula ๏Šฉ๏Šจ๐‘ƒ=3!(3โˆ’2)! or by using the permutations function on a calculator to get that the total number of different ways they can assign roles in the game is 6.

Example 6: Counting the Number of Elements in a Set Using Permutations

Let ๐‘‹={๐‘ฅโˆถ๐‘ฅโˆˆโ„ค,โˆ’13โ‰ค๐‘ฅ<17} and ๐‘Œ={(๐‘Ž,๐‘,๐‘)โˆถ๐‘Ž,๐‘,๐‘โˆˆ๐‘‹,๐‘Ž,๐‘,๐‘}aredistinctelements. Determine the value of ๐‘›(๐‘Œ) where ๐‘›(๐‘Œ) is the number of elements in ๐‘Œ.

Answer

We first count the number of elements in the set ๐‘‹. We need to be careful to remember to count the elements 0 and โˆ’13, but not 17. Therefore, the total number of elements in ๐‘‹ is 30.

We will now use permutations to count the number of elements that belong to the set ๐‘Œ. To form an element of ๐‘Œ we pick three distinct elements in order from the 30 elements of ๐‘‹. Hence, the number of elements in ๐‘Œ will be equal to the total number of ways we we can order 3 elements from a group of 30. Using permutations, the total number of distinct ways to do this will be given by ๏Šฉ๏Šฆ๏Šฉ๐‘ƒ. We can evaluate this using the formula ๏Šฉ๏Šฆ๏Šฉ๐‘ƒ=30!(30โˆ’3)! or by using the permutations function on a calculator to get that the total number element in ๐‘Œ is given by ๐‘›(๐‘Œ)=24,360.

Example 7: Using Permutations to Solve Word Problems

In horse racing, a โ€œtrifectaโ€ occurs when a bettor wins by selecting the first three finishers in their exact order: 1st place, 2nd place, and 3rd place. How many different trifectas are possible if there are 14 horses in a race?

Answer

There are a total of fourteen horses, and we need to pick one for each of the top three positions. This is equivalent to the number of ways that we can order 3 horses from a group of 14. Using permutations, the total number of distinct ways to do this will be given by ๏Šง๏Šช๏Šฉ๐‘ƒ. We can evaluate this using the formula ๏Šง๏Šช๏Šฉ๐‘ƒ=14!(14โˆ’3)! or by using the permutations function on a calculator to get that the total number of different ways someone could guess a trifecta is 2,184.

Example 8: Using Permutations to Solve Word Problems

In a football league, a team plays every other team twice. If there are 14 teams in the league, determine the total number of matches to be played.

Answer

We would like to count the number of matches featuring two teams from the 14 teams in the league. However, we would like to count each match twice. One way to do this is to count the number of ways we can choose two teams where order matters. This way, we will count the match Team A versus Team B as distinct from Team B versus Team A. Hence, for each pair of teams we will count two matches. This reduces the problem to counting the number of ways that we can order 2 teams from a group of 14. Hence, the total number of ways will be given by ๏Šง๏Šช๏Šจ๐‘ƒ. We can evaluate this using the formula ๏Šง๏Šช๏Šจ๐‘ƒ=14!(14โˆ’2)! or by using the permutations function on a calculator to get that the total number of matches in the league will be 182.

Key Points

  1. The permutation ๏Š๏Ž๐‘ƒ is the total number of ways to order ๐‘Ÿ items from a set of ๐‘›. We can evaluate it using the formula ๏Š๏Ž๐‘ƒ=๐‘›!(๐‘›โˆ’๐‘Ÿ)!, or using the permutations function on a calculator.
  2. To use permutations, we need to make sure that we have a scenario where order matters and where we are counting without repetition.
  3. There are many real-world examples which can be solved using permutations.

Nagwa uses cookies to ensure you get the best experience on our website. Learn more about our Privacy Policy.