Zykeltyp

kombinatorische oder gruppentheoretische Eigenschaft einer Permutation

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 .

Definition

Bearbeiten

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.

Beispiele

Bearbeiten

Konkrete Beispiele

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

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  

Anzahlen

Bearbeiten
  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

Zahl der Typen

Bearbeiten

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

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.

Zykelklassen

Bearbeiten

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  .

Siehe auch

Bearbeiten

Literatur

Bearbeiten
Bearbeiten

Einzelnachweise

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.