Комбинаторна математика
From Wikipedia, the free encyclopedia
Комбинаторика је грана чисте математике која се бави проучавањем дискретних (и обично коначних) објеката. Повезана је са многим другим гранама математике, попут алгебре, теорије вероватноће, и геометрије, као и са разним областима у рачунарству и статистичкој физици. Аспекти комбинаторике укључују пребројавање објеката који задовољавају одређени критеријум (енумеративна комбинаторика), одређивање да ли неки критеријум може бити испуњен, конструисање и анализирање објеката који испуњавају неки критеријум, налажење највећих најмањих или оптималних објеката, и налажење алгебарских структура у које ови објекти могу спадати (алгебарска комбинаторика).[1]
Комбинаторика се подједнако тиче решавања проблема као и изградње теорија, мада је развила моћне теоријске моделе, поготово у другом делу двадесетог века. Једна од најстаријих и најчешће коришћених области комбинаторике је теорија графова, која такође има изузетно бројне везе са другим областима.[2]
Постоје многе комбинаторне шеме и теореме у вези са структуром комбинаторних скупова. Оне се обично фокусирају на поделу или уређену поделу скупа. Пример комбинаторног проблема може бити: На колико начина је могуће уредити шпил од 52 различите карте за играње? Одговор је 52! (52 факторијел), што је приближно једнако 8,0658 × 1067. Следи пример мало компликованијег проблема: Ако је дато људи, да ли је могуће поделити их у скупове тако даје свака особа у најмање једном скупу, сваки пар особа је у тачно једном скупу заједно, свака два скупа имају тачно једну заједничку особу, и ниједан скуп не садржи све особе, све осим једне особе или тачно једну особу? Одговор зависи од .
Пуни обим комбинаторике није универзално прихваћен.[3] Према Х.Ј. Рајсеру, дефиниција субјекта је тешка јер прекорачује толико математичких подела.[4] У мери у којој се област може описати типовима проблема којима се бави, комбинаторика је укључена у:
- набрајање (пребројавање) одређених структура, које се понекад називају аранжмани или конфигурације у веома општем смислу, повезаних са коначним системима,
- постојање таквих структура које задовољавају одређене дате критеријуме,
- конструкција ових структура, можда на много начина, и
- оптимизација: проналажење „најбоље“ структуре или решења међу неколико могућности, било да је „највећа“, „најмања“ или задовољавање неког другог критеријума оптималности.
Леон Мирски је рекао: „комбинаторика је низ повезаних студија које имају нешто заједничко, а ипак се увелико разликују у својим циљевима, њиховим методама и степену кохерентности који су постигли.“[5] Један од начина да се дефинише комбинаторика је, можда, да опише своје поделе са њиховим проблемима и техникама. Ово је приступ који се користи у наставку. Међутим, постоје и чисто историјски разлози за укључивање или неукључивање неких тема под окриље комбинаторике.[6] Иако се првенствено баве коначним системима, нека комбинаторна питања и технике могу се проширити на бесконачно (конкретно, пребројиво) али дискретно окружење.
Комбинаторика је добро позната по ширини проблема којима се бави. Комбинаторни проблеми се јављају у многим областима чисте математике, посебно у алгебри, теорији вероватноће, топологији и геометрији,[7] као и у многим областима њене примене. Многа комбинаторна питања су историјски разматрана изоловано, дајући ад хок решење за проблем који се јавља у неком математичком контексту. У каснијем двадесетом веку, међутим, развијене су моћне и опште теоријске методе, чиме је комбинаторика постала независна грана математике сама по себи.[8] Један од најстаријих и најприступачнијих делова комбинаторике је теорија графова, која сама по себи има бројне природне везе са другим областима. Комбинаторика се често користи у рачунарству за добијање формула и процена у анализи алгоритама.
Математичар који проучава комбинаторику зове се комбинаториста.