Aufgabe #35 (IMO) < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 09:41 Sa 14.05.2005 | | Autor: | Hanno |
Hallo!
So, es muss auch im Wettbewerbsforum weiter gehen:
Es sei [mm] $p_{n}(k)$ [/mm] die Anzahl der Permutationen auf der Menge [mm] $\{1,2,...,n\}$, [/mm] die genau $k$ Fixpunkte besitzen.
Man zeige: [mm] $\summe_{k=0}^{n}k\cdot p_n(k)=n!$
[/mm]
Liebe Grüße,
Hanno
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:30 Mi 18.05.2005 | | Autor: | Hanno |
Hallo an alle!
Man bezeichne mit [mm] $D_n$ [/mm] die Derangement-Zahlen, d.h. die Anzahl der fixpunktfreien Permutationen einer n-Menge. Dann gilt [mm] $p_{n}(k)=\vektor{n\\ k} D_{n-k}$, [/mm] denn eine Permutation mit genau $k$ Fixpunkten erhalte ich, indem ich die Fixpunkte, also $k$ der $n$ Elemente auswähle, und die übrigen $n-k$ Elemente fixpunktfrei permutiere, wofür es nach Definition [mm] $D_{n-k}$ [/mm] Möglichkeiten gibt.
Nun muss versucht werden, dass $k$ im Binomialkoeffizienten zu "verarbeiten" und über einen kleinen Umweg zurück zu einer Summe über den [mm] $p_n(k)$ [/mm] zu gelangen, in der jedoch der Faktor $k$ nicht mehr auftaucht.
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:35 Mi 18.05.2005 | | Autor: | Hanno |
Hallo an alle!
Es sei [mm] $D_n$ [/mm] die Anzahl der fixpunktfreien Permutationen einer n-Menge. Dann ist [mm] $p_n(k)=\vektor{n\\ k}\cdot D_{n-k}$, [/mm] also [mm] $\summe_{k=0}^{n} k\cdot p_n(k)=\summe_{k=1}^{n} k\cdot\frac{n!}{k! (n-k)!} D_{n-k}=\summe_{k=1}^{n} n\cdot\frac{(n-1)!}{((n-1)-(k-1))!\cdot (k-1)!}\cdot D_{(n-1)-(k-1)}=n\cdot \summe_{k=0}^{n-1} \vektor{n-1\\ k} D_{(n-1)-k}=n\cdot [/mm] (n-1)!=n!$.
Liebe Grüße,
Hanno
|
|
|
|
