kombinatorika
kombinatorika [lat.], kombinatorická analýza — časť diskrétnej matematiky zaoberajúca sa otázkami existencie, konštrukcie a početnosti diskrétnych štruktúr, ako aj extremálnymi úlohami týkajúcimi sa takýchto štruktúr. Typickou kombinatorickou úlohou je zistenie počtu možností, ktorými sa dá vytvoriť (kombinatorická) konfigurácia so zadanými vlastnosťami. V závislosti od zložitosti problému sa za uspokojivú odpoveď považuje vyčíslenie (enumerácia) presného počtu konfigurácií, efektívny algoritmus na ich systematické vygenerovanie, približné zistenie ich počtu pomocou dolných alebo horných odhadov, určenie asymptotického správania počtu v závislosti od parametrov alebo dôkaz ich existencie či neexistencie. Kombinatorické úvahy a metódy majú významný presah do iných oblastí matematiky a často sa používajú napr. v teórii grafov, v algebre, teórii čísel, teórii pravdepodobnosti, optimalizácii, matematickej logike, štatistickej fyzike a teoretickej informatike.
Zmienky o jednoduchých kombinatorických výpočtoch a ich zdôvodnenia pochádzajú už zo staroveku, zachovali sa nezávisle od seba vo viacerých kultúrach. Najstarším je výpočet súčtu geometrického radu zaznamenaný ako úloha č. 79 na staroegyptskom Rhindovom (resp. Londýnskom, Achmosovom) papyruse asi z 18. stor. pred n. l. (→ Achmos). Konfigurácie, ktoré sa v súčasnosti označujú ako variácie s opakovaním, sa nachádzajú v čínskej vešteckej Knihe premien pochádzajúcej z 11. stor. pred n. l. Mystický význam sa v nej pripisuje šesťdesiatimštyrom (t. j. 26) hexagramom (šesticiam vodorovných plných alebo prerušovaných čiar). Rituálny význam mali magické štvorce v Číne známe pravdepodobne už v 2. tisícročí pred n. l. (napr. magický štvorec Luo šu). Kombinácie (→ kombinácie \(k\)-tej triedy z \(n\) prvkov) a kombinačné čísla sa objavili v indickom džinistickom texte (ágame) Bhagavatisútra z 3. stor. pred n. l., rekurentný vzťah pre ne poznal už staroindický matematik Pingala (pravdepodobne 3. stor. pred n. l., kniha Čhandasútra), ktorý ho použil pri štúdiu prozódie (striedania krátkych a dlhých slabík vo veršoch). V jeho diele sa vyskytujú aj čísla v súčasnosti známe ako Fibonacciho čísla (→ Fibonacciho postupnosť). V gréckych antických prameňoch sa zachovalo pomerne málo zmienok o kombinatorických problémoch a úvahách, a tak zostáva rozsah antického poznania v oblasti kombinatoriky pomerne nejasný. Jednou z mála výnimiek je Plutarchova zmienka o Hipparchovom výpočte rôznych uzátvorkovaní reťazca s desiatimi znakmi v kontexte stoickej logiky, ktorý poukazuje na nutnú pokročilú znalosť rekurentných výpočtov, ako aj kombinačných čísel (v modernom chápaní ide o výpočet tzv. Schröderových čísel).
V 9. stor. indický matematik Mahávíra vyjadril kombinačné čísla pomocou súčinov. Indický matematik Halajudha (10. stor.) v komentári k Pingalovmu dielu (okolo 950) uvádza postup výpočtu kombinačných čísel a ich grafický zápis (dnes známy ako Pascalov trojuholník). V encyklopedickom diele Listy Bratov čistoty (Rásá’il Ichván as-safá’, okolo 960 – 980) napísanom skupinou učencov islamskej organizácie Bratia čistoty sa uvádzajú magické štvorce veľkosti 5 × 5 a 6 × 6. Na prelome 10. a 11. stor. perzský matematik al-Karadží v prácach venovaných úpravám algebraických výrazov uvádza o. i. binomickú vetu, Pascalov trojuholník a náčrt princípu matematickej indukcie. Indický matematik Bháskara II. sa v traktáte Koruna vedy (Siddhanta-širómani, 1150) v časti Lílávatí zaoberá variáciami, resp. permutáciami s opakovaním a uvádza vzorce zodpovedajúce polynomickým číslam. Podobné výsledky získal aj španielsky židovský učenec Abraham ibn Ezra pri štúdiu astrológie. Do Európy sa indicko-arabské poznatky rozšírili prostredníctvom Knihy o abakuse (Liber abaci, 1202) L. Fibonacciho. Prvé kompletné dôkazy kombinatorických formúl založené na matematickej indukcii obsahujú práce (1. pol. 14. stor.) francúzskeho židovského mysliteľa Gersonida (Lévi ben Geršom).
V Európe sa za zrod modernej kombinatoriky dajú považovať práce B. Pascala a P. de Fermata (1654), v ktorých uvádzajú mnohé klasické kombinatorické výsledky získané pri štúdiu pravdepodobností v hazardných hrách (→ kombinatorická pravdepodobnosť). Názov kombinatorika po prvýkrát použil G. W. Leibniz v práci Dissertatio de arte combinatoria (1666). Významné výsledky dosiahol aj vo výskume symetrických polynómov a partícií, ktoré však neboli počas jeho života publikované. Dielo Umenie dohadu (Ars conjectandi, 1689, vydané posmrtne 1713) Jacoba Bernoulliho (→ Bernoulliovci) obsahuje enumeráciu permutácií a kombinácií, ako aj Bernoulliho čísla. Francúzsky matematik A. de Moivre pri riešení kartovej úlohy formalizoval princíp zapojenia a vypojenia (The Doctrine of Chances, 1718), pri riešení rekurentných problémov zaviedol vytvárajúce funkcie (1730) a odhadol asymptotické správanie faktoriálu (1733), ktoré neskôr upresnil J. Stirling (→ Stirlingov vzorec). K mnohým príspevkom L. Eulera k vývoju kombinatoriky patria použitie vytvárajúcich funkcií pri štúdiu partícií a Eulerových čísel pri enumerácii permutácií, položenie základov teórie grafov vyriešením tzv. problému siedmich mostov v Königsbergu (dnes Kaliningrad), sformulovanie Eulerovej vety o mnohostenoch, ktorá predchádzala vzniku kombinatorickej topológie (1894, J. H. Poincaré), ako aj sformulovanie hypotézy o grécko-latinských štvorcoch uspokojivo vyriešenej až v roku 1959.
V priebehu 18. a 19. stor. viedlo štúdium založené na roznásobovaní mnohočlenov k objavom mnohých kombinatorických identít pre Stirlingove, Catalanove, Bellove a Schröderove čísla. V mnohých prípadoch bola ich kombinatorická interpretácia nájdená až s odstupom času, napr. fakt, že Catalanove čísla, ktoré poznal už Euler, udávajú počet úplných binárnych stromov, bol zistený až v 50. rokoch 20. stor., keď sa binárne stromy začali podrobne skúmať ako základný objekt v rámci teoretickej informatiky.
V kombinatorike je pomerne bežné, že drobnou obmenou požadovaných vlastností skúmaných konfigurácií sa môžu výrazne zmeniť charakter a náročnosť úlohy. Príkladom môže byť úloha určenia počtu stromov s \(n\) vrcholmi. Počet stromov s \(n\) navzájom rôznymi vrcholmi (napr. očíslovanými) určil už 1889 A. Cayley ako \(n^{n-2}\). Ak sa však jednotlivé vrcholy nerozlišujú, pri určovaní počtu rôznych stromov treba zohľadniť aj počet vnútorných symetrií konfigurácií. To sa uspokojivo podarilo až po vyvinutí novej metódy G. Pólyom (1937, Pólyova enumeračná veta), ktorú nezávisle od neho objavil už 1927 John Howard Redfield (*1879, †1944).
Prínosom do teórie partícií bolo vyjadrenie partícií pomocou Youngových (Ferrersových) diagramov, ktoré v roku 1871 viedlo ku kombinatorickému vysvetleniu viacerých identít (J. J. Sylvester) a 1881 ku kombinatorickému dôkazu Eulerovej vety o päťuholníkových číslach (Fabian Franklin, *1853, †1939). Partície sa prirodzeným spôsobom objavujú aj v iných oblastiach matematiky, napr. v teórii reprezentácií symetrických grúp a klasických Lieho grúp, ktorú 1900 rozpracoval Alfred Young (*1873, †1940) a 1903 F. G. Frobenius. Asymptotické správanie ich počtu určili 1918 pomocou metód analytickej teórie čísel G. H. Hardy a S. A. Ramanujan, neskôr (1937) ho upresnil Hans Rademacher (*1892, †1969).
Viaceré z kombinatorických úloh majú pôvod v tzv. rekreačnej matematike. Riešenie tzv. problému pätnástich školáčok (1847) od Thomasa Penyngtona Kirkmana (*1806, †1896) je príkladom Steinerovho systému trojíc (1853, J. Steiner). Neskôr sa ukázal jeho súvis s geometriou projektívneho priestoru \(PG(3,2)\) nad \(\mathbb{Z}_2\) (→ konečná geometria), predznamenávajúc významný rozvoj geometrických a algebraických metód v kombinatorike od prvej pol. 20. stor. Steinerove systémy sú špeciálnym typom blokových plánov, ktoré 1935 pri návrhoch experimentov zaviedli R. A. Fisher a Frank Yates (*1902, †1994). Blokové plány súvisia s konečnými grupami (1861, Mathieuho grupy), mriežkami (1938, Wittova schéma; 1967, Leechova mriežka) a korekčnými kódmi (1949, Golayov kód). R. 1939 ich Raj Chandra Bose (*1901, †1987) zovšeobecnil do podoby asociačných schém, ktoré v roku 1973 použil Philippe Delsarte v teórii kódovania. Pri klasifikácii jednoduchých konečných grúp sa ukázali hlboké prepojenia kombinatoriky, geometrie a teórie grúp. R. 1979 John Horton Conway (*1937, †2020) a Simon Phillips Norton (*1952, †2019) poukázali na mnohé neočakávané podobnosti medzi grupou monster a modulárnymi funkciami a vyslovili hypotézu nazvanú monstrous moonshine, ktorú až 1992 dokázal a vysvetlil Richard Ewen Borcherds (*1959). Inými príkladmi z oblasti rekreačnej matematiky sú magické štvorce a tzv. problém tridsiatichšiestich dôstojníkov, ktorých skúmanie priviedlo L. Eulera k hypotéze (1782), že grécko-latinské štvorce rádu \(n\) neexistujú pre \(n\) tvaru \(n=4k+2\). Hypotéza bola dokázaná 1901 Gastonom Tarrym (*1843, †1913) pre \(n=6\) (t. j. pre \(k=1\)). R. 1959 – 60 R. Ch. Bose, Sharadchandra Shankar Shrikhande (*1917, †2020) a Ernest Tilden Parker (*1926, †1991) však ukázali, že grécko-latinské štvorce existujú pre všetky \(n\) tvaru \(n=4k+2\), \(k \ge 2\). Nájdenie grécko-latinského štvorca rádu 10 bolo jedným z prvých prípadov, keď sa riešenie kombinatorického problému našlo pomocou počítača. Príkladom latinských štvorcov, na ktoré sú kladené dodatočné štrukturálne podmienky, je aj populárna hra sudoku.
Mnohé koncepty objavené už pri zrode modernej kombinatoriky boli časom zovšeobecnené alebo znovuobjavené v príbuzných odboroch. Princíp zapojenia a vypojenia sa v teórii čísel objavil v podobe Möbiovej inverznej formuly (1832, A. F. Möbius), jeho moderným kombinatorickým zovšeobecnením je teória incidenčných algebier pre čiastočne usporiadané množiny (1964, G.-C. Rota). Dirichletov princíp (princíp priehradiek) je v modernej kombinatorike zovšeobecnený v podobe existenčných viet o reprezentantoch systémov podmnožín, ktoré 1927 sformulovali Karl Menger (*1902, †1985), 1931 Dénes Kőnig (*1884, †1944) a 1935 Philip Hall (*1904, †1982), pozoruhodné zovšeobecnenia má aj v extremálnej kombinatorike, v ktorej je typickou úlohou určiť, akú najmenšiu, resp. najväčšiu veľkosť alebo hustotu môže mať trieda objektov, aby spĺňala predpísanú vlastnosť. Od začiatku 20. stor. sa rozvíja Ramseyho teória (1916, I. Schur; 1927, B. L. van der Waerden; 1928, F. P. Ramsey) s presahmi do extremálnej teórie grafov a aditívnej teórie čísel (1941, P. Erdős a Pál Turán, *1910, †1976). Medzi významné techniky patrí tzv. pravdepodobnostná metóda (rozvíjaná hlavne P. Erdősom) poskytujúca nekonštrukčné dôkazy existencie matematických objektov s predpísanými vlastnosťami. Jedným z najvýznamnejších kombinatorických výsledkov 20. stor. je Szemerédiho veta o existencii aritmetickej postupnosti ľubovoľnej dĺžky v množine s kladnou hustotou dokázaná 1975 E. Szemerédim. Jej neskoršie dôkazy boli dosiahnuté pomocou ergodickej teórie vyvinutej 1977 Hillelom Furstenbergom (*1935) alebo pomocou Fourierovej a kombinatorickej analýzy (2001, W. T. Gowers). K novším (2004) výsledkom v aditívnej kombinatorike patrí dôkaz existencie aritmetickej postupnosti prvočísel ľubovoľnej dĺžky T. Taom a Benom Josephom Greenom (*1977).
V 2. pol. 20. stor. došlo v súvislosti s nástupom počítačov k rapídnemu rozvoju diskrétnej matematiky, s ktorým bol spojený aj zvýšený záujem o kombinatoriku. Kombinatorické problémy sa vyskytovali v pozadí praktických otázok, akými sú ukladanie dát či analýza algoritmov (→ teória zložitosti). Rozsiahle strojové výpočty, v minulosti prakticky nerealizovateľné bez počítačov, umožnili rutinné overovanie vlastností veľkého počtu konfigurácií a o. i. 1976 prispeli k dôkazu vety o štyroch farbách (Kenneth Ira Appel, *1932, †2013, a Wolfgang Haken, *1928; → ofarbovanie grafu) alebo 1989 k dôkazu neexistencie projektívnej roviny rádu 10 (Clement Wing Hong Lam). Široký záber kombinatorického výskumu je okrem množstva článkov v desiatkach vedeckých časopisov dokumentovaný aj najväčšou databázou kombinatorického charakteru On-Line Encyclopedia of Integer Sequences (oeis.org), ktorú 1964 založil Neil James Alexander Sloane (*1939); 2018 obsahovala okolo 317 000 postupností s ročným prírastkom okolo 10 000 položiek.
Kombinatorické úlohy sa tradične riešili izolovane a využívali sa pri nich mnohé ad hoc prístupy. Výrazný rozvoj výskumu na konci 20. stor. však priniesol viaceré moderné metódy, ktoré vďaka svojej efektivite a všeobecnosti poukazujú na zjednocujúce princípy a vzájomnú previazanosť rôznych častí kombinatoriky. Ich postupné odhaľovanie je jednou z výzev súčasného výskumu.
Na Slovensku sa kombinatorika rozvíja v Matematickom ústave SAV najmä v rámci výskumu v oblasti teórie grafov (zakladateľská osobnosť A. Kotzig; hlavní predstavitelia J. Bosák, A. Rosa), ďalej na Fakulte matematiky, fyziky a informatiky UK a Stavebnej fakulte STU v Bratislave (hlavní predstavitelia Š. Znám, J. Plesník, P. Horák, J. Širáň, M. Škoviera, R. Nedela, I. Vrťo, M. Knor, Martin Kochol, *1961, Robert Jajcay, *1964), ako aj na Prírodovedeckej fakulte UPJŠ a Technickej univerzite v Košiciach (E. Jucovič, S. Jendroľ, Martin Bača, *1956; Mirko Horňák, *1952). V Bratislave sa od roku 1961 pravidelne organizuje Bratislavský seminár z teórie grafov (pôvodne v Matematickom ústave SAV, v súčasnosti na Fakulte matematiky, fyziky a informatiky UK), na Technickej univerzite v Košiciach prebieha od r. 1966 Košický kombinatorický seminár.