\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}} \usepackage{tikz} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \DeclareMathOperator{\mbs}{\mathbf{s}} \DeclareMathOperator{\dist}{d} \DeclareMathOperator{\Frob}{Frob} \DeclareMathOperator{\gFrob}{gFrob} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\Large \bf Enumerating Lattice Walks with Prescribed Steps } \vskip 1cm \large Nestor Iwanojko, Steven Klee, Bryn Lasher, and Elena Volpi\\ Department of Mathematics\\ Seattle University\\ 901 12th Avenue\\ Seattle, WA 98122 \\ USA\\ \href{mailto:iwanojkonest@seattleu.edu}{\tt iwanojkonest@seattleu.edu}\\ \href{mailto:klees@seattleu.edu}{\tt klees@seattleu.edu}\\ \href{mailto:lasherb@seattleu.edu}{\tt lasherb@seattleu.edu}\\ \href{mailto:volpie@seattleu.edu}{\tt volpie@seattleu.edu} \end{center} \vskip .2 in \begin{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. \end{abstract} \section{Introduction} Let $S \subseteq \mathbb{N}^d$ be a finite set of vectors whose entries are nonnegative integers. For most of this paper, we will focus on vectors $S \subseteq \mathbb{N}^2$. An \textit{$S$-walk} is an ordered sequence of \textit{steps}, $\mathbf{s} = s_1,s_2,\ldots,s_k$, with $s_i \in S$ for all $i$. We visualize $\mathbf{s}$ as a walk in the plane, beginning at the origin and terminating at the point $s_1+s_2+\cdots+s_k$. We say the number of steps in the walk is its \textit{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\ \cite{Mansour06} explored a similar problem, counting paths comprised of a fixed set of steps $S = \{(i,1) \ : \ i \geq 0\}$ that were forced to stay in the nonnegative orthant $\{(a,b) \in \mathbb{Z}^2 \ : \ 0 \leq a \leq b\}$ and terminate at some point $(i,n)$ with $0 \leq i \leq n$. Mansour\ \cite{Mansour07} and Mansour and Deng\ \cite{Mansour08} 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 $$\mathbf{s} = (1,0), (1,0), (1,1), (0,1), (1,0)$$ and $$\mathbf{s}' = (1,1), (1,0), (1,1), (1,0)$$ are illustrated in Figure \ref{fig1}. Both walks terminate at $(a,b) = (4,2)$, but $\mathbf{s}$ has length $5$, while $\mathbf{s}'$ has length $4$. \begin{figure}[ht] \centering \begin{tabular}{p{.4\textwidth}p{.4\textwidth}} \centering \begin{tikzpicture} \draw[gray!50] (-1,-1) grid (5,3); \draw[->] (-1,0) -- (5,0); \draw[->] (0,-1) -- (0,3); \draw[ultra thick,->] (0,0) -- (1,0); \draw[ultra thick,->] (1,0) -- (2,0); \draw[ultra thick,->] (2,0) -- (3,1); \draw[ultra thick,->] (3,1) -- (3,2); \draw[ultra thick,->] (3,2) -- (4,2); \end{tikzpicture} & \centering \begin{tikzpicture} \draw[gray!50] (-1,-1) grid (5,3); \draw[->] (-1,0) -- (5,0); \draw[->] (0,-1) -- (0,3); \draw[ultra thick,->] (0,0) -- (1,1); \draw[ultra thick,->] (1,1) -- (2,1); \draw[ultra thick,->] (2,1) -- (3,2); \draw[ultra thick,->] (3,2) -- (4,2); \end{tikzpicture} \end{tabular} \caption{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)\}$.} \label{fig1} \end{figure} 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 \textit{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.\ \cite{EKM} studied $S$-walks of minimal length for various sets $S \subseteq \mathbb{N}^2$. Our first goal here is to build upon that work, enumerating $S$-walks according to an extra parameter, $\ell$, that counts the number of \textit{long steps} used in the walk --- that is, steps other than $(1,0)$ and $(0,1)$. When $\ell=0$, we reduce to the case that $S = \{(1,0),(0,1)\}$. When $\ell$ is maximal we enumerate walks of minimal length. One difference in our approach from that of Evoniuk et al.\ \cite{EKM} 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 $|\mathcal{W}(a,b;S)|$. By introducing the parameter $\ell$, we are able to compute $|\mathcal{W}(a,b;S,\ell)|$ directly, and then determine $d(a,b;S)$ as a consequence by finding the largest value of $\ell$ for which $|\mathcal{W}(a,b;S,\ell)|$ is nonzero. We explore this problem for $S = \{(1,0), (0,1), (1,1)\}$ in Section \ref{section2}, for sets of the form $S = \{(1,0), (0,1), (u,u+1), (u+1,u)\}$ with $u \geq 1$ in Section \ref{section3}, and for sets of the form $Q_n := \{(1,0), (0,1)\} \cup \{(n,n-i) \ : \ 0 \leq i \leq n\}$ with $n \geq 2$ in Section \ref{section4}. In Section \ref{section5}, we explore a question in the spirit of the Frobenius problem. Let $m = \max\{s_1+s_2 \ : \ (s_1,s_2) \in S\}$. For any $(a,b) \in \mathbb{N}^2$, there is a simple greedy bound of $d(a,b;S) \geq \left\lceil \frac{a+b}{m} \right\rceil$. 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 \subseteq \mathbb{N}$ that have this greedy Frobenius property. \section{Walks for $S = \{(1,0), (0,1), (1,1)\}$} \label{section2} 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 \textit{short steps}, and $(1,1)$ is a \textit{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 $\mathcal{W}(a,b;S,\ell)$ to denote the set of $S$-walks terminating at $(a,b)$ that use exactly $\ell$ long steps, and $|\mathcal{W}(a,b;S,\ell)|$ to denote the cardinality of that set. When enumerating minimal-length lattice walks, we suppress the $\ell$ from this notation, using $|\mathcal{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.\ \cite{EKM}. \begin{theorem} \label{thm:walks_11} Let $S = \{(1,0), (0,1), (1,1)\}$. For all $(a,b) \in \mathbb{N}^2$ we have \begin{equation} \label{walks_11} |\mathcal{W}(a,b;S,\ell)| = \binom{a+b-\ell}{a-\ell,b-\ell,\ell}. \end{equation} \end{theorem} \begin{proof} Let $\mathbf{s}$ be an $S$-walk that uses $\ell$ long steps and terminates at $(a,b)$. Those long steps contribute $\ell(1,1) = (\ell,\ell)$ to the overall sum of the vectors in $\mathbf{s}$. We know $\mathbf{s}$ terminates at $(a,b)$ and $(a,b)-(\ell,\ell) = (a-\ell,b-\ell)$, so $\mathbf{s}$ must use $a-\ell$ steps in the $(1,0)$ direction and $b-\ell$ steps in the $(0,1)$ direction. It follows that $\mathbf{s}$ has length $(a-\ell)+(b-\ell)+\ell = a+b-\ell$. The result follows, because any $S$-walk with $\ell$ long steps can be viewed as an ordered sequence of $a+b-\ell$ steps into which we must place $a-\ell$ steps in the $(1,0)$ direction, $b-\ell$ steps in the $(0,1)$ direction, and $\ell$ steps in the $(1,1)$ direction. \end{proof} It follows from Theorem \ref{thm:walks_11} that $|W(a,b;S,\ell)|$ is nonzero if and only if $0 \leq \ell \leq \min(a,b)$. Otherwise, one of $a-\ell$, $b-\ell$, or $\ell$ is negative, making $\binom{a+b-\ell}{a-\ell,b-\ell,\ell} = 0$. When $\ell=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 $\ell = \min(a,b)$, we get $a+b-\ell = \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.\ \cite{EKM}: \begin{corollary} {\rm{(\cite[Theorem 1]{EKM})}} \\ Let $S = \{(1,0),(0,1),(1,1)\}$ and let $(a,b) \in \mathbb{N}^2$. Then $d(a,b;S) = \max(a,b)$ and $$|\mathcal{W}(a,b;S)|= \binom{\max(a,b)}{\min(a,b)}.$$ \end{corollary} \section{Walks for $S = \{(1,0), (0,1), (u,u+1),(u+1,u)\}$} \label{section3} Let $u,v \in \mathbb{N}$ with $u,v \geq 1$. Evoniuk et al.\ \cite[Problem 10]{EKM} left open the question of understanding $d(a,b;S)$ and $\mathcal{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 \textit{short steps}, and $(u,u+1)$ and $(u+1,u)$ are \textit{long steps}. We begin with a motivating example in the case that $u=2$. Figure \ref{u23-distances} shows the values of $d(a,b;S)$ for points with $0 \leq a,b \leq 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 \cite{Sage}. \begin{figure}[ht] \centering \begin{tikzpicture}[scale=.9] \draw[->] (-1,0) -- (12,0); \draw[->] (0,-1) -- (0,12); \foreach \x in {0,...,11}{ \draw (\x+.5,-.5) node {\footnotesize \x}; \draw (-.5,\x+.5) node {\footnotesize \x}; } \draw (0,0) -- (-1,-1); \draw[dashed] (.5,.5) --++ (11,22/3); \draw[dashed] (.5,.5) --++ (22/3,11); \draw (-.25,-.75) node {\footnotesize $a$}; \draw (-.75,-.25) node {\footnotesize $b$}; \draw (0.5,0.5) node {\footnotesize 0}; \draw (0.5,1.5) node {\footnotesize 1}; \draw (0.5,2.5) node {\footnotesize 2}; \draw (0.5,3.5) node {\footnotesize 3}; \draw (0.5,4.5) node {\footnotesize 4}; \draw (0.5,5.5) node {\footnotesize 5}; \draw (0.5,6.5) node {\footnotesize 6}; \draw (0.5,7.5) node {\footnotesize 7}; \draw (0.5,8.5) node {\footnotesize 8}; \draw (0.5,9.5) node {\footnotesize 9}; \draw (0.5,10.5) node {\footnotesize 10}; \draw (0.5,11.5) node {\footnotesize 11}; \draw (1.5,0.5) node {\footnotesize 1}; \draw (1.5,1.5) node {\footnotesize 2}; \draw (1.5,2.5) node {\footnotesize 3}; \draw (1.5,3.5) node {\footnotesize 4}; \draw (1.5,4.5) node {\footnotesize 5}; \draw (1.5,5.5) node {\footnotesize 6}; \draw (1.5,6.5) node {\footnotesize 7}; \draw (1.5,7.5) node {\footnotesize 8}; \draw (1.5,8.5) node {\footnotesize 9}; \draw (1.5,9.5) node {\footnotesize 10}; \draw (1.5,10.5) node {\footnotesize 11}; \draw (1.5,11.5) node {\footnotesize 12}; \draw (2.5,0.5) node {\footnotesize 2}; \draw (2.5,1.5) node {\footnotesize 3}; \draw (2.5,2.5) node {\footnotesize 4}; \draw (2.5,3.5) node {\footnotesize 1}; \draw (2.5,4.5) node {\footnotesize 2}; \draw (2.5,5.5) node {\footnotesize 3}; \draw (2.5,6.5) node {\footnotesize 4}; \draw (2.5,7.5) node {\footnotesize 5}; \draw (2.5,8.5) node {\footnotesize 6}; \draw (2.5,9.5) node {\footnotesize 7}; \draw (2.5,10.5) node {\footnotesize 8}; \draw (2.5,11.5) node {\footnotesize 9}; \draw (3.5,0.5) node {\footnotesize 3}; \draw (3.5,1.5) node {\footnotesize 4}; \draw (3.5,2.5) node {\footnotesize 1}; \draw (3.5,3.5) node {\footnotesize 2}; \draw (3.5,4.5) node {\footnotesize 3}; \draw (3.5,5.5) node {\footnotesize 4}; \draw (3.5,6.5) node {\footnotesize 5}; \draw (3.5,7.5) node {\footnotesize 6}; \draw (3.5,8.5) node {\footnotesize 7}; \draw (3.5,9.5) node {\footnotesize 8}; \draw (3.5,10.5) node {\footnotesize 9}; \draw (3.5,11.5) node {\footnotesize 10}; \draw (4.5,0.5) node {\footnotesize 4}; \draw (4.5,1.5) node {\footnotesize 5}; \draw (4.5,2.5) node {\footnotesize 2}; \draw (4.5,3.5) node {\footnotesize 3}; \draw (4.5,4.5) node {\footnotesize 4}; \draw (4.5,5.5) node {\footnotesize 5}; \draw (4.5,6.5) node {\footnotesize 2}; \draw (4.5,7.5) node {\footnotesize 3}; \draw (4.5,8.5) node {\footnotesize 4}; \draw (4.5,9.5) node {\footnotesize 5}; \draw (4.5,10.5) node {\footnotesize 6}; \draw (4.5,11.5) node {\footnotesize 7}; \draw (5.5,0.5) node {\footnotesize 5}; \draw (5.5,1.5) node {\footnotesize 6}; \draw (5.5,2.5) node {\footnotesize 3}; \draw (5.5,3.5) node {\footnotesize 4}; \draw (5.5,4.5) node {\footnotesize 5}; \draw (5.5,5.5) node {\footnotesize 2}; \draw (5.5,6.5) node {\footnotesize 3}; \draw (5.5,7.5) node {\footnotesize 4}; \draw (5.5,8.5) node {\footnotesize 5}; \draw (5.5,9.5) node {\footnotesize 6}; \draw (5.5,10.5) node {\footnotesize 7}; \draw (5.5,11.5) node {\footnotesize 8}; \draw (6.5,0.5) node {\footnotesize 6}; \draw (6.5,1.5) node {\footnotesize 7}; \draw (6.5,2.5) node {\footnotesize 4}; \draw (6.5,3.5) node {\footnotesize 5}; \draw (6.5,4.5) node {\footnotesize 2}; \draw (6.5,5.5) node {\footnotesize 3}; \draw (6.5,6.5) node {\footnotesize 4}; \draw (6.5,7.5) node {\footnotesize 5}; \draw (6.5,8.5) node {\footnotesize 6}; \draw (6.5,9.5) node {\footnotesize 3}; \draw (6.5,10.5) node {\footnotesize 4}; \draw (6.5,11.5) node {\footnotesize 5}; \draw (7.5,0.5) node {\footnotesize 7}; \draw (7.5,1.5) node {\footnotesize 8}; \draw (7.5,2.5) node {\footnotesize 5}; \draw (7.5,3.5) node {\footnotesize 6}; \draw (7.5,4.5) node {\footnotesize 3}; \draw (7.5,5.5) node {\footnotesize 4}; \draw (7.5,6.5) node {\footnotesize 5}; \draw (7.5,7.5) node {\footnotesize 6}; \draw (7.5,8.5) node {\footnotesize 3}; \draw (7.5,9.5) node {\footnotesize 4}; \draw (7.5,10.5) node {\footnotesize 5}; \draw (7.5,11.5) node {\footnotesize 6}; \draw (8.5,0.5) node {\footnotesize 8}; \draw (8.5,1.5) node {\footnotesize 9}; \draw (8.5,2.5) node {\footnotesize 6}; \draw (8.5,3.5) node {\footnotesize 7}; \draw (8.5,4.5) node {\footnotesize 4}; \draw (8.5,5.5) node {\footnotesize 5}; \draw (8.5,6.5) node {\footnotesize 6}; \draw (8.5,7.5) node {\footnotesize 3}; \draw (8.5,8.5) node {\footnotesize 4}; \draw (8.5,9.5) node {\footnotesize 5}; \draw (8.5,10.5) node {\footnotesize 6}; \draw (8.5,11.5) node {\footnotesize 7}; \draw (9.5,0.5) node {\footnotesize 9}; \draw (9.5,1.5) node {\footnotesize 10}; \draw (9.5,2.5) node {\footnotesize 7}; \draw (9.5,3.5) node {\footnotesize 8}; \draw (9.5,4.5) node {\footnotesize 5}; \draw (9.5,5.5) node {\footnotesize 6}; \draw (9.5,6.5) node {\footnotesize 3}; \draw (9.5,7.5) node {\footnotesize 4}; \draw (9.5,8.5) node {\footnotesize 5}; \draw (9.5,9.5) node {\footnotesize 6}; \draw (9.5,10.5) node {\footnotesize 7}; \draw (9.5,11.5) node {\footnotesize 4}; \draw (10.5,0.5) node {\footnotesize 10}; \draw (10.5,1.5) node {\footnotesize 11}; \draw (10.5,2.5) node {\footnotesize 8}; \draw (10.5,3.5) node {\footnotesize 9}; \draw (10.5,4.5) node {\footnotesize 6}; \draw (10.5,5.5) node {\footnotesize 7}; \draw (10.5,6.5) node {\footnotesize 4}; \draw (10.5,7.5) node {\footnotesize 5}; \draw (10.5,8.5) node {\footnotesize 6}; \draw (10.5,9.5) node {\footnotesize 7}; \draw (10.5,10.5) node {\footnotesize 4}; \draw (10.5,11.5) node {\footnotesize 5}; \draw (11.5,0.5) node {\footnotesize 11}; \draw (11.5,1.5) node {\footnotesize 12}; \draw (11.5,2.5) node {\footnotesize 9}; \draw (11.5,3.5) node {\footnotesize 10}; \draw (11.5,4.5) node {\footnotesize 7}; \draw (11.5,5.5) node {\footnotesize 8}; \draw (11.5,6.5) node {\footnotesize 5}; \draw (11.5,7.5) node {\footnotesize 6}; \draw (11.5,8.5) node {\footnotesize 7}; \draw (11.5,9.5) node {\footnotesize 4}; \draw (11.5,10.5) node {\footnotesize 5}; \draw (11.5,11.5) node {\footnotesize 6}; \end{tikzpicture} \caption{Distances $d(a,b;S)$ for $0 \leq a,b \leq 11$ when $S = \{(1,0), (0,1), (2,3), (3,2)\}$.} \label{u23-distances} \end{figure} 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 \leq b$; or equivalently, when $a \leq \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 \ref{uu+1-dist} below shows this pattern continues for all $u \geq 1$. We begin with a more general result. \begin{theorem} \label{uu+1-long} Let $u \geq 1$ and $S = \{(1,0),(0,1),(u,u+1),(u+1,u)\}$. For any $(a,b) \in \mathbb{N}^2$, the number of $S$-walks terminating at $(a,b)$ that use $\ell$ long steps is \begin{equation}\label{numwalks_uu+1} |\mathcal{W}(a,b;S,\ell)| = \binom{a+b-2u\ell}{\ell} \cdot \binom{a+b-2u\ell}{a-u\ell}. \end{equation} \end{theorem} \begin{proof} Consider an $S$-walk using $\ell$ long steps. Of those, suppose $i$ steps are in the direction $(u,u+1)$ and $\ell-i$ are in the direction $(u+1,u)$. The contribution of long steps in the walk is $$ i(u,u+1) + (\ell-i)(u+1,u) = (u\ell+ \ell-i, u\ell + i). $$ Thus, in order to reach $(a,b)$, the walk must use $a-u\ell - \ell + i$ steps in the $(1,0)$ direction and $b-u\ell -i$ steps in the $(0,1)$ direction. The total length of such a walk is $$(a-u\ell - \ell +i) + (b-u\ell -i) + \ell = a+b-2u\ell.$$ The set of all such walks can be described by first choosing $\ell$ positions out of $a+b-2u\ell$ to be long steps, then choosing which $i$ of those $\ell$ long steps will be in the direction $(u,u+1)$, and finally choosing which of the remaining $a+b-2u\ell -\ell$ steps will be in the direction $(1,0)$. Therefore, \begin{align*} |\mathcal{W}(a,b;S,\ell)| &= \sum_{i=0}^\ell \binom{a+b-2u\ell}{\ell} \binom{\ell}{i} \binom{a+b-2u\ell-\ell}{a-u\ell-\ell+i} \\ &= \binom{a+b-2u\ell}{\ell}\sum_{k=0}^\ell \binom{\ell}{k}\binom{a+b-2u\ell-\ell}{a-u\ell-k} \\ &= \binom{a+b-2u\ell}{\ell}\binom{a+b-2u\ell}{a-u\ell}. \end{align*} In the second line above we reindex the sum, setting $k = \ell-i$. In the third line, we use the Vandermonde identity (see \cite[Example 4.4]{Bogart}) to collapse the summation. \end{proof} Now we will use Theorem \ref{uu+1-long} 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)$. \begin{corollary} \label{uu+1-dist} Let $u \geq 1$ and $S = \{(1,0),(0,1),(u,u+1),(u+1,u)\}$. Let $(a,b) \in \mathbb{N}^2$ with $a \leq b$ and write $a+b = (2u+1)q+r$, with $0 \leq r \leq 2u$. Then \begin{equation}\label{dist_uu+1} d(a,b;S) = \begin{cases} a+b-2u\left\lfloor \frac{a}{u} \right\rfloor, & \text{ if $a \frac{a}{u} \geq \ell$. Therefore, $$ a+b = (2u+1)q+r > (2u+1)\ell+r \geq (2u+1)\ell, $$ as desired. Next, we consider the case that $uq \leq a \leq \frac{a+b}{2}$. Note that $(2u+1)\ell \leq a+b = (2u+1)q+r$ if and only if $\ell \leq q$, because $r \leq 2u$. Moreover, when $\ell = q$, the requirement that $a \geq u\ell$ is immediately satisfied because we assumed $u\ell=uq \leq a$. \end{proof} \section{Walks with steps of fixed length} \label{section4} 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.\ \cite{EKM}, using $Q_n$ to denote the set $$ Q_n = \{(1,0),(0,1)\} \cup \{(i,n-i) \ : \ 0 \leq i \leq n\}. $$ As before, we say steps $(1,0)$ and $(0,1)$ are \textit{short steps} and steps of the form $(i,n-i)$ are \textit{long steps}. Our first goal is to enumerate $Q_n$-walks using exactly $\ell$ long steps. We require some additional notation. For nonnegative integers $s$, $m$, and $p$, we define $\kappa(s,p,m)$ to be the number of ways to write $s = a_1+a_1+\cdots+a_p$ such that $a_i \in \mathbb{N}$ and $a_i \leq m$ for all $i$. In other words, $\kappa(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 \ref{ks22} demonstrates the values of $\kappa(s,2,2)$. \begin{figure}[H] \begin{center} \begin{tabular}{c|c|c} $s$ & valid sums & $\kappa(s,2,2)$ \\ \hline $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$ \end{tabular} \end{center} \caption{Values for $\kappa(s,2,2)$} \label{ks22} \end{figure} The table in Figure \ref{q2twolong} shows the number of walks terminating at the point $(a,b)$ using $\ell=2$ long steps from $Q_2$. Once again, the data here was generated using Sage \cite{Sage}. \begin{figure}[h] \begin{center} \begin{tikzpicture} \draw[->] (-1,0) -- (7,0); \draw[->] (0,-1) -- (0,7); \foreach \x in {0,...,6}{ \draw (\x+.5,-.5) node {\footnotesize \x}; \draw (-.5,\x+.5) node {\footnotesize \x}; } \draw (0,0) -- (-1,-1); \draw (-.25,-.75) node {\footnotesize $a$}; \draw (-.75,-.25) node {\footnotesize $b$}; \draw (0.5,0.5) node {\footnotesize 0}; \draw (0.5,1.5) node {\footnotesize 0}; \draw (0.5,2.5) node {\footnotesize 0}; \draw (0.5,3.5) node {\footnotesize 0}; \draw (0.5,4.5) node {\footnotesize 1}; \draw (0.5,5.5) node {\footnotesize 3}; \draw (0.5,6.5) node {\footnotesize 6}; \draw (1.5,0.5) node {\footnotesize 0}; \draw (1.5,1.5) node {\footnotesize 0}; \draw (1.5,2.5) node {\footnotesize 0}; \draw (1.5,3.5) node {\footnotesize 2}; \draw (1.5,4.5) node {\footnotesize 9}; \draw (1.5,5.5) node {\footnotesize 24}; \draw (1.5,6.5) node {\footnotesize 50}; \draw (2.5,0.5) node {\footnotesize 0}; \draw (2.5,1.5) node {\footnotesize 0}; \draw (2.5,2.5) node {\footnotesize 3}; \draw (2.5,3.5) node {\footnotesize 15}; \draw (2.5,4.5) node {\footnotesize 48}; \draw (2.5,5.5) node {\footnotesize 120}; \draw (2.5,6.5) node {\footnotesize 255}; \draw (3.5,0.5) node {\footnotesize 0}; \draw (3.5,1.5) node {\footnotesize 2}; \draw (3.5,2.5) node {\footnotesize 15}; \draw (3.5,3.5) node {\footnotesize 60}; \draw (3.5,4.5) node {\footnotesize 180}; \draw (3.5,5.5) node {\footnotesize 450}; \draw (3.5,6.5) node {\footnotesize 987}; \draw (4.5,0.5) node {\footnotesize 1}; \draw (4.5,1.5) node {\footnotesize 9}; \draw (4.5,2.5) node {\footnotesize 48}; \draw (4.5,3.5) node {\footnotesize 180}; \draw (4.5,4.5) node {\footnotesize 540}; \draw (4.5,5.5) node {\footnotesize 1386}; \draw (4.5,6.5) node {\footnotesize 3164}; \draw (5.5,0.5) node {\footnotesize 3}; \draw (5.5,1.5) node {\footnotesize 24}; \draw (5.5,2.5) node {\footnotesize 120}; \draw (5.5,3.5) node {\footnotesize 450}; \draw (5.5,4.5) node {\footnotesize 1386}; \draw (5.5,5.5) node {\footnotesize 3696}; \draw (5.5,6.5) node {\footnotesize 8820}; \draw (6.5,0.5) node {\footnotesize 6}; \draw (6.5,1.5) node {\footnotesize 50}; \draw (6.5,2.5) node {\footnotesize 255}; \draw (6.5,3.5) node {\footnotesize 987}; \draw (6.5,4.5) node {\footnotesize 3164}; \draw (6.5,5.5) node {\footnotesize 8820}; \draw (6.5,6.5) node {\footnotesize 22050}; \end{tikzpicture} \end{center} \caption{Values of $|\mathcal{W}(a,b;Q_2,2)|$ for $0 \leq a,b \leq 6$.} \label{q2twolong} \end{figure} In Figure \ref{q2twolong} we observe the values of $\kappa(s,2,2)$ along the first nonzero diagonal where $a+b = 4$. Moreover, the entries $|\mathcal{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 $\ell$. \begin{theorem}\label{Qnwalks} For any $n \geq 2$ and $a,b,\ell \in \mathbb{N}$, \begin{equation} \label{eq:numQnwalks} |\mathcal{W}(a,b;Q_n,\ell)| = \binom{a+b-(n-1)\ell}{\ell} \sum_{s=0}^{n\ell} \kappa(s,\ell,n)\binom{a+b-n\ell}{a-s}. \end{equation} \end{theorem} \begin{proof} First we note that a $Q_n$-walk using $\ell$ long steps has length $a+b-(n-1)\ell$. 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 $\mathbf{s} \in \mathcal{W}(a,b;Q_n,\ell)$, we can consider the sum of the $\ell$ long steps in $\mathbf{s}$. We will partition $\mathcal{W}(a,b;Q_n,\ell)$ based on the sum of the long steps in each path --- the sum of long steps leads to a point $(s,n\ell-s)$ for some $0 \leq s \leq n\ell$. How many walks have a sum of long steps that leads to $(s,n\ell-s)$? Each walk in $\mathcal{W}(a,b;Q_n,\ell)$ has length $a+b-(n-1)\ell$, so there are $\binom{a+b-(n-1)\ell}{\ell}$ ways to choose the positions of the long steps. The number of ways to write $(s,n\ell-s)$ as a sum of $\ell$ vectors from $Q_n$ is equal to the number of ways of writing $$ (a_1,n-a_1) + (a_2,n-a_2) + \cdots + (a_\ell,n-a_\ell) = (s,n\ell-s), $$ where $0 \leq a_i \leq n$ for all $i$. However, if $\sum_{i=1}^\ell a_i = s$, then $\sum_{i=1}^\ell(n-a_i) = n\ell-s$ automatically. Therefore, the number of ways to write $(s,n\ell-s)$ as a sum of $\ell$ vectors from $Q_n$ is exactly $\kappa(s,\ell,n)$. Finally, if the long steps in a $Q_n$-walk terminating at $(a,b)$ lead to the point $(s,n\ell-s)$, then the short steps must lead to the point $(a-s,b-n\ell+s)$. There are $a+b-n\ell$ 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 $\mathcal{W}(a,b;Q_n,\ell)$ whose long steps lead to the point $(s,n\ell-s)$ is $$ \binom{a+b-(n-1)\ell}{\ell} \kappa(s,\ell,n)\binom{a+b-n\ell}{a-s}. $$ Summing over all values $0 \leq s \leq n\ell$ gives the desired result. \end{proof} In general, the formula in Eq.\ \eqref{eq:numQnwalks} can be quite complicated; however, we exhibit some cases where it can be simplified. \begin{corollary}\label{cor:Q2walks} For any $a,b,\ell \in \mathbb{N}$, the number of $Q_2$-walks terminating at $(a,b)$ using $\ell$ long steps is \begin{equation}\label{eq:numQ2walks} |\mathcal{W}(a,b;Q_2,\ell)| = \binom{a+b-\ell}{\ell} \sum_{i=0}^\ell \binom{\ell}{i}\binom{a+b-\ell-i}{a-2i}. \end{equation} \end{corollary} \begin{proof} First, we note that $$\kappa(s,\ell,2) = \sum_{i \geq 0} \binom{\ell}{i,s-2i, \ell-s+i} = \sum_{i\geq 0} \binom{\ell}{i} \binom{\ell-i}{s-2i}.$$ This is because $\kappa(s,\ell,2)$ counts the number of ways to express $s$ as a sum of $\ell$ 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 $\ell-s+i$ summands equal to $0$. Thus, the number of sums using $i$ summands equal to $2$ is $\binom{\ell}{i,s-2i,\ell-s+i} = \binom{\ell}{i}\binom{\ell-i}{s-2i}.$ Therefore, by Eq.\ \eqref{eq:numQnwalks}, \begin{equation} \label{Q2walks-step1} |\mathcal{W}(a,b;Q_2,\ell)| = \binom{a+b-\ell}{\ell} \sum_{s = 0}^{2\ell} \sum_{i \geq 0} \binom{\ell}{i} \binom{\ell-i}{s-2i} \binom{a+b-2\ell}{a-s}. \end{equation} The terms of the inner summation in Eq.\ \eqref{Q2walks-step1} are nonzero only when $i \geq 0$, $i \leq \frac{s}{2}$, and $i \geq s-\ell$. Changing the order of summations allows us to write \begin{align*} |\mathcal{W}(a,b;Q_2,\ell)| &= \binom{a+b-\ell}{\ell} \sum_{i=0}^{\ell} \binom{\ell}{i} \sum_{s=2i}^{i+\ell} \binom{\ell-i}{s-2i}\binom{a+b-2\ell}{a-s} \\ &= \binom{a+b-\ell}{\ell} \sum_{i=0}^{\ell} \binom{\ell}{i} \sum_{k=0}^{\ell-i} \binom{\ell-i}{k} \binom{a+b-2\ell}{a-2i-k} \\ &= \binom{a+b-\ell}{\ell} \sum_{i=0}^{\ell} \binom{\ell}{i} \binom{a+b-\ell-i}{a-2i}. \end{align*} Here, the second line comes from reindexing with $k = s-2i$. The third line follows from the Vandermonde identity. \end{proof} \begin{corollary} \label{cor:Q3walks} For any $a,b,\ell \in \mathbb{N}$, the number of $Q_3$-walks terminating at $(a,b)$ using $\ell$ long steps is \begin{equation} \label{eq:numQ3walks} |\mathcal{W}(a,b;Q_3,\ell)| = \binom{a+b-2\ell}{\ell} \sum_{i=0}^\ell \binom{\ell}{i} \binom{a+b-2\ell}{a-2i}. \end{equation} \end{corollary} \begin{proof} Note that $\kappa(s,\ell,3)$ is the coefficient on $x^s$ in the expansion of $(1+x+x^2+x^3)^\ell.$ We can rewrite $(1+x+x^2+x^3)^\ell = (1+x)^\ell (1+x^2)^\ell$. This tells us $\kappa(s,\ell,3) = \sum_{i+2j = s} \binom{\ell}{i} \binom{\ell}{j}$, where the sum is over nonnegative integers $i,j$ such that $i+2j = s$. Therefore, \begin{align*} \sum_{s = 0}^{3\ell} \kappa(s,\ell,3) \binom{a+b-3\ell}{a-s} &= \sum_{s=0}^{3\ell} \sum_{i+2j = s} \binom{\ell}{i} \binom{\ell}{j} \binom{a+b-3\ell}{a-s} \\ &= \sum_{j=0}^\ell \sum_{i=0}^\ell \binom{\ell}{i} \binom{\ell}{j} \binom{a+b-3\ell}{a-(i+2j)} \\ &= \sum_{j=0}^\ell \binom{\ell}{j} \sum_{i=0}^\ell \binom{\ell}{i} \binom{a+b-3\ell}{(a-2j)-i} \\ &= \sum_{j=0}^\ell \binom{\ell}{j} \binom{a+b-2\ell}{a-2j}. \end{align*} 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. \end{proof} The table in Figure \ref{fig:q3ell1} shows the values of $|\mathcal{W}(a,b;Q_3,1)|$ for $0 \leq a,b \leq 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.\ \eqref{eq:numQ3walks} gives $|\mathcal{W}(a,0;Q_3,1)| = a-2$ for $a \geq 2$ (sequence \seqnum{A000027} in the {\it On-Line Encyclopedia of Integer Sequences} (OEIS)). When $b=1$, Eq.\ \eqref{eq:numQ3walks} gives $|\mathcal{W}(a,2;Q_3,1)| = (a-1)^2$ for $a \geq 1$ (OEIS sequence \seqnum{A000290}). As a more interesting example, when $b=2$, Eq.\ \eqref{eq:numQ3walks} gives $|\mathcal{W}(a,2;Q_3,1)| = a \left[ \binom{a}{2} + 1 \right],$ which is OEIS sequence \seqnum{A006000}. The nonzero terms, $1, 4, 12, 28, 55, 96, 154, \ldots$, 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 $|\mathcal{W}(a,b;Q_3,1)|$ appear to be new, and were added to OEIS as sequence \seqnum{A330601}. \begin{figure} \begin{center} %\renewcommand{\arraystretch}{1.4} \begin{tabular}{c|cccccccccc} \footnotesize 9 & \footnotesize 7 & \footnotesize 64 & \footnotesize 333 & \footnotesize 1300 & \footnotesize 4235 & \footnotesize 12144 & \footnotesize 31603 & \footnotesize 76076 & \footnotesize 171600 & \footnotesize 366080 \\ \footnotesize 8 & \footnotesize 6 & \footnotesize 49 & \footnotesize 232 & \footnotesize 837 & \footnotesize 2550 & \footnotesize 6897 & \footnotesize 17028 & \footnotesize 39039 & \footnotesize 84084 & \footnotesize 171600 \\ \footnotesize 7 & \footnotesize 5 & \footnotesize 36 & \footnotesize 154 & \footnotesize 512 & \footnotesize 1458 & \footnotesize 3720 & \footnotesize 8712 & \footnotesize 19008 & \footnotesize 39039 & \footnotesize 76076 \\ \footnotesize 6 & \footnotesize 4 & \footnotesize 25 & \footnotesize 96 & \footnotesize 294 & \footnotesize 784 & \footnotesize 1890 & \footnotesize 4200 & \footnotesize 8712 & \footnotesize 17028 & \footnotesize 31603 \\ \footnotesize 5 & \footnotesize 3 & \footnotesize 16 & \footnotesize 55 & \footnotesize 156 & \footnotesize 392 & \footnotesize 896 & \footnotesize 1890 & \footnotesize 3720 & \footnotesize 6897 & \footnotesize 12144 \\ \footnotesize 4 & \footnotesize 2 & \footnotesize 9 & \footnotesize 28 & \footnotesize 75 & \footnotesize 180 & \footnotesize 392 & \footnotesize 784 & \footnotesize 1458 & \footnotesize 2550 & \footnotesize 4235 \\ \footnotesize 3 & \footnotesize 1 & \footnotesize 4 & \footnotesize 12 & \footnotesize 32 & \footnotesize 75 & \footnotesize 156 & \footnotesize 294 & \footnotesize 512 & \footnotesize 837 & \footnotesize 1300 \\ \footnotesize 2 & \footnotesize 0 & \footnotesize 1 & \footnotesize 4 & \footnotesize 12 & \footnotesize 28 & \footnotesize 55 & \footnotesize 96 & \footnotesize 154 & \footnotesize 232 & \footnotesize 333 \\ \footnotesize 1 & \footnotesize 0 & \footnotesize 0 & \footnotesize 1 & \footnotesize 4 & \footnotesize 9 & \footnotesize 16 & \footnotesize 25 & \footnotesize 36 & \footnotesize 49 & \footnotesize 64 \\ \footnotesize 0 & \footnotesize 0 & \footnotesize 0 & \footnotesize 0 & \footnotesize 1 & \footnotesize 2 & \footnotesize 3 & \footnotesize 4 & \footnotesize 5 & \footnotesize 6 & \footnotesize 7 \\ \hline \footnotesize $b/a$ & \footnotesize 0 & \footnotesize 1 & \footnotesize 2 & \footnotesize 3 & \footnotesize 4 & \footnotesize 5 & \footnotesize 6 & \footnotesize 7 & \footnotesize 8 & \footnotesize 9 \\ \end{tabular} \caption{The number of $Q_3$ walks using one long step, $|\mathcal{W}(a,b;Q_3,1)|$, for $0 \leq a,b \leq 9$.} \label{fig:q3ell1} \end{center} \end{figure} \section{A greedy Frobenius problem} \label{section5} 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 \subseteq \mathbb{N}$ with $n > 1$ for all $n \in N$, we define $Q_N = \bigcup_{n \in N} Q_n$. \begin{lemma} Let $N \subseteq \mathbb{N}$ be finite and nonempty, with $n>1$ for all $n \in N$. For any $a,b,c,d \in \mathbb{N}$ with $a+b = c+d$, $$d(a,b;Q_N) = d(c,d;Q_N).$$ \end{lemma} \begin{proof} We can assume without loss of generality that $a0$ and $b>0$. Let $\mathbf{s} = s_1,\ldots,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' \in Q_N$ because $s_i \in Q_N$ and $(x+1)+(y-1) = x+y$. This gives a path $\mathbf{s}' = s_1,\ldots,s_{i-1},s_i',s_{i+1},\ldots,s_k$ of length $k$ terminating at $(a,b) + (1,-1) = (c,d)$. Thus $k = d(a,b;Q_N) \geq d(c,d;Q_N)$. This argument can be reversed to show $d(a,b;Q_N) \leq d(c,d;Q_N)$. \end{proof} 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 \in \{1\} \cup 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\} \cup N$. In general, for a nonnegative integer $s$ and a finite, nonempty, set $S \subseteq \mathbb{N}$, 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 \textit{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 \cite{Sylvester} 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 \geq 8$ can be written in such a way. For more background on Frobenius numbers, we refer to the text of Ram\'{\i}rez Alfons\'in \cite{Alfonsin}. Let us return to the problem of determining $d(s;S)$. There is a simple greedy bound $$d(s;S) \geq \left\lceil \cfrac{s}{\max(S)} \right\rceil.$$ It seems natural to ask when this bound is tight. For a finite set $S \subseteq \mathbb{N}$, we can define the \textit{greedy Frobenius number} of $S$ (if it exists) to be the smallest integer $M$ such that $d(s;S) = \left\lceil \frac{s}{\max(S)}\right\rceil$ for all $s > M$. In other words, $M$ is the largest integer that cannot be written as a sum of $\left\lceil \frac{M}{\max(S)}\right\rceil$ elements from $S$. In this case, we write $\gFrob(S) = M$. If no such integer $M$ exists, we write $\gFrob(S) = \infty$. \begin{proposition} \label{prop:Frobgap} Let $S \subseteq \mathbb{N}$ be finite and nonempty, and let $m = \max(S)$. If $m \geq 2$ and $m-1 \notin S$, then $\gFrob(S) = \infty$. \end{proposition} \begin{proof} We claim that no positive integer $s$ with $s \equiv -1 \bmod m$ can be expressed as a sum of $\left\lceil \frac{s}{m} \right\rceil$ elements of $S$. This implies $\gFrob(S) = \infty$, because for any $M$ there exists an $s > M$ that cannot be written as a sum of $\left\lceil \frac{s}{m} \right\rceil$ elements from $S$. This claim is clear if $S = \{m\}$, as it is impossible to write any $s$ with $s \not\equiv 0 \bmod 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) = \infty$. 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 \equiv -1 \bmod m$ be sufficiently large that it can be expressed as a sum of elements from $S$. Write $s = qm-1$, so that $\left\lceil \frac{s}{m} \right\rceil = 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 \neq 0 \bmod m$, it must be the case that $a > 0$. By our assumption that $m-1 \notin S$, it must be the case that $$ qm-1 = s \leq a\cdot(m-2) + b \cdot m = (a+b) \cdot m - 2a < (a+b) \cdot m -1. $$ Therefore, $\left\lceil \frac{s}{m} \right\rceil = q < a+b = d(s;S)$. This means $s$ cannot be written as a sum of $\left\lceil \frac{s}{m} \right\rceil$ elements of $S$. \end{proof} As a converse to Proposition \ref{prop:Frobgap}, we can consider the simplest family of sets that do not violate the condition that $\max(S)-1 \notin S$, which are sets of the form $S = \{m-1,m\}$ for $m \geq 2$. \begin{proposition} \label{prop:Frobclassic} Let $m \geq 2$ and $S = \{m-1,m\}$. Then $$\gFrob(S) = (m-1)(m-2)-1 = \Frob(S).$$ \end{proposition} \begin{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 \cdot (m-1) + b \cdot m$. Then $a < m-2$, because $$ (m-1)(m-2)-1 = M \geq a\cdot (m-1). $$ On the other hand, $M \equiv 1 \bmod m$ and $a \cdot (m-1) + b \cdot m \equiv -a \bmod m$, so $a \equiv -1 \bmod m$. There is no nonnegative integer $a$ such that $a \equiv -1 \bmod 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 $\left\lceil \frac{s}{m}\right\rceil$ elements from $S$. We will prove the claim by showing any of the $m$ consecutive integers $(m-1)(m-2)+k$ for $0 \leq k \leq m-1$ can be expressed as such a sum. The claim follows immediately from this fact. For $0 \leq k \leq m-2$, the integer $(m-1)(m-2)+k$ can be written as $(m-2-k) \cdot (m-1) + k \cdot 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, $\left\lceil \frac{(m-1)(m-2)+k}{m}\right\rceil = 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, $\left\lceil \frac{(m-1)^2}{m} \right\rceil = m-1$. This completes the proof. \end{proof} Together, Proposition \ref{prop:Frobgap} and Proposition \ref{prop:Frobclassic} imply the following result. \begin{corollary} Let $S \subseteq \mathbb{N}$ be finite and nonempty with $m = \max(S)$. Then $\gFrob(S) < \infty$ if and only if $m=1$ or $m-1 \in S$. Moreover, if $m-1 \in S$, then $\gFrob(S) \leq (m-1)(m-2)-1$. \end{corollary} \begin{proof} The claim that $\gFrob(S) < \infty$ if and only if $m -1 \in S$ follows from Propositions \ref{prop:Frobgap} and \ref{prop:Frobclassic}. The bound $\gFrob(S) \leq \gFrob(\{m-1,m\}$ when $m-1 \in S$ is immediate, because $\gFrob(S) \leq \gFrob(T)$ whenever $T \subseteq S$. \end{proof} Now we return to our motivating example, which concerns sets of the form $S=\{1\} \cup N$. The simplest such sets for which $\gFrob(S) < \infty$ are those of the form $S = \{1,m-1,m\}$, for $m \geq 3$. However, the notation is cleaner if we write $S = \{1,n,n+1\}$ for some $n \geq 2$. \begin{theorem} \label{thm:nn+1Frobenius} Let $n \geq 2$ and $S = \{1,n,n+1\}$. Let $s \in \mathbb{N}$ and write $s = (n+1)q-r$ with $0 \leq r \leq n$, so that $\left\lceil \frac{s}{n+1} \right\rceil = q$. Then \begin{equation}\label{eq:n+1Frobenius} d(s;S) = \begin{cases} q, & \text{ if $r \leq q$ or $r=n$;} \\ q + (n-r), & \text{ if $qr$ to guarantee $n-r+1 \geq 0$ and the fact that $r>0$ to guarantee $q \geq 1$. So we are left to show $d(s;S) \geq 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 \begin{align*} 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). \end{align*} Now we note that $q+n-r < n$ because $qr$. This means $q+n-r$ is the remainder when $s$ is divided by $n$. Therefore, $a+c \geq q+n-r$ because $a+c \geq 0$ and $a+c \equiv q+n-r \bmod 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 \geq a+c \geq q+n-r.$$ This establishes Eq.\ \eqref{eq:n+1Frobenius}. In particular, setting $q = n-2$ and $r=n-1$ gives the largest value of $s$ for which $q n^2-2n-1 = (n-1)^2-2$. The sequence $a_k = k^2-2$ is \seqnum{A008865} in the OEIS \cite{oeis}. \end{proof} \section{Acknowledgments} We gratefully acknowledge support from the National Science Foundation. This research was supported by Grant DMS-1600048. \begin{thebibliography}{9} \bibitem{Bogart} Kenneth~P. Bogart, {\em Introductory Combinatorics}, 3rd edition, Harcourt/Academic Press, 2000. \bibitem{Mansour08} Eva Y.~P. Deng and Toufik Mansour, Three {H}oppy path problems and ternary paths, {\em Discrete Appl. Math.} {\bf 156} (2008), 770--779. \bibitem{EKM} Jackson Evoniuk, Steven Klee, and Van Magnan, Enumerating minimal length lattice paths, {\em J. Integer Sequences} {\bf 21} (2018), Article 18.3.6. \bibitem{Mansour06} Toufik Mansour, Combinatorial methods and recurrence relations with two indices, {\em J. Difference Equ. Appl.} {\bf 12} (2006), 555--563. \bibitem{Mansour07} Toufik Mansour, Recurrence relations with two indices and even trees, {\em J. Difference Equ. Appl.} {\bf 13} (2007), 47--61. \bibitem{Alfonsin} J.~L. Ram\'{\i}rez~Alfons\'{\i}n, {\em The {D}iophantine {F}robenius problem}, Vol.~30 of {\em Oxford Lecture Series in Mathematics and its Applications}, Oxford University Press, 2005. \bibitem{oeis} N.~J.~A. Sloane et al., {\em The {O}n-{L}ine {E}ncyclopedia of {I}nteger {S}equences}, 2020. \newblock Available at \url{https://oeis.org}. \bibitem{Sage} W.\thinspace{}A. Stein et~al., {\em {S}age {M}athematics {S}oftware ({V}ersion 8.8)}. \newblock The Sage Development Team, 2019. \newblock Available at \url{http://www.sagemath.org}. \bibitem{Sylvester} James~Joseph Sylvester, Question 7382, {\em Mathematical Questions from the Educational Times} {\bf 41} (1884), 21. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A19. \noindent \emph{Keywords:} lattice path enumeration, Frobenius problem. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000027}, \seqnum{A000290}, \seqnum{A006000}, \seqnum{A008865}, and \seqnum{A330601}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received January 16 2020; revised version received March 4 2020. Published in {\it Journal of Integer Sequences}, March 18 2020. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}