Lesson Explainer: Permutation | Nagwa Lesson Explainer: Permutation | Nagwa

Lesson Explainer: Permutation Mathematics

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 𝑛1 objects remaining. So, there are 𝑛1 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 thenumberofwaystoorderthenumberofwaystoordertherstthenumberofwaystoorderthelast𝑛=××=𝑛×(𝑛1)×(𝑛2)××2×1=𝑛.

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 thenumberofwaystoassignmedalsfromthenumberofwaystoorderrunnersthenumberofwaystoorderrunners𝑘𝑛×𝑛𝑘=𝑛.

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 𝑃×2.

Answer

We recall that the permutation 𝑃 is defined by 𝑃=𝑛𝑛𝑘.

So, 𝑃=552=53.

We recall that 5=5×4×3×2×1 and 3=3×2×1. So, we have the identity 5=5×4×3. Then, 53=5×4×33=5×4=20.

Finally, we have 𝑃×2=20×(2×1)=40.

Hence, 𝑃×2 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, 𝑃=554=51=5.

We compute 5=5×4×3×2×1=120, so 𝑃=120.

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, 𝑃=882=86.

We recall that 8=8×7×6. So, 86=8×7×66=8×7=56, which leads to 𝑃=56.

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 𝑃=32736.

Answer

By definition, we can write 𝑃=𝑛𝑛3.

For 𝑛3, we can write 𝑛=𝑛(𝑛1)(𝑛2)𝑛3, so 𝑛𝑛3=𝑛(𝑛1)(𝑛2)𝑛3𝑛3=𝑛(𝑛1)(𝑛2).

We have 𝑃=𝑛(𝑛1)(𝑛2). We need to find 𝑛 satisfying 𝑛(𝑛1)(𝑛2)=32736.

In other words, we need to find three consecutive integers (𝑛, 𝑛1, and 𝑛2) whose product is 32‎ ‎736.

Since 𝑛3, the product 𝑛(𝑛1)(𝑛2) should be between (𝑛2) and 𝑛. So, (𝑛2)32736𝑛.

Taking the cubic root of the inequality, since 3273631.99, we get 𝑛231.99𝑛.

Hence, 𝑛 should be at least 32. Also, 𝑛2 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 𝑛=32, then 𝑃=𝑛(𝑛1)(𝑛2)=323130=29760.

If 𝑛=33, then 𝑃=333231=32736.

The latter agrees with the given value, so this is the correct value of 𝑛.

Therefore, 𝑃=32736 implies that 𝑛=33.

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 𝑘=3 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, thenumberofdierentringswithstonesfromthenumberoflineararrangementsfromaringthenumberoflineararrangementsofstonesfrom𝑘𝑛×=𝑘𝑛.

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, thenumberofdierentcirculararrangements×𝑘=𝑃.

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

We note that the last identity is given by substituting 𝑘=𝑛, which gives us 𝑃𝑛=𝑛𝑛=𝑛×𝑛1𝑛=𝑛1.

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, 𝑛=6 and 𝑘=6. We need to compute 𝑃6.

We recall that 𝑃=𝑛𝑛𝑘. So, 𝑃=6(66)!=60=6.

So, 𝑃6=66=6×56=5=120.

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

Download the Nagwa Classes App

Attend sessions, chat with your teacher and class, and access class-specific questions. Download Nagwa Classes app today!

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