Erklärt: Permutationen vs. Kombinationen

Ja, ich rede von diesen mystischen Tasten auf Ihrem Taschenrechner (nCr und nPr), die Sie gnädigerweise drücken und die richtige Antwort ausspucken. Magie.

Die beiden Konzepte sind ziemlich einfach, daher sollte es nicht zu lange dauern, sie zu erklären. Ich werde die Unterschiede erklären; wann man sie verwendet; und was genau Ihr Rechner berechnet, wenn Sie sie eingeben (die Gleichung).

Am besten lassen sich die Anwendungsfälle anhand von zwei Beispielen veranschaulichen:

Beispiel 1: Es gibt 10 Sportler, die an einem Rennen teilnehmen, bei dem der Erstplatzierte eine Goldmedaille, der Zweitplatzierte eine Silbermedaille und der Drittplatzierte eine Bronzemedaille erhält. Wenn sie eine Medaille gewinnen, dürfen sie auf dem Siegertreppchen stehen. Der Rest erhält nichts… nicht einmal eine Teilnahme-Trophäe… denn das ist Amerika… und wer nicht der Erste ist, ist der Letzte.

Frage 1: Wie viele Möglichkeiten gibt es für das Podium?

Frage 2: wie viele Möglichkeiten gibt es dafür, wer eine Medaille gewinnt?

Wann verwendet man nPr und wann nCr?

Wann sollte man sie verwenden:

Die beiden Fragen mögen ähnlich erscheinen, aber es gibt einen grundlegenden Unterschied, der bestimmt, welche Gleichung man verwenden sollte.

Frage 1 (Podium) berücksichtigt die Relevanz der Reihenfolge:

Wenn Bob, Lacy und Sarah auf dem Podium stehen, ist der erste Platz von Bob nicht dasselbe wie der zweite Platz von Bob. Das ist ein anderes Ergebnis. Die Reihenfolge ist relevant, also verwenden Sie nPr.

nPr (Permutationen) wird verwendet, wenn die Reihenfolge eine Rolle spielt.

Frage 2 berücksichtigt nicht die Reihenfolge des Podiums, sondern fragt einfach, wer eine Medaille gewinnt. Die Frage grenzt nicht zwischen Gold, Silber oder Bronze ab, es sind alles Medaillen und nur das zählt. Wenn die Reihenfolge keine Rolle spielt, verwenden Sie nCr.

nCr (Kombinationen) wird verwendet, wenn die Reihenfolge keine Rolle spielt.

Was sie tatsächlich tun:

Nun, da Sie hoffentlich verstehen, wann Sie welche verwenden sollten, lassen Sie uns dazu übergehen, was sie tatsächlich tun.

nPr
Wie bereits erwähnt, findet nPr alle Permutationen, die innerhalb einer gegebenen Menge für eine gegebene Teilmenge existieren. In unserem speziellen Beispiel wird untersucht, wie viele verschiedene Ausgänge sich aus dem Rennen ergeben können, die zu einer Podiums-Permutation führen würden (unterschiedliche Reihenfolge).

In unserem Rennen:

Okay, so, wir haben den magischen Knopf ein bisschen mehr aufgeschlüsselt, aber Sie fragen sich jetzt vielleicht…warum ist das die Gleichung, und warum schreien mich die ganzen Zahlen an!!!! – was bedeutet das !?

! oder auch bekannt als Fakultät ist einfach eine bequeme Art, eine Reihe von Multiplikationen auszudrücken.

Im Einzelnen:

Zur Veranschaulichung gehen wir zurück zu unserem Beispiel:

n = 15 (weil es 15 Sportler gibt)

n! = 15! = 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1

Das errechnet Ihr Taschenrechner, wenn Sie die !-Taste drücken.

15! = 1 307 674 368 000

Diese Zahl steht für die maximale Anzahl von verschiedenen Aufträgen, die in einer Liste vorkommen können. Unsere Liste besteht aus 15 Läufern, und es gibt 1 307 674 368 000 verschiedene Möglichkeiten, wie sie angeordnet werden können. Die multiplizierte Zahl nimmt ab, weil mit der Platzierung einer Zahl dieser Platz nun belegt ist.

Wenn Läufer 1 auf Platz 15 steht, gibt es nur noch 14 weitere Plätze für alle verbleibenden Läufer, wenn Läufer 2 auf Platz 14 steht, gibt es nur noch 13 Plätze für alle Läufer. Wie bei den meisten Dingen ist es einfacher zu erklären, wenn man die Zahlen skaliert:

Einfacheres Beispiel (kann übersprungen werden, wenn Sie es schon verstehen):

Sagen wir, es gibt vier freie Plätze, und 4 Freunde, die sitzen wollen. Für den ersten Sitzplatz gibt es vier verschiedene Möglichkeiten (jeder der vier Freunde kann ihn sich schnappen), sobald er besetzt ist, hat der zweite Sitzplatz nur noch drei verschiedene Möglichkeiten (jeder der drei nicht gesetzten Freunde kann ihn sich schnappen), der dritte Sitzplatz hat nur noch zwei Möglichkeiten, und der letzte Sitzplatz hat standardmäßig nur noch eine Option – der arme Trottel, der sich noch nicht gesetzt hat.

Als Ergebnis gibt es mathematisch gesehen 4 x 3 x 2 x 1 mögliche Ergebnisse.

Wenn das Rennen einfach fragen würde, auf wie viele verschiedene Arten sich die Reihenfolge des Rennens ändern kann, würden wir nicht nPr verwenden, sondern Faktorial(!)… aber das tut es nicht… es fragt danach, wie oft sich das Podium ändern kann, was speziell die ersten drei Läufer betrachtet, nicht alle von ihnen. Aus diesem Grund verwenden wir keine Fakultät. Factorial ist ein zu breiter Bereich.

Weil er zu breit ist, müssen wir ihn reduzieren. Wir untersuchen nur die ersten drei Positionen, nicht die restlichen 12. Anders ausgedrückt: Wenn sich die Reihenfolge der ersten drei ändert, dann wird es als neue Permutation betrachtet, aber wenn die Reihenfolge der ersten drei gleich bleibt (auch wenn sich die Reihenfolge der restlichen 12 ändert), dann betrachten wir es nicht als neue Permutation.

Weil 12 Positionen irrelevant sind, müssen wir ihre Bedeutung in der Gleichung reduzieren.

Deshalb erhalten wir

Der einfachste Weg, die Relevanz der verbleibenden 12 Positionen zu entfernen, ist die Division der vollen Möglichkeitsanzahl(!) durch die Möglichkeitszahl für irrelevante Positionen zu dividieren. Wie bereits erwähnt, gibt es 12 Positionen, die für unser Podium irrelevant sind.

So 15! geteilt durch (15 -3)!

Das entspricht dem Ausschreiben:

was gleich 15 x 14 x 13 ist, da sich alle anderen Zahlen aufheben.

15 x 14 x 13 ist also = 2730

Nun schauen wir uns nCr an:

Wow, das hat lange gedauert, um die Permutationen durchzugehen, diese Runde sollte schneller gehen, weil ich jetzt schon über Faktorielle gesprochen habe.

Wie erwähnt, ist nCr, alle Kombinationen zu finden, die innerhalb einer gegebenen Menge für eine gegebene Teilmenge existieren, wenn die Reihenfolge keine Rolle spielt. In unserem Beispiel geht es um die Anzahl der verschiedenen Kombinationen, die für den Gewinn der Medaille auftreten können (d.h. Platz unter den ersten drei)

Nun gleich vorweg, Sie werden feststellen, dass es weniger Kombinationen als Permutationen gibt (455 < 2730). Das macht Sinn, weil Kombinationen ABC und ACB als das Gleiche kennzeichnen, während Permutation zwischen den beiden unterscheidet. Schauen wir uns an, was Ihr Taschenrechner macht, wenn Sie die Taste drücken.

Nun sollte Ihnen als erstes auffallen, dass die Gleichung der Permutationsgleichung ziemlich ähnlich ist, außer dass mehr zum Nenner hinzugefügt wird (es ist k!(n-r)!, nicht nur (n-r)!

Nach der vorherigen Aussage macht dies Sinn, da das Hinzufügen von mehr zum Nenner zu einem kleineren Ergebnis führt (z.B. 10/2) < 10/5), und wir haben festgestellt, dass Kombinationen kleiner sind als Permutationen.

Wenn Sie aufgepasst haben/meine Schrift Sinn ergibt, sollten wir bereits wissen, warum Sie (n-r)! zur Gleichung hinzufügen. Wenn nicht, drücken Sie Strg/Befehl +f „zu großer Bereich“ und lesen Sie die Passage noch einmal.

Wir fügen r! zum Nenner hinzu, weil es r! Möglichkeiten gibt, dass die Medaillengewinner gleich bleiben, während sich ihre Reihenfolge ändert.

Für jeden Satz von drei Medaillengewinnern können sie 3! mal umhergeschoben werden, um eine neue Permutation zu erzeugen (3! = 6 mal)…aber diese Permutation interessiert uns nicht. Diese 6 verschiedenen Permutationen sind in Wirklichkeit nur eine Kombination von Athleten, also wollen wir sie aus unserer Antwort herausziehen. Der einfachste Weg, dies zu tun, ist, sie zum Nenner zu addieren, so dass sie aus dem Zähler gezogen wird.

Es ist kein Zufall, dass 455 x 3! = 2730.

Alles in allem, das ist alles, was ich für heute habe. Hoffentlich macht das Sinn.

Ciao,