Rekursive Formel für Gleichung mit Binomialkoeffizient finden

Question

Aufgabe:

Es werden immer n Geschenke auf m ununterscheidbare Boxen verteilt. Dabei gilt für jede gültige Kombination, dass jede Box genau ein Geschenk enthält, und jedes Geschenk wird maximal einmal vergeben. T(n,m) gibt die Anzahl der verschiedenen gültigen Aufteilungen, wobei symmetrische Aufteilungen, weil die Boxen ja gleich aussehen, nicht mehrfach gezählt werden.

Entwickeln sie eine rekursive Berechnungsmethode für T(n,m).

Problem/Ansatz:

Erstmal habe ich mir überlegt, dass T(n,m) ja n C m entspricht, also dem Binomialkoeffizient. Für n = 4 und m = 2 gibt es ja beispielsweise die gültigen Kombinationen:

1) (G1, B1). (G2, B2)

2) (G1, B1). (G3, B2)

3) (G1, B1). (G4, B2)

4) (G2, B1). (G3, B2)

5) (G2, B1). (G4, B2)

6) (G3, B1). (G4, B2)

Also 6 Kombinationen, was genau 4 C 2 entspricht. Bis hier müsste ich ja richtig liegen, oder?

Jetzt habe ich allerdings nicht wirklich eine Idee, wie ich das in eine rekursive Formel umandeln kann...

Hat hier vielleicht jemand einen Tipp?

Comments

Das gilt aber nur für $n\geq m$. Was ist, wenn es mehr Boxen als Geschenke gibt?

---

Hast recht, das wird nicht abgedeckt durch den Binomialkoeffizient... Ja habe leider keine Idee, hast du vielleicht einen Tipp?

---

das wird nicht abgedeckt

Doch.

---

Merke:

(n über k) = 0 wenn k > n

Answer 1

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.

Answer 2

Warst du bereits selber mal auf die Idee gekommen, bei Wikipedia zu recherchieren?

https://de.wikipedia.org/wiki/Binomialkoeffizient

Stichwort Pascalsches Dreieck.