Permutationsgruppe

Eine Permutationsgruppe G ist eine Gruppe, deren Elemente Bijektionen von einer Menge X auf X sind; die Gruppenoperation ist die Verkettung dieser Abbildungen. Jedes Element von G ist eine Bijektion X → X, und G enthält das Identitätsabbild sowie die Inversen aller Elemente. Die Menge X wird als Träger oder Grundmenge der Gruppe bezeichnet. Die vollständige Gruppe aller Bijektionen von X auf X heißt Sym(X).

Beispiele: Für X = {1, ..., n} ist S_n = Sym(X) die symmetrische Gruppe der Ordnung n!, und A_n ist die Untergruppe der even Permutationen. Untergruppen von S_n nennt man Permutationsgruppen auf n Buchstaben. Dihedralgruppen D_n lassen sich als Untergruppen von S_n darstellen.

Darstellung und Struktur: Eine Permutationsgruppe G auf X ist äquivalent zu einer Gruppenhomomorphismus φ: G → Sym(X). Umgekehrt ergibt jede solche Abbildung eine Permutationsgruppe. Nach Cayley wirkt jede Gruppe G als Untergruppe von Sym(G) durch links- oder rechtsregularaction.

Eigenschaften: Man unterscheidet transitive, 2-transitive usw. Gruppen. Wichtige Konzepte sind Orbits und Stabilisatoren; das Orbit-Stabilizer-Theorems. Cycle-Notation dient zur Beschreibung einzelner Permutationen; oft genügt es, S_n durch Transpositionen oder Zyklen wie (1 2 ... n) zu erzeugen. Viele strukturelle Eigenschaften von Gruppen lassen sich durch Permutationsgruppen untersuchen, z. B. die Symmetrie von Graphen oder Polyedern.

Anwendungen: Permutationsgruppen spielen eine zentrale Rolle in der algebraischen Kombinatorik, der Galois- und Graphentheorie sowie in algorithmischen Problemen, etwa der Generierung von Gruppen durch Generatoren.