Variation mit Wiederholung

Die Variationen mit Wiederholung ähneln den klassischen Variationen, wir erlauben nur, dass sich die Elemente der Grundmenge M wiederholen dürfen.

Definition und Formel

Wir beginnen mit einem klassischen Beispiel: Wie viele verschiedene Wörter können wir aus den Buchstaben des lateinischen Alphabets (abc … xyz, es sind 26) bilden, wenn das Wort die Länge 6 haben soll? Sechs Buchstaben sind nicht viel, trotzdem wird es erstaunlich viele solcher Wörter geben. Die Bedeutung der Wörter interessiert uns nicht, also zählt auch „weqrww“ als gültiges Wort der Länge sechs.

Für die Berechnung brauchen wir nur die Produktregel. Wir haben insgesamt 26 verschiedene Buchstaben, die wir verwenden können. An die erste Stelle können wir also einen von 26 Buchstaben setzen. An die zweite Stelle können wir aber ebenfalls einen von 26 Buchstaben setzen, denn wir haben keine Bedingung gestellt, dass sich die Buchstaben nicht wiederholen dürfen. So kommen wir darauf, dass wir an jeder Position aus 26 Buchstaben auswählen, und die Gesamtzahl der Variationen ist nach der Produktregel 26⁶ = 308.915.776. Das ist ziemlich viel, wenn man bedenkt, dass wir nur 26 Buchstaben verwendet haben.

Wir sagen, dass eine Variation von k aus n Elementen mit Wiederholung aus einer Menge M der Größe n jedes geordnete k-Tupel ist, dessen Elemente aus der Menge M stammen und in dem jedes Element bis zu k-mal vorkommen kann. Haben wir also die Menge M = {1; 2; 3}, dann sind alle diese Tupel gültige Variationen von 4 aus 3 Elementen mit Wiederholung: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). Die Anzahl solcher Variationen mit Wiederholung, die wir mit V'(k; n) bezeichnen, ist dann gleich

$$V^{\prime }(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 dürfen? Wir setzen einfach in die Formel ein, die Menge hat die Größe 4 und wir wählen Sechser-Tupel aus:

   $$V^{\prime }(6;4)=4^6=4096.$$

2. In Computern wird üblicherweise das Binärsystem verwendet, also ein Zahlensystem, das nur die Ziffern 0 und 1 benutzt. Dort werden neue Einheiten eingeführt, z. B. stellt ein Bit eine Art Zelle dar, in der man genau entweder eine Null oder eine Eins speichert. Größer ist das Byte, das 8 Bit enthält. 1 ist also ein Bit, während 01110001 ein Byte ist. Wie viele verschiedene Möglichkeiten gibt es, ein Byte mit 8 Bit zu füllen?

   Wir wählen aus der Menge {0; 1}, also aus zwei Elementen. Wir wählen ein k-Tupel der Größe k = 8, also ist die Anzahl aller Möglichkeiten gleich

   $$V^{\prime }(8;2)=2^8=256.$$

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

   Vier Byte enthalten 4 · 8 = 32 Bit, wir wählen weiterhin aus einer Menge der Größe 2. Das Ergebnis ist also:

   $$V^{\prime }(32;2)=2^{32}=4.294.967.296.$$

   Wir sehen, dass gerade einmal vier Byte über vier Milliarden Werte unterscheiden können. Zur Vorstellung: Heutige Computer haben Festplatten mit einer Größe von Hunderten Gigabyte oder gleich von Terabyte. Ein Terabyte enthält 1.000.000.000.000 Byte und somit 8.000.000.000.000 Bit. Auf einer Terabyte-Festplatte können wir also bis zu 2^{8.000.000.000.000} verschiedene Werte speichern.

   Anmerkung: Heutzutage herrscht eine leichte Verwirrung beim Begriff Kilobyte (Megabyte usw.). Aus technischen Gründen enthielt ein Kilobyte nicht 1000 Byte, wie es bei den anderen Einheiten üblich ist (ein Kilogramm entspricht tausend Gramm), sondern ein Kilobyte war gleich 2¹⁰ Byte, das sind 1024 Byte. Ein Megabyte war dann 2²⁰ Byte oder auch 2¹⁰ Kilobyte.

   Heutzutage unterscheiden wir daher zwei Schreibweisen: 1 kB (gesprochen Kilobyte) sind 1000 Byte und 1 KiB (gesprochen Kibibyte) sind 2¹⁰ = 1024 Byte.

4. Ein weiteres Beispiel findet sich in einem eigenen Artikel über die Sicherheit von Passwörtern.