Zählprinzip
Das Zählprinzip (Produktregel der Kombinatorik) ist die Basis: Wenn ein Vorgang aus mehreren unabhängigen Schritten besteht, multipliziert man die Anzahl der Möglichkeiten pro Schritt.
\(n_i\) = Anzahl der Möglichkeiten im \(i\)-ten Schritt
3 Hosen, 5 T-Shirts, 2 Paar Schuhe → \(3 \cdot 5 \cdot 2 = 30\) verschiedene Outfits
Fakultät
Die Fakultät \(n!\) gibt die Anzahl der Möglichkeiten an, \(n\) verschiedene Objekte anzuordnen:
Sonderfall: \(0! = 1\) (per Definition)
\(5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120\)
\(3! = 3 \cdot 2 \cdot 1 = 6\)
\(1! = 1\), \(0! = 1\)
Permutationen
Eine Permutation ist eine Anordnung aller Elemente in einer bestimmten Reihenfolge.
Anzahl der Anordnungen von \(n\) verschiedenen Elementen
1. Stuhl: 4 Möglichkeiten, 2. Stuhl: 3, 3. Stuhl: 2, 4. Stuhl: 1
\(P(4) = 4! = 24\) verschiedene Sitzordnungen
Wenn einige Elemente identisch sind, reduziert sich die Anzahl:
\(k_i\) = Häufigkeit des \(i\)-ten gleichen Elements
6 Buchstaben: A kommt 3-mal vor, N kommt 2-mal vor, S kommt 1-mal vor.
\(P(6; 3, 2, 1) = \frac{6!}{3! \cdot 2! \cdot 1!} = \frac{720}{6 \cdot 2 \cdot 1} = \frac{720}{12} = 60\)
Kombinationen und Binomialkoeffizient
Bei einer Kombination wählt man \(k\) Elemente aus \(n\) aus, wobei die Reihenfolge keine Rolle spielt.
Lies: „n über k" – Anzahl der Möglichkeiten, k aus n auszuwählen
\(\binom{5}{3} = \frac{5!}{3! \cdot 2!} = \frac{120}{6 \cdot 2} = \frac{120}{12} = 10\)
Es gibt 10 verschiedene Komitees.
Symmetrie: \(\binom{n}{k} = \binom{n}{n-k}\). Zum Beispiel: \(\binom{5}{3} = \binom{5}{2} = 10\). Das Auswählen von 3 ist gleichwertig mit dem Weglassen von 2.
Wichtige Spezialfälle
- \(\binom{n}{0} = 1\) – es gibt genau eine Möglichkeit, nichts auszuwählen
- \(\binom{n}{1} = n\) – es gibt \(n\) Möglichkeiten, ein Element auszuwählen
- \(\binom{n}{n} = 1\) – es gibt genau eine Möglichkeit, alles auszuwählen
Übersicht der Zählformeln
| Reihenfolge wichtig | Reihenfolge egal | |
|---|---|---|
| Ohne Wiederholung | \(\frac{n!}{(n-k)!}\) (Variation) | \(\binom{n}{k}\) (Kombination) |
| Mit Wiederholung | \(n^k\) (Variation m. Wdh.) | \(\binom{n+k-1}{k}\) (Komb. m. Wdh.) |
6 Zahlen werden aus 45 gezogen (ohne Zurücklegen, Reihenfolge egal):
\(\binom{45}{6} = \frac{45!}{6! \cdot 39!} = \frac{45 \cdot 44 \cdot 43 \cdot 42 \cdot 41 \cdot 40}{6!} = \frac{45 \cdot 44 \cdot 43 \cdot 42 \cdot 41 \cdot 40}{720} = 8\,145\,060\)
Die Wahrscheinlichkeit eines Sechsers: \(P = \frac{1}{8\,145\,060} \approx 0{,}0000123\%\)
Übungen
Berechne \(6!\).
Berechne \(\binom{6}{2}\).
Auf wie viele Arten können 5 Schüler in einer Reihe aufgestellt werden?
Wie viele verschiedene Anordnungen der Buchstaben des Wortes MISSISSIPPI gibt es?
Aus 10 Bewerbern werden 4 für ein Projekt ausgewählt (Reihenfolge egal). Wie viele Möglichkeiten gibt es?