Permutationsgruppe/Anzahlberechnung/Einführung/2/Textabschnitt
Zu einer Menge nennt man die Menge
der bijektiven Selbstabbildungen die Automorphismengruppe oder die Permutationsgruppe zu .
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 nennt man auch eine Permutation.
Für eine endliche Menge schreibt man
Eine endliche Permutation kann man beispielsweise mit einer (vollständigen) Wertetabelle oder mit einem Pfeildiagramm beschreiben.
Es sei eine endliche Menge und eine Permutation auf . Man nennt einen Zykel der Ordnung , wenn es eine -elementige Teilmenge derart gibt, dass auf die Identität ist und die Elemente aus zyklisch vertauscht. Wenn ist, so schreibt man einfach
Ein Element mit nennt man Fixpunkt der Permutation. Der Wirkungsbereich einer Permutation ist die Menge der Punkte aus , die keine Fixpunkte sind. Bei einem Zykel ist der Wirkungsbereich. Jede Permutation ist ein Produkt von Zykeln, was wir hier ohne Beweis erwähnen. Eine solche Produktdarstellung heißt Zykeldarstellung.
Zu einer natürlichen Zahl nennt man die Zahl
die Fakultät von (sprich Fakultät).
Es sei eine endliche Menge mit Elementen.
Dann besitzt die Permutationsgruppe genau Elemente.
Es sei . Für die gibt es mögliche Bilder, für gibt es noch mögliche Bilder, für gibt es noch mögliche Bilder, usw. Daher gibt es insgesamt
mögliche Permutationen.