kombinatorischer Beweis durch doppeltes Abzählen in einem geeigneten paaren Graphen

Question

Aufgabe:

Text erkannt:

3.3 Es seien \( n \geq l \geq k \) gegebene natürliche Zahlen. Man gebe einen kombinatorischen Beweis für die Identität
\( \binom{n}{l} \cdot\binom{l}{k}=\binom{n}{k} \cdot\binom{n-k}{l-k} \)
durch doppeltes Abzählen in einem geeigneten paaren Graphen.

Problem/Ansatz:

Ich habe leider keine Ahnung. Hier der Lösungsvorschlag meines Dozenten: Ich brauche dringend Hilfe beim Verständnis :(

Answer 1

Also die Grafik ist mir auch nicht so ganz klar. Aber vielleicht kommst Du mit Folgendem weiter.

Wir betrachten einen paaren Graph. Die eine Knotenmenge X besteht aus allen l-elementigen Teilmengen von {1,...,n}, die andere Y aus allen k-elementigen Teilmengen. Ein Knoten x aus X ist mit einem Knoten y aus Y verbunden (Kante) genau dann, wenn y Teilmenge von x ist.

Jetzt zählen wir die Kanten ab:

1. Die Anzahl |X| ist \( {n \choose l}\). Vo jedem x aus X gehen \( {l \choose k}\) Kanten aus, weil x eben so viele k-elementigen Teilmengen hat. Insgesamt:\( {n\choose l}{l \choose k}\)

2. Die Anzahl |Y| ist \( {n \choose k}\). Von jedem y gehen so viele Kanten aus, wie es l-elementige Obermengen von y gibt. Eine solche Obermenge erhält man, indem man l-k Elemente aus den nicht zu y gehörenden Elementen von {1,...,n} auswählt, das sind \( {n-k\choose l-k }\). Insgesamt \( {n \choose k} {n-k\choose l-k }\).

Answer 2

Hier ist ein einfaches kombinatorisches Modell mit Boxen und Kugeln.

Wir haben \(n\) (unterscheidbare, z. Bsp. nummerierte) leere Boxen und \(l\) Kugeln. Von den \(l\) Kugeln sind \(\color{blue}{k}\) blau und \(\color{red}{l-k}\) sind rot. Die Kugeln einer Farbe sind jeweils ununterscheidbar.

Wir wollen jetzt wissen, auf wie viele verschiedene Weisen kann man jeweils alle \(l\) Kugeln in die Boxen legen, sodass in jeder Box höchstens eine Kugel ist.

Zählung 1:

Wähle von den \(n\) Boxen \(\color{blue}{k}\) Stück für blaue Kugeln: \(\binom nk\)

Wähle von den restlichen \(n-k\) Boxen \(\color{red}{l-k}\) für die roten Kugeln: \(\binom {n-k}{l-k}\)

Insgesamt: \(\binom nk\binom {n-k}{l-k}\)

Zählung 2:

Wähle von den \(n\) Boxen zunächst \(l\) Boxen für die \(l\) Kugeln: \(\binom nl\)

Wähle nun von diesen \(l\) Boxen \(\color{blue}{k}\) Stück für blaue Kugeln: \(\binom lk\)

(die roten Kugeln kommen in die restlichen \(\color{red}{l-k}\) der l gewählten Boxen)

Insgesamt: \(\binom nl\)\(\binom lk\)