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 Zykel der Ordnung ${}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 Zykel ${}\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 Zykel ist ${}Z$ der Wirkungsbereich. Jede Permutation ist ein Produkt von Zykeln, was wir hier ohne Beweis erwähnen. Eine solche Produktdarstellung heißt Zykeldarstellung.

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$