TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 122

WS08 Beispiel 124

Schreiben Sie die Zyklendarstellung der Permutation $\pi$ aus Aufgabe 121) so an, dass in jedem Zyklus das kleinste Element an erster Stelle steht, wir nennen es den Zyklenführer, und die Zyklen untereinander nach absteigender Größe ihrer Zyklenführer angeordnet sind. Zeigen Sie, dass man die Klammern in der Zyklendarstellung weglassen kann und die Permutation $\pi$ dennoch rekonstruierbar bleibt (klammernlose Zyklendarstellung).

Klammerlose Zyklenschreibweise

Die Angaben von Bsp 123 besagt:

$\pi ={\begin{pmatrix}1&2&3&4&5&6&7&8&9\\3&5&8&7&6&9&4&1&2\end{pmatrix}}$

In Zyklenschreibweise sieht das so aus:

$\pi =\left(1,3,8\right)\left(2,5,6,9\right)\left(4,7\right)$

Graphisch siehts so aus:

Dabei ist jeweils das kleinste Element schon an der ersten Stelle. Absteigend nach größe des ersten Elements ergibt:

$\pi =\left(4,7\right)\left(2,5,6,9\right)\left(1,3,8\right)$

Weglassen der Klammern:

$\pi =4,7,2,5,6,9,1,3,8$

Rekonstruieren der Permutation

Um aus der Zahlenfolge

$\pi =4,7,2,5,6,9,1,3,8$

die ursprüngliche Permutation wieder zu rekonstruieren, muss man die Zyklenführer finden. Die erste Zahl muss per Definition ein Zyklenführer sein. Innerhalb eines Zyklus gibt es nur größere Zahlen als den Zyklenführer (ebenfalls per Definition). Steht also rechts von einem Zyklenführer, eine kleinere Zahl, so muss diese Zahl ein anderer Zyklenführer sein.

• In unserem Beispiel ist der erste Zyklenführer die Zahl 4.
• Die nächste kleinere Zahl als 4 rechts davon ist die 2, also ist auch die 2 ein Zyklenführer.
• Die nächste kleinere Zahl als 2 rechts davon ist die 1, also ist auch die 1 ein Zyklenführer
• Rechts von der 1 gibt es keine kleineren Zahlen mehr, also haben wir alle gefunden.
• Die Zyklenführer sind 4, 2 und 1.

Durch diese Wissen können wir die Klammern wieder einfügen und erhalten wieder

$\pi =\left(4,7\right)\left(2,5,6,9\right)\left(1,3,8\right)$

mfg, --W wallner