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 thenumberofwaystoorderthenumberofwaystoorderthe๏ฌrstthenumberofwaystoorderthelast๐‘›=ร—โ‹ฏร—=๐‘›ร—(๐‘›โˆ’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, ๏Šซ๏Šจ๐‘ƒ=55โˆ’2=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, ๏Šซ๏Šช๐‘ƒ=55โˆ’4=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, ๏Šฎ๏Šจ๐‘ƒ=88โˆ’2=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 ๏Žขโˆš32736โ‰ˆ31.99, we get ๐‘›โˆ’2โ‰ค31.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)=32โ‹…31โ‹…30=29760.

If ๐‘›=33, then ๏Š๏Šฉ๐‘ƒ=33โ‹…32โ‹…31=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, thenumberofdi๏ฌ€erentringswithstonesfromthenumberoflineararrangementsfromaringthenumberoflineararrangementsofstonesfrom๐‘˜๐‘›ร—=๐‘˜๐‘›.

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, thenumberofdi๏ฌ€erentcirculararrangementsร—๐‘˜=๐‘ƒ.๏Š๏‡

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(6โˆ’6)!=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.

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