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

С Википедије, слободне енциклопедије
Пређи на навигацију Пређи на претрагу

Комбинаторика је грана чисте математике која се бави проучавањем дискретних (и обично коначних) објеката. Повезана је са многим другим гранама математике, попут алгебре, теорије вероватноће, и геометрије, као и са разним областима у рачунарству и статистичкој физици. Аспекти комбинаторике укључују пребројавање објеката кои задовољавају одређени критеријум (енумеративна комбинаторика), одређивање да ли неки критеријум може бити испуњен, конструисање и анализирање објеката који испуњавају неки критеријум, налажење највећих најмањих или оптималних објеката, и налажење алгебарских структура у које ови објекти могу спадати (алгебарска комбинаторика).[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.


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