Permutationen < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:47 Mo 06.07.2015 | | Autor: | rsprsp |
| Aufgabe | Gegeben sei die Permutation:
σ = [mm] \pmat{ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 7 & 3 & 5 & 1 & 2 & 4 & 9 & 6 & 8 }
[/mm]
a) Bestimmen Sie die Anzahl der Fehlstände von σ. Welchen Wert hat sign(σ)?
b) Wandeln Sie σ 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 γ erzeugt mit:
γ = [mm] \pmat{ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 7 & 3 & 1 & 5 & 2 & 4 & 9 & 6 & 8 }
[/mm]
c) Betrachten Sie nun die allgemeine Permutation:
σ = [mm] \pmat{ 1 & 2 & 3 & ... & n \\ σ(1) & σ(2) & σ(3) & ... & σ(n) }
[/mm]
Zeigen Sie, dass die minimale Anzahl von benachbarten Vertauschungen, die nötig sind um σ in die
identische Permutation umzuwandeln, immer genau der Anzahl der Fehlstände von σ entspricht. |
a)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
(2;4) weil 3>1
(2;5) weil 3>2
(3;4) weil 5>1
(3;5) weil 5>2
(3;6) weil 5>3
(7;8) weil 9>6
(7;9) weil 9>8
13 Fehlstände also ist sign(σ) = -1
Kann mir jemand bei Aufgabe b und c helfen ?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 05:20 Mi 08.07.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
