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

С Википедије, слободне енциклопедије

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

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

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

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

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

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

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

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

Историја[уреди | уреди извор]

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

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

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

Основни комбинаторни објекти[уреди | уреди извор]

Пермутације[уреди | уреди извор]

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

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

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

Варијације (k-пермутације)[уреди | уреди извор]

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

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

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

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

Комбинације[уреди | уреди извор]

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

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

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

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

Референце[уреди | уреди извор]

  1. ^ Група аутора, „Математика I Алгебра“, Београд 2004.
  2. ^ О. Шлимлих и Ј. Мајцен, „Логаритамске таблице“, Загреб 1972.
  3. ^ Pak, Igor. „What is Combinatorics?”. Приступљено 1. 11. 2017. 
  4. ^ Ryser 1963, p. 2
  5. ^ 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Слободан приступ 
  6. ^ 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) 
  7. ^ Björner and Stanley, p. 2
  8. ^ 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. 
  9. ^ 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. 
  10. ^ Stanley, Richard P.; "Hipparchus, Plutarch, Schröder, and Hough", American Mathematical Monthly 104 (1997), no. 4, 344–350.
  11. ^ 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. 
  12. ^ Netz, R.; Acerbi, F.; Wilson, N. „Towards a reconstruction of Archimedes' Stomachion”. Sciamvs. 5: 67—99. 
  13. ^ 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. 
  14. ^ Huxley, G. (1967). „Okytokion”. Greek, Roman, and Byzantine Studies. 8 (3): 203. 
  15. ^ O'Connor, John J.; Robertson, Edmund F. „Комбинаторна математика”. MacTutor History of Mathematics archive. University of St Andrews. 
  16. ^ 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. 
  17. ^ Biggs, Norman L. (1979). „The Roots of Combinatorics”. Historia Mathematica. 6 (2): 109—136. doi:10.1016/0315-0860(79)90074-0Слободан приступ. 
  18. ^ Maistrov, L.E. (1974), Probability Theory: A Historical Sketch, Academic Press, стр. 35, ISBN 978-1-4832-1863-2 . (Translation from 1967 Russian ed.)
  19. ^ White, Arthur T. (1987). „Ringing the Cosets”. The American Mathematical Monthly. 94 (8): 721—746. doi:10.1080/00029890.1987.12000711. 
  20. ^ White, Arthur T. (1996). „Fabian Stedman: The First Group Theorist?”. The American Mathematical Monthly. 103 (9): 771—778. doi:10.1080/00029890.1996.12004816. 

Литература[уреди | уреди извор]

Спољашње везе[уреди | уреди извор]