Järjestetty otos palauttaen

Järjestetty otos palauttaen eli k-permutaatio toistoja sallien muistuttaa tavallista k-permutaatiota, mutta sallimme, että perusjoukon M alkiot voivat toistua.

Määritelmä ja kaava

Aloitetaan klassisella esimerkillä: kuinka monta erilaista sanaa voimme muodostaa englannin aakkosten kirjaimista (abc … xyz, niitä on 26), kun sanan pituuden on oltava 6? Kuusi kirjainta ei ole paljon, mutta sanoja on silti melko monta. Emme välitä sanojen merkityksestä, joten myös ”weqrww” käy kuusikirjaimisesta sanasta.

Laskemiseen tarvitsemme vain kombinatoriikan tuloperiaatteen. Meillä on yhteensä 26 eri kirjainta, joita voimme käyttää. Ensimmäiselle paikalle voimme siis laittaa yhden 26 kirjaimesta. Myös toiselle paikalle voimme laittaa yhden 26 kirjaimesta, koska emme asettaneet ehtoa, ettei kirjain saa toistua. Päädymme siihen, että jokaisella paikalla valitsemme 26 kirjaimesta, ja järjestettyjen otosten kokonaismäärä on tuloperiaatteen mukaan 26⁶ = 308 915 776. Se on aika paljon, kun käytimme vain 26 kirjainta.

Sanomme, että k alkion järjestetty otos palauttaen joukosta M, jonka koko on n, on jokainen järjestetty k-monikko, jonka alkiot ovat joukosta M ja jonka jokainen alkio voi esiintyä k-monikossa jopa k kertaa. Jos siis M = {1, 2, 3}, kaikki nämä ovat kelvollisia 4 alkion järjestettyjä otoksia palauttaen: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). Tällaisten järjestettyjen otosten lukumäärä on

$$n^k.$$

Ratkaistuja esimerkkejä

1. Kuinka monta kuusinumeroista lukua voidaan muodostaa numeroista {2, 4, 6, 8}, kun numerot saavat toistua? Sijoitamme vain kaavaan, joukon koko on 4 ja valitsemme kuusikkoja:

   $$4^6=4096.$$

2. Tietokoneissa käytetään yleisesti binäärijärjestelmää eli lukujärjestelmää, jossa on vain numerot 0 ja 1. Siinä otetaan käyttöön uusia yksiköitä, esimerkiksi yksi bitti on eräänlainen solu, johon tallennetaan joko nolla tai ykkönen. Suurempi on tavu (englanniksi byte), jossa on 8 bittiä. Siis 1 on yksi bitti, kun taas 01110001 on yksi tavu. Kuinka monella eri tavalla yhden tavun 8 bittiä voi täyttää?

   Valitsemme joukosta {0, 1} eli kahdesta alkiosta. Valitsemme k-monikon, jonka koko on k = 8, joten kaikkien mahdollisuuksien lukumäärä on

   $$2^8=256.$$

3. Edellisestä esimerkistä tiedämme, että yksi tavu pystyy erottamaan jopa 256 eri arvoa. Kuinka monella tavalla voi täyttää 4 tavua?

   Neljässä tavussa on 4 · 8 = 32 bittiä, ja valitsemme edelleen kahden alkion joukosta. Tulos on siis:

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

   Näemme, että pelkät neljä tavua pystyvät erottamaan yli neljä miljardia arvoa. Vertailun vuoksi: nykyisten tietokoneiden levyt ovat satojen gigatavujen tai jopa teratavujen kokoisia. Yksi teratavu sisältää 1 000 000 000 000 tavua eli 8 000 000 000 000 bittiä. Teratavun levylle voimme siis tallentaa jopa 2^{8 000 000 000 000} eri arvoa.

   Huomautus: nykyisin kilotavun (megatavun jne.) käsitteessä vallitsee lievä sekaannus. Teknisistä syistä yksi kilotavu ei sisältänyt 1000 tavua, kuten muissa yksiköissä on tapana (yksi kilogramma on tuhat grammaa), vaan yksi kilotavu oli 2¹⁰ tavua eli 1024 tavua. Yksi megatavu oli sitten 2²⁰ tavua eli 2¹⁰ kilotavua.

   Nykyisin erotetaan kaksi merkintätapaa: 1 kB (luetaan kilotavu) on 1000 tavua ja 1 KiB (luetaan kibitavu) on 2¹⁰ = 1024 tavua.

4. Toinen esimerkki on omassa artikkelissaan, joka käsittelee salasanan turvallisuutta.