TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 159

Man beweise die Beziehung $(\binom{n + 1}{k + 1}) = (\binom{n}{k + 1}) + (\binom{n}{k})$ durch Interpreation von $(\binom{n}{k})$ als Anzahl der $k$ -elementigen Teilmengen einer $n$ -elementigen Menge.

Hilfreiches

Lösungsvorschlag von neo

Man kann die Auswahl von $k + 1$ Elementen aus einer $n + 1$ -elementigen Menge auf eine $n$ -elementige Menge zurückführen (d.h ohne ein Element $a$ ).
Man nimmt zuerst alle $k + 1$ Elemente aus der $n$ -elementigen Menge heraus. Dafür gibt es $(\binom{n}{k + 1})$ Möglichkeiten. Anschließend betrachtet man alle Auswahlen, welche das Element $a$ beinhalten. Da das Element $a$ zwangsweise dabei sein muss, kommen nur $k + 1 - 1 = k$ Elemente aus der $n$ -elementigen Menge dazu.
Das ergibt $(\binom{n}{k})$ Möglichkeiten. So kommt man auf $(\binom{n + 1}{k + 1}) = (\binom{n}{k + 1}) + (\binom{n}{k})$ .

TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 159

Hilfreiches

Lösungsvorschlag von neo

Navigationsmenü

Suche