Отворите главни мени

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

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

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

Постоје многе комбинаторне шеме и теореме у вези са структуром комбинаторних скупова. Оне се обично фокусирају на поделу или уређену поделу скупа.

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

Следи пример мало компликованијег проблема: Ако је дато n људи, да ли је могуће поделити их у скупове тако даје свака особа у најмање једном скупу, сваки пар особа је у тачно једном скупу заједно, свака два скупа имају тачно једну заједничку особу, и ниједан скуп не садржи све особе, све осим једне особе или тачно једну особу? Одговор зависи од n.

Основни комбинаторни проблемиУреди

Основни комбинаторни принципиУреди

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

ПермутацијеУреди

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

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

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

Варијације (k-пермутације)Уреди

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

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

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

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

КомбинацијеУреди

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

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

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

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

РеференцеУреди

  1. ^ Група аутора, „Математика I Алгебра“, Београд 2004.
  2. ^ О. Шлимлих и Ј. Мајцен, „Логаритамске таблице“, Загреб 1972.


Спољашње везеУреди