Kombinaatio

Malline:Lähteetön 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 merkitystä kombinaatioissa: kaikki joukot, jotka voidaan muodostaa vaihtamalla jäsenten järjestystä, esittävät samaa kombinaatiota.^[1] Sen sijaan variaatiossa jäsenten järjestyksellä on merkitystä eli eri järjestys on eri variaatio.

k-kombinaatioiden määrä on sama kuin binomikerroin "n yli k:n", joka kirjoitetaan yleensä^[1]

(\binom{n}{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ä. Malline:Monta palstaa

Oheisessa taulukossa on eräitä kombinaation C(n, k) arvoja.
Erityisesti C(n, 0) = 1^[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}

Malline:Monta palstaa-katko

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}$

Malline:Monta palstaa-loppu

Kombinaatio voidaan esittää myös lukumäärän laskemista kuvaavilla summalausekkeilla:

(\binom{n}{1}) = \sum_{i = 1}^{n} 1

,

(\binom{n}{2}) = \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} 1

,

(\binom{n}{3}) = \sum_{i = 1}^{n - 2} \sum_{j = i + 1}^{n - 1} \sum_{k = j + 1}^{n} 1

, jne.

Esimerkkejä

Esimerkki 1.

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

$(\binom{5}{3}) = \frac{5!}{3! (5 - 3)!} = \frac{5 \cdot 4 \cdot 3 \cdot 2!}{3! \cdot 2!} = \frac{5 \cdot 4 \cdot 3}{3!} = \frac{5 \cdot 4 \cdot 3}{6} = 5 \cdot 2 = 10 .$

Esimerkki 2.

Lasketaan todennäköisyys sille, että saadaan lotossa tasan k numeroa oikein $(0 \leq k \leq 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):

(\binom{7}{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:

(\binom{7}{k}) (\binom{32}{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ä $(\binom{39}{7})$ :

(\binom{7}{k}) (\binom{32}{7 - k}) : (\binom{39}{7})

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

$(\binom{7}{5}) (\binom{32}{7 - 5}) : (\binom{39}{7}) = (\binom{7}{5}) (\binom{32}{2}) : (\binom{39}{7}) = 21 \cdot 496 : 15380937 = 10416 : 15380937 \approx 1 : 1477 \approx 0, 0006772$

Katso myös

Permutaatio

Lähteet

Malline:Viitteet

Aiheesta muualla

Malline:Commonscat-rivi

↑ ^1,0 ^1,1 ^1,2 Malline:Kirjaviite

[Grimaldi-1] 1,0 ^1,1 ^1,2 Malline:Kirjaviite

[1]

Kombinaatio

Sisällys

Esimerkkejä

Esimerkki 1.

Esimerkki 2.

Katso myös

Lähteet

Aiheesta muualla

Navigointivalikko

Kombinaatio

Esimerkkejä

Esimerkki 1.

Esimerkki 2.

Katso myös

Lähteet

Aiheesta muualla

Navigointivalikko

Haku