StatlectThe Digital Textbook
Index > Mathematical tools

Permutations

This lecture introduces permutations, one of the most important concepts in combinatorial analysis.

We first deal with permutations without repetition, also called simple permutations, and then with permutations with repetition.

Table of Contents

Permutation of n elements without repetition

A permutation without repetition of n objects is one of the possible ways of ordering the n objects.

A permutation without repetition is also simply called a permutation.

The following subsections give a slightly more formal definition of permutation and deal with the problem of counting the number of possible permutations of n objects.

Definition of permutation without repetition

Let a_1, a_2,..., a_n be n objects. Let $s_{1}$, $s_{2}$, ..., $s_{n}$ be n slots to which the n objects can be assigned. A permutation (or permutation without repetition or simple permutation) of a_1, a_2,..., a_n is one of the possible ways to fill each of the n slots with one and only one of the n objects (with the proviso that each object can be assigned to only one slot).

Example Consider three objects a_1, a_2 and $a_{3}$. There are three slots ($s_{1}$, $s_{2}$ and $s_{3}$) to which we can assign the three objects ($a_{1} $, a_2 and $a_{3}$). There are six possible permutations of the three objects (six possible ways to fill the three slots with the three objects):[eq1]

Number of permutations without repetition

Denote by $P_{n}$ the number of possible permutations of n objects. How much is $P_{n}$ in general? In other words, how do we count the number of possible permutations of n objects?

The number $P_{n}$ can be derived by noting that filling the n slots is a sequential problem:

  1. First, we assign an object to the first slot. There are n objects that can be assigned to the first slot, so there are [eq2]

  2. Then, we assign an object to the second slot. There were n objects, but one has already been assigned to a slot. So, we are left with $n-1$ objects that can be assigned to the second slot. Thus, there are[eq3]and[eq4]

  3. Then, we assign an object to the third slot. There were n objects, but two have already been assigned to a slot. So, we are left with $n-2$ objects that can be assigned to the third slot. Thus, there are[eq5]and[eq6]

  4. An so on, until only one object and one free slot remain.

  5. Finally, when only one free slot remains, we assign the remaining object to it. There is only one way to do this. Thus, there are[eq7]and[eq8]

Therefore, by the above sequential argument, the total number of possible permutations of n objects is[eq9]

The number $P_{n}$ is usually indicated as follows:[eq10]where $n!$ is read "n factorial", with the convention that[eq11]

Example The number of possible permutations of $5$ objects is[eq12]

Permutation of n elements with repetition

A permutation with repetition of n objects is one of the possible ways of selecting another set of n objects from the original one. The selection rules are:

  1. each object can be selected more than once;

  2. the order of selection matters (the same n objects selected in different orders are regarded as different permutations).

Thus, the difference between simple permutations and permutations with repetition is that objects can be selected only once in the former, while they can be selected more than once in the latter.

The following subsections give a slightly more formal definition of permutation with repetition and deal with the problem of counting the number of possible permutations with repetition.

Definition of permutation with repetition

Let a_1, a_2,..., a_n be n objects. Let $s_{1}$, $s_{2}$, ..., $s_{n}$ be n slots to which the n objects can be assigned. A permutation with repetition of a_1, a_2,..., a_n is one of the possible ways to fill each of the n slots with one and only one of the n objects (with the proviso that an object can be assigned to more than one slot).

Example Consider two objects a_1 and a_2. There are two slots to fill ($s_{1} $ and $s_{2}$). There are four possible permutations with repetition of the two objects (four possible ways to assign an object to each slot, being allowed to assign the same object to more than one slot):[eq13]

Number of permutations with repetition

Denote by $P_{n}^{prime }$ the number of possible permutations with repetition of n objects. How much is $P_{n}^{prime }$ in general? In other words, how do we count the number of possible permutations with repetition of n objects?

We can derive a general formula for $P_{n}^{prime }$ by using a sequential argument:

  1. First, we assign an object to the first slot. There are n objects that can be assigned to the first slot, so there are [eq14]

  2. Then, we assign an object to the second slot. Even if one object has been assigned to a slot in the previous step, we can still choose among n objects, because we are allowed to choose an object more than once. So, there are n objects that can be assigned to the second slot and[eq15]and[eq16]

  3. Then, we assign an object to the third slot. Even if two objects have been assigned to a slot in the previous two steps, we can still choose among n objects, because we are allowed to choose an object more than once. So, there are n objects that can be assigned to the third slot and[eq17]and[eq18]

  4. An so on, until we are left with only one free slot (the n-th).

  5. When only one free slot remains, we assign one of the n objects to it. Thus, there are:[eq19]and[eq20]

Therefore, by the above sequential argument, the total number of possible permutations with repetition of n objects is[eq21]

Example The number of possible permutations with repetition of $3$ objects is[eq22]

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

There are 5 seats around a table and 5 people to be seated at the table. In how many ways can they seat themselves?

Solution

Sitting 5 people at the table is a sequential problem. We need to assign a person to the first chair. There are 5 possible ways to do this. Then we need to assign a person to the second chair. There are 4 possible ways to do this, because one person has already been assigned. An so on, until there remain one free chair and one person to be seated. Therefore, the number of ways to seat the 5 people at the table is equal to the number of permutations of 5 objects (without repetition). If we denote it by $P_{5}$, then[eq23]

Exercise 2

Bob, John, Luke and Tim play a tennis tournament. The rules of the tournament are such that at the end of the tournament a ranking will be made and there will be no ties. How many different rankings can there be?

Solution

Ranking 4 people is a sequential problem. We need to assign a person to the first place. There are 4 possible ways to do this. Then we need to assign a person to the second place. There are 3 possible ways to do this, because one person has already been assigned. An so on, until there remains one person to be assigned. Therefore, the number of ways to rank the 4 people participating in the tournament is equal to the number of permutations of 4 objects (without repetition). If we denote it by $P_{4}$, then[eq24]

Exercise 3

A byte is a number consisting of 8 digits that can be equal either to 0 or to 1. How many different bytes are there?

Solution

To answer this question we need to follow a line of reasoning similar to the one we followed when we derived the number of permutations with repetition. There are 2 possible ways to choose the first digit and 2 possible ways to choose the second digit. So, there are 4 possible ways to choose the first two digits. There are 2 possible ways two choose the third digit and 4 possible ways to choose the first two. Thus, there are 8 possible ways to choose the first three digits. An so on, until we have chosen all digits. Therefore, the number of ways to choose the 8 digits is equal to[eq25]

The book

Most of the learning materials found on this website are now available in a traditional textbook format.