permutation

A permutation of a finite set  $\{a_1,a_2,\mathrm{\dots },a_n\}$  is an arrangement of its elements. For example, if $S=\{A,B,C\}$ then $ABC$, $CAB$ , $CBA$ are three different permutations of $S$.

The number of permutations of a set with $n$ elements is $n!$ (see the rule of product).

A permutation can also be seen as a bijective function of a set into itself. For example, the permutation $ABC\mapsto CAB$ could be seen a function $f:\{A,B,C\}\to \{A,B,C\}$ that assigns:

$$f(A)=C,f(B)=A,f(C)=B.$$

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 $n!$ bijective functions from a set with $n$ 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  $\sigma ={\tau }_1{\tau }_2\mathrm{\cdots }{\tau }_m={\rho }_1{\rho }_2\mathrm{\cdots }{\rho }_n$  are two factorization of a permutation $\sigma$ into transpositions, then $m$ and $n$ 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 $n$. The subset of even permutations becomes a subgroup called the alternating group of order $n$.

Title	permutation
Canonical name	Permutation
Date of creation	2013-03-22 11:51:45
Last modified on	2013-03-22 11:51:45
Owner	alozano (2414)
Last modified by	alozano (2414)
Numerical id	13
Author	alozano (2414)
Entry type	Definition
Classification	msc 03-00
Classification	msc 20B99
Classification	msc 46L05
Classification	msc 82-00
Classification	msc 83-00
Classification	msc 81-00
Classification	msc 22A22
Classification	msc 05A05
Related topic	Bijection
Related topic	Function
Related topic	Cycle2
Related topic	CycleNotation
Related topic	OneLineNotationForPermutations