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 iz množice s končno mnogo elementi. Elementi so lahko poljubni – na primer: osebe, predmeti, števila, ki se jih označi s simboli, števkami, črkami, barvami, ipd.).[1] 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.[2] 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 najdostopnejših 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.

Zgodovina[uredi | uredi kodo]

Arhimedov Ostomachion v kvadratni rešetki 12 × 12
Zgled izmenjevalnega zvonjenja (s šestimi zvonovi), eden najzgodnejših netrivialnih rezultatov v teoriji grafov
Heksagram 37: ䷤ (家人: džiā rén) iz starodavnega kitajskega prerokovalnega besedila I Čing
Glavni članek: zgodovina kombinatorike.

Osnovni kombinatorični koncepti in enumerativni rezultati so se pojavili v starem veku. Najstarejša povezava s kombinatoriko izhaja iz Rhindovega papirusa – problem 79 za implementacijo geometrične vrste.

V 6. stoletju pr. n. št. je indijski zdravnik Sušruta v sanskrtskem besedilu Sušrutasamhita trdil, da se iz 6-ih različnih okusov lahko naredi 63 kombinacij, najprej z enim, nato z dvema itd, ter tako izračunal vseh 26 − 1 možnosti. To predstavlja enega prvih kombinatoričnih problemov. Džainistično besedilo Bhagabatisutra omenja isti problem. Delo je bilo napisano okoli leta 300 pr. n. št. in je med prvimi omenjalo binomske koeficiente (izbirne funkcije). Staroindijski matematik Pingala (okoli 5. stoletje pr. n. št.), avtor razprave Čandašastra (Čandasutra), najstarejšega sanskrtskega besedila o metriki in prozodiji. V delu je opisal dvojiški številski sistem v povezavi s sistematičnim štetjem metrumov s fiksnimi vzorci kratkih in dolgih zlogov.[3] Še posebej ga je zanimalo na koliko načinov se lahko tvori 6 zlogovnih metrumov iz kratkih in dolgih tonov.[4][5] Poleg tega je našel število metrumov, ki imajo n dolgih tonov in k kratkih, kar je enakovredno binomskim koeficientom. Halajudha je v 10. stoletju napisal tolmač Pingalovega dela in ga razširil. V tolmaču je predstavil aritmetični trikotnik (imenovan meruprastara). Pingalovo delo vsebuje tudi Fibonaccijeva števila, imenovana matrameru.[6] Pingalovo delo o prozodiji sta razširila tudi Bhaskara (1114–1185)[7] in Hemačandra (1088–1173) v istem času. Bhaskara je prvi našel posplošeno izbirno funkcijo, čeprav jo je morda Brahmagupta (598–668) poznal že prej.[8] Hemačandra je obravnaval število verznih ritmov dolžine n, in pokazal, da se lahko tvorijo z dodajanjem kratkega zloga k ritmu dolžine n − 1, ali z dolgim zlogom k ritmu dolžine n − 2. Ta rekurzivna zveza F(n) = F(n − 1) + F(n − 2) določa Fibonaccijevo zaporedje.[9][10] Zamisli o permutacijah in kombinacijah so uporabili tudi na področju glasbe, medicine, arhitekture in astrologije.[6] Džainistično raziskovanje kombinatoričnih problemov se lahko obravnava v smislu, da se filozofske izjave obdelujejo mehansko in tako predstavljajo prednike Booleove algebre in simbolne logike.

Starodavno kitajsko prerokovalno besedilo I Čing obravnava različne pomene heksagramov. Za poznavanje pomenov je potrebno znanje o možnem številu heksagramov. Ker je vsak heksagram permutacija s ponavljanjem 6-ih črt (爻: jao), kjer je vsaka črta lahko v dveh stanjih (polnem ali prekinjenem), kombinatorika da odgovor, da obstaja 26 = 64 heksagramov. Verjetno je menih tudi preštel število konfiguracij igre, podobne goju okoli leta 700. Čeprav je imela Kitajska relativno malo napredovanj v enumerativni kombinatoriki, so rešili problem kombinatorične konstrukcije, normalni magični kvadrat reda 3 okoli leta 100 v kvadratu Lo Šu. V daoistični kozmologiji so uporabljali 8 trigramov (八卦: bagua – dobesedno »osem simbolov«) za predstavitev osnovnih načel stvarnosti v smislu osmih medsebojno povezanih konceptov: nebesa/nebo, jezero/barje, ogenj, grom, veter, voda, gora in zemlja. Število trigramov je podobno 23 = 8.

Starogrški zgodovinar Plutarh (okoli 48–okoli 127) je obravnaval spor med Hrizipom (281 pr. n. št.–205 pr. n. št.) in Hiparhom (okoli 190 pr.n.št.–okoli 120 pr.n.št.) o dokaj kočljivem enumerativnem problemu, ki se je kasneje izkazal, da je povezan s Schröderjevimi števili.[11][12] Arhimed (287 pr. n. št.–212 pr. n. št.) je v delu Ostomachion obravnaval prekrivalno sestavljanko, podobno tangramu, in izračunal ploščine 14-ih trikotnikov, ki jih je mogoče sestaviti v kvadrat. Poskušal je ugotoviti na koliko načinov je mogoče dele sestavljanke sestaviti v obliko kvadrata. Reviel Netz z Univerze Stanford je izračunal, da je to mogoče izvesti na 17.152 načinov.[13] Če se iz tega števila izključijo rešitve zaradi sukanja in zrcaljenja, ostane 536 rešitev.[14] Plutarh je napisal, da je Ksenokrat odkril število možnih različnih zlogov v stari grščini. To je malo verjetno, saj je to ena od redkih omemb kombinatorike pri starih Grkih. Število je 1,002 · 1012 in je tudi malo verjetno, saj je preveč zaokroženo in ni kaj več kot ugibanje.[15][16]

V srednjem veku so nadaljevali z raziskovanjem kombinatorike, v večji meri zunaj evropske civilizacije. Indijski matematik Mahavira (okoli 850) je posplošil zamisli iz Bhagabatisutre in podal formule za število permutacij in kombinacij.[17][18] Te formule so bile verjetno znane indijskim matematikom že v 6. stoletju.[19]

Pesnik, filozof in astronom rabi Abraham Ibn Ezra (1089–1167) je okoli leta 1140 dognal simetrijo binomskih koeficientov, sklenjeno formulo pa je kasneje leta 1321 dobil filozof, talmudist, matematik, zdravnik, astronom in astrolog Levi ben Geršon (bolj znan kot Gersonid) (1288–1344).[20] Aritmetični trikotnik, grafični diagram, ki prikazuje povezavo med binomskimi koeficienti, so predstavili matematiki že v 10. stoletju, kasneje pa je postal znan kot Pascalov trikotnik. Kasneje v srednjeveški Angliji so v kampanologiji našli primere, ki so sedaj znani kot Hamiltonovi cikli v določenih Cayleyjevih grafih na permutacijah.[21][22]

V Evropo je kombinatorika prišla v 13. stoletju prek Leonarda Fibonaccija (1170–1250) in Jordana Nemorarija (okoli 1170–1237). Fibonaccijeva Knjiga o abaku (Liber Abaci) je predstavila veliko arabskih in indijskih zamisli, vključno s Fibonaccijevimi števili.[23][24] Nemorarij je razporedil binomske koeficiente v trikotnik v propoziciji 70 svojega dela De elementis arismetice artis. Podobno so to storili na Srednjem vzhodu leta 1265 in na Kitajskem okoli leta 1300.

Med renesanso je poleg preostale matematike in drugih znanosti kombinatorika doživela preporod. Gerolamo Cardano (1501–1576) je napisal matematično razpravo o igri s kockami, ki je izšla po njegovi smrti. S teorijo te igre sta se ukvarjala tudi Niccolo Fontana Tartaglia (1499–1557) in Galileo Galilei (1564–1642).

Dela Pascala (1623–1662), Newtona (1642–1727), Jakoba Bernoullija I. (1654–1705) in Eulerja (1707–1783) so postala temeljno in porajajoče področje. V sodobnem času je delo Jamesa Josepha Sylvestra (1814–1897) (pozno 19. stoletje) in Percyja MacMahona (1854–1929) (zgodnje 20. stoletje) pomagalo položiti temelje za enumerativno in algebrsko kombinatoriko. Tudi teorija grafov je v istem času doživela veliko zanimanje, še posebej v zvezi s problemom štirih barv.

V drugi polovici 20. stoletja je kombinatorika doživela hitro rast, kar je vodilo do ustanovitve mnogih strokovnih revij in konferenc o tej temi.[25] Deloma je bila rast pogojena z novimi povezavami in uporabami na drugih področjih, od algebre do verjetnosti, od funkcionalne analize do teorije števil, itd. Te povezave so prelile meje med kombinatoriko in deli matematike ter teoretičnega računalništva, istočasno pa so vodile do delne razdrobitve področja.

Osnovni kombinatorični problemi[uredi | uredi kodo]

Med osnovne pojme (klasične) kombinatirike spadajo permutacije, variacije, kombinacije, particije in kompozicije. Eden od glavnih problemov v kombinatoriki je določevanje števila raznih kombinatoričnih objektov.[26]

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} = n\cdot(n-1)\cdot\cdots\cdot3\cdot2\cdot1 \!\, .

To se zapiše tudi s simbolom:[1]

 P_{n} = n! \!\, ,

(beri: n fakulteta ali n faktoriela).

Permutacije s ponavljanjem elementov množice:

 P_{n}^{(p)} = \frac{n!}{r!s!} \!\, .

Permutacije s ponavljanjem n elementov, kjer je prvih n_{1}\, med seboj enakih, drugih n_{21}\, med seboj enakih, ..., in zadnjih n_{k}\, med seboj enakih:

 P_{n}^{(n_{1}, n_{2}, \ldots, n_{k})} = \frac {n!} {n_{1} ! n_{2} ! \ldots n_{k} !}, \qquad \sum_{i=1}^{k} n_{i}= n \!\, .

Variacije (r-permutacije)[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 k prostih mest brez ponavljanja je enako:

 V_{n}^{k} = \frac{n!}{(n-k)!}, \qquad ( 1 \le k \le n, \quad (n,k) \in \N ) \!\, .

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

 {}^{(p)}V_{n}^{k} = n^{k} \!\, .

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_{n}^{k} = \frac{n!}{k!\cdot(n-k)!}, \qquad ( 0 \le k \le n, \quad (n,k) \in \N ) \!\, .

To se pogosto označi tudi z binomskim simbolom:

 C_{n}^{k} = {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:

 {}^{(p)}C_{n}^{k} = {{n+k-1} \choose k} \!\, .

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

 {}^{(p)}C_{n}^{k} = \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]