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

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

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

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

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

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

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

Wiki letter w.svg Овај чланак, или један његов део, треба још да се прошири.
Погледајте страну за разговор за разлог. Када се побољшавање заврши, можете склонити ово обавештење.

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

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

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

Пермутације[уреди]

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

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

  • Пермутације са понављањем чланова скупа:
 Pp = \frac{n!}{r!s!}

Варијације (r-пермутације)[уреди]

  • Варијације без понављања чланова скупа:
 V = n(n-1)(n-2)...(n-r+1) = \frac{n!}{(n-r)!} = {n \choose r}r! = Kr!

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

  • Варијације са понављањем чланова скупа:
 Vp = n^r \,\!

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

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

  • Комбинације без понављања чланова скупа:
 K = \frac{n!}{r!(n - r)!} = {n \choose r} = {n \choose {n-r}}

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

  • Комбинације са понављањем чланова скупа:
 Kp = {{(n + r - 1)!} \over {r!(n - 1)!}} = {{n + r - 1} \choose {r}} = {{n + r - 1} \choose {n - 1}}

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

Референце[уреди]

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


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

Викиостава
Викимедијина остава има још мултимедијалних датотека везаних за: Комбинаторна математика