Rekursion für Recontre-Zahl < Wahrscheinlichkeitstheorie < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Bezeichne [mm] (D_{k})_{k\in \IN_{0}} [/mm] die Folge der Recontre-Zahlen. Dann gilt [mm] D_{0}=1, D_{1}=0 [/mm] sowie für [mm] n\in \IN [/mm] weiterhin: [mm] D_{n+1} [/mm] = [mm] n(D_{n}+D_{n-1}). [/mm] Beweisen Sie dies durch kombinatorische Überlegungen! |
Hallo liebe Mathefreunde!^^
Ich komme leider mit dieser Aufgabe nicht so zurecht.. Ich kann mir einfach auf keine richtige Weise das kombinatorisch erklären.
Mir ist bekannt, dass [mm] D_{n}=card E_{n} [/mm] gilt, also dies die Anzahl der Permutationen aus [mm] S_{n} [/mm] ohne Fixpunkte beschreibt. Doch ich finde leider keine richtige Schlussfolgerung daraus für n+1 ... Ich würde mich freuen wenn mir jemand beim Verständnis der Aufgabe helfen könnte ! :)
Vielen Dank !
LG Blacki
|
|
| |
|
Hallo Blackwolf1990,
> Bezeichne [mm](D_{k})_{k\in \IN_{0}}[/mm] die Folge der
> Recontre-Zahlen. Dann gilt [mm]D_{0}=1, D_{1}=0[/mm] sowie für [mm]n\in \IN[/mm] weiterhin: [mm]D_{n+1}[/mm] = [mm]n(D_{n}+D_{n-1}).[/mm]
[mm] D_n [/mm] beinhaltet die Permutationen, deren Zyklendarstellung keine Einzelelemente enthält.
Zeige die Aussage mittels Induktion.
[mm] n\to(n+1): [/mm] Es kommt das Element (n+1) dazu.
a) (n+1) ist in Zyklus der Länge 2 enthalten. Zeige, dass es [mm] nD_{n-1} [/mm] solche Permutationen/ Derangements gibt.
b) (n+1) ist in Zyklus der Länge [mm] \ge3 [/mm] enthalten. Zeige, dass es davon [mm] nD_n [/mm] viele gibt.
> Mir ist bekannt, dass [mm]D_{n}=card E_{n}[/mm] gilt, also dies die
> Anzahl der Permutationen aus [mm]S_{n}[/mm] ohne Fixpunkte
> beschreibt.
LG
|
|
|
| |
|
Achsoooo, na dann ist alles soweit klar ! :) Vielen Dank für deine Hilfe, kamaleonti, das hat mir weitergeholfen !
Liebe Grüße
Blacki
|
|
|
|
