Welcome to Week 5 of "Analytic Combinatorics."
This week, we study one of the jewels of analytic combinatorics: the
Flajolet-Odlyzko theorem that provides universal laws giving
coefficient asymptotics for the large class of GFs having
singularities of the square-root and logarithmic type.
----------
Lecture 6: Singularity Analysis. This lecture addresses the basic
Flajolet-Odlyzko theorem, where we find the domain of analyticity of
the function near its dominant singularity, approximate using
functions from standard scale, and then transfer to coefficient
asymptotics term-by-term.
Lecture 7: Applications of Singularity Analysis. We see how the
Flajolet-Odlyzko approach leads to universal laws covering
combinatorial classes built with the set, multiset, and recursive
sequence constructions. Then we consider applications to many of the
classic combinatorial classes that we encountered in Lectures 1 and 2.
----------
Your assignment for this week, due at 11:59PM on
Thursday, April 21, 2022
is to write up and submit solutions to
Web Exercises VI.1, VI.2, and VII.1 on the "Analytic
Combinatorics" booksite.
As usual, submit a potential exam question on the week's material.
Submit files named
"AC5-Q1.pdf"
"AC5-Q2.pdf"
"AC5-Q3.pdf"
"AC5-QQ.pdf"
RS