Kombinatorik vertiefen — Permutationen, Variationen und Kombinationen

Einführung

Wie viele verschiedene Passwörter aus 6 Buchstaben gibt es? Wie viele Möglichkeiten hat man beim Lotto? Wie viele Handshakes gibt es bei 10 Personen? Alle diese Fragen haben etwas gemeinsam — sie fragen, wie viele Möglichkeiten es gibt, Objekte auszuwählen oder anzuordnen.

Die Kombinatorik liefert systematische Antworten. Statt alle Möglichkeiten aufzuzählen, nutzt man Formeln — sobald man verstanden hat, welcher der vier Grundtypen vorliegt.

Grundidee

Die entscheidenden zwei Fragen:

1. Spielt die Reihenfolge eine Rolle? (geordnet vs. ungeordnet)
2. Darf dasselbe Element mehrfach vorkommen? (mit vs. ohne Wiederholung)

Das ergibt vier Fälle. Alle Kombinatorikaufgaben lassen sich in einen dieser Fälle einsortieren — dann braucht man nur noch die passende Formel.

Erklärung

Die vier Grundtypen

Wir wählen $k$ Objekte aus $n$ Objekten aus:

Jede Formel hat eine eigene Bedeutung und eigene Anwendungsgebiete.

Fall 1: Geordnet mit Wiederholung — $n^k$

Bei jeder der $k$ Stellen gibt es $n$ Möglichkeiten, unabhängig von den anderen.

Formel: $N = n^k$

Beispiel — PIN: Eine vierstellige PIN aus den Ziffern 0–9 (Wiederholung erlaubt, Reihenfolge wichtig): $N = 10^4 = 10000 \text{ mögliche PINs}$

Beispiel — Passwort: 6 Zeichen aus 26 Kleinbuchstaben: $N = 26^6 = 308.915.776$

Fall 2: Geordnet ohne Wiederholung — $\frac{n!}{(n-k)!}$

Jedes Element darf nur einmal verwendet werden. Die erste Stelle hat $n$ Möglichkeiten, die zweite $n-1$, usw.

Formel: $N = n \cdot (n-1) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n-k)!}$

Für $k = n$ (alle Elemente anordnen): $N = n!$ — das ist die klassische Permutation.

Beispiel — Podium: Aus 8 Läufern werden die Plätze 1, 2, 3 vergeben: $N = \frac{8!}{5!} = 8 \cdot 7 \cdot 6 = 336$

Beispiel — Anagramme: Wie viele Anordnungen hat das Wort MATHE (5 verschiedene Buchstaben)? $N = 5! = 120$

Fall 3: Ungeordnet ohne Wiederholung — $\binom{n}{k}$

Die Reihenfolge spielt keine Rolle, jedes Element höchstens einmal. Das ist der Binomialkoeffizient:

$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$

Beispiel — Lotto 6 aus 49: $\binom{49}{6} = \frac{49!}{6! \cdot 43!} = \frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{6!} = \frac{10.068.347.520}{720} = 13.983.816$

Die Gewinnwahrscheinlichkeit beträgt also $\frac{1}{13.983.816} \approx 0{,}000007\,\%$.

Beispiel — Ausschuss: Aus 10 Personen soll ein 3-köpfiger Ausschuss gewählt werden: $\binom{10}{3} = \frac{10 \cdot 9 \cdot 8}{3!} = \frac{720}{6} = 120$

Fall 4: Ungeordnet mit Wiederholung — $\binom{n+k-1}{k}$

Objekte dürfen mehrfach gewählt werden, aber die Reihenfolge ist irrelevant. Dieser Fall tritt seltener auf.

Formel: $\binom{n+k-1}{k}$

Beispiel — Eiskugeln: Eine Eisdiele hat 5 Sorten. Du wählst 3 Kugeln aus (Wiederholung erlaubt, Reihenfolge egal): $\binom{5+3-1}{3} = \binom{7}{3} = 35 \text{ Möglichkeiten}$

Übersichtstabelle mit Beispielen

Zusammengesetzte Aufgaben

Viele Abi-Aufgaben kombinieren mehrere Schritte. Typisch: „Wähle zuerst 2 aus Gruppe A, dann 3 aus Gruppe B.” Die Gesamtzahl ist dann das Produkt der Einzelfälle.

Beispiel — Kartenspiel: Aus 32 Karten (Skat) wird eine Hand von 10 Karten verteilt. Wie viele Hände enthalten genau 3 Buben (es gibt 4 Buben)?

• 3 der 4 Buben wählen: $\binom{4}{3} = 4$
• 7 der restlichen 28 Karten wählen: $\binom{28}{7} = 1184040$
• Gesamt: $4 \cdot 1184040 = 4736160$

Beispiel aus dem Alltag

Sicherheitscodes: Ein Fahrradschloss hat 4 Stellen, jede mit den Ziffern 0–9. Das sind $10^4 = 10000$ Codes — geordnet mit Wiederholung.

Wäre das Schloss stattdessen ein Buchstabencode mit 4 verschiedenen Buchstaben aus dem Alphabet (26): $\frac{26!}{22!} = 26 \cdot 25 \cdot 24 \cdot 23 = 358800$ Möglichkeiten — geordnet ohne Wiederholung.

Betriebsrat: In einem Betrieb mit 80 Mitarbeitern soll ein 5-köpfiger Betriebsrat gewählt werden. Die Anzahl der möglichen Zusammensetzungen: $\binom{80}{5} = 24.040.016$ — geordnete Auswahl spielt keine Rolle (ungeordnet ohne Wiederholung).

Anwendung

Aufgabe 1: Wie viele verschiedene Anordnungen hat das Wort MATHEMATIK (10 Buchstaben, davon M 2×, A 2×, T 2×)?

Lösung: Bei Wiederholung von Buchstaben: $\frac{10!}{2!\cdot2!\cdot2!} = \frac{3628800}{8} = 453600$.

Aufgabe 2: Aus 6 Männern und 4 Frauen soll ein Team von 3 Männern und 2 Frauen gebildet werden. Wie viele Teams gibt es?

Lösung: $\binom{6}{3} \cdot \binom{4}{2} = 20 \cdot 6 = 120$.

Aufgabe 3: Ein Passwort besteht aus genau 2 Großbuchstaben (A–Z) gefolgt von 4 Ziffern (0–9), Wiederholung erlaubt. Wie viele Passwörter gibt es?

Lösung: $26^2 \cdot 10^4 = 676 \cdot 10000 = 6.760.000$.

Typische Fehler

Zusammenfassung

Merke dir:

• Die zwei Schlüsselfragen: geordnet oder ungeordnet? Mit oder ohne Wiederholung?
• Geordnet mit Wiederholung: $n^k$ — jede Stelle unabhängig wählen (Passwörter, PINs)
• Geordnet ohne Wiederholung: $\frac{n!}{(n-k)!}$ — Permutation (Platzierungen, Anagramme)
• Ungeordnet ohne Wiederholung: $\binom{n}{k}$ — der Binomialkoeffizient (Lotto, Ausschüsse)
• Ungeordnet mit Wiederholung: $\binom{n+k-1}{k}$ — seltenster Fall (Eissorten)
• Zusammengesetzte Aufgaben: Teilschritte multiplizieren

Quiz

Frage 1: In welchen der vier Typen gehört die folgende Aufgabe? „Aus 15 Fragen wählt ein Schüler 5 für seine Prüfungsvorbereitung aus. Die Reihenfolge spielt keine Rolle.”

Frage 2: Wie viele sechsstellige Binärcodes (nur 0 und 1) gibt es?

Frage 3: Warum gilt $\binom{n}{0} = 1$ und $\binom{n}{n} = 1$?

Frage 4: Ein Schloss hat drei Räder, jedes mit den Ziffern 1–8. Wie viele Codes gibt es? Wie viele, wenn alle drei Ziffern verschieden sein müssen?