Lattice Paths and Submonoids of $$\mathbb Z^2$$ Z 2
2021
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: $$\mathscr {F}_X$$
, the monoid of all X-walks/paths; and $$\mathscr {A}_X$$
, the monoid of all endpoints of X-walks starting from the origin O. For each
$${A\in \mathscr {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
$$\mathscr {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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
13
References
0
Citations
NaN
KQI