ANALYTICKÁ A ENUMERATÍVNA KOMBINATORIKA
Letný semester 2023/24
Rozvrh:
Pondelok, 16:30 – 18:00, akvárium M-IX
Streda, 14:50 – 16:20, akvárium M-VII
Kontakt:
Peter Kostolányi
e-mail: kostolanyi zavináč fmph a tak ďalej
miestnosť: M-227
Skriptá:
Počas semestra bude postupne pribúdať predbežná verzia skrípt k predmetu.
Ďalšie materiály:
Prednášky:
Prednáška č. 1: Úvod do enumeratívnej kombinatoriky (19. februára 2024)
- Bijektívne dôkazy, Catalanove čísla. Kombinatorické triedy, ich disjunktné zjednotenia a karteziánske súčiny.
- Skriptá: kapitola 1 a prvá časť oddielu 2.1.
Prednáška č. 2: Formálne mocninové rady I (21. februára 2024)
- Obor integrity formálnych mocninových radov. Multiplikatívne inverzné prvky a delenie formálnych mocninových radov.
- Skriptá: zvyšok oddielu 2.1; oddiely 2.2 a 2.3.
Prednáška č. 3: Formálne mocninové rady II (26. februára 2024)
- Formálna derivácia. Obyčajné vytvárajúce funkcie a ich použitie pri riešení lineárnych rekurencií.
- Skriptá: oddiely 2.4 až 2.6.
Prednáška č. 4: Formálne mocninové rady III (28. februára 2024)
- Lokálne konečné súčty a skladanie formálnych mocninových radov. Formálna exponenciálna funkcia.
- Skriptá: oddiely 2.7 a 2.8.
Prednáška č. 5: Formálne mocninové rady IV (4. marca 2024)
- Formálny logaritmus. Racionálne mocniny formálnych mocninových radov.
- Skriptá: oddiel 2.9 a prvá časť oddielu 2.10.
Prednáška č. 6: Formálne mocninové rady V a úvod do symbolickej metódy (6. marca 2024)
- Formálna verzia Newtonovej zovšeobecnenej binomickej vety. Definícia komplexných mocnín formálnych mocninových radov. Nekonečné súčiny formálnych mocninových radov. Označené a neoznačené objekty. Kombinatorické triedy neoznačených objektov a prípustné konštrukcie na nich. Neutrálne a atomické triedy, disjunktné zjednotenie, karteziánsky súčin, mocniny kombinatorických tried a prechod k triede všetkých konečných postupností.
- Skriptá: veta 2.10.7, definície 2.10.8 a 2.10.9, oddiely 2.11 až 3.2 a začiatok oddielu 3.3 (po vetu 3.3.5).
Prednáška č. 7: Symbolická metóda pre neoznačené objekty (11. marca 2024)
- Niektoré významné prípustné konštrukcie na kombinatorických triedach neoznačených objektov: prechod k triede konečných podmnožín a multimnožín, punktácia, substitúcia. Iteratívne a rekurzívne špecifikácie.
- Skriptá: zvyšok oddielu 3.3 a oddiel 3.4.
Prednáška č. 8: Príklady použitia symbolickej metódy pre neoznačené objekty (13. marca 2024)
- Niekoľko príkladov.
- Skriptá: oddiel 3.5.
Prednáška č. 9: Symbolická metóda pre označené objekty (18. marca 2024)
- Kombinatorické triedy označených objektov. Exponenciálne vytvárajúce funkcie. Niektoré významné prípustné konštrukcie na kombinatorických triedach označených objektov.
- Skriptá: oddiel 3.6 a väčšia časť oddielu 3.7.
Prednáška č. 10: Príklady použitia symbolickej metódy pre označené objekty (20. marca 2024)
- Zvyšné prípustné konštrukcie na triedach označených objektov. Niekoľko príkladov.
- Skriptá: zvyšok oddielu 3.7 a oddiel 3.8.
Prednáška č. 11: Lagrangeova veta o inverzii a Cayleyho vzorec (25. marca 2024)
- Formálne Laurentove rady. Lagrangeova veta o inverzii. Enumerácia označených stromov a Cayleyho vzorec. Dôkaz Cayleyho vzorca pomocou symbolickej metódy a Lagrangeovej vety o inverzii. Bijektívny dôkaz Cayleyho vzorca založený na Prüferových kódoch.
- Skriptá: kapitola 4.
Prednáška č. 12: Základy analytickej kombinatoriky (27. marca 2024)
- Súvis polomeru konvergencie Maclaurinovho radu s asymptotickými vlastnosťami koeficientov. Pringsheimova veta. Exponenciálny rád postupnosti a prvý princíp asymptotiky koeficientov.
- Skriptá: kapitola 5.