TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 328
Bestimmen Sie zur folgenden Permutation die Zyklendarstellung, das Vorzeichen, sowie die inverse Permutation :
{{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 }}
Zyklendarstellung[Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
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[Bearbeiten | Quelltext bearbeiten]
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