Die richtige Formel wählen: Reihenfolge und Wiederholung
Je nach zwei voneinander unabhängigen Ja-Nein-Fragen gelten vier verschiedene Abzählformeln: Zählt die Reihenfolge, und ist Wiederholung zulässig?
| Reihenfolge zählt? | Wiederholung zulässig? | Formel | Beispielsituation |
|---|---|---|---|
| Ja | Nein | nPr = n! ÷ (n − r)! | Vergabe von Platz 1, 2 und 3 unter 7 Laufenden |
| Ja | Ja | nʳ | Bildung einer dreistelligen PIN aus den Ziffern 0 bis 6, Wiederholungen zulässig |
| Nein | Nein | nCr = n! ÷ (r!(n−r)!) | Wahl eines dreiköpfigen Ausschusses aus 7 Personen |
| Nein | Ja | C(n+r−1, r) | Wahl von 3 Kugeln aus 7 Eissorten, Wiederholungen zulässig |
- nCr ist bei gleichem n und r stets kleiner oder gleich nPr (genauer gilt nCr = nPr ÷ r!), da Kombinationen jede Gruppe von r! Anordnungen derselben Elemente zu einem einzigen Fall zusammenfassen.
- Für r = 0 ergeben nPr und nCr per Konvention beide 1 — es gibt genau eine Möglichkeit, null Elemente auszuwählen, nämlich die leere Auswahl.
- Für r = n (ohne Wiederholung) gilt nPr = n! und nCr = 1 — als ungeordnete Menge lassen sich alle n Elemente nur auf eine Weise wählen, in geordneter Form jedoch auf n! Weisen anordnen.
Was sind Permutationen und Kombinationen?
Eine Permutation ist eine Anordnung von Elementen, bei der die Reihenfolge zählt. Die Anzahl der Permutationen von r Elementen, die aus einer Menge von n unterscheidbaren Elementen ohne Wiederholung ausgewählt werden, schreibt man nPr; sie zählt Anordnungen wie erster, zweiter und dritter Platz, bei denen das Vertauschen zweier ausgewählter Elemente zu einem anderen, eigenständigen Ergebnis führt.
Eine Kombination ist eine Auswahl von Elementen, bei der die Reihenfolge keine Rolle spielt. Die Anzahl der Kombinationen von r aus n unterscheidbaren Elementen schreibt man nCr (auch n über r oder Binomialkoeffizient genannt); sie zählt Zusammenstellungen wie einen Ausschuss oder ein Kartenblatt, bei denen dieselben Elemente in anderer Reihenfolge als dasselbe Ergebnis gelten.
Die entscheidende Unterscheidungsfrage lautet: Führt ein Umordnen derselben ausgewählten Elemente zu einem anderen Ergebnis? Lautet die Antwort ja (etwa bei der Vergabe von Gold, Silber und Bronze oder beim Anordnen von Büchern im Regal), so verwendet man Permutationen. Lautet sie nein (etwa bei der Wahl eines dreiköpfigen Ausschusses oder beim Ziehen eines Kartenblatts), so verwendet man Kombinationen. Dieser Rechner gibt zusätzlich die Varianten mit Wiederholung aus, die dann gelten, wenn dasselbe Element mehrfach gewählt werden darf (etwa bei Ziffern einer PIN oder bei Eiskugeln, wenn Wiederholungen zulässig sind).
So verwenden Sie diesen Rechner für Permutationen und Kombinationen
- Geben Sie n ein — die Gesamtzahl der unterscheidbaren Elemente, aus denen ausgewählt wird.
- Geben Sie r ein — die Anzahl der auszuwählenden oder anzuordnenden Elemente. r muss kleiner oder gleich n sein: Ist r größer als n, liefert der Rechner überhaupt kein Ergebnis, auch nicht die Varianten mit Wiederholung.
- Lesen Sie die Permutationen (nPr) ab, wenn die Reihenfolge der Auswahl zählt und keine Wiederholung zulässig ist, oder die Kombinationen (nCr), wenn die Reihenfolge keine Rolle spielt und keine Wiederholung zulässig ist.
- Darf dasselbe Element mehrfach gewählt werden, so verwenden Sie statt der üblichen Werte für nPr und nCr die Ergebnisse mit Wiederholung.
Die Formeln für Permutationen und Kombinationen
Die Anzahl der Permutationen von r aus n Elementen ohne Wiederholung beträgt nPr = n! ÷ (n − r)!, gleichbedeutend mit dem Produkt von r aufeinanderfolgenden absteigenden ganzen Zahlen ab n. Rechenbeispiel mit n = 7 und r = 3: 7P3 = 7 × 6 × 5 = 210 — so viele Möglichkeiten gibt es, unter 7 Teilnehmenden einen ersten, zweiten und dritten Preis zu vergeben.
Die Anzahl der Kombinationen von r aus n Elementen ohne Wiederholung beträgt nCr = n! ÷ (r! × (n − r)!) = nPr ÷ r!. Damit werden die r! Anordnungen jeder ausgewählten Gruppe herausgeteilt, da Kombinationen die Reihenfolge nicht unterscheiden. Rechenbeispiel mit n = 7 und r = 3: 7C3 = 210 ÷ 3! = 210 ÷ 6 = 35 — so viele verschiedene dreiköpfige Ausschüsse lassen sich aus 7 Personen bilden.
Permutationen mit zugelassener Wiederholung (jede der r Positionen kann unabhängig jedes der n Elemente aufnehmen) ergeben schlicht nʳ. Für n = 7 und r = 3 gilt 7³ = 343 — etwa die Anzahl der dreistelligen Codes aus den Ziffern 0 bis 6, wenn Wiederholungen zulässig sind. Kombinationen mit zugelassener Wiederholung folgen der Formel des Sterne-und-Striche-Verfahrens, C(n + r − 1, r). Für n = 7 und r = 3 gilt C(9, 3) = 84 — etwa die Anzahl der Möglichkeiten, 3 Eiskugeln aus 7 Sorten zu wählen, wenn Sorten mehrfach vorkommen dürfen und die Reihenfolge keine Rolle spielt.
Häufige Fehler
- Die Permutationsformel verwenden, obwohl die Reihenfolge gar keine Rolle spielt (oder umgekehrt) — prüfen Sie vor der Wahl der Formel, ob das Vertauschen zweier ausgewählter Elemente das Ergebnis ändert.
- Vergessen zu prüfen, ob Wiederholung zulässig ist — die Wahl einer PIN (Ziffern dürfen sich wiederholen) erfordert eine andere Formel als das Austeilen von Karten aus einem Stapel (ohne Wiederholung, da Karten nicht zurückgelegt werden).
- nPr oder nCr mit einem r größer als n anwenden, obwohl keine Wiederholung zulässig ist — dies ist nicht definiert, da sich ohne Wiederholung nicht mehr unterscheidbare Elemente auswählen lassen, als die Menge enthält.
- Kombinationen mit Wiederholung (Sterne-und-Striche-Formel) mit dem gewöhnlichen nCr verwechseln — beide liefern sehr unterschiedliche Ergebnisse und gelten für verschiedene Situationen, je nachdem ob Wiederholungen zulässig sind.
Häufig gestellte Fragen
Worin unterscheiden sich Permutation und Kombination?
Eine Permutation zählt Anordnungen, bei denen die Reihenfolge zählt (nPr = n! ÷ (n−r)!) — etwa die Platzierung auf Rang 1, 2 und 3. Eine Kombination zählt Auswahlen, bei denen die Reihenfolge keine Rolle spielt (nCr = n! ÷ (r!(n−r)!)) — etwa die Wahl eines Ausschusses. Für n = 7 und r = 3 gilt 7P3 = 210 (geordnet), jedoch 7C3 = 35 (ungeordnet), da sich jede Gruppe von 3 Personen auf 3! = 6 verschiedene Weisen anordnen lässt und 210 ÷ 6 = 35 ergibt.
Wie berechnet man nCr (n über r)?
Verwenden Sie die Formel nCr = n! ÷ (r! × (n − r)!). Für n = 7 und r = 3 gilt: 7C3 = 7! ÷ (3! × 4!) = 5040 ÷ (6 × 24) = 5040 ÷ 144 = 35. Gleichwertig können Sie zunächst nPr berechnen (7 × 6 × 5 = 210) und anschließend durch r! teilen (3! = 6): 210 ÷ 6 = 35.
Wie berechnet man nPr?
Verwenden Sie die Formel nPr = n! ÷ (n − r)!, die sich zum Produkt von r aufeinanderfolgenden absteigenden ganzen Zahlen ab n vereinfacht. Für n = 7 und r = 3 gilt: 7P3 = 7 × 6 × 5 = 210.
Wann sollte ich Wiederholung bei Permutations- oder Kombinationsaufgaben zulassen?
Lassen Sie Wiederholung zu, wenn dasselbe Element innerhalb eines Ergebnisses mehrfach gewählt werden darf — etwa bei Ziffern eines PIN-Codes oder bei Eissorten, wenn eine Kundin für mehrere Kugeln dieselbe Sorte wählen darf. Lassen Sie keine Wiederholung zu, wenn jedes Element nur einmal verwendet werden kann — etwa beim Austeilen unterscheidbarer Spielkarten oder beim Zuweisen verschiedener Personen zu Rollen.
Was ergibt nPr, wenn r gleich n ist?
Für r = n, also beim Anordnen aller n Elemente ohne Wiederholung, vereinfacht sich nPr zu n! ÷ (n − n)! = n! ÷ 0! = n! ÷ 1 = n!. Dies entspricht der Gesamtzahl der Möglichkeiten, alle n unterscheidbaren Elemente in einer Reihe anzuordnen — 5 Elemente lassen sich beispielsweise auf 5! = 120 Weisen vollständig anordnen.
Was bedeutet das Sterne-und-Striche-Verfahren bei Kombinationen mit Wiederholung?
Das Sterne-und-Striche-Verfahren ist die übliche kombinatorische Technik zum Abzählen von Kombinationen mit zugelassener Wiederholung und liefert die Formel C(n + r − 1, r). Dabei stellt man die r gewählten Elemente als Sterne dar, die durch Striche voneinander getrennt werden, welche die Grenzen zwischen den n Kategorien markieren, und zählt anschließend die Anordnungen von Sternen und Strichen. Für n = 7 und r = 3 ergibt sich C(9, 3) = 84.
Quellenangaben
- Rosen KH. Discrete Mathematics and Its Applications. 8th ed. McGraw-Hill, 2018. (Permutations, combinations, and the stars-and-bars method.)
- NIST Digital Library of Mathematical Functions (DLMF), §26.1–26.3 Combinatorial Analysis. dlmf.nist.gov.
- Feller W. An Introduction to Probability Theory and Its Applications, Vol. 1. 3rd ed. Wiley, 1968. (Classic treatment of permutations and combinations.)