Permutation

Definition

A permutation on a set is defined as a bijective function from the set to itself.

The set of all permutations on a set forms a group with the group operation being function composition, the identity element being the identity function, and the inverse of a permutation being the inverse function. This group is termed the symmetric group on the set. A permutation on a set can thus also be defined as an element of the symmetric group on the set.

Notation

Two-line notation for permutations

Further information: two-line notation for permutations

Suppose $S$ is a finite set and $\sigma$ is a permutation of $S$. A two-line notation for $\sigma$ is a two-line description that uniquely determines $\sigma$. The first row lists the elements of $S$. In the second row, we list, below each element of $S$, its image under $\sigma$.

For instance, consider the permutation on $\{1,2,3,4,5 \}$ that sends $x$ to $6 - x$. The two-line notation for this permutation is:

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 3 & 2 & 1 \\\end{pmatrix}$.

One-line notation for permutations

Further information: one-line notation for permutations

The one-line notation for a permutation is an abbreviated form of the two-line notation where we write only the second line, because the first line is understood. This happens, for instance, when the elements of $S$ come with a standard ordering and it is understood that the first line, if written, would have the elements in that order.

Cycle decomposition for permutations

Further information: cycle decomposition for permutations, understanding the cycle decomposition

The cycle decomposition of a permutation is an expression of the permutation as a product of disjoint cycles. For instance, the permutation on $\{ 1,2,3,4,5 \}$ has three cycles: $(1,5)$, $(2,4)$ and $(3)$. The cycle decomposition is this $(1,5)(2,4)(3)$.