Lattice paths and submonoids of ${\mathbb{Z}}^2$

Abstract

We study a number of combinatorial and algebraic structures arising from walks on the two-dimensional integer lattice. To a given step set $X\subseteq {\mathbb{Z}}^2$, there are two naturally associated monoids: ${\mathcal{F}}_X$, the monoid of all $X$-walks/paths; and ${\mathcal{A}}_X$, the monoid of all endpoints of $X$-walks starting from the origin $O$. For each $A\in {\mathcal{A}}_X$, write ${\pi }_X(A)$ for the number of $X$-walks from $O$ to $A$. Calculating the numbers ${\pi }_X(A)$ is a classical problem, leading to Fibonacci, Catalan, Motzkin, Delannoy and Schroder numbers, among many other well-studied sequences and arrays. Our main results give relationships between finiteness properties of the numbers ${\pi }_X(A)$, geometrical properties of the step set $X$, algebraic properties of the monoid ${\mathcal{A}}_X$, and combinatorial properties of a certain bi-labelled digraph naturally associated to $X$. There is an intriguing divergence between the cases of finite and infinite step sets, and some constructions rely on highly non-trivial properties of real numbers. We also consider the case of walks constrained to stay within a given region of the plane. Several examples are considered throughout to highlight the sometimes-subtle nature of the theoretical results.

Contains an appendix joint with Stewart Wilcox. V3: 36 pages, 18 figures, 1 table; referee's suggestions incorporated, to appear in Annals of Combinatorics. V2 (final section on algorithms removed, several subsections and examples removed): 36 pages, 18 figures, 1 table. V1: 63 pages, 45 figures, 1 table