Kombinaatio ja permutaatio

Seuraa 
Viestejä4
Liittynyt28.8.2006

Hei,
Kombinaatio ja permutaatio sellaisesta joukosta, jonka kaikki alkiot ovat erilaisia, on triviaali juttu.

Mutta mitenhän nuo lasketaan, jos joukkoon laitetaan aina takaisin otettu alkio?
Esim: kuinka monta erilaista viisikirjaimista salasanaa voidaan muodostaa merkkijonosta 'ABCDEFGHIJ'?
(eli mahdollisia kombinaatioita olisi siten myös 'AAAEJ','BBCCI','CCCCC' jne ja mahdollisia permutaatioita
olisi siten myös 'AAABB','BBAAA','AABBA' jne)

Entäs jos salasanoissa saisi olla vain n kpl samoja merkkejä jolloin kysymys olisi:
kuinka monta erilaista viisikirjaimista salasanaa, joissa saa olla korkeintaan kaksi samaa merkkiä,
voidaan muodostaa merkkijonosta 'ABCDEFGHIJ'? Tällöin sallittu kombinaatio olisi 'AABBC' mutta
kombinaatiot 'AAABB','BBAAA','AABBA' ei-sallittuja.

Allekirjoitus

Kommentit (3)

Vierailija
vesa
Hei,
Kombinaatio ja permutaatio sellaisesta joukosta, jonka kaikki alkiot ovat erilaisia, on triviaali juttu.

Mutta mitenhän nuo lasketaan, jos joukkoon laitetaan aina takaisin otettu alkio?
Esim: kuinka monta erilaista viisikirjaimista salasanaa voidaan muodostaa merkkijonosta 'ABCDEFGHIJ'?
(eli mahdollisia kombinaatioita olisi siten myös 'AAAEJ','BBCCI','CCCCC' jne ja mahdollisia permutaatioita
olisi siten myös 'AAABB','BBAAA','AABBA' jne)




Tämä on helpompi, kuin osaat ajatellakaan. En nyt kerro suoraa vastausta, mutta ajattele tältä kannalta:
Erilaisia numeroja on kymmenen kappaletta (0,1,2,...,8,9). Kuinka monta 4-numeroista tunnuslukua on olemassa (0000 on sallittu)? Nyt sinulla on eri kirjaimia jopa sama määrä 10 kpl, joten...

vesa
Entäs jos salasanoissa saisi olla vain n kpl samoja merkkejä jolloin kysymys olisi:
kuinka monta erilaista viisikirjaimista salasanaa, joissa saa olla korkeintaan kaksi samaa merkkiä,
voidaan muodostaa merkkijonosta 'ABCDEFGHIJ'? Tällöin sallittu kombinaatio olisi 'AABBC' mutta
kombinaatiot 'AAABB','BBAAA','AABBA' ei-sallittuja.

Tämä on jo paljon vaikeampi tilanne. Itsellä ei nyt äkkiä tule mieleen muuta kuin seuraava:
Olkoon N kaikkien 5-kirjaimisten sanojen lukumäärä (edellisen osan vastaus). Olkoon Na sellaisten sanojen lukumäärä, jossa on vähintään kolme a-kirjainta, Nb sellaisten sanojen lukumäärä, jossa on vähintään kolme b-kirjainta jne. Kysytty lukumäärä on tällöin

N - Na - Nb - ... - Nj.

Koska Na = Nb = ... = Nj (jokainen kirjain on yhtä todennäköinen), niin lausekkeen saa sievennettyä muotoon

N - 10Na.

Nyt sitten pitää selvittää, mitä Na on. Tarvitset siihen binomitodennäköisyyksiä.

Tässäpä vihjeitä (tulikohan liikaakin )

PS: Ajattelin koko ajan, että aakkosista on vain a-j käytössä. Jos alkuosassa oli tarkoitus käyttää kaikkia aakkosia, niin lukumääriä pitää soveltaa. Laskut eivät vaikeudu, mutta numerot muuttuvat.

vesa
Seuraa 
Viestejä4
Liittynyt28.8.2006

Kiitoksia, vinkkien avulla sain kaavat selville ja määrät laskettua...

Mutta nuohan kumpikin antavat permutaatio-määrät eli mitenkähän saataisiin kombinaatiot eli esim ensimmäisessä tapauksessa erilaisten 4-numeroisten tunnuslukujen määrä kun samat numerokombinaatiot eivät ole sallittuja eli kun otetaan 0001, niin 1000,0100,0010 ei oteta mukaan.

Allekirjoitus

Uusimmat

Suosituimmat