Inversion einer Permutation < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:19 Sa 17.11.2012 | | Autor: | Lu- |
| Aufgabe | Zeige: Jede Permutation [mm] \pi \in S_n (\forall [/mm] n [mm] \n \IN) [/mm] gilt stets:
inv [mm] \pi [/mm] = [mm] inv(\pi^{-1}) [/mm] |
Die Inversion einer Permutation [mm] \pi \in S_n [/mm] ist ein paar (i,j) mit i<j und [mm] \pi(i) [/mm] > [mm] \pi [/mm] (j)
Das ganze habe ich mir schon bei Bsp klar gemacht, dass die Formel gilt.
Jetzt gehts um den Beweis, ich hab mich erst an einer Richtung versucht:
Ansatz 1:
Sei (i,j) eine Inversion von [mm] \pi^{-1} [/mm] mit i < j d.h. [mm] \pi^{-1} [/mm] (i) [mm] >\pi^{-1} [/mm] (j)
Eine Permutation ist eine Bijektion also besitzt jede Bild in der Zielmenge ein eindeutig bestimmtes Urbild.
D.h. [mm] \exists [/mm] a und b sodass: [mm] \pi^{-1} [/mm] (i) =a und [mm] \pi^{-1} [/mm] (j) =b
also a > b gilt.
Ansatz 2:
Sei [mm] (\pi(i), \pi(j)) [/mm] eine Inversion von [mm] \pi^{-1} [/mm] mit [mm] \pi(i)>\pi(j)d.h. \pi^{-1} [/mm] ( [mm] \pi(i)) >\pi^{-1} (\pi(j)) [/mm] <=> i >j
Also ist (j,i) eine Inversion von [mm] \pi [/mm] da gilt [mm] \pi(j)> \pi(i)
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:20 Sa 17.11.2012 | | Autor: | hippias |
Die Behauptung ist falsch: z.B. ist [mm] $(123)^{-1}= [/mm] (321)$ und [mm] $(2,3)\in [/mm] inv((123)$. Jedoch ist [mm] $(2,3)\not \in [/mm] inv((321))$. Richtig ist vielmehr, dass die beiden Mengen gleichviele Elemente enthalten.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 16:27 Sa 17.11.2012 | | Autor: | Lu- |
Hallo
Ich hab anscheinend vergessen dazuzusagen, dass wir mit [mm] inv(\pi) [/mm] die anzahl der Inversionen meinen.
Aber ich denke mein Ansatz 2 ) hat zum erfolg geführt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Mo 19.11.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:14 Sa 17.11.2012 | | Autor: | Helbig |
> Zeige: Jede Permutation [mm]\pi \in S_n (\forall[/mm] n [mm]\n \IN)[/mm] gilt
> stets:
> inv [mm]\pi[/mm] = [mm]inv(\pi^{-1})[/mm]
>
> Die Inversion einer Permutation [mm]\pi \in S_n[/mm] ist ein paar
> (i,j) mit i<j und [mm]\pi(i)[/mm] > [mm]\pi[/mm] (j)
> Das ganze habe ich mir schon bei Bsp klar gemacht, dass
> die Formel gilt.
> Jetzt gehts um den Beweis, ich hab mich erst an einer
> Richtung versucht:
>
> Ansatz 1:
> Sei (i,j) eine Inversion von [mm]\pi^{-1}[/mm] mit i < j d.h.
> [mm]\pi^{-1}[/mm] (i) [mm]>\pi^{-1}[/mm] (j)
> Eine Permutation ist eine Bijektion also besitzt jede Bild
> in der Zielmenge ein eindeutig bestimmtes Urbild.
> D.h. [mm]\exists[/mm] a und b sodass: [mm]\pi^{-1}[/mm] (i) =a und [mm]\pi^{-1}[/mm]
> (j) =b
> also a > b gilt.
Da kann ich keinen Beweis erkennen.
>
> Ansatz 2:
> Sei [mm](\pi(i), \pi(j))[/mm] eine Inversion von [mm]\pi^{-1}[/mm] mit
> [mm]\pi(i)>\pi(j)d.h. \pi^{-1}[/mm] ( [mm]\pi(i)) >\pi^{-1} (\pi(j))[/mm] <=>
> i >j
> Also ist (j,i) eine Inversion von [mm]\pi[/mm] da gilt [mm]\pi(j)> \pi(i)[/mm]
Nein. Dies entspricht nicht der von Dir gegebenen Definition von Inversion - Tippfehler? Es muß heißen: Wenn [mm] $(\pi(i), \pi(j))$ [/mm] eine Inversion von [mm] $\pi^{-1}$ [/mm] ist, ist [mm] $\pi(i) [/mm] < [mm] \pi(j)$ [/mm] und [mm] $j=\pi^{-1}(\pi(j))<\pi^{-1}(\pi(i)) [/mm] = i$. Also ist $(j,i)$ eine Inversion von [mm] $\pi\,.$
[/mm]
Mit dem Ansatz kannst Du jetzt eine Bijektion angeben zwischen [mm] $\{(i, j)\colon (i, j) \text { ist eine Inversion von } \pi\}$ [/mm] und [mm] $\{(i, j)\colon (i, j) \text { ist eine Inversion von } \pi^{-1}\}\,.$
[/mm]
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:25 Sa 17.11.2012 | | Autor: | Lu- |
Danke für den Post, ich habe es hinbekommen ;)
LG
|
|
|
|
