Permutations: Rearranging Things
A permutation is a rearrangement of a set of objects. Pick up all the items, put them back in a different order — that’s a permutation.
More precisely: a permutation of a set is a bijection from the set to itself. Every element goes somewhere, and no two elements go to the same place.
Two-line notation
The clearest way to write a permutation is two-line notation. The top row lists the original positions; the bottom row shows where each one goes:
$$\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$$
This says: 1 goes to 2, 2 goes to 3, 3 goes to 1.
The six permutations of {1, 2, 3}
With three objects, there are $3! = 6$ possible rearrangements:
| Two-line notation | What it does |
|---|---|
| $\begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}$ | Leave everything in place (the identity) |
| $\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}$ | Swap 1 and 2, leave 3 |
| $\begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}$ | Leave 1, swap 2 and 3 |
| $\begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}$ | Swap 1 and 3, leave 2 |
| $\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$ | Rotate: $1 \to 2 \to 3 \to 1$ |
| $\begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}$ | Rotate the other way: $1 \to 3 \to 2 \to 1$ |
The number of permutations grows fast: 3 objects give 6, 4 objects give 24, 5 give 120. In general, $n$ objects give $n!$ permutations.
Select a permutation of {1, 2, 3} and watch the arrows show where each element goes. Every element has exactly one arrow in, and exactly one arrow out — that’s what makes it a bijection.
Key observations
- The identity permutation leaves everything in place. It’s a valid permutation (the function $f(x) = x$ is a bijection).
- Every permutation is invertible — you can always undo a rearrangement by putting everything back. If 1 went to 3 and 3 went to 1, the inverse swaps them back.
- With $n$ objects, there are exactly $n!$ permutations. This number is called the order of the set of all permutations.
These optional nodes cover specific concepts in more detail: