Kombinatorik
Definition
Die Kombinatorik beschäftigt sich mit der Untersuchung von endlichen oder abzählbar unendlichen Mengen und ihren Strukturen. Sie befasst sich insbesondere mit der Frage, wie viele verschiedene Möglichkeiten es bei einem Zufallsexperiment gibt, bestimmte Anordnungen oder Auswahlen zu treffen. Dabei wird unterschieden, ob die Reihenfolge von Bedeutung ist oder nicht und ob Wiederholungen (Zurücklegen) zugelassen werden oder nicht.
Fakultät
Es sei [math]\displaystyle{ k }[/math] eine ganze Zahl, dann heißt [math]\displaystyle{ k!=k \cdot (k-1) \cdot (k-2) \cdot ... \cdot 1 }[/math] die Fakultät von [math]\displaystyle{ k }[/math].
Binomialkoeffizient
Für ganze Zahlen [math]\displaystyle{ 0 \leq k \leq n }[/math] ist der Binomialkoeffizient durch [math]\displaystyle{ \begin{align} \binom nk &= \frac{n!}{k!(n-k)!} \end{align} }[/math] definiert. Für [math]\displaystyle{ k \gt n }[/math] setzen wir [math]\displaystyle{ \binom nk := 0 }[/math].
Anzahl möglicher Ergebnisse bei einem Zufallsexperiment ermitteln
Es sei [math]\displaystyle{ e=(e_1;e_2;...;e_k) }[/math] für [math]\displaystyle{ k\in\mathbb{N} }[/math] das Ergebnis eines k-stufigen Zufallsexperiments. Es gilt [math]\displaystyle{ {e_i\in{f}_1;...,f_n} }[/math] für [math]\displaystyle{ n\in\mathbb{N} }[/math], [math]\displaystyle{ n\geq k }[/math] mit [math]\displaystyle{ 0 \le i \leq k }[/math]. D. h. es werden k-Elemente aus einer Menge von n Elementen gezogen.
- Beachtung der Reihenfolge, mit Zurücklegen
Bei jeder Stufe kann [math]\displaystyle{ e_i }[/math] genau einen der Werte [math]\displaystyle{ f_1,...,f_n }[/math] annehmen. Insgesamt gibt es also [math]\displaystyle{ n\cdot ...\cdot n=n^k }[/math] mögliche Ergebnisse. - Beachtung der Reihenfolge, ohne Zurücklegen
[math]\displaystyle{ e_1 }[/math] kann n unterschiedliche Werte annehmen. [math]\displaystyle{ e_2 }[/math] kann dann nur noch n-1 unterschiedliche Werte annehmen und so weiter. Damit gibt es [math]\displaystyle{ n\cdot\left(n-1\right)\cdot\ldots\cdot\left(n-k+1\right)=\frac{n\cdot\left(n-1\right)\cdot\ldots\cdot\left(n-k\right)\cdot\ldots\cdot1}{\left(n-k\right)\cdot\left(n-k-1\right)\cdot\ldots\cdot1}=\frac{n!}{\left(n-k\right)!} }[/math] mögliche Ergebnisse. - Ohne Beachtung der Reihenfolge, mit Zurücklegen
[math]\displaystyle{ \binom{n+k-1}{k} }[/math] wird zur Vollständigkeit erwähnt! - Ohne Beachtung der Reihenfolge, ohne Zurücklegen
[math]\displaystyle{ e_1 }[/math] kann n unterschiedliche Werte annehmen. [math]\displaystyle{ e_2 }[/math] kann dann nur noch n-1 unterschiedliche Werte annehmen und so weiter. Unter diesen [math]\displaystyle{ n\cdot\left(n-1\right)\cdot\ldots\cdot\left(n-k+1\right) }[/math] Möglichkeiten gibt es [math]\displaystyle{ k\cdot\left(k-1\right)\cdot\ldots\cdot 1 }[/math] so viele, verschiedene Reihenfolgen für e, die zum gleichen Ergebnis führen. Insgesamt gibt es also [math]\displaystyle{ \frac{n\cdot\left(n-1\right)\cdot\ldots\cdot\left(n-k+1\right)}{\left(k-1\right)\cdot\ldots\cdot1}=\frac{n\cdot\left(n-1\right)\cdot\ldots\cdot\left(n-k+1\right)\cdot\left(n-k\right)\cdot\ldots\cdot1}{\left(n-k\right)\cdot\ldots\cdot1\cdot\left(k-1\right)\cdot\ldots\cdot1}=\frac{n!}{\left(n-k\right)!\cdot k!}=\binom{n}{k} }[/math].