kombinatorisches Argument < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | a) Geben Sie ein kombinatorisches Argument an für die Identität
[mm] C(n,r) = C(n,n-r) [/mm] für [mm] 0 \le r \le n [/mm]
b) Geben Sie ein kombinatorisches Argument an für die Identität
[mm]C(n,r) * C(r,k) = C(n,k) * C(n-k,r-k)[/mm] für [mm] 0 \le k \le r \le n [/mm]
|
Hallo! Ich habe eine Frage zur Teilaufgabe b)
Teilaufgabe a) scheint mir leicht: Zu jeder Auswahl gibt es eine "Nicht-Auswahl" (die nicht in r enthaltenen Elemente). Diese Nicht-Auswahl enthält n-r Elemente (alle restlichen Elemente von n) also gilt für Auswahl wie "Nicht-Auswahl" die gleiche Anzahl möglicher Kombinationen.
Aber wie die Zusammenhänge in Teilaufgabe b) sind, ist mir nicht allgemein klar. Zunächst habe ich den Zusammenhang anhand eines Beispiels untersucht mit [mm] n=4, r=2 [/mm] und [mm] k=1 [/mm] Dabei sieht man, dass bei der Identität auf beiden Seiten zwei gleiche Produkte aus unterschiedlichen Faktoren gebildet werden. In diesem Beispiel also [mm] 6 * 2 = 4 * 3 [/mm]. Man kann sich das "Funktionieren" der Identität also vorstellen. Aber wie um Himmels Willen ist das kombinatorisch zu deuten??
Für jede konstruktive Hilfestellung, wäre ich sehr dankbar!! Mir wäre überhaupt am liebsten, es gäbe einen "kleinen" Hinweis wie dieser Fall angegangen werden könnte, so dass ich ihn selbst lösen kann. Danke schonmal!
-Ich habe diese Frage in keinem anderen Forum gestellt.-
|
|
| |
|
Hallo Stefan,
16 Stunden habe ich gegrübelt als sich mir plötzlich die ganze Systematik erschloss und ich für den Bruchteil der Sekunde spürte, wie sich mein
Bewußtsein erweiterte. Doch bevor ich hier esoterisch schwelge möchte
ich meine Lösung zum Besten geben, auf dass sie kritischer Überprüfung
unterzogen wird:
Ich habe also auf beiden Seiten der Identität nichts weiter, als die Summe
der aus allen möglichen r-elementigen Teilmengen von n gebildeten verschiedenen 2 Quotientenmengen der Kardinalitäten r-k und k!
Oder, anders ausgedrückt: Auf beiden Seiten der Identität steht die Anzahl aller möglichen r-elementigen Mengenvereinigungen zweier Mengen, von denen eine r-k-elementige Teilmenge von n und die andere k-elementige Teilmenge von n ist.
Wie kommt das?
Linke Seite:
Ich wähle aus einer n-elementigen Menge eine r-elementige Teilmenge (C(n,r)) und daraus wähle ich dann wiederum eine k-elementige Teilmenge (C(r,k)). Den zweiten Schritt wiederhole ich so lange, bis ich alle möglichen k-elementigen Teilmengen der r-elementigen Menge gebildet habe. Damit habe ich die r-elementige Teilmenge aber in alle möglichen Kombinationen aus einer r-k-elementigen Menge und einer k-elementigen Menge zerlegt und es geht weiter mit Schritt 1 (C(n,r)) und der nächsten r-elementigen Teilmenge ...
Rechte Seite:
Ich wähle zunächst eine k-elementige Teilmenge aus einer n-elementigen Menge (C(n,k)). Dann wähle ich für diese k-elementige Teilmenge eine r-k-elementige Teilmenge von n, ohne jedoch die Anzahl der Elemente der bereits gebildeten k-elementigen Teilmenge bei der Auswahl erneut zu berücksichtigen (C(n-k,r-k) - deswegen n-k!). Bis jetzt habe ich also ausgewählt: für eine k-elementige Teilmenge von n eine r-k-elementige verschiedene Teilmenge von n. Die Vereinigung dieser beiden Mengen ergibt also wieder eine r-elementige Teilmenge von n. Den zweiten Schritt wiederhole ich so lange, bis ich alle möglichen r-k-elementigen Teilmengen für die r-elementige Menge gebildet habe. Damit habe ich die k-elementige Teilmenge aus Schritt 1 aber nacheinander um alle möglichen Kombinationen einer r-k-elementigen Teilmenge ergänzt, und es geht weiter mit Schritt 1 (C(n,k)) um diesen Prozess für alle verbleibenden k-elementigen Teilmengen von n zu durchlaufen...
Am Ende habe ich also auf beiden Seiten die Anzahl aller möglichen r-elementigen Vereinigungsmengen aus einer r-k-elementigen und einer k-elementigen Menge. Beide Seiten beschreiben also tatsächlich nur einen anderen Auswahlprozess.
Eigentlich toll.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:24 Di 17.01.2006 | | Autor: | Stefan |
Hallo Vielfrager!
Deine Erklärung ist mir echt zu hoch; ich kann sie nur schwer nachvollziehen. ![[sorry]](/images/smileys/sorry.gif "[sorry]")
Sagen wir es daher mit einfachen Worten:
Beide Seiten beschreiben auf unterschiedliche Art aus einer $n$-elementigen Menge eine $k$-elementige Teilmenge einer $r$-elementigen Teilmenge zu wählen.
Liebe Grüße
Stefan
|
|
|
|
) und einen Stamm von, sagen wir, $r=16$ Spielern, die mit zu den Auswärtsspielen fahren, der also fünf zusätzliche Spieler beinhaltet.
![[wein]](/images/smileys/wein.gif "[wein]"){kind=small}
