Permutation¶

Definition¶

A permutation of a set $A$ is a bijective function

\pi\colon A\to A.

Interpretation¶

A permutation rearranges the elements of a set without losing or duplicating any element: each element is moved to a place in the same set, and each place receives exactly one element.

Arrows from the numbers 1 to 4 on the left to their images under a permutation on the right, 1 to 3, 2 to 1, 3 to 4 and 4 to 2, each number hit exactly once.

The arrows send $1\mapsto3$ $3$ , $2\mapsto1$ $1$ , $3\mapsto4$ and $4\mapsto2$ $2$ , and every number on the right is hit by exactly one arrow, which is bijectivity. In two-row notation, $\pi=\begin{pmatrix}1&2&3&4\\3&1&4&2\end{pmatrix}$ lists the images in the bottom row. Following the arrows from $1$ gives the cycle $1\mapsto3\mapsto4\mapsto2\mapsto1$ $1$ , written $(1\,3\,4\,2)$ . Reversing every arrow gives the inverse $\pi^{-1}=(1\,2\,4\,3)$ $(1243)$ , which undoes $\pi$ .

Bijectivity has two halves. Injective means that no two elements land in the same place, so nothing is duplicated; surjective means that every place is filled, so nothing is lost. On a finite set either half implies the other, since $n$ elements land in $n$ places. On an infinite set they differ, as the map $n\mapsto2n$ on $\mathbb{N}$ in the Examples shows.

To count the permutations of an $n$ -element set, choose the image of the first element in $n$ ways, that of the second in $n-1$ ways, and so on, which gives $n!$ (factorial). This is the same count as for ordered arrangements of $n$ distinct objects. Under composition the permutations of $\{1,\ldots,n\}$ form the symmetric group $S_n$ .

Key Results¶

The composition of two permutations is again a permutation.
A finite set with $n$ elements has $n!$ permutations.

Examples¶

Swapping two elements and leaving the rest fixed is a permutation.
On $A=\{1,2,3\}$ ${1, 2, 3}$ , the map $\pi(1)=2$ $2$ , $\pi(2)=3$ $3$ , $\pi(3)=1$ is a permutation. The map $f(n)=2n$ on $\mathbb{N}$ is injective but not surjective, so it is not a permutation of $\mathbb{N}$ .

Prerequisites¶

Bijection and Inverse Function

Sources¶

Math II: Linear Algebra · Week 1

Keywords: rearrangement, bijection of a set onto itself Symbols: natural numbers, pi

Last updated: 20 October 2026 03:02