Permutation Group - Transpositions, Simple Transpositions, Inversions and Sorting

Transpositions, Simple Transpositions, Inversions and Sorting

A 2-cycle is known as a transposition. A simple transposition in S_n is a 2-cycle of the form (i i + 1).

For a permutation p in S_n, a pair (i, j)∈I_n is a permutation inversion, if when i<j, we have p(i) > p(j).

Every permutation can be written as a product of simple transpositions; furthermore, the number of simple transpositions one can write a permutation p in S_n can be the number of inversions of p and if the number of inversions in p is odd or even the number of transpositions in p will also be odd or even corresponding to the oddness of p.