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

Hier ist die Kurzversion.

Nehmen wir als Beispiel das Klingeln in einer Kirche.

Eine Permutation ist eine Anordnung der Glocken. Sie finden die beste Reihenfolge heraus, um sie anzurufen.

Eine Kombination ist die Wahl der Glocken. Sie wählen die Glocken zum Läuten. Wenn Sie zu viele Glocken haben, wählen Sie diese zuerst aus und überlegen dann, sie zu bestellen.

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

Die Möglichkeit, rArtikel aus zu bestellen , nbesteht darin, zuerst rArtikel aus auszuwählen nund dann die rArtikel zu bestellen ( r!)

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

Aber möchten Sie wissen, wie Sie sich für immer daran erinnern können?

Ich bin ein großer Fan des Denkens nach ersten Prinzipien. Um ein Problem zu verstehen, gehen Sie zum Kern des Problems und argumentieren Sie von dort aus.

Wenn ich das nicht tue, ist das normalerweise verwirrend: Wenn ich nicht verstehe, wie die Dinge funktionieren, weiß ich nicht, wo ich die Konzepte aufhängen soll. Mein geistiger Rahmen ist nicht vollständig, deshalb entscheide ich mich, mich nur daran zu erinnern.

Wie Sie sich vorstellen können, ist dies nicht ideal. Von Zeit zu Zeit gönne ich mir also, Dinge aus der Quelle abzuleiten und eine Intuition dafür aufzubauen, wie Dinge funktionieren.

Dieses Mal bauen wir eine Intuition für Permutationen und Kombinationen auf.

Wissen Sie zum Beispiel, warum die Formel für eine Kombination (n C r) lautet? Von wo ist das gekommen? Und warum werden hier Fakultäten verwendet?

Beginnen wir an der Quelle. Factorials, Permutations und Combinations wurden von Mathematikern geboren, die zusammen spielten, ähnlich wie Steve Jobs und Steve Wozniak Apple gegründet haben, als sie zusammen in ihrer Garage spielten.

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

Vergiss alles, lass uns von unten nach oben denken.

Der erste bekannte interessante Anwendungsfall stammte aus Kirchen im 17. Jahrhundert.

Haben Sie sich gefragt, wie die Glocken in Kirchen geläutet werden? Es gibt eine Maschine, die sie der Reihe nach "klingelt". Wir haben auf Maschinen umgestellt, weil die Glocken zu groß sind. Es gibt auch Tonnen von Glocken.

Wie haben die Leute die beste Reihenfolge gefunden, um sie anzurufen? Was wäre, wenn sie die Dinge auf den Kopf stellen wollten? Wie konnten sie den besten Klang finden? Jeder Glockenturm hatte bis zu 16 Glocken!

Sie konnten nicht ändern, wie schnell Sie eine Glocke läuten konnten - die Maschinen klingelten nur eine Sekunde pro Sekunde. Das einzige, was Sie tun konnten, war die Reihenfolge der Glocken zu ändern. Bei dieser Herausforderung ging es also darum, die beste Reihenfolge herauszufinden.

Könnten wir unterwegs auch alle möglichen Bestellungen herausfinden? Wir möchten alle möglichen Bestellungen kennen, um herauszufinden, ob es sich lohnt, sie alle auszuprobieren.

Fabian Stedman, ein Klingelton, nahm diese Herausforderung an.

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

1 und 2.

oder

2 und 1.

Das machte Sinn. Es gab keinen anderen Weg.

Wie wäre es mit 3 Glocken?

1, 2 und 3.

1, 3 und 2.

Dann beginnend mit der zweiten Glocke,

2, 1 und 3.

2, 3 und 1.

Dann beginnend mit der dritten Glocke,

3, 1 und 2.

3, 2 und 1.

Insgesamt 6.

Dann stellte er fest, dass dies zwei Glocken sehr ähnlich war!

Wenn er die erste Glocke reparierte, gab es immer zwei Möglichkeiten, die verbleibenden zwei Glocken zu bestellen .

Auf wie viele Arten konnte er die erste Glocke reparieren? Jede der 3 Glocken könnte die eine sein!

Okay, er fuhr fort. Er erreichte dann 5 Glocken.

Zu diesem Zeitpunkt erkannte er, dass es unhandlich ist, Dinge von Hand zu tun. Sie haben nur so viel Zeit am Tag, Sie müssen Glocken läuten, Sie können nicht daran gehindert sein, alle möglichen Glocken herauszuziehen. Gab es eine Möglichkeit, dies schnell herauszufinden?

Er kehrte zu seiner Einsicht zurück.

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

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

Und er wusste, wie man das macht!

Also, Reihenfolge von 5 Glocken = 5 * Reihenfolge 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?

Fun Fact: Dies ist der Schlüssel für eine Programmiertechnik namens Rekursion.

Er tat es auch. Obwohl es viel länger dauerte, da niemand in seiner Nähe dies bereits entdeckt hatte. [2]

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

Diese Ordnungsformel wurde 1808 als Fakultät bekannt.

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

Diese Anordnung der Glocken wird als Permutation bezeichnet.

Eine Permutation ist eine Bestellung von Artikeln.

Wenn ich etwas lerne, denke ich, hilft es, Dinge aus jedem Blickwinkel zu betrachten, um das Verständnis zu festigen.

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

Wir haben 5 Felder, richtig?

Auf wie viele Arten können wir die erste Glocke 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 noch 4 Glocken übrig.

Die dritte Glocke? Nun, wir haben die ersten beiden ausgewählt, sodass nur noch 3 Glocken zur Auswahl stehen.

Die vierte Glocke? Nur noch 2 Glocken übrig, also 2 Optionen.

Die fünfte Glocke? Nur noch 1 übrig, also 1 Option.

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

Somit haben wir unsere erste allgemeine Formel.

Die Anzahl der Bestellmöglichkeiten für NArtikel beträgtN!

Die Permutation

Jetzt stehen wir vor einem anderen Problem. Der König befahl, für jede Kirche neue Glocken herzustellen. Manche sind nett, manche sind in Ordnung, manche werden dich taub machen. Aber jeder ist einzigartig. Jeder macht seinen eigenen Sound. Eine ohrenbetäubende Glocke, umgeben von schönen Glocken, kann majestätisch klingen.

Da unser Glockenturm jedoch immer noch 5 Glocken enthält, müssen wir die beste Bestellung aus 8 Glocken herausfinden, die die erfahrenen Glockenmacher hergestellt haben.

Mit der obigen Logik können wir fortfahren.

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

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

Am Ende erhalten wir 8 * 7 * 6 * 5 * 4mögliche Bestellungen von 8 Glocken in 5 Feldern.

Wenn Sie mit der Formelversion von (n P r) vertraut sind n! / (n-r)!, machen Sie sich keine Sorgen, wir werden das auch früh genug ableiten!

Eine schlechte Möglichkeit, dies abzuleiten, besteht darin, sowohl den Zähler als auch den Nenner mit 3 zu multiplizieren! in unserem obigen Beispiel -

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

Dies hilft uns jedoch nicht zu verstehen, warum diese Formel funktioniert. Bevor wir dort ankommen, werfen wir einen Blick auf die Auswahl der Dinge oder die Kombination.

Die Kombination

Jetzt, da wir wissen, wie man Dinge bestellt, können wir herausfinden, wie man Dinge auswählt!

Betrachten wir das gleiche Problem. Es gibt einen Glockenturm mit 5 Glocken und Sie haben 8 Glocken. Im Moment möchten Sie jedoch nicht die Reihenfolge der Glocken herausfinden (denken Sie daran, dass dies eine Permutation ist).

Stattdessen möchten Sie die 5 besten Glocken auswählen und jemand anderem mit besserem Musikgeschmack die Reihenfolge herausfinden lassen. Tatsächlich zerlegen wir das Problem in Teile: Zuerst finden wir heraus, welche Glocken wir wählen sollen. Als nächstes finden wir heraus, wie die ausgewählten Glocken bestellt werden.

Wie wählst du die Glocken aus? Dies ist die "Kombination" aus Permutationen und Kombination.

Die Kombination ist eine Auswahl. Du bist selektiv. Sie wählen 5 Glocken aus 8, die Ihre Handwerker hergestellt haben.

Da wir wissen, wie man Glocken bestellt, werden wir diese Informationen verwenden, um herauszufinden, wie man Glocken auswählt. Klingt unmöglich? Warten Sie, bis Sie die schöne Mathematik sehen.

Stellen wir uns vor, alle Glocken sind in einer Reihe.

Bevor wir alle Möglichkeiten zur Auswahl der Glocken finden, konzentrieren wir uns auf eine Möglichkeit zur Auswahl der Glocken.

Eine Möglichkeit besteht darin, zufällig 5 auszuwählen. Dies hilft uns nicht viel, das Problem zu lösen. Versuchen wir es also anders.

Wir setzen die Glocken in eine Linie und wählen die ersten 5. Dies ist eine Möglichkeit, die Glocken auszuwählen.

Beachten Sie, dass sich die Auswahl auch dann nicht ändert, wenn wir die Position der ersten 5 Glocken wechseln. Sie sind immer noch die gleiche Möglichkeit, 5 einzigartige Glocken auszuwählen.

Dies gilt auch für die letzten drei Glocken.

Nun, der schöne Mathe-Trick - für diese eine Möglichkeit, die 5 Glocken auszuwählen, wie lauten alle Ordnungen von 8 Glocken, bei denen wir genau diese 5 Glocken auswählen? Aus dem obigen Bild sind alle Ordnungen der 5 Glocken ( 5!) und alle Ordnungen der verbleibenden drei Glocken ( 3!) ersichtlich .

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

Was sind die insgesamt möglichen Bestellungen von 8 Glocken? 8!.

Denken Sie daran, dass wir für jede Auswahl der ersten 5 Glocken ( 5! * 3!) eine Reihenfolge von 8 Glocken haben, die dieselbe Auswahl ergeben.

Wenn wir dann die Anzahl der Möglichkeiten zur Auswahl der ersten 5 Glocken 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 

Damit,

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

In der Mathematik wird das:

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

Und siehe da, wir haben eine intuitive Erklärung gefunden, wie man 5 von 8 Dingen auswählt.

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

Was bedeutet, dass die restlichen Artikel sein werden N-R. Für eine Auswahl von RArtikeln haben wir also R! * (N-R)!Bestellungen, die dieselben RArtikel enthalten.

Für alle Arten der RArtikelauswahl haben wir N! / (R! * (N-R)!)Möglichkeiten.

Die Anzahl der Möglichkeiten zur Auswahl von rElementen nbeträgt(n C r) = n! / (r! * (n-r)!)

In umgangssprachlichen Begriffen wird auch (n C r) ausgesprochen n choose r, was dazu beiträgt, die Idee zu festigen, dass Kombinationen zur Auswahl von Elementen dienen.

Die Permutation - überarbeitet

Kommen wir mit der Kombination aus Staub und Staub zu Teil 2 unserer Arbeit 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 jetzt unsere Aufgabe, die perfekte Melodie zu finden, indem wir die Anzahl der Bestellungen herausfinden.

Aber das ist das Einfache. Wir wissen bereits, wie man 5 Artikel bestellt. Es ist 5!und wir sind fertig.

Um 5 von 8 Artikeln zu permutieren (zu bestellen), wählen wir zuerst 5 Artikel aus und bestellen dann die 5 Artikel.

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, rArtikel zu bestellen , nbeträgt(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 Auswahlmöglichkeiten sind.

Um N Elemente zu ordnen, haben wir zwei intuitive Möglichkeiten gefunden, um die Antwort herauszufinden. Beides führt zur Antwort N!.

Um 5 von 8 Elementen zu permutieren, müssen Sie zuerst die 5 Elemente auswählen und dann bestellen. Sie wählen mit (8 C 5)und bestellen dann die 5 mit 5!.

Und die Intuition für die Wahl Raus Nist , alle Ordnungen herauszufinden ( N!) und dividiert durch Anordnungen , wo die ersten Rund letzten N-Rgleich bleiben ( R!und (N-R)!).

Und das ist alles, was Permutationen und Kombinationen zu bieten haben.

Jede erweiterte Permutation und Kombination verwendet dies als Basis. Kombination mit Ersatz? Gleiche Idee. Permutation mit identischen Gegenständen? Gleiche Idee, nur die Anzahl der Bestellungen ändert sich, da einige Artikel identisch sind.

Wenn Sie interessiert sind, können wir in einem anderen Beispiel auf die komplexen Fälle eingehen. Lass es mich auf Twitter wissen.

Schauen Sie sich weitere Beiträge in meinem Blog an und nehmen Sie an der wöchentlichen Mailingliste teil.

Endnoten

  1. So stelle ich mir vor, dass er es herausgefunden hat. Nehmen Sie es nicht als Lektion in der Geschichte.
  2. Die Indianer hatten im 12. Jahrhundert 400 Jahre vor sich.