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ú.

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.

Vyčísľovanie konfigurácií

Vyjadrenie počtu všetkých konfigurácií sa dá považovať za centrálnu otázku kombinatoriky. Nech S je množina o n prvkoch. kombinácie (bez opakovania) k prvkov z množiny S sú podmožiny S majúce k prvkov (v reči konfigurácií sú to všetky zobrazenia f z množiny $\{1,2,\ldots ,k\}$ do množiny S také, že $f(i)<f(j)$ pre $i<j$ ). Variácie k prvkov z tejto množiny S sú postupnosti k rôznych prvkov z S. Všimnite si, že pri variáciach zaleží na poradí, kým kombinácie, ktoré sa odlišujú len poradím prvkov, považujeme za totožné. Vzorce udávajúce počet variácií a kombinácií k prvkov (hovoríme o variáciach, resp. kombinácia k-tej triedy) sú známe a veľmi často používané.

Všeobecnejšie, nech je daná nekonečná trieda konečných množín (S_i), typicky indexovaná prirodzenými číslami, enumeratívna kombinatorika hľadá rôzne spôsoby vyjadrenia vyčísľovacej funkcie, f(n), ktorá udáva ("vyčísľuje") počet prvkov v množine S_n pre každé n. V príkladoch v predchádzajúcom odstavci obsahovala množina S_n všetky kombinácie, resp. variácie n-tej triedy z množiny S.

Najjednoduchší spôsob vyjadrenia sú uzavreté tvary, t. j. konečná kompozícia elementárnych funkcií (v kombinatorike považujeme aj funkciu faktoriál za elementárnu). Ako už bolo spomenuté v úvode, počet všetkých rôznych usporiadaní n hracích kariet je presne n!.

Avšak nie vždy je vhodné a praktické udávať vyčísľovaciu funkciu explicitným uzavretým tvarom (dokonca v niektorých prípadoch je to nemožné). Napríklad, nech f(n) označuje počet všetkých rôznych podmnožín celých čísel z intervalu <1,n>, ktoré neobsahujú dve po sebe idúce čísla; napríklad pre n=4 by sme mali {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, teda f(4)=8. Ukazuje sa, že f(n) je (n+2). Fibonacciho číslo, čo sa dá v uzavretom tvare vyjadriť ako

f(n)={\frac {\phi ^{n+2}}{\sqrt {5}}}-{\frac {(1-\phi )^{n+2}}{\sqrt {5}}}

kde φ = (1 + √5) / 2 je tzv. zlatý priemer. Avšak samotný fakt, že počítame množiny celých čísel, a vo výsledku nám vystupuje √5, je pri najmenšom neestetický z kombinatorického hľadiska. Navyše nie je celkom jasný súvis výsledku s problémom, dokonca ani na prvý pohľad nie je vidno, či oborom hodnôt tejto funkcie sú prirodzené čísla. Alternatívne môže byť funkcia f vyjadrená v rekurentnom tvare:

f(n)=f(n-1)+f(n-2)

f(0)=1, f(1)=2

čo

f(n)\sim {\frac {\phi ^{n+2}}{\sqrt {5}}}

pre n rastúca do nekonečna.

Azda najužitočnejšie vyjadrenie je však prostredníctvom formálneho mocninového radu, nazývaného generujúca funkcia (alebo vytvárajúca funkcia), ktorá je najčastejšie buď tzv. obyčajná generujúca funkcia

\sum f(n)x^{n}

alebo exponenciálna generujúca funkcia

\sum f(n){\frac {x^{n}}{n!}}

kde sumy idú cez n ≥ 0. Hneď ako určíme generujúcu funkciu, dovolíme nám vyjadriť všetky informácie, ktoré nám poskytli predchádzajúce prístupy. Navyše rôzne prirodzené operácie na generujúcich funkciách ako napr. sčítanie, násobenie, derivácia a pod. majú kombinatorický význam, čo dovoľuje preniesť výsledky z jedného kombinatorického problému na iný.

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.

Vývoj kombinatoriky

Podobne ako matematika sprevádza ľudstvo po celú dobu jeho histórie, tiež kombinatorika sa v histórii objavuje už veľmi dávno. Prvé kombinatorické poznatky, príklady a výsledky môžeme nájsť už v období okolo roku 2000 pred Kr. Texty vzťahujúce sa ku kombinatorike nachádzame najčastejšie v indickej a čínskej civilizácii. Väčšinou je však zložité určiť čo len približný dátum vzniku týchto textov. Obsahujú totiž celý rad poznámok a záznamov, ktoré často nie sú pôvodné a do textov sa dostali v neskoršom období. Mnoho prác sa vôbec nezachovalo, existujú na ne len odkazy.

Vypátrať históriu základných pravidiel kombinatoriky pre počítanie je zložité aj z ďalších dôvodov. Pravidlá kombinatoriky sú natoľko jednoduché, že boli používané často len intuitívne, bez konkrétneho doloženia ich znalosti. Z mnohých príkladov je zrejmé, že ľudia tieto pravidlá poznali, ale nikde ich nenájdeme presne popísané. Jedným z najstarších matematických textov je Rhindov papyrus asi z roku 1650 pred Kr. Tieto príklady sa s drobnými obmenami objavovali v rôznych obdobiach u rôznych autorov.

Vzťahy pre výpočet variácií s opakovaním nájdeme v slávnej Knihe premien, ktorá pochádza z Číny z roku 2200 pred Kr. Čínsky systém bol založený na dvoch znakoch jang (-) a jin (- -), ktoré sa usporadúvali do tzv. trigramov a hexagramov, čo sú skupiny po troch a po šiestich. Starí Číňania sa zaoberali otázkou, koľko takých trigramov a hexagramov je možné zostaviť. S permutáciami a kombináciami sa stretávame v indickej matematike. Väčšinou však ide o príklady kombinácií vytváraných len z malého počtu prvkov. Výsledky bolo možné získať jednoduchým vypísaním všetkých možností. Preto nie je zrejme, či Indovia poznali pravidlá pre výpočet kombinácií.

Asi najznámejší je príklad ktorý sa objavil v 6. storočí v lekárskom spise zo Susruty. Autor v ňom píše o rôznych kombináciách chutí, ktoré môžeme získať zo šiestich základných: sladkej, kyslej, slanej, horkej, ostrej a trpkej. V riešení sú vypísané všetky typy kombinácií (po jednej, po dvoch…) a ich počty. Nájdeme aj príklady na vytváranie slov z rôzne dlhých slabík. Až v 6. storočí sa v práci Brihatsamhita od indického astrológa Varahamihiru objavil príklad, v ktorom sa miešajú štyri rôzne vône zo 16 možných. Autor jednoducho uvádza, že takýchto možností je 1 820, čo je správny výsledok. Je veľmi nepravdepodobné, že by Varahamihira vypisoval všetky možnosti. Predpokladáme teda, že autor získal výsledok použitím vzorca pre výpočet k-prvkových kombinácií z n prvkov.

V 7. storočí začala indická matematika prenikať na západ. Arabi si veľmi rýchlo osvojili poznatky Indov a začali ich bežne používať. Matematik Ibn-Ahmad al-Halil vo svojej práci uvádza príklad, v ktorom sa zaoberá počtom slabík vytvorených z niekoľkých písmen. Z jeho výpočtov je zrejmé, že rozumel základným pravidlám pre výpočet počtu kombinácií a permutácií. Veľkým prínosom Arabov v oblasti kombinatoriky sú ich práce o magických štvorcoch a binomickej vete.

Pozri aj

Literatúra

Handbook of Combinatorics, Volumes 1 and 2, R.L. Graham, M. Groetschel and L. Lovász (Eds.), MIT Press, 1996. ISBN 0-262-07169-X
Enumerative Combinatorics, Volumes 1 and 2, Richard P. Stanley, Cambridge University Press, 1997 and 1999, ISBN 0-521-55309-1N
Haverlík, I. a kol.: Matematická informatika I. Bratislava, 1984, skriptum Matematicko-fyzikálnej fakulty Univerzity Komenského v Bratislave.

Externé odkazy

Kombinatorika na http://www.1kspa.cz/ Archivované 2019-08-19 na Wayback Machine