Die Kernfrage: Spielt die Reihenfolge eine Rolle?
Permutationen und Kombinationen zählen beide die Anzahl der Möglichkeiten, r Elemente aus einer Gruppe von n verschiedenen Elementen auszuwählen, beantworten dabei jedoch zwei unterschiedliche Fragen. Eine Permutation zählt die Anzahl der Möglichkeiten, r Elemente auszuwählen und anzuordnen, sodass zwei Auswahlen mit denselben Elementen in unterschiedlicher Reihenfolge als zwei getrennte Ergebnisse gezählt werden. Eine Kombination zählt nur die Anzahl der Möglichkeiten, r Elemente auszuwählen, sodass zwei Auswahlen mit denselben Elementen unabhängig von der Reihenfolge, in der sie ausgewählt wurden, als ein einziges Ergebnis gezählt werden.
Eine einfache Methode, um zu entscheiden, welches Konzept zutrifft: Stellen Sie sich zwei Auswahlen vor, die genau dieselben Elemente verwenden, sie aber unterschiedlich auflisten oder anordnen. Stellen diese beiden Auswahlen tatsächlich unterschiedliche reale Ergebnisse dar -- unterschiedliche Rangfolgen, unterschiedliche Passwörter, unterschiedliche Zieleinläufe bei einem Rennen --, spielt die Reihenfolge eine Rolle, und eine Permutation ist die korrekte Zählweise. Stellen diese beiden Auswahlen dasselbe reale Ergebnis dar -- dasselbe Komitee, dasselbe Kartenblatt, dieselbe Menge an Lottozahlen --, spielt die Reihenfolge keine Rolle, und eine Kombination ist die korrekte Zählweise.
Die Formeln: nPr und nCr, mit einem geprüften Beispiel
Die Anzahl der Permutationen von r Elementen, ausgewählt aus n verschiedenen Elementen, beträgt nPr = n! / (n − r)!, und die Anzahl der Kombinationen beträgt nCr = n! / [r! (n − r)!] -- die Kombinationsformel ist die Permutationsformel geteilt durch r!, denn die Division durch r! entfernt die r! unterschiedlichen Anordnungen jeder Gruppe identischer Elemente, die die Permutationszählung als getrennt behandelt.
Rechenbeispiel: Auswahl von 3 Elementen aus einer Gruppe von 7. Permutationen: 7P3 = 7! / (7−3)! = 7 × 6 × 5 = 210. Kombinationen: 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35. Die Kombinationszahl ist genau die Permutationszahl geteilt durch 3! = 6, was die Beziehung nCr = nPr / r! bestätigt.
| Größe | Formel | Wert für n=7, r=3 |
|---|---|---|
| Permutationen (Reihenfolge spielt eine Rolle) | nPr = n! / (n − r)! | 7P3 = 7 × 6 × 5 = 210 |
| Kombinationen (Reihenfolge spielt keine Rolle) | nCr = n! / [r!(n − r)!] | 7C3 = 210 / 3! = 35 |
Mit Wiederholung vs. ohne Wiederholung
Beide obigen Formeln setzen voraus, dass jedes der n Elemente höchstens einmal ausgewählt werden kann -- eine Auswahl ohne Wiederholung. Können Elemente wiederverwendet werden (Auswahl mit Wiederholung, auch Auswahl mit Zurücklegen genannt), ändern sich die Zählformeln. Permutationen mit erlaubter Wiederholung erheben n einfach zur Potenz r, da jede der r Positionen unabhängig alle n Möglichkeiten zur Verfügung hat, unabhängig davon, was zuvor gewählt wurde: n^r.
Kombinationen mit erlaubter Wiederholung verwenden eine andere Formel, C(n + r − 1, r), die die Anzahl der Möglichkeiten zählt, r Elemente aus n Typen auszuwählen, wenn Wiederholungen erlaubt sind und die Reihenfolge weiterhin keine Rolle spielt -- ein seltener benötigter Fall, der jedoch beispielsweise auftritt, wenn Eiskugeln aus n Sorten ausgewählt werden und dieselbe Sorte mehr als einmal gewählt werden kann.
| Fall | Formel | Typisches Beispiel |
|---|---|---|
| Permutationen, ohne Wiederholung | n! / (n − r)! | Rangfolge von 3 Gewinnern aus 7 Finalisten |
| Permutationen, mit Wiederholung | n^r | Eine 4-stellige PIN, bei der sich Ziffern wiederholen können |
| Kombinationen, ohne Wiederholung | n! / [r!(n − r)!] | Auswahl von 6 Zahlen für einen Lottoschein |
| Kombinationen, mit Wiederholung | (n + r − 1)! / [r!(n − 1)!] | Auswahl von 3 Kugeln aus 5 Eissorten, Wiederholungen erlaubt |
Rechenbeispiele: ein PIN-Code und ein Lottoschein
Eine 4-stellige PIN, bei der jede der 4 Positionen eine beliebige Ziffer 0–9 sein kann und Ziffern sich wiederholen dürfen (die übliche Regel für Bank-PINs), ist ein Beispiel für Permutationen mit Wiederholung: Die Reihenfolge spielt eine Rolle (1234 und 4321 sind unterschiedliche PINs), und Wiederholung ist erlaubt, was 10^4 = 10.000 mögliche PINs ergibt. Wären wiederholte Ziffern stattdessen nicht erlaubt, würde die Anzahl auf den Wert für Permutationen ohne Wiederholung sinken, 10P4 = 10 × 9 × 8 × 7 = 5.040 -- weniger Möglichkeiten, da jede verwendete Ziffer eine Option für die verbleibenden Positionen entfernt.
Ein klassisches Lotterieformat, bei dem 6 Zahlen aus einem Pool von 49 gezogen werden, wobei keine Zahl wiederholt wird und die Ziehungsreihenfolge irrelevant dafür ist, ob ein Schein gewinnt, ist ein Beispiel für Kombinationen ohne Wiederholung: C(49, 6) = 49! / (6! × 43!) = 13.983.816. Diese hohe Zahl ist genau der Grund, warum solche Lotterieformate als Spiele mit sehr geringen Gewinnchancen gelten -- eine Kombinationszahl wächst sehr schnell sehr stark an, wenn n im Verhältnis zu r wächst, da hier ungeordnete Gruppen aus einem großen Pool gezählt werden statt einer kleinen, festen Menge von Anordnungen.
Ein schneller Merktrick für die richtige Formel
„Permutation" und „Position" beginnen beide mit einem P-Laut, und eine hilfreiche Eselsbrücke lautet: Permutationen kümmern sich um die Position -- also darum, wo in der Reihenfolge jedes Element landet. „Kombination" beschreibt eine zusammengesetzte Gruppe, wie den Inhalt einer Tasche oder eines Komitees, bei der nur die Zugehörigkeit zählt, nicht die Reihenfolge, in der die Mitglieder hinzukamen.
Passwörter, PINs, Rennrangfolgen und jede Sitzplatz- oder Terminplanung sind Permutationsprobleme, weil ein Vertauschen der Reihenfolge das Ergebnis ändert. Kartenblätter, Lottozahlenmengen, Komiteemitgliedschaften und jede ungeordnete Gruppenauswahl sind Kombinationsprobleme, weil allein die Mitglieder zählen, nicht die Reihenfolge, in der sie ausgewählt wurden.
Häufig gestellte Fragen
Was ist der Unterschied zwischen einer Permutation und einer Kombination?
Eine Permutation zählt Anordnungen, bei denen die Reihenfolge eine Rolle spielt, sodass dieselben Elemente in unterschiedlicher Reihenfolge als unterschiedliches Ergebnis zählen. Eine Kombination zählt Auswahlen, bei denen die Reihenfolge keine Rolle spielt, sodass dieselben Elemente in beliebiger Reihenfolge als ein einziges Ergebnis zählen. Beide gehen von derselben Gruppe von n Elementen aus und wählen r davon aus, doch eine Permutationszahl ist für dieselben n und r stets größer oder gleich der entsprechenden Kombinationszahl.
Was ist 7P3 und wie wird es berechnet?
7P3 ist gleich 210, die Anzahl der Möglichkeiten, 3 Elemente aus einer Gruppe von 7 verschiedenen Elementen auszuwählen und anzuordnen, wobei die Reihenfolge eine Rolle spielt. Es wird berechnet als 7P3 = 7! / (7 − 3)! = 7 × 6 × 5 = 210, indem die drei größten Faktoren von 7! miteinander multipliziert werden, da sich die kleineren Faktoren mit (7−3)! im Nenner kürzen.
Was ist 7C3 und wie wird es berechnet?
7C3 ist gleich 35, die Anzahl der Möglichkeiten, 3 Elemente aus einer Gruppe von 7 verschiedenen Elementen auszuwählen, wobei die Reihenfolge keine Rolle spielt. Es wird berechnet als 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35 -- genau die Permutationszahl, 7P3 = 210, geteilt durch 3! (die Anzahl der Möglichkeiten, jede Gruppe von 3 neu anzuordnen), da Kombinationen alle Anordnungen derselben Gruppe zu einem Ergebnis zusammenfassen.
Warum verwenden PINs Permutationen und Lotterien Kombinationen?
Eine PIN behandelt 1234 und 4321 als unterschiedliche Codes, sodass die Reihenfolge der Ziffern das Ergebnis verändert, was ein Permutationsszenario ist -- mit erlaubter Wiederholung ergibt eine typische 4-stellige PIN 10^4 = 10.000 Möglichkeiten. Ein Lottoschein gewinnt allein anhand der gezogenen Zahlen, unabhängig von deren Reihenfolge, sodass zwei Ziehungen mit denselben Zahlen in unterschiedlicher Reihenfolge dasselbe Gewinnergebnis darstellen, was ein Kombinationsszenario ist -- für ein 6-aus-49-Format ergibt C(49,6) = 13.983.816 mögliche Zahlenmengen.
Was bedeutet „mit Wiederholung" bei einer Permutations- oder Kombinationsformel?
Es bedeutet, dass ein Element innerhalb desselben Ergebnisses mehr als einmal ausgewählt werden kann. Permutationen mit erlaubter Wiederholung verwenden n^r (jede der r Positionen hat unabhängig alle n Möglichkeiten), während Kombinationen mit erlaubter Wiederholung (n + r − 1)! / [r!(n − 1)!] verwenden. Ohne Wiederholung kann jedes Element höchstens einmal verwendet werden, was die Standardformeln nPr und nCr voraussetzen.
Quellenangaben
- NIST Digital Library of Mathematical Functions (DLMF), §26 Combinatorial Analysis. dlmf.nist.gov.
- Rosen KH. Discrete Mathematics and Its Applications. 8th ed. McGraw-Hill, 2018 (permutations, combinations, and counting with repetition).
- Ross SM. A First Course in Probability. Pearson (combinatorial counting methods).
- Weisstein EW. "Permutation" and "Combination." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.