Kombinatorik

Kombinatorik ist die Kunst des Zählens: Sie berechnet, wie viele Möglichkeiten es gibt, Dinge auszuwählen oder anzuordnen, ohne alle Möglichkeiten aufzuschreiben. Das braucht man oft in der Wahrscheinlichkeitsrechnung, denn nach der Laplace-Regel ist die Wahrscheinlichkeit „günstige durch mögliche Ergebnisse“. Beide Zahlen musst du erst einmal zählen.

Diese Seite geht tiefer als der Überblick dort. Sie ordnet alle Fälle nach zwei Fragen: Kommt es auf die Reihenfolge an? Darf etwas mehrfach vorkommen? Zum Prüfen deiner Ergebnisse hilft der Kombinatorik-Rechner, zum Üben das Arbeitsblatt Kombinatorik.

Das Zählprinzip

Das Grundprinzip ist das Multiplizieren. Ein T-Shirt gibt es in 3 Farben (Rot, Blau, Grün) und 2 Größen (S, M). Für jede Farbe hast du zwei Größen zur Wahl, also gibt es $3·2=6$ verschiedene Shirts.

Ein Beispiel für die Summenregel: Zur Schule fahren drei Busse oder zwei Bahnen, das sind $3+2=5$ Verbindungen. Ein Beispiel für die Produktregel: Eine vierstellige PIN hat an jeder Stelle 10 Ziffern zur Wahl, also $10·10·10·10=10.000$ Möglichkeiten.

Wichtig ist, ob sich die Zahl der Möglichkeiten von Schritt zu Schritt ändert. Wählst du aus 5 Kindern nacheinander eine Reihenfolge für 3 Plätze, stehen für den ersten Platz 5, für den zweiten nur noch 4 und für den dritten noch 3 Kinder zur Wahl: $5·4·3=60$.

Fakultät und Permutationen

Alle $n$ Dinge in eine Reihe zu bringen, heißt permutieren. Für den ersten Platz gibt es $n$, für den zweiten $n-1$ Möglichkeiten und so fort. Das Produkt $n·(n-1)·\dots ·2·1$ heißt Fakultät $n!$, und es gilt $0!=1$.

6 Personen können auf $6!=720$ Arten in einer Reihe stehen. An einem runden Tisch zählen Drehungen nicht als verschieden. Dann bleibt $(6-1)!=120$.

Permutationen mit gleichen Elementen

Sind manche Dinge nicht unterscheidbar, werden Anordnungen mehrfach gezählt. Das Wort ANANAS hat 6 Buchstaben, aber dreimal A und zweimal N. Vertauschst du die drei A untereinander, entsteht dasselbe Wort, und das gilt für $3!=6$ Vertauschungen. Entsprechend für die N mit $2!=2$. Du teilst also:

Variationen: Auswahl mit Reihenfolge

Bei einer Variation wählst du $k$ von $n$ Dingen aus, und die Reihenfolge ist wichtig. Zwei Fälle:

• Mit Wiederholung (Zurücklegen): Jede Stelle hat $n$ Möglichkeiten, also $n^k$. Eine PIN mit 4 Ziffern: ${10}^4=10.000$.
• Ohne Wiederholung: Für die erste Stelle $n$, für die zweite $n-1$ und so weiter, bis $k$ Faktoren da sind: $n·(n-1)\cdots (n-k+1)=\frac{n!}{(n-k)!}$. Beim Siegerpodest mit 3 Plätzen aus 8 Läufern sind es $8·7·6=336$.

Passwörter und PIN

Variationen mit Wiederholung bestimmen, wie sicher ein Passwort ist. Die Zahl der Möglichkeiten wächst mit jedem Zeichen um den Faktor der Zeichenzahl. Die Tabelle zeigt, wie lange ein Computer im Modell höchstens braucht, wenn er pro Sekunde eine Milliarde Passwörter ausprobiert:

Die Länge zählt mehr als die Zeichenvielfalt: Vier Zeichen mehr (von 8 auf 12) vervielfachen die Möglichkeiten um ${62}^4\approx \mathrm{14,8}$ Millionen. Echte Angreifer probieren allerdings zuerst häufige Passwörter, daher schützt nur ein wirklich zufällig gewähltes Passwort so gut, wie die Rechnung zeigt.

Kombinationen: Auswahl ohne Reihenfolge

Bei einer Kombination kommt es nicht auf die Reihenfolge an, nur darauf, welche Dinge ausgewählt sind. Ohne Wiederholung gilt: Zählst du erst mit Reihenfolge ($\frac{n!}{(n-k)!}$), wird jede Auswahl $k!$-mal gezählt. Du teilst durch $k!$:

Gelesen: „$n$ über $k$“. Aus 10 Kindern lassen sich $\left(\genfrac{}{}{0ex}{}{10}{3}\right)=\frac{10·9·8}{3·2·1}=120$ Dreiergruppen bilden, aber $10·9·8=720$ Podeste mit Reihenfolge.

Mit Wiederholung gibt es $\left(\genfrac{}{}{0ex}{}{n+k-1}{k}\right)$ Möglichkeiten. Beispiel: Eine Eisdiele hat 5 Sorten, du bestellst 3 Kugeln, auch gleiche Sorten sind erlaubt: $\left(\genfrac{}{}{0ex}{}{5+3-1}{3}\right)=\left(\genfrac{}{}{0ex}{}{7}{3}\right)=35$ verschiedene Becher.

Die vier Urnenmodelle

Alle Fälle lassen sich als Ziehen von $k$ Kugeln aus einer Urne mit $n$ Kugeln beschreiben. Es kommt auf zwei Fragen an: Wird die gezogene Kugel zurückgelegt? Zählt die Reihenfolge?

Im Alltag spielt das Modell „ungeordnet mit Zurücklegen“ die kleinste Rolle. In der Wahrscheinlichkeitsrechnung braucht man vor allem $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, besonders bei der Binomialverteilung.

Binomialkoeffizient und Pascalsches Dreieck

Die Binomialkoeffizienten $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ stehen im Pascalschen Dreieck: Zeile $n$, Stelle $k$ (jeweils ab 0 gezählt). Jede Zahl ist die Summe der beiden Zahlen darüber:

Dahinter steckt eine Zählidee: Aus $n$ Dingen wählst du $k$ aus. Entweder ist ein festes Ding dabei (dann fehlen $k-1$ aus den übrigen $n-1$), oder nicht (dann sind alle $k$ aus den übrigen $n-1$). Weitere Eigenschaften:

• Symmetrie: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$, denn mit den gewählten Dingen bestimmst du auch die nicht gewählten.
• Zeilensumme: $\left(\genfrac{}{}{0ex}{}{n}{0}\right)+\left(\genfrac{}{}{0ex}{}{n}{1}\right)+\dots +\left(\genfrac{}{}{0ex}{}{n}{n}\right)=2^n$. Das ist die Zahl aller Teilmengen. Bei 10 Pizzabelägen gibt es $2^{10}=1024$ mögliche Belagskombinationen, die leere eingeschlossen.
• Binomischer Lehrsatz: Die Zeile $n$ liefert die Koeffizienten von $(a+b{)}^n$. Zeile 4 ergibt $(a+b{)}^4=a^4+4a^{3}b+6a^2{b}^2+4a{b}^3+b^4$.

Lotto 6 aus 49 genauer

Der Tipp ist eine Kombination: 6 von 49 Zahlen, die Reihenfolge zählt nicht, also $\left(\genfrac{}{}{0ex}{}{49}{6}\right)=\mathrm{13.983.816}$ mögliche Tipps. Wie wahrscheinlich sind $k$ Richtige? Du wählst $k$ der 6 Gewinnzahlen ($\left(\genfrac{}{}{0ex}{}{6}{k}\right)$ Möglichkeiten) und $6-k$ der 43 anderen Zahlen ($\left(\genfrac{}{}{0ex}{}{43}{6-k}\right)$ Möglichkeiten):

Die günstigen Tipps summieren sich zu $\mathrm{13.983.816}$. Rechne zur Kontrolle nach: $\mathrm{6.096.454}+\mathrm{5.775.588}+\mathrm{1.851.150}+246.820+13.545+258+1=\mathrm{13.983.816}$. Mit einem Tipp pro Woche dauert es im Mittel Hunderttausende Jahre bis zum Sechser. Ähnlich zählt man beim Poker: 5 Karten aus 52 ergeben $\left(\genfrac{}{}{0ex}{}{52}{5}\right)=\mathrm{2.598.960}$ Blätter, und der Royal Flush (4 Möglichkeiten, eine je Farbe) hat die Chance $\frac{4}{\mathrm{2.598.960}}$, also 1 zu 649.740.

Das Schubfachprinzip

Manchmal reicht ein einfacher Gedanke statt einer Rechnung. Verteilst du mehr Dinge auf Fächer, als Fächer da sind, muss ein Fach mindestens zwei Dinge enthalten. Das ist das Schubfachprinzip. Unter 13 Personen haben mindestens zwei im selben Monat Geburtstag, denn es gibt nur 12 Monate. Unter 367 Personen haben mindestens zwei am selben Tag des Jahres Geburtstag (es gibt höchstens 366 Tage). Unter 25 Personen sind mindestens drei im selben Monat, denn $12·2=24$ Plätze fassen höchstens zwei pro Monat.

Typische Fehler

Übungen

Geschichte: von Pingala bis Bernoulli

Zählprobleme sind sehr alt. Der indische Gelehrte Pingala beschrieb im 3. oder 2. Jahrhundert v. Chr., wie viele Versmaße es aus kurzen und langen Silben gibt (Pingala und die Verslehre). Sein Verfahren entspricht dem Pascalschen Dreieck, das Halayudha im 10. Jahrhundert als „Berg Meru“ erklärte. In China und Persien kannte man es im 11. und 13. Jahrhundert (Jia Xian, Yang Hui, Omar Chayyam). Blaise Pascal verwendete es für Wahrscheinlichkeiten. Seine Abhandlung erschien 1665, nach seinem Tod.

Den Namen „Kombinatorik“ prägte Gottfried Wilhelm Leibniz 1666 mit seiner Dissertatio de arte combinatoria. Der zweite Teil der Ars Conjectandi (1713) von Jakob Bernoulli widmet sich Permutationen und Kombinationen und machte sie zum festen Werkzeug der Wahrscheinlichkeitsrechnung.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Kombinatorik
• Wikipedia: Binomialkoeffizient
• Wikipedia: Schubfachprinzip
• Wikipedia: Geburtstagsparadoxon
• Wikipedia: Pascal's triangle (englisch, Abschnitt History)
• Gottfried Wilhelm Leibniz: Dissertatio de arte combinatoria, Leipzig 1666.
• Jakob Bernoulli: Ars Conjectandi, Basel 1713.