Kombinatorika

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi 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).[1]

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.

Osnovni kombinatorni problemi[uredi | uredi kod]

Osnovni kombinatorni principi[uredi | uredi kod]

Osnovni kombinatorni objekti[uredi | uredi kod]

Permutacije[uredi | uredi kod]

  • Permutacije bez ponavljanja članova skupa:

gde je n broj elemenata skupa koji mogu biti izabrani.

  • Permutacije sa ponavljanjem članova skupa:
[2]

Varijacije (r-permutacije)[uredi | uredi kod]

  • 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. [3]

Kombinacije[uredi | uredi kod]

  • 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. [4]

Izvori[uredi | uredi kod]

  1. Grupa autora, "Matematika I Algebra", Beograd 2004.
  2. Permutacija
  3. Varijacije
  4. Kombinacije

Literatura[uredi | uredi kod]

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