Kombinatorika

Kombinatorika – matematikos šaka, nagrinėjanti, kaip rasti tam tikrų baigtinių aibių elementų kiekį. Kombinatoriniai uždaviniai yra ir matematikos tikslas ir priemonė sprendžiant kitų matematikos ir mokslo sričių (statistinės fizikos, tikimybių teorijos, skaičių teorijos, teorinio kompiuterių mokslo) uždavinius.

Kombinatorika labai dažnai taikoma praktinių uždavinių sprendimui. Jos metodai taikomi sprendžiant statistikos, valdymo sistemų uždavinius. Kombinatorinės struktūros (pvz., grafai, medžiai) yra svarbūs modeliai taikomojo mokslo srityse kaip biologija, kompiuterių mokslas, ir sociologija.

Pavyzdžiui, kombinatorikos uždaviniai yra tokie: Kiek yra skirtingų 52 kortų kaladės išmaišymo kombinacijų? Keliais būdais galima pasiūti trispalvę vėliavą iš n skirtingų spalvų audeklo? Keliais būdais apie apvalų stalą galima susodinti n žmonių? Kiek spalvų užtenka nuspalvinti rajonus Lietuvos žemėlapyje, jog jokie du gretimi rajonai nebūtų vienos spalvos? Kiek žmonių pakvietus į vakarėlį, galime būti tikri, kad jame bus penki tarpusavy pažįstami žmonės arba penki tarpusavy visai nepažįstami žmonės?

Kombinatorinius uždavinius sprendė dar senovės graikų matematikai, tačiau šios matematikos šakos pagrindai sukurti XVII ir XVIII a. matematikų: Paskalio (1623-1662), Leibnico (1646-1716) ir Jakobo Bernulio (1654-1705).

Šiuolaikinėje kombinatorikoje išskiriamos kelios sritys, tarp jų skaičiuojamoji kombinatorika (būdai nustatyti ar įvertinti tam tikras savybes tenkinančių diskrečių struktūrų skaičių), ekstremalioji kombinatorika (nagrinėjanti kombinatorinių parametrų ekstremalias reikšmes), tikimybinė kombinatorika (nagrinėjanti atsitiktinių struktūrų savybes), kombinatorinė geometrija (nagrinėjanti geometrinių objektų, tokių kaip daugiasieniai, kombinatorines savybes), adityvioji kombinatorika (nagrinėjanti sveikųjų skaičių ir kitų adityviųjų grupių kombinatorines savybes).

Pavyzdys

Kombinatorika naudinga sprendžiant lošimo uždavinius. Pavyzdžiui, Keno loto 20 skaičių iš 60-ties galima pasirinkti

${60 \choose 20}={60! \over 20!(60-20)!}=4'191'844'505'805'495$ būdais.

Pasirinkus 10 skaičių, būdų pasirinkti 20 skaičių iš 60-ies taip, kad tarp jų būtų 10 pasirinktųjų skaičių yra

${50 \choose 10}={50! \over 10!(50-10)!}=10'272'278'170$

Taigi tikimybė, kad visi 10 pasirinkti skaičiai bus tarp 20-ies atsitiktinai ištrauktų yra ${10'272'278'170 \over 4'191'844'505'805'495}$, tai yra 1 iš 408 073,5.