| Autor |
Beitrag |
    
Mr. X (frage)
Neues Mitglied
Benutzername: frage
Nummer des Beitrags: 2
Registriert: 10-2002
| | Veröffentlicht am Freitag, den 25. Oktober, 2002 - 16:59: | 
|
Was ich auch versuche ich bekomm keine Lösung =(
Sei X eine Menge mit n Elementen, K die Menge {1,2...k} und r1, r2, rk natürliche Zahlen mit Summe n. Zeige durch Induktion nach k, dass die Anzahl aller Abblildungen von X nach K, die r1-mal den Wert 1, r2-mal den Wert 2,..., rk mal den Wert k annehmen, gegeben ist durch:
n!/(r1!r2!r3!...rk!) |
Orion (orion)
Erfahrenes Mitglied
Benutzername: orion
Nummer des Beitrags: 337
Registriert: 11-2001
| | Veröffentlicht am Samstag, den 26. Oktober, 2002 - 16:31: |
|
Mr.X:
Der Fall k=1 ist klar. Wir nehmen an, dass
die fragliche Aussage für irgendein k >=1
zutreffe. Nun sei K':={1,...,k,k+1} und für
die Besetzungszahlen r1,...,rk+1
gelte
r1+...+rk+1=n <==>
r1 +...+rk = n-rk+1.
Eine Abbildung f : X--> K' mit den gegebenen
Besetzungszahlen lässt sich in 2 Schritten
konstruieren:
1. Wähle eine (n-rk+1) -elementige Teilmenge Y aus X aus.
Das geht auf genau
N1 =
binom(n,n-rk+1) = n!/rk+1!*(n-rk+1)!
Arten.
2. Bilde Y auf K={1,...,k} unter Berücksichtigung der gegebenen Besetzungszahlen r1,...,rk ab. Nach
Induktionsannahme gibt es hierfür genau
N2 = (n-rk-1)!/r1!*...*rk!
Möglichkeiten. Die übriggebliebenen Elemente von X werden auf k+1 abgebildet.
Nach dem Multiplikationssatz der abzählenden Kombinatorik gibt es somit genau
N 1*N2 = n!/r1!*...*rk+1!
Abbildungen f : X-->K' mit den verlangten Eigenschaften.
mfg
Orion
|
Mr. X (frage)
Neues Mitglied
Benutzername: frage
Nummer des Beitrags: 3
Registriert: 10-2002
| | Veröffentlicht am Sonntag, den 27. Oktober, 2002 - 11:53: |
|
danke ! |
|
