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

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

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

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

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

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

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

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

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

Историја

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

Основни комбинаторни концепти и резултати набрајања појавили су се широм античког света. У 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)!}=(\genfrac{}{}{0ex}{}{n}{k})k!=K*k!$

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

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

$Vp=n^k$

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

Комбинације

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

$K=\frac{n!}{k!(n-k)!}=(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n}{n-k})$

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

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

$Kp=\frac{(n+k-1)!}{k!(n-1)!}=(\genfrac{}{}{0ex}{}{n+k-1}{k})=(\genfrac{}{}{0ex}{}{n+k-1}{n-1})$

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

Литература

• Björner, Anders; and Stanley, Richard P.; (2010); A Combinatorial Miscellany
• Шаблон:Cite book
• Graham, Ronald L.; Groetschel, Martin; and Lovász, László; eds. ; Шаблон:Cite book. Volumes 1 and 2. Amsterdam, NL, and Cambridge, MA: Elsevier (North-Holland) and MIT Press.
• Lindner, Charles C.; and Rodger, Christopher A.; eds. ; Шаблон:Cite book. CRC-Press; 1st. edition (1997). .
• Шаблон:Citation
• Шаблон:Citation
• Stanley, Richard P. (1997, 1999); Enumerative Combinatorics, Volumes 1 and 2, Cambridge University Press. Шаблон:ISBN
• van Lint, Jacobus H.; and Wilson, Richard M.; ; Шаблон:Cite book. 2nd Edition, Cambridge University Press.
• N.L. Biggs, The roots of combinatorics, Historia Mathematica 6 (1979), 109–136.
• Шаблон:Cite book. Addison-Wesley Education Publishers..
• O'Connor, John J. and Robertson, Edmund F. (1999–2004). MacTutor History of Mathematics archive. St Andrews University.
• Шаблон:Cite book. London.
• Wilson, R. and Watkins, J. Шаблон:Cite book. Oxford.
• Zeilberger, Doron, Enumerative and Algebraic Combinatorics
• Шаблон:Cite book
• Шаблон:Cite book
• Goulden, Ian P. and Jackson, David M. (2004). Шаблон:Cite journal. Dover Publications. .
• Combinatorial Analysis – an article in Encyclopædia Britannica Eleventh Edition
• Шаблон:Cite book. Wiley & Sons, New York (republished).
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book

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

• Шаблон:Springer
• 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.
• Шаблон:Cite web
• List of Combinatorics Software and Databases