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

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

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

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

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

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

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

Пермутације

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

$P={n!}$

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

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

$Pp={\frac {n!}{m_{1}!m_{2}!...m_{n}!}}$

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

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

$V=n(n-1)(n-2)...(n-k+1)={\frac {n!}{(n-k)!}}={n \choose k}k!=K*k!$

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

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

$Vp=n^{k}\,\!$

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

Комбинације

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

$K={\frac {n!}{k!(n-k)!}}={n \choose k}={n \choose {n-k}}$

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

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

$Kp={{(n+k-1)!} \over {k!(n-1)!}}={{n+k-1} \choose {k}}={{n+k-1} \choose {n-1}}$

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