Kapitoly z analytické kombinatoriky

Přednáška se koná ve středu ve 12:20 na chodbě před místností 323. Lze si ji zapsat pod názvem "Vybrané kapitoly z teorie grafů". 

Stručný sylabus: mocninné řady, obyčejné a exponenciální vytvořující funkce, použití metod komplexní analýzy pro odhady koeficientů mocninných řad, vytvořující funkce více proměnných.

• P. Flajolet, R. Sedgewick: Analytic Combinatorics
• H. Wilf: Generatingfunctionology

• (25. 2., Jan Volec) Formální mocninné řady, jejich násobení, dělení, kompozice a inverze
• (4.3., Jan Volec) Lagrangeova inerzní formule, (vážené i nevážené) obyčejné vytvořující funkce, příklady: počítání celočíselných kompozic, počítání zakořeněných rovinných stromů, počítání střední hodnoty pro polohu prvního výskytu daného slova v náhodném řetězci
• (18. 3., Vladimír Žák) Labelované kombinatorické třídy, exponenciální vytvořující funkce, součinová a kompoziční formule, příklad: EVF pro Bellova čísla
• (25. 3., Vladimír Žák) Další příklady labelovaných tříd: permutace, zakořeněné stromy. Konvergence mocninných řad, základní vlastnosti analytických funkcí.
• (1. 4., Vít Jelínek) Další vlastnosti analytických funkcí, jednoznačnost analytických prodloužení, izolované singularity, Laurentovy řady v okolí pólu. (Podrobnější spisek, pro ty, kdo byli na jarní škole.)
• (8. 4., Zuzana Safernová) Definice holomorfních a meromorfních funkcí. Integrál komplexní funkce, primitivní funkce, reziduová věta. Použití pro odhad koeficientů mocninné řady.
• (15. 4., Zuzana Safernová) Odhad koeficientů mocninné řady pomocí poloměru konergence: příklad se zakořeněnými stromy. Racionální funkce, obecný tvar jejich koeficientů. Příklad s posloupností hodů falešnou mincí, v níž nepadne dvakrát po sobě panna.
• (22. 4., Pavel Paták) Meromorfní funkce, odhad jejich koeficientů pomocí odečítání pólů. Příklady: pravděpodobnost, že náhodná permutace nemá krátké cykly, počet uspořádaných množinových rozkladů.
• (29. 4., Pavel Paták) Neceločíselné mocniny, a funkce aproximovatelné pomocí neceločíselných mocnin. Gama funkce a její použití při odhadu zobecněných binomických koeficientů. Příklady: přesnější odhad na počet zakořeněných stromů, odhad na počet permutací bez cyklů sudé délky.
• (6. 5., Pavel Klavík) Odhady na koeficienty u funkcí s nezápornými koeficienty pomocí komplexního integrálu, použití pro odhady faktoriálu a kombinačních čísel. Úvod do kombinatorických tříd s parametry, vytvořující funkce více proměnných. Příklad: vytvořující funkce pro binární slova, s druhou proměnnou počítající počet jedniček.
• (13. 5., Pavel Klavík) Příklad s náhodnými procházkami, které se nevrací na nulovou hladinu (motivován vývojem skóre v hazardní hře, kde v každém kole buď korunu vyhraju, nebo korunu prohraju).