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 (see the rule of product).
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 .
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 |