TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 180

Man beweise die Vandermonde'sche Identität mittels kombinatorischer Interpretation.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösung aus "Diskrete Mathematik, Aigner, Kapitel 1 unter Formel (12)"

Seien N und M disjunkte Mengen mit |R|=r und |S|=s. Links steht ${\binom {n+k}{k}}$, also die Anzahl aller k-Untermengen von N+M. Wir klassifizieren nun diese Untermengen K nach ihrem Durchschnitt $\mid K\cap N\mid =i$ i=0..k. Gilt $\mid K\cap N\mid =i$, so muss $\mid K\cap M\mid =k-i$ sein, d.h. es gibt genau ${\binom {n}{i}}{\binom {m}{k-i}}$ k-Untermengen mit $\mid K\cap N\mid =i$. Anwendung der Summenregel liefert nun das Ergebnis.

--Anwesender 22:09, 10. Okt. 2010 (CEST)