TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 175
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)