Anzahl der Inversionen < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
Hallo,
Momentan denke ich erneut in die falsche Richtung!
Folgende Aufgabe:
Man bezeichne die Anzahl der Inversionen, die alle Permutationen von n verschiedenen Elementen zusammengenommen ausweisen, mit [mm] J_{n} [/mm] so dass [mm] J_{1}=0, J_{2}=1, J_{3}=9 [/mm] ist. Man zeige, dass sich diese Anzahlen [mm] J_{n} [/mm] rekursiv durch die Formel [mm] J_{n+1}=(n+1)J_{n}+\bruch{1}{2}n[(n+1)!] [/mm] bestimmen lassen.
Meine Gedanken lauten folgendermaßen:
Ich versuche es mittels vollständiger Induktion zu zeigen.
Ich teile eine Permutation von n+1-Elementen in n+1 Spalten ein: Eine Spalte an der immer 1 an der ersten Stelle ist, eine wo immer 2 an der ersten Stelle steht usw.
[mm] (n+1)J_{n} [/mm] beschreibt dann die Anzahl der Inversionen aller Spalten ohne die erste Stelle. Nun fehlen logischerweise noch Inversionen welche ich dazu addieren muss. Leider komme ich nicht auf den zweiten Teil der Formel!
Für Unterstützung bin ich jetzt schon dankbar!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:35 So 13.02.2011 | | Autor: | wauwau |
Du bildest eine Permutation von n-Elementen [mm] (a_1,a_2,...a_n), [/mm] durch Hinzufügen von (n+1) an den Anfang, an das Ende oder zwischen die vorhandenen Elemente.
Beispiel [mm] (a_1,a_2,...a_{i-1},n+1,a_{i},...a_n)
[/mm]
d.h jeder Permutation von n-Elementen wird n+1 mal in dieser Weise zu einer Permutation von n+1 Elementen.
Die Inversion der obigen Permutation ist dabei die Inversion der ursprünglichen + (n-i)
Insgesamt also werden die ursp. Permutationen ver n+1 facht und die Inversionen zusätzlich nach obigen Prinzip 1+2+3+4+..+n = [mm] \frac{n(n+1)}{2} [/mm] vermehrt.
Wenn du Betrachtet dass
[mm] \frac{1}{2}n[(n+1)!] [/mm] = [mm] \frac{n(n+1)}{2}n! [/mm]
ist, sollte der REst kein Problem mehr sein
|
|
|
| |
|
Hallo
Erstmal vielen Dank für die Antwort!
Verzeihung für die erneute Frage, aber ich durchschaue momentan nicht was mit "nach dem obigen Prinzip" gemeint ist. Wie kommt man auf die [mm] \bruch{n(n+1)}{2} [/mm] ?
Für eine erneute Antwort bin ich dankbar!
|
|
|
| |
|
Hi,
> Wie kommt man auf die [mm]\bruch{n(n+1)}{2}[/mm] ?
bleiben wir bei $ [mm] (a_1,a_2,...a_{i-1},n+1,a_{i},...a_n) [/mm] $.
Also angenommen, das (n+1)-te Element wird an i-ter Stelle eingefügt (d.h. davor sind i-1 und danach n-i+1 Elemente). Dann entstehen für diesen Fall (n-i+1) neue Inversionen, denn so viel Plätze muss das Element (n+1) nach hinten getauscht werden, bis es wieder an seinem Stammplatz ist.
Das i kann jetzt alle Werte zwischen 1 und $n+1$ annehmen (das sind die Einfügepositionen). Daher wird die Summe zu [mm] \sum_{i=1}^{n+1}(n-i+1)=n(n+1)-\frac{(n+2)(n+1)}{2}+(n+1)=\frac{n(n+1)}{2} [/mm] berechnet.
>
> Für eine erneute Antwort bin ich dankbar!
Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Mo 14.02.2011 | | Autor: | Platoniker |
Hallo
Genial! Danke sehr vielmals! Ich habe einen riesen Denkfehler begangen: Ich hatte nicht bemerkt, dass ein n+1 tes Element in n Spalten verschiedner Arten eingefügt werden. Stattdessen dachte ich an n+1 Spalten (meiner Definition) mit n+1 Elementen und versuchte vergeblich einen Zusammenhang zu finden!
Ich hoffe, dass Beweise führen trainierbar ist!
Schöne Grüße
|
|
|
|
