Комбинаторна математика

Комбинаторика је грана чисте математике која се бави проучавањем дискретних (и обично коначних) објеката. Повезана је са многим другим гранама математике, попут алгебре, теорије вероватноће, и геометрије, као и са разним областима у рачунарству и статистичкој физици. Аспекти комбинаторике укључују пребројавање објеката који задовољавају одређени критеријум (енумеративна комбинаторика), одређивање да ли неки критеријум може бити испуњен, конструисање и анализирање објеката који испуњавају неки критеријум, налажење највећих најмањих или оптималних објеката, и налажење алгебарских структура у које ови објекти могу спадати (алгебарска комбинаторика).^[1]

Комбинаторика се подједнако тиче решавања проблема као и изградње теорија, мада је развила моћне теоријске моделе, поготово у другом делу двадесетог века. Једна од најстаријих и најчешће коришћених области комбинаторике је теорија графова, која такође има изузетно бројне везе са другим областима.^[2]

Постоје многе комбинаторне шеме и теореме у вези са структуром комбинаторних скупова. Оне се обично фокусирају на поделу или уређену поделу скупа. Пример комбинаторног проблема може бити: На колико начина је могуће уредити шпил од 52 различите карте за играње? Одговор је 52! (52 факторијел), што је приближно једнако 8,0658 × 10⁶⁷. Следи пример мало компликованијег проблема: Ако је дато n људи, да ли је могуће поделити их у скупове тако даје свака особа у најмање једном скупу, сваки пар особа је у тачно једном скупу заједно, свака два скупа имају тачно једну заједничку особу, и ниједан скуп не садржи све особе, све осим једне особе или тачно једну особу? Одговор зависи од n.

Пуни обим комбинаторике није универзално прихваћен.^[3] Према Х.Ј. Рајсеру, дефиниција субјекта је тешка јер прекорачује толико математичких подела.^[4] У мери у којој се област може описати типовима проблема којима се бави, комбинаторика је укључена у:

набрајање (пребројавање) одређених структура, које се понекад називају аранжмани или конфигурације у веома општем смислу, повезаних са коначним системима,
постојање таквих структура које задовољавају одређене дате критеријуме,
конструкција ових структура, можда на много начина, и
оптимизација: проналажење „најбоље“ структуре или решења међу неколико могућности, било да је „највећа“, „најмања“ или задовољавање неког другог критеријума оптималности.

Леон Мирски је рекао: „комбинаторика је низ повезаних студија које имају нешто заједничко, а ипак се увелико разликују у својим циљевима, њиховим методама и степену кохерентности који су постигли.“^[5] Један од начина да се дефинише комбинаторика је, можда, да опише своје поделе са њиховим проблемима и техникама. Ово је приступ који се користи у наставку. Међутим, постоје и чисто историјски разлози за укључивање или неукључивање неких тема под окриље комбинаторике.^[6] Иако се првенствено баве коначним системима, нека комбинаторна питања и технике могу се проширити на бесконачно (конкретно, пребројиво) али дискретно окружење.

Комбинаторика је добро позната по ширини проблема којима се бави. Комбинаторни проблеми се јављају у многим областима чисте математике, посебно у алгебри, теорији вероватноће, топологији и геометрији,^[7] као и у многим областима њене примене. Многа комбинаторна питања су историјски разматрана изоловано, дајући ад хок решење за проблем који се јавља у неком математичком контексту. У каснијем двадесетом веку, међутим, развијене су моћне и опште теоријске методе, чиме је комбинаторика постала независна грана математике сама по себи.^[8] Један од најстаријих и најприступачнијих делова комбинаторике је теорија графова, која сама по себи има бројне природне везе са другим областима. Комбинаторика се често користи у рачунарству за добијање формула и процена у анализи алгоритама.

Математичар који проучава комбинаторику зове се комбинаториста.

Историја

Пример промена звоњења (са шест звона), један од најранијих нетривијалних резултата у теорији графова.

Основни комбинаторни концепти и резултати набрајања појавили су се широм античког света. У 6. веку пре нове ере, древни индијски лекар Сушрута тврди у Сушрута Самхити да се 63 комбинације могу направити од 6 различитих укуса, узетих један по један, два по један, итд., тако да се израчунавају свих 2⁶ − 1 могућности. Грчки историчар Плутарх расправља о расправи између Крисипа (3. век пне) и Хипарха (2. век пне) о прилично деликатном проблему набрајања, за који се касније показало да је повезан са Шредер-Хипарховим бројевима.^[9]^[10]^[11] Раније, у Остомахиону, Архимед (3. век пне) је можда разматрао број конфигурација слагалице са плочицама,^[12] док су комбинаторичка интересовања вероватно била присутна у изгубљеним Аполонијевим делима.^[13]^[14]

У средњем веку, комбинаторика се наставила изучавати, углавном изван европске цивилизације. Индијски математичар Махавира (око 850.) дао је формуле за број пермутација и комбинација,^[15]^[16] и ове формуле су можда биле познате индијским математичарима још у 6. веку нове ере.^[17] Филозоф и астроном рабин Абрахам ибн Езра (око 1140.) успоставио је симетрију биномних коефицијената, док је затворену формулу добио касније талмудиста и математичар Леви бен Герсон (познатији као Герсонид), 1321. године.^[18] Аритметички троугао — графички дијаграм који показује односе међу биномских коефицијентима — представили су математичари у расправама које датирају још из 10. века, и на крају ће постати познат као Паскалов троугао. Касније, у средњовековној Енглеској, кампанологија је пружила примере онога што је сада познато као Хамилтонови циклуси у појединим Келијевим графовима пермутација.^[19]^[20]

Основни комбинаторни објекти

Пермутације

Пермутације без понављања чланова скупа:

P={n!}

где је n број елемената скупа који могу бити изабрани.

Пермутације са понављањем чланова скупа:

Pp={\frac {n!}{m_{1}!m_{2}!...m_{n}!}}

Варијације (k-пермутације)

Варијације без понављања чланова скупа:

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

где је n број елемената скупа који могу бити изабрани, а k број елемената који треба да буду изабрани.

Варијације са понављањем чланова скупа:

Vp=n^{k}\,\!

где је n број елемената скупа који могу бити изабрани, а k број елемената који треба да буду изабрани.

Комбинације

Комбинације без понављања чланова скупа:

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

где је n број елемената скупа који могу бити изабрани, а k број елемената који треба да буду изабрани.

Комбинације са понављањем чланова скупа:

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

где је n број елемената скупа који могу бити изабрани, а k број елемената који треба да буду изабрани.

Референце

^ Група аутора, „Математика I Алгебра“, Београд 2004.
^ О. Шлимлих и Ј. Мајцен, „Логаритамске таблице“, Загреб 1972.
^ Pak, Igor. „What is Combinatorics?”. Приступљено 1. 11. 2017.
^ 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. стр. 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. „Комбинаторна математика”. MacTutor History of Mathematics archive. University of St Andrews.
^ Puttaswamy, Tumkur K. (2000). „The Mathematical Accomplishments of Ancient Indian Mathematicians”. Ур.: Selin, Helaine. Mathematics Across Cultures: The History of Non-Western Mathematics. Netherlands: Kluwer Academic Publishers. стр. 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, стр. 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.

Литература

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 изд.). 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 изд.). 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. изд.). New York: Dover. ISBN 0486240738.
Gow, James (1968). A Short History of Greek Mathematics. AMS Bookstore. стр. 71. ISBN 0-8284-0218-3.