ANALYTICKÁ A ENUMERATÍVNA KOMBINATORIKA

Letný semester 2019/2020

Časy prednášok:

Pondelok, 16:30 – 18:00, miestnosť M-IX.

Utorok, 16:30 – 18:00, miestnosť M-IX (tento termín sa ešte môže zmeniť).

V čase uzatvorenia univerzity kvôli COVID-19 prebieha prednáška dištančnou formou. Nižšie na tejto stránke budú priebežne zverejňované materiály na samoštúdium; podrobnejšie pokyny budú zapísaným študentom poskytované mailom.

Kontakt:

Peter Kostolányi

e-mail: kostolanyi zavináč fmph a tak ďalej

miestnosť: M-227

Študijné materiály:

• Odporúčaná literatúra: Flajolet, P.; Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, 2009. Voľne dostupná internetová verzia.
• Stránka predmetu Komplexná analýza pre informatikov z minulého semestra.
• Odkazy na ďalšiu relevantnú literatúru budú pridávané k jednotlivým prednáškam.
• Počas uzatvorenia univerzity budú nižšie zverejňované študijné materiály k jednotlivým témam.

Témy a materiály na samoštúdium v čase uzatvorenia univerzity:

Zvyšok symbolickej metódy

• Odporúča sa doštudovať z knihy Flajoleta a Sedgewicka (bližšie informácie mailom).

Analytické vlastnosti vytvárajúcich funkcií

• Študijný materiál.
• Odporúčané čítanie: oddiely IV.1 a IV.3 knihy Flajoleta a Sedgewicka (okrem časti oddielu IV.3 o sedlových bodoch).
• Dôkaz Pringsheimovej vety možno nájsť napríklad aj v starej klasickej knihe od Titchmarsha (paragraf 7.21 na strane 214).

Hankelova integrálna reprezentácia funkcie 1/Γ(z)

• Študijný materiál.
• Menej podrobný dôkaz možno nájsť aj v dodatku B.3 knihy Flajoleta a Sedgewicka.
• Iná verzia Hankelovej integrálnej reprezentácie je dokázaná v Henriciho knihe (bibliografický odkaz je v materiáli vyššie).

Úvod do metódy analýzy singularít (1. časť)

• Študijný materiál.
• Odporúčané čítanie: oddiely VI.1 a VI.2 knihy Flajoleta a Sedgewicka.
• Pôvodný článok Flajoleta a Odlyzka z roku 1990.

Úvod do metódy analýzy singularít (2. časť)

• Študijný materiál.
• Odporúčané čítanie: oddiely VI.3 a VI.4 knihy Flajoleta a Sedgewicka.
• Pôvodný článok Flajoleta a Odlyzka z roku 1990.

Jednoduché aplikácie metódy analýzy singularít

• Študijný materiál.
• Odporúčané čítanie: príklady aplikácií metódy analýzy singularít z knihy Flajoleta a Sedgewicka.

Vytvárajúce funkcie s viacerými dominantnými singularitami

• Študijný materiál.
• Odporúčané čítanie: oddiel VI.5 knihy Flajoleta a Sedgewicka.

Koeficienty racionálnych, meromorfných a algebraických funkcií

• Asymptotické odhady pre koeficienty racionálnych a meromorfných funkcií možno odvodiť aj jednoduchšími metódami, než je analýza singularít (všetky singularity takýchto funkcií sú póly). Príslušná teória je rozpracovaná v kapitole IV knihy Flajoleta a Sedgewicka.
• Vlastnosti koeficientov algebraických funkcií sú do veľkej miery dané tým, že ich singulárne rozvoje sú vždy Puiseuxovými radmi. Odporúčané čítanie: oddiel VII.7 knihy Flajoleta a Sedgewicka.
• Dá sa dokázať, že vytvárajúce funkcie prislúchajúce kombinatorickým triedam s bezkontextovými špecifikáciami sú vždy algebraické (čo okrem iného využíval Flajolet na dokazovanie vnútornej viacznačnosti bezkontextových jazykov). V skutočnosti ide o veľmi špeciálny typ algebraických funkcií. Asymptotické vlastnosti koeficientov vytvárajúcich funkcií prislúchajúcich k silne súvislým bezkontextovým špecifikáciám sú popísané Drmotovou-Lalleyovou-Woodsovou vetou, o ktorej sa možno dočítať v oddiele VII.6 knihy Flajoleta a Sedgewicka (jej dôkaz presahuje rámec tohto predmetu). S obdobným výsledkom pre všeobecné bezkontextové špecifikácie prišli len nedávno Banderier a Drmota.

Vytvárajúce funkcie viacerých premenných

• Študijný materiál.
• Odporúčané čítanie: začiatok kapitoly III knihy Flajoleta a Sedgewicka.
• Článok o aplikáciách analytickej kombinatoriky na oblasť popisnej zložitosti.

Odkazy na prípadné ďalšie štúdium

• Metóda sedlových bodov – kapitola VIII knihy Flajoleta a Sedgewicka.
• Pólyova teória (klasická enumeračná metóda pre neoznačené objekty) – Brualdi, R. A.: Introductory Combinatorics 5th ed. Pearson, 2009 (kapitola 14).
• Súvis Pólyovej teórie s analytickou kombinatorikou – oddiel I.6 knihy Flajoleta a Sedgewicka.
• Enumerácia súvislých grafov – príklad II.15 knihy Flajoleta a Sedgewicka.
• Cayleyho vzorec pre počet označených nezakorenených stromov – Matoušek, J.; Nešetřil, J.: Kapitoly z diskrétní matematiky, tretie vydanie. Karolinum, 2007 (kapitola 8, v ktorej možno nájsť hneď päť rôznych dôkazov tohto vzorca).
• Möbiova inverzia na čiastočne usporiadaných množinách – Brualdi, R. A.: Introductory Combinatorics 5th ed. Pearson, 2009 (oddiel 6.6).

Domáce úlohy:

Všetky sady domácich úloh majú spoločný termín odovzdania: 10. júna 2020 pre riadny termín, 20. júna 2020 pre prvý opravný termín a 30. júna 2020 pre druhý opravný termín. Je však odporúčané riešiť ich priebežne.

• Prvá sada úloh.
• Druhá sada úloh.
• Tretia sada úloh.

Prednášky zo začiatku semestra:

Prednáška č. 1: Úvod (17. februára 2020)

• Predmet štúdia enumeratívnej kombinatoriky. Klasická metóda bijektívnych dôkazov, Catalanove čísla. Motivácia pre interpretáciu enumeračných postupností prostredníctvom formálnych mocninových radov a pre zavedenie pojmu vytvárajúcej funkcie.
• Rozširujúce čítanie ku Catalanovým číslam: Stanley, R. P.: Catalan Numbers. Cambridge University Press, 2015 (vyše 200 kombinatorických interpretácií Catalanových čísel).

Prednáška č. 2: Formálne mocninové rady I (18. februára 2020)

• Obor integrity formálnych mocninových radov o jednej premennej s komplexnými koeficientmi. Kritériá existencie multiplikatívnych inverzných prvkov a podielov. Aplikácia na Fibonacciho čísla.
• Odporúčané čítanie k tejto a nasledujúcim dvom prednáškam:
  • Niven, I.: Formal Power Series. In The American Mathematical Monthly, vol. 76, no. 8, pp. 871–889 (1969).
  • Cameron, P. J.: Notes on Counting: An Introduction to Enumerative Combinatorics. Cambridge University Press, 2017 (kapitola 2).

Prednáška č. 3: Formálne mocninové rady II (24. februára 2020)

• Nekonečné súčty cez lokálne konečné systémy formálnych mocninových radov, zloženie radov, nekonečné súčiny. Formálna derivácia, formálna exponenciálna funkcia a formálny logaritmus.

Prednáška č. 4: Formálne mocninové rady III (25. februára 2020)

• Racionálne mocniny formálnych mocninových radov. Binomická veta. Komplexné mocniny formálnych mocninových radov. Vnorenie oboru integrity funkcií holomorfných v bode 0 do oboru integrity formálnych mocninových radov.

Prednáška č. 5: Neoznačené kombinatorické objekty a obyčajné vytvárajúce funkcie I (2. marca 2020)

• Kombinatorické triedy, enumeračné postupnosti, obyčajné vytvárajúce funkcie. Prípustné konštrukcie na kombinatorických triedach a zodpovedajúce konštrukcie na vytvárajúcich funkciách. Symbolická metóda pre neoznačené objekty.
• Odporúčané čítanie k tejto a nasledujúcej prednáške: Flajolet a Sedgewick, kapitola I.