Kombinatorika i vjerojatnost
Kombinatorika i vjerojatnost, principi prebrojavanja, permutacije, varijacije, kombinacije
Table of Contents
- Principi prebrojavanja
- Osnovni principi prebrojavanja
- Igra: Obuci Anu
- Vježba: principi prebrojavanja
- Permutacije
- Permutacije bez ponavljanja
- Vježba: permutacije bez ponavljanja
- Permutacije s ponavljanjem
- Vježba: permutacije s ponavljanjem
- Varijacije
- Varijacije bez ponavljanja
- Vježba: varijacije bez ponavljanja
- Varijacije s ponavljanjem
- Vježba: varijacije s ponavljanjem
- Varijacije u glazbi
- Kombinacije
- Kombinacije bez ponavljanja
- Vježba: kombinacije bez ponavljanja
- Kombinacije s ponavljanjem
- Vježba: kombinacije s ponavljanjem
- Permutacije, varijacije, kombinacije
- Kako ih prepoznati?
- Mentalna mapa - kombinatorika
- Veza permutacija, varijacija i kombinacija
- Vježba: Permutacije, varijacije i kombinacije
- KVIZ - Kombinatorika
- Ocjena rezultata kviza
- Vjerojatnost
- Osnovni pojmovi vjerojatnosti
- Igra: Kuglice u vreći
- Računanje vjerojatnosti
- Vježba 1: Vjerojatnost
- Vježba 2. Vjerojatnost
Osnovni principi prebrojavanja
Brojanje i prebrojavanje dio je našeg svakodnevnog života.[br]Na primjer: Na koliko načina možemo poredati 5 knjiga na polici?[br]Na koliko načina možemo odabrati 2 kuglice sladoleda ako u ponudi imamo 10 različitih okusa?[br]Koliko ima različitih telefonskih brojeva od 6 znamenaka?[br]Na koliko se načina može izvući 7 brojeva od 39 u igri LOTO?[br]U rješavanju ovakvih i drugih sličnih pitanja pomoći će nam kombinatorika - grana matematike koja se bavi prebrojavanjem.
Primjer 1. Princip zbroja
U kutiji s nakitom nalaze se: 4 ogrlice, 2 para naušnica, 3 narukvice i 5 prstena.[br]Na koliko načina možemo odabrati jedan ukras?[br][br]Rj. U kutiji se nalazi 4+2+3+5=14 ukrasa. Dakle, jedan ukras možemo izabrati na 14 načina.[br]Ovo je primjer jednostavnog principa prebrojavanja - principa zbroja.
Primjer 2. Princip umnoška
U ormaru se nalaze 2 kape, 3 šala i 2 para rukavica. Na koliko načina možemo odabrati kapu, šal i rukavice?[br][br]Rj. Uvedimo oznake: kape - [math]K_1,K_2[/math], šalovi - [math]Š_1,Š_2,Š_3[/math], rukavice - [math]R_1,R_2[/math].[br]Nakon odabira kape (2 načina) biramo šal (3 načina) i rukavice (2 načina):
Dakle, postoji ukupno [math]2\cdot3\cdot2=12[/math] načina na koji možemo odabrati kapu, šal i rukavice.[br]U ovom primjeru imamo prebrojavanje po principu umnoška:[br]ako se prvi element može odabrati na [math]a_1[/math] načina, drugi element na [math]a_2[/math] načina, treći element na [math]a_3[/math] načina,[br]tada je ukupan broj odabira [math]a_1\cdot a_2\cdot a_3[/math] načina .[br][br]
Osim principa zbroja i umnoška, u kombinatorici koristimo još tri principa odabira ili raspoređivanja elemenata: permutacije, varijacije i kombinacije.
Permutacije bez ponavljanja
Primjer 1.
Ante želi na policu staviti ove tri knjige: [i]Volim matematiku,[/i] [i]Nogometna matematika i fizika[/i], [i]Mali princ[/i].[br]Na koliko načina to može napraviti?
Rj. Ante može prvu knjigu odabrati na 3 načina. [br]Nakon toga, preostale su mu još 2 knjige pa drugu može odabrati na 2 načina.[br]Na kraju, na treće mjesto stavlja preostalu knjigu (1 način).[br]Dakle, prema principu umnoška postoji [math]3\cdot2\cdot1=6[/math] načina slaganja tih knjiga.[br] _ _ _[br] [math]3\cdot2\cdot1=6[/math][br][br]Označimo knjige: M - [i]Volim matematiku, [/i]N - [i]Nogometna matematika i fizika, [/i] P - [i]Mali princ [br][/i]i ispišimo sve načine slaganja:[br]M N P N M P P M N[br]M P N N P M P N M
Neka je S = { [math]a_1,a_2,a_3[/math] } skup koji ima 3 elemenata. Svaka uređena trojka različitih elemenata iz skupa S[br]naziva se [b]permutacija [/b]skupa S. [br]Skup može imati i više elemenata pa govorimo o petorkama, šestorkama, ... općenito n-torkama.[br]Ako su elementi skupa S različiti često se koristi i naziv [b]permuacije bez ponavljanja[/b].[br][color=#ff0000]Zapamtimo: [br][/color][b][color=#0000ff]Sve[/color] [/b]elemente skupa S razmještamo na sve moguće načine , pri čemu je [color=#0000ff][b]bitan poredak[/b] [/color]elemenata.
[color=#0000ff]Faktorijeli[br][/color]Umnožak prvih n prirodnih brojeva označavamo [b]n! [/b]i čitamo "en faktorijela".[br]1!=1, 2!=[math]2\cdot1=2[/math], 3!=[math]3\cdot2\cdot1=6[/math], 4!=[math]4\cdot3\cdot2\cdot1=24[/math], 5!=[math]5\cdot4\cdot3\cdot2\cdot1=120[/math], ...[br]Po definiciji stavljamo 0!=1.[br]Vrijedi formula: n! = n [math]\cdot[/math] (n-1)![br]Npr. 5!=5[math]\cdot[/math]4!, 5!=5[math]\cdot[/math]4[math]\cdot[/math]3!, 7!=7[math]\cdot[/math]6!=7[math]\cdot[/math]6[math]\cdot[/math]5[math]\cdot[/math]4![br][color=#0000ff]Broj svih permutacija skupa od n elemenata jednak je [math]P_n=n![/math][/color]
Primjer 2.
Neka je zadan skup S={ 0,2,4,6,8 }.[br]a) Koliko postoji permutacija skupa S?[br]b) Koliko permutacija skupa S završava sa 6?[br]c) Koliko permutacija skupa S ne završava sa 6?[br]Rj.[br]a) Skup S ima 5 elemenata i broj svih permutacija jednak je [math]P_5=5!=5\cdot4\cdot3\cdot2\cdot1=[/math]120.[br]b) Tražene permutacije su oblika _ _ _ _ [u]6[br][/u]Na prva 4 mjesta možemo rasporediti preostale elemente 0,2,4,8 na 4!=[math]4\cdot3\cdot2\cdot1=[/math]24 načina.[br]c) Broj permutacija skupa S koje [color=#1e84cc][b]ne završavaju[/b] sa 6[/color] možemo dobiti tako da[br]od [color=#ff00ff]ukupnog broja permutacija [/color]oduzmemo [color=#ff00ff]one permutacije koje počinju sa 6[/color],[br]a njih ima (rj. a) - rj. b)): 120 - 24 =96
Varijacije bez ponavljanja
Primjer 1.
Na koliko načina možemo napraviti sendvič ako biramo[br] 3 različita nadjeva između ponuđenih:[br] piletina, kulen, pršut, šunka, sir, majoneza, jaje, salata, krastavac, rajčica?[br]
Rj. __ __ __[br] [math]10\cdot9\cdot8=720[/math][br]Kao prvi nadjev možemo odabrati jedan od 10 ponuđenih nadjeva.[br]Nakon toga, za drugi nadjev možemo odabrati jedan od 9 preostalih [br](jer mora biti različit od prvog).[br]Kao treći nadjev biramo jedan od preostalih 8 nadjeva.[br]Ukupan broj načina biranja tri različita nadjeva za sendvič jednak je [math]10\cdot9\cdot8=720[/math].[br][br]Iz skupa koji ima 10 elemenata birali smo 3 elementa, pri čemu je [b]poredak elemenata bitan[/b].[br]Svaku [b]uređenu[/b] trojku nazivamo [color=#0000ff]varijacijom trećeg razreda[/color] ili [color=#ff0000][b]varijacijom bez ponavljanja[/b][/color].
[color=#0000ff]Na koliko načina možemo odabrati [/color][color=#ff0000]k [/color][color=#0000ff]različitih elemenata iz skupa koji ima [/color][i][color=#ff0000]n[/color][/i][color=#0000ff] elemenata? ( [/color][math]k\le n[/math][color=#0000ff])[br][/color]Uređenu k-torku iz skupa od n elemenata nazivamo [b]varijacijom [/b][i]k-tog[/i][b] razreda[/b] [br]([b][color=#ff0000]varijacijom bez ponavljanja[/color][/b]) i možemo je izračunati pomoću formule:[br][br][math]V_n^k[/math]=[math]n\cdot\left(n-1\right)\cdot\left(n-2\right)\cdot...\cdot\left(n-k+1\right)[/math][br]odnosno: [math]V_n^k[/math]=[math]\frac{n!}{\left(n-k\right)!}[/math][br][br]Npr. [math]V_{10}^3[/math]=[math]\frac{10!}{\left(10-3\right)!}=\frac{10!}{7!}=\frac{10\cdot9\cdot8\cdot7!}{7!}=10\cdot9\cdot8=720[/math][math]\frac{10!}{\left(10-3\right)!}=\frac{10!}{7!}=\frac{10\cdot9\cdot8\cdot7!}{7!}=10\cdot9\cdot8=720[/math][math][/math]
Primjer 2.
Koliko ima troznamenkastih brojeva kojima su sve tri znamenke različiti[br]a) neparni brojevi,[br]b) parni brojevi?[br]Rj. [br]a)Biramo uređene trojke ([i]k[/i]=3) iz skupa {1,3,5,7,9}, [i]n[/i]=5.[br]__ __ __[br][math]5\cdot4\cdot3=60[/math][br]Prvu znamenku možemo odabrati na 5 načina. Nakon toga, druga znamenka treba biti različita pa je biramo između preostala 4 neparna broja. Treću znamenku biramo između preostala 3 neparna brojeva.[br]Imamo ukupno [math]5\cdot4\cdot3=60[/math] troznamenkastih brojeva kojima su sve tri znamenke različiti neparni brojevi.[br][br]b)Biramo uređene trojke ([i]k[/i]=3) iz skupa {0,2,4,6,8},[i] n[/i]=5.[br]__ __ __[br][math]4\cdot4\cdot3=48[/math][br]Prva znamenka ne može biti 0, prvu znamenku možemo birati na 4 načina između brojeva 2,4,6,8.[br]Nakon toga, druga znamenka mora biti različita od prve pa je biramo između preostala 4 parna broja (sada možemo birati 0[br]i treću znamenku biramo između preostala 3 parna broja.[br]Troznamenkastih brojeva u kojima su sve znamenke različiti parni brojevi ima [math]4\cdot4\cdot3=48[/math].
Kombinacije bez ponavljanja
Kod permutacija i varijacija [b][color=#1e84cc]bitan[/color][/b] je poredak elemenata, tj. radi se o uređenim [i]n[/i]-torkama ili [i]k[/i]-torkama.[br]Međutim, u mnogim problemima prebrojavanja poredak izabranih elemenata [b][color=#ff0000]nije bitan[/color][/b].
Primjer 1.
Imamo 5 kuglica različitih boja: crvenu, narančastu, žutu, zelenu i plavu.[br]Na koliko različitih načina možemo odabrati 3 kuglice?
Označimo kuglice prema bojama: C - crvena, N- narančasta, Ž - žuta, Z - zelena, P - plava.[br]Nije važno kojim se redom izvlače 3 kuglice, već samo koje su to boje kuglica.[br]Ispišimo sve moguće načine biranja:[br]C N Ž C N Z C N P C Ž Z C Ž P C Z P [br]N Ž Z N Ž P N Z P Ž Z P [br]Postoji 10 različitih načina na koje možemo odabrati 3 kuglice od njih 5. [br]Izbore { C, N, Ž }, ..., {Ž, Z, P } tj. tročlane podskupove skupa { C, N, Ž, Z, P } nazivamo kombinacije trećeg razreda u peteročlanom skupu.[br]Općenito, iz skupa od n elemenata k-člane podskupove nazivamo kombinacija bez ponavljanja k-tog razreda i njihov broj jednak je:[br][br][math]C_n^k=\binom{n}{k}=\frac{n!}{k!\cdot\left(n-k\right)!}[/math], [math]0\le k\le n[/math][br]Broj [math]\binom{n}{k}[/math] nazivamo binomni koeficijent (čitamo: "en povrh ka").
Primjer 2.
Na koliko se načina može odabrati početna petorka igrača u košarkaškoj ekipu koja ima 9 igrača?[br]Rj. [br]Iz skupa od n=9 elemenata biramo podskupove od k=5 elemenata, pri čemu poredak nije bitan.[br][math]C_9^5=\binom{9}{5}=\frac{9!}{5!\cdot\left(9-5\right)!}=\frac{9\cdot8\cdot7\cdot6\cdot5!}{5!\cdot4!}=\frac{9\cdot8\cdot7\cdot6}{4\cdot3\cdot2\cdot1}=126[/math][br]Početna petorka može se odabrati na 126 načina.
Kako ih prepoznati?
Kako prepoznati u nekom zadatku o čemu se radi? [br]Jesu li to permutacije? Varijacije? Ili možda kombinacije?[br]Da bismo ih prepoznali potrebno je odgovoriti na ova pitanja:[br][table][tr][td][color=#0000ff][b]1. Biraju li se svi elementi početnog skupa?[/b][/color][br][color=#9900ff][b]2. Da li je poredak izabranih elemenata bitan?[/b][/color][/td][/tr][/table][i][br]Odgovor:[/i][br][table][tr][td][color=#6aa84f][b]Permutacije[/b][/color][/td][td][b][color=#1e84cc]Varijacije[/color][/b][/td][td][b][color=#e06666]Kombinacije[/color][/b][/td][/tr][tr][td][b]Svi [/b]elementi se biraju. [br]Poredak je [b]bitan[/b].[br][/td][td]Ne biraju se svi elementi. [br]Poredak je [b]bitan[/b].[/td][td]Ne biraju se svi elementi.[br]Poredak [b]nije[/b] [b]bitan[/b].[/td][/tr][/table][br][color=#980000][b]3. Mogu li se elementi ponavljati? [br][/b][table][tr][td][color=#000000]DA[/color][/td][td][color=#6aa84f]Permutacije [br] s ponavljanjem[/color][/td][td][color=#1e84cc]Varijacije [br]s ponavljanjem [/color][br][/td][td][color=#e06666]Kombinacije [br]s ponavljanjem[/color] [/td][/tr][tr][td][color=#000000]NE[/color][/td][td][color=#444444]Permutacije[br]bez ponavljanja[br][/color][/td][td][color=#444444]Varijacije[br] bez ponavljanja[br][/color][/td][td][color=#444444]Kombinacije[br]bez ponavljanja[/color][color=#000000][br][/color][/td][/tr][/table][/color]
VJEŽBA
1. Ako 6 osoba treba razmjestiti oko okruglog stola, u pitanju su:
2. Želimo li znati koliko postoji različitih pinova za bankovni račun (pin ima 4 znamenke),[br]radi se o:
3. Želimo li znati koliko se mješovitih plesnih parova može složiti[br] između 7 djevojaka i 5 mladića, u pitanju su:
Osnovni pojmovi vjerojatnosti
[i]Kolika je vjerojatnost da će sutra padati kiša?[br]Možemo pogledati vremensku prognozu i na osnovi nje procijeniti.[br][/i]Npr.
[i]Vjerojatnost da će padati kiša je 55%.[/i]
[b][color=#0000ff]Slučajan pokus[/color][/b] ili eksperiment je pokus čiji ishod ne možemo sa sigurnošću predvidjeti.[br]Mogući ishodi slučajnog pokusa zovu se [b][color=#0000ff]elementarni događaji[/color][/b].[br]Skup svih elementarnih događaja zovemo [b][color=#0000ff]prostor elementarnih događaja[/color][/b][br] i označavamo [math]\Omega[/math] (omega).
[color=#0000ff][b]Vjerojatnost događaja A[/b][/color], oznaka p(A), jednaka je[br][br] [color=#980000][b]p(A)=[u] broj povoljnih ishoda za A [/u] [br] ukupan broj ishoda[/b][/color][br][br] p(A)= [math]\frac{card\left(A\right)}{card\left(\Omega\right)}[/math]
Primjer 1.
Promatrajmo slučajan pokus - bacanje dvije igraće kocke.[br]Kolika je vjerojatnost događaja A={zbroj brojeva na kockama je 4}?[br]Rj. [br]Prostor elementarnih događaja: [br] [math]\Omega[/math]={ (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), [br] (2,1), (2,2), (2,3), (2,4), (2,5), (2,6),[br] (3,1), (3,2), (3,3), (3,4), (3,5), (3,6),[br] (4,1), (4,2), (4,3), (4,4), (4,5), (4,6),[br] (5,1), (5,2), (5,3), (5,4), (5,5), (5,6),[br] (6,1), (6,2), (6,3), (6,4), (6,5), (6,6)}[br]Događaj A se sastoji od elementarnih događaja A={ (1,3), (2,2), (3,1)}[br][math]card\left(\Omega\right)=36[/math], [math]card\left(A\right)=3[/math], p(A)= [math]\frac{card\left(A\right)}{card\left(\Omega\right)}=\frac{3}{36}=\frac{1}{12}\approx0.083[/math] ( 8.3 % )
Primjer 2.
Bacamo novčić i izračunajmo vjerojatnost događaja:[br] a) A={ palo je pismo ili grb }[br]b) B={ novčić je ostao u zraku }.[br]Rj. [br]Označimo: P- pismo, G- grb. Prostor elementarnih događaja [math]\Omega[/math] = { P, G }[br]A = { P, G } p(A)=[math]\frac{card\left(A\right)}{card\left(\Omega\right)}=\frac{2}{2}=1[/math][br]Događaj A nazivamo [b][color=#0000ff]sigurnim događajem[/color][/b] i njegova vjerojatnost je jednaka 1.[br][br]B=[math]\varnothing[/math] p(B)=[math]\frac{card\left(B\right)}{card\left(\Omega\right)}=\frac{0}{2}=0[/math][br]Događaj B nazivamo [b][color=#0000ff]nemogućim događajem[/color][/b] i njegova vjerojatnost je jednaka 0.[br]
Za svaki događaj A vrijedi [math]0\le[/math]p(A)[math]\le1[/math]