Lesson Explainer: Counting Using Permutations

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

A permutation is used to count the number of different ways we can rearrange a subset of a collection of elements. For instance, say we want to arrange 3 different letters from the English alphabet. First, we must pick 3 different letters and then we can arrange them in order. This leads to arrangements like BJA, EMQ, XPG, etc. We cannot use arrangements like BVB since the letter B is repeated. On the other hand, BJA, AJB, and JBA will all count as distinct arrangements despite the fact that they use the same 3 letters. In permutations, the order of elements matters.

Let us recall the formula for permutations, which represents the number of distinct arrangements of a subset of a collection of elements.

Definition: Permutation

Given nonnegative integers and satisfying , the permutation represents the number of different ways to order objects from the total of distinct objects. Its formula is given by

Let us begin with an example where we will use the permutation to count the number of distinct arrangements.

Example 1: Counting Using Permutations

Let and . Determine the value of , where is the number of elements in .

Answer

In this example, we want to count the number of distinct elements in set , where the elements of set are the ordered pairs of elements of set . Also, the ordered pairs in set cannot contain 2 identical elements.

To form an ordered pair of distinct elements, we can first select 2 elements from set and then arrange the 2 selected elements in order. Hence, the number of ordered pairs is equal to the number of different ways to arrange 2 distinct elements in order from set . This leads to the concept of permutations.

Recall that, given nonnegative integers and satisfying , the permutation represents the number of different ways to order objects from the total of distinct objects. Its formula is given by

Since contains all integers between 7 and 16, the number of elements in is given by

This gives . We want to arrange 2 elements in order; hence, . Then, the number of ways to order 2 elements from a collection of 10 total elements is given by , which is equal to . We can compute

Therefore, .

In real-world counting problems, it is sometimes unclear whether to use the permutation rule and how to use it. To use the permutation rule in a real-world scenario, we need to identify a sequence of events in permutations leading to the same outcomes as the given scenario.

How To: Solving Real-World Counting Problems Using Permutation Rules

Given a real-world counting problem, we can construct a sequence of events that has the same number of outcomes as in the given real-world scenario by doing the following:

Selecting distinct objects from total distinct objects where
Ordering the selected objects

Then, the number of outcomes in the real-world scenario is given by .

In the next example, we will apply the above method to a real-world counting problem by using permutations to count the number of possible arrangements of a group of people.

Example 2: Counting Using Permutations

Determine the number of different ways for 4 players to sit on 11 seats in one row.

Answer

In this example, we need to count the number of different ways 4 players can sit on 11 seats in one row. We can solve this problem by using permutations to count the number of possible arrangements of the players. Recall that, given nonnegative integers and satisfying , the permutation represents the number of different ways to order distinct objects from total distinct objects. In other words, we need to find a sequence of events by

selecting distinct objects from total distinct objects,
ordering the selected objects.

To determine the seating arrangements for 4 players, we can first choose 4 seats from 11 distinct seats. After choosing the 4 seats to be occupied, we can order the 4 selected seats. The ordering of the selected seats can be interpreted as follows. Say that the 4 players are numbered 1, 2, 3, and 4. After ordering the 4 seats, player 1 sits on the first seat, player 2 sits on the second seat, and so on.

We can see that, following this logic, we can cover every possible seating arrangement for 4 players. Hence, the number of different seating arrangements is given by the permutation . Recall that the formula for permutation is given by

Substituting and , we compute

Hence, there are 7‎ ‎920 ways for 4 players to sit on 11 seats in one row.

Identifying a sequence of events leading to the same outcomes can be tricky. Let us consider another example where we will count the number of different outcomes using this method.

Example 3: Solving Problems Involving Permutations

How many unique anagrams are there of the word ERROR?

Answer

In this example, we need to find the number of unique anagrams of the word ERROR. In other words, we need to find the number of different arrangements using all the letters in this word. If the word had had five distinct letters, then we could have applied the factorial rule to conclude that there are distinct arrangements, or anagrams, of this word. However, this is not the case here, since the letter R appears three times in this word.

We can apply the permutation rule to this counting problem by identifying a sequence of events leading to the same number of outcomes. Recall that, given nonnegative integers and satisfying , the permutation represents the number of different ways to order distinct objects from total distinct objects. In other words, we need to find a sequence of events by

selecting distinct objects from total distinct objects,
ordering the selected objects.

Any anagram of the word ERROR must be a five-letter word containing one E, one O, and three Rs. We can define the sequence of events as follows.

We note that as the three Rs are not distinct, the order they go in does not matter. Hence, the number of permutations depends only on the placements of E and O. The remaining three placements can be filled by three R’s. As the word is five letters long and the two letters can be placed in either order, we are considering permutations of two letters in five total possible positions.

For instance, if we have chosen and ordered (5th placement, 3rd placement), then this would result in the anagram RRORE. An anagaram ERORR would correspond to the ordering (1st placement, 3rd placement). We can see that this sequence of events leads to each anagram from the word ERROR. Hence, the number of such anagrams is given by the permutation . Recall that the formula for permutation is given by

Substituting and , we compute

Hence, there are 20 unique anagrams of the word ERROR.

We can also apply the fundamental counting principle (also known as the product rule) with permutations to find the number of different outcomes in a given scenario. Let us recall the counting principle.

Theorem: Fundamental Counting Principle

If we have two independent events and such that the number of possible outcomes for event is and the number of possible outcomes for event is , the total number of distinct possible outcomes of these two events together is the product .

Two events are independent if the outcome of one event does not change the number of possible outcomes of the other event. Furthermore, the fundamental counting principle works when there are more than two events. In short, we can multiply the number of possible outcomes for each event, as long as they are independent.

In the next example, we will apply the fundamental counting principle and permutations to find the number of different outcomes.

Example 4: Applications of the Counting Principle (Product Rule) and Permutations

A company labels their products with codes that start with 3 English letters followed by 8 nonzero digits. Which of the following represents the number of codes that can be created with no repetition of any letter or digit?

Answer

In this example, we want to count the number of different codes that can be created with no repetition of any letter or digit. We are given that a code must begin with 3 English letters and be followed by 8 nonzero digits. We can create a code by first ordering 3 English letters and then ordering 8 nonzero digits so that there are no repetitions.

We recall the fundamental counting principle: given two independent events and such that the number of possible outcomes for event is and the number of possible outcomes for event is , the total number of distinct possible outcomes of these two events together is the product . We also recall that two events are independent if the outcome of one event does not change the number of possible outcomes of the other event.

To apply the fundamental counting principle, let be the event of ordering 3 English letters and be the event of ordering 8 nonzero digits. We can see that a specific order of 3 English letters does not affect the number of different orderings of 8 nonzero digits. Hence, and are independent events. We now need to find the number of each event separately and then multiply them to obtain the total number of ways to form codes.

Let us find the number of different ways to order 3 English letters. Recall that, given nonnegative integers and satisfying , the permutation represents the number of different ways to order objects from the total of distinct objects. Its formula is given by

Since there are 26 letters in the English alphabet, there are different ways to arrange 3 different letters in order from the English alphabet. Also, since there are 9 different nonzero digits, there are different ways to order 8 distinct nonzero digits.

Applying the product rule, the number of codes that can be created with no repetition of any letter or digit is

This is option D.

Let us consider another example where we need to apply both the product and permutation rules to count different outcomes.

Example 5: Applications of the Counting Principle (Product Rule) and Permutations

Find the number of ways we can select 2 milk chocolate bars first and 2 dark chocolate bars next from a box of 10 milk chocolate bars and 8 dark chocolate bars, considering that the elements are distinct, the selection is without replacement, and the order of selection matters.

Answer

In this example, we want to count the number of ways to select 2 milk chocolate bars and 2 dark chocolate bars, where the order of selection matters and the selection is without replacement.

To apply the fundamental counting principle, let be the event of selecting 2 milk chocolate bars and be the event of selecting 2 dark chocolate bars. We need to keep in mind that the order of selection matters, both for milk and dark chocolate bars. We can see that a specific order of selection for 2 milk chocolate bars does not affect the number of different ways to select 2 dark chocolate bars. Hence, and are independent events. We now need to find the number of each event separately and then multiply them to obtain the total number of ways to select chocolate bars.

Let us first find the number of different ways to select 2 milk chocolate bars, where the order of selection matters and the selection is without replacement. Recall that, given nonnegative integers and satisfying , the permutation represents the number of different ways to order objects from the total of distinct objects. Its formula is given by

Since there are 10 milk chocolate bars in the box, there are different ordered ways to achieve this task. We can compute

Next, let us find the number of different ways to select 2 dark chocolate bars, where the order of selection matters and the selection is without replacement. Since there are 8 dark chocolate bars in the box, there are different ordered ways to achieve this task. We can compute

Applying the product rule, the number of different outcomes of the given event is

We recall that permutations can also be used to describe the number of circular arrangements from a collection of distinct elements.

Theorem: Counting Circular Arrangements

The number of different ways to arrange objects in a circular pattern from total distinct objects is

In particular, the number of different ways to arrange total distinct objects in a circular pattern is

In our final example, we will apply this formula to count the number of circular arrangements.

Example 6: Counting Circular Arrangements

True or False: In a flower shop, there are 40‎ ‎320 ways to arrange 8 flowers in a circle.

Answer

Recall that the number of different ways to arrange total distinct objects in a circular pattern is

In this example, we want to find the number of different circular arrangements of 8 flowers; hence, . This leads to

This is different from the number stated in the problem. We can see that the number given in the problem is , which is the number of different ways to arrange 8 flowers in a straight line. This number does not account for the fact that some circular arrangements are considered identical due to the rotational symmetry of a circle.

Hence, the given statement is false.

Let us finish by recapping a few important concepts from this explainer.

Key Points

Given nonnegative integers and satisfying , the permutation represents the number of different ways to order objects from the total of distinct objects. Its formula is given by
We can solve a counting problem using permutations if it is equivalent to the following events: For integers and satisfying ,
1. select distinct objects from total distinct objects,
2. order the selected objects.
Then, the number of outcomes in the real-world scenario is given by .
The number of different ways to arrange objects in a circular pattern from total distinct objects is In particular, the number of different ways to arrange total distinct objects in a circular pattern is