Permutationen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:08 Fr 29.10.2010 | | Autor: | icarus89 |
| Aufgabe | Wie viele Permutationen von n Elementen gibt es, sodass alles komplett durcheinander ist? D. h.: für wieviele verschiedene Permutation [mm] \pi [/mm] gilt:
[mm] \pi(i)\not=i \forall [/mm] i |
Heyho!
Irgendwie erkenn ich da noch nicht, wie das allgemein aussieht...
Ich hab mir das mal für die ersten paar n angeguckt:
1: 0
2: 1
3: 2
4: 9
5: 44 (?)
Meine erste Vermutung war (n-1)! Aber das hat sich durch die Beispiele nicht bewahrheitet...
|
|
| |
|
Hallo icarus89,
da stimmt aber etwas an Deinen Ermittlungen nicht.
edit: offenbar doch. Ich lag falsch. Danke an Sax für den Hinweis samt eines produktiven Ansatzes!
> Irgendwie erkenn ich da noch nicht, wie das allgemein
> aussieht...
> Ich hab mir das mal für die ersten paar n angeguckt:
> 1: 0
> 2: 1
> 3: 2
> 4: 9
> 5: 44 (?)
>
> Meine erste Vermutung war (n-1)! Aber das hat sich durch
> die Beispiele nicht bewahrheitet...
Alles hiernach stimmt also nicht.
Richtig wäre:
[mm] 1\to0
[/mm]
[mm] 2\to1
[/mm]
[mm] 3\to2
[/mm]
[mm] 4\to6
[/mm]
[mm] 5\to24
[/mm]
Deine erste Vermutung war richtig. Du musst nur einen Weg finden, sie auch zu zeigen. Und sie gilt übrigens nicht für n=1.
Nennen wir die Zahl der vollständig vermischten Permutationen [mm] \tau{(n)}.
[/mm]
Dann ist leicht zu zeigen, dass für n>1 gilt: [mm] \tau{(n+1)}=n\tau{(n)}. [/mm] Überleg mal, warum. Wie kommt man von k zu k+1?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Korrektur) fundamentaler Fehler  | | Datum: | 00:07 Sa 30.10.2010 | | Autor: | Sax |
Hi,
das stimmt nicht, die ursprünglich genannten Zahlen (einschließlich der 44) sind richtig.
Es gilt die Rekursion
[mm] \tau(1)=0 [/mm] , [mm] \tau(2)=1 [/mm] und [mm] \tau(n) [/mm] = [mm] (n-1)*(\tau(n-1)+\tau(n-2)) [/mm] für [mm] n\ge2
[/mm]
Gruß Sax.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:09 Sa 30.10.2010 | | Autor: | icarus89 |
> Hallo icarus89,
>
> da stimmt aber etwas an Deinen Ermittlungen nicht.
>
> > Irgendwie erkenn ich da noch nicht, wie das allgemein
> > aussieht...
> > Ich hab mir das mal für die ersten paar n angeguckt:
> > 1: 0
> > 2: 1
> > 3: 2
> > 4: 9
> > 5: 44 (?)
> >
> > Meine erste Vermutung war (n-1)! Aber das hat sich durch
> > die Beispiele nicht bewahrheitet...
>
> Richtig wäre:
> [mm]1\to0[/mm]
> [mm]2\to1[/mm]
> [mm]3\to2[/mm]
> [mm]4\to6[/mm]
> [mm]5\to24[/mm]
>
> Deine erste Vermutung war richtig. Du musst nur einen Weg
> finden, sie auch zu zeigen. Und sie gilt übrigens nicht
> für n=1.
>
> Nennen wir die Zahl der vollständig vermischten
> Permutationen [mm]\tau{(n)}.[/mm]
>
> Dann ist leicht zu zeigen, dass für n>1 gilt:
> [mm]\tau{(n+1)}=n\tau{(n)}.[/mm] Überleg mal, warum. Wie kommt man
> von k zu k+1?
>
> Grüße
> reverend
>
Mmmh? Aber ich komm bei n=4 definitiv auf 9 Permutationen...
Oder bin ich jetzt blöd?
2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321
Das sind doch 9...
Oder versteh ich da irgendwas falsch???
|
|
|
| |
|
Hallo nochmal,
nein, Du liegst völlig richtig und ich bin blöd. Sax hat die richtige Idee, aber Du musst noch herausfinden, warum diese Rekursion gilt.
Wenn Du willst, erkläre ich gern, wie ich auf meine falsche Herleitung kam, aber das ist wahrscheinlich nicht hilfreich, sondern eher verwirrend.
Pardon!
Grüße
reverend
|
|
|
|
