Zykeltyp

Van Wikipedia, de gratis encyclopedie

Der Zykeltyp, kurz Typ, ist in der Kombinatorik und der Gruppentheorie eine wichtige Eigenschaft von Permutationen. Der Zykeltyp beschreibt die Anzahl und Längen der Zyklen in der Zykeldarstellung einer Permutation. Die Anzahl der möglichen Typen -stelliger Permutationen entspricht gerade der Anzahl der Partitionen der Zahl . Die Anzahl der Permutationen pro Zykeltyp kann aus der Typbeschreibung errechnet werden, wobei die Permutationen mit gleicher Zyklenzahl durch die Stirling-Zahlen erster Art gezählt werden.

Die inverse Permutation weist immer den Typ der Ausgangspermutation auf. Auch das Ergebnis der Komposition zweier Permutationen besitzt unabhängig von der Reihenfolge der Operanden immer den gleichen Zykeltyp. Weiter sind zwei Permutationen genau dann zueinander konjugiert, wenn sie vom gleichen Typ sind. Die Permutationen gleichen Zykeltyps bilden demnach die Konjugationsklassen der symmetrischen Gruppe vom Grad .

Jede Permutation der symmetrischen Gruppe lässt sich eindeutig (bis auf Vertauschung der Faktoren) als Komposition von höchstens paarweise disjunkten Zyklen darstellen. Bezeichnet nun für die Anzahl der Zyklen der Länge einer Permutation , dann ist der Zykeltyp dieser Permutation der formale Ausdruck

,

wobei die Terme mit nicht aufgeführt werden müssen.[1] Formal heißt hier, dass das Produkt und die Potenzen nicht tatsächlich ausgerechnet werden. Teilweise wird der Ausdruck auch mit eckigen Klammern versehen.[2] Eine alternative Darstellung des Typs einer Permutation ist das -Tupel

,

wobei und die Längen der Zyklen in der Zykeldarstellung der Permutation in absteigender Reihenfolge sind.[3][4] Gelegentlich werden die Zyklenlängen auch in aufsteigender Reihenfolge notiert.[5] Beide Darstellungen beinhalten die gleichen Informationen über eine Permutation und können einfach ineinander umgewandelt werden.

Konkrete Beispiele

[Bearbeiten | Quelltext bearbeiten]
Graph einer Permutation vom Typ oder .

Die Permutation

weist den Zykeltyp

  oder  

auf, denn ihre Zykeldarstellung besteht aus je einem Zyklus der Länge eins, zwei und vier. Den gleichen Zykeltyp besitzt etwa auch die Permutation .

Allgemeinere Beispiele

[Bearbeiten | Quelltext bearbeiten]

Die folgenden Arten -stelliger Permutationen mit besitzen jeweils den zugehörigen Zykeltyp:

  oder  
  oder  
  oder  
  oder   mit für alle
  oder   mit für alle
Zykeltyp Zykelstruktur Anzahl
1 11 (1) ( • ) 1
2 12 (1,1) ( • ) ( • ) 1
21 (2) ( • • ) 1
3 13 (1,1,1) ( • ) ( • ) ( • ) 1
11 21 (2,1) ( • • ) ( • ) 3
31 (3) ( • • • ) 2
4 14 (1,1,1,1) ( • ) ( • ) ( • ) ( • ) 1
12 21 (2,1,1) ( • • ) ( • ) ( • ) 6
22 (2,2) ( • • ) ( • • ) 3
11 31 (3,1) ( • • • ) ( • ) 8
41 (4) ( • • • • ) 6
5 15 (1,1,1,1,1) ( • ) ( • ) ( • ) ( • ) ( • ) 1
13 21 (2,1,1,1) ( • • ) ( • ) ( • ) ( • ) 10
11 22 (2,2,1) ( • • ) ( • • ) ( • ) 15
12 31 (3,1,1) ( • • • ) ( • ) ( • ) 20
21 31 (3,2) ( • • • ) ( • • ) 20
11 41 (4,1) ( • • • • ) ( • ) 30
51 (5) ( • • • • • ) 24

Für die Anzahl und Längen der Zyklen einer -stelligen Permutation gilt stets[1]

,

demnach müssen für manche der Zahlen gleich null sein. Für die Summe aller Zykellängen gilt entsprechend

.

Daher entspricht die Anzahl der Zykeltypen in gerade der Anzahl der Partitionen der Zahl ,[4] die durch die Folge

  (Folge A000041 in OEIS)

gegeben ist. In der nebenstehenden Tabelle ist die Anzahl der Zykeltypen in die Zahl der Zeilen zu dem gegebenen .

Zahl der Permutationen pro Typ

[Bearbeiten | Quelltext bearbeiten]

Die Anzahl der Permutationen mit beträgt[6]

  (Folge A036039 in OEIS),

denn die Zyklen der Länge können auf verschiedene Weisen angeordnet werden, wobei jeder dieser Zyklen auf verschiedene Weisen geschrieben werden kann. In der nebenstehenden Tabelle finden sich diese Anzahlen in der letzten Spalte. Unter Zuhilfenahme der Tupeldarstellung lässt sich die Anzahl der möglichen Permutationen eines gegebenen Zykeltyps auch durch

,

angeben. Verwandt dazu sind die Stirling-Zahlen erster Art , die die Anzahl der -stelligen Permutationen angeben, die genau Zyklen aufweisen. Die Stirling-Zahlen entstehen aus der Summe der Anzahlen der Permutationen mit gleicher Zyklenzahl.[6] Beispielsweise ist die Stirling-Zahl , siehe die zweit- und drittletzte Zeile in der Tabelle.

Die Permutationen gleichen Zykeltyps bilden Äquivalenzklassen und man schreibt , wenn zwei Permutationen den gleichen Typ besitzen, das heißt

.

Für die inverse Permutation einer Permutation gilt immer

,

denn durch die Invertierung drehen sich nur die Reihenfolgen der Zahlen innerhalb der einzelnen Zyklen um. Zwar ist die Hintereinanderausführung zweier Permutationen im Allgemeinen nicht kommutativ, aber es gilt stets

,

das Resultat einer Komposition weist also unabhängig von der Reihenfolge der Operanden den gleichen Zykeltyp auf. Auch durch Konjugation mit einer beliebigen Permutation ändert sich der Typ einer Permutation nicht, das heißt, es gilt

.

Allgemein sind zwei Permutationen sogar genau dann konjugiert, wenn sie vom gleichen Typ sind.[4][7] Die -stelligen Permutationen gleichen Zykeltyps bilden daher die Konjugationsklassen der symmetrischen Gruppe .

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. a b Aigner: Diskrete Mathematik. S. 11.
  2. Reiss, Stroth: Endliche Strukturen. S. 171.
  3. Artin: Algebra. S. 241.
  4. a b c Kurzweil, Stellmacher: Theorie der endlichen Gruppen: eine Einführung. S. 80.
  5. Jacobs, Jungnickel: Einführung in die Kombinatorik. S. 293.
  6. a b Aigner: Diskrete Mathematik. S. 12.
  7. Artin: Algebra. S. 242.