Werbung
Kombinatorik
Hier findest du folgende Inhalte
Formeln
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.
| 1. Unterscheidung: alle Elemente oder Stichprobe |
2. Unterscheidung, falls Stichprobe: Reihenfolge relevant oder egal | 3. Unterscheidung: mit oder ohne Wiederholung | ||
| Kombinatorische Abzählverfahren | Elemente der Grundmenge | Reihenfolge bzw. Anordnung | Wiederholung, Zurücklegen, treten Elemente mehrfach auf |
Anzahl |
|
Permutation Urnenmodel: Ziehen aller n unterscheidbaren Kugeln ohne Zurücklegen, wobei die Reihenfolge beachtet wird |
alle n Elemente müssen verwendet werden | relevant \(\left( {a,b} \right) \ne \left( {b,a} \right)\) |
ohne | \(n!\) |
|
Permutation Urnenmodel: Ziehen aller n Kugeln, von denen manche r, s und t fach vorkommen / mit Zurücklegen, wobei die Reihenfolge beachtet wird |
alle n Elemente müssen verwendet werden | relevant \(\left( {a,b} \right) \ne \left( {b,a} \right)\) |
mit | \(\begin{gathered} \dfrac{{n!}}{{r! \cdot s! \cdot t!}} \\ {\text{mit:}} \\ r + s + t = n \\ \end{gathered}\) |
|
Variation Urnenmodel: Ziehen von nur k aus n unterscheidbaren Kugeln, wobei die Reihenfolge beachtet wird |
nur k Elemente (Stichprobe) werden verwendet | relevant \(\left( {a,b} \right) \ne \left( {b,a} \right)\) |
ohne | \(\dfrac{{n!}}{{\left( {n - k} \right)!}} = \left( {\begin{array}{*{20}{c}} n\\ k \end{array}} \right) \cdot k!\) |
|
Variation Urnenmodel: Ziehen von nur k aus n unterscheidbaren Kugeln, von denen manche mehrfach vorkommen können, wobei die Reihenfolge beachtet wird |
nur k Elemente (Stichprobe) werden verwendet | relevant \(\left( {a,b} \right) \ne \left( {b,a} \right)\) |
mit | \({n^k}\) |
|
Kombination Urnenmodel: Ziehen von nur k aus n unterscheidbaren Kugeln, ohne Beachtung der Reihenfolge N … Anzahl der Elemente insgesamt M … Anzahl der Elemente, die als Erfolg gelten n … Anzahl der im Rahmen des Experiments gezogenen Elemente x … Anzahl der Treffer |
nur k Elemente (Stichprobe) werden verwendet | egal
(a,b)=(b,a) |
ohne |
Anzahl: Wahrscheinlichkeit: |
|
Kombination Urnenmodel: Ziehen von nur k aus n Kugeln, von denen manche mehrfach vorkommen können, ohne Beachtung der Reihenfolge |
nur k Elemente (Stichprobe) werden verwendet | egal
(a,b)=(b,a) |
mit | \(\dfrac{{\left( {n + k - 1} \right)!}}{{k! \cdot \left( {n - 1} \right)!}} = \left( {\begin{array}{*{20}{c}} {n + k - 1}\\ k \end{array}} \right)\) |
Werbung
Schon den nächsten Urlaub im Süden geplant?
Schnell noch kostenlos auf die Prüfung vorbereiten!
Nach der Prüfung den Erfolg genießen...
Bild
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\)