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

From VoWi
Jump to navigation Jump to search

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

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

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

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