In this explainer, we will learn how to use permutation properties to solve problems and use permutation to count possible outcomes.
The permutation, denoted , represents the number of different ways to order objects from total distinct objects. For permutations, the order of each element matters. For example, if we wanted to find the number of ordered triplets from the numbers 1 through 5, which is given by , then the arrangements 1, 2, 3 and 3, 2, 1 are counted as two different arrangements. For this definition to make sense, we require the parameters and to be nonnegative integers, satisfying .
In particular, let us consider the permutation that counts the different ways to order distinct objects. We recall the fundamental 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.
The task of ordering distinct objects can be decomposed into separate steps, starting with selecting the first object. There are different ways to select the first object. Having selected the first object, there are objects remaining. So, there are different ways to select the second object. The pattern continues until we select the last object, where there is only one possibility. Using the fundamental counting principle, we get
There are different ways to order distinct objects. So, we have
Next, let us consider the more general case , where . The permutation represents the number of different ways to order objects from total distinct objects. The task of ordering objects from total distinct objects can be thought of in the context of a race. Say that students participate in a race, where the first finishers will earn medals with their placement printed on it. For example, the first-place student will win a medal with “#1” printed on it, the second-place student will receive one with “#2” printed on it, and so on. Students who finish after the student number will not receive a medal.
If we count the number of different ways to assign medals at the end of this race, we are counting the different ways to order students from the total of students. By definition, this number is given by the permutation .
Let us apply the fundamental counting principle to our example. We let be the event of assigning medals for the top finishers and let be the event of ordering the remaining runners. We note that assigning medals to the top finishers does not affect the order of the remaining runners, so the events and are independent. If we combine the events and , then we get an event in which we order all runners. By the fundamental counting principle, we have
Based on the previous discussion, there are different ways to assign medals for the top finishers. As discussed above, there are different ways to order runners and different ways to order all runners. So,
Dividing each side by , we can compute
This leads to the general formula for permutations.
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
We remark that several equivalent different notations are used for permutations. The notations , , and are equivalent.
We consider a few examples to familiarize ourselves with different contexts.
Example 1: Using the Permutation Formula to Compute Values
Evaluate .
Answer
We recall that the permutation is defined by
So,
We recall that and . So, we have the identity . Then,
Finally, we have
Hence, is equal to 40.
Next, we consider a few examples dealing with word problems related to permutations. In word problems, it is important to rephrase the problem to associate the problem’s context with the corresponding permutation symbol .
Example 2: Using Permutations to Solve a Counting Problem
How many different 4-digit numbers can be formed from the digits 5, 3, 2, 7, and 6? Assume no number can be used more than once.
Answer
We need to count the number of different 4-digit numbers created using 5 distinct digits so that there is no repeated digit. Rephrasing the problem slightly, we need to count the number of ways to order 4 digits from 5 distinct digits. This number is given by the permutation . We recall that . Then,
We compute so .
There are 120 different 4-digit numbers that can be formed from the digits 5, 3, 2, 7, and 6 so that no digit is repeated.
Example 3: Using Permutations to Solve a Word Problem
In how many ways can 2 people sit on 8 chairs?
Answer
We need to count the number of different ways 2 people can sit on 8 chairs. We will rephrase the counting statement to fit the definition of permutations. Say that the two people are labeled #1 and #2. We note that the task of #1 and #2 of choosing 2 chairs to sit on is equivalent to the task of labeling two chairs #1 and #2. We can rephrase the latter task as ordering two chairs from 8 total chairs.
So, we need to count the number of ways to order 2 chairs out of 8 chairs. This is given by the permutation . We recall that . So,
We recall that . So, which leads to .
So, there are 56 different ways 2 people can sit on 8 chairs.
In the next example, we will consider a problem involving an unknown parameter of the permutation .
Example 4: Finding the Value of an Unknown by Evaluating Permutations
Find the value of such that .
Answer
By definition, we can write
For , we can write , so
We have . We need to find satisfying
In other words, we need to find three consecutive integers (, , and ) whose product is 32 736.
Since , the product should be between and . So,
Taking the cubic root of the inequality, since , we get
Hence, should be at least 32. Also, can be at most 31, meaning is at most 33. We note that should be either 32 or 33.
We check the permutation formula for both these values. If , then
If , then
The latter agrees with the given value, so this is the correct value of .
Therefore, implies that .
Problems on permutation can also contain rotational symmetries, which further reduces the number due to the fact that rotating a given circular arrangement leads to an equivalent arrangement. For example, consider a ring that contains distinct stones that are equally spaced, where there are distinct types of stones. Let us count the number of different rings from this context.
From our earlier discussions, we know that there are ways we can order stones in a straight line from total stones. Say that we create a ring by bringing the left and the right ends to be adjacent in a circular arrangement. For example, consider the following linear and circular arrangements with pictured below.
We observe that all three circular arrangements above are identical, while the corresponding linear arrangements are distinct. The linear arrangements can be obtained from the circular arrangements by taking the stone on the top and proceeding clockwise.
So, when we count the number of linear arrangements, each distinct ring design is repeated 3 times. In other words, there are 3 different linear arrangements that root from a single circular ring design pictured above. If we have distinct stones in a ring, then each ring design can form distinct linear arrangements.
Let us use the fundamental counting principle to formulate the number of distinct ring designs with stones from total distinct stones. Let be the event of creating a ring design, and let be the event of forming a linear arrangement from a given ring design. The outcome of event , which is a specific ring design, does not affect the number of different ways to achieve event (i.e., there are always different ways to achieve ). So, the events and are independent. Then, by the fundamental counting principle,
The right-hand side of the equation is given by , and we have observed that there are different ways to form linear arrangements from a ring. Then,
Dividing both sides by , we obtain the following formula.
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 object in a circular pattern is
We note that the last identity is given by substituting , which gives us
Let us consider another example of circular arrangements to become more familiar with this concept.
Example 5: Using Permutations to Solve a Word Problem with Rotational Symmetries
Determine the number of ways 6 children can sit in a circle.
Answer
We want to count the number of ways that 6 children can sit in a circle. We recall that the number of different ways to arrange objects in a circular pattern from total distinct objects is
In our example, we are arranging in a circle 6 students from 6 total students. So, and . We need to compute
We recall that . So,
So,
Hence, there are 120 different ways that six children can sit in a circle.
Key Points
- The permutation counts the different ways to order objects from total distinct objects.
- The permutation is also denoted or .
- The number of different ways to order distinct objects is given by
- The permutation is given by .
- The number of circular arrangements for elements from total elements is given by . In particular, the number of circular arrangements for total distinct objects is .
