imported>Lómelinde: End-Tag fehlt nicht geschlossenes fett ausgelöst durch kursiv im Parameter |title= der Vorlage:PlanetMath

2017-12-18T09:21:13Z

End-Tag fehlt nicht geschlossenes fett ausgelöst durch kursiv im Parameter |title= der Vorlage:PlanetMath

Neue Seite

Der '''Zykeltyp''', kurz '''Typ''', ist in der [[Kombinatorik]] und der [[Gruppentheorie]] eine wichtige Eigenschaft von [[Permutation]]en. Der Zykeltyp beschreibt die Anzahl und Längen der [[Zyklische Permutation|Zyklen]] in der [[Zykelschreibweise|Zykeldarstellung]] einer Permutation. Die Anzahl der möglichen Typen <math>n</math>-stelliger Permutationen entspricht gerade der Anzahl der [[Zahlpartition|Partitionen]] der Zahl <math>n</math>. Die Anzahl der Permutationen pro Zykeltyp kann aus der Typbeschreibung errechnet werden, wobei die Permutationen mit gleicher Zyklenzahl durch die [[Stirling-Zahl]]en erster Art gezählt werden.

Die [[inverse Permutation]] weist immer den Typ der Ausgangspermutation auf. Auch das Ergebnis der [[Komposition (Mathematik)|Komposition]] zweier Permutationen besitzt unabhängig von der Reihenfolge der Operanden immer den gleichen Zykeltyp. Weiter sind zwei Permutationen genau dann zueinander [[Konjugation (Gruppentheorie)|konjugiert]], wenn sie vom gleichen Typ sind. Die Permutationen gleichen Zykeltyps bilden demnach die [[Konjugationsklasse]]n der [[Symmetrische Gruppe|symmetrischen Gruppe]] vom Grad <math>n</math>.

== Definition ==

Jede [[Permutation]] der [[Symmetrische Gruppe|symmetrischen Gruppe]] <math>S_n</math> lässt sich eindeutig (bis auf Vertauschung der Faktoren) als [[Komposition (Mathematik)|Komposition]] von höchstens <math>n</math> paarweise [[disjunkt]]en [[Zyklische Permutation|Zyklen]] darstellen. Bezeichnet nun <math>b_j</math> für <math>j=1, \ldots , n</math> die Anzahl der Zyklen der Länge <math>j</math> einer Permutation <math>\pi \in S_n</math>, dann ist der Zykeltyp dieser Permutation der formale Ausdruck

: <math>\operatorname{typ}(\pi) = 1^{b_1} 2^{b_2} \ldots n^{b_n}</math>,

wobei die Terme mit <math>b_j=0</math> nicht aufgeführt werden müssen.<ref name="aigner11">{{Literatur |Autor=Aigner |Titel=Diskrete Mathematik |Datum= |Seiten=11}}</ref> Formal heißt hier, dass das Produkt und die Potenzen nicht tatsächlich ausgerechnet werden. Teilweise wird der Ausdruck auch mit [[Eckige Klammer|eckigen Klammern]] versehen.<ref>{{Literatur |Autor=Reiss, Stroth |Titel=Endliche Strukturen |Datum= |Seiten=171}}</ref> Eine alternative Darstellung des Typs einer Permutation ist das <math>s</math>-Tupel

:<math>\operatorname{typ}(\pi) = \left( k_1, k_2, \ldots , k_s \right)</math>,

wobei <math>s \leq n</math> und <math>k_1 \geq \ldots \geq k_s \in \N</math> die Längen der Zyklen in der [[Zykelschreibweise|Zykeldarstellung]] der Permutation in absteigender Reihenfolge sind.<ref>{{Literatur |Autor=Artin |Titel=Algebra |Datum= |Seiten=241}}</ref><ref name="kurzweil">{{Literatur |Autor=Kurzweil, Stellmacher |Titel=Theorie der endlichen Gruppen: eine Einführung |Datum= |Seiten=80}}</ref> Gelegentlich werden die Zyklenlängen auch in aufsteigender Reihenfolge notiert.<ref>{{Literatur |Autor=Jacobs, Jungnickel |Titel=Einführung in die Kombinatorik |Datum= |Seiten=293}}</ref> Beide Darstellungen beinhalten die gleichen Informationen über eine Permutation und können einfach ineinander umgewandelt werden.

== Beispiele ==

=== Konkrete Beispiele ===
[[Datei:050712 perm 0.png|mini|Graph einer Permutation vom Typ <math> 1^1 2^1 4^1</math> oder <math>(4,2,1)</math>.]]

Die Permutation

:<math>\pi = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 4 & 1 & 3 & 5 & 7 & 6 \end{pmatrix} = (1243)(5)(67) \in S_7</math>

weist den Zykeltyp

:<math>\operatorname{typ}(\pi) = 1^1 2^1 3^0 4^1 5^0 6^0 7^0 = 1^1 2^1 4^1</math>   oder   <math>\operatorname{typ}(\pi) = \left( 4,2,1 \right)</math>

auf, denn ihre Zykeldarstellung besteht aus je einem Zyklus der Länge eins, zwei und vier. Den gleichen Zykeltyp besitzt etwa auch die Permutation <math>\pi = (1457)(36)(2) \in S_7</math>.

=== Allgemeinere Beispiele ===

Die folgenden Arten <math>n</math>-stelliger Permutationen <math>\pi \in S_n</math> mit <math>n \geq 2</math> besitzen jeweils den zugehörigen Zykeltyp:

* [[identische Permutation]]:
::<math>\operatorname{typ}(\pi) = 1^n</math>   oder   <math>\operatorname{typ}(\pi) = (1, \ldots , 1)</math>
* [[Vertauschung|Transpositionen]] (Vertauschungen):
::<math>\operatorname{typ}(\pi) = 1^{n-2} 2^1</math>   oder   <math>\operatorname{typ}(\pi) = (2, 1, \ldots , 1)</math>
* [[zyklische Permutation]]en der Länge <math>r \geq 2</math>:
::<math>\operatorname{typ}(\pi) = 1^{n-r} r^1</math>   oder   <math>\operatorname{typ}(\pi) = (r, 1, \ldots , 1)</math>
* [[fixpunktfreie Permutation]]en:
::<math>\operatorname{typ}(\pi) = 2^{b_2} \ldots n^{b_n}</math>   oder   <math>\operatorname{typ}(\pi) = \left( k_1, \ldots , k_s \right)</math> mit <math>k_j \geq 2</math> für alle <math>j</math>
* [[selbstinverse Permutation]]en:
::<math>\operatorname{typ}(\pi) = 1^{b_1} 2^{b_2}</math>   oder   <math>\operatorname{typ}(\pi) = \left( k_1, \ldots , k_s \right)</math> mit <math>k_j \leq 2</math> für alle <math>j</math>

== Anzahlen ==

{| class="wikitable float-right"
|- class="hintergrundfarbe8"
! style="width:1.2em"| <math>n</math>
! colspan="2"| Zykeltyp
! Zykelstruktur
! Anzahl
|-
|rowspan="1" class="hintergrundfarbe8" style="text-align:center"| 1
| 11 || (1) || ( • ) ||style="text-align:right"| 1
|-
|rowspan="2" class="hintergrundfarbe8" style="text-align:center"| 2
| 12 || (1,1) || ( • ) ( • ) ||style="text-align:right"| 1
|-
| 21 || (2) || ( • • ) ||style="text-align:right"| 1
|-
|rowspan="3" class="hintergrundfarbe8" style="text-align:center"| 3
| 13 || (1,1,1) || ( • ) ( • ) ( • ) ||style="text-align:right"| 1
|-
| 11 21 || (2,1) || ( • • ) ( • ) ||style="text-align:right"| 3
|-
| 31 || (3) || ( • • • ) ||style="text-align:right"| 2
|-
|rowspan="5" class="hintergrundfarbe8" style="text-align:center"| 4
| 14 || (1,1,1,1) || ( • ) ( • ) ( • ) ( • ) ||style="text-align:right"| 1
|-
| 12 21 || (2,1,1) || ( • • ) ( • ) ( • ) ||style="text-align:right"| 6
|-
| 22 || (2,2) || ( • • ) ( • • ) ||style="text-align:right"| 3
|-
| 11 31 || (3,1) || ( • • • ) ( • ) ||style="text-align:right"| 8
|-
| 41 || (4) || ( • • • • ) ||style="text-align:right"| 6
|-
|rowspan="7" class="hintergrundfarbe8" style="text-align:center"| 5
| 15 || (1,1,1,1,1) || ( • ) ( • ) ( • ) ( • ) ( • ) ||style="text-align:right"| 1
|-
| 13 21 || (2,1,1,1) || ( • • ) ( • ) ( • ) ( • ) ||style="text-align:right"| 10
|-
| 11 22 || (2,2,1) || ( • • ) ( • • ) ( • ) ||style="text-align:right"| 15
|-
| 12 31 || (3,1,1) || ( • • • ) ( • ) ( • ) ||style="text-align:right"| 20
|-
| 21 31 || (3,2) || ( • • • ) ( • • ) ||style="text-align:right"| 20
|-
| 11 41 || (4,1) || ( • • • • ) ( • ) ||style="text-align:right"| 30
|-
| 51 || (5) || ( • • • • • ) ||style="text-align:right"| 24
|}

=== Zahl der Typen ===

Für die Anzahl und Längen der Zyklen einer <math>n</math>-stelligen Permutation gilt stets<ref name="aigner11" />

: <math>1 \cdot b_1 + 2 \cdot b_2 + \ldots + n \cdot b_n = n</math>,

demnach müssen für <math>n \geq 2</math> manche der Zahlen <math>b_j</math> gleich null sein. Für die Summe aller Zykellängen gilt entsprechend

: <math>k_1 + k_2 + \ldots + k_s = n</math>.

Daher entspricht die Anzahl der Zykeltypen in <math>S_n</math> gerade der Anzahl der [[Zahlpartition|Partitionen]] der Zahl <math>n</math>,<ref name="kurzweil" /> die durch die Folge

: <math>1, 2, 3, 5, 7, 11, \ldots</math>   ({{OEIS|A000041}})

gegeben ist. In der nebenstehenden Tabelle ist die Anzahl der Zykeltypen in <math>S_n</math> die Zahl der Zeilen zu dem gegebenen <math>n</math>.

=== Zahl der Permutationen pro Typ ===

Die Anzahl der Permutationen <math>\pi \in S_n</math> mit <math>\operatorname{typ}(\pi) = 1^{b_1} 2^{b_2} \ldots n^{b_n}</math> beträgt<ref name="aigner12">{{Literatur |Autor=Aigner |Titel=Diskrete Mathematik |Datum= |Seiten=12}}</ref>

: <math>\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}}</math>   ({{OEIS|A036039}}),

denn die Zyklen der Länge <math>j</math> können auf <math>b_j!</math> verschiedene Weisen angeordnet werden, wobei jeder dieser Zyklen auf <math>j</math> 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

: <math>\frac{n!}{b_1! \cdot \ldots \cdot b_n! \cdot k_1 \cdot \ldots \cdot k_s}</math>,

angeben. Verwandt dazu sind die [[Stirling-Zahl]]en erster Art <math>s_{n,k}</math>, die die Anzahl der <math>n</math>-stelligen Permutationen angeben, die genau <math>k</math> Zyklen aufweisen. Die Stirling-Zahlen entstehen aus der Summe der Anzahlen der Permutationen mit gleicher Zyklenzahl.<ref name="aigner12" /> Beispielsweise ist die Stirling-Zahl <math>s_{5,2} = 30 + 20 = 50</math>, siehe die zweit- und drittletzte Zeile in der Tabelle.

== Zykelklassen ==

Die Permutationen gleichen Zykeltyps bilden [[Äquivalenzklasse]]n und man schreibt <math>\pi \sim \sigma</math>, wenn zwei Permutationen <math>\pi, \sigma \in S_n</math> den gleichen Typ besitzen, das heißt

: <math>\pi \sim \sigma \Leftrightarrow \operatorname{typ}(\pi) = \operatorname{typ}(\sigma)</math>.

Für die [[inverse Permutation]] <math>\pi^{-1}</math> einer Permutation <math>\pi</math> gilt immer

: <math>\pi^{-1} \sim \pi</math>,

denn durch die Invertierung drehen sich nur die Reihenfolgen der Zahlen innerhalb der einzelnen Zyklen um. Zwar ist die [[Komposition (Mathematik)|Hintereinanderausführung]] zweier Permutationen <math>\pi, \sigma</math> im Allgemeinen nicht [[kommutativ]], aber es gilt stets

: <math>\pi \circ \sigma \sim \sigma \circ \pi</math>,

das Resultat einer Komposition weist also unabhängig von der Reihenfolge der Operanden den gleichen Zykeltyp auf. Auch durch [[Konjugation (Gruppentheorie)|Konjugation]] mit einer beliebigen Permutation <math>\sigma</math> ändert sich der Typ einer Permutation <math>\pi</math> nicht, das heißt, es gilt

: <math>\sigma \circ \pi \circ \sigma^{-1} \sim \pi</math>.

Allgemein sind zwei Permutationen sogar genau dann konjugiert, wenn sie vom gleichen Typ sind.<ref name="kurzweil" /><ref>{{Literatur |Autor=Artin |Titel=Algebra |Datum= |Seiten=242}}</ref> Die <math>n</math>-stelligen Permutationen gleichen Zykeltyps bilden daher die [[Konjugationsklasse]]n der symmetrischen Gruppe <math>S_n</math>.

== Siehe auch ==
* [[Young-Tableau]]
* [[Zyklenzeiger]]

== Literatur ==
* {{Literatur
|Autor=[[Martin Aigner]]
|Titel=Diskrete Mathematik
|Verlag=Vieweg
|Datum=2006
|ISBN=3-8348-9039-1}}
* {{Literatur
|Autor=[[Michael Artin]]
|Titel=Algebra
|Verlag=Springer
|Datum=1998
|ISBN=3-7643-5938-2}}
* {{Literatur
|Autor=[[Konrad Jacobs]], [[Dieter Jungnickel]]
|Titel=Einführung in die Kombinatorik
|Verlag=de Gruyter
|Datum=2003
|ISBN=3-11-016727-1}}
* {{Literatur
|Autor=Hans Kurzweil, [[Bernd Stellmacher]]
|Titel=Theorie der endlichen Gruppen: eine Einführung
|Verlag=Springer
|Datum=1998
|ISBN=3-540-60331-X}}
* {{Literatur
|Autor=[[Kristina Reiss]], [[Gernot Stroth]]
|Titel=Endliche Strukturen
|Verlag=Springer
|Datum=2011
|ISBN=3-642-17181-8}}

== Weblinks ==
* {{PlanetMath|id=conjugacyclassesinthesymmetricgroupsn|title=Conjugacy classes in the symmetric group Sn|author=Roger Lipsett}}

== Einzelnachweise ==
<references />

[[Kategorie:Permutationstheorie]]

Zykeltyp - Versionsgeschichte

imported>Lómelinde: End-Tag fehlt nicht geschlossenes fett ausgelöst durch kursiv im Parameter |title= der Vorlage:PlanetMath