Det.-formen - Permutation < Determinanten < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Betrachten Sie die allgemeine Permutation:
[mm] \sigma [/mm] = [mm] \pmat{1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \sigma (1) & \sigma (2)& \sigma (3) & \sigma (4) & \sigma (5) & \sigma (6) & \sigma (7) & \sigma (8) & \sigma (9)} [/mm] .
Zeigen Sie, dass die minimale Anzahl von benachbarten Vertauschungen, die nötig sind um [mm] \sigma [/mm] in die identische Permutation umzuwandeln, immer der Fehlstandszahl [mm] \Phi (\sigma) [/mm] entspricht. |
Hallo.
Obige Tatsache soll ich also beweisen. Leider weiß ich nicht so recht, wie ich da ran gehen soll. Prinzipiell weiß ich, was zu beweisen ist aber ich weiß nicht, wie man das aufschreiben kann.
[mm] \Phi (\sigma) [/mm] = |{ ((i,j) [mm] \in \IN^2: [/mm] i < j und [mm] \sigma(i) [/mm] > [mm] \sigma(j) [/mm] }|
So haben wir die Fehlstandszahl definiert und sicher kann man damit arbeiten, leider habe ich keinen Plan wie.
Für ein klein wenig Hilfe wäre ich sehr dankbar.
Grüße
Kalia
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:17 Fr 01.07.2011 | | Autor: | felixf |
Moin!
> Betrachten Sie die allgemeine Permutation:
> [mm]\sigma[/mm] = [mm]\pmat{1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \sigma (1) & \sigma (2)& \sigma (3) & \sigma (4) & \sigma (5) & \sigma (6) & \sigma (7) & \sigma (8) & \sigma (9)}[/mm]
> .
>
> Zeigen Sie, dass die minimale Anzahl von benachbarten
> Vertauschungen, die nötig sind um [mm]\sigma[/mm] in die identische
> Permutation umzuwandeln, immer der Fehlstandszahl [mm]\Phi (\sigma)[/mm]
> entspricht.
> Hallo.
>
> Obige Tatsache soll ich also beweisen.
Wenn du von einer Tatsache sprichst, brauchst du sie nicht mehr zu beweisen 
Nenn es lieber Aussage.
> Leider weiß ich
> nicht so recht, wie ich da ran gehen soll. Prinzipiell
> weiß ich, was zu beweisen ist aber ich weiß nicht, wie
> man das aufschreiben kann.
>
> [mm]\Phi (\sigma)[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
= |{ ((i,j) [mm]\in \IN^2:[/mm] i < j und [mm]\sigma(i)[/mm] >
> [mm]\sigma(j)[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
}|
>
> So haben wir die Fehlstandszahl definiert und sicher kann
> man damit arbeiten, leider habe ich keinen Plan wie.
Ich wuerd folgende drei Aussagen zeigen:
a) die einzige Permutation mit genau 0 Fehlstaenden ist die Identitaet
b) vertauscht man zwei benachbarte Eintraege, so kann sich die Anzahl der Fehlstaende hoechstens um 1 verringern
c) hat man mind. einen Fehlstand, so gibt es immer eine benachbarte Vertauschung, die die Anzahl der Fehlstaende um mindestens 1 verringert
LG Felix
|
|
|
| |
|
> Wenn du von einer Tatsache sprichst, brauchst du sie nicht
> mehr zu beweisen
>
> Nenn es lieber Aussage.
Ja das stimmt.^^ Sry, das hab ich etwas oberflächlich betrachtet bzw. ausgedrückt.
> a) die einzige Permutation mit genau 0 Fehlstaenden ist die
> Identitaet
>
> b) vertauscht man zwei benachbarte Eintraege, so kann sich
> die Anzahl der Fehlstaende hoechstens um 1 verringern
>
> c) hat man mind. einen Fehlstand, so gibt es immer eine
> benachbarte Vertauschung, die die Anzahl der Fehlstaende um
> mindestens 1 verringert
>
> LG Felix
>
...und wie genau kann man das dann aufschreiben? Also könntest du mir mal den Ansatz von deinem Lösungsvorschlag a) aufschreiben?
Mit dankenden Grüßen
Kalia
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:35 So 03.07.2011 | | Autor: | felixf |
Moin Kalia!
> > a) die einzige Permutation mit genau 0 Fehlstaenden ist die
> > Identitaet
> >
> > b) vertauscht man zwei benachbarte Eintraege, so kann sich
> > die Anzahl der Fehlstaende hoechstens um 1 verringern
> >
> > c) hat man mind. einen Fehlstand, so gibt es immer eine
> > benachbarte Vertauschung, die die Anzahl der Fehlstaende um
> > mindestens 1 verringert
> >
> > LG Felix
> >
>
> ...und wie genau kann man das dann aufschreiben? Also
> könntest du mir mal den Ansatz von deinem
> Lösungsvorschlag a) aufschreiben?
Wenn [mm] $\sigma$ [/mm] die Identitaet ist, dann ist [mm] $\Phi(\sigma) [/mm] = 0$. Das solltest du leicht verifizieren koennen.
Wenn [mm] $\Phi(\sigma) [/mm] = 0$ ist, dann kannst du [mm] $\sigma(i) [/mm] = i$ zeigen fuer alle $i$. Betrachte erst $i = 1$. Was ist, wenn [mm] $\sigma(1) \neq [/mm] 1$ ist? Dann betrachte $i = 2$, $i = 3$, ... (sozusagen Induktion ueber $i$ mit $i [mm] \in \{ 1, \dots, n \}$).
[/mm]
LG Felix
|
|
|
|
