Transposition und S_n < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:32 Mo 29.06.2009 | | Autor: | Pille456 |
| Aufgabe | Eine Transposition ist ein Zyklus der Länge 2, d. h. eine Permutation, die
zwei Elemente vertauscht und alle übrigen fest lässt.
Sei n [mm] \in [/mm] N. Beweisen Sie, dass sich jede Permutation in [mm] S_n [/mm] als Verkettung
von Transpositionen der Form (i, i + 1) schreiben lässt. Wie viele derartige
Transpositionen braucht man höchstens? |
Hi!
Mal wieder habe ich Probleme diese Frage richtig zu deuten.
Ich habe mir das folgendermaßen gedacht:
Ausgehend von der Identitätspermutation id = (1,2,3,...,n-1,n) in Zyklenschreibweise muss ich ja nur beweisen, dass ich durch die Vertauschung von zwei benachbarten Zahlen jede Zahl an jede beliebige Stelle bekomme. Da ich mit der Hintereinandeausführung einer Transposition die vorherige wieder Rückgängig machen kann ist das aber irgendwie logisch.
Genauer handelt es sich hierbei um eine Unterform des BubbleSort Algorithmus. Damit hätte ich auch schon die Anzahl der höchsten Vertauschungen gefunden, nämlich [mm] \bruch{n(n-1)}{2}. [/mm] Das ist nämlich der Fall, wenn ich aus (1,2,3,...,n-1,n) die Permutation (n,n-1,...,3,2,1) machen will.
Ist die Aufgabe so richtig interpretiert oder habe ich das einfach komplett falsch verstanden?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:19 Mi 01.07.2009 | | Autor: | felixf |
Moin!
> Eine Transposition ist ein Zyklus der Länge 2, d. h. eine
> Permutation, die
> zwei Elemente vertauscht und alle übrigen fest lässt.
> Sei n [mm]\in[/mm] N. Beweisen Sie, dass sich jede Permutation in
> [mm]S_n[/mm] als Verkettung
> von Transpositionen der Form (i, i + 1) schreiben lässt.
> Wie viele derartige
> Transpositionen braucht man höchstens?
>
> Hi!
> Mal wieder habe ich Probleme diese Frage richtig zu
> deuten.
> Ich habe mir das folgendermaßen gedacht:
> Ausgehend von der Identitätspermutation id =
> (1,2,3,...,n-1,n) in Zyklenschreibweise muss ich ja nur
> beweisen, dass ich durch die Vertauschung von zwei
> benachbarten Zahlen jede Zahl an jede beliebige Stelle
> bekomme.
Genau.
> Da ich mit der Hintereinandeausführung einer
> Transposition die vorherige wieder Rückgängig machen kann
> ist das aber irgendwie logisch.
Hmm, naja dass daraus die Behauptung folgt ist nicht umbedingt logisch, allerdings das hier:
> Genauer handelt es sich hierbei um eine Unterform des
> BubbleSort Algorithmus.
Diese Interpretation habe ich noch nie gesehen, und halte das fuer eine sehr interessante Bemerkung :)
> Damit hätte ich auch schon die
> Anzahl der höchsten Vertauschungen gefunden, nämlich
> [mm]\bruch{n(n-1)}{2}.[/mm] Das ist nämlich der Fall, wenn ich aus
> (1,2,3,...,n-1,n) die Permutation (n,n-1,...,3,2,1) machen
> will.
Genau.
> Ist die Aufgabe so richtig interpretiert oder habe ich das
> einfach komplett falsch verstanden?
Du hast sie schon richtig interpretiert. Du musst nur noch formal richtig aufschreiben, warum das so geht.
LG Felix
|
|
|
|
