Kombinatorika je grana matematike koja se bavi izborom, uređenjem i operacijama nad konačnim ili prebrojivim diskretnim strukturama. Osnovni problemi kojima se bavi kombinatorika su:
- prebrojavanje struktura,
- određivanje mogućnosti za ispunjenje nekog kriterijuma,
- konstruisanje i analiziranje objekata koji ispunjavaju postavljeni kriterijum,
- nalaženje najvećih, najmanjih i optimalnih objekata,
- nalaženje algebarskih struktura i dr.
Značajna oblast kombinatorike je teorija grafova.
Problemi kombinatorike se javljaju u mnogim granama matematike:
- algebri,
- verovatnoći,
- geometriji i dr.
Kombinatorika se primenjuje i u optimizaciji, informatici, fizici i dr.
U verovatnoći se kombinatorika često primenjuje kada je potrebno izbrojati načine na koje se može desiti neki događaj. Na primer, prilikom izračunavanja a priori verovatnoće, potrebno je utvrditi ukupan broj i broj povoljnih elementarnih događaja u nekom prostoru uzorka, a prosto brojanje nije pogodno jer je prostor uzorka veliki.
U kombinatorici postoji jedna osnovna ideja. Pretpostavimo da se iz nekog skupa {a1, a2,...an} bira jedan element ai. Zatim se bira element bij iz drugog skupa {bi1, bi2,...,bim}. Svaki par (ai, bij) predstavlja rezultat i obeležava se sa ƒ(i, j). Ako su svi rezultati drugačiji, postoji nm mogućih rezultata. Ako se, zatim, bira element cijk iz skupa {cij1, cij2,...,cijp}, tada se dobija rezultat ƒ (ai, bij, cijk), a ukupan broj mogućih rezultata je nmp. Ovo važi za bilo koji konačan broj skupova iz kojih se bira.
Postoje dve glavne vrste varijacija ove ideje:
- Prilikom biranja, moguće je izabrani element vraćati u skup, tako da ima šansu da bude izabran ponovo, ili vršiti biranje iz preostalih elemenata, tako da izabrani element više ne učestvuje u biranju. U prvom slučaju govorimo o biranju sa vraćanjem (na primer bacanje kockice) dok se u drugom slučaju radi o biranju bez vraćanja (na primer igra na sreću loto). Koncept "vraćanja" elementa koji se bira je bitan u teoriji verovatnoće, jer određuje međusobnu zavisnost događaja.
- Druga varijacija osnovne ideje uzima u obzir redosled izabranih elemenata u rezultatu, na osnovu čega rezultat može biti uređen, kod kojeg je bitan redosled izabranih elemenata i neuređen kod kojeg redosled nije bitan.
Mnogi problemi kojima se bavi kombinatorika su u prošlosti rešavani izolovano, a tek u 20. veku kombinatorika se razvija kao posebna grana matematike. Pojavom i razvojem savremenih računara ubrzava se i razvoj kombinatorike.
Komentari (0)