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₀ 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^³), 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.