Aloha :)
Du hast die Aufgabenstellung richtig abstrahiert. Im Kern geht es darum, eine rekursive Formel für den Binomialkoeffizienten \(\binom{n}{k}\) zu finden...
\(\binom{n}{k}\) soll die Anzahl der unterschiedlichen \(k\)-elementigen Teilmengen einer \(n\)-elementigen Menge sein. Es ist klar, dass eine \(n\)-elementige Menge genau eine \(n\)-elementige Teilmenge hat, nämlich sich selbst. Und es ist klar, dass eine \(n\)-elementige Menge genau eine \(0\)-elementige Teilmenge hat, nämlich die leere Menge. Damit haben wir schon mal die Abbruchbedingungen für unsere Rekursion:$$\binom{n}{0}\coloneqq1\quad;\quad\binom{n}{n}\coloneqq1$$Es ist auch klar, dass \(\binom{n}{k}\) für \(k>n\) nicht definiert ist, denn wir können aus einer Menge nicht mehr Elemente auswählen als sie hat.
Für die Rekursion überlegen wir uns, dass wir zu einer \(n\)-elementigen Menge \(1\) Element dazu tun und aus der neuen \((n+1)\)-elementigen Menge alle \(k\)-elementigen Teilmengen bilden wollen. Wir suchen also eine Formel für \(\binom{n+1}{k}\).
Dazu unterscheiden wir zwei Fälle:
1. Fall: Das neu hinzu gekommene Element wird nicht ausgewählt.
Dann müssen alle \(k\) ausgewählten Elemente aus den bisherigen \(n\) Elementen stammen. Dafür gibt es \(\binom{n}{k}\) Möglichkeiten.
2. Fall: Das neu hinzu gekommene Element wird ausgewählt.
Dann müssen aus den bisherigen \(n\) Elementen noch genau \((k-1)\) ausgewählt werden. Dafür gibt es \(\binom{n}{k-1}\) Möglichkeiten.
Da entweder Fall 1 oder Fall 2 eintritt, zählen wir keine Möglichkeit doppelt und erhalten eine einfache Rekursionsformel:$$\binom{n+1}{k}=\binom{n}{k}+\binom{n-1}{k}$$
Diese Rekursion kann man graphisch sehr schön als sog. "Pasal-Dreieck" darstellen:$$\begin{array}{c}\binom{0}{0}\\\binom{1}{0} \binom{1}{1}\\\binom{2}{0} \binom{2}{1} \binom{2}{2}\\\binom{3}{0} \binom{3}{1} \binom{3}{2} \binom{3}{3}\\\binom{4}{0} \binom{4}{1} \binom{4}{2} \binom{4}{3} \binom{4}{4}\\\binom{5}{0} \binom{5}{1} \binom{5}{2} \binom{5}{3} \binom{5}{4} \binom{5}{5}\end{array}\quad\begin{array}{c}1\\1\;\;1\\1\;\;2\;\;1\\1\;\;3\;\;3\;\;1\\1\;\; 4\;\;6\;\;4\;\;1\\1\;\;5\;\,10\;10\,\;5\;\;1\end{array}$$
An den Rändern findest du die beiden Randbedingungen \(\binom{n}{0}=1\) und \(\binom{n}{n}=1\).
Innerhalb des Dreiecks ergibt sich jede Zahl aus der Summe der beiden Zahlen über ihr.
