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

Aus VoWi
Zur Navigation springen Zur Suche springen

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

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

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)