Durchnummerierung Permutatione < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:30 Sa 24.11.2012 | | Autor: | Lu- |
| Aufgabe | Für verschiedene Zwecke benötigt nab eine Durchnummerierung aller Permutationen von[n], sodaß man [mm] \pi_k [/mm] sofort angeben kann, ohne vorher die anderen Permutationen zu konstruieren.
Eine Möglichkeiet der Durchnummerierung besteht im Anzählen der Insersionen: Sei $ [mm] \pi [/mm] $ eine Permutation von [n]. 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) [/mm] = (1,0,3,1,3,4) gegeben.
ZEIGE: Es gilt 0 [mm] \le a_i \le [/mm] i , i=1,2,..,n-1
Jede Folge, kurz Inversionsfolge genannt defeniert eine eindeutig bestimmte Permutation . Man kann also jeder Zahl k mit 0 [mm] \le [/mm] k [mm] \le [/mm] n! -1 eine eindeutig bestimmte [mm] Permuttaion\pi [/mm] zuordnen: Schreibe einfach k in der Gestalt
k= [mm] a_1 [/mm] *1! + [mm] a_1 [/mm] * 2! +..+ [mm] a_{n-1} [/mm] * (n-1)!
und interpretiere [mm] (a_1,.., a_{n-1}) [/mm] als Inversionsfolge.
Finde eine möglichst einfache Methode, um aus der Inversionsfolge die Permutationen [mm] \pi [/mm] zu konstruieren. |
Hei
Also
Sei a= [mm] (a_1,.., a_{n-1} [/mm] )Inversionsfolge einer Permutation [mm] \pi\in S_n [/mm] , [mm] \pi= (\pi_1 [/mm] ,.., [mm] \pi_{n-1} [/mm] , [mm] \pi_n [/mm] ) defeniert durch:
[mm] a_i [/mm] =| [mm] \{ (k,l) | k < l und \pi_k > \pi_l = n -i \}
[/mm]
für i=1,..,n-1
Ich glaub ich verstehe das ganze nicht wirklich.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Mo 26.11.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
