Permutationen und Kombinationen erklärt

Das allgemeine Zählprinzip

Zählaufgaben fragen, auf wie viele Arten etwas geschehen kann. Die Grundlage ist das allgemeine Zählprinzip, auch Produktregel genannt: Lässt sich eine Wahl auf $m$ Arten treffen und eine zweite, unabhängige Wahl auf $n$ Arten, dann lassen sich beide zusammen auf $m \times n$ Arten treffen. Die Idee gilt für beliebig viele Stufen.

Mit 3 Hemden, 4 Hosen und 2 Paar Schuhen kannst du $3 \times 4 \times 2 = 24$ verschiedene Outfits zusammenstellen. Eine vierstellige PIN aus den Ziffern 0 bis 9, bei der Wiederholungen erlaubt sind, hat $10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000$ Möglichkeiten. Alle Formeln in diesem Artikel sind Abkürzungen dieser Multiplikation: Wenn dir eine Aufgabe seltsam vorkommt, ist das Zurückgehen zu einer Zählung Stufe für Stufe immer eine sichere Wahl.

Fakultäten

Um $n$ verschiedene Objekte in eine Reihe zu stellen, gibt es $n$ Möglichkeiten für den ersten Platz, $n - 1$ für den zweiten und so weiter bis 1. Dieses Produkt heißt $n$ Fakultät:

So ist $5! = 120$: Fünf Bücher lassen sich auf 120 verschiedene Arten in ein Regal stellen. Per Definition ist $0! = 1$, was die folgenden Formeln stimmig hält, denn es gibt genau eine Möglichkeit, „nichts“ anzuordnen. Fakultäten wachsen atemberaubend schnell: $10! = 3{,}628{,}800$, und ein gemischtes Kartenspiel hat $52!$ mögliche Reihenfolgen, eine Zahl mit 68 Stellen.

Permutationen und Variationen: Die Reihenfolge zählt

Eine Variation, auch geordnete Stichprobe ohne Zurücklegen genannt, ist eine geordnete Folge von $r$ Objekten, die aus $n$ verschiedenen Objekten ausgewählt werden. Da die Reihenfolge zählt, ist Erster-Zweiter-Dritter etwas anderes als Dritter-Zweiter-Erster. Die Anzahl der Variationen ist

Menschen an einem runden Tisch zu platzieren, ist ein Sonderfall. Rückt jeder einen Stuhl weiter, ergibt sich dieselbe Sitzordnung, $n$ Personen können sich also auf $(n-1)!$ verschiedene Arten setzen. Sechs Personen an einem runden Tisch haben $5! = 120$ Sitzordnungen und nicht 720. Das nennt man eine Kreispermutation.

Kombinationen: Die Reihenfolge spielt keine Rolle

Eine Kombination ist eine Auswahl, bei der nur zählt, welche Elemente gewählt wurden. Wählt man Anna, Ben und Clara für einen Ausschuss, ergibt das denselben Ausschuss, egal in welcher Reihenfolge. Jede Gruppe von $r$ Objekten entspricht $r!$ Variationen, also teilen wir durch diese Zahl:

Kombinationen sind symmetrisch: $\binom{n}{r} = \binom{n}{n-r}$, denn die 3 Personen auszuwählen, die dabei sind, ist dasselbe, wie die 5 auszuwählen, die draußen bleiben. Sie sind auch die Zahlen im Pascalschen Dreieck und die Koeffizienten beim Ausmultiplizieren des Binoms $(a + b)^n$.

Woran man erkennt, was man braucht

Stell eine einzige Frage: Wenn ich zwei der gewählten Elemente vertausche, erhalte ich dann ein anderes Ergebnis? Wenn ja, zählt die Reihenfolge, und du brauchst Variationen. Wenn nein, nimm Kombinationen.

• Platzierungen, Ranglisten, PINs, Sitzordnungen und Zeitpläne: Variationen.
• Mannschaften, Ausschüsse, Kartenhände, Lottotipps und Pizzabeläge: Kombinationen.
• Ämter innerhalb einer Gruppe, etwa Vorsitz und Kasse, machen die Reihenfolge wichtig, auch wenn die Personen aus derselben Gruppe kommen.

Eine schnelle Probe: Die Anzahl der Variationen ist immer $r!$-mal die Anzahl der Kombinationen. Erfüllen deine beiden Ergebnisse diese Beziehung nicht, ist eines davon falsch.

Zählen mit Wiederholung und mehrfachen Buchstaben

Dürfen sich Elemente wiederholen, ändern sich die Formeln. Geordnete Auswahlen mit Wiederholung gibt es $n^r$, wie im Beispiel mit der PIN. Ungeordnete Auswahlen mit Wiederholung, etwa 3 Kugeln Eis aus 5 Sorten, wobei Sorten doppelt vorkommen dürfen, gibt es

Buchstaben mit Wiederholungen anzuordnen, erfordert eine weitere Anpassung: Man teilt durch die Fakultät jeder Wiederholungsanzahl, weil das Vertauschen gleicher Buchstaben nichts ändert. Das Wort MISSISSIPPI hat 11 Buchstaben, darunter 4-mal I, 4-mal S und 2-mal P: Es hat also $\frac{11!}{4!\,4!\,2!} = 34{,}650$ verschiedene Anagramme.

Zählen, um Wahrscheinlichkeiten zu berechnen

Sind die Ergebnisse gleich wahrscheinlich, ist eine Wahrscheinlichkeit die Anzahl der günstigen Fälle geteilt durch die Anzahl der möglichen Fälle: Variationen und Kombinationen erledigen also den Großteil der Arbeit. Die Grundlage dieses Verhältnisses erklären die Grundlagen der Wahrscheinlichkeitsrechnung.

Kartenspiele bieten weitere Übungen. Es gibt $\binom{52}{5} = 2{,}598{,}960$ mögliche Hände mit fünf Karten. Eine Hand mit allen vier Assen braucht nur noch eine Karte, die aus den übrigen 48 gewählt wird, die Wahrscheinlichkeit ist also $\frac{48}{2{,}598{,}960} = \frac{1}{54{,}145}$.

Häufige Fehler

• Variationen für eine Mannschaft oder einen Ausschuss verwenden, was um den Faktor $r!$ zu viel zählt.
• Vergessen, dass $0! = 1$ ist, was Formeln wie $\binom{n}{n}$ zunichtemacht.
• Gleiche Elemente nicht berücksichtigen, etwa bei Anagrammen mit mehrfachen Buchstaben.
• Stufen multiplizieren, die nicht unabhängig sind, ohne die folgenden Anzahlen anzupassen.

Der Rechner für Variationen und Kombinationen berechnet ${}_nP_r$ und ${}_nC_r$ mit allen Schritten über die Fakultäten, und der Wahrscheinlichkeitsrechner macht aus diesen Anzahlen Wahrscheinlichkeiten.

Das Pascalsche Dreieck und Teilmengen

Jede Zahl im Pascalschen Dreieck ist die Summe der beiden Zahlen direkt darüber, und die Zeile $n$ enthält die Werte $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. Zeile 4 lautet 1, 4, 6, 4, 1, genau die Koeffizienten von $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$. Die Regel, nach der das Dreieck aufgebaut wird, ist selbst ein Zählergebnis:

Um zu sehen, warum, halte ein bestimmtes Element fest. Jede Auswahl von $r$ Elementen enthält es entweder, und dann bleiben $r - 1$ Elemente aus den übrigen $n - 1$ zu wählen, oder sie schließt es aus, und dann bleiben alle $r$ Elemente aus den übrigen $n - 1$ zu wählen. Die Summe einer ganzen Zeile ist $2^n$, die Gesamtzahl der Teilmengen einer Menge mit $n$ Elementen, da jedes Element entweder dabei ist oder nicht. Eine Pizzeria mit 8 Belägen kann also $2^8 = 256$ verschiedene Pizzen zubereiten, die ohne jeden Belag mitgezählt.

Übungen

1. Auf wie viele Arten lassen sich 4 Bücher, ausgewählt aus 7 verschiedenen Büchern, in ein Regal stellen? Lösung: ${}_7P_4 = 7 \times 6 \times 5 \times 4 = 840$.
2. Auf wie viele Arten lassen sich 4 Beläge aus 10 auswählen? Lösung: $\binom{10}{4} = 210$.
3. Wie viele verschiedene Anagramme hat das Wort BANANA? Lösung: $\frac{6!}{3!\,2!} = 60$.
4. Wie viele Codes aus fünf Buchstaben lassen sich mit 26 Buchstaben bilden, wenn Wiederholungen erlaubt sind? Lösung: $26^5 = 11{,}881{,}376$.

Häufige Fragen