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
1. Definition of permutation without repetition
2. Number of permutations without repetition
Permutation of n elements with repetition
1. Definition of permutation with repetition
2. Number of permutations with repetition
Solved exercises

Permutation of n elements without repetition

A permutation without repetition of objects is one of the possible ways of ordering the 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 objects.

Definition of permutation without repetition

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

Example Consider three objects , and $a_{3}$ . There are three slots ( $s_{1}$ , $s_{2}$ and $s_{3}$ ) to which we can assign the three objects ( $a_{1}$ , 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 objects. How much is $P_{n}$ in general? In other words, how do we count the number of possible permutations of objects?

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

First, we assign an object to the first slot. There are objects that can be assigned to the first slot, so there are
Then, we assign an object to the second slot. There were objects, but one has already been assigned to a slot. So, we are left with objects that can be assigned to the second slot. Thus, there areand
Then, we assign an object to the third slot. There were objects, but two have already been assigned to a slot. So, we are left with objects that can be assigned to the third slot. Thus, there areand
An so on, until only one object and one free slot remain.
Finally, when only one free slot remains, we assign the remaining object to it. There is only one way to do this. Thus, there areand

Therefore, by the above sequential argument, the total number of possible permutations of objects is

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

Example The number of possible permutations of objects is

Permutation of n elements with repetition

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

each object can be selected more than once;
the order of selection matters (the same 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 , ,..., be objects. Let $s_{1}$ , $s_{2}$ , ..., $s_{n}$ be slots to which the objects can be assigned. A permutation with repetition of , ,..., is one of the possible ways to fill each of the slots with one and only one of the objects (with the proviso that an object can be assigned to more than one slot).

Example Consider two objects and . 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 objects. How much is $P_{n}^{prime }$ in general? In other words, how do we count the number of possible permutations with repetition of objects?

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

First, we assign an object to the first slot. There are objects that can be assigned to the first slot, so there are
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 objects, because we are allowed to choose an object more than once. So, there are objects that can be assigned to the second slot andand
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 objects, because we are allowed to choose an object more than once. So, there are objects that can be assigned to the third slot andand
An so on, until we are left with only one free slot (the -th).
When only one free slot remains, we assign one of the objects to it. Thus, there are:and

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

Example The number of possible permutations with repetition of objects is

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]

How to cite

Please cite as:

Taboga, Marco (2021). "Permutations", Lectures on probability theory and mathematical statistics. Kindle Direct Publishing. Online appendix. https://www.statlect.com/mathematical-tools/permutations.