Napravi pauzu
banner
banner
banner
banner
banner
banner
banner
banner
banner

Elementi kombinatorike /Dodatna nastava za VII razred/

Elementi kombinatorike /Dodatna nastava za VII razred/

Idi na vrh
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:

(Cool+(Cool+(Cool+(Cool =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



Registruj se da bi učestvovao u diskusiji. Registrovanim korisnicima se NE prikazuju reklame unutar poruka.

Potreban je samo minut da se registrujete - da biste učestvovali u diskusiji:
Izaberite vaše korisničko ime [username] :
Vaša email adresa je [email] : Email adresa mora biti tačna!
Ukucajte željenu šifru [password] :
Ukucajte šifru ponovo [password again] :
Jezik [language] :




Ili se jednostavno uloguj preko Facebook-a:
Ko je trenutno na forumu
 

Ukupno su 507 korisnika na forumu :: 67 registrovanih, 11 sakrivenih i 429 gosta   ::   [ Administrator ] [ Supermoderator ] [ Moderator ] :: Detaljnije

Najviše korisnika na forumu ikad bilo je 1311 - dana 15 Nov 2012 21:40

Korisnici koji su trenutno na forumu:
Korisnici trenutno na forumu: _Rade, Aleksandar Tomić, amir3045, Bane91, bozidar87, castro36, Challenger__, Chuck Norris, cinoeye, Cobi026, damirZR, dexter300, Djokkinen, dovlado, Envitrustisit, Futurama, GrobarRomanticar, guta89, GZ, Hussar, i.senica, iCho, ikan, ilovephp, Joe Husaphet 2, kljift, Kule, kuzmar, Loes, Logic005, m4rk0, Marko Marković, markus2, Milovan Dinic, Miloš CG, mirbat, mungus, nenad81, pandur, r77adder, Rade Jakovljevic, respekt, S2M, Sasa Pavlovic, Sass Drake, ShurikSST, Sima zna, SlobaBgd, sosko, Springfield, Srki94, StepskiVuk2, t.mile, t84dar, Toni, vasa.93, vathra, vilenjakmax, virked, Vlada78, Warhawk, Yellow Pinky, Zoran Marinkovic, zoran MKD, zoran-ruma, zoranis, Žan Klod vam dam
Siguran hosting