Permutationsgruppe/Anzahlberechnung/Einführung/Textabschnitt

Definition

Zu einer Menge $M$ nennt man die Menge

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

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

Eine bijektive Selbstabbildung $\phi :M\to M$ nennt man auch eine Permutation. Für eine endliche Menge $I=\{1,\dots ,n\}$ schreibt man $S_n=\mathrm{Perm}(I)$. Eine endliche Permutation kann man beispielsweise mit einer (vollständigen) Wertetabelle oder mit einem Pfeildiagramm beschreiben.

Lemma

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

Dann besitzt die Permutationsgruppe  $\mathrm{Perm}(M)\cong S_n$  genau $n!$ Elemente.

Beweis

Es sei  $M=\{1,\dots ,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.

$◻$

Lemma

Es sei $M$ eine Menge und $N\subseteq M$ eine Teilmenge.

Dann gibt es eine natürliche injektive Abbildung

$\mathrm{Perm}(N)⟶\mathrm{Perm}(M),\sigma ⟼\tilde{\sigma },$

wobei $\tilde{\sigma }$ auf $N$ gleich $\sigma$ und auf $M\setminus N$ die Identität ist.

Mittels dieser Abbildung ist $\mathrm{Perm}(N)$ eine Untergruppe von $\mathrm{Perm}(M)$.

Beweis

Offenbar ist die Abbildung wohldefiniert. Sie ist injektiv, da aus  $\tilde{\sigma }=\tilde{\tau }$  sofort folgt, dass  $\sigma =\tau$  ist. Die Abbildung liefert eine Bijektion zwischen $\mathrm{Perm}(N)$ und der Menge der Permutationen auf $M$, die $M\setminus N$ fest lassen. Diese Permutationen bilden eine Untergruppe.

$◻$