Analytická kombinatorika (NDMI087) 

Co se probralo:

• 25. 2.: Formální mocninné řady nad nějakým okruhem koeficientů, jejich základní operace: násobení konstantou, sčítání, násobení. Existence převrácené hodnoty. Formální konvergence, nekonečné sumy mocninných řad. Skládání řad: jeho (ne)asociativita, existence inverzní řady.
• 4. 3.: Obyčejné kombinatorické třídy (případně s váhovými funkcemi) a jejich obyčejné vytvořující funkce. Kombinatorický význam sčítání a násobní těchto funkcí. Příklad: průměrná délka čekání na první výskyt slova v nekonečném náhodném slově.
• 11. 3.: Labelované kombinatorické třídy, jejich exponenciální vytvořující funkce. Kombinatorický význam pro sčítání, násobení, mocnění a exp(A(x)). Příklady: subbinární nelabelované zakořeněné stromy, obecné labelované zakořeněné stromy. Lagrangeova inverzní formule, příklad jejího užití na předchozí dva příklady, začátek jejího důkazu.
• 18. 3.: Dokončen kombinatorický důkaz Lagrangeovy inverzní formule. Poloměr konvergence mocninných řad,  definice analytické funkce.
• 25. 3.: Základní vlastnosti analytických funkcí (součty, součiny, atd. analytických funkcí jsou analytické). V okolí nulového bodu je analytická funkce nenulová nebo identicky rovná nule. Příklady neanalytických funkcí: Re(z), Im(z), |z|. Limita mocninné řady je analytická uvnitř kruhu konvergence. Pojem oblasti. Nulové body analytické funkce jsou izolované, pokud ta funkce není v celé oblasti nulová.
• 1. 4.: Pojem analytického prodloužení, jeho jednoznačnost na dané oblasti. Definice a komplexní odmocniny, coby analytického prodloužení reálné odmocniny. Další komplexní funkce: exponenciála, sinus, kosinus, logaritmus. Jejich základní vlastnosti, dokázané pomocí jednoznačnosti analytických prodloužení. Singularita funkce vzhledem k nějaké oblasti, formulace věty o souvislosti mezi singularitami a poloměrem konvergence a jejího zesílení pro řady s nezápornými koeficienty. Příklad užití: hrubý odhad na počet uspořádaných množinových rozkladů.
• 8. 4.: Pojem holomorfní funkce, zmínka o jeho ekvivalenci s analytičností. Integrál komplexní funkce podél (po částech hladké) komplexní křivky, definovaný převedením na reálný integrál pomocí parametrizace. Primitivní funkce, její souvislost s hodnotou integrálu. Pojem jednoduše souvislé oblasti, homotopie křivek na oblasti (relativně ke koncovým bodům). Základní fakta o integrálu analytických funkcí: existence primitivní funkce na jednoduše souvislé oblasti, nezávislost hodnoty integrálu na volbě křivky v rámci třídy homotopie, nezávislost hodnoty integrálu přes uzavřenou křivku při spojité deformaci.
• 15. 4.: Cauchyho integrální vzorec. Důkaz věty o tom, že poloha nejbližší singularity určuje poloměr konvergence. Druhy izolovaných singularit: odstranitelné singularity, póly řádu k, podstatné singularity. Meromorfní funkce, jejich rozvoj v okolí pólu řádu k do Laurentovy řady s k zápornými exponenty. Zmínka, že meromorfní funkce na dané oblasti jsou podílem dvou analytických funkcí.
• 22. 4.: Koeficienty racionálních a meromorfních funkcí: rozklad na parciální zlomky pro racionální funkce, aproximace meromorfní funkce na omezené oblasti pomocí racionální funkce. Příklad počty věží, které mají počet kostek 0 mod 3.
• 29. 4.: Příklady meromorfních vytvořujících funkcí: pravděpodobnost, že náhodná permutace délky n nemá žádný cyklus délky d, zobecnění na konečně mnoho zakázaných délek cyklů; počítání počtu uspořádaných množinových rozkladů.
• 6. 5.: Vzorec pro počet uspořádaných množinových rozkladů pomocí součtu nekonečné řady. Eulerova Gamma funkce (definována pomocí integrálu), její základní vlastnosti, její hodnoty v přirozených bodech a v 1/2, její analytické prodloužení, její alternativní definice pomocí limity, její využití pro odhady koeficientů funkcí tvaru 1/(1-z)^q, pro konstantu q nepatřící do {0,-1,-2,...}.
• 20. 5.: Funkce aproximovatelné pomocí funkcí tvaru 1/(1-z)^q. Příklad: počítání 2-regulárních grafů. Výpočet dolního odhadu na n! pomocí Cauchyho integrálního vzorečku.
  

Literatura:

• Flajolet & Sedgewick: Analytic Combinatorics. Obsáhlá monografie, v níž se dá najít většina látky, kterou jsem přednášel, a ještě mnoho dalších výsledků z této oblasti.
• Wilf: Generatingfunctionology. Knížka zabývající se různými aspekty vytvořujících funkcí, včetně stručné kapitolky o analytických metodách.
• Stanley: Enumerative Combinatorics, vol. 2. V této knize najdete kombinatorický důkaz Lagrangeovy inverzní formule, který, pokud vím, není k nalezení v předchozích dvou knihách.