Permutationen - Fehlstände, Signum sign

Question

  Gegeben sei die Permutation:
$$ \sigma=\left(\begin{array}{ccccccccc} {1} & {2} & {3} & {4} & {5} & {6} & {7} & {8} & {9} \\ {7} & {3} & {5} & {1} & {2} & {4} & {9} & {6} & {8} \end{array}\right) $$
a) Bestimmen Sie die Anzahl der Fehlstände von \( \sigma . \) Welchen Wert hat \( \operatorname{sign}(\sigma) ? \)
b) Wandeln Sie \( \sigma \) durch eine Folge von Transpositionen von benachbarten Elementen in die identische Permutation um. Benutzen Sie dabei so wenig Vertauschungen wie möglich. Beispielsweise wird also durch Vertauschen der beiden benachbarten Elemente 5 und 1 die Permutation \( \gamma \) erzeugt mit:
$$ \gamma=\left(\begin{array}{ccccccccc} {1} & {2} & {3} & {4} & {5} & {6} & {7} & {8} & {9} \\ {7} & {3} & {1} & {5} & {2} & {4} & {9} & {6} & {8} \end{array}\right) $$
c) Betrachten Sie nun die allgemeine Permutation:
$$ \sigma=\left(\begin{array}{cccccccc} {1} & {2} & {3} & {4} & {5} & {6} & {\ldots} & {n} \\ {\sigma(1)} & {\sigma(2)} & {\sigma(3)} & {\sigma(4)} & {\sigma(5)} & {\sigma(6)} & {\ldots} & {\sigma(n)} \end{array}\right) $$
Zeigen Sie, dass die minimale Anzahl von benachbarten Vertauschungen, die nötig sind um \( \sigma \) in die identische Permutation umzuwandeln, immer genau der Anzahl der Fehlstände von \( \sigma \) entspricht.

Könnten Sie mir bei der Aufgabe helfen ?

Comments

Ich habe aktuell die selbe Aufgabe

kann mir jemand AUfgabe b und c erklären?? Ich weiß nicht was ich da machen soll??

Danke für die Hilfe

Answer 1

Fehlstände sind

(1;2) weil 7>3
(1;3) weil 7>5
(1;4) weil 7>1
(1;5) weil 7>2
(1;6) weil 7>4
(1;8) weil 7>6

Das waren alle Fehlständen, die durch die 7 am Anfang erreicht werden.

Dann kommt die nächste Zahl in der 2. Reihe, das ist die 3. Sie erzeugt

die Fehlstände

(2;4) weil 3>1
2;5) weil 3>2     
Das waren alle mit der 3. 

Dann die 5, gibt die Fehlstände

(3;4)   (3;5)    (3;6) 

Jetzt die nächste Zahl, das ist die 1,

damit gibt es keinen Fehlstand,.

etc.

Comments

Ich komme dann auf 13 Fehlstände. -> sign = -1

Hast du einen Ansatz für c) ?

---

c)  Wenn man zwei Nachbarn tauscht, kann man doch höchstens einen Fehlstand wegbekommen.

Da die identische Perm. keinen Fehlstand hat, muss man also mindestens so oft benachbarte

Elemente tauschen, bis alle Fehlstände weg sind.