Kombinatorika

Izvor: Wikipedia

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

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

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

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

Permutacije[uredi - уреди]

  • Permutacije bez ponavljanja članova skupa:
 P = {n!}

gde je n broj elemenata skupa koji mogu biti izabrani.

  • Permutacije sa ponavljanjem članova skupa:
 Pp = \frac{n!}{r!s!}

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

  • Varijacije bez ponavljanja članova skupa:
 V = n(n-1)(n-2)...(n-r+1) = \frac{n!}{(n-r)!} = {n \choose r}r! = Kr!

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

  • Varijacije sa ponavljanjem članova skupa:
 Vp = n^r \,\!

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

Kombinacije[uredi - уреди]

  • Kombinacije bez ponavljanja članova skupa:
 K = \frac{n!}{r!(n - r)!} = {n \choose r} = {n \choose {n-r}}

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

  • Kombinacije sa ponavljanjem članova skupa:
 Kp = {{(n + r - 1)!} \over {r!(n - 1)!}} = {{n + r - 1} \choose {r}} = {{n + r - 1} \choose {n - 1}}

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

Literatura[uredi - уреди]

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