Lattice walks ending on a coordinate hyperplane avoiding backtracking and repeats

Central binomial coefficients and Catalan numbers are two fundamental sequences in enumerative combinatorics as well as in other areas of mathematics. Both these numbers can be thought of as enumerating walks in $\mathbb{Z}$ with steps from $\{\pm 1\}$ that end at the origin. The Catalan number model has the additional restriction the walks must stay in the nonnegative integers and correspond to the height of usual Dyck paths. We generalize this situation by looking at walks in $\mathbb{Z}^{r+1}$ with steps from $\{\pm 1\}^{r+1}$. The condition that the walks must end on the hyperplane defined by $x_{r+1}=0$ is imposed. For the generalized Catalan situation we also require the walks be confined to the halfspace with $x_{r+1}\geq 0$. We then look at such walks avoiding the backtracking pattern $[v,-v]$ and the repeat pattern $[v,v]$ for $v\in\{\pm 1\}^{r+1}$. Here a walk is a sequence of vectors from $\{\pm 1\}^{r+1}$ and $[v_{1},v_{1},\dots,v_{\ell}]$ contains the pattern $[u_{1},u_{2}]$ if and only if $[v_{i},v_{i+1}]=[u_{1},u_{2}]$ for $1\leq i<\ell$. That is, our pattern avoidance means that no contiguous subsequence of a walk is equal to the pattern. When $r=0$ there are no nonempty walks ending at the origin avoiding the backtracking pattern. While for avoiding the repeat pattern there are the two walks of length $2n$ namely $[+1,-1]^{n}$ and $[-1,+1]^{n}$ only the first of which is relevant the Catalan situation. However, for $r>0$ there are many such walks. Our aim is enumerating these walks.

Walks in integer lattices are a topic of interest in computer science, mathematics, physics, and statistics. Lattice path combinatorics can be approached from various perspectives (see [Kra15] for survey with focus on enumeration). Our focus is enumeration (i.e. finding recurrences, generating functions, and formulas). One such enumeration problem involving avoidance of backtracking we solve gives an interpretation of sequence A085363 in the OEIS [OEI] in terms of 2D lattices walks. This sequence was an original motivation, but we found the techniques readily generalized to arbitrary dimension as well as avoidance of consecutive steps. In addition to combinatorial arguments, we make use of formal language theory and its connection to generating functions. We also use automated methods for dealing with hypergeometric terms and finding polynomial recurrences (see [PWZ96] for more about these types of techniques).

Lattice path enumeration has a long and rich history, and recent attention has been given to avoiding patterns as we consider here. We saw for Dyck paths (i.e. $r=0$) that avoiding consecutive steps or backtracking is not interesting. However, the consecutive step patterns $[+1,+1]$ and $[-1,-1]$ are special cases of runs $[+1,+1,\dots,+1]$ and $[-1,-1,\dots,-1]$. Study of Dyck paths avoiding runs of given lengths (as well as peaks and valleys avoiding certain heights) is conducted in [EZ] with automated computational methods and in [BDB] with formal grammar techniques. Avoiding a pattern in lattice paths was considered in [ABBG20] and later for multiple patterns in [AB20, ABR20]. These latter works make use of the so called vectorial kernel method which modifies the kernel method to allow for pattern avoidance. While the vectorial kernel method is an efficient and flexible way to access the generating functions of our walks, we want to focus in this work on binomial expressions for the coefficients; so, for our set of jumps we present a way to do so via an alternative approach based on context-free grammars and ad-hoc recurrences.

The remainder of the paper is organized as follows. In Section 2 we formally define the languages of walks we are interested in and show that their generating functions are algebraic (and hence the sequences of coefficients satisfy a recurrence with polynomial coefficients). Formulas and recurrences are found in Section 3, then generating functions and asymptotics are given in Section 4. Lastly, Section 5 concludes by looking at some open problems and related work. Also, there is the Appendix which provides Maple code used to prove some results from earlier in the article.

For $r\geq 0$ we consider lattice walks in $\mathbb{Z}^{r+1}$ that use steps from $\mathcal{S}_{r}:=\{\pm 1\}^{r+1}$ which start at the origin and end with $x_{r+1}=0$. Let $\mathbf{A}^{(r)}$ be the language over the alphabet $\mathcal{S}_{r}$ consisting of such walks. Evidently any such walk must consist of $2n$ steps for some $n\geq 0$. Let $a^{(r)}_{n}$ be the number of such walks with $2n$ steps.

We are further interested in subsets of these walks with additional conditions. We consider the language of walks $\mathbf{B}^{(r)}\subseteq\mathbf{A}^{(r)}$ which avoid backtracking. That is, walks ending with $x_{r+1}=0$ with the additional constraint that a step $v$ cannot be directly followed by $-v$ for any $v\in\mathcal{S}_{d}$. We let $b^{(r)}_{n}$ be the number of walks avoiding backtracking with $2n$ steps. Similarly, we let $\mathbf{C}^{(r)}\subseteq\mathbf{A}^{(r)}$ denote the language of walks avoiding consecutive repeats. That is, walks avoiding a step $v$ directly followed by $v$ for any $v\in\mathcal{S}_{d}$. We let $c^{(r)}_{n}$ denote the number of walks avoiding consecutive repeats with $2n$ steps.

Now let $\mathbf{D}^{(r)}$ be the language consisting of walks starting at the origin for which $x_{r+1}\geq 0$ at all times and finish with $x_{r+1}=0$. We similarly let $\mathbf{E}^{(r)}\subseteq\mathbf{D}^{(r)}$ and $\mathbf{F}^{(r)}\subseteq\mathbf{D}^{(r)}$ denote the sublanguages which avoid backtracking and consecutive equal steps respectively. Again we let the sequences $d^{(r)}_{n}$, $e^{(r)}_{n}$, and $f^{(r)}_{n}$ count the number of walks of length $2n$ in each of the languages $\mathbf{D}^{(r)}$, $\mathbf{E}^{(r)}$, and $\mathbf{F}^{(r)}$. Letting $\mathbf{X}^{(r)}$ denote the language of walks avoiding the backtracking pattern $[v,-v]$ and $\mathbf{Y}^{(r)}$ denote the language of walks avoiding consecutive repeats $[v,v]$ we have

as expressions of our languages of interest. It is worth noting that both $\mathbf{X}^{(r)}$ and $\mathbf{Y}^{(r)}$ are regular languages.

In enumeration it is often advantageous and interesting to work with generating functions. We will consider the following generating functions

which are the ordinary generating functions for our sequences. Also for any $r\geq 0$, $v\in\mathcal{S}_{r}$, and $\mathbf{L}\in\{\mathbf{A}^{(r)},\mathbf{B}^{(r)},\mathbf{C}^{(r)},\mathbf{D}^{(r)},\mathbf{E}^{(r)},\mathbf{F}^{(r)}\}$ we let $\mathbf{L}(v)\subseteq L$ be the sublanguage of walks which start with $v$. Furthermore, we let

be the generating function for these walks with a given first step.

We now review some facts on power series which can be found in [Sta80]. A formal power series $G(x)$ is algebraic if it satisfies a nontrivial polynomial equation. A holonomic sequence is a sequence that satisfies a recurrence relation with polynomial coefficients. That is, a sequence $\{t_{n}\}_{n\geq 0}$ such that

for some $j$ and polynomials $p_{i}(n)$ not all of which are equal to zero. The sequence of coefficients of an algebraic formal power series is holonomic.

From a generating function one can find the asymptotics of its sequence of coefficients. Methods for obtaining these asymptotic expressions are well established and can be found in the text [FS09]. We write $f(n)\sim g(n)$ to mean that

which is the standard notation. Consider a generating function $G(z)=\sum_{n\geq 0}g_{n}z^{n}$ viewed as a complex analytic function and let $\rho$ be its unique singularity closest to the origin. Assume $G(z)$ approaches $C\cdot(1-\frac{z}{\rho})^{-\alpha}$ as $z\to\rho$ for some constant $C$ where $\alpha$ is neither $0$ nor a negative integer. This is the situation that will be relevant to use, and under these assumptions

where $\Gamma(\alpha)$ denotes the Gamma function.

Let us now show using formal language and generating function theory that each of our generating functions are algebraic from which it follows each of the sequences is holonomic. Our goal will be to further understand these generating functions and find the recurrence relations that the sequences obey. The Chomsky–Schützenberger enumeration theorem [CS63] (see [KS86, Pan05] for proofs) says that the length generating function of an unambigous context free language is algebraic. A deterministic context free language is a language recognized by a deterministic push down automata (DPDA). Ginsburg and Greibach [GG66] have shown that a deterministic context free language is an unambiguous context free language and that when such a language is intersected with a regular language it remains a deterministic context free language.

Now that we know our generating functions are algebraic we turn our attention to describing these generating functions and their coefficient as explicitly as possible. The values of $a_{n}^{(r)}$ and $F(x;\mathbf{A}^{(r)})$ can be found without difficulty. We have that

since any walk in $\mathbf{A}^{(r)}$ is

where for coordinates $1\leq i\leq r$ in $v_{1},\dots,v_{2n}$ form any binary string and the last coordinate makes a balanced binary string. Hence, $a^{(r)}_{n}$ satisfies the recurrence

of the form guaranteed from being holonomic. It follows that

is the expression for the generating function. By similar arguments we find that

where $C_{n}=\frac{1}{n+1}\binom{2n}{n}$ is the $n$th Catalan number. Also,

and

give the recurrence and generating function for $d^{(r)}_{n}$

In this section we find formulas for each of the sequences $\{b^{(r)}_{n}\}_{n\geq 0}$, $\{c^{(r)}_{n}\}_{n\geq 0}$, $\{e^{(r)}_{n}\}_{n\geq 0}$, and $\{f^{(r)}_{n}\}_{n\geq 0}$ consisting of a sum of hypergeometric terms and as an evaluation of a hypergeometric function. Zeilberger’s algorithm [Zei90, Zei91] is then applied to obtain a recurrence.