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)\) |