Kombinatorika

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

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

Magični kvadrat reda 4 na gravuri Melanholija Albrechta Dürerja

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 2⁶ − 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. Še posebej ga je zanimalo na koliko načinov se lahko tvori 6 zlogovnih metrumov iz kratkih in dolgih tonov. 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. Pingalovo delo o prozodiji sta razširila tudi Bhaskara (1114–1185) 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. 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. Zamisli o permutacijah in kombinacijah so uporabili tudi na področju glasbe, medicine, arhitekture in astrologije. 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 2⁶ = 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 2³ = 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öder-Hiparhovimi števili. 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. Če se iz tega števila izključijo rešitve zaradi sukanja in zrcaljenja, ostane 536 rešitev. 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×10¹² in je tudi malo verjetno, saj je preveč zaokroženo in ni kaj več kot ugibanje.

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. Te formule so bile verjetno znane indijskim matematikom že v 6. stoletju.

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

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

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.

Permutacije

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 \cdot 3\cdot 2\cdot 1\!\,.$

To se zapiše tudi s simbolom:

$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_{2}\,$ 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)

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}=n(n-1)\cdots (n-k+1)={\frac {n!}{(n-k)!}}={\binom {n}{k}}k!,\qquad (1\leq k\leq n,\quad (n,k)\in \mathbb {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

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\leq k\leq n,\quad (n,k)\in \mathbb {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:

${}^{(p)}C_{n}^{k}=\left({n \choose k}\right)\!\,.$

Leksikografski vrstni red

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

• particija (teorija števil)
• particija množice
• ravninska particija
• telesna particija
• kompozicija
• kombinatorična biologija
• kombinatorična kemija
• kombinatorična analiza podatkov
• kombinatorična teorija iger
• kombinatorična teorija grup
• filogenija

Viri

• Bhaskara (1150), The Lilavati of Bhaskara (v angleščini), Univerza Brown, arhivirano iz prvotnega spletišča dne 25. marca 2008, pridobljeno 6. marca 2008
• Biggs, Norman Linstead (1979), »The Roots of Combinatorics«, Historia Mathematica, 6: 109–136, doi:10.1016/0315-0860(79)90074-0
• Biggs, Norman Linstead; Lloyd, Keith; Wilson, Robin (1995), »44«, v Graham, Ronald; Grötschel, Martin; Lovász, László (ur.), Handbook of Combinatorics (Google book), MIT Press, str. 2163–2188, ISBN 0-262-57172-2, pridobljeno 8. marca 2008
• Björner, Anders; Stanley, Richard P. (2010), A Combinatorial Miscellany (PDF)
• Cvetković, Dragoš M.; Simić, Slobodan K. (1990), Kombinatorika - Klasična i moderna (2. spr. in dop. izd.), Beograd: Naučna knjiga, COBISS 1474060, ISBN 86-23-20216-3
• Devlin, Keith (Oktober 2002), »The 800th birthday of the book that brought numbers to the west«, Devlin's Angle (v angleščini), pridobljeno 8. marca 2008
• Dieudonné, Jean, »The Rhind/Ahmes Papyrus - Mathematics and the Liberal Arts«, Historia Math (v angleščini), Trumanova državna univerza, arhivirano iz prvotnega spletišča dne 12. decembra 2012, pridobljeno 6. marca 2008
• Goonatilake, Susantha (1998), Toward a Global Science, Indiana University Press, ISBN 978-0-253-33388-9
• Gow, James (1968), A Short History of Greek Mathematics, AMS Bookstore, ISBN 0-8284-0218-3
• Habsieger, Laurent; Kazarian, Maxim; Lando, Sergei (1998), »On the Second Number of Plutarch«, American Mathematical Monthly, 105 (5): 446
• Hall, Rachel (16. februar 2005), Math for Poets and Drummers-The Mathematics of Meter (PDF) (v angleščini), arhivirano iz prvotnega spletišča (PDF) dne 7. septembra 2008, pridobljeno 5. marca 2008
• Kolata, Gina (14. december 2003), »Archimedes' Puzzle, a New Eureka Moment«, The New York Times, pridobljeno 23. julija 2007
• Koshy, Thomas (2001), Fibonacci and Lucas numbers with applications, John Wiley & Sons, ... preden je Fibonacci predlagal problem, sta ga podala Virahanka (med letoma 600 in 800), Gopala (pred letom 1135), ...
• Kulkarni, Amba (22. marec 2007), Recursion and Combinatorial Mathematics in Chandashāstra, arXiv:math/0703658
• Maistrov, L. E. (1974), Probability Theory: A Historical Sketch, Academic Press, ISBN 9781483218632, angleški prevod iz ruske izdaje leta 1967
• O'Connor, John J.; Robertson, Edmund Frederick (november 2000), Mahavira (v angleščini), Arhiv zgodovine matematike MacTutor, Univerza svetega Andreja, pridobljeno 6. maja 2016{{citation}}: Vzdrževanje CS1: samodejni prevod datuma (povezava)
• Pegg, Ed mlajši (17. november 2003), The Loculus of Archimedes, Solved, Matematična zveza Amerike, pridobljeno dne 2008-05-18
• Puttaswamy, Tumkur K. (2000), »The Mathematical Accomplishments of Ancient Indian Mathematicians«, v Selin, Helaine (ur.), Mathematics Across Cultures: The History of Non-Western Mathematics, Nizozemska: Kluwer Academic Publishers, ISBN 978-1-4020-0260-1
• Stanley, Richard Peter (1997), »Hipparchus, Plutarch, Schröder, and Hough«, American Mathematical Monthly, 104 (4): 344–350
• Stöcker, Horst (2006), Matematični priročnik z osnovami računalništva, Ljubljana: Tehniška založba Slovenije, COBISS 229576192, ISBN 86-365-0587-9
• Tetlow, Philip (2007), The Web's awake: an introduction to the field of Web science and the concept, John Wiley & Sons, ISBN 0-470-13794-0, To zaporedje sta prva predstavila indijska matematika Gopala in Hemačandra leta 1150, ki sta raziskovala možne načine eksaktnega pakiranja predmetov dolžine 1 in 2 v zabojnike. Na zahodu je zaporedje prvi raziskoval ...
• Van Nooten, B. (1. marec 1993), »Binary numbers in Indian antiquity«, Journal of Indian Philosophy, 21 (1): 31–50, doi:10.1007/BF01092744, pridobljeno 6. maja 2010
• Vilenkin, Naum Jakovljevič (1975), Популярная комбинаторика (v ruščini), Moskva: Nauka, arhivirano iz prvotnega spletišča (DJVU) dne 5. junija 2016, pridobljeno 6. maja 2016
• White, Arthur T. (1987), »Ringing the Cosets«, American Mathematical Monthly, 94 (8): 721–746
• White, Arthur T. (1996), »Fabian Stedman: The First Group Theorist?«, American Mathematical Monthly, 103 (9): 771–778
• Wilson, Robin James; Watkins, John Jaeger (1997), Uvod v teorijo grafov [Graphs : an introductory approach] (Knjižnica Sigma - 63 izd.), Ljubljana: DFMA Slovenije, COBISS 72250368, ISBN 961-212-081-1

Zunanje povezave

• Weisstein, Eric Wolfgang. »Combinatorics«. MathWorld.