Ordnat urval med återläggning

Ordnat urval med återläggning liknar vanligt ordnat urval, men vi tillåter att elementen ur den underliggande mängden M upprepas.

Definition och formel

Vi börjar med ett klassiskt exempel: hur många olika ord kan vi bilda av bokstäverna i det engelska alfabetet (abc … xyz, de är 26 stycken) om ordet ska ha längden 6? Sex bokstäver är inte mycket, men ändå blir det ganska många ord. Vi bryr oss inte om ordens betydelse, så även ”weqrww” räknar vi som ett giltigt ord med längden sex.

För att räkna ut det behöver vi bara känna till multiplikationsprincipen. Vi har totalt 26 olika bokstäver som vi kan använda. På första platsen kan vi alltså sätta en av 26 bokstäver. På andra platsen kan vi också sätta en av 26 bokstäver, eftersom vi inte har ställt något villkor om att bokstäverna inte får upprepas. Därmed kommer vi fram till att vi på varje position väljer ur 26 bokstäver, och det totala antalet ordnade urval är enligt multiplikationsprincipen 26⁶ = 308 915 776. Det är ganska mycket med tanke på att vi bara har använt 26 bokstäver.

Vi säger att ett ordnat urval med återläggning av k element ur en mängd M med storleken n är varje ordnad k-tipel vars element tillhör mängden M och där varje element kan förekomma upp till k gånger i k-tipeln. Om vi har mängden M = {1, 2, 3}, så är alla de här giltiga ordnade urval med återläggning av 4 element: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). Antalet sådana ordnade urval med återläggning är lika med

$$n^k.$$

Lösta exempel

1. Hur många sexsiffriga tal kan vi bilda av siffrorna {2, 4, 6, 8} om siffrorna får upprepas? Vi sätter helt enkelt in i formeln, mängden har storleken 4 och vi väljer sextiplar:

   $$4^6=4096.$$

2. I datorer används vanligen det binära talsystemet, dvs. ett talsystem som bara använder siffrorna 0 och 1. Där införs nya enheter, t.ex. en bit är ett slags cell där man lagrar antingen en nolla eller en etta. Större är en byte, som innehåller 8 bitar. Så 1 är en bit, medan 01110001 är en byte. På hur många olika sätt kan man fylla en byte med 8 bitar?

   Vi väljer ur mängden {0, 1}, dvs. ur två element. Vi väljer en k-tipel med storleken k = 8, så antalet möjligheter är lika med

   $$2^8=256.$$

3. Av föregående exempel vet vi att en byte kan skilja mellan upp till 256 olika värden. På hur många sätt kan man fylla 4 byte?

   Fyra byte innehåller 4 · 8 = 32 bitar, och vi väljer fortfarande ur en mängd med storleken 2. Resultatet är alltså:

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

   Vi ser att bara fyra byte kan skilja mellan över fyra miljarder värden. För att få en uppfattning: dagens datorer har hårddiskar på hundratals gigabyte eller till och med terabyte. En terabyte innehåller 1 000 000 000 000 byte och alltså 8 000 000 000 000 bitar. På en hårddisk på en terabyte kan vi därför lagra upp till 2^{8 000 000 000 000} olika värden.

   Anmärkning: för närvarande råder viss förvirring kring begreppet kilobyte (megabyte osv.). Av tekniska skäl innehöll en kilobyte inte 1000 byte, som är brukligt för andra enheter (ett kilogram är lika med tusen gram), utan en kilobyte var lika med 2¹⁰ byte, vilket är 1024 byte. En megabyte var då 2²⁰ byte, dvs. 2¹⁰ kilobyte.

   För närvarande skiljer vi alltså mellan två skrivsätt: 1 kB (utläses kilobyte) är 1000 byte och 1 KiB (utläses kibibyte) är 2¹⁰ = 1024 byte.

4. Ett annat exempel finns i en separat artikel om lösenordssäkerhet.