Cyril Banderier, CR-CNRS, University Paris13
"Limit Laws in Analytic Combinatorics and Random
This course presents how analytic combinatorics can get enumeration, asymptotics and limit laws for numerous combinatorial structures.
We illustrate this powerful approach on random walks,
for which we fill first present classical results (related to Brownian motion theory),
and then concentrate on the discrete point of view (lattice paths).
Despite the fact that they have been studied for centuries,
these theories have been revolutionized during the last ten years,
mostly via the nice "kernel method"; using this method, we will show
how we can
We will explain why and when we can get Gaussian, Rayleigh, Airy,
Theta, Gumbel, or some other limit distributions.
Finally we will use the computer to make some simulations and conjectures,
that we will prove with the tools presented in this course.
- obtain a functional equation for the relevant generating function
and solve it,
- derive fast enumeration schemes (with a pinch of computer algebra),
- get asymptotic results (where complex analysis "à la Flajolet" will play a key role), and
- get the limit laws of more and more difficult parameters.
As typical of analytic combinatorics, all the methods presented here
apply to a
large variety of combinatorial structures (random walks, permutations,
partitions, tilings, trees, maps, words) which play a key role in
computer science, bioinformatics and theoretical physics.