Kombinaatio

Kombinaatiota käytämme, kun valitsemme jostakin objektien joukosta tietyn määrän objekteja eikä valintajärjestyksellä ole väliä. Tyypillinen tehtävä on lotto 6/49 – uurnassa on 49 numeroa ja niistä arvotaan 6, eikä ole väliä, missä järjestyksessä ne nostetaan.

Kaavan johto

Onnenpyörä

Olkoon meillä jokin joukko M, esimerkiksi M = {a, b, c, d, e}. Tällöin k alkion kombinaatio on osajoukko K ⊆ M, jossa on tasan k alkiota. Koska K on joukko, järjestyksellä ei tietenkään ole väliä. Joukon M kolmen alkion kombinaatio voisi siis olla {a, b, d} tai {b, c, d}.

Ero k-permutaatioon on se, että k-permutaatiossa järjestyksellä oli väliä, joten (a, b, e) ja (e, b, a) ovat eri k-permutaatiot, mutta ne ovat sama kombinaatio, koska sekä (a, b, e) että (e, b, a) sisältävät samat alkiot. Se, että ne ovat eri järjestyksessä, ei kiinnosta meitä kombinaatioissa.

Voimme kuitenkin käyttää k-permutaatioita saadaksemme kaavan kaikkien erilaisten kombinaatioiden lukumäärälle. Tiedämme, että n alkion joukosta saadaan tasan

$\frac{n!}{(n - k)!}$

k alkion k-permutaatiota. Jos laskisimme kaikkien edellisen joukon M = {a, b, c, d, e} kolmen alkion k-permutaatioiden lukumäärän, saisimme $\frac{5!}{(5 - 3)!} = 60$ erilaista k-permutaatiota. Jokaisesta kolmikosta meillä olisi kuitenkin mukana myös kaikki sen permutaatiot. Eli mukana olisi kolmikko abc, mutta myös kolmikot acb, bac, bca, cab ja cba. Nämä ovat kuusi eri k-permutaatiota, mutta ne ovat yksi kombinaatio, koska niissä kaikissa on samat alkiot.

Jos meillä on jokin kolmikko, kuinka monta erilaista permutaatiota tällä kolmikolla on? Tasan 3!. Toisin sanoen kolmen alkion k-permutaatioita on tasan 3! kertaa enemmän kuin kolmen alkion kombinaatioita. Sen sijaan että laskisimme yhden kombinaation, laskemme 3! k-permutaatiota, yhden kunkin kolmikon permutaation. Jos siis jaamme k-permutaatioiden lukumäärän luvulla 3!, saamme kombinaatioiden lukumäärän.

Edellisen päättelyn voi yleistää: jos etsimme kaikkien erilaisten k alkion kombinaatioiden lukumäärää joukosta, jonka koko on n, tämä lukumäärä, jota merkitsemme $(\binom{n}{k})$ , on

$(\binom{n}{k}) = \frac{1}{k!} \cdot \frac{n!}{(n - k)!},$

eli k-permutaatioiden lukumäärä jaettuna luvulla k!, joka on kunkin k-monikon permutaatioiden lukumäärä. Kaavaa voi muokata sijoittamalla k-permutaatioiden lukumäärän lausekkeen:

$(\binom{n}{k}) = \frac{1}{k!} \cdot \frac{n!}{(n - k)!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

Esimerkki: joukon {a, b, c} kahden alkion kombinaatioiden lukumäärä on

$(\binom{3}{2}) = \frac{3!}{1! \cdot 2!} = 3$

ja ne ovat nämä kombinaatiot: {a, b}, {a, c} ja {b, c}. Alkuperäisen joukon M = {a, b, c, d, e} kolmen alkion kombinaatioita saisimme

$(\binom{5}{3}) = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

ja ne ovat nämä kombinaatiot: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

Binomikerroin

Merkintä $(\binom{n}{k})$ on binomikerroin. Se on kuin murtoluku ilman murtoviivaa (jonka kuitenkin tottumuksesta kirjoitat sinne), mutta sulkeilla (ne eivät ole vapaaehtoiset, niiden on oltava siinä). Binomikerroin luetaan ”n yli k” tai ”n valitaan k”. Binomikertoimen arvo on

$(\binom{n}{k}) = \frac{n!}{(n - k)! \cdot k!}$

Jos siis meillä on 5 alkion joukko ja valitsemme siitä neljän alkion joukkoja, niiden kokonaismäärä on

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5.$

Perusominaisuudet

Binomikertoimelle ja n ∈ ℤ⁺ pätee:

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Lisäksi, kun n, k ∈ ℕ ja k ≤ n, pätee

$\begin{array}{rcl} (\binom{n}{n - k}) & = & (\binom{n}{k}) . \end{array}$

Ja kun n, k ∈ ℕ ja k < n, pätee

$\begin{array}{rcl} (\binom{n}{k}) + (\binom{n}{k + 1}) & = & (\binom{n + 1}{k + 1}) . \end{array}$

Laskin

Seuraava laskin laskee binomikertoimen n yli k.

Ratkaistuja esimerkkejä

Aloitetaan jo mainitusta lotosta 6/49. Siinä uurnasta, jossa on 49 palloa, nostetaan yhteensä 6 palloa. Kuinka monta erilaista tulosta voidaan arpoa?

Ensinnäkin – onko numeroiden nostojärjestyksellä väliä? Ei ole, veikkaamme vain numerot, ei niiden järjestystä. Käytämme kombinaatioita. Palloja on yhteensä 49, nostamme 6 palloa, ja saamme binomikertoimen

$(\binom{49}{6}) = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13 983 816$

Arvottavia tuloksia on yhteensä 13 983 816. Tämä antaa muuten todennäköisyydeksi voittaa yhdellä rivillä 1/13 983 816, mikä on 0,00000715112 %.
Leevi, tunnettu naistenmies, on kylän tanssilavalla, jossa on yhteensä 13 ihanaa tyttöä, jotka kiinnostaisivat häntä. Leevi tietää ehtivänsä ilahduttaa illan aikana 4 eri tyttöä. Kuinka monesta eri nelikosta Leevi voi valita?

Tämä on taas yksinkertainen kombinaatioesimerkki, järjestyksellä ei ole väliä, Leevi on yhtä hyvä ensimmäisen tytön kanssa kuin viimeisen. Saamme siis 13 tytön joukon, josta valitsemme aina 4 tyttöä. Tämä johtaa binomikertoimeen

$(\binom{13}{4}) = 715.$
Sinulla on viidenkymmenen ihmisen ryhmä – puolet miehiä ja puolet naisia. Kuinka monta erilaista kolmen ihmisen ryhmää on olemassa, kun ryhmässä ei saa olla vain yhtä sukupuolta (eli ryhmässä ei saa olla kolmea miestä eikä kolmea naista)?

Tämä on jo hieman monimutkaisempi kombinaatiotehtävä. Kun suljemme pois yhden sukupuolen kolmikot, jäljelle jää vain kaksi vaihtoehtoa, miten kolmikko voi koostua – kaksi miestä ja yksi nainen tai yksi mies ja kaksi naista, ja ensimmäisen ryhmän (kaksi miestä ja yksi nainen) kombinaatioiden määrä on sama kuin toisen ryhmän. Riittää siis laskea ensimmäisen ryhmän kombinaatioiden määrä ja kertoa se kahdella. Nyt se on taas helppoa. Määritämme erilaisten miesparien kombinaatioiden määrän, joka on kaksikymmentäviisi yli kaksi, ja kerromme sen yhden naisen kombinaatioiden määrällä (se on kaksikymmentäviisi, katso perusominaisuudet yllä, tarkemmin toinen rivi). Tämän tuloksen vielä kerromme kahdella, ja lopputulos on valmis.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
Laatikossa on 15 tuotetta, joista 4 on viallisia. Kuinka monella tavalla voidaan valita 6 tuotetta niin, että
- yksikään ei ole viallinen? Nyt valitsemme 6 tuotetta 15 − 4 = 11 virheettömästä tuotteesta. Saamme siis binomikertoimen
  
  $(\binom{11}{6}) = 462.$
- täsmälleen yksi tuote on viallinen? Valitsemme siis joukon, jossa on 5 toimivaa ja 1 viallinen tuote. Toimivia tuotteita on yhteensä 11, viallisia 4. Käytämme tuloperiaatetta ja saamme tuloksen:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- korkeintaan yksi on viallinen? Ratkaisussa hyödynnämme edellisiä tuloksia. Tiedämme, että tapoja valita tasan 6 toimivaa tuotetta on 462 ja tapoja valita viisi toimivaa ja yksi viallinen tuote on 1848. Käytämme siis summaperiaatetta, laskemme nämä tulokset yhteen, ja saamme halutun tuloksen eli korkeintaan yhden viallisen tuotteen (= joko ei yhtään viallista tuotetta tai täsmälleen yksi). Tulos on siis: 462 + 1848 = 2310.

Luvut: Kombinatoriikka, K-permutaatio, Permutaatio, Kombinaatio, Järjestetty otos palauttaen, Kombinaatio palauttaen, Kuinka monta erilaista PIN-koodia on olemassa?

« Edellinen: Permutaatio

Seuraava: Järjestetty otos palauttaen »