Enumerating Minimal Length Lattice Paths

Jackson Evoniuk, Steven Klee, and Van Magnan Department of Mathematics Seattle University 901 12th Avenue Seattle, WA 98122 USA evoniukj@seattleu.edu klees@seattleu.edu magnanv@seattleu.edu

Abstract Given a finite set of integer vectors, S, we consider the set of all lattice walks comprised as ordered sequences of steps whose directions come from S. We further restrict our attention to walks of minimal length, meaning they cannot be shortened through some linear combination of allowable steps from S. We consider the problem of counting the number of such minimal walks terminating at a fixed point (a, b) for various choices of the set S.

1 Introduction

Let S be a finite set of vectors in ℤ^{2}. An S-walk is an ordered sequence s = s_{1}, s_{2}, …, s_{k} of steps with s_{i} ∈ S for all i. We may visualize an S-walk as a path beginning at the origin and terminating at the point whose coordinates are given by s_{1} + s_{2} + ⋯ + s_{k}. We say the the number of steps in a path is its length, and we refer to the elements of S as allowable steps.

The problem of enumerating the walks terminating at a fixed point (a, b) with a, b ∈ ℕ is classical in combinatorics. For example, when S = {(1, 0), (0, 1)}, the number of such walks is \binom{a+b}{a}. When S is an arbitrary set of allowable vectors, there may be several paths of different lengths that terminate at a fixed point (a, b). For example, if S = {(1, 0), (0, 1), (1, 1)}, then the path s = (1, 0), (1, 0), (0, 1), (1, 1), (0, 1), (1, 0), (1, 1) is a path of length 7 terminating at the point (5, 4), and s′ = (1, 1), (1, 0), (1, 1), (1, 1), (1, 1) is a path of length 5 terminating at the point (5, 4). These walks are illustrated in Figure 1.

Figure 1: A non-minimal S-walk (left) and a minimal S-walk (right) terminating at the point (a, b) = (5, 4) when S = {(1, 0), (0, 1), (1, 1)}.

Our goal in this paper is to enumerate the minimal S-walks to a point (a, b) — among all S-walks terminating at (a, b), we consider only those of minimal length. We will write d(a, b; S) to denote the S-distance of the point (a, b) from the origin, which counts the number of steps in a minimal S-walk to (a, b). In the previous example, any S-walk terminating at (5, 4) must utilize at least 5 steps among {(1, 0), (1, 1)}, so d(5, 4; S) ≥ 5. Therefore, s′ is minimal because it is an S-walk of length 5. In contrast, s is not minimal. In general, we write W(a, b; S) to denote the set of minimal S-walks terminating at the point (a, b). Our goal in this paper is to examine this problem in several different contexts, exhibiting either explicit closed formulas or generating functions to determine |W(a, b; S)|.

The rest of the paper is structured as follows. In Section 2, we warm up with the case that S = {(1, 0), (0, 1), (1, 1)}. In Section 3, we consider the sets

Q_{n} := {(1, 0), (0, 1)} ∪ {(i, n − i) : 0 ≤ i ≤ n},

consisting of the standard basis vectors along with all nonnegative integer vectors whose coordinate sum equals n for n ≥ 2. We include the standard basis vectors to ensure that every point (a, b) with a, b ∈ ℕ can be reached by a Q_{n}-walk. Next, we turn our attention to the case that S = {(1, 0), (0, 1), (u, v)} for arbitrary u, v ∈ ℕ in Section 4. In Section 5, we explore the case that S = {(1, 0), (0, 1), (2, 1), (1, 2)}. We conclude in Section 6 with some open problems.

2 Minimal walks for S = {(1, 0), (0, 1), (1, 1)}

We begin by examining the set of allowable steps S = {(1, 0), (0, 1), (1, 1)}. In this and subsequent sections, we have implemented a simple greedy search in Sage [3] to determine the number of minimal S-walks terminating at a given point (a, b) for small values of a and b. This data is depicted visually in Figure 2. For example, the circled 20 indicates that there are 20 minimal S-paths terminating at the point (6, 3).

\begin{matrix}1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 1 \\ 2 \\ 1 \\ 3 \\ 6 \\ 10 \\ 15 \\ 21 \\ 28 \\ 36 \\ 45 \\ 1 \\ 3 \\ 3 \\ 1 \\ 4 \\ 10 \\ 20 \\ 35 \\ 56 \\ 84 \\ 120 \\ 1 \\ 4 \\ 6 \\ 4 \\ 1 \\ 5 \\ 15 \\ 35 \\ 70 \\ 126 \\ 210 \\ 1 \\ 5 \\ 10 \\ 10 \\ 5 \\ 1 \\ 6 \\ 21 \\ 56 \\ 126 \\ 252 \\ 1 \\ 6 \\ 15 \\ 20 \\ 15 \\ 6 \\ 1 \\ 7 \\ 28 \\ 84 \\ 210 \\ 1 \\ 7 \\ 21 \\ 35 \\ 35 \\ 21 \\ 7 \\ 1 \\ 8 \\ 36 \\ 120 \\ 1 \\ 8 \\ 28 \\ 56 \\ 70 \\ 56 \\ 28 \\ 8 \\ 1 \\ 9 \\ 45 \\ 1 \\ 9 \\ 36 \\ 84 \\ 126 \\ 126 \\ 84 \\ 36 \\ 9 \\ 1 \\ 10 \\ 1 \\ 10 \\ 45 \\ 120 \\ 210 \\ 252 \\ 210 \\ 120 \\ 45 \\ 10 \\ 1 \\ a \\ b \\ 0 \\ 0 \\ 1 \\ 1 \\ 2 \\ 2 \\ 3 \\ 3 \\ 4 \\ 4 \\ 5 \\ 5 \\ 6 \\ 6 \\ 7 \\ 7 \\ 8 \\ 8 \\ 9 \\ 9 \\ 10 \\ 10 \end{matrix}

Figure 2: The number of minimal S-walks terminating at each point (a, b) for 0 ≤ a, b ≤ 10 and S = {(1, 0), (0, 1), (1, 1)}.

In that image, we notice that there appear to be two copies of Pascal’s triangle (OEIS sequence \underline{A007318}) glued together along the line y = x. Our first result proves that this pattern continues.

Theorem 1. Let S = {(1, 0), (0, 1), (1, 1)} and let (a, b) be a point with a, b ∈ ℕ. Then |W(a, b; S)| = \binom{max(a,b)}{min(a,b)}.

Proof. By symmetry, we may assume without loss of generality that a ≥ b. Note that d(a, b; S) ≥ a since an allowable step in S increases the x-coordinate by at most 1. Conversely, d(a, b; S) ≤ a since (a, b) can be reached by taking b steps in the (1, 1)-direction, followed by a − b steps in the (1, 0)-direction. Thus d(a, b; S) = a.

In particular, it follows that every step in a minimal S-walk terminating at (a, b) must increase the x-coordinate, and hence such a walk does not use any (0, 1) steps. Since a (1, 1) step is the only remaining step that can increase the y-coordinate, a minimal S-walk is comprised of a total steps, b of which are (1, 1) steps and the remaining a − b of which are (1, 0) steps. There are \binom{a}{b} such paths.

3 Minimal walks for steps of fixed length

Our next goal is to consider the set of allowable steps

Q_{n} := {(1, 0), (0, 1)} ∪ {(i, n − i) : 0 ≤ i ≤ n},

for n ≥ 2. For example, Q_{3} = {(1, 0), (0, 1), (0, 3), (1, 2), (2, 1), (3, 0)}, and Figure 3 shows data for the number of minimal Q_{3}-walks. This array did not previously appear in OEIS, but we have added it as sequence \underline{A292435}.

\begin{matrix}1 \\ 1 \\ 1 \\ 1 \\ 2 \\ 3 \\ 1 \\ 3 \\ 6 \\ 1 \\ 4 \\ 1 \\ 2 \\ 1 \\ 4 \\ 9 \\ 2 \\ 9 \\ 24 \\ 3 \\ 16 \\ 50 \\ 1 \\ 1 \\ 4 \\ 12 \\ 3 \\ 15 \\ 48 \\ 6 \\ 36 \\ 130 \\ 10 \\ 1 \\ 4 \\ 12 \\ 4 \\ 21 \\ 72 \\ 10 \\ 64 \\ 250 \\ 20 \\ 150 \\ 2 \\ 9 \\ 3 \\ 21 \\ 84 \\ 12 \\ 88 \\ 380 \\ 31 \\ 255 \\ 1215 \\ 3 \\ 2 \\ 15 \\ 72 \\ 12 \\ 96 \\ 460 \\ 40 \\ 355 \\ 1830 \\ 101 \\ 1 \\ 9 \\ 48 \\ 10 \\ 88 \\ 460 \\ 44 \\ 420 \\ 2325 \\ 135 \\ 1416 \\ 3 \\ 24 \\ 6 \\ 64 \\ 380 \\ 40 \\ 420 \\ 2520 \\ 155 \\ 1740 \\ 11046 \\ 6 \\ 3 \\ 36 \\ 250 \\ 31 \\ 355 \\ 2325 \\ 155 \\ 1860 \\ 12600 \\ 546 \\ 1 \\ 16 \\ 130 \\ 20 \\ 255 \\ 1830 \\ 135 \\ 1740 \\ 12600 \\ 580 \\ 7882 \\ 4 \\ 50 \\ 10 \\ 150 \\ 1215 \\ 101 \\ 1416 \\ 11046 \\ 546 \\ 7882 \\ 63056 \\ a \\ b \\ 0 \\ 0 \\ 1 \\ 1 \\ 2 \\ 2 \\ 3 \\ 3 \\ 4 \\ 4 \\ 5 \\ 5 \\ 6 \\ 6 \\ 7 \\ 7 \\ 8 \\ 8 \\ 9 \\ 9 \\ 10 \\ 10 \end{matrix}

Figure 3: The number of minimal Q_{3}-walks terminating at each point (a, b) for 0 ≤ a, b ≤ 10.

In Figure 3, we observe an interesting phenomenon. If we fix a value m = 3q + r with 0 ≤ r < 3, and consider all points (a, b) with a + b = m, then the number of minimal Q_{3}-walks terminating at (a, b) is a multiple of \binom{q+r}{r}. For example, when m = 7 = 3 · 2 + 1, the entries along the diagonal (3, 9, 15, 21, 21, 15, 9, 3) are all divisible by \binom{2+1}{1} = 3.

In order to justify this phenomenon in general, we introduce an additional piece of terminology. For Q_{n}, we will call the steps (1, 0) and (0, 1) short steps and the remaining steps of the form (i, n − i) long steps.

Lemma 2. Let a, b ∈ ℕ and write a + b = n · q + r with 0 ≤ r < n. Then any minimal Q_{n}-walk terminating at (a, b) uses exactly q long steps and r short steps. Consequently, d(a, b; Q_{n}) = q + r.

Proof. Let s be a (not necessarily minimal) Q_{n}-walk terminating at (a, b), and suppose s uses q′ long steps and r′ short steps. If r′ ≥ n, then we can replace n of those short steps with one long step, which would result in shorter path. Here, it is worth noting that we do not require these n short steps to appear consecutively in s. We can simply remove them from s and append their vector sum, which is a long step, to the end of the resulting walk. This creates a new walk terminating at (a, b) with fewer steps.

Therefore, if s is a minimal Q_{n}-walk, then r′ < n. By taking the vector sum of every step in s, we see that a + b = n · q′ + r′. Since the quotient and remainder in the division algorithm are unique, we must have q′ = q and r′ = r, meaning s uses q long steps and r short steps.

Let (a, b) ∈ ℕ^{2} and write a + b = q · n + r with 0 ≤ r < n. We can now use Lemma 2 to see why |W(a, b; Q_{n})| is divisible by \binom{q+r}{r}. We can partition W(a, b; Q_{n}) into equivalence classes by declaring s ∼ s′ if (1) s and s′ use the same number of each step from Q_{n} and (2) the relative order of the long steps and the relative order of the short steps in s is the same as that in s′. For example, in Q_{3}, the paths (3, 0), (2, 1), (1, 0), (0, 1), (1, 2), (2, 1) and (1, 0), (3, 0), (0, 1), (2, 1), (1, 2), (2, 1) are equivalent. The paths equivalent to s are determined by choosing r positions out of q + r total steps in which we will place the (ordered list of) short steps.

At this point, however, the combinatorics of enumerating minimal Q_{n}-walks to a fixed point (a, b) is somewhat complicated because the linear algebra problem of determining all ways to write (a, b) as a sum of q long steps and r short steps is difficult to do in generality. Instead, it is easier to exhibit a generating function that will enumerate all such walks.

Theorem 3. For all n ≥ 2, the number of minimal Q_{n}-walks can be computed by the generating function

∑_{(a,b)∈ℕ^{2}} |W(a, b; Q_{n})|x^{a}y^{b} = ∑_{q=0}^{∞} ∑_{r=0}^{n−1} \binom{q + r}{r} (∑_{i=0}^{n} x^{i}y^{n−i})^{q} (x + y)^{r}.  (1)

Proof. For fixed q and r, let σ = n · q + r. Expanding (∑_{i=0}^{n} x^{i}y^{n−i})^{q} encodes all possible ways to make an ordered list of q long steps, and expanding (x + y)^{r} encodes all possible ways to make an ordered list of r short steps. Hence, multiplying these quantities together encodes all possible ways to make an ordered list of q long steps followed by r short steps. Multiplying by \binom{q+r}{r} accounts for all possible ways to shuffle these steps together. Therefore, the summand of the generating function for fixed q and r covers all equivalence classes (as described above) of minimal Q_{n}-walks terminating along the diagonal where a + b = σ.

4 Minimal walks for S = {(1, 0), (0, 1), (u, v)}

In this section, we consider an asymmetric set of allowable steps in S = {(1, 0), (0, 1), (u, v)} for arbitrary integers u, v ≥ 1.

Given a point (a, b) ∈ ℕ^{2}, let m = m(a, b) = min(⌊\frac{a}{u}⌋, ⌊\frac{b}{v}⌋). Concretely, m is the largest integer such that m · u ≤ a and m · v ≤ b; or in other words, m is the largest number of steps one can take in the (u, v)-direction without exceeding the x- or y-coordinate of (a, b).

Theorem 4. Let S = {(1, 0), (0, 1), (u, v)} with u, v ≥ 1, and let (a, b) ∈ ℕ^{2}. A minimal S-walk to the point (a, b) uses exactly m steps in the (u, v)-direction. Consequently,

d(a, b; S) = m + a − m · u + b − m · v,

and

|W(a, b; S)| = \binom{m + a − m · u + b − m · v}{m, a − m · u, b − m · v}.

Proof. First, we will prove that a minimal S-walk uses exactly m steps in the (u, v)-direction. As noted above, any S-walk terminating at (a, b) uses at most m steps in the (u, v)-direction. We claim an S-walk using fewer than m steps in the (u, v)-direction is non-minimal. Indeed, consider an S-walk using m′ steps in the (u, v)-direction, x steps in the (1, 0)-direction, and y steps in the (0, 1)-direction, and assume m′ < m.

Since

a = m′ · u + x ≤ (m − 1) · u + x = m · u + x − u ≤ a + x − u,

it follows that x ≥ u. Similarly, y ≥ v. Since x ≥ u and y ≥ v, we can replace u steps in the (1, 0)-direction and v steps in the (0, 1)-direction with one step in the (u, v)-direction, resulting in a shorter path. Thus, a walk using m′ steps in the (u, v)-direction is non-minimal, and hence a minimal S-walk uses at least m steps in the (u, v)-direction.

Finally, since a minimal S-walk uses m steps in the (u, v)-direction, then it must use a − m · u steps in the (1, 0)-direction and b − m · v steps in the (0, 1)-direction. This immediately implies the stated formulas for the distance and number of minimal S-walks.

Remark 5. In the case that (u, v) = (1, 1), note that m = min(a, b), that m+a−mu+b−mv = a + b − m = max(a, b), and that one of a − mu and b − mv is equal to 0. Thus Theorem 4 generalizes the results in Section 2.

5 Minimal walks for \overline{Q}_{3} = \{(1, 0), (0, 1), (2, 1), (1, 2)\}

Recall that in Section 3, we considered the set of allowable steps Q_{3}. By removing the vectors (3, 0) and (0, 3) from this set, we obtain the set \overline{Q}_{3} = \{(1, 0), (0, 1), (2, 1), (1, 2)\}. The combinatorial data coming from this seemingly simple example did not appear in OEIS [1] and seems interesting in its own right. We have since added this data to OEIS as sequence \underline{A292436}.

Figure 4 shows the number of minimal walks for \overline{Q}_{3}. Here, we have included the lines spanned by the vectors (2, 1) and (1, 2) for reference. We observe that these lines divide the nonnegative quadrant into three regions. In the regions weakly above the line y = 2x and weakly below the line 2y = x, we observe that the number of minimal \overline{Q}_{3}-walks appears to be a binomial coefficient, while the behavior between these two lines appears to be different. Our goal in this section is to explain several patterns in data collected in Figure 4.

\begin{matrix}1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 2 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 1 \\ 1 \\ 4 \\ 9 \\ 1 \\ 3 \\ 6 \\ 10 \\ 15 \\ 21 \\ 28 \\ 1 \\ 2 \\ 9 \\ 2 \\ 9 \\ 24 \\ 1 \\ 4 \\ 10 \\ 20 \\ 35 \\ 1 \\ 3 \\ 1 \\ 9 \\ 36 \\ 3 \\ 16 \\ 50 \\ 1 \\ 5 \\ 15 \\ 1 \\ 4 \\ 3 \\ 24 \\ 3 \\ 24 \\ 100 \\ 4 \\ 25 \\ 90 \\ 1 \\ 1 \\ 5 \\ 6 \\ 1 \\ 16 \\ 100 \\ 6 \\ 50 \\ 225 \\ 5 \\ 36 \\ 1 \\ 6 \\ 10 \\ 4 \\ 50 \\ 4 \\ 50 \\ 300 \\ 10 \\ 90 \\ 441 \\ 1 \\ 7 \\ 15 \\ 10 \\ 1 \\ 25 \\ 225 \\ 10 \\ 120 \\ 735 \\ 15 \\ 1 \\ 8 \\ 21 \\ 20 \\ 5 \\ 90 \\ 5 \\ 90 \\ 735 \\ 20 \\ 245 \\ 1 \\ 9 \\ 28 \\ 35 \\ 15 \\ 1 \\ 36 \\ 441 \\ 15 \\ 245 \\ 1960 \\ a \\ b \\ 0 \\ 0 \\ 1 \\ 1 \\ 2 \\ 2 \\ 3 \\ 3 \\ 4 \\ 4 \\ 5 \\ 5 \\ 6 \\ 6 \\ 7 \\ 7 \\ 8 \\ 8 \\ 9 \\ 9 \\ 10 \\ 10 \end{matrix}

Figure 4: The number of minimal \overline{Q}_{3}-walks terminating at each point (a, b) for 0 ≤ a, b ≤ 10.

We begin by establishing some notation that will be used throughout the proofs in this section. Given a point (a, b) ∈ ℕ^{2}, consider a minimal \overline{Q}_{3}-walk, s, terminating at (a, b). Let x, y, z, and w respectively denote the number of (1, 0)-, (0, 1)-, (2, 1)-, and (1, 2)-steps in s. Thus

a = x + 2z + w and b = y + z + 2w.  (2)

As in Section 3, we will refer to the steps (2, 1) and (1, 2) in \overline{Q}_{3} as long steps and the steps (1, 0) and (0, 1) as short steps.

Our first goal is to explain the combinatorial data observed in the outer regions where a ≥ 2b or b ≥ 2a.

Theorem 6. Let (a, b) ∈ ℕ^{2} with a ≥ 2b. A minimal \overline{Q}_{3}-walk terminating at (a, b) does not use any steps in the (0, 1)-direction or in the (1, 2)-direction. Consequently,

d(a, b; \overline{Q}_{3}) = a − b

and

|W(a, b; \overline{Q}_{3})| = \binom{a − b}{b}.

Proof. Consider a minimal \overline{Q}_{3}-walk, s, terminating at the point (a, b). Let x, y, z, and w be as defined above. Our first goal is to show y = 0 and w = 0.

Since a ≥ 2b, it follows from Eq. (2) that x ≥ 2y + 3w. Therefore, if y ≥ 1, then x ≥ 2. So if s uses a (0, 1)-step, then it uses (at least) two (1, 0)-steps. But a (0, 1)-step and two (1, 0)-steps can be replaced with a (2, 1)-step, which would give a shorter path. Thus y = 0.

Similarly, if w ≥ 1, then x ≥ 3. So if s uses a (1, 2)-step, it uses at least three (1, 0)-steps. But (1, 2)+3(1, 0) = (4, 2) = 2(2, 1), so these four steps can be replaced with two (2, 1)-steps, which would give a shorter path. Thus w = 0 as well.

Since y = 0 and w = 0, Eq. (2) reduces to

a = x + 2z and b = z,

which is equivalent to x = a − 2b (which is nonnegative since a ≥ 2b) and z = b. Since x + z is the total number of steps in s, it follows that d(a, b; \overline{Q}_{3}) = a − b. Finally, to determine a path to the point (a, b), we must use a − b total steps, b of which go in the direction (2, 1) and a − 2b of which go in the direction (1, 0). There are \binom{a−b}{b} ways to determine such a path. This completes the proof.

Since \overline{Q}_{3} is symmetric, the following corollary immediately handles the case that b ≥ 2a.

Corollary 7. Let (a, b) ∈ ℕ^{2} with b ≥ 2a. A minimal \overline{Q}_{3}-walk terminating at (a, b) does not use any steps in the (1, 0)-direction or in the (2, 1)-direction. Consequently, d(a, b; \overline{Q}_{3}) = b−a and |W(a, b; \overline{Q}_{3})| = \binom{b−a}{a}.

Now we turn our attention to the case that (a, b) lies in the central region of Figure 4.

Lemma 8. Let (a, b) ∈ ℕ^{2} with \frac{1}{2}b ≤ a ≤ 2b. A minimal \overline{Q}_{3}-walk terminating at (a, b) uses at most two short steps.

Proof. As before, consider a minimal \overline{Q}_{3}-walk, s, terminating at the point (a, b). Let x, y, z, and w be as defined above. Assume by way of contradiction that s uses at least three short steps, or equivalently that x + y ≥ 3.

If x ≥ 2 and y ≥ 1 (or if x ≥ 1 and y ≥ 2), then s can be shortened by replacing three short steps with a (2, 1)-step (respectively, with a (1, 2)-step). So we need only consider the case that x ≥ 3 and y = 0. By symmetry, this will cover the case that x = 0 and y ≥ 3.

Since a ≤ 2b, it follows from Eq. (2) that x ≤ 2y + 3w. Since y = 0 and x ≥ 3, it follows that w ≥ 1. Thus s uses at least three (1, 0)-steps and one (1, 2)-step, which can be shortened by replacing 3(1, 0) + (1, 2) = (4, 2) with two (2, 1)-steps. This contradicts our assumption that s is minimal.

Theorem 9. Let (a, b) ∈ ℕ^{2} with \frac{1}{2}b ≤ a ≤ 2b, and write a + b = 3q + r with 0 ≤ r ≤ 2. Then

d(a, b; \overline{Q}_{3}) = q + r

and

|W(a, b; \overline{Q}_{3})| = \binom{q + r}{r}\binom{q + r}{a − q}.

Proof. As before, consider a minimal \overline{Q}_{3}-walk, s, terminating at the point (a, b). Let x, y, z, and w be as defined above. By Eq. (2), a + b = x + y + 3(z + w). By Lemma 8, x + y < 3, and hence by uniqueness of the quotient and remainder in the division algorithm, it must be the case that x + y = r and z + w = q. But x + y + z + w is the total number of steps used in s, and hence d(a, b; \overline{Q}_{3}) = q + r. In particular, r counts the number of short steps used in a minimal path.

Now we turn our attention to counting the number of minimal \overline{Q}_{3}-walks terminating at (a, b). Let s be such a walk. We know s uses r short steps. Define a new \overline{Q}_{3}-walk ŝ as follows: replace each (1, 0)-step in s with a (2, 1)-step and replace each (0, 1)-step in s with a (1, 2)-step. Note that ŝ is a \overline{Q}_{3}-walk that only uses long steps. Moreover, ŝ terminates at the point (a + r, b + r) as each replacement increases the vector sum by (1, 1).

Now let ŵ and ẑ respectively denote the number of (2, 1)- and (1, 2)-steps in ŝ. Applying Eq. (2) to ŝ gives rise to the system of equations

2ẑ + ŵ = a + r
ẑ + 2ŵ = b + r.

The coefficient matrix [\begin{matrix}2 & 1 \\ 1 & 2 \end{matrix}] is invertible, so this system has a unique solution. We can

easily verify that

ẑ = a − q
ŵ = b − q

is a solution, which can also be derived by inverting the coefficient matrix and making use of the fact that a + b = 3q + r.

Moreover, a − q and b − q are both nonnegative because \frac{1}{2}b ≤ a ≤ 2b. Indeed, 3q + r = a + b ≤ a + 2a, and hence 3(a − q) ≥ r ≥ 0. The same logic shows 3(b − q) ≥ r ≥ 0.

Therefore, the \overline{Q}_{3}-minimal walks terminating at (a, b) can be constructed as follows. Start with a \overline{Q}_{3}-walk using a − q steps in the direction (2, 1) and b − q steps in the direction (1, 2). There are \binom{a−q+b−q}{a−q} = \binom{q+r}{a−q} such walks. Next, choose r of those steps to transform into short steps. If the chosen step is a (2, 1)-step, turn it into a (1, 0) step; if it is a (1, 2)-step, turn it into a (0, 1)-step. There are \binom{q+r}{r} ways to make these choices. The resulting path terminates at the point (a, b) and has length q + r = d(a, b; \overline{Q}_{3}). Thus |W(a, b; \overline{Q}_{3})| = \binom{q+r}{r}\binom{q+r}{a−q}, as desired.

6 Open problems

6.1 Minimal walks for general S = {(1, 0), (0, 1), (u, v), (v, u)}.

Based on the results in Section 5, it seems natural to explore the more general case that our allowable steps are S = {(1, 0), (0, 1), (u, v), (v, u)} for arbitrary u and v such that u > v ≥ 1.

In this case, the distances seem more complicated than they were in any of our previous examples. The reason for this is that a point’s distance from the origin is inherently dependent on its position relative to the ℕ-span of {(u, v), (v, u)}. In particular, that distance to point (a, b) can be determined greedily by finding a nearest point in the ℕ-span of {(u, v), (v, u)} that lies weakly south and west of (a, b) and filling in the rest of the walk

\begin{matrix}0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 13 \\ 14 \\ 15 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 13 \\ 14 \\ 15 \\ 16 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 13 \\ 14 \\ 15 \\ 16 \\ 17 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 5 \\ 6 \\ 7 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 13 \\ 6 \\ 7 \\ 8 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 7 \\ 8 \\ 9 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 8 \\ 9 \\ 10 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 9 \\ 10 \\ 11 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 3 \\ 10 \\ 11 \\ 12 \\ 6 \\ 7 \\ 8 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 4 \\ 11 \\ 12 \\ 13 \\ 7 \\ 8 \\ 9 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 3 \\ 4 \\ 5 \\ 12 \\ 13 \\ 14 \\ 8 \\ 9 \\ 10 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 4 \\ 5 \\ 6 \\ 13 \\ 14 \\ 15 \\ 9 \\ 10 \\ 11 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 14 \\ 15 \\ 16 \\ 10 \\ 11 \\ 12 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 15 \\ 16 \\ 17 \\ 11 \\ 12 \\ 13 \\ 7 \\ 8 \\ 9 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ a \\ b \\ 0 \\ 0 \\ 1 \\ 1 \\ 2 \\ 2 \\ 3 \\ 3 \\ 4 \\ 4 \\ 5 \\ 5 \\ 6 \\ 6 \\ 7 \\ 7 \\ 8 \\ 8 \\ 9 \\ 9 \\ 10 \\ 10 \\ 11 \\ 11 \\ 12 \\ 12 \\ 13 \\ 13 \\ 14 \\ 14 \\ 15 \\ 15 \end{matrix}

Figure 5: The distance d(a, b; {(1, 0), (0, 1), (3, 5), (5, 3)}) for 0 ≤ a, b ≤ 15. with short steps. This means the distance changes, often dramatically, depending on a point’s position in a fundamental parallelogram spanned by (u, v) and (v, u). For example, consider the case that S = {(1, 0), (0, 1), (3, 5), (5, 3)}. The distances from the origin to nearby points (a, b) are displayed in Figure 5.

Problem 10. Let S = {(1, 0), (0, 1), (u, v), (v, u)} with u > v ≥ 1 arbitrary. Determine d(a, b; S) and |W(a, b; S)|.

6.2 Catalan generalizations

Based on the wealth of beautiful combinatorics arising from Catalan and Motzkin paths, the following question is very natural.

Problem 11. Let a ≥ b and let S be a set of allowable steps. How many minimal S-walks terminating at (a, b) stay weakly below the line y = x?

For brevity, let us say that an S-Catalan walk is a minimal S-walk that stays weakly below the line y = x. For integers a, b with a ≥ b, we will write C(a, b; S) to denote the set of all S-Catalan walks terminating at (a, b).

Consider the set S_{n} = {(i, n − i) : 0 ≤ i ≤ n}; i.e., the nonnegative integer vectors with coordinate sum n. We can explore C(a, b; S_{n}) for several values of n.

For S_{1} = {(1, 0), (0, 1)} the number of S_{1}-Catalan walks terminating at (a, a) is the a-th Catalan number, which appear in OEIS as sequence \underline{A000108}. More generally, the number of walks terminating at (a, b) is \frac{a−b+1}{a+b+1} \binom{a+b+1}{a+1}, which is OEIS sequence \underline{A009766}. Krattenthaler [2, Corollary 10.3.2] gives a proof of this fact.

\begin{matrix}1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 2 \\ 0 \\ 0 \\ 2 \\ 0 \\ 0 \\ 0 \\ 2 \\ 0 \\ 0 \\ 6 \\ 0 \\ 1 \\ 0 \\ 0 \\ 7 \\ 0 \\ 0 \\ 13 \\ 0 \\ 0 \\ 5 \\ 0 \\ 0 \\ 18 \\ 0 \\ 0 \\ 0 \\ 3 \\ 0 \\ 0 \\ 21 \\ 0 \\ 0 \\ 52 \\ 0 \\ 1 \\ 0 \\ 0 \\ 16 \\ 0 \\ 0 \\ 68 \\ 0 \\ 0 \\ 120 \\ 0 \\ 0 \\ 9 \\ 0 \\ 0 \\ 64 \\ 0 \\ 0 \\ 184 \\ 0 \\ 4 \\ 0 \\ 0 \\ 50 \\ 0 \\ 0 \\ 234 \\ 1 \\ 0 \\ 0 \\ 30 \\ 0 \\ 0 \\ 212 \\ 0 \\ 0 \\ 14 \\ 0 \\ 0 \\ 158 \\ 0 \\ 5 \\ 0 \\ 0 \\ 99 \\ 1 \\ 0 \\ 0 \\ 50 \\ 0 \\ 0 \\ 20 \\ 0 \\ 6 \\ 1 \\ a \\ b \\ 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 13 \\ 14 \\ 15 \\ 16 \\ 17 \\ 18 \\ 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \end{matrix}

Figure 6: Number of S_{3}-Catalan paths terminating at points (a, b) with 0 ≤ a + b ≤ 18.

For S_{2} = {(2, 0), (1, 1), (0, 2)}, the number of S_{2}-Catalan walks terminating at (a, a) is the a-th Motzkin number, which is found in sequence \underline{A001006}. Indeed, the map sending (2, 0) ↦ (1, 1), (1, 1) ↦ (1, 0), and (0, 2) ↦ (1, −1) gives a bijection to classical Motzkin paths comprised of steps {(1, 1), (1, 0), (1, −1)} that start at (0, 0), terminate at (a, 0), and stay above the line y = 0.

As a next step we can consider S_{3} = {(3, 0), (2, 1), (1, 2), (0, 3)}. Figure 6 shows the number of S_{3}-Catalan paths terminating at points (a, b) with a ≥ b and a + b ≤ 18.

The sequence of nonzero numbers along the line y = x, which continues as 1, 2, 13, 120, 1288, 15046, …, did not appear in OEIS. We have added it as sequence \underline{A292437}. Problem 12. Determine the generating function for

∑_{a≥b≥0} |C(a, b; S_{3})|x^{a}y^{b} or  ∑_{a=0}^{∞} |C(a, a; S_{3})|t^{a}.

7 Acknowledgments

We gratefully acknowledge support from NSF grant DMS-1600048. We also thank Naomi Cameron, Tom Edgar, Lara Pudwell, and Jennifer Quinn for providing helpful insights and suggestions over the course of this project.

References

[1] OEIS Foundation Inc. (2016). The On-Line Encyclopedia of Integer Sequences, http://

   oeis.org.

[2] Christian Krattenthaler, Lattice path enumeration. In Handbook of Enumerative Combinatorics, Discrete Math. Appl. (Boca Raton), pp. 589–678. CRC Press, 2015.

[3] W. A. Stein et al., Sage Mathematics Software (Version 8.0). The Sage Development

   Team, 2017. http://www.sagemath.org.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: lattice path enumeration, generating function, Catalan number, Motzkin number.

(Concerned with sequences \underline{A000108}, \underline{A001006}, \underline{A007318}, \underline{A009766}, \underline{A292435}, \underline{A292436}, and \underline{A292437}.)

Received December 9 2017; revised version received March 27 2018. Published in Journal of Integer Sequences, March 28 2018.

Return to Journal of Integer Sequences home page.