Permutationen mit k Inversen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei I(n,k) die Anzahl der Permutationen [mm] \pi \in S_{n} [/mm] mit k Inversionen.
1.) Zeige, dass für n >= k
I(n+1,k) = I(n,k) + I(n+1,k-1) gilt. |
Ich habe das folgendermaßen gelöst:
Also auf der linken Seite habe ich eine n+1 elementige Permutation [mm] p=p_{1}p_{2}...p_{n+1} [/mm] mit k Inversen stehen [mm] (k\le [/mm] n). Jetzt habe ich folgende zwei Fälle unterschieden;
1.) Falls [mm] p_{n+1} [/mm] = n+1 ist kann man n+1 weglassen und man bekommt eine n-elementige Permutation mit k Inversen.
2.) Falls [mm] p_{i} [/mm] = n+1 (i <= n) kann ich n+1 mit der darauffolgenden Zahl unmittelbar vertauschen. Das Resultat ist also eine n+1-elementige Permutation mit k-1 Inversen, bie der sich n+1 nicht in der 1. Position befindet.
Durch das Setzen von n+1 in die 1. Position habe ich mindestens [mm] n\ge [/mm] k>k-1 Inverse
Stimmt das so oder muss man noch irgendwas verändern?
|
|
| |
|
Kann mir denn niemand helfen??
Lg,
Tsetsefliege
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Fr 10.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
