Kombinatorna matematika

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.^[2]

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 × 10⁶⁷. 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.

Puni obim kombinatorike nije univerzalno prihvaćen.^[3] Prema H.J. Rajseru, definicija subjekta je teška jer prekoračuje toliko matematičkih podela.^[4] U meri u kojoj se oblast može opisati tipovima problema kojima se bavi, kombinatorika je uključena u:

nabrajanje (prebrojavanje) određenih struktura, koje se ponekad nazivaju aranžmani ili konfiguracije u veoma opštem smislu, povezanih sa konačnim sistemima,
postojanje takvih struktura koje zadovoljavaju određene date kriterijume,
konstrukcija ovih struktura, možda na mnogo načina, i
optimizacija: pronalaženje „najbolje“ strukture ili rešenja među nekoliko mogućnosti, bilo da je „najveća“, „najmanja“ ili zadovoljavanje nekog drugog kriterijuma optimalnosti.

Leon Mirski je rekao: „kombinatorika je niz povezanih studija koje imaju nešto zajedničko, a ipak se uveliko razlikuju u svojim ciljevima, njihovim metodama i stepenu koherentnosti koji su postigli.“^[5] Jedan od načina da se definiše kombinatorika je, možda, da opiše svoje podele sa njihovim problemima i tehnikama. Ovo je pristup koji se koristi u nastavku. Međutim, postoje i čisto istorijski razlozi za uključivanje ili neuključivanje nekih tema pod okrilje kombinatorike.^[6] Iako se prvenstveno bave konačnim sistemima, neka kombinatorna pitanja i tehnike mogu se proširiti na beskonačno (konkretno, prebrojivo) ali diskretno okruženje.

Kombinatorika je dobro poznata po širini problema kojima se bavi. Kombinatorni problemi se javljaju u mnogim oblastima čiste matematike, posebno u algebri, teoriji verovatnoće, topologiji i geometriji,^[7] kao i u mnogim oblastima njene primene. Mnoga kombinatorna pitanja su istorijski razmatrana izolovano, dajući ad hok rešenje za problem koji se javlja u nekom matematičkom kontekstu. U kasnijem dvadesetom veku, međutim, razvijene su moćne i opšte teorijske metode, čime je kombinatorika postala nezavisna grana matematike sama po sebi.^[8] Jedan od najstarijih i najpristupačnijih delova kombinatorike je teorija grafova, koja sama po sebi ima brojne prirodne veze sa drugim oblastima. Kombinatorika se često koristi u računarstvu za dobijanje formula i procena u analizi algoritama.

Matematičar koji proučava kombinatoriku zove se kombinatorista.

Istorija

Primer promena zvonjenja (sa šest zvona), jedan od najranijih netrivijalnih rezultata u teoriji grafova.

Osnovni kombinatorni koncepti i rezultati nabrajanja pojavili su se širom antičkog sveta. U 6. veku pre nove ere, drevni indijski lekar Sušruta tvrdi u Sušruta Samhiti da se 63 kombinacije mogu napraviti od 6 različitih ukusa, uzetih jedan po jedan, dva po jedan, itd., tako da se izračunavaju svih 2⁶ − 1 mogućnosti. Grčki istoričar Plutarh raspravlja o raspravi između Krisipa (3. vek pne) i Hiparha (2. vek pne) o prilično delikatnom problemu nabrajanja, za koji se kasnije pokazalo da je povezan sa Šreder-Hiparhovim brojevima.^[9]^[10]^[11] Ranije, u Ostomahionu, Arhimed (3. vek pne) je možda razmatrao broj konfiguracija slagalice sa pločicama,^[12] dok su kombinatorička interesovanja verovatno bila prisutna u izgubljenim Apolonijevim delima.^[13]^[14]

U srednjem veku, kombinatorika se nastavila izučavati, uglavnom izvan evropske civilizacije. Indijski matematičar Mahavira (oko 850.) dao je formule za broj permutacija i kombinacija,^[15]^[16] i ove formule su možda bile poznate indijskim matematičarima još u 6. veku nove ere.^[17] Filozof i astronom rabin Abraham ibn Ezra (oko 1140.) uspostavio je simetriju binomnih koeficijenata, dok je zatvorenu formulu dobio kasnije talmudista i matematičar Levi ben Gerson (poznatiji kao Gersonid), 1321. godine.^[18] Aritmetički trougao — grafički dijagram koji pokazuje odnose među binomskih koeficijentima — predstavili su matematičari u raspravama koje datiraju još iz 10. veka, i na kraju će postati poznat kao Paskalov trougao. Kasnije, u srednjovekovnoj Engleskoj, kampanologija je pružila primere onoga što je sada poznato kao Hamiltonovi ciklusi u pojedinim Kelijevim grafovima permutacija.^[19]^[20]

Osnovni kombinatorni objekti

Permutacije

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!}{m_{1}!m_{2}!...m_{n}!}}

Varijacije (k-permutacije)

Varijacije bez ponavljanja članova skupa:

V=n(n-1)(n-2)...(n-k+1)={\frac {n!}{(n-k)!}}={n \choose k}k!=K*k!

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

Varijacije sa ponavljanjem članova skupa:

Vp=n^{k}\,\!

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

Kombinacije

Kombinacije bez ponavljanja članova skupa:

K={\frac {n!}{k!(n-k)!}}={n \choose k}={n \choose {n-k}}

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

Kombinacije sa ponavljanjem članova skupa:

Kp={{(n+k-1)!} \over {k!(n-1)!}}={{n+k-1} \choose {k}}={{n+k-1} \choose {n-1}}

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

Reference

^ Grupa autora, „Matematika I Algebra“, Beograd 2004.
^ O. Šlimlih i J. Majcen, „Logaritamske tablice“, Zagreb 1972.
^ Pak, Igor. „What is Combinatorics?”. Pristupljeno 1. 11. 2017. CS1 održavanje: Format datuma (veza)
^ Ryser 1963, p. 2
^ Mirsky, Leon (1979), „Book Review” (PDF), Bulletin of the American Mathematical Society, New Series, 1: 380—388, doi:10.1090/S0273-0979-1979-14606-8 
^ Rota, Gian Carlo (1969). Discrete Thoughts. Birkhaüser. str. 50. „... combinatorial theory has been the mother of several of the more active branches of today's mathematics, which have become independent ... . The typical ... case of this is algebraic topology (formerly known as combinatorial topology)”
^ Björner and Stanley, p. 2
^ Lovász, László (1979). Combinatorial Problems and Exercises. North-Holland. ISBN 9780821842621. „In my opinion, combinatorics is now growing out of this early stage.”
^ Acerbi, F. (2003). „On the shoulders of Hipparchus”. Archive for History of Exact Sciences. 57 (6): 465—502. S2CID 122758966. doi:10.1007/s00407-003-0067-0.
^ Stanley, Richard P.; "Hipparchus, Plutarch, Schröder, and Hough", American Mathematical Monthly 104 (1997), no. 4, 344–350.
^ Habsieger, Laurent; Kazarian, Maxim; Lando, Sergei (1998). „On the Second Number of Plutarch”. The American Mathematical Monthly. 105 (5): 446. doi:10.1080/00029890.1998.12004906.
^ Netz, R.; Acerbi, F.; Wilson, N. „Towards a reconstruction of Archimedes' Stomachion”. Sciamvs. 5: 67—99.
^ Hogendijk, Jan P. (1986). „Arabic Traces of Lost Works of Apollonius”. Archive for History of Exact Sciences. 35 (3): 187—253. ISSN 0003-9519. JSTOR 41133783. S2CID 121613986. doi:10.1007/BF00357307.
^ Huxley, G. (1967). „Okytokion”. Greek, Roman, and Byzantine Studies. 8 (3): 203.
^ O'Connor, John J.; Robertson, Edmund F. „Kombinatorna matematika”. MacTutor History of Mathematics archive. University of St Andrews.
^ Puttaswamy, Tumkur K. (2000). „The Mathematical Accomplishments of Ancient Indian Mathematicians”. Ur.: Selin, Helaine. Mathematics Across Cultures: The History of Non-Western Mathematics. Netherlands: Kluwer Academic Publishers. str. 417. ISBN 978-1-4020-0260-1.
^ Biggs, Norman L. (1979). „The Roots of Combinatorics”. Historia Mathematica. 6 (2): 109—136. doi:10.1016/0315-0860(79)90074-0  .
^ Maistrov, L.E. (1974), Probability Theory: A Historical Sketch, Academic Press, str. 35, ISBN 978-1-4832-1863-2 . (Translation from 1967 Russian ed.)
^ White, Arthur T. (1987). „Ringing the Cosets”. The American Mathematical Monthly. 94 (8): 721—746. doi:10.1080/00029890.1987.12000711.
^ White, Arthur T. (1996). „Fabian Stedman: The First Group Theorist?”. The American Mathematical Monthly. 103 (9): 771—778. doi:10.1080/00029890.1996.12004816.

Literatura

Björner, Anders; and Stanley, Richard P.; (2010); A Combinatorial Miscellany
Bóna, Miklós; (2011); „A Walk Through Combinatorics (3rd Edition)”. doi:10.1142/8027. . ISBN 978-981-4335-23-2
Graham, Ronald L.; Groetschel, Martin; and Lovász, László; eds. (1996); Handbook of Combinatorics, Volumes 1 and 2. Amsterdam, NL, and Cambridge, MA: Elsevier (North-Holland) and MIT Press. ISBN 0-262-07169-X
Lindner, Charles C.; and Rodger, Christopher A.; eds. (1997); Design Theory, CRC-Press; 1st. edition (1997). ISBN 0-8493-3986-3.
Riordan, John (2002) [1958], An Introduction to Combinatorial Analysis, Dover, ISBN 978-0-486-42536-8
Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs(#14), The Mathematical Association of America
Stanley, Richard P. (1997, 1999); Enumerative Combinatorics, Volumes 1 and 2, Cambridge University Press. ISBN 0-521-55309-1
van Lint, Jacobus H.; and Wilson, Richard M.; (2001); A Course in Combinatorics, 2nd Edition, Cambridge University Press. ISBN 0-521-80340-3
N.L. Biggs, The roots of combinatorics, Historia Mathematica 6 (1979), 109–136.
Katz, Victor J. (1998). A History of Mathematics: An Introduction, 2nd Edition. Addison-Wesley Education Publishers. ISBN 0-321-01618-1.
O'Connor, John J. and Robertson, Edmund F. (1999–2004). MacTutor History of Mathematics archive. St Andrews University.
Rashed, R. (1994). The development of Arabic mathematics: between arithmetic and algebra. London.
Wilson, R. and Watkins, J. (2013). Combinatorics: Ancient & Modern. Oxford.
Zeilberger, Doron, Enumerative and Algebraic Combinatorics
Joseph, George Gheverghese (1994) [1991]. The Crest of the Peacock: Non-European Roots of Mathematics (2nd izd.). London: Penguin Books. ISBN 0-14-012529-9.
Loehr, Nicholas A. (2011). Bijective Combinatorics. CRC Press. ISBN 143984884X, ISBN 978-1439848845.
Goulden, Ian P. and Jackson, David M. (2004). „Combinatorial Enumeration”. doi:10.1137/1026127. . Dover Publications. ISBN 0486435970.
Combinatorial Analysis – an article in Encyclopædia Britannica Eleventh Edition
Riordan, John (1968). Combinatorial Identities, Wiley & Sons, New York (republished).
Wilf, Herbert S. (1994). Generating functionology (2nd izd.). Boston, MA: Academic Press. ISBN 0-12-751956-4. Zbl 0831.05001.
Heath, Sir Thomas (1981). A history of Greek mathematics (Reprod. en fac-sim. izd.). New York: Dover. ISBN 0486240738.
Gow, James (1968). A Short History of Greek Mathematics. AMS Bookstore. str. 71. ISBN 0-8284-0218-3.