Permutation

A permutation of a finite set is an arrangement of its elements. For example, if then , , are three different permutations of .

The number of permutations of a set with elements is .

A permutation can also be seen as a bijective function of a set into itself. For example, the permutation could be seen a function that assigns:

In fact, every bijection of a set into itself gives a permutation, and any permutation gives rise to a bijective function.

Therefore, we can say that there are bijective functions from a set with elements into itself.

Using the function approach, it can be proved that any permutation can be expressed as a composition of disjoint cycles and also as composition of (not necessarily disjoint) transpositions.

Moreover, if are two factorization of a permutation into transpositions, then and must be both even or both odd. So we can label permutations as even or odd depending on the number of transpositions for any decomposition.

Permutations (as functions) form in general a non-abelian group with function composition as binary operation called symmetric group of order . The subset of even permutations becomes a subgroup called the alternating group of order .