Kombinaatio

Wikipedia
Loikkaa: valikkoon, hakuun

Kombinatorisessa matematiikassa joukon alkioiden kombinaatio on joukon osajoukko. k-kombinaatio on joukon S osajoukko, jossa on k kappaletta jäseniä. Jäsenten listausjärjestyksellä ei ole väliä kombinaatioissa - kaikki joukot, jotka voidaan muodostaa vaihtamalla jäsenten järjestystä esittävät samaa kombinaatiota. Sen sijaan variaatiossa jäsenten järjestyksellä on väliä eli eri järjestys on eri variaatio.

k-kombinaatioiden määrä on sama kuin binomikerroin "n yli k:n", joka kirjoitetaan yleensä;

{n \choose k} = \frac{n!}{k!(n-k)!},

missä

k = kombinaation jäsenten lukumäärä,
n = pääjoukon S jäsenten lukumäärä.

Myös kirjoitusasu C(n, k) on tavallinen sen käyttökelpoisuuden vuoksi tekstirivillä.

Oheisessa taulukossa on eräitä kombinaation C(n, k) arvoja.
Erityisesti C(n, 0) = 1, C(n, 1) = n ja C(n, n) = 1.

Voidaan myös kirjoittaa differenssiyhtälö

C(n, k) = C(n – 1, k) + C(n – 1, k – 1)

eli taulukkoarvo saadaan kahden aikaisemmin lasketun
summana.

Edelleen havaitaan, että sarakkeella n olevien lukujen
summa on

\sum_{k=0}^n C(n, k) = 2^n
k   luku (kelt.) on kahden muun (sin.) summa
6   1
5   1 6
4   1 5 15
3   1 4 10 20
2   1 3 6 10 15
1   1 2 3 4 5 6
  0   1 1 1 1 1 1 1
  0   1   2   3   4   5   6 n
1 2 4 8 16 32 64 2^n

Esimerkkejä[muokkaa | muokkaa wikitekstiä]

Esimerkki 1.[muokkaa | muokkaa wikitekstiä]

C(7, 3) kertoo, kuinka monta erilaista kolmen hengen ryhmää voidaan muodostaa seitsemän henkilön joukosta. Lasketaan se:


{7 \choose 3} = \frac{7!}{3!(7-3)!} = \frac{7 \cdot 6 \cdot 5 \cdot 4!}{3! \cdot 4!} 
= \frac{7 \cdot 6 \cdot 5}{3!} = \frac{7 \cdot 6 \cdot 5}{6} = 7 \cdot 5 = 35.

Esimerkki 2.[muokkaa | muokkaa wikitekstiä]

Lasketaan todennäköisyys sille, että saadaan lotossa tasan k numeroa oikein (0 \le k \le 7):

Lasketaan ensiksi kaikkien niiden lottorivien määrä, joissa on tasan k numeroa oikein. Tämä saadaan laskemalla kaikki 7:n oikean numeron k-kombinaatiot, joka siis kertoo, kuinka monella tavalla 7:stä numerosta voidaan valita k numeroa (muista, että k on korkeintaan 7):

{7 \choose k}

Nyt väärät numerot voivat olla mitä vain, vaikka selvästikin niiden muodostamat osajoukot vaikuttavat lopullisten rivien määrään. Ongelma ratkaistaankin kertomalla yllä oleva luku kaikkien 32 arpomatta jääneiden numeroiden (7-k) kombinaatiolla, eli kaikilla mahdollisilla väärin menneiden numeroiden kombinaatioilla:

{7 \choose k} {32 \choose 7-k}

siis kertoo, kuinka monta erilaista lottoriviä voidaan muodostaa, joissa on täsmälleen k numeroa oikein ja 7-k väärin.

Kysytty todennäköisyys tapahtumalle saadaan, kun saatu luku jaetaan kaikkien mahdollisten lottorivien lukumäärällä {39 \choose 7}:

{7 \choose k} {32 \choose 7-k} : {39 \choose 7}

Siten esimerkiksi todennäköisyys saada lotossa viisi oikein on


{7 \choose 5} {32 \choose 7-5} : {39 \choose 7} = {7 \choose 5} {32 \choose 2} : {39 \choose 7}
= 21 \cdot 496 : 15 380 937 = 10416 : 15 380 937 \approx 1 : 1477 \approx 0{,}0006772

Katso myös[muokkaa | muokkaa wikitekstiä]