permutation


A permutationMathworldPlanetmath of a finite setMathworldPlanetmath{a1,a2,,an}  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 ABCCAB could be seen a function f:{A,B,C}{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 compositionMathworldPlanetmath of disjoint cycles and also as composition of (not necessarily disjoint) transpositionsMathworldPlanetmath.

Moreover, if  σ=τ1τ2τm=ρ1ρ2ρn  are two factorization of a permutation σ 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 groupMathworldPlanetmath with function composition as binary operationMathworldPlanetmath called symmetric groupMathworldPlanetmathPlanetmath of order n. The subset of even permutationsMathworldPlanetmath becomes a subgroupMathworldPlanetmathPlanetmath called the alternating groupMathworldPlanetmath 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