Kombinatorik

Kombinatorik

Die Kombinatorik beschäftigt sich mit der Anzahl der möglichen Anordnungen bei einem Versuch, wobei sie unterscheidet, ob die Reihenfolge von Bedeutung ist oder nicht und ob Wiederholungen (Zurücklegen) zugelassen werden oder nicht.

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 Versuchs. 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.

1. 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.

2. 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.

3. Ohne Beachtung der Reihenfolge, mit Zurücklegen

[math]\displaystyle{ \binom{n+k-1}{k} }[/math] wird zur Vollständigkeit erwähnt!

4. 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].

Für [math]\displaystyle{ \binom{n}{k} }[/math] sagen wir „n über k“. Für [math]\displaystyle{ n! }[/math] sagen wir „n-Fakultät“.