Diskrete Mathematik < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:14 Sa 03.06.2006 | | Autor: | Sunny85 |
| Aufgabe | Man zeige auf kombinatorische Art, d.h. ohne die Formel für D(n) zu verwenden, dass
D(n+1) = n*(D(n)+D(n+1) |
Ein Derangement ist eine Permutation von [n] mit [mm] g(i)\not=i [/mm] für alle i [mm] \in [/mm] [n], d.h. g hat keine Fixpunkt, somit hat g keinen Zykel der Länge 1.
Die Anzahl der Derangements von [n] sei D(n)
D(n) = n! [mm] \summe_{j=1}^{n} (-1)^j \bruch{1}{j!}
[/mm]
ich weiß leider nich, wie ich das auf kombinatorische Weise zeigen soll
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:39 Sa 03.06.2006 | | Autor: | felixf |
Hallo!
> Man zeige auf kombinatorische Art, d.h. ohne die Formel für
> D(n) zu verwenden, dass
> D(n+1) = n*(D(n)+D(n+1)
Diese Formel ist kaputt! Das $D(n+1)$ hinten soll sicher $D(n-1)$ sein. Und da fehlt eine Klammer zu.
> Ein Derangement ist eine Permutation von [n] mit
> [mm]g(i)\not=i[/mm] für alle i [mm]\in[/mm] [n], d.h. g hat keine Fixpunkt,
> somit hat g keinen Zykel der Länge 1.
> Die Anzahl der Derangements von [n] sei D(n)
> D(n) = n! [mm]\summe_{j=1}^{n} (-1)^j \bruch{1}{j!}[/mm]
>
> ich weiß leider nich, wie ich das auf kombinatorische Weise
> zeigen soll
Mach es so: Wenn du ein Derangement der Laenge $n+1$ hast, schaust du dir an was mit $n+1$ passiert. Wenn $n+1$ in einem $2$-Zyklus enthalten ist, dann entfernst du diesen Zyklus und erhaelst ein Derangement der Laenge $n-1$. Fuer das zweite Element aus dem Zyklus gibt es $n$ Moeglichkeiten, womit du $n [mm] \cdot [/mm] D(n-1)$ Darangements dieser Form hast.
Wenn nun $n+1$ in einem Zyklus der Laenge $> 2$ ist, kannst du $n+1$ einfach aus dem Zyklus entfernen (warum?). So, den Rest solltest du jetzt aber auch selber hinbekommen, das ist schon fast am Ziel 
LG Felix
|
|
|
|
