Sisällön pääryhmät Diskreettiä matematiikkaa Lukumäärän laskeminen [ 1 2 3 4 5 6 7 ] ESITIEDOT: KATSO MYÖS:  joukko-oppi,  binomi- ja multinomikertoimet

Kansisivu  Sisältö  Hakemisto

Joukossa A olkoon äärellisen monta alkiota, n kappaletta:

A = {a₁, a₂, ..., a_n}.

Tämän osajoukot ovat joukkoja, joihin on otettu joitakin näistä alkioista. Esimerkiksi {a₁, a₃, a₇} on osajoukko (mikäli n on vähintään 7). Yhden alkion muodostamat joukot ovat myös osajoukkoja, esimerkiksi {a₁}. Tyhjää joukkoa, so. joukkoa, jossa ei ole ainuttakaan alkiota, ja joukkoa A itseään pidetään myös osajoukkoina.

Jokainen osajoukko voidaan esittää nollista ja ykkösistä muodostuvalla jonolla, jossa on n merkkiä, so. yhtä monta merkkiä, kuin joukossa A on alkioita. Nolla tarkoittaa, että vastaava alkio ei kuulu osajoukkoon, ykkönen puolestaan, että se kuuluu. Jos n = 7, on osajoukon {a₁, a₃, a₇} esitys 1010001. (Edellytyksenä on, että joukosta A poimitut alkiot luetellaan aina tietyssä, esimerkiksi kasvavan indeksin mukaisessa järjestyksessä.)

Kysymys osajoukkojen lukumäärästä pelkistyy tällöin kysymykseksi merkkijonojen lukumäärästä: Miten monta jonoa voidaan muodostaa merkeistä 0 ja 1, kun jonojen pituus on n? Vakiopituisten jonojen lukumäärää koskevan tuloksen perusteella saadaan seuraavaa:

Jos joukossa on n alkiota, sen osajoukkojen lukumäärä on 2ⁿ.

joukko  alkio  osajoukko  tyhjä joukko

Kivelä, niinkuin matematiikka, versio 1.12