Kombinaatio palauttaen
Kombinaatio palauttaen eli toistokombinaatio muistuttaa tavallista kombinaatiota, mutta sallimme, että perusjoukon M alkiot voivat toistua.
Määritelmä ja kaava
Aloitetaan kivalla esimerkillä: menet kauppaan ja haluat ostaa mökkireissulle kaksitoista tölkkiolutta. Hyllyssä on yhteensä neljä eri olutta. Nyt sinulla on useita vaihtoehtoja, miten oluet ostat – voit ostaa esimerkiksi 5 Koffia, 2 Karhua, 1 Lapin Kultaa ja 4 Karjalaa tai voit ostaa jokaista merkkiä täsmälleen kolme tölkkiä. Kuinka monta eri tapaa ostaa oluet on yhteensä, kun niitä halutaan täsmälleen kaksitoista?
Meillä on siis perusjoukko M = {Koff, Karhu, Lapin Kulta, Karjala}, ja kysymme, kuinka monta k-monikkoa, missä k = 12, on olemassa, kun niiden alkiot ovat joukosta M eikä järjestyksellä ole väliä.
Kaavan johto on jo selvästi monimutkaisempi kuin muissa kombinatoriikan tehtävissä. Ensin kuvittelemme ostoksemme nollien ja ykkösten jonona niin, että ykkösten määrä vastaa kunkin merkin ostettujen tölkkien määrää ja nolla erottaa eri merkit toisistaan. Jono 111011101111101 kertoo siis, että ostimme kolme Koffia (kolme ensimmäistä ykköstä), sitten kolme Karhua (0 on erotin, seuraavat kolme ykköstä), sitten viisi Lapin Kultaa (0 erottimena ja sitten viisi ykköstä) ja lopuksi yhden Karjalan. Koko periaatteen näyttää seuraava kuva:
Jos haluaisimme ostaa 6 Koffia, 4 Karhua, 2 Karjalaa eikä yhtään Lapin Kultaa, jono näyttäisi tältä:
Huomaamme, että tämän jonon pituus on aina 15 – siinä täytyy olla 12 ykköstä, jotta ostamme yhteensä 12 olutta. Ja siinä täytyy olla kolme erotinta, jotta pystymme erottamaan neljä eri merkkiä. Jää laskettavaksi, kuinka monta tällaista 15 merkin pituista jonoa on olemassa, kun niissä on täsmälleen kolme nollaa.
Riittää laskea nollien sijoittelu – kun sijoitamme 3 nollaa 12 ykkösen sekaan, meillä on jokin kelvollinen olutyhdistelmä. Toisin sanoen: meillä on yhteensä 15 lokeroa, ja 3 niistä on täytettävä nollalla. Loput lokerot täytämme automaattisesti ykkösillä.
Tämä on jo yksinkertainen tehtävä kombinaatioista ilman palauttamista. Numeroimme 15 lokeroa luvuilla {1, …, 15} ja valitsemme nyt tästä joukosta aina kolmikoita, jolloin saamme kolme indeksiä, joihin sijoitamme nollan. Esimerkiksi kombinaatiosta {2, 4, 7} saisimme jonon: 101011011111111. Toisella, neljännellä ja seitsemännellä paikalla on nolla, loput ovat ykkösiä. Tapoja sijoittaa nollat 15 lokeroon on siis yhteensä
ja siten myös 455 eri mahdollisuutta ostaa 12 olutta, kun oluita on neljää eri lajia.
Edellisen päättelyn voi yleistää. Jos meillä on n alkion joukko M ja valitsemme siitä k-monikkoja niin, että alkiot voivat toistua, kokoamme nollien ja ykkösten jonon, jonka pituus on n + k − 1 (k ykköstä ja n − 1 nollaa), ja selvitämme, kuinka monella tavalla n − 1 nollaa voi sijoittaa. Kombinaatioiden palauttaen lukumäärä on siis
Viimeisen muokkauksen saimme tehdä binomikertoimien perusominaisuuksien ansiosta.
Ratkaistuja esimerkkejä
- Kuinka monella tavalla 20 ilmaista lippua teatterin ensi-iltaan voidaan jakaa 10 eläkeläisen kesken? Tämä on kombinaatio palauttaen -esimerkki, koska yksi eläkeläinen voi saada useita, mahdollisesti kaikki, ilmaislipuista. Meidän on vain ymmärrettävä oikein, mikä on n ja mikä k. Todellisuudessa valitsemme 20 alkion kombinaatioita 10 eläkeläisestä, toisin sanoen muodostamme nollien ja ykkösten jonon, jonka pituus on 29 ja jossa on 20 ykköstä ja 9 nollaa. Siis n = 10, k = 20. Saamme tuloksen:
Luvut: Kombinatoriikka, K-permutaatio, Permutaatio, Kombinaatio, Järjestetty otos palauttaen, Kombinaatio palauttaen, Kuinka monta erilaista PIN-koodia on olemassa?
