Any one-to-one transformation of a set of ordered elements onto itself is called a permutation of elements of the set.
If S is an ordered set of the first n natural numbers:
then a permutation of S gives a set of the numbers arranged in a particular way:
.
A permutation, which changes the order of two elements of a set and fixes all others, is called a transposition.
Example of a permutation:
(*)Example of a transposition:
Every permutation of ordered elements can be expressed as a sequence of transpositions.
For instance, permutation (*) is a sequence of three transpositions:
A permutation of S contains the inversion
of elements 
and 
, if
j < k but 
.
Example:
The permutation {2, 4, 1, 3} contains the inversions of the following elements:
2 and 1,
4 and 1,
4 and 3.
The inversion parity of a permutation is the number of inversions of elements that the permutation has.
A permutation is called even if it has an even number of inversions. This means that an even permutation includes an even number of transpositions of S.
An odd permutation has an odd number of inversions of elements. This means that an odd permutation contains a sequence of an odd number of transpositions of S.
In the above example, permutation (*) is odd.
| Theorem 1 |
 |
|
Any transposition changes the inversion parity
of a given permutation
|
| Theorem 2 |
|
Given the set  , there are n!
different permutations of S |
