permutation Permutation 2001-10-20 23:29:24 2007-10-22 10:22:38 Definition Combinatorics \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{graphicx} \usepackage{xypic} 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!$. 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$.