Kombinatorik

Einführung

Wie viele verschiedene Passwörter kann man aus 8 Zeichen bilden? Wie viele Möglichkeiten gibt es beim Lotto? Kombinatorik beantwortet die Frage „Wie viele Möglichkeiten gibt es?” — und diese Frage ist der Schlüssel zur Wahrscheinlichkeitsrechnung. Denn oft berechnet man Wahrscheinlichkeiten, indem man günstige und mögliche Fälle zählt.

Grundidee

Stell dir vor, du stehst morgens vor deinem Kleiderschrank. Du hast:

5 T-Shirts (weiß, schwarz, blau, rot, grün)
4 Hosen (Jeans, Chino, Jogger, Shorts)
3 Paar Schuhe (Sneaker, Boots, Sandalen)

Wie viele verschiedene Outfits kannst du zusammenstellen?

Für jedes T-Shirt hast du 4 Hosen-Optionen. Für jede T-Shirt-Hosen-Kombination 3 Schuhe. Also:

$5 \times 4 \times 3 = 60 \text{ verschiedene Outfits}$

Das ist das Multiplikationsprinzip — und es steckt hinter jeder Zählformel der Kombinatorik. Wenn du bei jedem Schritt unabhängig wählen kannst, multiplizierst du die Anzahlen.

Jetzt wird es spannend: Du hast 3 Buchstaben — A, B, C. Wie viele Reihenfolgen gibt es? Du zählst: ABC, ACB, BAC, BCA, CAB, CBA — genau 6. Bei 4 Buchstaben wären es schon 24, bei 10 Buchstaben über 3 Millionen. Die Zahlen explodieren! Zum Glück gibt es Formeln, die das Zählen ersetzen. Die Kunst besteht darin, die richtige Formel für das richtige Problem zu wählen.

Erklärung

Fakultät

Die Fakultät $n!$ gibt an, wie viele Möglichkeiten es gibt, $n$ verschiedene Objekte in eine Reihenfolge zu bringen:

In Worten: „Für den ersten Platz hast du $n$ Möglichkeiten, für den zweiten noch $n-1$ , dann $n-2$ , … bis nur noch 1 übrig bleibt.”

$n! = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1$

$n$	$n!$
$0$	$1$ (per Definition)
$1$	$1$
$3$	$6$
$5$	$120$
$10$	$3\,628\,800$

Warum ist 0! = 1?

Das irritiert viele, ist aber logisch: Es gibt genau eine Möglichkeit, null Objekte anzuordnen — nämlich gar nichts zu tun. Außerdem brauchen wir $0! = 1$ , damit Formeln wie $\binom{n}{0} = 1$ und $\binom{n}{n} = 1$ funktionieren.

Die vier Zählprinzipien

Die Wahl der richtigen Formel hängt von zwei Fragen ab:

Ist die Reihenfolge wichtig? (Ja → Variation/Permutation, Nein → Kombination)
Dürfen Elemente wiederholt werden? (Ja → mit Wiederholung, Nein → ohne)

	Reihenfolge wichtig	Reihenfolge egal
Mit Wiederholung	Variation m. W.: $n^k$	Kombination m. W.: $\binom{n+k-1}{k}$
Ohne Wiederholung	Variation o. W.: $\frac{n!}{(n-k)!}$	Kombination o. W.: $\binom{n}{k}$

Dabei: $n$ = Anzahl der verfügbaren Elemente, $k$ = Anzahl der ausgewählten Elemente.

Entscheidungsbaum: Die richtige Formel finden

Bevor du rechnest, geh diesen Baum durch:

Werden ALLE n Objekte angeordnet?
│
├── JA ──────────────────────────→  Permutation: n!
│
└── NEIN: k aus n werden gewählt
    │
    ├── Reihenfolge WICHTIG?
    │   │
    │   ├── Wiederholung erlaubt?
    │   │   ├── JA ──────────────→  n^k
    │   │   └── NEIN ────────────→  n! / (n-k)!
    │   │
    │
    └── Reihenfolge EGAL?
        │
        └── Wiederholung erlaubt?
            ├── JA ──────────────→  (n+k-1) über k
            └── NEIN ────────────→  (n über k)

Permutation

Eine Permutation ist die Anordnung aller $n$ Elemente — ein Spezialfall der Variation mit $k = n$ :

$P(n) = n!$

Beispiel: 5 Personen setzen sich auf 5 Stühle → $5! = 120$ Möglichkeiten.

Variation mit Wiederholung

Aus $n$ Elementen werden $k$ ausgewählt, Reihenfolge zählt, Wiederholung erlaubt:

In Worten: „Bei jedem der $k$ Schritte habe ich wieder alle $n$ Optionen — also $n \times n \times \ldots$ ( $k$ -mal).”

$V_w(n, k) = n^k$

Beispiel: 4-stellige PIN aus Ziffern 0–9 → $10^4 = 10\,000$ Möglichkeiten.

Variation ohne Wiederholung

Wie oben, aber jedes Element darf nur einmal vorkommen:

In Worten: „Beim ersten Schritt $n$ Optionen, beim zweiten nur noch $n-1$ , usw.”

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

Beispiel: 3 Medaillen (Gold, Silber, Bronze) an 8 Sportler → $\frac{8!}{5!} = 8 \cdot 7 \cdot 6 = 336$ .

Kombination ohne Wiederholung (Binomialkoeffizient)

Die Reihenfolge spielt keine Rolle, jedes Element wird höchstens einmal gewählt:

In Worten: „Erst wie Variation ohne Wiederholung wählen, dann durch $k!$ teilen, weil uns die Reihenfolge egal ist.”

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

Der Binomialkoeffizient — die wichtigste Formel der Kombinatorik

Gesprochen: „ $n$ über $k$ ”
Zählt: Wie viele Möglichkeiten gibt es, $k$ Dinge aus $n$ auszuwählen, wenn die Reihenfolge egal ist?
Symmetrie: $\binom{n}{k} = \binom{n}{n-k}$ — 3 auswählen = 3 weglassen
Taucht überall auf: Lotto, Komitees, Binomialverteilung im Abi

Beispiel: Aus 10 Schülern ein 3er-Komitee wählen → $\binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120$ .

Häufiger Irrtum

Irrtum: „Bei $\binom{n}{k}$ muss ich nur $n \cdot (n-1) \cdot \ldots \cdot (n-k+1)$ rechnen.”

Richtig ist: Das ist erst die Hälfte! Du musst noch durch $k!$ teilen, um die doppelt gezählten Reihenfolgen zu entfernen. $\binom{10}{3} = \frac{10 \cdot 9 \cdot 8}{3!} = \frac{720}{6} = 120$ , nicht $720$ .

Beispiel aus dem Alltag

Beispiel 1: Zahlenschloss

Ein Zahlenschloss hat 4 Ringe mit jeweils den Ziffern 0–9. Reihenfolge ist wichtig (1234 ≠ 4321), und jede Ziffer darf mehrfach vorkommen.

Wenn jede Ziffer nur einmal vorkommen darf:

Beispiel 2: Lotto „6 aus 49”

Beim Lotto werden 6 Zahlen aus 49 gezogen. Die Reihenfolge spielt keine Rolle, jede Zahl kann nur einmal gezogen werden.

$\binom{49}{6} = \frac{49!}{6! \cdot 43!} = \frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 13\,983\,816$

Die Chance auf 6 Richtige: $P = \frac{1}{13\,983\,816} \approx 0{,}0000000715$ — etwa 1 zu 14 Millionen.

Zum Vergleich

Die Wahrscheinlichkeit, vom Blitz getroffen zu werden, liegt bei etwa 1 zu 1 Million pro Jahr. Du wirst also 14-mal wahrscheinlicher vom Blitz getroffen als dass du im Lotto gewinnst. Trotzdem spielen Millionen Menschen jede Woche.

Anwendung

Aufgabe 1: Sitzordnung

8 Schüler sitzen in einer Reihe. Wie viele verschiedene Sitzordnungen gibt es?

$\boxed{8! = 40\,320}$

Aufgabe 2: Passwort-Möglichkeiten

Ein Passwort besteht aus 6 Kleinbuchstaben (26 Zeichen), Wiederholung erlaubt.

$26^6 = 308\,915\,776 \approx 309 \text{ Millionen}$

Aufgabe 3: Komitee-Wahl

Aus einer Klasse mit 25 Schülern soll ein 4er-Komitee gewählt werden. Reihenfolge egal.

$\binom{25}{4} = \frac{25 \cdot 24 \cdot 23 \cdot 22}{4 \cdot 3 \cdot 2 \cdot 1} = \frac{303\,600}{24} = \boxed{12\,650}$

Aufgabe 4: Wahrscheinlichkeit beim Lotto

Wie wahrscheinlich sind genau 3 Richtige beim Lotto „6 aus 49”?

Es gibt $\binom{6}{3}$ Möglichkeiten, 3 der 6 richtigen Zahlen zu treffen, und $\binom{43}{3}$ Möglichkeiten, die restlichen 3 aus den 43 falschen zu wählen:

$P(3 \text{ Richtige}) = \frac{\binom{6}{3} \cdot \binom{43}{3}}{\binom{49}{6}} = \frac{20 \cdot 12\,341}{13\,983\,816} = \frac{246\,820}{13\,983\,816} \approx \boxed{0{,}0177 \approx 1{,}77\,\%}$

Typische Fehler

Häufiger Irrtum

Irrtum: „3 Personen für ein Komitee wählen und 3 Plätze vergeben (1., 2., 3.) — das ist doch dasselbe?”

Richtig ist: Nein! Beim Komitee ist die Reihenfolge egal → Kombination. Bei Plätzen (Gold, Silber, Bronze) ist die Reihenfolge wichtig → Variation. Frage dich: „Ändert sich etwas, wenn ich die Reihenfolge vertausche?” Wenn ja → Variation. Wenn nein → Kombination.

Binomialkoeffizient falsch berechnen: $\binom{n}{k}$ durch $k!$ teilen nicht vergessen! Häufiger Fehler: nur $n \cdot (n-1) \cdot \ldots$ ohne die Division.
$0! = 1$ vergessen: Per Definition gilt $0! = 1$ . Das ist wichtig, z. B. bei $\binom{n}{0} = 1$ oder $\binom{n}{n} = 1$ .
Mit/ohne Wiederholung verwechseln: Bei einer PIN darf die gleiche Ziffer mehrfach vorkommen → mit Wiederholung. Bei Lotto wird jede Zahl nur einmal gezogen → ohne Wiederholung.
Zu schnell die Formel anwenden: Erst die Situation analysieren, dann die Formel wählen. Den Entscheidungsbaum (Reihenfolge? Wiederholung?) durchgehen.

Zusammenfassung

Die Fakultät $n!$ zählt die Anordnungen von $n$ Objekten.
Variationen (Reihenfolge wichtig): mit Wiederholung $n^k$ , ohne Wiederholung $\frac{n!}{(n-k)!}$ .
Kombinationen (Reihenfolge egal): der Binomialkoeffizient $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ .
Die Entscheidung hängt an zwei Fragen: Reihenfolge wichtig? Wiederholung erlaubt?
Der Binomialkoeffizient ist die Grundlage für die Binomialverteilung im Abi.
Kombinatorik + Laplace-Formel = Wahrscheinlichkeiten durch Abzählen.

Quiz

Frage 1: Ein Code besteht aus 3 verschiedenen Buchstaben (A–Z). Welche Formel ist richtig?

Frage 2: Warum ist $\binom{5}{2} = \binom{5}{3}$ ?

Frage 3: 12 Mannschaften spielen ein Turnier. Wie viele verschiedene Podestplätze (1., 2., 3.) sind möglich?

Frage 4: Ein Gremium aus 3 Personen soll aus 8 Kandidaten gewählt werden. Wie viele Möglichkeiten gibt es?

Lernziele