Kolegij: Matematika 2, ljetni semestar 2010./2011.
Asistentica: Sanda Bujaˇci´c
1
Kombinatorika
Veliki broj zadataka vezanih za prebrojavanja moˇze se rijeˇsiti upotrebom oˇciglednih principa za konaˇcne
skupove.
• PRINCIP SUME
Ako je |A| = a, |B| = b, gdje su A i B skupovi koji nemaju zajedniˇckih elemenata, tada vrijedi
|A ∪ B| = a + b.
• PRINCIP PRODUKTA
Ako je |A| = a, |B| = b, gdje su A i B skupovi, tada za njihov Kartezijev produkt vrijedi
|A × B| = a · b.
• PRINCIP JEDNAKOSTI
Ako postoji bijekcija iz skupa A u skup B, onda su A i B jednakobrojni skupovi, odnosno
|A| = |B|.
Principi sume i produkta ˇcesto se koriste i za viˇse skupova odjednom:
• Ako su Ai , i = 1, 2, . . . , n, medusobno disjunktni skupovi (nemaju zajedniˇckih elemenata), onda
je:
|A1 ∪ A2 ∪ . . . An | = |A1 | + |A2 | + · · · + |An |.
• Za proizvoljne skupove Ai , i = 1, 2, . . . , n, vrijedi:
|A1 × A2 × . . . An | = |A1 | · |A2 | · · · · · |An |.
Zadatak 1. Jedno dijete ima tri zelene drvene bojice razliˇcitih nijansi, dvije plave, dvije smede i jednu
ˇzutu. Na koliko razliˇcitih naˇcina dijete moˇze izabrati jednu bojicu?
Zadatak 2. Na koliko razliˇcitih naˇcina dijete iz prethodnog zadatka moˇze izabrati bojice za crtanje stabla sa smedim deblom i zelenom kroˇsnjom?
Zadatak 3. Na koliko razliˇcitih naˇcina ´ce dijete iz prethodnog zadatka mo´ci nacrtati stablo sa smedim
deblom, zelenom kroˇsnjom i plavim cvjeti´cima (iste nijanse)?
Kolegij: Matematika 2, ljetni semestar 2010./2011.
Asistentica: Sanda Bujaˇci´c
2
Zadatak 4. Na koliko razliˇcitih naˇcina moˇze dijete iz prethodnih zadataka izabrati boje za crtanje
stabla s deblom i kroˇsnjom razliˇcite boje ili nijanse?
Zadatak 5. U jednoj ˇskoli postoje tri prva razreda. U I A je 34 uˇcenika, u I B je 37 uˇcenika, a u
I C je 32 uˇcenika.
a) Na koliko razliˇcitih naˇcina moˇzemo izabrati dva predstavnika prvog razreda te ˇskole?
b) Na koliko razliˇcitih naˇcina moˇzemo izabrati dva predstavnika, ali pod uvjetom da su oni iz
razliˇcitih razreda?
Zadatak 6. U koˇsari se nalazi 12 jabuka i 10 kruˇsaka. Dunja ´ce uzeti jedan komad vo´ca - ili jabuku
ili kruˇsku. U kojem od tih sluˇcajeva ostaje ve´ci izbor za Jagodu koja namjerava uzet po jedan komad
vo´ca od svake vrste?
Zadatak 7. Na koliko razliˇcitih naˇcina moˇzemo iz skupine od 6 rajˇcica i 8 paprika staviti nekoliko
komada povr´ca u koˇsaru? Koˇsara smije ostati i prazna, bitno je samo koliko je komada kojeg povr´ca
u koˇsari.
Zadatak 8. Koliko je ˇsifri koje se sastoje od ˇcetiri slova i tri znamenke?
Kolegij: Matematika 2, ljetni semestar 2010./2011.
Asistentica: Sanda Bujaˇci´c
3
Zadatak 9.
a) Koliko ima prirodnih brojeva manjih od 10000 s razliˇcitim znamenkama?
b) Koliko ima ˇcetveroznamenkastih brojeva s razliˇcitim znamenkama?
c) Koliko ima prirodnih brojeva ve´cih ili jednakih broju 100, a manjih od 10000, s razliˇcitim znamenkama?
PERMUTACIJE
Permutacije bez ponavljanja
Broj permutacija bez ponavljanja:
Pn = n! = n(n − 1)(n − 2) · · · · · 2 · 1.
Zadatak 1. Dokazati da vrijedi:
Pn = (n − 1)(Pn−1 + Pn−2 ).
Kolegij: Matematika 2, ljetni semestar 2010./2011.
Asistentica: Sanda Bujaˇci´c
4
Zadatak 2. Broj permutacija skupa od n + 2 elementa 56 puta je ve´ci od broja permutacija skupa od
n elemenata. Koliki je n?
Zadatak 3. Ako skupu od n elemenata dodamo dva elementa, broj permutacija novog skupa je 90
puta ve´ci od broja permutacija starog skupa. Koliki je n?
Zadatak 4. Odredimo sve permutacije od slova u rijeˇci IVA!
Zadatak 5. Zadan je skup {a, b, c, d}. Koliko permutacija moˇzemo dobiti iz tog skupa?
Zadatak 6. Na koliko razliˇcitih naˇcina moˇzemo sloˇziti vlak od 12 vagona tako da u kompoziciju
budu ukljuˇceni svi vagoni?
Zadatak 7. Od znamenaka 0, 1, 2, 3, 4 sastavljeni su svi peteroznamenkasti brojevi koji nemaju jednake
znamenke. Koliko ih ima?
Zadatak 8. Na koliko se razliˇcitih naˇcina na jednoj ˇsahovskoj ploˇci moˇze postaviti osam topova tako
da se oni medusobno ne napadaju?
Kolegij: Matematika 2, ljetni semestar 2010./2011.
Asistentica: Sanda Bujaˇci´c
5
Zadatak 9. Pet djeˇcaka i pet djevojˇcica moramo smjestiti na 10 stolica u jednom redu tako da sjede
naizmjence. Na koliko naˇcina to moˇzemo uˇciniti?
ˇ
Zadatak 10. Cetiri
bijele i tri crne kuglice razliˇcitih veliˇcina treba poredati u niz tako da dvije jednako
obojene ne budu jedna do druge. Na koliko razliˇcitih naˇcina moˇzemo to uˇciniti?
Zadatak 11. Koliko permutacija skupa S = {1, 2, 5, 7, 9}
a) Poˇcinje brojem 9?
b) Ne poˇcinje ni s 1, ni s 5?
c) Ne zavrˇsava sa 75?
Zadatak 12. U zgradi od 10 katova je dizalo, a u dizalu troje ljudi: muˇskarac, ˇzena i dijete. Ako svatko
od njih izlazi na razliˇcitom katu, na koliko se razliˇcitih naˇcina dizalo moˇze isprazniti?
Kolegij: Matematika 2, ljetni semestar 2010./2011.
Asistentica: Sanda Bujaˇci´c
6
Zadatak 13. Osam prijatelja se okupilo u restoranu. Oko pono´ci gazda nudi pogodbu: ako svake subote
navrate k njemu, sjednu za isti okrugli stol, ali u drugom poretku, od trenutka kad se raspored ponovi,
on ´ce ih ˇcastiti. Kad ´ce gazda ˇcastiti?
Zadatak 14. Koja je po redu permutacija BIOGRAD u leksikografskom poretku uˇcinjenom od rijeˇci
ABGDIOR?
Permutacije s ponavljanjem
Broj permutacija s ponavljanjem:
Pr1 ,r2 ...rk (n) =
n!
.
r1 !r2 ! . . . rk !
Zadatak 1. Neka je zadan skup S kojih se sastoji od ˇcetiri elementa od koji se jedan element ponavlja
dva puta (na primjer, S = {a, a, b, c}). Koliki je broj permutacija skupa S?
Zadatak 2. Koliko se peteroznamenkastih brojeva moˇze napisati tako da se znameka 3 upotrijebi
tri, a znamenka 7 dva puta?
Kolegij: Matematika 2, ljetni semestar 2010./2011.
Asistentica: Sanda Bujaˇci´c
7
KOMBINACIJE
Kombinacije bez ponavljanja
Ukupan broj kombinacija bez ponavljanja r-tog reda u skupu od n elemenata odreden je formulom:
Kn,r =
n
n!
=
.
r
(n − r)! · r!
Napomena
n
= n,
1
n
= 1,
0
n
= 1,
n
n
n
=
.
r
n−r
Zadatak 1. Neka je zadan skup S = {a, b, c, d, e}. Odredite ukupan broj kombinacija drugog reda
u skupu S i ispiˇsite ih.
Zadatak 2. Rijeˇsite u skupu N:
Kn,3 : Kn,5 = 5 : 3.
Kolegij: Matematika 2, ljetni semestar 2010./2011.
Asistentica: Sanda Bujaˇci´c
8
Zadatak 3. Koliko troˇclanih podskupova ima u skupu od 8 elemenata? Koliko peteroˇclanih podskupova
ima u skupu od 7 elemenata?
Zadatak 4. Na koliko se razliˇcitih naˇcina moˇze odabrati poˇcetna petorka igraˇca u koˇsarkaˇskoj ekipi
koja ima 10 igraˇca?
Zadatak 5. Na jednom skupu je 52 ljudi izmedu kojih treba izabrati peteroˇclano predsjedniˇstvo.
Na koliko razliˇcitih naˇcina je to mogu´ce uˇciniti?
Zadatak 6. Tri mladi´ca i pet djevojaka igraju na plaˇzi odbojku. Na koliko razliˇcitih naˇcina se mogu
podijeliti u dvije ekipe po ˇcetiri osobe tako da svi mladi´ci ne budu u jednoj ekipi?
Zadatak 7. Na kirurˇskom odjelu neke bolnice je 30 lijeˇcnika. Na koliko razliˇcitih naˇcina se moˇze
odabrati jedan kirurg i ˇcetiri njegova asistenta?
Zadatak 8. Koliko je razliˇcitih ˇsestorki u igri LOTO 6/45?
Zadatak 9. Na koliko razliˇcitih naˇcina moˇzemo raspodijeliti 32 karte na 4 igraˇca tako da se svakom dijeli odjednom po 8 karata?
Zadatak 10. Na koliko razliˇcitih naˇcina moˇzemo podijeliti 12 ˇcokoladica na troje djece tako da jedno
dijete dobije 3, drugo 4, a tre´ce 5 ˇcokoladica?
Kolegij: Matematika 2, ljetni semestar 2010./2011.
Asistentica: Sanda Bujaˇci´c
9
Kombinacije s ponavljanjem
Ukupan broj kombinacija s ponavljanjem r-tog reda u skupu od n elemenata odreden je formulom:
0
Kn,r
n+r−1
=
.
r
Zadatak 1. U trgovini se mogu kupiti banane, jabuke i kruˇske. Na koliko naˇcina moˇzemo kupiti 2 kg
vo´ca ako moˇzemo kupiti po kilogram ponudenog vo´ca?
Zadatak 2. U cvje´carnici se prodaju mini ruˇze, ruˇze i ljiljani. Na koliko naˇcina je mogu´ce napraviti buket od 9 cvjetova?
Kolegij: Matematika 2, ljetni semestar 2010./2011.
Asistentica: Sanda Bujaˇci´c
10
BINOMNI TEOREM
Teorem
Ako su a, b ∈ R i n ∈ N, tada vrijedi formula koju zovemo binomna formula:
(a + b)n =
n n n 0
n n−1
n 0 n X n n−k k
a b +
a
b + ··· +
a b =
a
b .
0
1
n
k
k=0
Napomena
n
(a − b) =
n
X
k=0
n n−k k
(−1)
a
b .
k
k
Svojstva binomnih koeficijenata
Binomni koeficijent nk (ˇcitamo ”n povrh k”), n, k ∈ N, n ≥ k ima sljede´ca svojstva:
n
n(n − 1) . . . (n − k + 1)
•
=
k(k − 1) . . . 2 · 1
k
0
n
•
=
=1
0
0
n
•
=n
1
n
•
=1
n
n
n
•
=
k
n−k
n
n
n+1
•
+
=
.
k
k+1
k+1
Zadatak 1. Odrediti deseti ˇclan u razvoju binoma
√
2
3
(√
− 3)n
3
2
x
ako je binomni koeficijent tre´ceg ˇclana jednak 66.
Zadatak 2. Izraˇcunajte:
n
n+2
5
=
.
3
4
Download

Kombinatorika.pdf