Kombination mit Wiederholung
Kapitoly: Kombinatorik, Variationen, Permutation, Kombination, Variationen mit Wiederholungen, Kombination mit Wiederholung, Wie viele verschiedene PINs gibt es, Taschenrechner.
Kombinationen mit Wiederholung sind ähnlich wie klassische Kombinationen, nur dass wir die Wiederholung von Elementen aus der Unterstützungsmenge M erlauben.
Definition und Formel
Beginnen wir mit einem schönen Beispiel: Sie gehen in einen Laden und wollen zwölf Flaschenbiere vom Fass kaufen. Es gibt insgesamt vier verschiedene Flaschen im Regal. Nun haben Sie mehrere Möglichkeiten, Flaschen zu kaufen - Sie können zum Beispiel 5 Pils, 2 Gambrinus und 1 Staropramen kaufen, oder Sie können von jedem Hersteller nur zwei Flaschen kaufen. Wie viele verschiedene Möglichkeiten gibt es insgesamt, um Flaschen zu kaufen, so dass man nur zwölf hat?
Wir haben also eine Grundmenge M = {Plzeň, Gambrinus, Staropramen, Kozel} und fragen uns, wie viele k-tic es gibt, bei denen k = 12, die Elemente aus der Menge M enthalten und bei denen die Reihenfolge keine Rolle spielt?
Die Herleitung der Formel ist schon etwas komplizierter als bei anderen kombinatorischen Problemen. Zunächst stellen wir uns unseren Einkauf als eine Folge von Nullen und Einsen vor, wobei die Anzahl der Einsen der Anzahl der bei einem bestimmten Hersteller gekauften Flaschen entspricht und die Null die Hersteller trennt. So sagt uns 111011101111101, dass wir drei Pilsner gekauft haben (die ersten drei 1en), dann drei Gambrinus (0 ist das Trennzeichen, die nächsten drei 1en), dann fünf Staropramen (0 ist das Trennzeichen, dann fünf 1en) und schließlich ein Kozel. Das ganze Prinzip ist in der folgenden Abbildung dargestellt:
$$ \underbrace{111}_{Plz}0\underbrace{111}_{Gam}0\underbrace{11111}_{Star}0\underbrace{1}_{Koz} $$
Wenn wir 6 Pilsner, 4 Gambrinus, 2 Kozlas und keine Staropramen kaufen wollten, sähe die Reihenfolge wie folgt aus:
$$ \underbrace{111111}_{Plz}0\underbrace{1111}_{Gam}00\underbrace{11}_{Koz} $$
Beachten Sie, dass die Länge dieser Folge immer gleich 15 ist - es müssen 12 1en sein, um insgesamt 12 Biere zu kaufen. Und es muss drei Trennzeichen geben, um vier verschiedene Hersteller trennen zu können. Es bleibt also zu berechnen, wie viele solcher Folgen der Länge 15 insgesamt existieren, die genau drei Nullen enthalten?
Wir müssen nur die Platzierung der Nullen berechnen - in dem Moment, in dem wir 3 Nullen unter die 12 Einsen setzen, haben wir eine gültige Kombination von Bieren. Mit anderen Worten: Wir haben insgesamt 15 Bierhütten, und wir müssen 3 davon mit Nullen besetzen. Die restlichen Fässer belegen wir automatisch mit Einsen.
Dies ist bereits ein einfaches Kombinationsproblem ohne Wiederholung. Wir nummerieren die 15 Schuppen mit {1, …, 15} und wählen nun immer drei Zahlen aus dieser Menge, was uns drei Indizes gibt, wo wir die Null platzieren. Für die Kombination {2, 4, 7} ergibt sich zum Beispiel die Folge: 101011011111111. Der 2., 4. und 7. Index sind Nullen, der Rest sind Einsen. Es gibt also insgesamt
$$ {15\choose3} = 455 $$
verschiedene Möglichkeiten, Nullen in den 15 Hütten zu platzieren, und somit 455 verschiedene Möglichkeiten, 12 Biere zu kaufen, wenn wir vier verschiedene Biere haben.
Wir können die vorangegangenen Überlegungen verallgemeinern. Wenn wir eine Menge von Elementen M der Größe n haben und daraus k-tice auswählen, und die Elemente sich wiederholen können, dann stellen wir eine Folge von Nullen und Einsen der Länge n + k − 1 zusammen (k Einsen und n − 1 Nullen) und finden heraus, an wie vielen Stellen wir n − 1 Nullen platzieren können, so dass die Anzahl der Kombinationen mit Wiederholung, bezeichnet als C'(k, n), gleich ist
$$ C'(k, n) = {n+k-1 \choose n-1} = {n+k-1\choose k}. $$
Die letzte Anpassung konnten wir aufgrund der grundlegenden Beziehungen zwischen den Kombinationszahlen vornehmen.
Gelöste Beispiele
- Auf wie viele Arten können 20 Freikarten für die Premiere von The Babel unter 10 Rentnerinnen aufgeteilt werden? Dies ist ein Beispiel für Kombinationen mit Wiederholung, da eine Rentnerin mehrere, möglicherweise sogar alle, Freikarten erhalten kann. Wir müssen nur die richtige Vorstellung davon bekommen, was n und was k ist. Tatsächlich wählen wir 20 Kombinationen von 10 Rentnern, mit anderen Worten, wir erstellen eine Folge von Nullen und Einsen, so dass die Folge die Länge 29 hat, 20 Einsen und 9 Nullen enthält. So n = 10, k = 20 Wir erhalten das Ergebnis:
$$ C'(10, 20) = {10 + 20 - 1 \choose 20} = 10{,}015,005. $$