Aufgaben zum Thema Kombinatorik

1
Zeige:
$(\binom{n}{n - k}) = (\binom{n}{k})$

Für diese Aufgabe benötigst Du folgendes Grundwissen: Kombinatorik
Zur Erinnerung:
$(\binom{n}{k}) = \frac{n!}{k! (n - k)!}$
Wir beginnen von der rechten Seite:
$(\binom{n}{n - k}) = \frac{n!}{(n - k)! (n - (n - k))!} = \frac{n!}{(n - k)! (n - n + k)!} = \frac{n!}{(n - k)! k!} = (\binom{n}{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{array}{c} n \\ k \end{array})$ .
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):
$(x + 1)^{n} = \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k}$
Nun versuchen wir, darüber $2^{n}$ darzustellen:
$2^{n} = (1 + 1)^{n} = \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) 1^{k} = \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) ■$
Ähnlich verfahren wir mit der zweiten angegebenen Gleichung (mit der Bedingung $n > 0$ ):
$0 = 0^{n} = (1 - 1)^{n} = \sum_{k = 0}^{n} (- 1)^{k} (\begin{array}{c} n \\ k \end{array}) ■$
Anhang
Zuerst müssen wir
$(\begin{array}{c} n \\ k - 1 \end{array}) + (\begin{array}{c} n \\ k \end{array}) = (\begin{array}{c} n + 1 \\ k \end{array})$
zeigen:
$(\begin{array}{c} n \\ k - 1 \end{array}) + (\begin{array}{c} n \\ k \end{array}) = \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{array}{c} n + 1 \\ k \end{array})$
Mit dieser Gleichung können wir nun einen Induktionsbeweis führen mit der Induktionsvoraussetzung:
$(x + 1)^{n} = \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k}, n \in ℕ_{𝟘}$
Beginnen wir bei $n = 0$ und betrachten auch $n = 1$ :
$(x + 1)^{0} = 1 = (\begin{array}{c} 0 \\ 0 \end{array})$
$(x + 1)^{1} = x + 1 = (\begin{array}{c} 1 \\ 0 \end{array}) x + (\begin{array}{c} 1 \\ 1 \end{array})$
Nun können wir den Induktionsschritt von $n \to n + 1$ durchführen:
$(x + 1)^{n + 1} = (x + 1) (x + 1)^{n} \overset{I V}{=} (x + 1) \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k} = x \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k} + \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k} = \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k + 1} + \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k} = \sum_{k = 1}^{n + 1} (\begin{array}{c} n - 1 \\ k \end{array}) x^{k} + \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k} = (\begin{array}{c} n \\ n \end{array}) x^{n + 1} + (\begin{array}{c} n \\ 0 \end{array}) x^{0} + \sum_{k = 1}^{n} ((\begin{array}{c} n \\ k \end{array}) + (\begin{array}{c} n \\ k - 1 \end{array})) x^{k} = (\begin{array}{c} n + 1 \\ n + 1 \end{array}) x^{n + 1} + (\begin{array}{c} n + 1 \\ 0 \end{array}) x^{0} + \sum_{k = 1}^{n} (\begin{array}{c} n + 1 \\ k \end{array}) x^{k} = \sum_{k = 0}^{n + 1} (\begin{array}{c} n + 1 \\ k \end{array}) x^{k} ■$
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):
$\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.):
$(\begin{array}{c} 4 \\ 3 \end{array}) (\begin{array}{c} 4 \\ 2 \end{array}) = 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:
$\frac{13!}{(13 - 2)!} (\begin{array}{c} 4 \\ 3 \end{array}) (\begin{array}{c} 4 \\ 2 \end{array}) = 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:
$P (" F u l l H o u s e ") = \frac{3744}{(\begin{array}{c} 52 \\ 5 \end{array})} = \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