Permutationen und Kombinationen berechnen – Vollständiger Leitfaden
Erfahren Sie, wie Sie Permutationen und Kombinationen mit klaren Formeln und Beispielen berechnen. Verstehen Sie, wann die Reihenfolge wichtig ist.
Zählprinzipien
Bevor wir in Permutationen und Kombinationen eintauchen, hilft es, zwei grundlegende Zählprinzipien zu verstehen. Das Multiplikationsprinzip besagt, dass wenn eine Aufgabe auf m Weisen erledigt werden kann und eine zweite unabhängige Aufgabe auf n Weisen, dann können beide zusammen auf m × n Weisen erledigt werden. Zum Beispiel: Wenn Sie 5 Hemden und 3 Hosen haben, können Sie 5 × 3 = 15 Outfits zusammenstellen. Das Additionsprinzip besagt, dass wenn ein Ereignis auf m Weisen und ein sich gegenseitig ausschließendes Ereignis auf n Weisen eintreten kann, die Gesamtzahl m + n beträgt.
Was ist eine Fakultät?
Die Fakultät einer nicht-negativen ganzen Zahl n, geschrieben n!, ist das Produkt aller positiven ganzen Zahlen von 1 bis n. Also 5! = 5 × 4 × 3 × 2 × 1 = 120. Per Konvention ist 0! = 1. Fakultäten wachsen extrem schnell: 10! = 3.628.800 und 20! ≈ 2,43 × 10¹⁸. Fakultäten erscheinen in den Formeln für Permutationen und Kombinationen, weil sie die Gesamtzahl der Möglichkeiten darstellen, n verschiedene Objekte anzuordnen. Das Verständnis von Fakultäten ist essenziell für die Kombinatorik.
Permutationen: Wenn die Reihenfolge wichtig ist
Eine Permutation ist eine Anordnung von Objekten, bei der die Reihenfolge wichtig ist. Die Anzahl der Möglichkeiten, r Objekte aus n verschiedenen Objekten anzuordnen, ist P(n, r) = n! / (n - r)!. Zum Beispiel: Die Anzahl der Möglichkeiten, Gold-, Silber- und Bronzemedaillen an 3 von 10 Athleten zu vergeben, ist P(10, 3) = 10! / 7! = 10 × 9 × 8 = 720. Jede Anordnung wird separat gezählt: Gold an Alice und Silber an Bob ist verschieden von Gold an Bob und Silber an Alice. Wenn r = n (alle Objekte anordnen), vereinfacht sich die Formel zu n!.
Kombinationen: Wenn die Reihenfolge nicht wichtig ist
Eine Kombination ist eine Auswahl von Objekten, bei der die Reihenfolge nicht wichtig ist. Die Anzahl der Möglichkeiten, r Objekte aus n verschiedenen Objekten auszuwählen, ist C(n, r) = n! / (r! × (n - r)!), auch geschrieben als „n über r". Zum Beispiel: Die Anzahl der Möglichkeiten, ein Komitee von 3 Personen aus einer Gruppe von 10 zu wählen, ist C(10, 3) = 10! / (3! × 7!) = 720 / 6 = 120. Der Unterschied zu Permutationen ist die Division durch r!, die berücksichtigt, dass jede Gruppe von r Objekten intern auf r! Weisen umgeordnet werden kann, die alle als dieselbe Kombination zählen.
Permutationen vs. Kombinationen: Wie man den Unterschied erkennt
Die Schlüsselfrage ist: Spielt die Reihenfolge der Auswahl eine Rolle? Wenn das Umordnen der gewählten Elemente ein anderes Ergebnis erzeugt, verwenden Sie Permutationen. Wenn das Umordnen dasselbe Ergebnis erzeugt, verwenden Sie Kombinationen. Rangfolgen, Reihenfolgen, Passwörter und Anordnungen sind Permutationsprobleme. Komitees, Teams, Gruppen und Sammlungen sind Kombinationsprobleme. Ein hilfreicher Test: Wenn Sie das Ergebnis als „Gruppe" oder „Menge" beschreiben würden, ist es eine Kombination; als „Reihenfolge" oder „Anordnung" ist es eine Permutation.
Permutationen mit Wiederholung
Wenn Wiederholung erlaubt ist, ändern sich die Formeln. Wenn Sie eine Anordnung von r Elementen aus n Typen erstellen, wobei jeder Typ mehrfach verwendet werden kann, ist die Anzahl n^r. Zum Beispiel: Eine 4-stellige PIN, bei der jede Ziffer 0-9 sein kann, hat 10⁴ = 10.000 Möglichkeiten. Eine andere Art der Permutation mit Wiederholung entsteht beim Anordnen von Objekten, bei denen einige identisch sind. Die Anzahl verschiedener Anordnungen von n Objekten mit n₁ eines Typs, n₂ eines anderen usw. ist n! / (n₁! × n₂! × ... × nₖ!). Zum Beispiel: Die Anzahl verschiedener Anordnungen der Buchstaben in „MISSISSIPPI" ist 11! / (1! × 4! × 4! × 2!) = 34.650.
Kombinationen mit Wiederholung
Kombinationen mit Wiederholung (auch Multimengen genannt) zählen die Anzahl der Möglichkeiten, r Elemente aus n Typen auszuwählen, wenn Wiederholung erlaubt ist und die Reihenfolge keine Rolle spielt. Die Formel ist C(n + r - 1, r) = (n + r - 1)! / (r! × (n - 1)!). Zum Beispiel: Die Anzahl der Möglichkeiten, 3 Kugeln Eis aus 5 Sorten zu wählen (mit Wiederholung), ist C(5 + 3 - 1, 3) = C(7, 3) = 35. Dieses Szenario wird oft mit der „Sterne und Striche"-Technik modelliert.
Anwendungen und Problemlösungstipps
Permutationen und Kombinationen werden umfassend in Wahrscheinlichkeit, Statistik, Informatik und alltäglicher Entscheidungsfindung verwendet. In der Wahrscheinlichkeit werden günstige und mögliche Ergebnisse oft mit diesen Formeln berechnet. In der Genetik bestimmen Kombinationen, wie Allele bei der Fortpflanzung zusammenkommen. In der Informatik treten Kombinationen in der Algorithmenanalyse und Optimierung auf. Beginnen Sie bei der Problemlösung damit, die Gesamtzahl der Objekte (n), die Anzahl der ausgewählten (r), ob die Reihenfolge wichtig ist und ob Wiederholung erlaubt ist, zu identifizieren.