Ordnet utvalg med tilbakelegging

Ordnet utvalg med tilbakelegging ligner på vanlig ordnet utvalg, bare at vi tillater at elementene fra den underliggende mengden M kan gjentas.

Definisjon og formel

Vi begynner med et klassisk eksempel: Hvor mange ulike ord kan vi lage av bokstavene i det engelske alfabetet (abc … xyz, det er 26 av dem) hvis ordet skal ha lengde 6? Seks bokstaver er ikke mye, men likevel blir det ganske mange ord. Vi bryr oss ikke om hva ordene betyr, så også «weqrww» regner vi som et gyldig ord med lengde seks.

For å regne ut dette trenger vi bare multiplikasjonsprinsippet. Vi har til sammen 26 ulike bokstaver vi kan bruke. På første plass kan vi altså sette én av 26 bokstaver. På andre plass kan vi også sette én av 26 bokstaver, for vi har ikke stilt noe krav om at bokstavene ikke kan gjentas. Dermed velger vi på hver plass blant 26 bokstaver, og det totale antallet ordnede utvalg er etter multiplikasjonsprinsippet 26⁶ = 308 915 776. Det er ganske mye, tatt i betraktning at vi bare brukte 26 bokstaver.

Vi sier at et ordnet utvalg med tilbakelegging av k elementer fra en mengde M med n elementer er et hvilket som helst ordnet k-tuppel der elementene er fra mengden M, og hvert element kan forekomme opptil k ganger i k-tuppelet. Hvis vi har mengden M = {1, 2, 3}, er alle disse gyldige ordnede utvalg med tilbakelegging av 4 elementer: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). Antallet slike ordnede utvalg med tilbakelegging er da lik

$$n^k.$$

Løste eksempler

1. Hvor mange sekssifrede tall kan vi sette sammen av sifrene {2, 4, 6, 8} hvis sifrene kan gjentas? Vi setter bare inn i formelen, mengden har 4 elementer, og vi velger sekstupler:

   $$4^6=4096.$$

2. I datamaskiner brukes vanligvis totallsystemet, altså et tallsystem som bare bruker sifrene 0 og 1. Der innføres nye enheter, for eksempel representerer én bit en slags celle der man lagrer enten null eller én. En større enhet er byte, som inneholder 8 bit. Så 1 er én bit, mens 01110001 er én byte. Hvor mange ulike måter finnes det å fylle én byte med 8 bit på?

   Vi velger fra mengden {0, 1}, altså fra to elementer. Vi velger et k-tuppel med lengde k = 8, så antallet muligheter er lik

   $$2^8=256.$$

3. Fra forrige eksempel vet vi at én byte kan skille mellom opptil 256 ulike verdier. Hvor mange måter finnes det å fylle 4 byte på?

   Fire byte inneholder 4 · 8 = 32 bit, og vi velger fortsatt fra en mengde med 2 elementer. Resultatet er altså:

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

   Vi ser at bare fire byte kan skille mellom over fire milliarder verdier. For å gi et bilde: Dagens datamaskiner har disker på flere hundre gigabyte eller til og med terabyte. Én terabyte inneholder 1 000 000 000 000 byte og dermed 8 000 000 000 000 bit. På en terabyte-disk kan vi altså lagre opptil 2^{8 000 000 000 000} ulike verdier.

   Merknad: I dag hersker det en viss forvirring om begrepet kilobyte (megabyte osv.). Av tekniske grunner var én kilobyte ikke lik 1000 byte, slik det pleier å være for andre enheter (ett kilogram er lik tusen gram), men én kilobyte var lik 2¹⁰ byte, altså 1024 byte. Én megabyte var da 2²⁰ byte eller 2¹⁰ kilobyte.

   I dag skiller vi mellom to skrivemåter: 1 kB (leses kilobyte) er 1000 byte, og 1 KiB (leses kibibyte) er 2¹⁰ = 1024 byte.

4. Et eksempel til finner du i en egen artikkel om passordsikkerhet.