Variaties met herhaling

Variaties met herhaling lijken op de gewone variaties, alleen laten we nu toe dat elementen uit de onderliggende verzameling M herhaald worden.

Definitie en formule

We beginnen met een klassiek voorbeeld: hoeveel verschillende woorden kunnen we maken met de letters van het alfabet (abc … xyz, dat zijn er 26) als het woord 6 letters lang moet zijn? Zes letters is niet veel, toch zijn er heel wat van zulke woorden. De betekenis van de woorden interesseert ons niet, dus ook “weqrww” zien we als een geldig woord van zes letters.

Om dit te berekenen hebben we alleen de vermenigvuldigingsregel nodig. We hebben 26 verschillende letters die we kunnen gebruiken. Op de eerste plaats kunnen we dus een van de 26 letters zetten. Op de tweede plaats kunnen we ook een van de 26 letters zetten, want we hebben niet als voorwaarde gesteld dat letters niet herhaald mogen worden. Zo komen we erop uit dat we op elke plaats uit 26 letters kiezen, en het totale aantal variaties is volgens de vermenigvuldigingsregel dus 26⁶ = 308 915 776. Dat is nogal wat, terwijl we maar 26 letters gebruikten.

We noemen een variatie met herhaling van k elementen uit een verzameling M met n elementen elk geordend k-tal waarvan de elementen uit de verzameling M komen en waarin elk element tot wel k keer mag voorkomen. Als we dus de verzameling M = {1, 2, 3} hebben, dan zijn dit allemaal geldige variaties met herhaling van 4 elementen: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). Het aantal van zulke variaties met herhaling is dan gelijk aan

$$n^k.$$

Uitgewerkte voorbeelden

1. Hoeveel zescijferige getallen kunnen we maken met de cijfers {2, 4, 6, 8} als cijfers herhaald mogen worden? We vullen gewoon in de formule in: de verzameling heeft 4 elementen en we kiezen zestallen:

   $$4^6=4096.$$

2. In computers gebruikt men gewoonlijk het binaire talstelsel, dus een stelsel dat alleen de cijfers 0 en 1 gebruikt. Daar worden nieuwe eenheden ingevoerd, bijvoorbeeld één bit, een soort cel waarin je precies een nul of een één kunt opslaan. Groter is de byte, die 8 bits bevat. Dus 1 is één bit, terwijl 01110001 één byte is. Op hoeveel manieren kunnen we één byte met 8 bits vullen?

   We kiezen uit de verzameling {0, 1}, dus uit twee elementen. We kiezen een k-tal met k = 8, dus het aantal mogelijkheden is gelijk aan

   $$2^8=256.$$

3. Uit het vorige voorbeeld weten we dat één byte tot 256 verschillende waarden kan onderscheiden. Op hoeveel manieren kunnen we 4 bytes vullen?

   Vier bytes bevatten 4 · 8 = 32 bits en we kiezen nog steeds uit een verzameling van 2 elementen. Het resultaat is dus:

   $$2^{32}=4294967296.$$

   We zien dat slechts vier bytes al meer dan vier miljard waarden kunnen onderscheiden. Ter vergelijking: de huidige computers hebben schijven van honderden gigabytes of zelfs terabytes. Eén terabyte bevat 1 000 000 000 000 bytes en dus 8 000 000 000 000 bits. Op een schijf van een terabyte kunnen we dus tot 2^{8 000 000 000 000} verschillende waarden opslaan.

   Opmerking: op dit moment heerst er enige verwarring over het begrip kilobyte (megabyte enzovoort). Om technische redenen bevatte één kilobyte niet 1000 bytes, zoals gebruikelijk is bij andere eenheden (één kilogram is gelijk aan duizend gram), maar was één kilobyte gelijk aan 2¹⁰ bytes, en dat is 1024 bytes. Eén megabyte was dan 2²⁰ bytes, of ook 2¹⁰ kilobytes.

   Tegenwoordig onderscheiden we twee schrijfwijzen: 1 kB (we zeggen kilobyte) is 1000 bytes en 1 KiB (we zeggen kibibyte) is 2¹⁰ = 1024 bytes.

4. Nog een voorbeeld vind je in een apart artikel over de veiligheid van wachtwoorden.