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

Von $m$ weißen Kugeln, die mit den Zahlen $1,\dots ,m$ nummeriert sind, sollen $k\geq 1$ Kugeln schwarz eingefärbt werden. Wieviele derartige Färbungen gibt es unter der Einschränkung, dass die Kugel mit der Nummer $n$ schwarz ist, und alle Kugeln mit einer höheren Nummer weiß bleiben? Erklären Sie, warum aus dem Ergebnis die folgende Gleichung folgt:

$\sum _{n=1}^{m}{\binom {n-1}{k-1}}={\binom {m}{k}}$

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches

Binomialkoeffizient

Binomialkoeffizient

$\forall n,k\in \mathbb {N} ,k\leq n:\qquad {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}$

Äquivalente Definition (Merkregel): ${\binom {n}{k}}={\frac {\overbrace {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)} ^{k\;{\text{Glieder}}}}{\underbrace {1\cdot 2\cdots k} _{k\;{\text{Glieder}}}}}$ Spezialfall: ${\tbinom {n}{0}}:=1$

Lösungsvorschlag

Insgesamt gibt es also $m$ weiße Kugeln, die alle nummeriert sind, d.h. deren Reihenfolge ist bedeutsam. Von diesen weißen Kugeln sollen nun $k$ (mindestens aber eine) Kugeln schwarz eingefärbt werden. Zusätzlich gibt es eine Kugel mit der Nummer $n$, die immer schwarz gefärbt wird. Diese Kugel dient als "Abgrenzung" zu den restlichen weißen Kugeln. Alle Kugeln, die nach der schwarzen Kugel mit der Nummer $n$ kommen, bleiben unberührt, also weiß.

Leichter verständlich wird es, wenn man die Kugeln visualisiert:

$\circ \circ \circ \circ \circ \dots \bullet \circ \circ \dots \circ$

Insgesamt gibt es $m$ Kugeln, die letzte schwarze Kugel hat die Nummer $n$. Das heißt also, vor der $n$-Kugel gibt es immer $n-1$ Kugeln, die man schwarz einfärben darf. Ist $k<n$ sollen weniger Kugeln eingefärbt werden als zur Verfügung stünden. Anders gesagt: Es stehen mehr Kugeln zum Einfärben zur Verfügung als wirklich eingefärbt werden sollen. In diesem Fall gibt es mehrere Möglichkeiten, die zu färbenden Kugeln auszuwählen. Wie viele Möglichkeiten es gibt, kann man leicht mit Hilfe des Binomialkoeffizient berechnen. Es handelt es sich also um ein "Kombination ohne Wiederholung"-Problem ("Auswählen einer Teilmenge", etc.).

Im Term der Angabe sind $m$ und $k$ fix gegeben während $n$ eine Laufvariable ist. Wir überlegen uns die Fälle $k=1,2$ um daraus dann das Ergebnis der Angabe abzuleiten:

$k=1$

Es soll eine Kugel schwarz eingefärbt werden.

Egal wie groß wir $n$ wählen, nachdem $k=1$ ist, können wir keine weiteren Kugeln schwarz einfärben.

$n=1:\bullet \circ \circ \dots \circ$

$n=2:\circ \bullet \circ \dots \circ$

$n=3:\circ \circ \bullet \dots \circ$

...

$n=m:\circ \circ \circ \dots \bullet$

Für jede Zeile wurde $n$ also mit einem Wert zwischen $1$ und $m$ festgelegt. Jede Zeile kann als "Kombination ohne Wiederholung" aufgefasst werden. "Wieviele Möglichkeiten gibt es, 0 Kugeln (= $k-1$) aus $n-1$ Kugeln einzufärben?": ${\binom {n-1}{k-1}}={\binom {n-1}{0}}=1$ (Von $n$ und $k$ ist $1$ abzuziehen, da nur die frei zu wählenden Kugeln, also alle Kugeln vor der $n$-Kugel in Betracht gezogen werden dürfen.). Nun summiert man das Ergebnis für jede Zeile auf: $\sum _{n=1}^{m}{\binom {n-1}{k-1}}=1+1+1+\dots +1=m$.

Conclusio

Betrachtet man nun alle Zeilen gemeinsam, das "Kombination ohne Wiederholung"-Problem also generell über alle $n$ hinweg, so ergibt sich die Fragestellung "Wieviele Möglichkeiten gibt es, 1 Kugel (= $k$) aus $m$ Kugeln einzufärben?": ${\binom {m}{k}}={\binom {m}{1}}=m$.

Somit ist das Ergebnis aus der Angabe zumindest für $k=1$ erklärt.

$k=2$

Schauen wir uns nun den Fall $k=2$ an. Es sollen zwei Kugeln schwarz eingefärbt werden.

Die $n$-Kugel ist immer schwarz, wobei eine weitere Kugel zu wählen ist, die eingefärbt wird. Je nach größe von $n$ stehen unterschiedlich viele Kugeln zum Einfärben zur Verfügung.

$n=1(=n<k)$

Die erste Kugel ist schwarz, wir sollen aber zwei Kugeln einfärben. Die Bedingung aus der Angabe, dass die $n$-Kugel immer die letzte schwarze Kugel ist, kann zusammen mit der Bedingung, dass $k$ Kugeln schwarz eingefärbt werden sollen, nicht gewährleistet werden, da einfach zu wenig Kugeln zum Einfärben zur Verfügung stehen. In diesem Fall gibt es also 0 Möglichkeiten: ${\binom {n-1}{k-1}}={\binom {0}{1}}=0$. Gemäß der Definition des Binomialkoeffizienten ist das Ergebnis $0$ wenn $k>n$.

$n=2$

Die zweite Kugel wird immer schwarz gefärbt. Die erste Kugel ist somit auch schwarz, da 2 Kugeln schwarz sein müssen und nur die erste zur Auswahl steht.

$\bullet \bullet \circ \circ \dots \circ$

Binomialkoeffizient: ${\binom {n-1}{k-1}}={\binom {1}{1}}=1$

$n=3$

Die dritte Kugel wird nun immer schwarz gefärbt. Hier gibt es nun mehrere Fälle:

$\bullet \circ \bullet \circ \dots \circ$

$\circ \bullet \bullet \circ \dots \circ$

Binomialkoeffizient: ${\binom {n-1}{k-1}}={\binom {2}{1}}=2$

$n=4$

Die vierte Kugel wird nun immer schwarz gefärbt. Hier gibt es nun mehrere Fälle:

$\bullet \circ \circ \bullet \dots \circ$

$\circ \bullet \circ \bullet \dots \circ$

$\circ \circ \bullet \bullet \dots \circ$

Binomialkoeffizient: ${\binom {n-1}{k-1}}={\binom {3}{1}}=3$

$n=m$

Generell lässt sich also sagen, dass hier auch wieder ein "Kombination ohne Wiederholung"-Problem vorliegt. "Wieviele Möglichkeiten gibt es, $k-1$ Kugeln aus $n-1$ Kugeln einzufärben?"

Binomialkoeffizient: ${\binom {n-1}{k-1}}={\binom {m-1}{k-1}}$

Conclusio

Das Endergebnis ist nun wieder die Summe über alle möglichen Fälle: $\sum _{n=1}^{m}{\binom {n-1}{k-1}}=0+1+2+\dots +{\binom {m-1}{1}}$. Diese Summe lässt sich nun nicht mehr so leicht ausrechnen wie für $k=1$.

Allgemeine Betrachtung

Man sieht nun ganz allgemein, dass eine Zeile (also eine Möglichkeit für $k$ schwarze Kugeln) über alle möglichen $n$ hinweg für ein bestimmtes $k$ nie doppelt vorkommt. Dadurch kann man ganz allgemein sagen, dass $k$ Kugeln aus $m$ möglichen Kugeln zum Einfärben ausgewählt werden sollen. Die Anzahl dieser Möglichkeiten lässt sich über den Binomialkoeffizient berechnen: ${\binom {m}{k}}$ Womit das Ergebnis der Angabe erklärt wäre.

-- Superwayne (Diskussion) 13:22, 10. Nov. 2014 (CET)