TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 323

Aus VoWi
Wechseln zu: Navigation, Suche

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}

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

Zyklendarstellung[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]

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]

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[Bearbeiten]