TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 175

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

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)