Permutation vs. Kombination: Was ist der Unterschied zwischen der Permutationsformel und der Kombinationsformel?

Permutation vs. Kombination: Was ist der Unterschied zwischen der Permutationsformel und der Kombinationsformel?

Hier ist die Kurzfassung.

Nehmen wir als Beispiel das Läuten der Glocken in einer Kirche.

Eine Permutation ist eine Anordnung der Glocken. Man sucht die beste Reihenfolge für das Läuten aus.

Eine Kombination ist die Auswahl der Glocken. Du wählst die Glocken aus, die du läuten willst. Wenn du zu viele Glocken hast, wählst du sie zuerst aus und überlegst dann, wie du sie anordnen kannst.

Daraus ergibt sich die bekannte Identität: (n P r) = (n C r) * r!

Der Weg, r Gegenstände aus n zu ordnen, besteht darin, zuerst r Gegenstände aus n auszuwählen und dann die r Gegenstände zu ordnen (r! )

Und das bedeutet (n P r) = n! / (n-r)! und (n C r) = n! / ( (n-r)! * r! )

Aber willst du wissen, wie du dir das für immer merken kannst?

Ich bin ein großer Fan des Denkens nach ersten Prinzipien. Um ein Problem zu verstehen, muss man zum Kern vordringen und von dort aus weiterdenken.

Wenn ich das nicht tue, ist das meist die Quelle der Verwirrung: Wenn ich nicht verstehe, wie die Dinge funktionieren, weiß ich nicht, wo ich die Konzepte einordnen soll. Mein geistiges Gerüst ist nicht vollständig, also beschließe ich, es mir einfach zu merken.

Wie Sie sich vorstellen können, ist das nicht ideal. Deshalb mache ich von Zeit zu Zeit die Übung, Dinge aus der Quelle abzuleiten und eine Intuition dafür zu entwickeln, wie die Dinge funktionieren.

Diesmal geht es um die Entwicklung einer Intuition für Permutationen und Kombinationen.

Wissen Sie zum Beispiel, warum die Formel für eine Kombination (n C r) lautet? Woher kommt das? Und warum werden hier Faktoren verwendet?

Beginnen wir an der Quelle. Faktoren, Permutationen und Kombinationen wurden von Mathematikern beim gemeinsamen Spielen geboren, ähnlich wie Steve Jobs und Steve Wozniak Apple beim gemeinsamen Spielen in ihrer Garage gründeten.

Genauso wie Apple zu einem vollwertigen, profitablen Unternehmen wurde, wurde die einfache Fakultät, !, zum Atom eines ganzen Bereichs der Mathematik: der Kombinatorik.

Vergessen Sie alles, fangen wir an, von unten nach oben zu denken.

Der erste bekannte interessante Anwendungsfall kam von den Kirchen im 17. Jahrhundert.

Haben Sie sich gefragt, wie die Glocken in den Kirchen geläutet werden? Es gibt eine Maschine, die sie der Reihe nach „läutet“. Wir sind zu Maschinen übergegangen, weil die Glocken zu groß sind. Außerdem gibt es sehr viele Glocken.

Wie haben die Menschen die beste Reihenfolge für das Läuten der Glocken herausgefunden? Was ist, wenn man etwas anderes machen wollte? Wie konnte man den besten Klang finden? Jeder Glockenturm hatte bis zu 16 Glocken!

Man konnte nicht ändern, wie schnell man eine Glocke läuten konnte – die Maschinen läuteten nur eine Glocke pro Sekunde. Das Einzige, was man tun konnte, war, die Reihenfolge der Glocken zu ändern. Bei dieser Aufgabe ging es also darum, die beste Reihenfolge herauszufinden.

Könnten wir auf dem Weg dorthin auch alle möglichen Reihenfolgen herausfinden? Wir wollen alle möglichen Anordnungen kennen, um herauszufinden, ob es sich lohnt, sie alle auszuprobieren.

Ein Glöckner, Fabian Stedman, nahm diese Herausforderung an.

Er begann mit 2 Glocken. In welcher Reihenfolge könnte er diese Glocken läuten?

1 und 2.
oder
2 und 1.

Das machte Sinn. Es gab keine andere Möglichkeit.

Wie wäre es mit 3 Glocken?

1, 2, und 3.
1, 3, und 2.

Dann mit der zweiten Glocke beginnend,

2, 1, und 3.
2, 3, und 1.

Dann mit der dritten Glocke beginnend,

3, 1, und 2.
3, 2 und 1.

Gesamt 6.

Dann erkannte er, dass dies sehr ähnlich wie bei zwei Glocken war!

Wenn er die erste Glocke festlegte, dann war die Anzahl der Möglichkeiten, die verbleibenden zwei Glocken anzuordnen, immer zwei.

Wie viele Möglichkeiten konnte er die erste Glocke festlegen? Jede der 3 Glocken könnte die eine sein!

Okay, er machte weiter. Dann war er bei 5 Glocken angelangt.

Da merkte er, dass es unhandlich ist, Dinge von Hand zu machen. Man hat nur so viel Zeit am Tag, man muss die Glocken läuten, man kann sich nicht damit aufhalten, alle möglichen Glocken herauszuziehen. Gab es eine Möglichkeit, das schnell herauszufinden?

Er kehrte zu seiner Einsicht zurück.

Wenn er 5 Glocken hatte und die erste Glocke reparierte, musste er nur herausfinden, wie er 4 Glocken bestellen konnte.

Für 4 Glocken? Nun, wenn er 4 Glocken hatte und die erste Glocke reparierte, musste er nur herausfinden, wie er 3 Glocken bestellen konnte.

Und er wusste, wie man das macht!

So, Bestellung von 5 Glocken = 5 * Bestellung von 4 Glocken.

Bestellung von 4 Glocken = 4 * Bestellung von 3 Glocken

Bestellung von 3 Glocken = 3 * Bestellung von 2 Glocken.

. Sie sehen das Muster, nicht wahr?

Spaßfakt: Dies ist der Schlüssel für eine Programmiertechnik, die Rekursion genannt wird.

Er tat es auch. Allerdings brauchte er viel länger, da niemand in seiner Nähe dies bereits entdeckt hatte.

So fand er heraus, dass die Ordnung von 5 Glocken = 5 * 4 * 3 * 2 * 1 ist.

Diese Ordnungsformel wurde 1808 als Fakultät bekannt.

Wir denken an die Fakultät als Basis, aber die Idee existierte lange bevor sie einen Namen hatte. Erst als der französische Mathematiker Christian Kramp bemerkte, dass sie an einigen Stellen verwendet wurde, nannte er sie die Fakultät.

Diese Anordnung von Glocken wird Permutation genannt.

Eine Permutation ist eine Anordnung von Elementen.

Wenn man etwas lernt, denke ich, dass es hilft, die Dinge aus allen möglichen Blickwinkeln zu betrachten, um das Verständnis zu festigen.

Was wäre, wenn wir versuchen würden, die obige Formel direkt abzuleiten, ohne zu versuchen, das Problem auf eine geringere Anzahl von Glocken zu reduzieren?
Wir haben 5 Räume, richtig?

Wie viele Möglichkeiten gibt es, die erste Glocke zu wählen? 5, denn das ist die Anzahl der Glocken, die wir haben.

Die zweite Glocke? Nun, wir haben eine Glocke verbraucht, als wir sie in die erste Position gebracht haben, also haben wir 4 Glocken übrig.

Die dritte Glocke? Nun, wir haben die ersten beiden gewählt, also sind nur noch 3 Glocken zur Auswahl übrig.

Die vierte Glocke? Nur noch 2 Glocken, also 2 Möglichkeiten.
Die fünfte Glocke? Nur noch 1 übrig, also 1 Möglichkeit.

Und da haben wir es, die Gesamtzahl der Ordnungen ist 5 * 4 * 3 * 2 * 1

Damit haben wir unsere erste allgemeine Formel.

Die Anzahl der Möglichkeiten, N Gegenstände zu bestellen, ist N!

Nun stehen wir vor einem anderen Problem. Der König hat für jede Kirche neue Glocken anfertigen lassen. Manche sind schön, manche sind okay, von manchen wird man taub. Aber jede von ihnen ist einzigartig. Jede macht ihren eigenen Klang. Eine ohrenbetäubende Glocke, die von schönen Glocken umgeben ist, kann majestätisch klingen.

Aber unser Glockenturm fasst immer noch 5 Glocken, also müssen wir herausfinden, welche der 8 Glocken, die die geschickten Glockengießer gemacht haben, wir am besten bestellen sollen.

Nach der obigen Logik können wir vorgehen.

Für die erste Glocke können wir eine beliebige der 8 Glocken wählen.

Für die zweite Glocke können wir eine beliebige der verbleibenden 7 Glocken wählen… und so weiter.

Am Ende erhalten wir 8 * 7 * 6 * 5 * 4 mögliche Anordnungen von 8 Glocken in 5 Räumen.

Wenn du mit der Formelversion von (n P r) vertraut bist, die n! / (n-r)! ist, mach dir keine Sorgen, wir werden das auch noch früh genug herleiten!

Eine schlechte Art der Herleitung ist es, sowohl den Zähler als auch den Nenner mit 3 zu multiplizieren! In unserem obigen Beispiel –

erhalten wir 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 = 8! / 3!.

Aber das hilft uns nicht zu verstehen, warum diese Formel funktioniert. Bevor wir dazu kommen, werfen wir einen Blick auf die Auswahl von Dingen, oder die Kombination.

Die Kombination

Nun, da wir wissen, wie man Dinge anordnet, können wir herausfinden, wie man Dinge auswählt!

Betrachten wir das gleiche Problem. Es gibt einen Glockenturm mit 5 Glocken, und du hast 8 Glocken. Aber im Moment willst du nicht die Reihenfolge der Glocken herausfinden (das ist eine Permutation).

Stattdessen willst du die 5 besten Glocken auswählen und jemand anderen mit besserem Musikgeschmack die Reihenfolge herausfinden lassen. Im Grunde genommen zerlegen wir das Problem in zwei Teile: Zuerst finden wir heraus, welche Glocken wir auswählen sollen. Als nächstes überlegen wir uns, wie wir die gewählten Glocken anordnen.

Wie wählt man die Glocken aus? Das ist die „Kombination“ aus Permutationen und Kombination.

Die Kombination ist eine Auswahl. Du bist wählerisch. Du wählst 5 Glocken aus 8 Glocken aus, die deine Handwerker hergestellt haben.

Da wir wissen, wie man Glocken bestellt, werden wir diese Information nutzen, um herauszufinden, wie man Glocken auswählt. Klingt unmöglich? Warte, bis du die schöne Mathematik siehst, die damit verbunden ist.

Stellen wir uns vor, dass alle Glocken in einer Reihe liegen.

Bevor wir alle Möglichkeiten finden, die Glocken auszuwählen, wollen wir uns auf eine Möglichkeit konzentrieren.

Eine Möglichkeit ist, 5 beliebige auszuwählen. Das hilft uns bei der Lösung des Problems nicht weiter, also versuchen wir eine andere Möglichkeit.

Wir stellen die Glocken in einer Reihe auf und wählen die ersten 5 aus. Das ist eine Möglichkeit, die Glocken auszuwählen.

Beachte, dass sich die Auswahl nicht ändert, auch wenn wir die Positionen der ersten 5 Glocken tauschen. Es sind immer noch dieselben 5 einzigartigen Glocken.

Das gilt auch für die letzten drei Glocken.

Jetzt kommt der schöne mathematische Trick – für diese eine Möglichkeit, die 5 Glocken zu wählen, was sind alle Reihenfolgen von 8 Glocken, bei denen wir genau diese 5 Glocken wählen? In der obigen Abbildung sind es alle Anordnungen der 5 Glocken (5!) und alle Anordnungen der restlichen drei Glocken (3!).

Damit haben wir für jede einzelne Möglichkeit, 5 Glocken auszuwählen, (5! * 3!) Anordnungen von 8 Glocken.

Was sind die gesamten möglichen Anordnungen von 8 Glocken? 8!.

Denken Sie daran, dass wir für jede Wahl der ersten 5 Glocken (5! * 3!) Ordnungen von 8 Glocken haben, die die gleiche Wahl ergeben.

Wenn wir dann die Anzahl der Möglichkeiten, die ersten 5 Glocken zu wählen, mit allen möglichen Ordnungen einer Wahl multiplizieren, sollten wir die Gesamtzahl der Ordnungen erhalten.

Ways to choose 5 bells * orderings of one choice = Total orderings

So,

Ways to choose 5 bells = the total possible orderings / total orderings of one choice.

In der Mathematik wird daraus:

(8 C 5) = 8! / ( 5! * 3!)

Siehe da, wir haben eine intuitive Erklärung dafür gefunden, wie man 5 Dinge aus 8 auswählen kann.

Nun können wir das verallgemeinern. Wenn wir N Dinge haben und R davon auswählen wollen, bedeutet das, dass wir eine Linie bei R ziehen.

Das bedeutet, dass die verbleibenden Dinge N-R sind. Für eine Auswahl von R Gegenständen haben wir also R! * (N-R)! Anordnungen, die die gleichen R Gegenstände ergeben.

Für alle Möglichkeiten, R Gegenstände auszuwählen, haben wir N! / (R! * (N-R)!) Möglichkeiten.

Die Anzahl der Möglichkeiten, r Gegenstände aus n auszuwählen, ist (n C r) = n! / (r! * (n-r)!)

Umgangssprachlich wird (n C r) auch n choose r ausgesprochen, was die Idee verfestigt, dass Kombinationen zum Auswählen von Gegenständen dienen.

Die Permutation – revisited

Wenn die Kombination erledigt ist, kommen wir zu Teil 2 unserer Aufgabe zurück. Unser lieber Freund hat die besten 5 Glocken ausgewählt, indem er alle möglichen Kombinationen von 5 Glocken herausgefunden hat.

Es ist nun unsere Aufgabe, die perfekte Melodie zu finden, indem wir die Anzahl der Ordnungen herausfinden.

Aber das ist der einfache Teil. Wir wissen bereits, wie man 5 Artikel bestellen kann. Es ist 5!, und wir sind fertig.

Um also 5 Elemente aus 8 zu permutieren (zu ordnen), wählen wir zuerst 5 Elemente aus und ordnen dann die 5 Elemente.

Mit anderen Worten,

(8 P 5) = (8 C 5) * 5!

Und wenn wir die Formel erweitern, (8 P 5) = (8! / ( 5! * 3!)) * 5!

(8 P 5) = 8! / 3!.

Und wir haben den Kreis zu unserer ursprünglichen Formel geschlossen, die richtig abgeleitet wurde.

Die Anzahl der Möglichkeiten, r Elemente aus n zu ordnen, ist (n P r) = n! / (n-r)!

Unterschied zwischen Permutation und Kombination

Ich hoffe, dies macht den Unterschied zwischen Permutationen und Kombinationen kristallklar.

Permutationen sind Ordnungen, während Kombinationen Wahlmöglichkeiten sind.

Um N Elemente zu ordnen, haben wir zwei intuitive Wege gefunden, die Antwort herauszufinden. Beide führen zu der Antwort N!.

Um 5 von 8 Elementen zu permutieren, muss man zuerst die 5 Elemente auswählen und sie dann ordnen. Du wählst mit (8 C 5), dann ordnest du die 5 mit 5!.

Und die Intuition für die Wahl von R aus N besteht darin, alle Ordnungen (N!) herauszufinden und durch Ordnungen zu teilen, bei denen das erste R und das letzte N-R gleich bleiben (R! und (N-R)!).

Und das ist alles, was es an Permutationen und Kombinationen gibt.

Jede fortgeschrittene Permutation und Kombination verwendet dies als Basis. Kombinationen mit Ersatz? Gleiche Idee. Permutation mit identischen Elementen? Gleiche Idee, nur die Anzahl der Reihenfolgen ändert sich, da einige Elemente identisch sind.

Wenn Sie Interesse haben, können wir in einem weiteren Beispiel auf die komplexen Fälle eingehen. Lassen Sie es mich auf Twitter wissen.

Sehen Sie sich weitere Beiträge in meinem Blog an und tragen Sie sich in die wöchentliche Mailingliste ein.

Abschlussbemerkungen

1. So hat er es wohl herausgefunden. Nimm es nicht als Lektion in Geschichte.
2. Die Indianer hatten im 12. Jahrhundert, 400 Jahre vor ihm.