Grundsatz: Kombinatorik zählt, auf wie viele Arten sich Elemente anordnen oder auswählen lassen. Zentrale Frage: mit oder ohne Wiederholung; mit oder ohne Beachtung der Reihenfolge.
Vier Grundfälle (n Elemente, k Auswahl):
| Mit Reihenfolge | Ohne Reihenfolge | |
|---|---|---|
| Ohne Wiederholung | $\frac{n!}{(n-k)!}$ (Variation) | $\binom{n}{k}$ (Kombination) |
| Mit Wiederholung | $n^k$ | $\binom{n+k-1}{k}$ |
Binomialkoeffizient:
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
Permutationen (Anordnungen von n Elementen): $n!$. Mit gleichen Elementen ($n_1$ vom Typ 1, $n_2$ vom Typ 2, …): $\frac{n!}{n_1!, n_2!, \cdots}$.
Zirkuläre Permutationen: Werden $n$ verschiedene Objekte im Kreis angeordnet, so gilt:
$$(n-1)!$$
Die Division durch $n$ trägt dem Umstand Rechnung, dass Drehungen derselben Anordnung identisch sind.
Beispiel: 5 Personen an einem runden Tisch: $(5-1)! = 24$ Anordnungen.
Beispiel — Variation
Wie viele 3-stellige Zahlen aus den Ziffern 1–9 ohne Wiederholung? $9 \cdot 8 \cdot 7 = 504$.
Beispiel — Kombination
Lotterie mit 6 aus 45 Zahlen (Rechenbeispiel): $\binom{45}{6} = 8'145'060$.
Beispiel — Kombination mit Wiederholung
Eine Eisdiele bietet 5 Geschmackssorten an. Man wählt 3 Kugeln (Reihenfolge egal, Wiederholungen erlaubt). Wie viele Möglichkeiten gibt es?
$$\binom{5+3-1}{3} = \binom{7}{3} = \frac{7!}{3!,4!} = 35$$
Beispiel — Permutation mit gleichen Buchstaben
„MISSISSIPPI" (11 Buchstaben, 1 M, 4 I, 4 S, 2 P): $\frac{11!}{1!,4!,4!,2!} = 34'650$.
Beispiel — Mit Wiederholung, mit Reihenfolge
4-stelliger PIN (Ziffern 0–9): $10^4 = 10'000$.
Zählprinzipien und Standardtricks
Summenregel und Produktregel: Kann man entweder aus Gruppe 1 oder aus Gruppe 2 wählen (sich ausschliessende Fälle), addiert man die Anzahlen. Muss man eine Wahl nach der anderen treffen («je eines aus jeder Gruppe», «erst ... dann ...»), multipliziert man die Anzahlen der Möglichkeiten. Hängt die zweite Wahl von der ersten ab (ohne Wiederholung), zählt man die verbleibenden Möglichkeiten.
Zählen über das Komplement: «Mindestens ein ...» ist oft einfacher als Gesamtzahl minus «keines». Auch «nicht benachbart» ist Gesamtzahl minus «benachbart».
Block-Methode
Sollen Elemente beieinander stehen, fasst man sie zu einem Block zusammen, ordnet die Blöcke an und multipliziert mit den Anordnungen innerhalb des Blocks. Stehen zwei Personen nebeneinander: $2\cdot(n-1)!$ Anordnungen von $n$ Personen in einer Reihe.
Bedingungen an Positionen: Zuerst die Plätze mit Vorgaben besetzen (zum Beispiel erste Ziffer nicht $0$, Position festgelegt), dann den Rest frei anordnen.
Teilmengen
Eine $n$-elementige Menge hat $2^n$ Teilmengen (jedes Element ist drin oder nicht), davon $\binom nk$ mit genau $k$ Elementen. Es gilt $\binom nk=\binom n{n-k}$ und $\binom nk+\binom n{k+1}=\binom{n+1}{k+1}$.
Aufteilen auf Gruppen oder Zimmer
Gruppen mit festgelegten Namen oder Grössen füllt man nacheinander mit Binomialkoeffizienten. Zimmer unterschiedlicher Grösse für $n$ Personen: $\binom{n}{k_1}\binom{n-k_1}{k_2}\cdots$. Sind die Gruppen untereinander nicht unterscheidbar und gleich gross, teilt man durch die Anzahl der Vertauschungen der Gruppen. Verschiedene Objekte auf nummerierte Fächer verteilen (jedes Objekt wählt sein Fach): $f^n$ bei $f$ Fächern und $n$ Objekten ohne Kapazitätsgrenze.
Gleiche Objekte
Sind Kugeln einer Farbe nicht unterscheidbar, zählt man nur Anordnungen der Farben (Permutation mit gleichen Elementen). Hat jede Kugel eine eigene Nummer oder einen eigenen Buchstaben, sind alle verschieden, und man rechnet $n!$. Gleiche Walzen oder gleiche Würfel, bei denen es nur auf die Symbole ankommt (nicht auf die Reihenfolge), entsprechen der Kombination mit Wiederholung; bei unterscheidbaren Walzen mit Reihenfolge gilt $n^k$.
Wahrscheinlichkeiten mit Kombinatorik: $P=\dfrac{\text{günstige}}{\text{mögliche}}$, beide Anzahlen gleich gezählt (beide mit oder beide ohne Reihenfolge).
Beispiel — Summen- und Produktregel
Kiosk mit $5$ Sandwiches, $5$ Salaten, $10$ Getränken. Genau ein Artikel: $5+5+10=20$. Je eines aus jeder Gruppe: $5\cdot5\cdot10=250$.
Beispiel — Block und Komplement
$5$ Personen in einer Reihe, $A$ und $B$ stehen nebeneinander: $2\cdot4!=48$. Nicht nebeneinander: $5!-48=120-48=72$.
Beispiel — Aufteilen
$6$ Kinder auf ein Zweier- und ein Viererzimmer: $\binom62=15$. Auf drei benannte Zweierzimmer: $\binom62\binom42\binom22=15\cdot6\cdot1=90$; sind die drei Zimmer nicht unterscheidbar, ist es $\frac{90}{3!}=15$.
Beispiel — Mindestens und Teilmengen
Fünf Münzwürfe mit mindestens einem Kopf: $2^5-1=31$ Folgen. Eine Pizza mit beliebiger Auswahl aus $5$ Belägen (auch ohne Belag): $2^5=32$ Möglichkeiten.
Häufige Fehler
- Reihenfolge ignoriert/eingeführt: „Wie viele Möglichkeiten, eine Hand von 5 Karten zu erhalten?" → $\binom{52}{5}$ ohne Reihenfolge. „Auf wie viele Arten 5 Karten in Reihe legen?" → $52 \cdot 51 \cdot 50 \cdot 49 \cdot 48$.
- Binomialkoeffizient mit Variation verwechselt: $\binom{n}{k}$ = Anzahl $k$-elementiger Teilmengen; Variation = geordnete Anordnung.
- $0! = 1$ vergessen: Per Konvention. So macht $\binom{n}{0}=1$ Sinn.
- Zirkuläre Permutation vergessen: Am runden Tisch gilt $(n-1)!$, nicht $n!$.
- Kombination mit Wiederholung: $\binom{n+k-1}{k}$, nicht $\binom{n}{k}$.
Weitere Zählmuster
Nicht benachbart (Lückenmethode): Erst die übrigen Objekte anordnen, dann die Plätze für die «verbotenen Nachbarn» in die Lücken legen. Bei $m$ übrigen Objekten gibt es $m+1$ Lücken (Zwischenräume und beide Ränder); davon wählt man so viele, wie Objekte der betroffenen Sorte da sind, jeweils eine pro Lücke: Binomialkoeffizient $\binom{m+1}{\text{Anzahl}}$.
Aufsteigend sortiert
Ist die Reihenfolge der Beschriftungen vorgeschrieben (zum Beispiel Buchstaben von links nach rechts alphabetisch, gleiche Beschriftung in beliebiger Folge), so ist nur noch bei jedem doppelt vorkommenden Buchstaben offen, welcher der beiden Gegenstände zuerst steht. Bei $k$ Paaren sind das $2^k$ Anordnungen.
Nachbarn verschieden
Soll bei einer Reihe aus $m$ Plätzen mit $n$ Farben nie dieselbe Farbe zweimal nebeneinander stehen, hat der erste Platz $n$ und jeder weitere $n-1$ Möglichkeiten:
$$n\cdot(n-1)^{m-1}$$
Mindestens jede Sorte einmal
Werden $n$ Plätze mit $k$ Farben gefärbt und soll jede Farbe vorkommen, zieht man von allen Färbungen die ab, bei denen eine Farbe fehlt, und addiert zu viel Abgezogenes wieder dazu (Inklusion-Exklusion):
$$k^n-\binom k1(k-1)^n+\binom k2(k-2)^n-\cdots$$
Für $k=3$ Farben: $3^n-3\cdot2^n+3$. Dasselbe Prinzip zählt auch Zuordnungen, bei denen kein Fach leer bleiben darf: Man zählt alle Zuordnungen und zieht die mit $j$ leeren Fächern ab, mit dem Faktor $(-1)^j\binom kj$.
Gleiche Objekte auf unterscheidbare Fächer
Die Anzahl der Verteilungen von $n$ nicht unterscheidbaren Objekten auf $k$ unterscheidbare Fächer (oder der Lösungen von $x_1+\dots+x_k=n$ mit ganzen Zahlen $x_i\ge0$) ist eine Kombination mit Wiederholung:
$$\binom{n+k-1}{k-1}=\binom{n+k-1}{n}$$
Muss jedes Fach mindestens ein Objekt erhalten, legt man zuerst in jedes Fach eines und verteilt die restlichen $n-k$ Objekte frei.
Zwei verschiedene Gruppen
Zweierauswahlen aus Gruppen der Grössen $a$, $b$, $c$, deren Mitglieder aus verschiedenen Gruppen stammen, zählt man als Summe der Produkte $ab+ac+bc$ oder über das Komplement (alle Paare minus die Paare innerhalb einer Gruppe). Höchstens eine Person pro Gruppe: Zuerst wählt man die Gruppen, aus denen jemand kommt, dann eine Person aus jeder gewählten Gruppe.
Auswählen und anordnen: Wählt man zuerst eine Teilmenge und ordnet sie dann an, multipliziert man die Zahl der Auswahlen mit der Zahl der Anordnungen der gewählten Elemente.
Zwei Arten gleicher Objekte auf Felder legen
Man wählt zuerst die Felder der ersten Art, dann aus den übrigen Feldern die der zweiten Art: $\binom{N}{a}\binom{N-a}{b}$.
Gruppen mit Sprecher oder Delegation
Sind die Gruppen schon festgelegt, wählt man aus jeder Gruppe unabhängig (Produktregel). Ein Sprecher aus jeder Gruppe der Grössen $g_1,g_2,\dots$ ergibt $g_1\cdot g_2\cdots$; zwei Personen aus jeder Gruppe ergeben $\binom{g_1}{2}\binom{g_2}{2}\cdots$. Die Aufteilung von $n$ Personen auf feste, unterscheidbare Gruppen der Grössen $k_1,k_2,\dots,k_r$ (mit $k_1+\dots+k_r=n$) heisst Multinomialkoeffizient:
$$\frac{n!}{k_1!,k_2!\cdots k_r!}=\binom n{k_1}\binom{n-k_1}{k_2}\cdots$$
Zwei gleich grosse, nicht unterscheidbare Gruppen vertauscht man nicht mehr: Man teilt durch die Zahl ihrer Vertauschungen.
Zufällige Einteilung in zwei Gruppen
Zufällige Einteilung in zwei Gruppen (günstige durch mögliche Fälle): Die Wahrscheinlichkeit, dass die erste Gruppe von $n$ aus $N$ Personen genau $m$ der $M$ Frauen enthält, ist
$$P=\frac{\binom Mm\binom{N-M}{n-m}}{\binom Nn}$$
Gleich wahrscheinliche Ergebnisse
Die Formel «günstig durch möglich» gilt nur, wenn alle gezählten Ergebnisse gleich wahrscheinlich sind. Bei unterscheidbaren Würfeln oder Walzen sind das die geordneten Ergebnisse, nicht die ungeordneten Kombinationen. Ein Passwort, das unter $N$ gleich wahrscheinlichen Möglichkeiten zufällig gesucht wird, wird mit der Wahrscheinlichkeit $\frac1N$ genau beim $k$-ten Versuch gefunden, für jedes $k\le N$.
Fakultäten umformen
$n!=n\cdot(n-1)!$, also zum Beispiel $99!=\dfrac{100!}{100}$. Es gilt $\binom{2m}{m}=\dfrac{(2m)!}{(m!)^2}$.
Beispiel — Lückenmethode
Eine Dose enthält $3$ rote, $3$ weisse und $2$ gelbe Kugeln (gleichfarbige nicht unterscheidbar). Keine zwei roten sollen benachbart sein. Die $5$ übrigen Kugeln lassen sich auf $\frac{5!}{3!,2!}=10$ Arten anordnen. Dazu gibt es $6$ Lücken, in die $3$ rote Kugeln kommen: $\binom63=20$. Zusammen $10\cdot20=200$.
Beispiel — Nachbarn verschieden
Eine Fahne aus $5$ waagrechten Streifen in $8$ Farben, benachbarte Streifen verschieden: $8\cdot7^4=19'208$. Eine Lichterkette mit $10$ Lampen in $6$ Farben: $6\cdot5^9=11'718'750$.
Beispiel — Jede Farbe mindestens einmal
Sechs Felder werden mit vier Stiften gefärbt, jeder Stift wird mindestens einmal benutzt: $4^6-4\cdot3^6+6\cdot2^6-4=4096-2916+384-4=1560$.
Beispiel — Gleiche Objekte auf Fächer
Sechs nicht unterscheidbare Pfeile treffen drei Felder: $\binom{8}{6}=28$ Wurfbilder. Neun Klötzchen, von denen nur gezählt wird, wie oft jede von drei Flächenarten vorkommt: $\binom{11}{2}=55$. Zwölf Kontrollfahrten auf fünf Linien, jede Linie mindestens einmal: $\binom{11}{4}=330$.
Beispiel — Gruppen, Sprecher, Delegation
$15$ Personen auf Zelte mit $6$, $5$ und $4$ Plätzen: $\frac{15!}{6!,5!,4!}=630'630$. Ein Sprecher pro Zelt: $6\cdot5\cdot4=120$. Zwei Personen pro Zelt: $\binom62\binom52\binom42=15\cdot10\cdot6=900$.
Beispiel — Verschiedene Gruppen und Komitee
Gruppen mit $4$, $6$ und $9$ Personen, Zweierauswahlen aus verschiedenen Gruppen: $4\cdot6+4\cdot9+6\cdot9=114$. Vier Gruppen mit $15$, $11$, $13$ und $15$ Personen, ein Dreierkomitee mit höchstens einer Person pro Gruppe: $15\cdot11\cdot13+15\cdot11\cdot15+15\cdot13\cdot15+11\cdot13\cdot15=9'690$.
Beispiel — Auswählen und anordnen
Aus den Buchstaben von ZUERICH (Vokale U, E, I; Konsonanten Z, R, C, H) werden $1$ Vokal und $2$ Konsonanten gezogen und in der Zugreihenfolge hingelegt: $3\cdot\binom42\cdot3!=3\cdot6\cdot6=108$.
Beispiel — Zwei Zeichen mit festen Häufigkeiten
Ein Code aus $5$ Zeichen (Vorrat $20$ Zeichen), in dem ein Zeichen dreimal und ein anderes zweimal vorkommt: Zeichen mit drei Vorkommen $20$ Möglichkeiten, Zeichen mit zwei Vorkommen $19$, Plätze der zwei Vorkommen $\binom52=10$. Zusammen $20\cdot19\cdot10=3800$.
Beispiel — Geordnete Ergebnisse
Drei faire Tetraeder (Seiten $1$ bis $4$) haben $4^3=64$ gleich wahrscheinliche geordnete Ergebnisse. Drei verschiedene Zahlen: $\frac{4\cdot3\cdot2}{64}=0.375$. Genau ein Paar: $\frac{4\cdot3\cdot3}{64}=0.5625$. Drei gleiche Zahlen: $\frac4{64}$. Die ungeordnete Kombination ${1;2;3}$ hat die Wahrscheinlichkeit $\frac6{64}$, die Kombination ${4;4;4}$ nur $\frac1{64}$.
Beispiel — Passwort erraten
Ein Code aus den Ziffern $1,9,9,2$ hat $\frac{4!}{2!}=12$ Anordnungen. Wird jede Anordnung genau einmal in zufälliger Reihenfolge probiert, findet man den Code mit der Wahrscheinlichkeit $\frac1{12}$ genau beim fünften Versuch.
Beispiel — Zufällige Einteilung
$40$ Personen ($16$ Frauen, $24$ Männer) werden zufällig in zwei Gruppen zu je $20$ geteilt. Die erste Gruppe enthält genau $8$ Frauen und $12$ Männer mit der Wahrscheinlichkeit $\frac{\binom{16}{8}\binom{24}{12}}{\binom{40}{20}}\approx0.252$.
Weitere häufige Fehler
- Lücken vergessen: Bei «nicht benachbart» zuerst die anderen Objekte anordnen; die Ränder zählen als Lücken mit.
- Geordnete und ungeordnete Ergebnisse mischen: Die Kombination ${1;2;3}$ ist wahrscheinlicher als ${4;4;4}$, obwohl beide eine Kombination sind. Gleich wahrscheinlich sind die geordneten Ergebnisse unterscheidbarer Würfel.
- Gruppen teilen, die man unterscheiden kann: Durch die Zahl der Vertauschungen teilt man nur bei gleich grossen, nicht unterscheidbaren Gruppen. Zimmer mit Nummern oder verschiedener Grösse sind unterscheidbar.
- Drei Köpfe «irgendwo» mit drei Köpfen «hintereinander» verwechseln: $\binom83$ zählt beliebige Plätze, ein zusammenhängender Block der Länge $3$ hat in einer Reihe aus $8$ Plätzen nur $6$ Startplätze.
Wie es weitergeht
Aus abgezählten Möglichkeiten werden Wahrscheinlichkeiten in Wahrscheinlichkeitsrechnung. Wiederholte Versuche mit festem Erfolgsanteil (Ziehen mit Zurücklegen, mindestens ein Treffer, genau $k$ Treffer) gehören zu Binomial- und Normalverteilung; Vierfeldertafeln, Quartile und Boxplots stehen in Deskriptive Statistik.