Permutations: Introduction

A set V consists of n elements if its elements can be counted 1, 2,..., n. In other words, the set V can be brought into a 1-1 correspondence with the set {1, 2, ..., n}. Often it's more convenient to start counting from 0. Then we get the set {0, 1, 2, ..., n-1}.

Definition

A permutation is a 1-1 correspondence of a set V onto itself: f: V → V.

Being able to count elements in the set V means the set can be written as {v₁, v₂, ..., v_n}. However, a set may be counted in many different ways. For example, a set of two elements can be counted in exactly two ways. The first element first and the second second or the first element second and the second first. A permutation is a way of counting elements in a set. What was {v₁, v₂, ..., v_n} for one counting is {v_i₁, v_i₂, ..., v_{i_n}} for another. In other words, a permutation is a way of reindexing a set. Most often for the sake of convenience, when discussing permutations, indices is all that's considered and the symbol v for the set's element is omitted. This makes sense too. For then we just talk of permutations of the (index) set {1, 2, 3, ..., n}.

In how many ways may one count a set of n elements? Or, which is the same, how many permutations are there of (a set of ) n elements?

Definition

The number of permutations of a set of n elements is denoted n! (pronounced n factorial.)

Thus n! is the number of ways to count a set of n elements. As we saw, 2! = 2. Obviously, 1! = 1, 3! = 6. Indeed, there are just six ways to count three elements:

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

How many ways are there to count an empty set, the set with 0 elements? (Note that {0} contains one element thus is not empty. The empty set contains no elements at all - {}.) Since there is nothing to count the question is In how many ways can one do nothing? A mathematical answer to this is just one: 0! = 1.

An aside

There is just one way to do nothing so that 0! = 1. However, the result of this activity is nothing or, in math parlance, 0. You may enjoy the following question. Guess the next number in the following sequence

0, 1, 2, 720!

I placed the answer to the question at the bottom of this page.

What's 4!? There are 4 ways to select the first element. There remain only three candidates for the second position and, after this was selected, only two candidates for the third position. The remaining element automatically goes to the fourth place. Therefore, 4! = 4·3·2. Similarly, 5! = 5·4·3·2 = 5·4!.

Here is another way to do this. Look at the six permutations of a 3-element set. Let's try mimicking this for a set of n elements. There are n ways to select the first element. For each of these, by definition, the remaining (n-1) elements can be counted in (n-1)! ways. Therefore, there are n·(n - 1)! ways to count an n-element set.

Theorem

For all integer n > 0, n! = n·(n-1)!.

References

J. Landin, An Introduction to Algebraic Structures, Dover, NY, 1969.

Answer to the problem

720! = (6!)! = ((3!)!)!, i.e. three followed by three factorials.
2 = 2! = (2!)!, i.e. two followed by two factorials.
1 = 1!

and finally, 0 = 0 followed by zero factorials - a result of doing nothing.

The answer then is 4!!!! The number is quite big (how big?). So that computing it would take a lot of effort.

Permutations

Transpositions

Groups of Permutations

Sliders

Puzzles on graphs

Equation in Permutations

71947120