Permutation und Kombination

Anordnungen und Auswahlen aus einer Gruppe Zählen

Eine Permutation (nPr) zählt, auf wie viele Arten r Elemente aus n angeordnet werden können, wobei die Reihenfolge wichtig ist, während eine Kombination (nCr) zählt, auf wie viele Arten r Elemente aus n ausgewählt werden können, wobei die Reihenfolge nicht wichtig ist. Geben Sie eine Gesamtzahl von Elementen (n) und wie viele Sie auswählen (r) ein, und dieser Rechner findet beide verwandten Antworten auf einmal.

Die Formeln

• Permutationen: $P(\vA{n}, \vB{r}) = \frac{\vA{n}!}{(\vA{n} - \vB{r})!}$ — gleichbedeutend mit dem Produkt von $\vB{r}$ absteigenden Zahlen, beginnend bei $\vA{n}$: $\vA{n} \times (\vA{n}-1) \times \cdots \times (\vA{n}-\vB{r}+1)$.
• Kombinationen: $C(\vA{n}, \vB{r}) = \frac{P(\vA{n}, \vB{r})}{\vB{r}!}$ — dieselbe Permutationsanzahl, geteilt durch die $\vB{r}!$ Arten, wie diese $\vB{r}$ Elemente selbst neu angeordnet werden könnten (da die Reihenfolge bei einer Kombination nicht wichtig ist).

Beispielrechnung

Auswahl von 3 Elementen aus einer Gruppe von 10, bei der die Reihenfolge wichtig ist (Permutationen):

$$P(10,3) = 10 \times 9 \times 8 = 720$$

Dieselbe Auswahl, bei der die Reihenfolge NICHT wichtig ist (Kombinationen):

$$C(10,3) = 720 \div 3! = 720 \div 6 = 120$$

Eine Überprüfung Aus Der Realen Welt

Die Chancen, alle 6 Zahlen in einer 6-aus-49-Lottoziehung zu treffen, stehen 1 zu C(49,6) — exakt 13.983.816 — da die Reihenfolge, in der die Zahlen gezogen werden, nicht ändert, ob Sie gewonnen haben.

Wichtige Einflussfaktoren

• Ob die Reihenfolge zählt, ist die einzige Frage, die bestimmt, welche Formel gilt. Die Anordnung von Medaillengewinnern auf einem Podest (1., 2., 3. Platz zählt) ist ein Permutationsproblem, während die Auswahl, welche 3 Personen ein Komitee bilden (keine Rangfolge beteiligt), ein Kombinationsproblem ist — diese Unterscheidung korrekt zu erkennen ist die häufigste Fehlerquelle bei der Anwendung dieser Formeln.
• Kombinationen ergeben bei gleichem n und r immer eine gleiche oder kleinere Anzahl als Permutationen. Da eine Kombination jede mögliche Anordnung derselben r Elemente zu einer einzigen Zählung zusammenfasst, ist K(n,r) immer P(n,r) geteilt durch r! — die beiden Werte stimmen nur exakt überein, wenn r 0 oder 1 ist, da es nur eine Möglichkeit gibt, 0 oder 1 Elemente anzuordnen, unabhängig von der Reihenfolge.
• Sowohl Permutations- als auch Kombinationsanzahlen wachsen extrem schnell, wenn n und r zunehmen. Dieses explosive Wachstum (kombinatorische Explosion genannt) ist genau der Grund, warum Lotterie-Gewinnchancen mit nur einer bescheidenen Erhöhung der Anzahl gezogener Zahlen so astronomisch klein werden — der Übergang von einer 6-aus-49-Lotterie zu einer 6-aus-59-Lotterie verschlechtert die Chancen beispielsweise bedeutsam, obwohl der Pool nur um 10 Zahlen wächst.
• Diese Formeln setzen voraus, dass jedes Element eindeutig ist und keines mehr als einmal gewählt werden kann. Ein Szenario, das wiederholte Auswahlen erlaubt (wie eine 4-stellige PIN, bei der sich Ziffern wiederholen können), verwendet eine völlig andere Zählformel — bestätigen Sie immer, ob Wiederholung erlaubt ist, bevor Sie die hier verwendeten Standard-nPr-/nCr-Formeln anwenden.

Häufige Fehler

• Die Permutationsanzahl verwenden, wenn die Reihenfolge tatsächlich keine Rolle spielt, oder umgekehrt. Dies ist der häufigste Fehler — fragen Sie immer zuerst, ob das Vertauschen zweier ausgewählter Elemente als ein anderes Ergebnis zählen würde, bevor Sie eine Formel wählen, statt anhand der Formulierung des Problems zu raten.
• Vergessen, dass Kombinationen bei gleichem n und r nie größer sind als Permutationen. Wenn eine Kombinationsanzahl größer ausfällt als die entsprechende Permutationsanzahl bei denselben Eingaben, wurde etwas falsch eingegeben — Kombinationen teilen die Permutationsanzahl herunter, sie erhöhen sie nie.
• Diese Formeln auf eine Situation anwenden, die wiederholte Auswahlen erlaubt. Beide Formeln gehen davon aus, dass jedes Element höchstens einmal gewählt werden kann — ein Problem, das Wiederholungen erlaubt (wie das Erzeugen einer 4-stelligen PIN), braucht einen völlig anderen Zählansatz, nicht nPr oder nCr.

Gut zu Wissen

• Möchten Sie tatsächlich die Wahrscheinlichkeit eines bestimmten Ergebnisses berechnen, nicht nur die Möglichkeiten zählen? Wahrscheinlichkeitsrechner wandelt eine Kombinations- oder Permutationsanzahl in eine tatsächliche Wahrscheinlichkeit um.
• Arbeiten Sie mit einem vollständigen Datensatz statt nur Anordnungen zu zählen? Statistikrechner berechnet Mittelwert, Standardabweichung und andere zusammenfassende Kennzahlen aus einer Zahlenliste.
• Müssen Sie ein Verhältnis vereinfachen oder einen gemeinsamen Nenner als Teil eines verwandten kombinatorischen Problems finden? Rechner für ggT und kgV findet den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache einer Zahlenmenge.