Pierre Nicodème, Université Paris 13
"Introduction to Analytic Combinatorics"
The course is a short introduction to Analytic Combinatorics (AC), a
relatively recent and powerful branch of mathematics that draws upon
combinatorial and analytic techniques to investigate the properties of
(large) discrete combinatorial structures. The course will focus on two
fundamental and representative tools: the symbolic method
(combinatorial techniques) and singularity analysis (analytical techniques),
although we will briefly touch upon some other important techniques,
methods and tools from AC like the saddle point method. Along the
course, we will illustrate with numerous examples the basics of AC
using applications coming from Computer Science, more specifically
from the analysis of algorithms and data structures.
Some background on data structures and algorithms (to follow the
understand the applications of AC), and on elementary probability,
combinatorics and complex analysis (to understand the principles of
is necessary. First-year undergraduate level must be enough to follow
the course, but for students who would like to delve into more
material on their own, a stronger background in mathematics and
Computer science is
The fundamental bibliographic reference is the book by Flajolet and
Sedgewick "Analytic Combinatorics", Cambridge U. Press
(2009), which is freely available in the web.