# 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

### Definition

A *permutation* is a 1-1 correspondence of a set V onto itself:

Being able to count elements in the set V means the set can be written as _{1}, v_{2}, ..., v_{n}}._{1}, v_{2}, ..., v_{n}}_{i1}, v_{i2}, ..., v_{in}}*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

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,

- 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, 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,

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

### 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

- Various ways to define a permutation
- Counting and listing all permutations
- Johnson-Trotter Algorithm: Listing All Permutations

|Contact| |Front page| |Contents| |Did you know?| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

64490506 |