Permutationsgruppe/Anzahlberechnung/Einführung/2/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

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.

Permutation8.png


Composicion de permutaciones.svg


050712 perm 0.png



Definition  

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


Beispiel  

Wir betrachten die Permutation

Man kann sie als Produkt der beiden Zykel und schreiben.


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.


Definition  

Zu einer natürlichen Zahl nennt man die Zahl

die Fakultät von (sprich Fakultät).



Lemma  

Sei eine endliche Menge mit Elementen.

Dann besitzt die Permutationsgruppe genau Elemente.

Beweis  

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.