Transposition Permutations

Transposition Permutations

Recall from the Decomposition of Permutations as Products of Disjoint Cycles page that if $\sigma$ is a permutation of the $n$-element set $\{ 1, 2, ..., n \}$ and if $\sigma$ is not the identity permutation $\epsilon$ then $\sigma$ can be written as a finite product of disjoint cycles.

We will soon look at another type of decomposition of a permutation, though, we will first need to give a definition of a special type of cycle known as a transposition.

Definition: A Transposition is a cycle of length $2$. That is, for $a, b \in \{ 1, 2, ..., n \}$, if $\sigma (a) = b$ and $\sigma (b) = a$ then $(ab) = (ba)$ is a transposition.

For example, consider the set $\{1,2,3,4,5 \}$. Then the transposition $(12)$ is given by:

(1)
\begin{align} \quad (12) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 1 & 3 & 4 & 5 \end{pmatrix} \end{align}

Furthermore, the transposition $(13)$ is given by:

(2)
\begin{align} \quad (13) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 2 & 1 & 4 & 5 \end{pmatrix} \end{align}

In the following theorem we will see that for the finite $n$-element set $\{ 1, 2, ..., n \}$ there will be precisely $\sum_{k=1}^{n-1} k$ distinct transposition.

Theorem 1: The number of distinct transpositions of the finite $n$-element set $\{ 1, 2, ..., n \}$ is $\sum_{k=1}^{n-1} k$.
  • Proof: All transpositions of $\{1, 2, ..., n \}$ will be of the form $(ab)$. Set $a = 1$. Then for $b \neq 1$, $(1b)$ is a transposition. We must have that $b \in \{2, 3, ..., n \}$ and so $n - 1$ transpositions of the form $(1b)$ exist.
  • Now set $a = 2$. Then for $b \neq 2, 1$, $(2b)$ will be a transposition that hasn't been accounted for yet. We have that $b \in \{3, 4, ..., n \}$ and so $n - 2$ transpositions of the form $(2b)$ exist.
  • In general, by setting $a = k$ we will see that $n - k$ unaccounted transpositions of the form $(kb)$ exist where $b$ is an integer such that $k < b \leq n$.
  • Repeating this process gives us $(n - 1) + (n - 2) + ... + (n - k) + ... + 2 + 1$ distinct transpositions total, i.e., the number of transpositions of the finite $n$-element set $\{ 1, 2, ..., n \}$ is $\sum_{k=1}^{n-1} k$. $\blacksquare$
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License