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)Furthermore, the transposition $(13)$ is given by:
(2)In the following proposition 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.
| Proposition 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$