Variationen mit Wiederholungen

Variationen mit Wiederholung sind ähnlich wie klassische Variationen, nur dass wir Elemente aus der Unterstützungsmenge M wiederholen lassen.

Definition und Formel

Beginnen wir mit einem klassischen Beispiel: Wie viele verschiedene Wörter können wir aus den Buchstaben des englischen Alphabets (abc ... xyz, es sind 26) bilden, wenn das Wort 6 Buchstaben lang sein soll? Sechs Buchstaben sind nicht viel, und doch wird es eine ganze Reihe von Wörtern geben. Wir kümmern uns nicht um die Bedeutung der Wörter, also nehmen wir auch "weqrww" als gültiges Wort der Länge sechs.

Wir müssen nur die Regel des kombinatorischen Produkts kennen, um die Berechnung durchzuführen. Wir haben insgesamt 26 verschiedene Buchstaben, die wir verwenden können. Wir können also einen der 26 Buchstaben an die erste Stelle setzen. Wir können aber auch einen der 26 Buchstaben an die zweite Stelle setzen, weil wir nicht die Bedingung gestellt haben, dass sich die Buchstaben nicht wiederholen dürfen. Dies bringt uns zu der Tatsache, dass wir in jeder Position aus 26 Buchstaben wählen und die Gesamtzahl der Variationen nach der Produktregel 26⁶ = 308 915 776 beträgt. Dies ist ziemlich viel für die Tatsache, dass wir nur 26 Buchstaben verwendet haben.

Wir sagen, dass eine k-Element-Variation mit Wiederholung aus der Menge M der Größe n jedes geordnete k-Würfelchen ist, dessen Elemente aus der Menge M stammen und jedes Element bis zu k-mal im k-Würfelchen vorkommen kann. Wenn wir also eine Menge M = {1, 2, 3} haben, dann sind dies alle gültigen 4-gliedrigen Varianten mit Wiederholung: [1, 1, 1, 1], [1, 2, 3, 1], [2, 2, 3, 3]. Die Anzahl solcher Varianten mit Wiederholung, bezeichnet mit V'(k, n), ist dann gleich

$$ V'(k, n) = n^k. $$

Gelöste Beispiele

1. Wie viele sechsstellige Zahlen lassen sich aus den Ziffern {2, 4, 6, 8} bilden, wenn sich die Ziffern wiederholen können? Setzen Sie einfach die Formel ein, die Menge hat die Größe 4, und wählen Sie Sechser:

   $$ V'(6, 4) = 4^6=4096. $$

2. In Computern wird üblicherweise ein binäres Zahlensystem verwendet, d. h. ein System, das nur die Ziffern 0 und 1 verwendet. Es werden neue Einheiten eingeführt, z. B. stellt ein Bit eine Art Zelle dar, in der man nur entweder Null oder Eins speichert. Die größere Einheit ist das Byte, das 8 Bits enthält. 1 ist also ein Bit, während 01110001 ein Byte ist. Wie viele verschiedene Möglichkeiten gibt es, ein Byte mit 8 Bits zu füllen?

   Wir wählen aus der Menge {0, 1}, d.h. zwei Elemente. Wir wählen k- dies ist die Größe von k = 8, also ist die Anzahl aller Möglichkeiten gleich

   $$ V'(8, 2) = 2^8 = 256. $$

3. Aus dem vorherigen Beispiel wissen wir, dass ein einziges Byte bis zu 256 verschiedene Werte auflösen kann. Wie viele Möglichkeiten gibt es, 4 Bytes zu füllen?

   Die vier Bytes enthalten 4 · 8 = 32 Bits, die immer noch aus einer Menge der Größe 2 ausgewählt werden. Das Ergebnis ist also:

   $$ V'(32, 2) = 2^{32} = 4{,}294,967{,}296. $$

   Wir können sehen, dass nur vier Bytes über vier Milliarden Werte unterscheiden können. Zur Veranschaulichung: Heutige Computer haben Festplatten mit Hunderten von Gigabyte oder sogar Terabyte. Ein Terabyte enthält 1 000 000 000 000 Bytes und damit 8 000 000 000 000 Bits. Wir können also bis zu 2^{8 000 000 000 000} verschiedene Werte auf einer Terabyte-Festplatte speichern.

   Hinweis: Der Begriff Kilobyte (Megabyte usw.) ist derzeit etwas verwirrend. Aus technischen Gründen umfasste ein Kilobyte nicht 1000 Byte, wie es in anderen Einheiten üblich ist (ein Kilogramm entspricht tausend Gramm), sondern ein Kilobyte entsprach 2¹⁰ Byte, also 1024 Byte. Ein Megabyte war dann 2²⁰ Bytes oder auch 2¹⁰ Kilobytes.

   Daher unterscheiden wir heute zwei Arten der Notation: 1 kB (gelesenes Kilobyte) entspricht 1000 Byte und 1 KiB (gelesenes Kibyte) entspricht 2¹⁰ = 1024 Byte.

4. Ein weiteres Beispiel finden Sie in einem separaten Artikel über die Sicherheit von Passwörtern.

Ressourcen und weiterführende Literatur

• Kombinatorik auf cuni.cz
• Bělohlávek, Vychodil: Diskrete Mathematik [PDF]