Kombinatorika

Iz Wikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu

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 verovatnoć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).

Kombinatorika se podjednako tiče rešavanja problema kao i izgradnje teorija, mada je razvila moćne teorijske modele, pogotovo u drugom delu dvadesetog veka. 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 podelu ili uređenu podelu skupa.

Primer 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.

Sledi primer malo komplikovanijeg problema: Ako je dato -{n}- ljudi, da li je moguće podeliti ih u skupove tako daje 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}-.

Puzzle stub cropped.png Ovaj dio članka je u začetku.
Pogledajte kako uređivati članak i pomozite Wikipediji u njegovom proširenju.

Osnovni kombinatorni problemi[uredi - уреди | uredi izvor]

Osnovni kombinatorni principi[uredi - уреди | uredi izvor]

Osnovni kombinatorni objekti[uredi - уреди | uredi izvor]

Permutacije[uredi - уреди | uredi izvor]

  • Permutacije bez ponavljanja članova skupa:

gde je n broj elemenata skupa koji mogu biti izabrani.

  • Permutacije sa ponavljanjem članova skupa:

Varijacije (r-permutacije)[uredi - уреди | uredi izvor]

  • Varijacije bez ponavljanja članova skupa:

gde je n broj elemenata skupa koji mogu biti izabrani, a r broj elemenata koji treba da budu izabrani.

  • Varijacije sa ponavljanjem članova skupa:

gde je n broj elemenata skupa koji mogu biti izabrani, a r broj elemenata koji treba da budu izabrani.

Kombinacije[uredi - уреди | uredi izvor]

  • Kombinacije bez ponavljanja članova skupa:

gde je n broj elemenata skupa koji mogu biti izabrani, a r broj elemenata koji treba da budu izabrani.

  • Kombinacije sa ponavljanjem članova skupa:

gde je n broj elemenata skupa koji mogu biti izabrani, a r broj elemenata koji treba da budu izabrani.

Literatura[uredi - уреди | uredi izvor]

  • Grupa autora, „Matematika I Algebra“, Beograd 2004.
  • O. Šlimlih i J. Majcen, „Logaritamske tablice“, Zagreb 1972.