Permutationsgruppe/Anzahlberechnung/Einführung/2/Textabschnitt

Definition

Zu einer Menge ${}M$ nennt man die Menge

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

der bijektiven Selbstabbildungen die Automorphismengruppe oder die Permutationsgruppe zu ${}M$.

Die Verknüpfung ist die Hintereinanderschaltung von Abbildungen und somit assoziativ, die Identität ist das neutrale Element. Das inverse Element zu einer bijektiven Abbildung ist einfach die Umkehrabbildung. Damit handelt es sich um eine Gruppe. Eine bijektive Selbstabbildung ${}\varphi \colon M\rightarrow M$ nennt man auch eine Permutation.

Für eine endliche Menge  ${}I=\{1,\ldots ,n\}$  schreibt man

${}S_{n}=\operatorname {Perm} \,(I)\,.$

Eine endliche Permutation kann man beispielsweise mit einer (vollständigen) Wertetabelle oder mit einem Pfeildiagramm beschreiben.

Definition

Es sei ${}M$ eine endliche Menge und ${}\pi$ eine Permutation auf ${}M$. Man nennt ${}\pi$ einen Zyklus der Ordnung ${}r$ (oder der Länge ${}r$), wenn es eine ${}r$-elementige Teilmenge  ${}Z\subseteq M$  derart gibt, dass ${}\pi$ auf ${}M\setminus Z$ die Identität ist und ${}\pi$ die Elemente aus ${}Z$ zyklisch vertauscht. Wenn  ${}Z=\{z,\pi (z),\,\pi ^{2}(z),\ldots ,\pi ^{r-1}(z)\}$  ist, so schreibt man einfach

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

Beispiel

Wir betrachten die Permutation

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

Man kann sie als Produkt der beiden Zyklen ${}\langle 1,2\rangle$ und ${}\langle 3,5,4\rangle$ schreiben.

Ein Element  ${}x\in M$  mit  ${}\pi (x)=x$  nennt man Fixpunkt der Permutation. Der Wirkungsbereich einer Permutation ist die Menge der Punkte aus ${}M$, die keine Fixpunkte sind. Bei einem Zyklus ist ${}Z$ der Wirkungsbereich. Jede Permutation ist ein Produkt von Zyklen, was wir hier ohne Beweis erwähnen. Eine solche Produktdarstellung heißt Zyklendarstellung.

Definition

Zu einer natürlichen Zahl ${}n$ nennt man die Zahl

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

die Fakultät von ${}n$ (sprich ${}n$ Fakultät).

Lemma

Es sei ${}M$ eine endliche Menge mit ${}n$ Elementen.

Dann besitzt die Permutationsgruppe  ${}\operatorname {Perm} \,(M)\cong S_{n}$  genau ${}n!$ Elemente.

Beweis

Es sei  ${}M={\{1,\ldots ,n\}}$.  Für die ${}1$ gibt es ${}n$ mögliche Bilder, für ${}2$ gibt es noch ${}n-1$ mögliche Bilder, für ${}3$ gibt es noch ${}n-2$ mögliche Bilder, usw. Daher gibt es insgesamt

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

mögliche Permutationen.

$\Box$