Kombinatorik

Kombinatorik

Die Kombinatorik beschäftigt sich damit, die Anzahl der Elemente von endlichen Mengen geschickt (also durch Rechnen, nicht durch Zählen) zu bestimmen. Sie untersucht die Fragestellung, wie viele Möglichkeiten es gibt, eine endliche Anzahl an Objekten anzuordnen oder auszuwählen.
Dabei unterscheidet man zwischen

• mit / ohne Berücksichtigung der Reihenfolge
• mit / ohne Zurücklegen
• ob alle n Elemente oder nur k (k<=n) Elemente verwendet werden

Kombinatorische Abzählverfahren

Man unterscheidet bei den kombinatorischen Abzählverfahren zwischen Permutationen, Variationen bzw. Kombinationen je nachdem ob alle Elemente (Permutation) oder nur eine Stichprobe verwendet werden. Wird eine Stichprobe verwendet unterscheidet man weiters ob die Reihenfolge relevant (Variation) oder irrelevant (Kombination) ist. Zuletzt unterscheidet man bei allen 3 kombinatorischen Abzählverfahren ob Elemente zurückgelegt werden oder ob nicht.

Fakultät

Zu jeder natürlichen Zahl gibt es eine Fakultät. Die Fakultät ist das Produkt aller natürlichen Zahlen größer als Null, die kleiner oder gleich der jeweiligen natürlichen Zahl sind, von der die Fakultät bestimmt werden soll. "n!" oder „n Faktorielle“ oder “n Fakultät“ sind entsprechende vereinfachte Schreibweisen für Fakultät. F

\(n! = 1 \cdot 2 \cdot 3 \cdot ... \cdot n = \prod\limits_{i = 1}^n k \) mit \(n \in {\Bbb N}\)

Rechenregeln zur Fakultät

\(\eqalign{ & \left( {n + 1} \right)! = n! \cdot \left( {n + 1} \right) \Rightarrow n! = \dfrac{{\left( {n + 1} \right)!}}{{n + 1}} \cr & 0! = \dfrac{{\left( {0 + 1} \right)!}}{{0 + 1}} = \dfrac{1}{1} = 1 \cr & 1! = \dfrac{{\left( {1 + 1} \right)!}}{{1 + 1}} = \dfrac{{2!}}{2} = \dfrac{{1 \cdot 2}}{2} = 1 \cr} \)

\(\eqalign{ & 0! = 1 \cr & 1! = 1 \cr & 2! = 1 \cdot 2 = 2 \cr & 3! = \left( {1 \cdot 2} \right) \cdot 3 = 2 \cdot 3 = 6 \cr & 4! = \left( {1 \cdot 2 \cdot 3} \right) \cdot 4 = 6 \cdot 4 = 24 \cr & 5! = \left( {1 \cdot 2 \cdot 3 \cdot 4} \right) \cdot 5 = 24 \cdot 4 = 120 \cr & 6! = \left( {1 \cdot 2 \cdot 3 \cdot 4 \cdot 5} \right) \cdot 6 = 120 \cdot 6 = 720 \cr & 7! = \left( {1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6} \right) \cdot 7 = 720 \cdot 7 = 5040 \cr} \)

Fakultät in der Kombinatorik

• Permutation: Die Fakultät n! gibt die Anzahl der möglichen unterschiedlichen Reihenfolgen an, die n Elemente einer Menge anzuordnen.
• Binomialkoeffizient: Mit Hilfe der Fakultät kann der Binomialkoeffizient \(\left( {\begin{array}{*{20}{c}} n\\ k \end{array}} \right) = \dfrac{{n!}}{{k! \cdot (n - k)!}}\) berechnet werden, der angibt, wie viele Möglichkeiten es gibt, k Elemente aus einer Menge mit n Elementen zu ziehen.

Binomialkoeffizient

Der Binomialkoeffizient „n über k“ besagt, wie viele Möglichkeiten es gibt, k Elemente aus einer Menge von n Elementen auszuwählen.

\(\eqalign{ & \left( {\matrix{ n \cr k \cr } } \right) = {{n!} \over {k!(n - k)!}} = \left( {\matrix{ n \cr {n - k} \cr } } \right); \cr & \left( {\matrix{ n \cr 0 \cr } } \right) = \left( {\matrix{ n \cr n \cr } } \right) = 1; \cr & \left( {\matrix{ n \cr 1 \cr } } \right) = \left( {\matrix{ n \cr {n - 1} \cr } } \right) = n; \cr & \left( {\matrix{ n \cr k \cr } } \right) + \left( {\matrix{ n \cr {k + 1} \cr } } \right) = \left( {\matrix{ {n + 1} \cr {k + 1} \cr } } \right); \cr}\)

\(n,k \in {\Bbb N};\)

Eingabe am Taschenrechner

\(\left( {\begin{array}{*{20}{c}} 9\\ 3 \end{array}} \right) = 9 + Shift + nCr + 3 = 84\)