2
Sadržaj
1.Uvod.........................................................................................................................................3
2.Pojam kombinatorike...............................................................................................................4
2.1.Kombinatorna prebrojavanja.................................................................................................5
2.1.1.Permutacije, varijacije i kombinacije.................................................................................6
2.1.2.Teorem o uzastopnom prebrojavanju.................................................................................7
2.2.Dirichletov princip................................................................................................................7
2.3.Invarijante.............................................................................................................................8
2.5.Osnovni skup i uzorak.........................................................................................................11
3.Zaključak................................................................................................................................13
4.Literatura................................................................................................................................14
4
2.Pojam kombinatorike
Kombinatorika je grana čiste matematike koja se bavi proučavanjem diskretnih (i obično
konačnih) objekata. Povezana je sa mnogim drugim granama matematike, poput algebre,
teorije vjerovatnoće, i geometrije, kao i sa raznim oblastima u računarstvu i statističkoj fizici.
Aspekti kombinatorike uključuju prebrojavanje objekata koji zadovoljavaju određeni
kriterijum (
enumerativna kombinatorika
), određivanje da li neki kriterijum može biti
ispunjen, konstruisanje i analiziranje objekata koji ispunjavaju neki kriterijum, nalaženje
najvećih najmanjih ili optimalnih objekata, i nalaženje algebarskih struktura u koje ovi objekti
mogu spadati (
algebarska kombinatorika
).
1
Kombinatorika se podjednako tiče rješavanja problema kao i izgradnje teorija, mada je razvila
moćne teorijske modele, pogotovo u drugom dijelu dvadesetog vijeka. Jedna od najstarijih i
najčešće korišćenih oblasti kombinatorike je teorija grafova, koja takođe ima izuzetno brojne
veze sa drugim oblastima. Postoje mnoge kombinatorne šeme i teoreme u vezi sa strukturom
kombinatornih skupova. One se obično fokusiraju na podjelu ili uređenu podjelu skupa.
PRIMJER 1:
Primjer kombinatornog problema može biti:
Na koliko načina je moguće urediti špil od 52 različite karte za igranje?
Odgovor je 52! (52 faktorijel), što je približno jednako 8,0658 × 1067.
PRIMJER 2:
Slijedi primjer malo komplikovanijeg problema:
Ako je dato -{n}- ljudi, da li je moguće podijeliti ih u skupove tako da je svaka osoba u
najmanje jednom skupu, svaki par osoba je u tačno jednom skupu zajedno, svaka dva skupa
imaju tačno jednu zajedničku osobu, i nijedan skup ne sadrži sve osobe, sve osim jedne osobe
ili tačno jednu osobu?
Odgovor zavisi od -{n}-.
1
Tošić R., Kombinatorika, Prirodno-matematički fakultet Univerziteta u Novom Sadu, Novi Sad, 1999.str.42
