03-00-Permutation.tex

\documentclass[12pt]{article}
\usepackage{pmmeta}
\pmcanonicalname{Permutation}
\pmcreated{2013-03-22 11:51:45}
\pmmodified{2013-03-22 11:51:45}
\pmowner{alozano}{2414}
\pmmodifier{alozano}{2414}
\pmtitle{permutation}
\pmrecord{13}{30434}
\pmprivacy{1}
\pmauthor{alozano}{2414}
\pmtype{Definition}
\pmcomment{trigger rebuild}
\pmclassification{msc}{03-00}
\pmclassification{msc}{20B99}
\pmclassification{msc}{46L05}
\pmclassification{msc}{82-00}
\pmclassification{msc}{83-00}
\pmclassification{msc}{81-00}
\pmclassification{msc}{22A22}
\pmclassification{msc}{05A05}
%\pmkeywords{Combinatorics}
\pmrelated{Bijection}
\pmrelated{Function}
\pmrelated{Cycle2}
\pmrelated{CycleNotation}
\pmrelated{OneLineNotationForPermutations}

\endmetadata

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
%%%%\usepackage{xypic}
\begin{document}
A \emph{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 $A B C$, $C A B$ , $C B A$ 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 $A B C \mapsto C A B$ 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 \emph{even} or \emph{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 \emph{symmetric group of order $n$}. The subset of even permutations becomes a subgroup called the alternating group of order $n$.
%%%%%
%%%%%
%%%%%
%%%%%
\end{document}