Kombination mit Wiederholung
Die Kombinationen mit Wiederholung ähneln den klassischen Kombinationen, wir erlauben nur, dass sich die Elemente der Grundmenge M wiederholen dürfen.
Definition und Formel
Wir beginnen mit einem schönen Beispiel: Du kommst in einen Laden und willst für einen Ausflug zwölf Flaschen Bier kaufen. Im Regal gibt es insgesamt vier verschiedene Sorten. Nun hast du mehrere Möglichkeiten, die Flaschen zu kaufen – du kannst zum Beispiel 5 Pils, 2 Weizen, 1 Helles und 4 Dunkle kaufen oder von jeder Sorte genau drei Flaschen. Wie viele verschiedene Möglichkeiten gibt es insgesamt, die Flaschen so zu kaufen, dass du genau zwölf hast?
Wir haben also die Grundmenge M = {Pils, Weizen, Helles, Dunkel} und fragen, wie viele k-Tupel mit k = 12 es gibt, die Elemente aus der Menge M enthalten und bei denen es nicht auf die Reihenfolge ankommt.
Die Herleitung der Formel ist schon etwas komplizierter als bei den anderen kombinatorischen Aufgaben. Zuerst stellen wir uns unseren Einkauf als Folge von Nullen und Einsen vor, und zwar so, dass die Anzahl der Einsen der Anzahl der gekauften Flaschen der jeweiligen Sorte entspricht und eine Null die einzelnen Sorten trennt. Die Folge 111011101111101 sagt uns also, dass wir drei Pils gekauft haben (die ersten drei Einsen), dann drei Weizen (0 ist das Trennzeichen, die nächsten drei Einsen), dann fünf Helle (0 als Trennzeichen und dann fünf Einsen) und schließlich ein Dunkles. Das ganze Prinzip zeigt die folgende Abbildung:
Wollten wir 6 Pils, 4 Weizen, 2 Dunkle und kein Helles kaufen, sähe die Folge so aus:
Beachte, dass die Länge dieser Folge immer 15 beträgt – es müssen 12 Einsen darin sein, damit wir insgesamt 12 Flaschen kaufen. Und es müssen drei Trennzeichen darin sein, damit wir vier verschiedene Sorten voneinander trennen können. Es bleibt also zu berechnen, wie viele solcher Folgen der Länge 15 es gibt, die genau drei Nullen enthalten.
Es genügt, die Positionen der Nullen zu berechnen – sobald wir zwischen 12 Einsen 3 Nullen verteilt haben, haben wir eine gültige Zusammenstellung der Flaschen. Mit anderen Worten: Wir haben insgesamt 15 Plätze und 3 davon müssen wir mit einer Null besetzen. Die übrigen Plätze besetzen wir automatisch mit Einsen.
Das ist schon eine einfache Aufgabe zu Kombinationen ohne Wiederholung. Wir nummerieren die 15 Plätze mit den Zahlen {1; …; 15} und wählen nun aus dieser Menge immer Dreiergruppen von Zahlen aus, wodurch wir drei Indizes erhalten, an die wir die Null setzen. Für die Kombination {2; 4; 7} erhielten wir z. B. die Folge: 101011011111111. An der 2., 4. und 7. Stelle steht eine Null, der Rest sind Einsen. Es gibt also insgesamt
verschiedene Möglichkeiten, die Nullen auf 15 Plätze zu verteilen, und damit auch 455 verschiedene Möglichkeiten, 12 Flaschen Bier einzukaufen, wenn wir vier verschiedene Sorten haben.
Die vorige Überlegung können wir verallgemeinern. Haben wir eine Menge M der Größe n und wählen aus ihr k-Tupel aus, wobei sich die einzelnen Elemente wiederholen dürfen, dann bilden wir eine Folge von Nullen und Einsen der Länge n + k − 1 (k Einsen und n − 1 Nullen) und bestimmen, auf wie viele Arten wir n − 1 Nullen verteilen können. Die Anzahl der Kombinationen mit Wiederholung, die wir mit C'(k; n) bezeichnen, ist daher gleich
Die letzte Umformung konnten wir uns dank der grundlegenden Beziehungen zwischen den Binomialkoeffizienten erlauben.
Gelöste Beispiele
- Auf wie viele Arten lassen sich 20 Freikarten für die Premiere eines Films unter 10 Rentnerinnen verteilen? Das ist ein Beispiel für Kombinationen mit Wiederholung, denn eine Rentnerin kann mehrere, potenziell alle, Freikarten bekommen. Wir müssen uns nur richtig klarmachen, was n und was k ist. In Wirklichkeit wählen wir Kombinationen von 20 aus 10 Rentnerinnen, mit anderen Worten bilden wir eine Folge von Nullen und Einsen, die die Länge 29 hat und 20 Einsen und 9 Nullen enthält. Also n = 10, k = 20. Wir erhalten das Ergebnis:
Kapitel: Kombinatorik, Variationen, Permutationen, Kombinationen, Variation mit Wiederholung, Kombination mit Wiederholung, Wie viele verschiedene PINs gibt es?
