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

uredi
 
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 26 − 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

uredi

Permutacije

uredi
  • Permutacije bez ponavljanja članova skupa:
 

gde je n broj elemenata skupa koji mogu biti izabrani.

  • Permutacije sa ponavljanjem članova skupa:
 

Varijacije (k-permutacije)

uredi
  • Varijacije bez ponavljanja članova skupa:
 

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

  • Varijacije sa ponavljanjem članova skupa:
 

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

Kombinacije

uredi
  • Kombinacije bez ponavljanja članova skupa:
 

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

  • Kombinacije sa ponavljanjem članova skupa:
 

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

Reference

uredi
  1. ^ Grupa autora, „Matematika I Algebra“, Beograd 2004.
  2. ^ O. Šlimlih i J. Majcen, „Logaritamske tablice“, Zagreb 1972.
  3. ^ Pak, Igor. „What is Combinatorics?”. Pristupljeno 1. 11. 2017. 
  4. ^ Ryser 1963, p. 2
  5. ^ 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  
  6. ^ 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) 
  7. ^ Björner and Stanley, p. 2
  8. ^ 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. 
  9. ^ 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. 
  10. ^ Stanley, Richard P.; "Hipparchus, Plutarch, Schröder, and Hough", American Mathematical Monthly 104 (1997), no. 4, 344–350.
  11. ^ 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. 
  12. ^ Netz, R.; Acerbi, F.; Wilson, N. „Towards a reconstruction of Archimedes' Stomachion”. Sciamvs. 5: 67—99. 
  13. ^ 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. 
  14. ^ Huxley, G. (1967). „Okytokion”. Greek, Roman, and Byzantine Studies. 8 (3): 203. 
  15. ^ O'Connor, John J.; Robertson, Edmund F. „Kombinatorna matematika”. MacTutor History of Mathematics archive. University of St Andrews. 
  16. ^ 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. 
  17. ^ Biggs, Norman L. (1979). „The Roots of Combinatorics”. Historia Mathematica. 6 (2): 109—136. doi:10.1016/0315-0860(79)90074-0 . 
  18. ^ Maistrov, L.E. (1974), Probability Theory: A Historical Sketch, Academic Press, str. 35, ISBN 978-1-4832-1863-2 . (Translation from 1967 Russian ed.)
  19. ^ White, Arthur T. (1987). „Ringing the Cosets”. The American Mathematical Monthly. 94 (8): 721—746. doi:10.1080/00029890.1987.12000711. 
  20. ^ 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

uredi

Spoljašnje veze

uredi