Ordnet udvælgelse med tilbagelægning

Ordnet udvælgelse med tilbagelægning ligner almindelig ordnet udvælgelse, vi tillader bare, at elementerne fra den underliggende mængde M kan gentages.

Definition og formel

Vi begynder med et klassisk eksempel: hvor mange forskellige ord kan vi danne af bogstaverne i det engelske alfabet (abc … xyz, der er 26 af dem), hvis ordet skal have længden 6? Seks bogstaver er ikke mange, alligevel bliver der forholdsvis mange ord. Vi interesserer os ikke for ordenes betydning, så også »weqrww« regner vi som et gyldigt ord af længden seks.

Til beregningen skal vi kun kende multiplikationsprincippet. Vi har i alt 26 forskellige bogstaver, som vi kan bruge. På første plads kan vi sætte et af de 26 bogstaver. På anden plads kan vi også sætte et af de 26 bogstaver, for vi har ikke stillet den betingelse, at bogstaverne ikke må gentages. Dermed når vi frem til, at vi på hver plads vælger blandt 26 bogstaver, og det samlede antal udvælgelser er således ifølge multiplikationsprincippet 26⁶ = 308.915.776. Det er ret mange i betragtning af, at vi kun har brugt 26 bogstaver.

Vi siger, at en ordnet udvælgelse med tilbagelægning af r elementer fra en mængde M af størrelse n er ethvert ordnet r-tupel, hvis elementer er fra mængden M, og hvor hvert element kan forekomme op til r gange i r-tuplet. Hvis vi har mængden M = {1, 2, 3}, så er alle disse gyldige ordnede udvælgelser med tilbagelægning af 4 elementer: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). Antallet af sådanne ordnede udvælgelser med tilbagelægning, som vi betegner P'(n, r), er så lig med

$$P^{\prime }(n,r)=n^r.$$

Løste eksempler

1. Hvor mange sekscifrede tal kan der sammensættes af cifrene {2, 4, 6, 8}, hvis cifrene må gentages? Vi sætter bare ind i formlen, mængden har størrelsen 4, og vi vælger sekstupler:

   $$P^{\prime }(4,6)=4^6=4096.$$

2. I computere bruger man almindeligvis det binære talsystem, dvs. et talsystem, som kun bruger cifrene 0 og 1. Man indfører dér nye enheder, fx er én bit en slags celle, hvori man gemmer præcis enten nul eller et. Større er en byte, som indeholder 8 bit. Så 1 er én bit, mens 01110001 er én byte. Hvor mange forskellige måder er der at udfylde én byte med 8 bit på?

   Vi vælger fra mængden {0, 1}, dvs. fra to elementer. Vi vælger et r-tupel af størrelse r = 8, så antallet af alle muligheder er lig med

   $$P^{\prime }(2,8)=2^8=256.$$

3. Fra det forrige eksempel ved vi, at én byte kan skelne mellem op til 256 forskellige værdier. Hvor mange måder er der at udfylde 4 bytes på?

   Fire bytes indeholder 4 · 8 = 32 bit, vi vælger stadig fra en mængde af størrelse 2. Så resultatet er:

   $$P^{\prime }(2,32)=2^{32}=4.294.967.296.$$

   Vi ser, at blot fire bytes kan skelne mellem over fire milliarder værdier. For at give en forestilling: nutidens computere har diske på flere hundrede gigabyte eller direkte terabyte. Én terabyte indeholder 1.000.000.000.000 bytes og dermed 8.000.000.000.000 bit. På en terabytedisk er vi således i stand til at gemme op til 2^{8.000.000.000.000} forskellige værdier.

   Bemærkning: i øjeblikket hersker der en mild forvirring omkring begrebet kilobyte (megabyte osv.). Af tekniske grunde gjaldt det, at én kilobyte ikke indeholder 1000 bytes, som det er sædvane i andre enheder (ét kilogram er lig med et tusind gram), men én kilobyte var lig med 2¹⁰ bytes, hvilket er 1024 bytes. Én megabyte var så 2²⁰ bytes eller også 2¹⁰ kilobyte.

   I dag skelner vi således mellem to skrivemåder: 1 kB (læses kilobyte) er 1000 bytes, og 1 KiB (læses kibibyte) er 2¹⁰ = 1024 bytes.

4. Et andet eksempel findes i en selvstændig artikel om sikkerheden af adgangskoder.