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

Olkoon annettuna n kappaletta merkkejä (olioita, alkioita)

a₁,  a₂,  a₃,  ...,  a_n.

Tehtävänä on selvittää, monellako tavalla näistä voidaan poimia p kappaletta, kun huomiota ei kiinnitetä poimittavien merkkien keskinäiseen järjestykseen. Sama voidaan lausua toisin: Montako p alkion muodostamaa osajoukkoa joukolla {a₁, a₂, a₃, ..., a_n} on?

Poimittavia p merkin yhdelmiä kutsutaan p-kombinaatioiksi.

Jos poimittavien merkkien keskinäinen järjestys otetaan huomioon, on kyseessä p-variaatioiden lukumäärä. Variaatioita on n!/(n - p)! kappaletta. Näiden joukossa on kuitenkin sellaisia, joissa on samat merkit, mutta eri järjestyksissä. Koska tietyt p merkkiä voidaan järjestää p! järjestykseen, on samat merkit sisältäviä järjestyksiä aina p! kappaletta, jolloin p-kombinaatioiden määrä saadaan jakamalla p-variaatioiden määrä luvulla p!. Lukumäärä on siis

.

Tätä kutsutaan myös binomikertoimeksi ja merkitään .

Siis:

n alkion joukosta voidaan valita p kappaletta eri tavalla, kun järjestykseen ei kiinnitetä huomiota.

Esimerkiksi merkeistä a, b, c, d voidaan poimia kahden merkin yhdelmiä = 6 kappaletta. Nämä ovat

ab,  ac,  ad,  bc,  bd,  cd.

Koska p-kombinaatiot ovat p-alkioisia osajoukkoja, tulee näiden lukumäärien summan olla sama kuin kaikkien osajoukkojen lukumäärä, kun huomioon otetaan kaikki mahdolliset arvot p, ts. p = 0, 1, ..., n. On siis oltava

= 2ⁿ.

Tämä on erikoistapaus binomikaavasta (x + y)ⁿ = x^n-py^p, kun asetetaan x = y = 1.

osajoukko  joukko  binomikerroin  binomikerroin  summamerkintä  binomikaava  binomikaava

Kivelä, niinkuin matematiikka, versio 1.12