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)