Permutation group/Number/2/Introduction/Section

Definition

For a set $M$, we call the set

$\mathrm{Aut}(M)=\mathrm{Perm}(M)=\{\phi :M⟶M\mid \phi \text{ bijective}\}$

of all bijective mappings

on $M$ the automorphism group or the permutation group of $M$.

The operation is the composition of mappings, therefore, it is associative, the identity is the neutral element. The inverse element for a bijective mapping is just the inverse mapping. Hence, this is a group. A bijective mapping $\phi :M\to M$ is also called a permutation.

For the finite set $I=\{1,\dots ,n\}$, we also write

$S_n=\mathrm{Perm}(I).$

A permutation of a finite set can be described with a (complete) value table or with an arrow diagram.

Definition

Let $M$ be a finite set and let $\pi$ be a permutation on $M$. Then $\pi$ is called a cycle of order $r$ (or of length $r$), if there exists a subset $Z\subseteq M$, containing $r$ elements and such that $\pi$ is on $M\setminus Z$ the identity and such that $\pi$ commutes the elements of $Z$ in a cyclic way. If $Z=\{z,\pi (z),{\pi }^2(z),\dots ,{\pi }^{r-1}(z)\}$, then we write

$\pi =⟨z,\pi (z),{\pi }^2(z),\dots ,{\pi }^{r-1}(z)⟩.$

Example

We consider the permutation

$x$	$1$	$2$	$3$	$4$	$5$
$\pi (x)$	$2$	$1$	$5$	$3$	$4$

We can write this as the product of the two cycles $⟨1,2⟩$ and $⟨3,5,4⟩$.

An element $x\in M$ with $\pi (x)=x$ is called a fixed point of the permutation. The (action) scope of a permutation is the set of points from $M$ which are not fixed points. For a cycle, the set $Z$ is the scope. We mention without proof that every permutation is a product of cycles. Such a product representation is called a cycle representation.

Definition

For a natural number $n$, one puts

$n!:=n(n-1)(n-2)\cdots 3\cdot 2\cdot 1,$

and calls this $n$ factorial.

Lemma

Let $M$ be a finite set with $n$ elements. Then the permutation group

$\mathrm{Perm}(M)\cong S_n$

contains exactly $n!$ elements.

Proof

Let $M=\{1,\dots ,n\}$. For $1$, there are $n$ possible images, for $2$, there are $n-1$ possible images remaining, for $3$, there are $n-2$ possible images remaining, etc. Therefore, there are altogether

$n(n-1)(n-2)\cdots 2\cdot 1=n!$

possible permutations.

$◻$