# permutation

A permutation of a finite set$\{a_{1},\,a_{2},\,\ldots,\,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,\qquad f(B)=A,\qquad 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}\cdots\tau_{m}=\rho_{1}\rho_{2}\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