Kombinatorika

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Zgled kombinatoričnega problema je samoizogibni sprehod (SAW) v kvadratni rešetki 15 × 15.

Kombinatórika je matematična disciplina, ki preučuje končne ali števne diskretne strukture, na koliko načinov je možno razporediti, preurediti oziroma izbrati določeno množico elementov. Med aspekte kombinatorike spadajo: štetje struktur dane vrste in velikosti (enumerativna kombinatorika), odločanje o določenih pogojih za kriterije, ter konstruiranje in analiziranje objektov za katere veljajo kriteriji (kot v teoriji kombinatorične konstrukcije in teoriji matroidov), iskanje »največjih«, »najmanjših« ali »optimalnih« objektov (ekstremalna kombinatorika in kombinatorična optimizacija), in raziskovanje kombinatoričnih struktur v algebrskem smislu, ali uporaba algebrskih tehnik na kombinatorične probleme (algebrska kombinatorika).

Kombinatorični problemi se pojavljajo na mnogih področjih čiste matematike, še posebej v algebri, verjetnostnem računu, topologiji in geometriji.[1] Kombinatorika ima tudi veliko uporab v matematični optimizaciji, računalništvu, ergodični teoriji in statistični fiziki. Veliko kombinatoričnih vprašanj se je zgodovinsko obravnavalo v osami, in dalo ad hoc rešitve problemov v nekaterih matemtičnih kontekstih. V poznem 20. stoletju so razvili močne in splošne teoretične metode, tako da je kombinatorika zasluženo postala neodvisna veja matematike. Drugače pa se kombinatoriko pogosto šteje za pomožno panogo verjetnostnega računa. Ena od najstarejših in najbolj dostopnih delov kombinatorike je teorija grafov, ki ima tudi sama veliko naravnih povezav z drugimi področji. Kombinatorika se velikokrat rabi v računalništvu pri iskanju formul in obravnavanju ocen pri analizi algoritmov.

Matematik ali matematičarka, ki raziskujeta na področju kombinatorike, sta kombinatorik in kombinatoričarka.

Osnovni kombinatorični problemi[uredi | uredi kodo]

Permutacije[uredi | uredi kodo]

Permutacije treh raznobarvnih kroglic urejene po leksikografskem vrstnem redu

Permutacije so različne razporeditve n elementov na n prostih mest. Pri tem je pomembno, da je število prostih mest enako kot število predmetov, ki se jih razporeja. Predmeti so lahko med seboj vsi različni (permutacije brez ponavljanja) ali pa tudi ne (permutacije s ponavljanjem).

Kombinatorika se ukvarja z vprašanjem, koliko je vseh permutacij in kako jih razporediti po smiselnem vrstnem redu.

Število permutacij n različnih elementov (brez ponavljanja) je enako produktu vseh naravnih števil od 1 do n:

 P=n\cdot(n-1)\cdot\cdots\cdot3\cdot2\cdot1 \!\, .

To se zapiše tudi s simbolom:

 P=n! \!\, ,

(beri: n fakulteta ali n faktoriela).

Variacije[uredi | uredi kodo]

Variacije so podobne permutacijam, le da število prostih mest ni nujno enako kot število predmetov.

Pri variacijah brez ponavljanja je na voljo manj prostih mest kot je predmetov, zato nekaj predmetov ostane nerazporejenih. Število variacij n elementov na r prostih mest brez ponavljanja je enako:

 V=\frac{n!}{(n-r)!} \!\, .

Pri variacijah s ponavljanjem se dopusti, da se predmet v razporeditvi lahko pojavi poljubno mnogokrat. Število variacij n elementov na r prostih mest s ponavljanjem je enako:

 V=n^{r} \!\, .

Kombinacije[uredi | uredi kodo]

Kombinacije so podobne variacijam, le da pri kombinacijah ni pomemben vrstni red (razporeditev) izbranih predmetov, pač pa samo to, kateri predmeti so bili izbrani.

Tudi pri kombinacijah se loči kombinacije s ponavljanjem in kombinacije brez ponavljanja.

Kombinacije brez ponavljanja so izbire k različnih elementov izmed n različnih elementov, ki so na voljo. Število vseh možnih izbir je enako:

 C=\frac{n!}{k!\cdot(n-k)!} \!\, .

To se pogosto označi tudi z binomskim simbolom:

 C={n \choose k} \!\, .

Pri kombinacijah s ponavljanjem je na voljo n različnih elementov, izmed njih pa se želi izbrati k elementov tako, da se lahko posamezni element izbere tudi večkrat (poljubno mnogokrat). Število kombinacij s ponavljanjem je enako:

 C={{n+k-1} \choose k} \!\, .

To se označi tudi z dvema oklepajema:[2]

 C= \left( {n \choose k} \right) \!\, .

Leksikografski vrstni red[uredi | uredi kodo]

Eden od osnovnih problemov kombinatorike je tudi vprašanje, kako urediti permutacije, variacije ali kombinacije po smiselnem vrstnem redu. Najpogosteje se uporablja leksikografski vrstni red, ki je posplošitev običajnega abecednega vrstnega reda, kakršnega se uporablja v leksikonih (od tod ime leksikografski), slovarjih, imenikih in abecednih seznamih.

Črke abecede so urejene po standardnem vrstnem redu. Pri razvrščanju besed, ki imajo več črk, pa se upošteva naslednja pravila:

  • če imata dve besedi različni prvi črki, se ju razvrsti glede na prvi črki
  • če imata dve besedi enako prvo črko, pa različni drugi črki, se ju razvrsti glede na drugi črki
  • če se dve besedi ujemata v prvih n črkah, na naslednjem mestu pa imata različni črki, se ju razvrsti glede na ti dve črki

Zgledi leksikografskega razvrščanja slovenskih besed:

  • beseda AVTO je pred besedo BRAT (ker je A pred B)
  • beseda ATA je pred besedo AVTO (prvi črki sta enaki, zato se pogleda drugi črki: T pa je pred V)
  • beseda AVTOMAT je pred besedo AVTOMOBIL (črke AVTOM se ujemajo, zato se pogleda naslednji črki: A je pred O)

V kombinatoriki se pogosto uporablja isto načelo tudi za urejanje drugih objektov, ne le za črke. Zgled: Če se določi, da je modra barva (M) pred rdečo (R) in ta pred zeleno (Z), se lahko vse permutacije treh raznobarvnih kroglic uredi po leksikografskem redu (glej sliko zgoraj):

M R Z
M Z R
R M Z
R Z M
Z M R
Z R M

Glej tudi[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]