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

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

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

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

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

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

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

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

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

Историја

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

Главни чланак: Историја комбинаторике

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

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

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

Пермутације

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

$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 број елемената који треба да буду изабрани.

Литература

• 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 изд.). 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 изд.). 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. 

Спољашње везе

• Hazewinkel Michiel, ур. (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"
• List of Combinatorics Software and Databases