An introduction to lattice path counting (with catastrophes)

Abstract

The enumeration of lattice paths is a classical topic in combinatorics which is up to now a very active field of research. They have many applications in chemistry, physics, mathematics and computer science. For example lattice paths are used as the solution of integer programming problems, in cryptanalysis, in crystallography and as models in queueing theory. After a short introduction of these objects and for our purposes classical solution strategies (e.g., generating functions and analytic combinatorics), we will introduce a new model of lattice paths: lattice paths with catastrophes. Such paths arise for example in queuing theory where it is natural to have models with a "reset" of the queue. In terms of lattice paths or random walks, it is like having the possibility of jumping from any altitude to zero. These objects have the interesting feature that they do not have the same intuitive probabilistic behaviour like classical lattice paths. In this talk we will quantify some relations between these two types of paths. Our main tools will be generating functions and asymptotic transfer theorems from analytic combinatorics. With these we solve the enumeration problem and derive several limit laws for parameters like the number of returns to zero or the size of an average catastrophe. This is joint work with Cyril Banderier.