# 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 |