Permutation group/Number/2/Introduction/Section

Definition

For a set ${}M$, we call the set

${}\operatorname {Aut} \,(M)=\operatorname {Perm} \,(M)={\left\{\varphi :M\longrightarrow M\mid \varphi {\text{ bijective}}\right\}}\,$

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 ${}\varphi \colon M\rightarrow M$ is also called a permutation.

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

${}S_{n}=\operatorname {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$, 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),\ldots ,\pi ^{r-1}(z)\}$, then we write

${}\pi =\langle z,\pi (z),\,\pi ^{2}(z),\ldots ,\pi ^{r-1}(z)\rangle \,.$

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 ${}\langle 1,2\rangle$ and ${}\langle 3,5,4\rangle$.

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

${}\operatorname {Perm} \,(M)\cong S_{n}\,$

contains exactly ${}n!$ elements.

Proof

Let ${}M=\{1,\ldots ,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.

$\Box$