Kombinatorika

Kombinatorika alebo kombinatorická matematika alebo kombinatorická analýza je súčasť diskrétnej matematiky, ktorá študuje (spravidla) konečné množiny objektov, ktoré vyhovujú zadaným kritériám a zaoberá sa najmä "počítaním" objektov v týchto množinách (enumeratívna kombinatorika) a rozhodovaním, či isté "optimálne" objekty a množiny objektov vôbec existujú (extremálna kombinatorika). Jedným z najvýznamnejších kombinatorikov nedávnej doby bol Gian-Carlo Rota, ktorý pomohol sformalizovať kombinatoriku začiatkom šesťdesiatych rokov. Produktívny riešiteľ rôznych problémov Paul Erdös pracoval hlavne na extremálnych problémoch.
Typický príklad, na ktorý sa kombinatorika snaží nájsť odpoveď, je takýto: Aký je počet všetkých usporiadaní balíka 52 hracích kariet? Odpoveď je 52! (t. j. "päťdesiatdva faktoriál"), čo je súčin všetkých prirodzených čísel od jedna po 52, čo je približne 8.065817517094 × 10⁶⁷. Pri porovnaní s inými veľkými číslami je väčšie než druhá mocnina Avogadrovej konštanty (6.022 × 10²³), ktorá vyjadruje počet častíc v jednom móle látky.

Definícia

Samotný predmet štúdia kombinatoriky možno vyjadriť na základe pojmu konfigurácie (pozri napr. I. Haverlík: Matematická informatika I):
Nech A a B sú dve konečné množiny. Ľubovoľné zobrazenie množiny A do množiny B, vyhovujúce určitým podmienkam, ktorých charakter dopredu nie je určený (v tejto definícii), sa nazýva konfigurácia.
Kombinatorika skúma otázky existencie, vytvárania a vyčíslenia (t. j. určenia počtu) konfigurácií, pričom sa často vyčísľujú nie samotné konfigurácie, ale iba im zodpovedajúce triedy ekvivalencie.
Príkladom konfigurácií sú variácie, kombinácie či permutácie.

Výsledky

Dajú sa zostrojiť niektoré veľmi rafinované konfigurácie a dokázať niektoré veľmi prekvapujúce tvrdenia. Jedným z takých príkladov pochádza od Franka Ramseyho:
Predpokladajme, že na oslave sa stretne šesť ľudí. Každý pár sa buď navzájom pozná alebo nie. V každom prípade sa však vždy dajú nájsť traja ľudia, ktorí sa buď poznajú navzájom alebo sú si úplne neznámi.
Dôkaz je krátky a vedie sa sporom: predpokladajme, že takí traja ľudia neexistujú (teda takí, ktorí buď všetci navzájom poznajú alebo nepoznajú). Uvažujeme teraz ľubovoľnú osobu na oslave, nazvime ju A: spomedzi zvyšných piatich ľudí musia byť aspoň traja, ktorí ju buď poznajú, alebo traja, ktorí ju nepoznajú (tento fakt vyplýva z Dirichletovho princípu). Bez ujmy na všeobecnosti, predpokladajme, že títo traja ľudia osobu A poznajú. Potom ale medzi týmito troma ľuďmi sú najmenej dvaja, ktorí sa poznajú (inak by sme mali troch ľudí, ktorí sa navzájom nepoznajú, čo by bol spor). Keďže však títo dvaja ľudia sa poznajú aj s A, máme troch ľudí, ktorí sa navzájom poznajú, čo je spor. (Toto je špeciálny prípad Ramseyho vety.
Iný dôkaz používa dvojité vyčíslenie: spočítajte všetky usporiadané trojice ľudí (A,B,C), kde osoba B pozná osobu A, ale nepozná osobu C. Predpokladajme, že osoba K pozná k z piatich ostatných. Potom vystupuje ako druhá zložka (B) v presne k(5-k) takýchto trojíc, pretože človek v prvej zložke (A) musí byť jeden spomedzi k ľudí, ktorých pozná a človek v tretej zložke (C) musí byť jeden zo zvyšných 5-k ľudí, ktorých nepozná. Z toho vyplýva, že vystupuje v druhom komponente v buď 0*5=0, 1*4=4 alebo 2*3=6 takýchto trojiciach. Keďže spolu máme 6 ľudí a každý môže byť na druhom mieste v najviac šiestich trojiciach, spolu máme najviac 36 trojíc.
Teraz uvažujme trojicu ľudí, kde presne jeden pár sa navzájom pozná. Je zrejmé, že ich môžeme vyjadriť ako našu trojicu (A,B,C) presne dvomi spôsobmi: nech C' je ten, ktorý je neznámy pre zvyšných dvoch a potom sa na prvom a druhom mieste môžu vystriedať títo dvaja dvomi spôsobmi. Podobne, keď sa presne dva páry navzájom poznajú, potom sa dajú vyjadriť ako trojica tiež dvoma spôsobmi: nech A je osoba, ktorá pozná obidvoch zo zvyšných a B a C (v nejakom poradí) sú títo zvyšní dvaja. To znamená, že existuje najviac 36/2=18 trojíc, v ktorých buď presne jeden alebo dva páry sa poznajú navzájom. Keďže je však len 20 trojíc, existujú najmenej dve trojice, ktoré sa buď poznajú navzájom alebo sú si neznámi.
Myšlienka hľadania usporiadania v náhodných konfiguráciách je základom Ramseyho teórie. Vo svojej podstate táto teórie hovorí, že ľubovoľná dostatočne veľká konfigurácia obsahuje najmenej jednu inštanciu nejakého iného typu konfigurácie.