Archive

Archive for February, 2012

Sadržaj

18. February 2012. 3 comments

Osnovna škola:

Rešavanje linearnih jednačina

Razlomci

Zadaci sa školskih takmičenja za VIII razred

Srednja škola:

Kombinatorika na lakši način 🙂

Kvadratne jednačine

Procentni i promilni račun

Rešavanje linearnih jednačina

For english speaking visitors: please visit http://mathematikon.wordpress.com/ .

Thank You!

Advertisements
Categories: Sadržaj

KOMBINATORIKA NA LAKŠI NAČIN – :)

18. February 2012. 118 comments

Šta biste uradili sa novcem koji dobijete na loto premiji? Hmm, lepa tema za razmišljanje. Međutim, koje su šanse da dobijete premiju na lotou, odnosno, da od svih mogućih kombinacija izvuku baš vašu. Treba pogoditi jednu kombinaciju od … hmmm… mnogo J . Dakle, treba da izračunamo koliko ima svih mogućih loto kombinacija. E, tu na scenu stupa kombinatorika.

Kombinatorika u srednjoj školi može biti pravi bauk. Silne permitacije, kombinacije, varijacije i još ko zna šta. Baš kad pomislite da ste nešto razumeli dobijete zadatak koji nemate pojma kako da rešite. Kako najlakše razumeti elemente kombinatorike? Kako shvatiti kombinacije, permutacije i varijacije? I, na kraju, kako sve to primeniti u konkretnim zadacima?

Na sva ova pitanja pokušaću da odgovorim što jednostavnije i što razumljivije. Uvedimo najpre neke osnovne oznake i formule.

FAKTORIJEL

Faktorijel nekog prirodno broja je proizvod svih prirodnih brojeva koji su manji ili jednaki njemu. Faktorijel označavamo uzvičnikom (n!) i računamo ga na sledeći način:

n!=n\cdot (n-1)\cdot (n-2)\cdot ..\cdot 2\cdot 1

Dakle, kada treba da izračunamo faktorijel neko broja samo pomnožimo sve prirodne brojeve od 1 do tog broja. To znači da je faktorijel broja 5 jednak

5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120

Zadatak 1: Koliko je 8!

Rešenje: 8!=8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=40320

Primetimo da važi:

n!=n\cdot (n-1)\cdot (n-2)\cdot ..\cdot 2\cdot 1=n\cdot (n-1)!

odnosno:

5!=5\cdot 4\cdot 3\cdot 2\cdot 1=5\cdot 4!

Ovo možemo i dalje da nastavimo:

n!=n\cdot (n-1)!=n\cdot (n-1)\cdot (n-2)!=..

To znači da je:

10!=10\cdot 9!=10\cdot 9\cdot 8!=10\cdot 9\cdot 8\cdot 7!=10\cdot 9\cdot 8\cdot 7\cdot 6!=...

Radi lakšeg računanja uzima se da je 0!=1.

BINOMNI KOEFICIJENT

Još jedan važan pojam je binomni koeficijent. Naziv “binomni koeficijent” potiče iz formule za razvijanje pirodnog stepena binoma, ali to nama ovde ne treba pa nećemu gubiti vreme na to 😉 .

Binomni koeficijent označavamo \left( \begin{matrix}  n \\  k \\  \end{matrix} \right) (čita se n nad k) i računamo po formuli

\left( \begin{matrix}  n \\  k \\  \end{matrix} \right)=\frac{n!}{k!\cdot (n-k)!}

Dakle, za računanje binomnog koeficijenta potrebna su nam dva prirodna broja.

Zadatak 2: Koliko je \left( \begin{matrix}  7 \\  4 \\  \end{matrix} \right)?

Rešenje:

 \left( \begin{matrix}  7 \\  4 \\  \end{matrix} \right)=\frac{7!}{4!\cdot (7-4)!}=\frac{7!}{4!\cdot 3!}=\frac{7\cdot 6\cdot 5\cdot 4!}{4!\cdot 3\cdot 2\cdot 1}=\frac{210}{6}=35

.

Vratimo se sada na kombinatoriku. Kombinatorika nam računa na koliko načina možemo da izaberemo elemente nekog skupa. Dakle, imamo neki skup, iz njega izdvajamo podskupove i brojimo ih. Tri osnovna elementa kombinatorike su: permutacija, varijacija i kombinacija. Da bismo ih prepoznali potrebno je da odgovorimo na dva pitanja:

Da li su izabrani svi elementi početnog skupa?
Da li je poredak izabranih elemenata bitan?

Kada odgovorimo na ova dva pitanja znaćemo da li je u pitanju permutacija, varijacija ili kombinacija. J

PERMUTACIJE

Zamislite da tri knjige treba da stavimo na policu. Na koliko načina možemo da ih poređamo?

Ako označimo knjige brojevima 1, 2 i 3 dobićemo šest mogućih rasporeda (1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2 i 3-2-1). Dakle, tri knjige možemo rasporediti na ukupno 6 načina. Ovo i nije bilo teško.

Međutim, stvar nam se znatno komplikuje ako imamo više knjiga, na primer 15. Posmatrajmo zato ovaj primer kao permutaciju. Naime, od 15 knjiga iz početnog skupa svih 15 moraju da budu postavljene na policu i bitan nam je njihov raspored na polici.

Odavde vidimo da će permutacija kao odgovor na gore spomenuta pitanja dati sledeće:

Svi elementi početnog skupa JESU izabrani.
Poredak izabranih elemenata JESTE bitan.

Dakle, ako u zadatku na oba pitanja dobijemo potvrdan odgovor, u pitanju su permutacije.

Permutacije mogu da budu bez ponavljanja i sa ponavljanjem. Bez ponavljanja znači da su svi elementi u početnom skupu različiti (svih 15 knjiga koje treba da stavimo na polici su različite), dok permutacija sa ponavljanjem znači da neki elementi mogu da se javljaju više puta (na primer, u reči TATA slova T i A se javljaju po dva puta).

Broj permutacija od n elemenata bez ponavljanja (u oznaci P(n))računamo po formuli:

P(n)=n!

Pretpostavimo da da imamo 3 knjige među kojima su dve iste. Dve iste knjige možemo označiti brojem 1, a treću brojem 2. Sada ih na polici možemo rasporediti na samo 3 načina (1-1-2, 1-2-1 i 2-1-1). Dakle, dozvolimo li ponavljanje smanjiće nam se broj mogućih rasporeda.

Ako imamo n elemenata u početnom skupu u kome su m1, m2, m3,.. i mk brojevi istih elemenata elemenata, to jest koliko imamo istih elemenata koje vrste (pri čemu je m1+m2+m3+.. +mk=n), ukupan broj permutacija računamo prema formuli:

P(n,{{m}_{1}},{{m}_{2}},{{m}_{3}},..{{m}_{k}})=\frac{n!}{{{m}_{1}}!\cdot {{m}_{2}}!\cdot {{m}_{3}}!\cdot \cdot \cdot {{m}_{k}}!}

Dakle, ako imamo 15 knjiga na policu ih možemo rasporediti na

P(15)=15!=1307674368000

Kad vidim ovako veliki broj, moram da priznam da mi je drago da nisam morao da pišem sve moguće kombinacije. J

Zadatak 3: Na koliko se načina 3 ista udžbenika matematike, 2 iste zbirke iz matematike i 1 radna sveska mogu poređati na polici.Rešenje: Odgovorimo najpre na dva važna pitanja. Vidimo da sve knjige idu na policu pa svi elementi početnog skupa jesu izabrani. Osim toga, poredak knjiga na polici jeste važan, pa zaključujemo da se radi o permutacijama.Takođe vidimo da se neke knjige ponavljaju pa su u pitanju permutacije sa ponavljanjem.Od ukupno n=3+2+1=6
knjiga imamo 3 ista udžbenika pa se prva knjiga ponavlja 3 puta, odnosno m1=3, dve iste zbirke te je m2=2 i samo jedna radna sveska pa je m3=1. Prema formuli za računanje broja permutacija sa ponavljanjem imamo:

P(n)=\frac{n!}{{{m}_{1}}!\cdot {{m}_{2}}!\cdot {{m}_{3}}!}=\frac{6!}{3!\cdot 2!\cdot 1!}=\frac{120}{2}=60

VARIJACIJE

Pretpostavimo sada da u jednom odeljenju od 25 učenika treba da izaberemo predsednika, sekretara i blagajnika. Dakle, od 25 učenika treba da odaberemo 3 i pritom je važno ko je predsednik, ko sekretar a ko blagajnik u odeljenju. Na koliko načina možemo napraviti ovaj izbor.

Ovde su u pitanju varijacije. Od 25 učenika u odeljenju mi biramo samo 3, pa nisu svi učenici izabrani. Takođe, važno je koga ćemo izabrati za predsednika, koga za sekretara a koga za blagajnike, obnosno, bitan je poredak našeg izbora. Odavde zaključujemo da će na dva važna pitanja varijacije dati sledeće odgovore:

  1. NISU svi elementi početnog skupa izabrani.
  2. Poredak izabranih elemenata JESTE bitan.

Varijacije takođe mogu da budu sa i bez ponavljanja. Ako od n početnih elemenata biramo njih k, dobijamo varijacije od n elemenata k-te klase njihov broj označavamo kao V_{n}^{k} ako su varijacije bez ponavljanja, i \overline{V_{n}^{k}} ako su u pitanju varijacije sa ponavljanjem. Da ne dođe do zabune, u nekim udžbenicima se koriste i oznake V_{k}^{n} i \overline{V_{k}^{n}}.

Broj varijacija k-te klase od n elemenata bez ponavljanja računamo po formuli:

V_{n}^{k}=\frac{n!}{(n-k)!}

U slučaju varijacija sa ponavljanjem imamo formulu:

\overline{V_{n}^{k}}={{n}^{k}}

U našem primeru pretpostavimo da isti učenik ne može da dobije dve funkcije (niko ne može da bude, na primer, i predsednik i blagajnik). Dakle, od 25 učenika biramo 3 bez ponavljanja učenika. To su varijacije od 25 elemenata treće klase bez ponavljanja pa imamo da je n=25 i k=3:

V_{25}^{3}=\frac{25!}{(25-3)!}=\frac{25!}{22!}=\frac{25\cdot 24\cdot 23\cdot 22!}{22!}=13800

Zadatak 4: Koliko se trocifrenih brojeva može napisati pomoću cifara 1, 2, 3, 4, 5 i 6 ako se cifre

  1. ne ponavljaju;
  2. ponavljaju;

Rešenje:

a) Dakle, od ponuđenih 6 cifara mi pravimo trocifrene brojeve (odnosno biramo po tri cifre) pri čemu se cifre ne ponavljaju. Dakle, sve cifre NISU izabrane i poredak izabranih JESTE bitan pa su u pitanju varijacije bez ponavljanja treće klase od 6 elemenata, odnosno n=6 i k=3:

V_{6}^{3}=\frac{6!}{(6-3)!}=\frac{6!}{3!}=\frac{6\cdot 5\cdot 4\cdot 3!}{3!}=120

odnosno, ukupno 120 brojeva.

b) Ovde imamo isti slučaj ali ifre smeju da se ponavljaju pa je broj mogućih varijacija veći:

\overline{V_{6}^{3}}={{6}^{3}}=216

KOMBINACIJE

Pretpostavimo sada da o jednom odeljenju od 25 učenika treba odabrati dva predstavnika za Učenički parlament. U ovom slučaju opet ne mogu svi učenici da budu izabrani (jer od njih 25 biramo samo 2), ali poredak nije bitan (jer oba člana parlamenta imaju jednake funkcije). Dakle, kombinacija nam na dva važna pitanja daje sledeće odgovore:

NISU svi elementi početnog skupa izabrani.
Poredak izabranih elemenata NIJE bitan.

I kombinacije mogu biti sa ponavljanjem i bez ponavljanja. Kombinacije bez ponavljanja od n elemenata k-te klase obeležavamo sa C_{n}^{k} i računamo po formuli:

C_{n}^{k}=\left( \begin{matrix}  n \\  k \\  \end{matrix} \right)

Kombinacije sa ponavljanjem od n elemenata k-te klase (u oznaci\overline{C_{n}^{k}}) računamo formulom:

\overline{C_{n}^{k}}=\left( \begin{matrix}  n+k-1 \\  k \\  \end{matrix} \right)

Dakle, u našem slučaju od 25 učenika biramo 2 pa su u pitanju kombinacije druge klase od 25 elemenata, a njih ima ukupno:

C_{25}^{2}=\left( \begin{matrix}  25 \\  2 \\  \end{matrix} \right)=\frac{25!}{2!\cdot (25-2)!}=\frac{25!}{2!\cdot 23!}=\frac{25\cdot 24\cdot 23!}{2!\cdot 23!}=\frac{600}{2}=300

Zadatak 5: Na koliko se načina iz špila od 32 karte mogu izvući 4 karte?

Rešenje: Od ukupno 32 karte mi biramo 4. Kako ne mogu biti izabrane sve karte i poredak nije bitan, zaključujemo da su u pitanju kombinacije od 32 elementa četvrte klase bez ponavljanja, pa je n=32 i k=4 odakle imamo da je:

C_{32}^{4}=\left( \begin{matrix}  32 \\  4 \\  \end{matrix} \right)=\frac{32!}{4!\cdot (32-4)!}=\frac{32!}{2!\cdot 28!}=\frac{32\cdot 31\cdot 30\cdot 29\cdot 28!}{4!\cdot 28!}=

=\frac{32\cdot 31\cdot 30\cdot 29}{4\cdot 3\cdot 2\cdot 1}=\frac{863040}{24}=35960

ZAKLJUČCI

Sve gore navedeno možemo smestiti u jednu tabelu:

Da li su izabrani svi elementi početnog skupa?

Da li je bitan poredak među izabranim elementima?

Formule za računanje

DA

DA

PERMUTACIJE

Bez ponavljanja

P(n)=n!

Sa ponavljanjem

P(n,{{m}_{1}},{{m}_{2}},{{m}_{3}},..{{m}_{k}})=\frac{n!}{{{m}_{1}}!\cdot {{m}_{2}}!\cdot {{m}_{3}}!\cdot \cdot \cdot {{m}_{k}}!}

NE

DA

VARIJACIJE

Bez ponavljanja

V_{n}^{k}=\frac{n!}{(n-k)!}

Sa ponavljanjem

\overline{V_{n}^{k}}={{n}^{k}}

NE

NE

KOMBINACIJE

Bez ponavljanja

C_{n}^{k}=\left( \begin{matrix}  n \\  k \\  \end{matrix} \right)

Sa ponavljanjem

\overline{C_{n}^{k}}=\left( \begin{matrix}  n+k-1 \\  k \\  \end{matrix} \right)

Vratimo se sada na naš problem sa početka ovog teksta, dakle, koliko ima mogućih kombinacija u lotou. Podsetimo se da se u lotou od 39 brojeva bira 7 i nije važno kojim redom su brojevi izabrani. Posmatramo gornju tabelu i odgovaramo na pitanja: svi elementi NISU izabrani i poredak NIJE bitan. Dakle, zaključujemo da su u pitanju kombinacije. Osim toga, znamo da se brojevi ne vraćaju u bubanj pa se ne može desiti da se isti broj izvuče više puta, te su u pitanju kombinacije bez ponavljanja sedme klase o 39 elemenata. Dalje pratimo tablicu i nalazimo formulu po kojoj ćemo izračunati ukupan broj kombinacija:

C_{n}^{k}=\left( \begin{matrix}  n \\  k \\  \end{matrix} \right)

U našem slučaju imamo:

C_{39}^{7}=\left( \begin{matrix}  39 \\  7 \\  \end{matrix} \right)=\frac{39!}{7!\cdot (39-7)!}=\frac{39!}{7!\cdot 32!}=\frac{39\cdot 38\cdot 37\cdot 36\cdot 35\cdot 34\cdot 33\cdot 32!}{7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1\cdot 32!}=

=\frac{77519922480}{5040}=15380937

Dakle, šanse da na lotou dobijemo premiju su 1 u 15380937, ili 1 u preko 15 miliona. Hmmm, može li kombinatorika i teorija verovatnoće bar malo da povećaju te šanse? 😉

Napomena: Ceo tekst možete preuzeti u pdf formatu ovde.

Categories: Srednja škola