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

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 × 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. Prema H.J. Rajseru, definicija subjekta je teška jer prekoračuje toliko matematičkih podela. 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.“ 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. 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, 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. 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.

Glavni članak: Istorija kombinatorike

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. Ranije, u Ostomahionu, Arhimed (3. vek pne) je možda razmatrao broj konfiguracija slagalice sa pločicama, dok su kombinatorička interesovanja verovatno bila prisutna u izgubljenim Apolonijevim delima.

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, i ove formule su možda bile poznate indijskim matematičarima još u 6. veku nove ere. 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. 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.

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.

Literatura

• Björner, Anders; and Stanley, Richard P.; (2010); A Combinatorial Miscellany
• Bóna, Miklós; (2011); A Walk Through Combinatorics (3rd Edition). 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. 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. 

Spoljašnje veze

• Hazewinkel Michiel, ur. (2001). „Combinatorial analysis”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• Combinatorial Analysis – an article in Encyclopædia Britannica Eleventh Edition
• Combinatorics, a MathWorld article with many references.
• Combinatorics, from a MathPages.com portal.
• The Hyperbook of Combinatorics, a collection of math articles links.
• The Two Cultures of Mathematics by W.T. Gowers, article on problem solving vs theory building.
• "Glossary of Terms in Combinatorics" Arhivirano na sajtu Wayback Machine (17. avgust 2017)
• List of Combinatorics Software and Databases