2.3: Permutations

In this section, we will discuss the theory of permutations. Before doing so, it is important to note how all of our counting structures will be related to each other. The following flowchart summarizes how each structure is naturally derived from the one before it:

This means rather than focusing on the differences between the different counting structures, we should instead focus on crafting a narrative on how each structure leads to another. In this section, we will discuss how The Generalized Principle of Counting naturally leads to the idea of a permutation.

In order to discuss the theory of permutations, we first define what a permutation is.

Definition: Permutation

Suppose a set has \(n \) distinct elements and an experiment consists of selecting \( k\) of the elements one at a time without replacement. Let each outcome consist of the \( k\) elements in the order selected. Each such outcome is called a permutation of \( n \) elements taken \( k\) at a time or is called an ordered sample without replacement.

Moreover, if the \( k\) elements are selected in the following order: \( s_1, s_2, s_3 \ldots, s_k \), then we denote this permutation of \( n \) elements taken \( k \) at a time by the following notation: \( (s_1, s_2, s_3 \ldots, s_k) \).

There is a lot to take in the above definition and so allow us to highlight the important assumptions above.

Assumptions of a Permutation

In order to have a permutation, the following assumptions must be met:

1. We have \(n \) distinct elements.
2. We are selecting \( k\) of the elements.
3. The selection takes place without replacement (meaning there is no repetition of elements).
4. For some reason, we wish to note the order of selection. That is, there has to be something special or unique to being chosen first, and something special or unique to being chosen second, and so on and so forth.

Once all four assumptions are met, we can denote the permutation by writing the elements between parenthesis and placing the elements in the appropriate order.

Here is a classic example of a scenario involving a permutation.

Example 1 \(\PageIndex{1}\)

Suppose that in a race between 26 runners, we are asked to guess who receives the gold, silver and bronze medals. Explain why our guesses can be thought of as a permutation of 26 elements taken 3 at a time. Can you write down a few different outcomes?

Solution

In order to explain why our guesses can be thought of as permutations of 26 elements taken 3 at a time, we simply verify that all four assumptions outlined above apply to the given situation.

1. We have 26 distinct runners.
2. We are selecting 3 of the runners.
3. The selection takes place without replacement since once we choose a runner to receive gold, that same runner cannot also get silver. Hence, there is no repetition.
4. The order of selection should be noted since there is something special or unique to being first (which is receiving gold), something special or unique to being second (which is receiving silver), and something special or unique to being third (which is receiving bronze).

Hence an outcome can be viewed as a permutation of 26 elements taken 3 at a time.

Now suppose the runners are labeled \(A, B, C, D, \ldots, Z \). Here is an example of a permutation of 26 elements taken 3 at a time: \( (M, A, T ) \). In this outcome, runner \(M \) placed first, runner \(A \) placed second, and runner \(T \) placed third.

Here is another (different!) outcome: \( (T, A, M ) \). This outcome is different because here, runner \(T \) placed first, runner \(A \) placed second, and runner \(M \) placed third.

Finally, although this was not asked in the problem, note that \( (Q, V, Q ) \) is not a possible outcome since in a permutation, there is no repetition.

Intuition of a Permutation

Informally speaking, a permutation of \( n \) elements taken \( k\) at a time is just simply an ordered \(k\)-tuple without replacement. For instance, a permutation of \( n \) elements taken \(2 \) at a time is just simply an ordered pair \( (x,y) \). Meanwhile, a permutation of \( n \) elements taken \(3 \) at a time is just simply an ordered triple \( (x,y,z) \), so on and so forth.

With this idea in mind, allow to try and count the number of permutations of \( n \) elements taken \( k\) at a time. We first start off with a concrete example and then generalize.

Example 2 \(\PageIndex{2}\)

Reconsider the race between 26 runners mentioned in Example 1. If we were asked to guess the outcome on who receives gold, silver and bronze, then how many outcomes are possible?

Solution

By the previous discussion, we know that an outcome can be considered a permutation of 26 elements taken 3 at a time. In this question, we are interested in finding the total number of permutations of 26 elements taken 3 at a time. To do this, we note that an outcome is simply an ordered triple that resembles ( __ , __ , __ ). To find the number of such ordered triples, we can think of this as a three-stage experiment.

1. Choose a runner for position 1: 26 choices
2. Choose a runner for position 2: 25 choices
3. Choose a runner for position 3: 24 choices

By The Generalized Principle of Counting, there are \( 26 \times 25 \times 24 = 15,600 \) different permutations.

With the above example in mind, allow us to consider the more general problem:

Example 3 \(\PageIndex{3}\)

How many permutations are there of \( n \) elements taken \( k\) at a time? (Try this on your own before checking the answer!)

Answer

In order to answer this question, we first must understand what the problem is asking us. Based off our intuition of a permutation, this problem is asking us to find the total number of ordered \(k\)-tuples without replacement. This means we must find the number of ways to fill in the following structure: \( ( \underbrace{\_\_}_{1}, \underbrace{\_\_}_{2}, \underbrace{\_\_}_{3}, \ldots, \underbrace{\_\_}_{k-1}, \underbrace{\_\_}_{k} ) \).

We can think of filling in the above spaces as a \(k\)-stage experiment. We proceed in steps:

1. Choose an element for position 1: there are \(n \) choices.

2. Choose an element for position 2: there are \(n - 1 \) choices.

3. Choose an element for position 3: there are \(n - 2 \) choices.

...

...

...

k) Choose an element for position k: there are \(n - (k-1) = n - k + 1 \) choices.

By The Generalized Principle of Counting, the number of permutations of \( n \) elements taken \( k\) at a time is given by \( n \times (n-1) \times (n-2) \times \ldots \times (n - k + 1) \).

The above example proves the following theorem.

Theorem: Total Number of Permutations \(\PageIndex{4}\)

The number of permutations of \( n \) elements taken \( k\) at a time is given by \( n \times (n-1) \times (n-2) \times \ldots \times (n - k + 1) \).

Proof: Already done in Example 3.

For convenience, we often denote the expression \( n \times (n-1) \times (n-2) \times \ldots \times (n - k + 1) \) by \( P_{n,k} \) which is read as "the number of permutations of \( n \) elements taken \( k\) at a time". Hence we make the following slight addition to the above theorem:

Theorem: Total Number of Permutations \(\PageIndex{5}\)

The number of permutations of \( n \) elements taken \( k\) at a time is given by \( P_{n,k} = n \times (n-1) \times (n-2) \times \ldots \times (n - k + 1) \).

Above, we developed a formula for the number of permutations of \( n \) elements taken \( k\) at a time. Allow us to see what happens if we are asked for the number of permutations of \( n \) elements taken \( n \) at a time.

Example 4 \(\PageIndex{6}\)

How many permutations are there of \( n \) elements taken \( n\) at a time? (Try this on your own before checking the answer!)

Answer

In order to answer this question, we first must understand what the problem is asking us. Based off our intuition of a permutation, this problem is asking us to find the total number of ordered \(n\)-tuples without replacement. That is, given \(n\) distinct elements, we are asking how many ways are there to select \(n\) elements and order them. This means we must find the number of ways to fill in the following structure: \( ( \underbrace{\_\_}_{1}, \underbrace{\_\_}_{2}, \underbrace{\_\_}_{3}, \ldots, \underbrace{\_\_}_{n-1}, \underbrace{\_\_}_{n} ) \).

We can think of filling in the above spaces as a \(n\)-stage experiment. We proceed in steps:

1. Choose an element for position 1: there are \(n \) choices.

2. Choose an element for position 2: there are \(n - 1 \) choices.

3. Choose an element for position 3: there are \(n - 2 \) choices.

...

...

...

n) Choose an element for position k: there is 1 choice.

By The Generalized Principle of Counting, the number of permutations of \( n \) elements taken \( n\) at a time is given by \( n \times (n-1) \times (n-2) \times \ldots \times 3 \times 2 \times 1 \).

We denote the above expression as \( n! \).

Formally, allow us to make the following definition and summarize the above result as a theorem.

Definition: \(n!\)

Given a positive integer \(n\), we define \(n!\), read as "\(n\) factorial" to be

\[ n! = n(n-1)(n-2) \ldots (3)(2)(1) \nonumber\ \]

For the special case that \(n=0\), we define \( 0! = 1 \).

Theorem \(\PageIndex{7}\)

Given \(n\) distinct objects, there are \(n!\) ways to arrange them.

Proof: Already done in Example 4.

Example 5 \(\PageIndex{8}\)

How many ways are there to arrange 6 distinct books on a bookshelf?

Solution

By the above theorem, there are \( 6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720 \) different arrangements.

We present one last theorem for this section followed by three examples. The following theorem establishes how the number of permutations of \(n\) elements taken \(k\) at a time can be expressed in terms of factorials.

Theorem \(\PageIndex{1}\)

\( \displaystyle P_{n,k} = \frac{n!}{(n-k)!} \)

Proof: The proof is left as an exercise to the reader.

Example 6 \(\PageIndex{9}\)

Suppose that from a group of 30 people, a president, vice president, secretary and treasurer are to be chosen. How many different outcomes are possible?

Solution 1

For this question, allow us to proceed in steps.

1. We first choose a president. There are 30 choices.
2. We then choose a vice president. There are 29 choices.
3. We then choose a secretary. There are 28 choices.
4. We finally choose a treasurer. There are 27 choices.

By The Generalized Principle of Counting, we see that there are \( 30 \times 29 \times 28 \times 27 = 657,720 \) different choices. (Notice that by invoking The Generalized Principle of Counting, we are saying that each step above is different or distinct. This will be important in the next example!)

Solution 2

We see that the above question satisfies the four assumptions required to have a permutation. That is, we can think of an outcome as an ordered 4-tuple such as \( ( \underbrace{\_\_}_{pres.}, \underbrace{\_\_}_{vp.}, \underbrace{\_\_}_{sec.}, \underbrace{\_\_}_{trea.} ) \). By our theorem, the number of different permutations of 30 elements taken 4 at a time is given by \( P_{30,4} = 30 \times \times 29 \times 28 \times 27 = 657,720 \) choices.

Critique This Solution! \(\PageIndex{10}\)

Suppose that from a group of 30 people, a president, vice president, and two secretaries are to be chosen. How many different outcomes are possible?

Critique This Solution:

For this question, allow us to proceed in steps.

1. We first choose a president. There are 30 choices.
2. We then choose a vice president. There are 29 choices.
3. We then choose a secretary. There are 28 choices.
4. We then choose another secretary. There are 27 choices.

By The Generalized Principle of Counting, we see that there are \( 30 \times 29 \times 28 \times 27 = 657,720 \) different choices.

Alternatively, we see that the above question satisfies the four assumptions required to have a permutation. That is, we can think of an outcome as an ordered 4-tuple such as \( ( \underbrace{\_\_}_{pres.}, \underbrace{\_\_}_{vp.}, \underbrace{\_\_}_{sec.}, \underbrace{\_\_}_{sec.} ) \). By our theorem, the number of different permutations of 30 elements taken 4 at a time is given by \( P_{30,4} = 30 \times \times 29 \times 28 \times 27 = 657,720 \) choices. Hence we get the same answer.

Do you think the above solution is correct or incorrect? Why?

Answer

Unfortunately, the above solution is incorrect! It is incorrect to use The Generalized Principle of Counting. Recall that The Generalized Principle of Counting requires us to have distinct steps! In the proposed solution, steps 3 and 4 are the same.

Additionally, the second solution in using the permutation is incorrect because we have violated the requirement discussed under the assumptions of a permutation. To have a permutation, there must be something special about the order. Here, there is no difference between the third person being chosen and the fourth and hence we no longer have a permutation.

Thus the proposed solutions are incorrect. In order to correctly answer this problem, we need an additional counting structure that will be discussed in the next section.

Example \(\PageIndex{11}\)

In how many different ways can 12 people be seated in a row if two of the people, \(A\) and \(B\), must be seated together?

Critique This Solution:

We have 12 distinct people and we must arrange all 12 people. By our theorem above, there are \( 12! = 479,001,600 \} ways to do so.

Do you think the above solution is correct or incorrect? Why?

Answer

Unfortunately, the above solution is incorrect! While the statement itself is true, (there are indeed \12!\) ways to arrange 12 people), the statement does not answer the appropriate question. In \(12!\), we are obtaining all possible arrangements of the 12 people and hence we get arrange arrangements where person \(A)\) is not seated with person \(B\). So how can we fix this?

Here is some advice: whenever a problem requires certain elements to stick together, a good idea is to "bundle" those elements together. For instance, initially we have the following diagram:

\[ \boxed{A} , ~\boxed{B} , ~ \boxed{C} , ~ \boxed{D} , ~ \boxed{E} ,~ \boxed{F} , ~ \boxed{G} , ~ \boxed{H} , ~ \boxed{I} , ~ \boxed{J} , ~ \boxed{K} , ~ \boxed{L} \nonumber\ \]

However, since person \(A\) must be seated with person \(B\), we can regard them as one element. We accomplish this by "bundling" \(A\) and \(B\) together or alternatively gluing \(A\) and \(B\) side-by-side to make sure they are together. The picture now looks like this:

\[ \boxed{AB} , ~ \boxed{C} , ~ \boxed{D} , ~ \boxed{E} , ~ \boxed{F} , ~ \boxed{G} , ~ \boxed{H} , ~ \boxed{I} , ~ \boxed{J} , ~ \boxed{K} , ~ \boxed{L} \nonumber\ \]

Every arrangement of the 11 blocks above will insure that persons \(A \) and \(B\) are together. Thus, we proceed in steps:

1) Arrange the 11 blocks above. There are 11! ways to do so.

2) Within every arrangement of the 11 blocks, we can switch persons \(A \) and \(B\). That is, we can either have AB or BA. There are 2 choices here.

By The Basic Principle of Counting, we have a total of \( 11! \times 2 = 79,833,600 \) different arrangements where persons \(A\) and \(B\) are seated together.