Zeigen Sie, dass für m, n, k ∈ ℕ gilt:

Question

Aufgabe:

Zeigen Sie, dass für m, n, k ∈ ℕ gilt:

$$\sum \limits_{j=0}^{k}\begin{pmatrix} n\\j \end{pmatrix}\begin{pmatrix} m\\k-j \end{pmatrix} =\begin{pmatrix} n+m\\k \end{pmatrix}$$

Hinweis: Betrachten Sie disjunkte Mengen A und B mit I A I = n und I B I = m.

Folgern Sie danach, dass für alle n, k ∈ ℕ gilt:

$$\begin{pmatrix} n+1\\k+1 \end{pmatrix}=\begin{pmatrix} n\\k \end{pmatrix} + \begin{pmatrix} n\\k+1 \end{pmatrix}$$

Answer 1

Aloha :)

Das scheint mir mehr eine Verständnis-Aufgabe als eine Rechenaufgabe zu sein...

\(\binom{n+m}{k}\) ist die Anzahl der Möglichkeiten, aus \((n+m)\) Objekten genau \(k\) auszuwählen. Lege die \((n+m)\) Objekte der Reihe nach nebeneinander. Wenn du von den ersten \(n\) Objekten der Reihe genau \(j\) auswählst, wofür es \(\binom{n}{j}\) Möglichkeiten gibt, musst du von den hinteren \(m\) Objekten noch genau \((k-j)\) auswählen, wofür es \(\binom{m}{k-j}\) Möglichkeiten gibt. Macht insgesamt \(\binom{n}{j}\cdot\binom{m}{k-j}\) Möglichkeiten.

Da du aus den ersten \(n\) Objekten \(j=0\), \(j=1\), \(j=2\), ... oder \(j=k\) Objekte auszuwählen kannst, musst du diese Möglichkeiten noch summieren:$$\sum\limits_{j=0}^k\binom{n}{j}\cdot\binom{m}{k-j}=\binom{n+m}{k}$$

Wenn du dieses Prinzip verstanden hast, ist auch$$\binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}$$sofort ohne Rechnung klar. Du hast \((n+1)\) Objekten und sollst genau \((k+1)\) davon auswählen. Markiere eines dieser Objekte. Wenn das markierte Objekt ausgewählt wird, müssen von den übrigen \(n\) Objekten noch \(k\) Objekte ausgewählt werden, was \(\binom{n}{k}\) Möglichkeiten liefert. Wenn das markierte Objekt nicht ausgewählt wird, müssen von den übrigen \(n\) Objekten genau \((k+1)\) Objekte ausgewählt werden, was \(\binom{n}{k+1}\) Möglichkeiten liefert. In Summe ergibt das die Gleichung.