Permutations of Elements in a Set as Functions

Consider the set $S = \{ 1, 2, 3, 4, 5 \}$. We often say that a permutation of the elements in the set $S$ is an ordered list of length $n$ that contains each element in $S$ exactly once. For example, $(4, 2, 1, 3, 5)$ and $(1, 2, 5, 3, 4)$ are permutations of the elements in $S$.

We can instead give a more formal definition of a permutation of elements in a set $S$ in terms of functions.

Definition: Let $S$ be a set. A Permutation is a bijective function $\sigma : S \to S$.

For example, if we consider the set $S = \{1, 2, 3, 4, 5 \}$ and the permutation $(4, 2, 1, 3, 5)$ from earlier, then we can define a bijective function $\sigma : S \to S$ which gives us this permutation. Namely we define $\sigma (1) = 4$, $\sigma(2) = 2$, $\sigma(3) = 1$, $\sigma(4) = 3$, and $\sigma(5) = 5$. Therefore, any permutation of elements from $S$ is of the form:

(1)

\begin{align} \quad (\sigma(1), \sigma(2), \sigma(3), \sigma(4), \sigma(5)) \end{align}

In general, if $S$ is an $n$-element set and $\sigma : S \to S$ is a bijective function, then a permutation of the elements $S$ is:

(2)

\begin{align} \quad (\sigma(1), \sigma(2), ..., \sigma(n)) \end{align}

Notice that we require $\sigma$ to be injective because if not, then $\sigma(k) = \sigma(j)$ for some $k, j \in \{1, 2, ..., n \}$ and $k \neq j$, so the element $\sigma(k) = \sigma(j)$ is repeated in the permutation which is not allowed since by definition, elements in a set cannot be repeated (otherwise the "set" would actually be a multiset). We also require that $\sigma$ is surjective because if not, then there exists an element in $S$ that is not accounted for in the permutation. Therefore the requirement that $\sigma$ is bijective ensures us that each element in $S$ is used exactly once in forming the permutation of elements from $S$.

Now if $S = \{ x_1, x_2, ..., x_n \}$ is a finite $n$-element set, then there is a type of notation that is particularly useful to represent the function $\sigma$ of a permutation. This notation is called Cauchy's Two-Line Notation which constructs a $2 \times n$ matrix whose first row consists of the elements $x_1, x_2, ..., x_n$ and whose second row consists of the corresponding elements $\sigma(x_1), \sigma(x_2), ..., \sigma(x_n)$ as:

(3)

\begin{align} \quad \sigma = \begin{pmatrix} x_1 & x_2 & \cdots & x_n\\ \sigma(x_1) & \sigma(x_2) & \cdots & \sigma(x_n) \end{pmatrix} \end{align}

Often times we will be looking at permutations of the set $S = \{1, 2, ..., n \}$ for some positive integer $n$, and so by using Cauchy's two-line notation we will often write:

(4)

\begin{align} \quad \sigma = \begin{pmatrix} 1 & 2 & \cdots & n\\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{pmatrix} \end{align}