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.
Domáce úlohy:
Najneskôr do skúšky je potrebné vyriešiť najmenej osem úloh.
Ď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á: oddiely 5.1 až 5.3.
Prednáška č. 14: Hankelova integrálna reprezentácia funkcie 1/Γ(z) I (3. apríla 2024)
- Opakovanie najdôležitejších vlastností funkcie gama. Legendreov vzťah a súvis funkcie gama so sínusom. Veta o Hankelovej integrálnej reprezentácii funkcie 1/Γ(z) a prvé tvrdenia vedúce k jej dôkazu.
- Skriptá z komplexnej analýzy pre informatikov: veta 14.7.9 a oddiel 14.8.
- Skriptá: prvá časť oddielu 5.4 (po lemu 5.4.4).
Prednáška č. 15: Hankelova integrálna reprezentácia funkcie 1/Γ(z) II (8. apríla 2024)
- Dôkaz Hankelovej integrálnej reprezentácie funkcie 1/Γ(z).
- Skriptá: zvyšok oddielu 5.4.
Prednáška č. 16: Metóda analýzy singularít I (10. apríla 2024)
- Úvod do metódy analýzy singularít. Koeficienty Maclaurinových radov funkcií štandardnej triedy.
- Skriptá: oddiel 6.1 a prvá časť oddielu 6.2 (po vetu 6.2.2).
Prednáška č. 17: Metóda analýzy singularít II (15. apríla 2024)
- Koeficienty Maclaurinových radov funkcií štandardnej triedy (pokračovanie).
- Skriptá: zvyšok oddielu 6.2.
Prednáška č. 18: Metóda analýzy singularít III (17. apríla 2024)
- Veta o O-transfere.
- Skriptá: oddiel 6.3.
Prednáška č. 19: Jednoduché aplikácie metódy analýzy singularít (22. apríla 2024)
- Niekoľko príkladov.
- Skriptá: oddiel 6.4.
Prednáška č. 20: Metóda analýzy singularít IV (24. apríla 2024)
- Metóda analýzy singularít v prípade funkcií s konečným počtom dominantných singularít. Koeficienty racionálnych a meromorfných funkcií, enumerácia slov opísaných jednoznačnými racionálnymi výrazmi.
- Skriptá: oddiely 6.5 a 6.6.
Prednáška č. 21: Vytvárajúce funkcie viacerých premenných (29. apríla 2024)
- Algebraické vytvárajúce funkcie a enumerácia slov v jednoznačných bezkontextových jazykoch. Formálne mocninové rady viacerých premenných. Kombinatorické triedy s parametrom a symbolická metóda pre ne. Kumulatívne vytvárajúce funkcie a stredné hodnoty. Pravdepodobnostné vytvárajúce funkcie.
- Skriptá: oddiely 6.7 až 7.5.
Prednáška č. 23: Aplikácie vytvárajúcich funkcií viacerých premenných (6. mája 2024)
- Niekoľko príkladov.
- Skriptá: oddiel 7.6.
Prednáška č. 25: Pólyova teória I (13. mája 2024)
- Akcie grupy na množine. Veta o orbite a stabilizátore. Burnsidova lema. Zjednodušená Pólyova veta o enumerácii.
- Skriptá: oddiely 8.1 až 8.3 a veta 8.4.1.
Prednáška č. 26: Pólyova teória II (15. mája 2024)
- Počítanie náhrdelníkov. Cyklový index a Pólyova veta o enumerácii. Prechod ku kombinatorickej triede neoznačených orientovaných kružníc.
- Skriptá: zvyšok oddielu 8.4 a oddiel 8.5.