Permutationsgruppe/Anzahlberechnung/Einführung/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$.

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.

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$

Lemma

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

Dann gibt es eine natürliche injektive Abbildung

$\operatorname {Perm} \,(N)\longrightarrow \operatorname {Perm} \,(M),\,\sigma \longmapsto {\tilde {\sigma }},$

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

Mittels dieser Abbildung ist ${}\operatorname {Perm} \,(N)$ eine Untergruppe von ${}\operatorname {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 ${}\operatorname {Perm} \,(N)$ und der Menge der Permutationen auf ${}M$, die ${}M\setminus N$ fest lassen. Diese Permutationen bilden eine Untergruppe.

$\Box$