Verständnis Inversionen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:15 Sa 24.11.2012 | | Autor: | Lu- |
| Aufgabe | Sei [mm] \pi [/mm] eine Permutation von [n]. Sei [mm] a_i [/mm] die Anzahl der Inversionen (k,l) mit [mm] \pi(l)=n-i [/mm] für i=1,2,..,n-1
Zum Bsp ist für n =7, [mm] \pi [/mm] = 5 3 7 2 1 6 4 die entsprechende Folge durch
[mm] (a_1,a_2,..,a_6)=(1,0,3,1,3,4) [/mm] gegeben. |
Hallo zusammen.
Wie zu hölle komme ich auf den "Vektor" [mm] (a_1,a_2,..,a_6)=(1,0,3,1,3,4).
[/mm]
ich verstehe das nicht!
Ps.:
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)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:44 Sa 24.11.2012 | | Autor: | Helbig |
Hallo Lu_,
> Sei [mm]\pi[/mm] eine Permutation von [n]. Sei [mm]a_i[/mm] die Anzahl der
> Inversionen (k,l) mit [mm]\pi(l)=n-i[/mm] für i=1,2,..,n-1
> Zum Bsp ist für n =7, [mm]\pi[/mm] = 5 3 7 2 1 6 4 die
> entsprechende Folge durch
> [mm](a_1,a_2,..,a_6)=(1,0,3,1,3,4)[/mm] gegeben.
> Hallo zusammen.
> Wie zu hölle komme ich auf den "Vektor"
> [mm](a_1,a_2,..,a_6)=(1,0,3,1,3,4).[/mm]
Zum Beispiel [mm] $a_3$:
[/mm]
[mm] $i=3\,,$
[/mm]
[mm] $\pi(\ell) [/mm] = 7 - i = 7-3 = [mm] 4\,,$
[/mm]
[mm] $\ell [/mm] = [mm] 7\,,$ [/mm] denn [mm] $\pi(7) [/mm] = [mm] 4\,.$
[/mm]
Die Zahl der $k$ mit $k<7$ und [mm] $\pi(k) [/mm] > [mm] \pi(\ell)= [/mm] 4$ ist 3. Also [mm] $a_3 [/mm] = [mm] 3\,.$
[/mm]
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:25 Sa 24.11.2012 | | Autor: | Lu- |
> $ [mm] \ell [/mm] = [mm] 7\,, [/mm] $ denn $ [mm] \pi(7) [/mm] = [mm] 4\,. [/mm] $
[mm] \pi [/mm] ist doch = 5 3 7 2 1 6 4
also [mm] \pi(7) [/mm] = 2
und [mm] \pi( [/mm] 6) = 4
??
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:30 Sa 24.11.2012 | | Autor: | Helbig |
> > [mm]\ell = 7\,,[/mm] denn [mm]\pi(7) = 4\,.[/mm]
> [mm]\pi[/mm] ist doch = 5 3 7 2 1 6 4
> also [mm]\pi(7)[/mm] = 2
> und [mm]\pi([/mm] 6) = 4
> ??
Ja, das ist auch eine mögliche Interpretation dieser Darstellung von [mm] $\pi\,.$ [/mm] Aber ich habe
[mm] $\pi(1) [/mm] = 5, [mm] \pi(2) [/mm] = 3, [mm] \pi(3) [/mm] = [mm] 7,\ldots, \pi(7) [/mm] =4$
herausgelesen, und ich glaube, so versteht es auch der Aufgabensteller.
Grüße,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:47 Sa 24.11.2012 | | Autor: | Lu- |
Achso jetzt ist es klar.
Kann ich die [mm] a_i [/mm] nicht so defenieren:
$ [mm] a_i [/mm] $ =| $ [mm] \{ (k,l) | k < l und \pi_k > \pi_l = n -i \} [/mm] $
Und warum sind 0 $ [mm] \le a_i \le [/mm] $ i , i=1,2,..,n-1 ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:31 Sa 24.11.2012 | | Autor: | Helbig |
> Achso jetzt ist es klar.
> Kann ich die [mm]a_i[/mm] nicht so defenieren:
> [mm]a_i[/mm] =| [mm]\{ (k,l) | k < l und \pi_k > \pi_l = n -i \}[/mm]
Ja.
> Und warum sind 0 [mm]\le a_i \le[/mm] i , i=1,2,..,n-1 ?
Es gibt genau $i$ Zahlen k in [n] mit [mm] $\pi(k) [/mm] > [mm] n-i\,.$
[/mm]
Grüße,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:39 Sa 24.11.2012 | | Autor: | Lu- |
Ah danke.
Und wenn nun alle [mm] a_i [/mm] =0 sind.
Dann ist die Permuttaion doch "geordnet" Wie kann man sich die Permutation dann vorstellen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:44 Sa 24.11.2012 | | Autor: | Helbig |
> Ah danke.
> Und wenn nun alle [mm]a_i[/mm] =0 sind.
> Dann ist die Permuttaion doch "geordnet" Wie kann man sich
> die Permutation dann vorstellen?
Das ist dann die Identität auf [n].
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 22:25 Sa 24.11.2012 | | Autor: | Lu- |
Ok, danke.
Trotzdem habe ich noch eine Frage.
Angenommen solch eine Inversionsfolge ist angegeben, kann man dann eindeutig die Permutation [mm] \pi [/mm] wieder herausfinden?
[mm] (a_1 a_2 a_3 [/mm] .. [mm] a_{n-1}) [/mm] Sei gegeben.
( [mm] \pi_1 \pi_2 [/mm] ,..., [mm] \pi_n) [/mm] ist gesucht.
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 Mo 26.11.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
