# 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 choices because we have one less item. Similarly, for the third position, we have 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 . 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?

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 .

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 .

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 .

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

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 :

Considering the first three equations, we can rewrite each one using factorial notation as follows:

Since we would like to connect our general form to the and in , we can rewrite this as

So it appears to indicate that a general form is given by

However, does this work for ? Using the general formula, we get

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?

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

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 or using the permutation function on our calculator. Either way, we conclude that the number of arrangements of 11 books on a shelf are

### 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?

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?

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?

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 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 and . Determine the value of where is the number of elements in .

We first count the number of elements in the set . We need to be careful to remember to count the elements 0 and , 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 or by using the permutations function on a calculator to get that the total number element in is given by .

### 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?

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 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.