TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 328

Bestimmen Sie zur folgenden Permutation $\pi$ die Zyklendarstellung, das Vorzeichen, sowie die inverse Permutation $\pi ^{-1}$:

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

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Dieser Artikel überschneidet sich oder ist ident mit TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel_119. Vergleich

Zyklendarstellung

Für eine Erklärung der Zyklendarstellung siehe Wikipedia.

PI = (1,8,3), (2,9,6,5) (4,7)

2.3.2012: mMn nicht richtig! PI = (138)(2569)(47)

Nachtrag 26.11.2016: Hier wurde die Angabe geändert. Bei dieser Angabe stimmt die zweite Lösung. Die erste Lösung stimmt bei der Angabe:

123456789

891725436

Vorzeichen

Jede Permutationen lässt sich als Produkt von Transpositionen darstellen. Dabei gilt: Für einen Zyklus der länge n braucht man n-1 Transpositionen.

Das Vorzeichen einer Permutation gibt an, ob die Anzahl der benötigten Transpositionen gerade oder ungerade ist.

Zusammenhang Fehlstellung <--> Transposition Steht in einer Permutation eine größere Zahl vor einer kleineren Zahl, so bezeichnet man das als Fehlstellung.

Falls die Anzahl der Fehlstellungen einer Permutation gerade ist und eine Transposition ausgeführt wird, ist die Anzahl der Fehlstellungen nacher ungerade, weil entweder eine neue Fehlstellung entstanden oder eine bestehende ausgebessert wurde. Deshalb bedeutet eine gerade Anzahl an Fehlstellungen eine gerade Anzahl an Transpositionen und umgekehrt.

Um das Vorzeichen zu berechnen gibt es also zwei Möglichkeiten:

• ) Zählen der Fehlstellungen in der Permutation:

Jede Zahl die vor einer kleineren steht zählt als Fehlstellung.
In der Permutation ( 3 5 8 7 6 9 4 1 2 ) steht 3 vor den Zahlen 1 und 2, 5 vor den Zahlen 4, 1, 2, usw.
Ergibt insgesamt 22 Fehlstellungen.
Vorzeichen = (-1) ^ 22 = 1

• ) Berechnen der Anzahl an Transpositionen:

Wir haben 3 Zyklen mit den Längen 3, 4 und 2.
Die lassen sich durch jeweils 2, 3, und 1 Transpositonen darstellen.
Anzahl der Transposition insgesamt = 2 + 3 + 1 = 6
Vorzeichen = (-1) ^ 6 = 1

Inverse Permutation

Für die inverse Permutation müssen bei der Zyklendarstellung nur die Richtungen der Zyklen vertauscht werden.

PI^-1 = (1,3,8), (2,5,6,9), (4,7)

2.3.2012 Auch die inverse Permutation stimmt mMn nicht: PI^-1 = (183)(2965)(47)

mfg, --W wallner

• Referenzen:

Beitrag im Informatik Forum

Matheboard.de

Wikipedia Permutation

Wikipedia Transposition

Wikipedia Signum

Links

• Datei:Mathe1-sol.pdf