www.wikidata.de-de.nina.az

Zykeltyp Der kurz Typ ist in der Kombinatorik und der Gruppentheorie eine wichtige Eigenschaft von Permutationen Der bes

Zykeltyp

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. Formal heißt hier, dass das Produkt und die Potenzen nicht tatsächlich ausgerechnet werden. Teilweise wird der Ausdruck auch mit eckigen Klammern versehen. 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. Gelegentlich werden die Zyklenlängen auch in aufsteigender Reihenfolge notiert. 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

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:

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

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 , die durch die Folge

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

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. 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. Die -stelligen Permutationen gleichen Zykeltyps bilden daher die Konjugationsklassen der symmetrischen Gruppe .

Siehe auch Bearbeiten

Literatur Bearbeiten

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. ↑ Aigner: Diskrete Mathematik. S. 11.
  2. Reiss, Stroth: Endliche Strukturen. S. 171.
  3. Artin: Algebra. S. 241.
  4. ↑ Kurzweil, Stellmacher: Theorie der endlichen Gruppen: eine Einführung. S. 80.
  5. Jacobs, Jungnickel: Einführung in die Kombinatorik. S. 293.
  6. ↑ Aigner: Diskrete Mathematik. S. 12.
  7. Artin: Algebra. S. 242.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Zykeltyp kurz Typ ist in der Kombinatorik und der Gruppentheorie eine wichtige Eigenschaft von Permutationen Der Zykeltyp beschreibt die Anzahl und Langen der Zyklen in der Zykeldarstellung einer Permutation Die Anzahl der moglichen Typen n displaystyle n stelliger Permutationen entspricht gerade der Anzahl der Partitionen der Zahl n displaystyle n Die Anzahl der Permutationen pro Zykeltyp kann aus der Typbeschreibung errechnet werden wobei die Permutationen mit gleicher Zyklenzahl durch die Stirling Zahlen erster Art gezahlt werden Die inverse Permutation weist immer den Typ der Ausgangspermutation auf Auch das Ergebnis der Komposition zweier Permutationen besitzt unabhangig 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 n displaystyle n Inhaltsverzeichnis 1 Definition 2 Beispiele 2 1 Konkrete Beispiele 2 2 Allgemeinere Beispiele 3 Anzahlen 3 1 Zahl der Typen 3 2 Zahl der Permutationen pro Typ 4 Zykelklassen 5 Siehe auch 6 Literatur 7 Weblinks 8 EinzelnachweiseDefinition BearbeitenJede Permutation der symmetrischen Gruppe S n displaystyle S n nbsp lasst sich eindeutig bis auf Vertauschung der Faktoren als Komposition von hochstens n displaystyle n nbsp paarweise disjunkten Zyklen darstellen Bezeichnet nun b j displaystyle b j nbsp fur j 1 n displaystyle j 1 ldots n nbsp die Anzahl der Zyklen der Lange j displaystyle j nbsp einer Permutation p S n displaystyle pi in S n nbsp dann ist der Zykeltyp dieser Permutation der formale Ausdruck typ p 1 b 1 2 b 2 n b n displaystyle operatorname typ pi 1 b 1 2 b 2 ldots n b n nbsp wobei die Terme mit b j 0 displaystyle b j 0 nbsp nicht aufgefuhrt werden mussen 1 Formal heisst hier dass das Produkt und die Potenzen nicht tatsachlich ausgerechnet werden Teilweise wird der Ausdruck auch mit eckigen Klammern versehen 2 Eine alternative Darstellung des Typs einer Permutation ist das s displaystyle s nbsp Tupel typ p k 1 k 2 k s displaystyle operatorname typ pi left k 1 k 2 ldots k s right nbsp wobei s n displaystyle s leq n nbsp und k 1 k s N displaystyle k 1 geq ldots geq k s in mathbb N nbsp die Langen der Zyklen in der Zykeldarstellung der Permutation in absteigender Reihenfolge sind 3 4 Gelegentlich werden die Zyklenlangen auch in aufsteigender Reihenfolge notiert 5 Beide Darstellungen beinhalten die gleichen Informationen uber eine Permutation und konnen einfach ineinander umgewandelt werden Beispiele BearbeitenKonkrete Beispiele Bearbeiten nbsp Graph einer Permutation vom Typ 1 1 2 1 4 1 displaystyle 1 1 2 1 4 1 nbsp oder 4 2 1 displaystyle 4 2 1 nbsp Die Permutation p 1 2 3 4 5 6 7 2 4 1 3 5 7 6 1243 5 67 S 7 displaystyle pi begin pmatrix 1 amp 2 amp 3 amp 4 amp 5 amp 6 amp 7 2 amp 4 amp 1 amp 3 amp 5 amp 7 amp 6 end pmatrix 1243 5 67 in S 7 nbsp weist den Zykeltyp typ p 1 1 2 1 3 0 4 1 5 0 6 0 7 0 1 1 2 1 4 1 displaystyle operatorname typ pi 1 1 2 1 3 0 4 1 5 0 6 0 7 0 1 1 2 1 4 1 nbsp oder typ p 4 2 1 displaystyle operatorname typ pi left 4 2 1 right nbsp auf denn ihre Zykeldarstellung besteht aus je einem Zyklus der Lange eins zwei und vier Den gleichen Zykeltyp besitzt etwa auch die Permutation p 1457 36 2 S 7 displaystyle pi 1457 36 2 in S 7 nbsp Allgemeinere Beispiele Bearbeiten Die folgenden Arten n displaystyle n nbsp stelliger Permutationen p S n displaystyle pi in S n nbsp mit n 2 displaystyle n geq 2 nbsp besitzen jeweils den zugehorigen Zykeltyp identische Permutation typ p 1 n displaystyle operatorname typ pi 1 n nbsp oder typ p 1 1 displaystyle operatorname typ pi 1 ldots 1 nbsp dd Transpositionen Vertauschungen typ p 1 n 2 2 1 displaystyle operatorname typ pi 1 n 2 2 1 nbsp oder typ p 2 1 1 displaystyle operatorname typ pi 2 1 ldots 1 nbsp dd zyklische Permutationen der Lange r 2 displaystyle r geq 2 nbsp typ p 1 n r r 1 displaystyle operatorname typ pi 1 n r r 1 nbsp oder typ p r 1 1 displaystyle operatorname typ pi r 1 ldots 1 nbsp dd fixpunktfreie Permutationen typ p 2 b 2 n b n displaystyle operatorname typ pi 2 b 2 ldots n b n nbsp oder typ p k 1 k s displaystyle operatorname typ pi left k 1 ldots k s right nbsp mit k j 2 displaystyle k j geq 2 nbsp fur alle j displaystyle j nbsp dd selbstinverse Permutationen typ p 1 b 1 2 b 2 displaystyle operatorname typ pi 1 b 1 2 b 2 nbsp oder typ p k 1 k s displaystyle operatorname typ pi left k 1 ldots k s right nbsp mit k j 2 displaystyle k j leq 2 nbsp fur alle j displaystyle j nbsp dd Anzahlen Bearbeitenn displaystyle n nbsp Zykeltyp Zykelstruktur Anzahl1 11 1 12 12 1 1 121 2 13 13 1 1 1 111 21 2 1 331 3 24 14 1 1 1 1 112 21 2 1 1 622 2 2 311 31 3 1 841 4 65 15 1 1 1 1 1 113 21 2 1 1 1 1011 22 2 2 1 1512 31 3 1 1 2021 31 3 2 2011 41 4 1 3051 5 24Zahl der Typen Bearbeiten Fur die Anzahl und Langen der Zyklen einer n displaystyle n nbsp stelligen Permutation gilt stets 1 1 b 1 2 b 2 n b n n displaystyle 1 cdot b 1 2 cdot b 2 ldots n cdot b n n nbsp demnach mussen fur n 2 displaystyle n geq 2 nbsp manche der Zahlen b j displaystyle b j nbsp gleich null sein Fur die Summe aller Zykellangen gilt entsprechend k 1 k 2 k s n displaystyle k 1 k 2 ldots k s n nbsp Daher entspricht die Anzahl der Zykeltypen in S n displaystyle S n nbsp gerade der Anzahl der Partitionen der Zahl n displaystyle n nbsp 4 die durch die Folge 1 2 3 5 7 11 displaystyle 1 2 3 5 7 11 ldots nbsp Folge A000041 in OEIS gegeben ist In der nebenstehenden Tabelle ist die Anzahl der Zykeltypen in S n displaystyle S n nbsp die Zahl der Zeilen zu dem gegebenen n displaystyle n nbsp Zahl der Permutationen pro Typ Bearbeiten Die Anzahl der Permutationen p S n displaystyle pi in S n nbsp mit typ p 1 b 1 2 b 2 n b n displaystyle operatorname typ pi 1 b 1 2 b 2 ldots n b n nbsp betragt 6 n b 1 b 2 b n 1 b 1 2 b 2 n b n displaystyle frac n b 1 cdot b 2 cdot ldots cdot b n cdot 1 b 1 cdot 2 b 2 cdot ldots cdot n b n nbsp Folge A036039 in OEIS denn die Zyklen der Lange j displaystyle j nbsp konnen auf b j displaystyle b j nbsp verschiedene Weisen angeordnet werden wobei jeder dieser Zyklen auf j displaystyle j nbsp verschiedene Weisen geschrieben werden kann In der nebenstehenden Tabelle finden sich diese Anzahlen in der letzten Spalte Unter Zuhilfenahme der Tupeldarstellung lasst sich die Anzahl der moglichen Permutationen eines gegebenen Zykeltyps auch durch n b 1 b n k 1 k s displaystyle frac n b 1 cdot ldots cdot b n cdot k 1 cdot ldots cdot k s nbsp angeben Verwandt dazu sind die Stirling Zahlen erster Art s n k displaystyle s n k nbsp die die Anzahl der n displaystyle n nbsp stelligen Permutationen angeben die genau k displaystyle k nbsp Zyklen aufweisen Die Stirling Zahlen entstehen aus der Summe der Anzahlen der Permutationen mit gleicher Zyklenzahl 6 Beispielsweise ist die Stirling Zahl s 5 2 30 20 50 displaystyle s 5 2 30 20 50 nbsp siehe die zweit und drittletzte Zeile in der Tabelle Zykelklassen BearbeitenDie Permutationen gleichen Zykeltyps bilden Aquivalenzklassen und man schreibt p s displaystyle pi sim sigma nbsp wenn zwei Permutationen p s S n displaystyle pi sigma in S n nbsp den gleichen Typ besitzen das heisst p s typ p typ s displaystyle pi sim sigma Leftrightarrow operatorname typ pi operatorname typ sigma nbsp Fur die inverse Permutation p 1 displaystyle pi 1 nbsp einer Permutation p displaystyle pi nbsp gilt immer p 1 p displaystyle pi 1 sim pi nbsp denn durch die Invertierung drehen sich nur die Reihenfolgen der Zahlen innerhalb der einzelnen Zyklen um Zwar ist die Hintereinanderausfuhrung zweier Permutationen p s displaystyle pi sigma nbsp im Allgemeinen nicht kommutativ aber es gilt stets p s s p displaystyle pi circ sigma sim sigma circ pi nbsp das Resultat einer Komposition weist also unabhangig von der Reihenfolge der Operanden den gleichen Zykeltyp auf Auch durch Konjugation mit einer beliebigen Permutation s displaystyle sigma nbsp andert sich der Typ einer Permutation p displaystyle pi nbsp nicht das heisst es gilt s p s 1 p displaystyle sigma circ pi circ sigma 1 sim pi nbsp Allgemein sind zwei Permutationen sogar genau dann konjugiert wenn sie vom gleichen Typ sind 4 7 Die n displaystyle n nbsp stelligen Permutationen gleichen Zykeltyps bilden daher die Konjugationsklassen der symmetrischen Gruppe S n displaystyle S n nbsp Siehe auch BearbeitenYoung Tableau ZyklenzeigerLiteratur BearbeitenMartin Aigner Diskrete Mathematik Vieweg 2006 ISBN 3 8348 9039 1 Michael Artin Algebra Springer 1998 ISBN 3 7643 5938 2 Konrad Jacobs Dieter Jungnickel Einfuhrung in die Kombinatorik de Gruyter 2003 ISBN 3 11 016727 1 Hans Kurzweil Bernd Stellmacher Theorie der endlichen Gruppen eine Einfuhrung Springer 1998 ISBN 3 540 60331 X Kristina Reiss Gernot Stroth Endliche Strukturen Springer 2011 ISBN 3 642 17181 8 Weblinks BearbeitenRoger Lipsett Conjugacy classes in the symmetric group Sn In PlanetMath englisch Einzelnachweise Bearbeiten a b Aigner Diskrete Mathematik S 11 Reiss Stroth Endliche Strukturen S 171 Artin Algebra S 241 a b c Kurzweil Stellmacher Theorie der endlichen Gruppen eine Einfuhrung S 80 Jacobs Jungnickel Einfuhrung in die Kombinatorik S 293 a b Aigner Diskrete Mathematik S 12 Artin Algebra S 242 Abgerufen von https de wikipedia org w index php title Zykeltyp amp oldid 172072012