Kombinatorische Argumentation für folgende Gleichung finden

Question

Hallo, kann mir jmd. bei diesen Gleichung weiterhelfen. Die algebraische Lösung habe ich verstanden. Ich würde aber gerne eine kombinatorische Argumentation bzw. Begründung mit einem Beispiel finden, warum dies stimmt. Vielen Dank.

1.

\( \left(\begin{array}{l}{n+1} \\ {k+1}\end{array}\right)=\left(\begin{array}{l}{n} \\ {k}\end{array}\right) + \left(\begin{array}{l}{n} \\ {k+1}\end{array}\right) \)

2.

\( \left(\begin{array}{l}{n} \\ {n+k-1}\end{array}\right)=\left(\begin{array}{l}{n+k-1} \\ {k}\end{array}\right)  \)

Comments

Bei 2. soll stehen

\(\left(\begin{array}{l}{n+k-1} \\ {n-1}\end{array}\right)=\left(\begin{array}{l}{n+k-1} \\ {k}\end{array}\right)  \)

Answer 1

Wenn du k+1 Dinge aus n+1 Dingen auswählen darfst, kannst du ein mal das n+1. Ding nehmen und dann noch k Dinge aus den n Dingen. Oder du nimmst nicht das n+1. Ding und dann k Dinge aus den n Dingen.

Comments

Ich verstehe was du schreibst, weiß jedoch nicht wie ich dies auf die obigen beiden Gleichungen anwenden soll/kann.

---

Das sollst du zunächst mal nur auf die 1. Gleichung anwenden.

Die 2. Gleichung stimmt ja nicht. Aber ich sehe jetzt hast du sie verbessert.

2.

Argumentiere das

(a über b) = (a über a - b)

Mit a = n + k - 1 und b = n - k bist du dann am Ziel.

---

Das 2. verstehe ich etwas besser.

Beim 1. stehe ich leider immer noch auf dem Schlauch. Aus kombinatorischer Sicht kann ich mir keinen Reim daraus machen wieso die linke Seite = der rechten ist. Ich wähle ja auf der rechten Seite zweimal aus einer Menge n. Auf der rechten Seite dann plötzlich aus einer Menge n+1. Das verstehe ich einfach nicht

---

Du hast 4+1 = 5 Kugeln (1), (2), (3), (4), (5)

Von diesen darfst du 2+1 = 3 Kugeln nehmen. Dafür hast du (4 + 1 über 2 + 1) Möglichkeiten.

Dann kannst du zuerst die Kugel (5) nehmen und dann noch 2 aus den Kugeln (1), (2), (3), (4). Dafür hast du (4 über 2) Möglichkeiten.

Oder du nimmst nicht die Kugel (5) und dafür 2 + 1 = 3 Kugeln aus den Kugeln (1), (2), (3), (4). Dafür hast du (4 über 3) Möglichkeiten

(5 über 3) = (4 über 2) + (4 über 3)

---

Danke für dein Beispiel. Das hilft mir sehr. Habe es nun besser verstanden. Zwei kleine Fragen habe ich aber noch:

1. Du sagst " Dann kannst du zuerst die Kugel (5) nehmen und dann noch 2" . Das Ziehen der zwei Kugeln wird ja durch 4 über 2 bzw. nüber k abgeildet. Allerdings wird der Vorgang, dass ich vorher die Kugel 5 nehme doch nun gar nicht berücksichtig bzw. abgebildet. Müsste das nicht auch in die Formel oder warum wird das Ziehen der Kugel 5 nicht berücksichtig in der Fromel.

2. Du sagst danach "Oder du nimmst nicht die Ku"  warum "Oder" ? in der Gleichung werden ja die beiden Vorgänge addiert. Es heißt ja (4 über 2) + (4 über 3) und nicht
(4 über 2) oder (4 über 3)

Answer 2

Aloha :)

\(\binom{n}{k}\) ist die Anzahl der Möglichkeiten, aus \(n\) Objekten genau \(k\) Objekte (ohne Zurücklegen) auszuwählen. Nun packst du zu den \(n\) Objekten eines hinzu, hast also \((n+1)\) Objekte. Wenn du daraus nun \((k+1)\) Objekte auswählen möchtest, gibt es 2 Möglichkeiten:

a) Das neue Objekt wird ausgewählt, dann müssen aus den alten \(n\) Objekten noch genau \(k\) weitere ausgewählt werden. Dafür gibt es \(\binom{n}{k}\) Möglichkeiten.

b) Das neue Objekt wird nicht ausgewählt, dann müssen aus den alten \(n\) Objekten genau \((k+1)\) Objekte ausgewählt werden. Dafür gibt es \(\binom{n}{k+1}\) Möglichkeiten.

Zusammengefasst heißt das formal:$$\binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}$$

Die zweite Gleichung ist eignetlich sofort klar. Wenn du aus \(n\) Objekten genau \((n-k)\) auswählen möchtest, kannst du genauso gut aus den \(n\) Objekten genau \(k\) Objekte markieren, die du nicht auswählen möchtest. Die Anzahl der Möglichkeiten muss gleich sein:$$\binom{n}{n-k}=\binom{n}{k}$$

Daraus folgt die etwas fummelige Beziehung aus der Aufgabenstellung:$$\binom{n+k-1}{n-1}=\binom{n+k-1}{(n+k-1)-(n-1)}=\binom{n+k-1}{k}$$