Anzahl der Permutationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:10 Sa 01.12.2012 | | Autor: | Lu- |
| Aufgabe | Sei I(n,k) die Anzhal der Permutationen [mm] \pi \in S_n [/mm] mit k Inversionen.
Zeige dass für n [mm] \ge [/mm] k
I(n+1, k) = I(n,k)+ I(n+1, k-1)
gilt. |
Sei [mm] (\pi_1 [/mm] ,.., [mm] \pi_n [/mm] , [mm] \pi_{n+1}) [/mm] eine n+1 elementige Permutation mit k inversionen:
) Ist [mm] \pi_{n+1} [/mm] =n+1 (Fixpunkt)
Dann hab ich eine n elemntige Permutation mit k Inversen
-) Ist [mm] \pi_{i} [/mm] =n ( i [mm] \le [/mm] n )
Konstruiere [mm] \pi [/mm] ' mit [mm] \forall [/mm] k [mm] \in \{1,..,n+1} [/mm] ohne [mm] \{i,i+1\} [/mm] ist [mm] \pi [/mm] ' (k)= [mm] \pi(k) [/mm] und [mm] \pi [/mm] ' (i) = [mm] \pi [/mm] ' (i+1)
-> inv [mm] (\pi [/mm] ' )= k-1
Frage1: Was ist wenn n+1 an erster Stelle steht ?
Es ist klar, dass es dann mindestens n Inversionen geben muss.
Frage2:
Warum kann es nie bei Deiner Konstruktion vorkommen, dass aus zwei verschiedenen Ausgangspermutationen mit k Inversionen dieselbe Permutation mit (k-1) Inversionen konstruiert wird?
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 00:03 So 02.12.2012 | | Autor: | Lu- |
Hallo,
keine einer idee??
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:20 Di 04.12.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Mo 03.12.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
