offline
- Pridružio: 16 Mar 2010
- Poruke: 160
|
ELEMENTI KOMBINATORIKE
(Dodatna nastava za VII razred osnovne škole)
Miroslav B .Mladenović-Mirac
Nastavnik matematike
OŠ „Braća Milenković“ selo Šišava-lomnica
Vlasotince, Srbija
mmirac@ptt.rs
Često se dešava da treba izračunati broj svih mogućih načina rasporeda nekih predmeta uku broj svih mogućnih načina da se ostvare neke radnje.
Na primer odgovoriti na pitanje: na koliko načina se 5 ljudi može poređati u vrstu? Ili na koliko načina se novčanice od 50 dinara može usitniti?.
Problemima ovakvog tipa bavi se deo matematike koji se zove
k o m b i n a t o r i k a.
Ovde ćemo se upoznati samo sa dva osnovna pojma kombinatorike:- permutacije i kombinacije.
1.P e r m u t a c i j e
P r i m e r 1.
Problem: Na koliko različitih načina Aca, Branko i Cica mogu da stanu u vrstu?
Označavamanjem datih imena sa prvim slovom A,B i C, možemo odrediti sve vrste u koje se oni mogu porediti:
ABC, ACE, BAC, BCA, CAB, CBA.
Vidimo da ih ima 6, pa Aca, Branko i Cica mogu na 6 različitih načina da stanu u vrstu..
Ovaj problem se rešava na sledeći način: Na koliko različitih načina mogu slova slova A,B, i C da „stanu“ u vrstu?
Videli smo da ima 6 različitih vrsta. Vrste se razlikuju u poretku slova.
Savku od tih vrsta szvaćemo p e r m u n t a c i j a slova A, B i C; pa se dve permutacije razlikuju po tome što poredak slova u njima nije isti.
Ovde smo pravili permuntaciju od slova, a možemo da pravimo i permutacije cifara.
Sama reč permutacija je latinska reč, znači: promena poretka, promena rasporeda. Otuda reč permutovati znači: promeniti poredak, raspored, uzajamno zameniti mesta.
Uopošte, ako imamo n različitih objekata (slova ili cifara ili predmeta) koje ćemo označiti sa: a,a,a,...a., onda ćemo (raspored („vrstu“) tih objekata nazvati p e r u n t a c i j o m tih obkekata.
Ranije smo videli da je broj vrsta sastavljenih od slova A,B, i C
Jednak 6, pa je broj permutacija od 3 objekata jednak 6. To smo mogli da utvrdimo i ne ispisujući sve permutacije od 3 objekata jednak 6. To smo mogli da utvrdimo i ne ispisujući sve permunatcije, i to na sledeći:
Na prvom ispuri u permutaciji može da stoji bilo koje od slova A,B,C-onda se na drugom mestu može napisati bilo koje od preostala dva slova-znači, postoje dve mogućnosti.
Ako smo i na prvom i na drugom mestu napisali slovo, onda na trećem mestu može da stoji samo preostalo slovo-znači, postioji 1 mogućnost.
Prema tome, ukupan broj permutacija n objekata a,a,a,...a, odredićemo na sledeći način:
-Na prvom mestu može stojati samo preostalo slovo-znači, postoji 1 mogućnost. Prema tome, ukupan broj permutacija od 3 objekata (slova) je 3.2=6.
P r i m e r 2.
Napisati sve permutacije objekata(slova): a) a1, a2 b) a1, a 2,a 3; c) a1, a2, a3,a4.
Pokušajmo da izračunamo koliko ima različitih permutacija od n objekata. To ćemo prvo utvrditi za slučaj n=3. Ranije smo videli da je broj brsta sastavljenih od A,B i C jednak 6, pa je broj permutacija od 3 objekta jednak 6. To smo mogli da utvrdimo i ne ispisujući sve permutacije i to na sledeći način:
-znači, postoje 3 mogućnosti. Ako smo na prvom mestu napisali neko slovo, onda se na drugom mestu može napisati bilo koje od preostala dva slova-znači, postoje 2 mogućnosti. Ako smo i na prvom i na drugom mestu napisali slovo, onda na trećem mestu može da stoji samo preostalo slovo-znači, postoji 1 mogućnost.
Prema tome, ukupan broj permutacija a) od 2 objekat(slova) je 2;b) od 3 objekata (slova) je 3.2.1=6.; dok pod c) ima ih 24 mogućnost (4.3.2.1=24).
U opštem slučaju broj permunatacija n objekata a,a,a,...a, odredićemo na sledeći način:
Na prvom mestu u permutaciji može da stoji bilo koji od njih-znači, postoji n mogućnosti. Ako smo na prvom mestu napisali neki od njih, onda na drugom mestu može da stoji bilo koji od preostalih- n-1 objekata-znači, postoji još
( n-1) mogućnosti, tojest ukupno n(n-1) mogućnosti.
Ako smo na prva dva nesta napisali dva objekata, onda na trećem mestu da može da stoji bilo koji od preostalih (n-2) objekata-znači, postoji (n-2) mogućnosti, tojest ukupno n(n-1)(n-2) mogućnosti.
Nastavljajući na ovakav način rasuđivanjem zaključujemo da je broj permutacije od n objekata (označićemo ga sa Pn ) jednak je:
Pn=n(n-1)(n-2)....3.2.1.
Tojest
Pn=1,2,3,...n.
Znači, broj Pn je jednak proizvodu svih prirodnih brojeva od 1 do n. Taj proizvod se kraće označava sa n! (čita se n faktorijel ili faktorijel). Dakle n!=1.2.3...n, pa je Pn=n!.
Tako je:
P1=1!=1,
P2 =2!=1.2=2,
P3 =3!=1.2.3=6,
P4 =4!=1.2.3.4=24,
P5=5!=1.2.3.4.5=120,
P6 =6! =1.2.3.4.5.6=720,
P7 =7!=1.2.3.4.5.6.7=5040.
P r i m e r 3.
Izračunati 8!+9!
Rešenje:- a) 8!+9!=1.2.3.4.5.6.7.8 +1.2.3.4.5.6.7.8.9=8!.(1+9)=403200.
P r i m e r 4.
Na koliko se različitih načina može sastaviti spisak spiak od 9 učenika?
Rešenje:- P =9!=362880 načina.
Posmatrali smo permutacije kod kojih su svi objekti bili međusobno različiti. To su bile permutacije bez p o n v lj a nj a, tj. Permutacije kod kojih neki objekti mogu biti međusobno jednaki.
Napišimo permutacije slova:A,A,A,B.
Kao što vidimo imamo ih 4.:
AAAB ,AABA ,ABAA ,BAAA.
Da su slova bila različita bilo bilo bi ih 4!=24. Znači, ima ih manje, zato ako bilo koja dva slova A zamene mesta, nećemo dobiti novu permuntaciju.
Za permutacije slova A,A,A,B, kaže se da su to permutacije četvrte klase (od ukupno 4 objekta) sa po 3 jednaka objekata.
Uopšte, od n objekata među kojima ima m (m manje ili jednako n) jednakih možemo obrazovati permutacije n-te klase sa m jednakih objekata.
Posmatramo sada situaciju kada imamo m jednakih objekata jedne vrste (svaki od njih označavamo sa a) i n jednakih objekata druge vrste (svaki od njih označimo sa b); aa...aa bb...b (ovde su a i b samo slova kojima smo označili posmatrane objekte, a nisu brojevi, pa zato aa...a nije proizvod, već je to vrsta poređanih slova) i izražavamo koliko ima permutacija tih objekata. Da su svi različiti, bili bi ih (m+n)!.
Napravimo bilo koju permutaciju datih objekata. Ona se ne menja ako objekti označeni sa a ne menjaju mesta.
Ti objekti mogu da menjaju mesta na m!, n načina. Posmatrana permutacija se ne menja ni kada objekti označeni sa b međusobno menjaju mesta, a oni mogu da menjaju mesta na n! Načina.
Kako i objekti označeni sa a i objekti označeni sa b mogu istovremeno da menjaju mesta (naravno, ne objekata a i b odnosno ne menja objekt a mesto sa objektom b), to se pri m!.n! promena mesta objekata a i b posmatranja permutacijom ne menja.
Znači, skup od (m+n)! Permutacija se sastoji iz podskupova od kojih svaki ima po m!.n! istih permutacija, pa je ukupan broj permutacija od objekata jednak:
(m+n)!/m!.n! ;
to je dakle, broj permutacija klasa (m+n) sa ponavljanjem, u kojima se jedan objekat ponavlja m puta ( tojest. ima jednakih objekata druge vrste).
P r i m e r 5
Koliko se četvorocifrenih brojeva može napisati ako se koriste samo cifre broja 132132?
Rešenje:
Kada od cifara datog broja pravimo četvorocifrene brojeve, dobijamo brojeve koji imaju jedan par ili dva para istih cifara pa se može napraviti
3.(2+1+1)!/(2!.1!.1!)+3.(2+.2)!/(2!.2!)=54.
2.K o m b i n a c i j e
P r i m e r 6.
Problem:- Na koliko različitih načina se od slova A,B,C,D i E mogu izabrati 3 slova?
Ispišimo sve mogućnosti:
ABC, ABD, ABE,ACD, ACE, ADE, BCE, BDE, CDE.
Prema tome, ima 10 različitih načina da se od slova A,B,C,D,E izaberu 3 slova.
To smo mogli da utvrdimo i na sledeći način: na prvom mestu može da stoji bilo koje od satih 5 slova-ima 5 mogućnosti, na drugom bilo koje od preostalih 3 slova.
Znači, ima 5.4=60 načina izbora 3 slova!
Kako je to moguće, kada smo utvrdili da ima samo 10 načina?
U čemu je greška?
Tako smo, na primer, ABAC, ACE, BAC, CAB, CBA računali kao različite izbore slova, a oni su isti (ista su slova u njima).
To isto uradili smo i za svaka druga 3 slova.
Permutacija od 3 slova ima 3!(čitaj faktorijela), pa broj 60 moramo da podelimo sa 3! Da bismo dobili broj izbora 3 slova od datih 5 slova:
60/3!=5.4.3/1.2.3=10.
U opštem slučaju, da smo od n različitih objekata a.a.....a. birali k(k manje ili jednako n), dobili bismo da je ukupan broj različitih izbora jednak k:
n(n-1)(n-2)...(n.k+1)/k!=n(n-19(n-2)....(n-k+1)/1.2.3...k
(broj faktorijela u brojiocu jednak je broju faktorijela u imeniocu).
Taj broj se kraće označava:
( n) (Čita se n iznad k)
k
Dakle: ( n) =(n-1)....(n-k+1)/k!.
k
Svaki izbor k objekata od datih n zove se k o m b i n a c i j a k-te klase od n objekata.
Kao što smo videli, kod kombinacije nije bitan poredak objekata (slova), a videli smo da je ukupan broj kombinacija k-te klase od n objekata jednak:
( n) (Čita se n iznad k).
k
To možemo zapisati i na sledeći način: Cn = ( n) (Čita se n iznad k). Kao broj
k
kombinacije klase k od n objekata.
Tako, na primer, broj kombinacija klase 3 od 5 različitih elemenata
a , a ,a , a , a , izznosi:
1 2 3 4 5
3
C5 = 5.4.3/3!=5.4.3.2.1=10.
P r o b l e m 7.
Od 10 različitih cvetova treba napraviti buket u kome se nalaze bar 2 cveta. Na koliko načina se to može uraditi?
Rešenje:
Biramo ili 2ili 3 ili 4 itd. Ili 10 cvetova, pa je traženi broj buketa jednak
( 10 )+(10 )+(10)+(10) +( 10)+( 10)+(10 )+(10)+(10 )+( 10) =1013 načina.
1 2 3 4 5 6 7 8 9 10
R i m e r 8 .
Koliko je šahista bilo na šahovskom turniru ako je poznato da su svaka dva od njih odigrala po jednu partiju, kao i da je ukupan broj odigranih partija 6?
Rešenje:
ako je bilo n šahista, onda su oni odigrali (n) partija tojest (n) =6
2 2
Odakle je n=4.
3. Zadaci za vežbu
1. Koliko se različitih četvroocifrenih brojeva (čije su sve cifre različite) može napisati ako se koriste samo cifre 6,7,8 i9?
1. Za koliko načina se 8 topova može razmestiti na šahovskoj tabli tako da se ni koja dva ne tuku?
2. Koliko se četvorocifrenih brojeva može napisatiod cifara broja 123153 ?
3. Od 8 različitih knjiga treba izabrati paran broj knjiga. Na koliko načina se to može uraditi?
4. na koliko načina 4 đaka mogu međusobom da podele 25 metalnih novčića?
5. Koliko je pravih određeno pomoću 6 tačaka, ako ni 3 od ovih tačaka ne leže na istoj pravoj?
6. U koliko se tačaka seku 6 pravih, ako ni 2 od njih nisu paralelne i ni 3 od njih ne prolaze kroz istu tačku?
7. Koliko je šahista bilo na šahovskom turniru ako je poznato da su svaka dva od njih odigrala po jednu partiju, kao i da je ukupan broj odigranih partija 6?
8. Na koliko načina se može formirati fudbalski tim, ako se raspolaže s 13 igrača?
Rešenje: 1.)9!= 24 načina,
2) 8!=40320,
3) Dobijamo traženi broj: 4!+6.(2+1+1)!/(2!1!1!)+(2+2)!/(2!2!)=102.
4) Birajmo ili 2 ili 4 knjige ili 6 ili 8 knjiga, pa je traženi broj načina izbora knjiga jednak:
( +(+(+( =127.
2 4 6 8
4. Literatura:
[1] Grupa autora: Dr.M. Arsenović, J.Vukadinović, dr S.Vukadinović, B.Đerasimović, dr. A.Zolić, dr. M.Ilić-Dajović, I.Mitrović, dr. V.Mićić, mr. M.Mrmak, mr. LJ.Čukić -Matematika, priručnik za Dodatnu nastavu za VII i VIII razred, strana: 25-31, Zavod za udžbenike i nastavna sredstva Beograd, 1980. godine
[2] Kombinatorika :- članak, Matematički list broj 6, 1987. godine-Savez društava matematičara, fizičara i astronoma Jugoslavije
Vlasotince, proleće 1995. godine Autor: Miroslav B. Mladenovć-Mirac
Miroslav B .Mladenović-Mirac
Nastavnik matematike
OŠ „Braća Milenković“ selo Šišava-lomnica
Vlasotince, Srbija
mmirac@ptt.rs
28. mart 2010. godine Vlasotince Srbija
|
