Aufgaben zum Thema Kombinatorik

1
Zeige:
$\displaystyle {n \choose {n - k}} = \binom{n}{k}$

Für diese Aufgabe benötigst Du folgendes Grundwissen: Kombinatorik
Zur Erinnerung:
$\displaystyle {n \choose k} = \dfrac{n!}{k!(n - k)!}$
Wir beginnen von der rechten Seite:
$\displaystyle {n \choose {n - k}} = \dfrac{n!}{(n - k)!(n - (n - k))!} = \dfrac{n!}{(n - k)!(n - n + k)!} = \dfrac{n!}{(n - k)!k!} = {n \choose k}$

Weil sich das $n$ in $(n - (n - k))!$ „herauskürzt“ und nur $k!$ über bleibt und wir noch $(n - k)!$ im Nenner haben (Der Zähler ist bei beiden sowieso gleich), erhalten wir den selben Nenner wie bei $\begin{pmatrix}n\\k\end{pmatrix}$ .
2
Gib die Koeffizienten des Polynoms $(1 + x)^{n}$ mittels Binomialkoeffizienten an und zeige durch geschickes Verwenden dieser Formel
$\sum_{k=0}^n\binom{n}{k} = 2^n$ und, falls n>0, $\sum_{k=0}^n(-1)^k\binom{n}{k} = 0$

Für diese Aufgabe benötigst Du folgendes Grundwissen: Kombinatorik
Zuerst geben wir die Koeffizienten von $(x + 1)^{n}$ an (Beweis ist der Vollständigkeit angehängt; laut der Aufgabenstellung reicht das bloße Angeben):
$\displaystyle (x+1)^n=\sum_{k=0}^n{\begin{pmatrix}n\\k\end{pmatrix}x^k}$
Nun versuchen wir, darüber $2^{n}$ darzustellen:
$\displaystyle 2^n=(1+1)^n=\sum_{k=0}^n{\begin{pmatrix}n\\k\end{pmatrix}1^k}=\sum_{k=0}^n{\begin{pmatrix}n\\k\end{pmatrix}}\\\blacksquare$
Ähnlich verfahren wir mit der zweiten angegebenen Gleichung (mit der Bedingung $n > 0$ ):
$\displaystyle 0=0^n=(1-1)^n=\sum_{k=0}^n{(-1)^k\begin{pmatrix}n\\k\end{pmatrix}}\\\blacksquare$
Anhang
Zuerst müssen wir
$\displaystyle \begin{pmatrix}n\\k-1\end{pmatrix}+\begin{pmatrix}n\\k\end{pmatrix}=\begin{pmatrix}n+1\\k\end{pmatrix}$
zeigen:
$\displaystyle \begin{pmatrix}n\\k-1\end{pmatrix}+\begin{pmatrix}n\\k\end{pmatrix}=\frac{n!}{(k-1)!(n-(k-1))!}+\frac{n!}{k!(n-k)!}=\frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{k!(n-k)!}=\frac{n!}{(k-1)!(n-k)!}\cdot\frac{1}{n-k+1}+\frac{n!}{k!(n-k)!}=\frac{n!}{(k-1)!(n-k)!}\cdot\frac{k}{k}\cdot\frac{1}{n-k+1}+\frac{n!}{k!(n-k)!}=\frac{n!}{k(k-1)!(n-k)!}\cdot\frac{k}{n-k+1}+\frac{n!}{k!(n-k)!}=\frac{n!}{k!(n-k)!}\cdot\frac k{n-k+1}+\frac{n!}{k!(n-k)!}=\frac{n!}{k!(n-k)!}(1+\frac k{n-k+1})=\frac{n!}{k!(n-k)!}(\frac{n-k+1}{n-k+1}+\frac k{n-k+1})=\frac{n!}{k!(n-k)!}\cdot\frac{n+1}{n-k+1}=\frac{(n+1)!}{k!((n+1)-k)!}=\begin{pmatrix}n+1\\k\end{pmatrix}$
Mit dieser Gleichung können wir nun einen Induktionsbeweis führen mit der Induktionsvoraussetzung:
$\displaystyle (x+1)^n=\sum_{k=0}^n{\begin{pmatrix}n\\k\end{pmatrix}x^k},n\in\mathbb{N_0}$
Beginnen wir bei $n = 0$ und betrachten auch $n = 1$ :
$\displaystyle (x+1)^0=1=\begin{pmatrix}0\\0\end{pmatrix}$
$\displaystyle (x+1)^1=x+1=\begin{pmatrix}1\\0\end{pmatrix}x+\begin{pmatrix}1\\1\end{pmatrix}$
Nun können wir den Induktionsschritt von $n\rightarrow n+1$ durchführen:
$\displaystyle (x+1)^{n+1}=(x+1)(x+1)^n\overset{IV}=(x+1)\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}x^k=x\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}x^k+\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}x^k=\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}x^{k+1}+\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}x^k=\sum_{k=1}^{n+1}\begin{pmatrix}n-1\\k\end{pmatrix}x^k+\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}x^k=\begin{pmatrix}n\\n\end{pmatrix}x^{n+1}+\begin{pmatrix}n\\0\end{pmatrix}x^0+\sum_{k=1}^n(\begin{pmatrix}n\\k\end{pmatrix}+\begin{pmatrix}n\\k-1\end{pmatrix})x^k=\begin{pmatrix}n+1\\n+1\end{pmatrix}x^{n+1}+\begin{pmatrix}n+1\\0\end{pmatrix}x^0+\sum_{k=1}^n\begin{pmatrix}n+1\\k\end{pmatrix}x^k=\sum_{k=0}^{n+1}\begin{pmatrix}n+1\\k\end{pmatrix}x^k\\\blacksquare$
3
Wie viele verschiedene "Full House" gibt es beim Poker? (52 Karten, vier Farben mit je 2, 3, 4,…, 10, Bube, Dame, König, As)

Für diese Aufgabe benötigst Du folgendes Grundwissen: Kombinatorik
Wir haben $52$ Karten, $4$ Farben, folglich auch $\frac{52}{4}=13$ verschiedene Figuren und damit jeweils $\frac{52}{13}=4$ Figuren einer Sorte.
Für ein Full House benötigen (wenn wir vom Pokerspiel mit $5$ ausgeteilten Karten ausgehen… Ist nicht genau spezifiziert, wahrscheinlich aber implizit gemeint) wir $3$ Karten von einer Figur (ein Drilling) und $2$ Karten von einer anderen Figur (ein Paar) auf der Hand.
Zuerst müssen wir uns überlegen, wie viele Möglichkeiten es gibt, $2$ verschiedene Figuren aus den $13$ auszuwählen, die Reihenfolge beachten wir hierbei noch (im Vergleich zum Urnenmodell: mit Unterscheidung der Reihenfolge und ohne Zurücklegen):
$\displaystyle \frac{13!}{(13-2)!}=\frac{13!}{11!}=13\cdot 12=156$
Anschließend müssen wir uns noch überlegen, wie viele Möglichkeiten es gibt, $3$ Karten aus den ersten Figuren und $2$ Karten von den zweiten Figuren auszuwählen (jeweils im Vergleich zum Urnenmodell: ohne Unterscheidung der Reihenfolge und ohne Zurücklegen). Da jede Auswahlmöglichkeit der $3$ Karten auf jede Auswahlmöglichkeit bei den $2$ Karten angewandt werden kann, sind die Möglichkeiten insgesamt (Anmerkung: Hier liegt der Grund, wieso wir vorhin die Reihenfolge beachtet haben: Wir müssen zwischen Figuren, von denen wir $3$ Karten und Figuren, von denen wir $2$ Karten ziehen unterscheiden. Natürlich hätte man aber oben ohne Reihenfolge ziehen können und dann hier einen Faktor $2$ für das Vertauschen integrieren. Das Endergebnis wäre das selbe.):
$\displaystyle \begin{pmatrix}4\\3\end{pmatrix}\begin{pmatrix}4\\2\end{pmatrix}=24$
Nun können wir beide Möglichkeiten zusammenführen, wobei wir wieder bei jedem Paar von Figuren entsprechend $3$ und $2$ Karten auswählen müssen:
$\displaystyle \frac{13!}{(13-2)!}\begin{pmatrix}4\\3\end{pmatrix}\begin{pmatrix}4\\2\end{pmatrix}=3744$
Dies entspricht aller Möglichkeiten, ein Full House aus $5$ Karten bei einem $52$ er-Kartenblatt zu bilden.
Die Wahrscheinlichkeit für einen Full House beträgt nebenbei entsprechend:
$\displaystyle P("Full House")=\frac{3744}{\begin{pmatrix}52\\5\end{pmatrix}}=\frac{3744}{2598960}=\approx 0{,}144\%$

Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0 → Was bedeutet das?

Aufgaben zum Thema Kombinatorik

Anhang