We consider paths in the plane governed by the following rules: (a) There is a finite set of states. (b) For each state *q*, there is a finite set *S*(*q*) of allowable "steps" ((*i,j)*,*q*′). This means that from any point (*x*,*y*) in state *q*, we can move to (*x*+*i*,*y*+*j*) in state *q*′. We want to count the number of paths that go from (0,0) in some starting state q_{0} to the point (*n*,0) without ever going below the *x*-axis. There are strong indications that, under some natural technical conditions, the number of such paths is asymptotic to *C*^^{n}/(√*n*^^{3}), for some "growth constant" *C* which I will show how to compute.

I will discuss how lattice paths with states can be used to model asymptotic counting problems for some non-crossing geometric structures (such as trees, matchings, triangulations) on certain structured point sets. These problems were recently formulated in terms of so-called production matrices.

This is ongoing joint work with Andrei Asinowski and Alexander Pilz.

Nov 04, 2019 | 02:15 PM

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

Room 005 (Ground Floor)