Symmetric group

Definition

If $n$ is a positive integer, the symmetric group on $n$ letters (often denoted $S_{n}$) is the group formed by all bijections from a set $S$ to itself (under the operation of function composition), where $S$ is an $n$-element set. It is customary to take $S$ to be the set of integers from $1$ to $n$, but this is not strictly necessary. The bijections which are elements of the symmetric group are called permutations.

Note that this means the identity of the group is the identity map on $S$, which is the map sending each element of $S$ to itself.

The order of $S_{n}$ is $n!$.

Cycle Decomposition

Any permutation of a finite set can be written as a product of permutations called cycles. A cycle $\rho$ acting on $S$ fixes all the elements of S outside a nonempty subset $C$ of $S$. On $C$, the action of $\rho$ is as follows: for some indexing $C=\{c_{1},\ldots ,c_{k}\}$ of the elements of $C$, $\rho$ sends $c_{i}$ to $c_{i+1}$ for all $1\leq i\leq k-1$ and sends $c_{k}$ to $c_{1}$. Then one writes

$\rho =(c_{1},\ldots ,c_{k})$

(Sometimes the commas are omitted.) If k > 1, such a $\rho$ is called a k-cycle.

For example, the permutation of the integers from 1 to 4 sending $i$ to $5-i$ for all $1\leq i\leq 4$ can be denoted $(1,4)(2,3)$.

If $C$ is a one-element set, then its element is a fixed point of the permutation. Fixed points are often omitted from permutations written in cycle notation, since any $\rho$ cycling the elements of $C$ as discussed above would be the identity permutation.

Permutational Parity

A 2-cycle is called a transposition. Every permutation in $S_{n}$, for n > 1, can be written as a product of transpositions. A permutation of n points is then called even if it can be written as the product of an even number of transpositions and odd if it can be written as the product of an odd number of transpositions. The nontrivial fact about this terminology is that it is well-defined; that is, no permutation is both even and odd.

The even permutations in $S_{n}$ form a subgroup of $S_{n}$. This subgroup is called the alternating group on n letters and denoted $A_{n}$. In fact, $A_{n}$ is always a normal subgroup of $S_{n}$.

The order of $A_{n}$ is ${\frac {n!}{2}}$.