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

Комбинаторика се подједнако тиче решавања проблема као и изградње теорија, мада је развила моћне теоријске моделе, поготово у другом делу двадесетог века. Једна од најстаријих и најчешће коришћених области комбинаторике је теорија графова, која такође има изузетно бројне везе са другим областима.О. Шлимлих и Ј. Мајцен, „Логаритамске таблице“, Загреб 1972.

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

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

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

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

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

Историја

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

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

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

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

Варијације (k-пермутације) Варијације без понављања чланова скупа:

где је n број елемената скупа који могу бити изабрани, а k број елемената који треба да буду изабрани. Варијације са понављањем чланова скупа:

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

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

где је n број елемената скупа који могу бити изабрани, а k број елемената који треба да буду изабрани. Комбинације са понављањем чланова скупа:

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

Референце

Литература

. Amsterdam, NL, and Cambridge, MA: Elsevier (North-Holland) and MIT Press. . 1st. edition (1997). .

Stanley, Richard P. (1997, 1999); . Volumes 1 and 2, Cambridge University Press. .

. O'Connor, John J. and Robertson, Edmund F. (1999–2004). MacTutor History of Mathematics archive. St Andrews University. . . Zeilberger, Doron, Enumerative and Algebraic Combinatorics

Goulden, Ian P. and Jackson, David M. . Dover Publications. . Combinatorial Analysis – an article in Encyclopædia Britannica Eleventh Edition (republished).

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

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.

List of Combinatorics Software and Databases

*