Permutationen und Kombinationen: Warum die Reihenfolge die Anzahl verändert
Fünf Personen melden sich freiwillig für ein Projekt. Du brauchst eine Leitung und eine Stellvertretung. Die Leitung kannst du auf fünf Arten wählen, danach die Stellvertretung auf vier Arten. Es gibt zwanzig Zuordnungen.
Ändere nun einen Satz: Du brauchst einen zweiköpfigen Ausschuss ohne getrennte Rollen. Dieselben fünf Personen ergeben zehn Ausschüsse. An den Personen hat sich nichts geändert. Verändert hat sich die Definition eines Ergebnisses.
Permutationen und Kombinationen sind zwei Möglichkeiten, Ergebnisse zu zählen, ohne jede Möglichkeit einzeln aufzuführen. Die Formeln werden verständlich, sobald du entscheidest, welche Informationen das Ergebnis bewahrt. Dieser Artikel entwickelt zuerst diese Entscheidung und leitet daraus die Schreibweise ab.
Beginne mit Positionen, nicht mit einer Formel
Stell dir zwei leere Felder mit den Beschriftungen Leitung und Stellvertretung vor. Für das erste Feld kommen fünf Personen infrage. Ist es besetzt, bleiben vier Personen für das zweite. Jede erste Wahl hat vier Fortsetzungen, also gilt:
Das ist das Multiplikationsprinzip. Wenn jede Möglichkeit in einer Stufe dieselbe Anzahl möglicher Fortsetzungen besitzt, multiplizierst du die Anzahlen der Stufen. Du kannst dir einen Baum mit fünf Ästen vorstellen, von denen sich jeder in vier weitere Äste teilt.
Die Beschriftungen sind entscheidend. Alex als Leitung und Bea als Stellvertretung ist etwas anderes als Bea als Leitung und Alex als Stellvertretung. Es sind dieselben Personen auf verschiedenen Positionen. Das ist eine geordnete Auswahl, eine sogenannte Permutation.
Ein Ausschuss hat keine beschrifteten Positionen. Alex, Bea und Bea, Alex bezeichnen dieselbe Gruppe. Wenn du für Ausschüsse die zwanzig Zuordnungen verwendest, hast du jede Gruppe zweimal gezählt.
Der Vertauschungstest zeigt, ob die Reihenfolge zählt
Frage: Erhalte ich ein anderes Ergebnis, wenn ich zwei ausgewählte Elemente vertausche?
Bei den Podestplätzen eines Rennens lautet die Antwort ja. Gold und Silber sind verschiedene Ergebnisse. Bei einer Auswahl von Pizzabelägen lautet sie normalerweise nein. Pilze plus Oliven sind dieselbe Auswahl wie Oliven plus Pilze.
Die Frage betrifft das Modell, nicht das Substantiv. Eine Aufgabe kann verlangen, drei Bücher zum Kaufen auszuwählen, wobei die Reihenfolge ignoriert wird, oder drei Bücher in einem Regal anzuordnen, wobei die Reihenfolge festgehalten wird. Das Wort „Bücher“ verrät dir nicht, welche Formel gilt.
Schreibe vor dem Rechnen ein Beispielergebnis auf. „Leitung Alex, Stellvertretung Bea“ enthält Rollen. „Die Gruppe mit Alex und Bea“ enthält keine. Dieser kleine Schritt verhindert mehr Fehler als das Auswendiglernen einer längeren Formelsammlung.
| Situation | Was das Ergebnis festhält | Modell |
|---|---|---|
| Gold, Silber und Bronze vergeben | Person auf jedem Platz | Geordnet, ohne Wiederholung |
| Drei Ausschussmitglieder auswählen | Nur die Zugehörigkeit | Ungeordnet, ohne Wiederholung |
| Einen vierstelligen Code bilden | Ziffer an jeder Position | Geordnet, Wiederholung kann erlaubt sein |
| Mehrere Eiskugeln auswählen | Anzahl je Sorte | Ungeordnet, Wiederholung kann erlaubt sein |
Bei den letzten beiden Zeilen musst du zusätzlich nach Wiederholungen fragen. Entscheide nicht allein anhand der Reihenfolge.
Fakultäten zählen vollständige Anordnungen
Stelle vier verschiedene Bücher in eine Reihe. Für den ersten Platz gibt es vier Möglichkeiten, für den zweiten drei, für den dritten zwei und für den letzten eine:
Das Ausrufezeichen steht für die Fakultät. Es kürzt das absteigende Produkt ab. Für eine nichtnegative ganze Zahl zählt die Fakultät die Anordnungen aller verschiedenen Elemente.
Warum gilt ? Es gibt genau eine leere Anordnung. Du tust nichts, und die leere Anordnung ist vollständig. Dieser Wert sorgt außerdem dafür, dass konsistent bleibt.
Verwechsle die Fakultät nicht mit wiederholter Addition oder einer Potenz. Vier Fakultät ist vierundzwanzig; vier hoch vier ist zweihundertsechsundfünfzig. Bei einer Fakultät schrumpft die Zahl der Möglichkeiten, weil ein Element nicht erneut verwendet werden kann. Bei einer Potenz bleibt sie konstant.
Permutationen beenden das Produkt früher
Angenommen, sieben Personen nehmen an einem Rennen teil und du möchtest nur die ersten drei Plätze ohne Gleichstand bestimmen. Für den ersten Platz gibt es sieben Möglichkeiten, für den zweiten sechs und für den dritten fünf:
Wie die übrigen vier Personen ins Ziel kommen, spielt keine Rolle. Bis eins weiterzumultiplizieren würde eine andere Frage beantworten.
Für geordnete Positionen, die ohne Wiederholung aus verschiedenen Elementen besetzt werden, gilt:
Der Nenner kürzt den unbenutzten Rest der Fakultät. Im Rennbeispiel bleiben nach der Division von sieben Fakultät durch vier Fakultät genau sieben mal sechs mal fünf übrig.
Diese Formel setzt und verschiedene verfügbare Elemente voraus. Ändert die Aufgabe diese Voraussetzungen, kehre zu den Feldern zurück, statt die Zahlen in den Ausdruck zu zwingen.
Kombinationen entfernen mehrfach gezählte Anordnungen
Wähle drei von sieben Personen für einen Ausschuss. Die geordnete Anzahl ist 210, behandelt aber verschiedene Anordnungen derselben Dreiergruppe als unterschiedliche Ergebnisse.
Nimm eine Dreiergruppe aus Alex, Bea und Chen. Ihre Mitglieder lassen sich in sechs Reihenfolgen aufführen: ABC, ACB, BAC, BCA, CAB und CBA. Jede Dreiergruppe erscheint genau sechsmal in der geordneten Anzahl, denn .
Teile durch die Anzahl der mehrfach gezählten Anordnungen:
Allgemein gilt:
Dies liest man als „n über r“. Die erste Division entfernt unbenutzte Elemente aus der Anordnungszahl, die zweite entfernt Reihenfolgen, die du nicht mehr unterscheidest.
Hier zeigt sich eine nützliche Symmetrie: . Die Wahl der drei Personen, die teilnehmen, bestimmt zugleich die vier, die nicht teilnehmen. Beide Beschreibungen beziehen sich auf dieselben Entscheidungen.
Wiederholung verändert die Frage erneut
Ein vierstelliger Code kann an jeder Position jede Ziffer von null bis neun verwenden, auch am Anfang. Wiederholte Ziffern sind erlaubt. Jedes Feld hat zehn Möglichkeiten:
Darf keine Ziffer wiederholt werden, wird daraus:
Steht in der Aufgabe „vierstellige Zahl“ statt „Code“, ist eine führende Null normalerweise ausgeschlossen. Sind Wiederholungen erlaubt, ergibt das:
Drei sehr ähnliche Sätze, drei verschiedene Anzahlen. Die Formel ist nicht unzuverlässig geworden. Die Einschränkungen haben sich verändert.
Eine ungeordnete Auswahl mit Wiederholung, etwa Eiskugeln mit mehrfach gewählten Sorten, erfordert eine andere Zählmethode. Gewöhnliche Kombinationen setzen voraus, dass jedes verfügbare Element höchstens einmal ausgewählt wird. Zu erkennen, dass eine vertraute Formel nicht gilt, ist ein richtiger erster Schritt.
Arbeite die Entscheidung in dieser Reihenfolge durch
Schreibe vor dem Rechnen auf, wie ein vollständiges Ergebnis aussieht. Frage dann, ob Reihenfolge oder Rollen Ergebnisse unterscheiden, ob sich ein Element wiederholen darf und ob für eine Position eine besondere Einschränkung gilt.
Versuche diese drei Aufgaben, ohne sofort auf die Antworten zu schauen:
- Wähle aus sechs Personen eine vorsitzende und eine protokollführende Person, wobei niemand beide Rollen übernimmt.
- Wähle aus denselben sechs Personen zwei gleichberechtigte Vertretungen.
- Bilde einen dreistelligen Code aus vier Symbolen, wobei Wiederholungen erlaubt sind.
Die erste Aufgabe hat Zuordnungen. Bei der zweiten teilst du diese Zahl durch und erhältst fünfzehn Paare. Die dritte hat Codes, weil an jeder Position alle vier Symbole verfügbar bleiben.
Die Begründung ist wichtiger als die Zahl. Wenn du erklären kannst, warum eine Antwort durch zwei geteilt wird und eine andere nicht, hast du den Unterschied verstanden.
Zählen ist die Grundlage der Wahrscheinlichkeitsrechnung
Wenn gleich wahrscheinliche Ergebnisse korrekt gezählt werden, kannst du Wahrscheinlichkeiten bilden, indem du günstige Ergebnisse mit allen möglichen Ergebnissen vergleichst. Unser intuitiver Leitfaden zur Wahrscheinlichkeit geht diesen nächsten Schritt. Das Geburtstagsparadoxon zeigt, wie eine sorgfältig gewählte Zählung ein überraschendes Ergebnis handhabbar macht.
Halte die Fertigkeit vorerst klein: Definiere ein Ergebnis, zeichne vorhandene Positionen und erkläre jeden Faktor. Nutze die Wahrscheinlichkeitsübungen in Math Zen für die nächste Anwendung und kehre zu einem kleinen Beispiel zurück, sobald die Schreibweise die Begründung verdeckt.
Eine Permutation bewahrt die Anordnung. Eine Kombination bewahrt die Zugehörigkeit. Die Division durch eine Fakultät bedeutet schlicht, die Anordnung zu vergessen, ohne dieselbe Gruppe erneut zu zählen.
Häufige Fragen
- Was ist der Unterschied zwischen einer Permutation und einer Kombination?
- Eine Permutation hält eine Reihenfolge oder die Zuordnung zu verschiedenen Positionen fest. Eine Kombination hält nur fest, welche Elemente ausgewählt wurden. Wer aus fünf Personen eine Leitung und eine Stellvertretung bestimmt, erhält 20 Zuordnungen; wer einen zweiköpfigen Ausschuss wählt, erhält 10 Gruppen.
- Wie erkenne ich, ob die Reihenfolge zählt?
- Vertausche zwei ausgewählte Elemente. Verändert sich das Ergebnis, zählt die Reihenfolge. Werden Leitung und Stellvertretung vertauscht, ändern sich ihre Rollen. Die Reihenfolge, in der du Ausschussmitglieder nennst, verändert den Ausschuss dagegen nicht.
- Warum teilt man bei Kombinationen durch r Fakultät?
- Die geordnete Anzahl führt jede Gruppe einmal für jede Anordnung ihrer r verschiedenen Mitglieder auf. Es gibt r Fakultät solcher Anordnungen, daher entfernt die Division diese Mehrfachzählungen. Diese Begründung setzt eine Auswahl ohne Wiederholung voraus.
- Was gilt, wenn Wiederholungen erlaubt sind?
- Bei r geordneten Positionen mit jeweils n verfügbaren Möglichkeiten beträgt die Anzahl n hoch r. Eine ungeordnete Auswahl mit Wiederholung ist ein anderes Modell und verwendet nicht die gewöhnliche Formel n über r.
- Warum ist null Fakultät gleich eins?
- Es gibt genau eine Möglichkeit, keine Elemente anzuordnen: Die Anordnung bleibt leer. Null Fakultät gleich eins sorgt außerdem dafür, dass die Fakultätsrekursion bei eins Fakultät konsistent bleibt.
