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 ! |
|