Enumerating Lattice Walks with Prescribed Steps

Nestor Iwanojko, Steven Klee, Bryn Lasher, and Elena Volpi Department of Mathematics Seattle University 901 12th Avenue Seattle, WA 98122 USA

                   iwanojkonest@seattleu.edu
                      klees@seattleu.edu
                     lasherb@seattleu.edu
                      volpie@seattleu.edu

Abstract Given a finite set of integer vectors, S, we consider the set of all lattice walks whose allowable step directions come from S. We partition the set of all such walks according to their length (the number of steps used) and terminal point. In several cases, we are able to give explicit combinatorial formulas that count the number of such paths. We conclude with a Frobenius-type problem for lattice walks with prescribed steps.

1 Introduction

Let S ⊆ ℕ^{d} be a finite set of vectors whose entries are nonnegative integers. For most of this paper, we will focus on vectors S ⊆ ℕ^{2}. An S-walk is an ordered sequence of steps, s = s_{1}, s_{2}, …, s_{k}, with s_{i} ∈ S for all i. We visualize s as a walk in the plane, beginning at the origin and terminating at the point s_{1} + s_{2} + ⋯ + s_{k}. We say the number of steps in the walk is its length.

The canonical example for this problem comes from taking S = {(1, 0), (0, 1)}. In this case, every S-walk from (0, 0) to a point (a, b) has length a + b, and the number of such walks is \binom{a+b}{b}. Mansour [4] explored a similar problem, counting paths comprised of a fixed set of steps S = {(i, 1) : i ≥ 0} that were forced to stay in the nonnegative orthant {(a, b) ∈ ℤ^{2} : 0 ≤ a ≤ b} and terminate at some point (i, n) with 0 ≤ i ≤ n. Mansour [5] and Mansour and Deng [2] explored variations on this problem.

For more general sets of vectors, it may be possible to realize walks of several different lengths. For example, if S = {(1, 0), (0, 1), (1, 1)}, the S-walks

s = (1, 0), (1, 0), (1, 1), (0, 1), (1, 0)

and

s′ = (1, 1), (1, 0), (1, 1), (1, 0)

are illustrated in Figure 1. Both walks terminate at (a, b) = (4, 2), but s has length 5, while s′ has length 4.

Figure 1: An S-walk of length 5 (left) and an S-walk of length 4 (right), both terminating at (a, b) = (4, 2) when S = {(1, 0), (0, 1), (1, 1)}.

Our goal is to enumerate the S-walks of a given length for different sets of allowable steps. For a given set of vectors, S and a terminating point (a, b), we use d(a, b; S) to denote the distance from the origin to (a, b) using steps in S. This is the length of the shortest S-walk terminating at (a, b). For an arbitrary set S, it is possible that certain points (a, b) cannot be reached using steps in S. We often assume (1, 0) and (0, 1) belong to S to eliminate this concern.

Evoniuk et al. [3] studied S-walks of minimal length for various sets S ⊆ ℕ^{2}. Our first goal here is to build upon that work, enumerating S-walks according to an extra parameter, ℓ, that counts the number of long steps used in the walk — that is, steps other than (1, 0) and (0, 1). When ℓ = 0, we reduce to the case that S = {(1, 0), (0, 1)}. When ℓ is maximal we enumerate walks of minimal length.

One difference in our approach from that of Evoniuk et al. [3] is that Evoniuk et al. approached the problem of enumerating minimal-length S-walks by first determining d(a, b; S) and then using the value of d(a, b; S) in determining |W(a, b; S)|. By introducing the parameter ℓ, we are able to compute |W(a, b; S, ℓ)| directly, and then determine d(a, b; S) as a consequence by finding the largest value of ℓ for which |W(a, b; S, ℓ)| is nonzero.

We explore this problem for S = {(1, 0), (0, 1), (1, 1)} in Section 2, for sets of the form S = {(1, 0), (0, 1), (u, u + 1), (u + 1, u)} with u ≥ 1 in Section 3, and for sets of the form Q_{n} := {(1, 0), (0, 1)} ∪ {(n, n − i) : 0 ≤ i ≤ n} with n ≥ 2 in Section 4.

In Section 5, we explore a question in the spirit of the Frobenius problem. Let m = max{s_{1} + s_{2} : (s_{1}, s_{2}) ∈ S}. For any (a, b) ∈ ℕ^{2}, there is a simple greedy bound of d(a, b; S) ≥ ⌈\frac{a+b}{m}⌉. For which points (a, b) is equality achieved? For the sets S under consideration, we show d(a, b; S) depends only on a + b. In this case, problem reduces to a one-dimensional problem of writing a + b as a sum of elements from a fixed set, using the minimum number of summands as prescribed by a greedy bound. In certain cases, we show that once a + b is sufficiently large, every number can be expressed in such a way, which is analogous to the classical Frobenius problem. We go on to give a characterization of sets S ⊆ ℕ that have this greedy Frobenius property.

2 Walks for S = {(1, 0), (0, 1), (1, 1)}

We begin by considering S = {(1, 0), (0, 1), (1, 1)} to help establish some notation and ideas that will be useful in later sections. We say (1, 0) and (0, 1) are short steps, and (1, 1) is a long step. Here and in subsequent sections, we will enumerate S-walks according to the number of long steps they use. For us, the long steps will always have fixed coordinate sum, so stipulating the number of long steps used is equivalent to fixing the length of the path.

We use W(a, b; S, ℓ) to denote the set of S-walks terminating at (a, b) that use exactly ℓ long steps, and |W(a, b; S, ℓ)| to denote the cardinality of that set. When enumerating minimal-length lattice walks, we suppress the ℓ from this notation, using |W(a, b; S)| to denote the number of minimal-length lattice walks terminating at (a, b). This is done to be consistent with the notation used by Evoniuk et al. [3].

Theorem 1. Let S = {(1, 0), (0, 1), (1, 1)}. For all (a, b) ∈ ℕ^{2} we have

|W(a, b; S, ℓ)| = \binom{a + b − ℓ}{a − ℓ, b − ℓ, ℓ}.  (1)

Proof. Let s be an S-walk that uses ℓ long steps and terminates at (a, b). Those long steps contribute ℓ(1, 1) = (ℓ, ℓ) to the overall sum of the vectors in s. We know s terminates at (a, b) and (a, b) − (ℓ, ℓ) = (a − ℓ, b − ℓ), so s must use a − ℓ steps in the (1, 0) direction and b − ℓ steps in the (0, 1) direction. It follows that s has length (a − ℓ) + (b − ℓ) + ℓ = a + b − ℓ.

The result follows, because any S-walk with ℓ long steps can be viewed as an ordered sequence of a + b − ℓ steps into which we must place a − ℓ steps in the (1, 0) direction, b − ℓ steps in the (0, 1) direction, and ℓ steps in the (1, 1) direction.

It follows from Theorem 1 that |W (a, b; S, ℓ)| is nonzero if and only if 0 ≤ ℓ ≤ min(a, b). Otherwise, one of a−ℓ, b−ℓ, or ℓ is negative, making \binom{a+b−ℓ}{a−ℓ,b−ℓ,ℓ} = 0. When ℓ = 0, we recover |W (a, b; S, 0)| = \binom{a+b}{min(a,b)} = \binom{a+b}{a}, which counts the number of walks using only short steps. When ℓ = min(a, b), we get a+b−ℓ = max(a, b) and |W (a, b; S, min(a, b))| = \binom{max(a,b)}{min(a,b)}. This recovers the following result of Evoniuk et al. [3]:

Corollary 2. ([3, Theorem 1]) Let S = {(1, 0), (0, 1), (1, 1)} and let (a, b) ∈ ℕ^{2}. Then d(a, b; S) = max(a, b) and

|W(a, b; S)| = \binom{max(a, b)}{min(a, b)}.

3 Walks for S = {(1, 0), (0, 1), (u, u + 1), (u + 1, u)}

Let u, v ∈ ℕ with u, v ≥ 1. Evoniuk et al. [3, Problem 10] left open the question of understanding d(a, b; S) and W(a, b; S) for S = {(1, 0), (0, 1), (u, v), (v, u)}. Here, we give a partial answer to this question in the special case that v = u + 1. As before we say (0, 1) and (1, 0) are short steps, and (u, u + 1) and (u + 1, u) are long steps.

We begin with a motivating example in the case that u = 2. Figure 2 shows the values of d(a, b; S) for points with 0 ≤ a, b ≤ 11 when S = {(1, 0), (0, 1), (2, 3), (3, 2)}. The dashed lines are spanned by (2, 3) and (3, 2). The data presented here were gathered using a simple greedy algorithm in Sage [8].

Consider the values of d(a, b; S) as (a, b) ranges along the diagonal where a + b is fixed. For example, when a + b = 11, those distances are (11, 11, 7, 7, 3, 3, 3, 3, 7, 7, 11, 11). Here we observe three properties of these distances. First, d(a, b; S) = d(b, a; S) because the vectors in S are symmetric about the line y = x. Thus we need only consider distances d(a, b; S) when a ≤ b; or equivalently, when a ≤ \frac{a+b}{2}. Second, aside from the run of consecutive threes at the center of this list, all other values (in this case, 11 and 7) appear in blocks of size u = 2. Third, the distinct values in this list (11, 7, and 3) form an arithmetic progression whose common difference is 2u = 4 and whose initial value is a + b = 11. Corollary 4 below shows this pattern continues for all u ≥ 1. We begin with a more general result.

Theorem 3. Let u ≥ 1 and S = {(1, 0), (0, 1), (u, u + 1), (u + 1, u)}. For any (a, b) ∈ ℕ^{2}, the number of S-walks terminating at (a, b) that use ℓ long steps is

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

Proof. Consider an S-walk using ℓ long steps. Of those, suppose i steps are in the direction (u, u + 1) and ℓ − i are in the direction (u + 1, u). The contribution of long steps in the walk is

i(u, u + 1) + (ℓ − i)(u + 1, u) = (uℓ + ℓ − i, uℓ + i).

Thus, in order to reach (a, b), the walk must use a − uℓ − ℓ + i steps in the (1, 0) direction and b − uℓ − i steps in the (0, 1) direction. The total length of such a walk is

(a − uℓ − ℓ + i) + (b − uℓ − i) + ℓ = a + b − 2uℓ.

The set of all such walks can be described by first choosing ℓ positions out of a + b − 2uℓ to be long steps, then choosing which i of those ℓ long steps will be in the direction (u, u + 1),

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

Figure 2: Distances d(a, b; S) for 0 ≤ a, b ≤ 11 when S = {(1, 0), (0, 1), (2, 3), (3, 2)}.

and finally choosing which of the remaining a + b − 2uℓ − ℓ steps will be in the direction (1, 0). Therefore,

|W(a, b; S, ℓ)| = ∑_{i=0}^{ℓ} \binom{a + b − 2uℓ}{ℓ}\binom{ℓ}{i}\binom{a + b − 2uℓ − ℓ}{a − uℓ − ℓ + i}

= \binom{a + b − 2uℓ}{ℓ} ∑_{k=0}^{ℓ} \binom{ℓ}{k}\binom{a + b − 2uℓ − ℓ}{a − uℓ − k}

= \binom{a + b − 2uℓ}{ℓ}\binom{a + b − 2uℓ}{a − uℓ}.

In the second line above we reindex the sum, setting k = ℓ − i. In the third line, we use the Vandermonde identity (see [1, Example 4.4]) to collapse the summation.

Now we will use Theorem 3 to find the maximum number of long steps that can be used in a walk terminating at a point (a, b), which translates into the length of the shortest walk terminating at (a, b).

Corollary 4. Let u ≥ 1 and S = {(1, 0), (0, 1), (u, u + 1), (u + 1, u)}. Let (a, b) ∈ ℕ^{2} with a ≤ b and write a + b = (2u + 1)q + r, with 0 ≤ r ≤ 2u. Then

d(a, b; S) = \begin{cases}a + b − 2u ⌊\frac{a}{u}⌋ , & if a < uq; \\ a + b − 2uq, & if uq ≤ a ≤ \frac{a+b}{2}. \end{cases}  (3)

Proof. By Theorem 3, it suffices to find the largest value of ℓ for which both \binom{a+b−2uℓ}{ℓ} and \binom{a+b−2uℓ}{a−uℓ} are nonzero. It follows from the proof of Theorem 3 that d(a, b; S) = a + b − 2uℓ for this maximal value of ℓ.

Note that \binom{a+b−2uℓ}{ℓ} is nonzero if and only if a + b − 2uℓ ≥ ℓ, which is equivalent to a + b ≥ (2u + 1)ℓ. Similarly, \binom{a+b−2uℓ}{a−uℓ} is nonzero if and only if a + b − 2uℓ ≥ max(a, b) − uℓ. This is equivalent to requiring a ≥ uℓ, because we assumed a ≤ b. Thus, we need to find the largest value of ℓ for which a + b ≥ (2u + 1)ℓ and a ≥ uℓ. We claim that when a < uq, the largest such value is ℓ = ⌊\frac{a}{u}⌋, and when uq ≤ a ≤ \frac{a+b}{2}, the largest such value is ℓ = q.

First we consider the case that a < uq. The requirement that a ≥ uℓ is equivalent to ℓ ≤ ⌊\frac{a}{u}⌋. We claim that a + b ≥ (2u + 1)ℓ when ℓ = ⌊\frac{a}{u}⌋. Our assumption that a < uq tells us q > \frac{a}{u} ≥ ℓ. Therefore,

a + b = (2u + 1)q + r > (2u + 1)ℓ + r ≥ (2u + 1)ℓ,

as desired.

Next, we consider the case that uq ≤ a ≤ \frac{a+b}{2}. Note that (2u+1)ℓ ≤ a+b = (2u+1)q +r if and only if ℓ ≤ q, because r ≤ 2u. Moreover, when ℓ = q, the requirement that a ≥ uℓ is immediately satisfied because we assumed uℓ = uq ≤ a.

4 Walks with steps of fixed length

Our next goal is to study walks coming from vectors with a fixed coordinate sum. Here and throughout the remainder of the paper, we adopt notation of Evoniuk et al. [3], using Q_{n} to denote the set

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

As before, we say steps (1, 0) and (0, 1) are short steps and steps of the form (i, n − i) are long steps. Our first goal is to enumerate Q_{n}-walks using exactly ℓ long steps. We require some additional notation. For nonnegative integers s, m, and p, we define κ(s, p, m) to be the number of ways to write s = a_{1} + a_{1} + ⋯ + a_{p} such that a_{i} ∈ ℕ and a_{i} ≤ m for all i. In other words, κ(s, p, m) is the number of weak compositions of s into p parts, each of which has a maximum value of m.

For example, the table in Figure 3 demonstrates the values of κ(s, 2, 2).

s  valid sums  κ(s, 2, 2)
0  0 + 0  1
1  1 + 0, 0 + 1  2
2 0 + 2, 1 + 1, 2 + 0  3
3  1 + 2, 2 + 1  2
4  2 + 2  1

Figure 3: Values for κ(s, 2, 2)

The table in Figure 4 shows the number of walks terminating at the point (a, b) using ℓ = 2 long steps from Q_{2}. Once again, the data here was generated using Sage [8].

\begin{matrix}0 \\ 0 \\ 1 \\ 1 \\ 2 \\ 2 \\ 3 \\ 3 \\ 4 \\ 4 \\ 5 \\ 5 \\ 6 \\ 6 \\ a \\ b \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 3 \\ 6 \\ 0 \\ 0 \\ 0 \\ 2 \\ 9 \\ 24 \\ 50 \\ 0 \\ 0 \\ 3 \\ 15 \\ 48 \\ 120 \\ 255 \\ 0 \\ 2 \\ 15 \\ 60 \\ 180 \\ 450 \\ 987 \\ 1 \\ 9 \\ 48 \\ 180 \\ 540 \\ 1386 \\ 3164 \\ 3 \\ 24 \\ 120 \\ 450 \\ 1386 \\ 3696 \\ 8820 \\ 6 \\ 50 \\ 255 \\ 987 \\ 3164 \\ 8820 \\ 22050 \end{matrix}

Figure 4: Values of |W(a, b; Q_{2}, 2)| for 0 ≤ a, b ≤ 6.

In Figure 4 we observe the values of κ(s, 2, 2) along the first nonzero diagonal where a + b = 4. Moreover, the entries |W(a, b; Q_{2}, 2)| appear to be divisible by \binom{a+b−2}{2}, with equality when b = 0. We begin by showing this pattern continues to hold for all values of n and ℓ.

Theorem 5. For any n ≥ 2 and a, b, ℓ ∈ ℕ,

|W(a, b; Q_{n}, ℓ)| = \binom{a + b − (n − 1)ℓ}{ℓ} ∑_{s=0}^{nℓ} κ(s, ℓ, n)\binom{a + b − nℓ}{a − s}.  (4)

Proof. First we note that a Q_{n}-walk using ℓ long steps has length a + b − (n − 1)ℓ. Indeed, if we were to rewrite each long step as a sum of n short steps, the resulting path would have length a + b. Each replacement increases the length of the path by (n − 1) steps.

If s ∈ W(a, b; Q_{n}, ℓ), we can consider the sum of the ℓ long steps in s. We will partition W(a, b; Q_{n}, ℓ) based on the sum of the long steps in each path — the sum of long steps leads to a point (s, nℓ − s) for some 0 ≤ s ≤ nℓ.

How many walks have a sum of long steps that leads to (s, nℓ − s)? Each walk in W(a, b; Q_{n}, ℓ) has length a + b − (n − 1)ℓ, so there are \binom{a+b−(n−1)ℓ}{ℓ} ways to choose the positions of the long steps. The number of ways to write (s, nℓ − s) as a sum of ℓ vectors from Q_{n} is equal to the number of ways of writing

(a_{1}, n − a_{1}) + (a_{2}, n − a_{2}) + ⋯ + (a_{ℓ}, n − a_{ℓ}) = (s, nℓ − s),

where 0 ≤ a_{i} ≤ n for all i. However, if ∑_{i=1}^{ℓ} a_{i} = s, then ∑_{i=1}^{ℓ}(n−a_{i}) = nℓ−s automatically. Therefore, the number of ways to write (s, nℓ − s) as a sum of ℓ vectors from Q_{n} is exactly κ(s, ℓ, n).

Finally, if the long steps in a Q_{n}-walk terminating at (a, b) lead to the point (s, nℓ − s), then the short steps must lead to the point (a − s, b − nℓ + s). There are a + b − nℓ short steps, and we must choose a − s of them to be in the (1, 0)-direction.

Putting all of this together, the number of walks in W(a, b; Q_{n}, ℓ) whose long steps lead to the point (s, nℓ − s) is

\binom{a + b − (n − 1)ℓ}{ℓ}κ(s, ℓ, n)\binom{a + b − nℓ}{a − s}.

Summing over all values 0 ≤ s ≤ nℓ gives the desired result.

In general, the formula in Eq. (4) can be quite complicated; however, we exhibit some cases where it can be simplified.

Corollary 6. For any a, b, ℓ ∈ ℕ, the number of Q_{2}-walks terminating at (a, b) using ℓ long steps is

|W(a, b; Q_{2}, ℓ)| = \binom{a + b − ℓ}{ℓ} ∑_{i=0}^{ℓ} \binom{ℓ}{i}\binom{a + b − ℓ − i}{a − 2i}.  (5)

Proof. First, we note that

κ(s, ℓ, 2) = ∑_{i≥0} \binom{ℓ}{i, s − 2i, ℓ − s + i} = ∑_{i≥0} \binom{ℓ}{i}\binom{ℓ − i}{s − 2i}.

This is because κ(s, ℓ, 2) counts the number of ways to express s as a sum of ℓ numbers, each of which belongs to {0, 1, 2}. If such a sum uses i summands equal to 2, then it must use s − 2i summands equal to 1 and ℓ − s + i summands equal to 0. Thus, the number of sums using i summands equal to 2 is \binom{ℓ}{i,s−2i,ℓ−s+i} = \binom{ℓ}{i}\binom{ℓ−i}{s−2i}.

Therefore, by Eq. (4),

|W(a, b; Q_{2}, ℓ)| = \binom{a + b − ℓ}{ℓ} ∑_{s=0}^{2ℓ} ∑_{i≥0} \binom{ℓ}{i}\binom{ℓ − i}{s − 2i}\binom{a + b − 2ℓ}{a − s}.  (6)

The terms of the inner summation in Eq. (6) are nonzero only when i ≥ 0, i ≤ \frac{s}{2}, and i ≥ s − ℓ. Changing the order of summations allows us to write

|W(a, b; Q_{2}, ℓ)| = \binom{a + b − ℓ}{ℓ} ∑_{i=0}^{ℓ} \binom{ℓ}{i} ∑_{s=2i}^{i+ℓ} \binom{ℓ − i}{s − 2i}\binom{a + b − 2ℓ}{a − s}

= \binom{a + b − ℓ}{ℓ} ∑_{i=0}^{ℓ} \binom{ℓ}{i} ∑_{k=0}^{ℓ−i} \binom{ℓ − i}{k}\binom{a + b − 2ℓ}{a − 2i − k}

= \binom{a + b − ℓ}{ℓ} ∑_{i=0}^{ℓ} \binom{ℓ}{i}\binom{a + b − ℓ − i}{a − 2i}.

Here, the second line comes from reindexing with k = s − 2i. The third line follows from the Vandermonde identity.

Corollary 7. For any a, b, ℓ ∈ ℕ, the number of Q_{3}-walks terminating at (a, b) using ℓ long steps is

|W(a, b; Q_{3}, ℓ)| = \binom{a + b − 2ℓ}{ℓ} ∑_{i=0}^{ℓ} \binom{ℓ}{i}\binom{a + b − 2ℓ}{a − 2i}.  (7)

Proof. Note that κ(s, ℓ, 3) is the coefficient on x^{s} in the expansion of (1 + x + x^{2} + x^{3})^{ℓ}. We can rewrite (1 + x + x^{2} + x^{3})^{ℓ} = (1 + x)^{ℓ}(1 + x^{2})^{ℓ}. This tells us κ(s, ℓ, 3) = ∑_{i+2j=s} \binom{ℓ}{i}\binom{ℓ}{j}, where the sum is over nonnegative integers i, j such that i + 2j = s. Therefore,

∑_{s=0}^{3ℓ} κ(s, ℓ, 3)\binom{a + b − 3ℓ}{a − s} = ∑_{s=0}^{3ℓ} ∑_{i+2j=s} \binom{ℓ}{i}\binom{ℓ}{j}\binom{a + b − 3ℓ}{a − s}

= ∑_{j=0}^{ℓ} ∑_{i=0}^{ℓ} \binom{ℓ}{i}\binom{ℓ}{j}\binom{a + b − 3ℓ}{a − (i + 2j)}

= ∑_{j=0}^{ℓ} \binom{ℓ}{j} ∑_{i=0}^{ℓ} \binom{ℓ}{i}\binom{a + b − 3ℓ}{(a − 2j) − i}

= ∑_{j=0}^{ℓ} \binom{ℓ}{j}\binom{a + b − 2ℓ}{a − 2j}.

Here, in the second line we change the order of summation and substitute s = i + 2j. In the last line we use the Vandermonde identity to simplify the inner summation.

\begin{matrix}9 & 7 & 64 & 333 & 1300 & 4235 & 12144 & 31603 & 76076 & 171600 & 366080 \\ 8 & 6 & 49 & 232 & 837 & 2550 & 6897 & 17028 & 39039 & 84084 & 171600 \\ 7 & 5 & 36 & 154 & 512 & 1458 & 3720 & 8712 & 19008 & 39039 & 76076 \\ 6 & 4 & 25 & 96 & 294 & 784 & 1890 & 4200 & 8712 & 17028 & 31603 \\ 5 & 3 & 16 & 55 & 156 & 392 & 896 & 1890 & 3720 & 6897 & 12144 \\ 4 & 2 & 9 & 28 & 75 & 180 & 392 & 784 & 1458 & 2550 & 4235 \\ 3 & 1 & 4 & 12 & 32 & 75 & 156 & 294 & 512 & 837 & 1300 \\ 2 & 0 & 1 & 4 & 12 & 28 & 55 & 96 & 154 & 232 & 333 \\ 1 & 0 & 0 & 1 & 4 & 9 & 16 & 25 & 36 & 49 & 64 \\ 0 & 0 & 0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ b/a & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \end{matrix}

Figure 5: The number of Q_{3} walks using one long step, |W(a, b; Q_{3}, 1)|, for 0 ≤ a, b ≤ 9.

The table in Figure 5 shows the values of |W(a, b; Q_{3}, 1)| for 0 ≤ a, b ≤ 9. Reading the entries across the rows of this table, we observe some familiar sequences when b = 0, 1, or 2.

When b = 0, Eq. (7) gives |W(a, 0; Q_{3}, 1)| = a−2 for a ≥ 2 (sequence \underline{A000027} in the On-Line Encyclopedia of Integer Sequences (OEIS)). When b = 1, Eq. (7) gives |W(a, 2; Q_{3}, 1)| = (a − 1)^{2} for a ≥ 1 (OEIS sequence \underline{A000290}). As a more interesting example, when b = 2, Eq. (7) gives |W(a, 2; Q_{3}, 1)| = a [\binom{a}{2} + 1] , which is OEIS sequence \underline{A006000}. The nonzero terms, 1, 4, 12, 28, 55, 96, 154, …, are the first triangular number, the second square number, the third pentagonal number, the fourth hexagonal number, and so on. So in general, |W (a, 2; Q_{3}, 1)| is the a-th entry in the sequence of (a + 2)-gonal numbers. For b > 2, the rows of the array |W(a, b; Q_{3}, 1)| appear to be new, and were added to OEIS as sequence \underline{A330601}.

5 A greedy Frobenius problem

For many of the sets we considered in previous sections, the distances d(a, b; S) only depend on a + b. We formalize this observation in the following lemma. For a nonempty subset N ⊆ ℕ with n > 1 for all n ∈ N, we define Q_{N} = ⋃_{n∈N} Q_{n}.

Lemma 8. Let N ⊆ ℕ be finite and nonempty, with n > 1 for all n ∈ N. For any a, b, c, d ∈ ℕ with a + b = c + d,

d(a, b; Q_{N}) = d(c, d; Q_{N}).

Proof. We can assume without loss of generality that a < c. It suffices to consider the case that c = a + 1 so that d = b − 1. This means c > 0 and b > 0.

Let s = s_{1}, …, s_{k} be a Q_{N}-walk of minimal length that terminates at (a, b). Because b > 0, there is some step s_{i} = (x, y) with y > 0. Consider replacing s_{i} with s′_{i} = (x+1, y −1). Note that s′_{i} ∈ Q_{N} because s_{i} ∈ Q_{N} and (x + 1) + (y − 1) = x + y.

This gives a path s′ = s_{1}, …, s_{i−1}, s′_{i}, s_{i+1}, …, s_{k} of length k terminating at (a, b) + (1, −1) = (c, d). Thus k = d(a, b; Q_{N}) ≥ d(c, d; Q_{N}). This argument can be reversed to show d(a, b; Q_{N}) ≤ d(c, d; Q_{N}).

As a consequence, the problem of determining d(a, b; Q_{N}) is the same as determining d(a + b, 0; Q_{N}). Since a Q_{N}-walk terminating at (a + b, 0) can only use steps of the form (n, 0) with n ∈ {1} ∪ N, this problem is, in turn, equivalent to the one-dimensional problem of determining the minimum number of summands needed to express a + b as a sum of elements in {1} ∪ N.

In general, for a nonnegative integer s and a finite, nonempty, set S ⊆ ℕ, we use d(s; S) to denote the minimum number of summands needed to express s as a sum of elements in S. Without the qualification that the number of summands be minimized, this problem is quite similar to the classical Frobenius problem.

If S is a nonempty set of relatively prime integers, the Frobenius number, Frob(S), is defined as the largest integer that cannot be written as a sum of elements of S. A classical result of Sylvester [9] states that if x and y are relatively prime integers, then Frob({x, y}) = (x − 1)(y − 1) − 1. For example, when x = 3 and y = 5, the integer 7 cannot be written as a sum of threes and fives, but any integer s ≥ 8 can be written in such a way. For more background on Frobenius numbers, we refer to the text of Ramírez Alfonsín [6].

Let us return to the problem of determining d(s; S). There is a simple greedy bound

d(s; S) ≥ ⌈\frac{s}{max(S)}⌉ .

It seems natural to ask when this bound is tight. For a finite set S ⊆ ℕ, we can define the greedy Frobenius number of S (if it exists) to be the smallest integer M such that d(s; S) = ⌈\frac{s}{max(S)}⌉ for all s > M. In other words, M is the largest integer that cannot be

written as a sum of ⌈\frac{M}{max(S)}⌉ elements from S. In this case, we write gFrob(S) = M. If no such integer M exists, we write gFrob(S) = ∞.

Proposition 9. Let S ⊆ ℕ be finite and nonempty, and let m = max(S). If m ≥ 2 and m − 1 ∉ S, then gFrob(S) = ∞.

Proof. We claim that no positive integer s with s ≡ −1 mod m can be expressed as a sum of ⌈\frac{s}{m}⌉ elements of S. This implies gFrob(S) = ∞, because for any M there exists an s > M that cannot be written as a sum of ⌈\frac{s}{m}⌉ elements from S.

This claim is clear if S = {m}, as it is impossible to write any s with s ≢ 0 mod m as a sum of elements of S. More generally, if there exists an infinite family of integers that cannot be expressed as a sum of elements of S, then gFrob(S) = ∞. Thus we need only consider the case that |S| > 1, and we may assume that any sufficiently large s can be expressed as a sum of elements from S.

Let s ≡ −1 mod m be sufficiently large that it can be expressed as a sum of elements from S. Write s = qm − 1, so that ⌈\frac{s}{m}⌉ = q. Consider an expression of S as a sum of elements from S that uses a minimum number of summands. Assume there are a summands not equal to m and b summands equal to m. Since s ≠ 0 mod m, it must be the case that a > 0.

By our assumption that m − 1 ∉ S, it must be the case that

qm − 1 = s ≤ a · (m − 2) + b · m = (a + b) · m − 2a < (a + b) · m − 1.

Therefore, ⌈\frac{s}{m}⌉ = q < a + b = d(s; S). This means s cannot be written as a sum of ⌈\frac{s}{m}⌉ elements of S.

As a converse to Proposition 9, we can consider the simplest family of sets that do not violate the condition that max(S) − 1 ∉ S, which are sets of the form S = {m − 1, m} for m ≥ 2.

Proposition 10. Let m ≥ 2 and S = {m − 1, m}. Then

gFrob(S) = (m − 1)(m − 2) − 1 = Frob(S).

Proof. Let M = (m − 1)(m − 2) − 1. First we claim it is impossible to write M as a sum of elements in S. Indeed, suppose M = a · (m − 1) + b · m. Then a < m − 2, because

(m − 1)(m − 2) − 1 = M ≥ a · (m − 1).

On the other hand, M ≡ 1 mod m and a · (m − 1) + b · m ≡ −a mod m, so a ≡ −1 mod m. There is no nonnegative integer a such that a ≡ −1 mod m and a < m − 2. This proves it is impossible to write M as a sum of elements in S.

Next, we claim that any s > M can be written as a sum of ⌈\frac{s}{m}⌉ elements from S. We will prove the claim by showing any of the m consecutive integers (m − 1)(m − 2) + k for 0 ≤ k ≤ m − 1 can be expressed as such a sum. The claim follows immediately from this fact.

For 0 ≤ k ≤ m−2, the integer (m−1)(m−2)+k can be written as (m−2−k)·(m−1)+k·m, which is a sum of m − 2 − k parts of size m − 1 and k parts of size m. This expresses (m − 1)(m − 2) + k as a sum of m − 2 elements from S. Further, ⌈\frac{(m−1)(m−2)+k}{m}⌉ = m − 2 for all these numbers. When k = m − 1, the integer (m − 1)(m − 2) + k = (m − 1)^{2}, which is a sum of m − 1 parts of size m − 1 and 0 parts of size m. In this case, ⌈\frac{(m−1)^{2}}{m} ⌉ = m − 1. This completes the proof.

Together, Proposition 9 and Proposition 10 imply the following result.

Corollary 11. Let S ⊆ ℕ be finite and nonempty with m = max(S). Then gFrob(S) < ∞ if and only if m = 1 or m−1 ∈ S. Moreover, if m−1 ∈ S, then gFrob(S) ≤ (m−1)(m−2)−1.

Proof. The claim that gFrob(S) < ∞ if and only if m − 1 ∈ S follows from Propositions 9 and 10. The bound gFrob(S) ≤ gFrob({m − 1, m} when m − 1 ∈ S is immediate, because gFrob(S) ≤ gFrob(T) whenever T ⊆ S.

Now we return to our motivating example, which concerns sets of the form S = {1} ∪ N. The simplest such sets for which gFrob(S) < ∞ are those of the form S = {1, m − 1, m}, for m ≥ 3. However, the notation is cleaner if we write S = {1, n, n + 1} for some n ≥ 2.

Theorem 12. Let n ≥ 2 and S = {1, n, n + 1}. Let s ∈ ℕ and write s = (n + 1)q − r with 0 ≤ r ≤ n, so that ⌈\frac{s}{n+1}⌉ = q. Then

d(s; S) = \begin{cases}q, & if r ≤ q or r = n; \\ q + (n − r), & if q < r < n. \end{cases}  (8)

In particular, gFrob(S) = n^{2} − 2n − 1 = Frob({n, n + 1}) − n.

Proof. We begin by establishing Eq. (8).

First we consider the case that r ≤ q or r = n. We know d(s; S) ≥ q, so we need only show it is possible to express s as a sum of elements in S with exactly q summands. When r ≤ q we can write

s = (n + 1)q − r = (n + 1)(q − r) + nr,

which is a sum with q − r parts of size n + 1 and r parts of size n. Similarly, when r = n, we can write

s = (n + 1)q − n = (n + 1)(q − 1) + 1,

which is a sum with q − 1 parts of size n + 1 and 1 part of size 1.

Now we move on to the case that q < r < n. In this case,

s = (n + 1)q − r = (n + 1)(q − 1) + (n − r + 1),

which is a sum with q − 1 parts of size n + 1 and n − r + 1 parts of size 1, giving a total of (q − 1) + (n − r + 1) = n + q − r summands. Therefore, d(s; S) ≤ q + (n − r). Here, we have used the fact that n > r to guarantee n − r + 1 ≥ 0 and the fact that r > 0 to guarantee q ≥ 1. So we are left to show d(s; S) ≥ q + (n − r).

Consider any sum of the form s = a + bn + c(n + 1), having a parts of size 1, b parts of size n, and c parts of size n + 1. Then

s = (n + 1)q − r
a + bn + c(n + 1) = (q − 1)n + (q + n − r)
(b + c)n + (a + c) = (q − 1)n + (q + n − r).

Now we note that q + n − r < n because q < r. Similarly, q + n − r ≥ 0 because n > r. This means q + n − r is the remainder when s is divided by n. Therefore, a + c ≥ q + n − r because a + c ≥ 0 and a + c ≡ q + n − r mod n.

If we choose a, b, and c to be parameters that realize d(s; S), it follows that

d(s; S) = a + b + c ≥ a + c ≥ q + n − r.

This establishes Eq. (8). In particular, setting q = n − 2 and r = n − 1 gives the largest value of s for which q < r < n. This corresponds to s = (n+1)(n−2)+(n−1) = n^{2} −2n−1. Thus d(s; S) = ⌈\frac{s}{n+1}⌉ once s > n^{2} − 2n − 1 = (n − 1)^{2} − 2. The sequence a_{k} = k^{2} − 2 is \underline{A008865} in the OEIS [7].

6 Acknowledgments

We gratefully acknowledge support from the National Science Foundation. This research was supported by Grant DMS-1600048.

References

[1] Kenneth P. Bogart, Introductory Combinatorics, 3rd edition, Harcourt/Academic Press, 2000.

[2] Eva Y. P. Deng and Toufik Mansour, Three Hoppy path problems and ternary paths, Discrete Appl. Math. 156 (2008), 770–779.

[3] Jackson Evoniuk, Steven Klee, and Van Magnan, Enumerating minimal length lattice paths, J. Integer Sequences 21 (2018), Article 18.3.6.

[4] Toufik Mansour, Combinatorial methods and recurrence relations with two indices, J. Difference Equ. Appl. 12 (2006), 555–563.

[5] Toufik Mansour, Recurrence relations with two indices and even trees, J. Difference Equ. Appl. 13 (2007), 47–61.

[6] J. L. Ramírez Alfonsín, The Diophantine Frobenius problem, Vol. 30 of Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, 2005.

[7] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2020. Available

   at https://oeis.org.

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

   Team, 2019. Available at http://www.sagemath.org.

[9] James Joseph Sylvester, Question 7382, Mathematical Questions from the Educational Times 41 (1884), 21.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: lattice path enumeration, Frobenius problem.

(Concerned with sequences \underline{A000027}, \underline{A000290}, \underline{A006000}, \underline{A008865}, and \underline{A330601}.)

Received January 16 2020; revised version received March 4 2020. Published in Journal of Integer Sequences, March 18 2020.

Return to Journal of Integer Sequences home page.