Search
STATLECT > 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.

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 is:[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:

  1. Exercise set 1 (combinatorial problems involving permutations)

by
About | Contacts | Privacy and terms of use | Sitemap