\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\usepackage{breakurl}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}


\usepackage{graphics,amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{tikz}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}

\DeclareMathOperator{\mbs}{\mathbf{s}}
\DeclareMathOperator{\dist}{d}

\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}
\newtheorem{question}[theorem]{Question}
\newtheorem{problem}[theorem]{Problem}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}



\begin{center}
\vskip 1cm{\Large \bf 
Enumerating Minimal Length Lattice Paths
}
\vskip 1cm
\large
Jackson Evoniuk, Steven Klee, and Van Magnan\\
Department of Mathematics\\
Seattle University\\
901 12th Avenue\\
Seattle, WA 98122 \\ 
USA\\
\href{mailto:evoniukj@seattleu.edu}{evoniukj@seattleu.edu}\\
\href{mailto:klees@seattleu.edu}{klees@seattleu.edu}\\
\href{mailto:magnanv@seattleu.edu}{magnanv@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 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$. 
\end{abstract}


\section{Introduction}
Let $S$ be a finite set of vectors in $\mathbb{Z}^2$.  An \textit{$S$-walk} is an ordered sequence $\mbs = s_1,s_2,\ldots, s_k$ of \textit{steps} with $s_i \in 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 + \cdots + s_k$.  We say the the number of steps in a path is its \textit{length}, and we refer to the elements of $S$ as \textit{allowable steps}.  

The problem of enumerating the  walks terminating at a fixed point $(a,b)$ with $a,b \in \mathbb{N}$ 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 $\mbs = (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 $\mbs' = (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 \ref{fig1}.

\begin{figure}[H]
\centering
\begin{tabular}{cc}
\begin{tikzpicture}
\draw[gray] (0,0) grid (6,5);
\filldraw[black] (5,4) circle (.1);
\draw[ultra thick, black] (0,0) -- (1,0) -- (2,0) -- (2,1) -- (3,2) -- (3,3) -- (4,3) -- (5,4);
\end{tikzpicture}
& 
\begin{tikzpicture}
\draw[gray] (0,0) grid (6,5);
\filldraw[black] (5,4) circle (.1);
\draw[ultra thick, black] (0,0) -- (1,1) -- (2,1) -- (5,4);
\end{tikzpicture}
\end{tabular}
\caption{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)\}$.}
\label{fig1}
\end{figure}

Our goal in this paper is to enumerate the \textit{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 $\dist(a,b;S)$ to denote the \textit{$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 $\dist(5,4;S) \geq 5$.  Therefore,  $\mbs'$ is minimal because it is an $S$-walk of length 5.  In contrast, $\mbs$ is not minimal.  In general, we write  $\mathcal{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 $|\mathcal{W}(a,b;S)|$.  

The rest of the paper is structured as follows.  In Section \ref{sec2}, we warm up with the case that $S = \{(1,0), (0,1), (1,1)\}$.  In Section \ref{sec3}, we consider the sets $$Q_n:= \{(1,0), (0,1)\} \cup \{(i,n-i) \ : \ 0 \leq i \leq n\},$$ consisting of the standard basis vectors along with all nonnegative integer vectors whose coordinate sum equals $n$ for $n \geq 2$.  We include the standard basis vectors to ensure that every point $(a,b)$ with $a,b \in \mathbb{N}$ 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 \mathbb{N}$ in Section \ref{sec4}.  In Section \ref{sec5}, we explore the case that $S = \{(1,0), (0,1), (2,1), (1,2)\}$.  We conclude in Section \ref{sec6} with some open problems. 




\section{Minimal walks for $S = \{(1,0), (0,1), (1,1)\}$} \label{sec2}

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 \cite{sage} 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 \ref{100111data}.  For example, the circled 20 indicates that there are 20 minimal $S$-paths terminating at the point $(6,3)$.


\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=.8]
\draw (6,3) circle (.3);
\draw(0,0) node {\small{1}}; 
\draw(0,1) node {\small{1}}; 
\draw(0,2) node {\small{1}}; 
\draw(0,3) node {\small{1}}; 
\draw(0,4) node {\small{1}}; 
\draw(0,5) node {\small{1}}; 
\draw(0,6) node {\small{1}}; 
\draw(0,7) node {\small{1}}; 
\draw(0,8) node {\small{1}}; 
\draw(0,9) node {\small{1}}; 
\draw(0,10) node {\small{1}}; 
\draw(1,0) node {\small{1}}; 
\draw(1,1) node {\small{1}}; 
\draw(1,2) node {\small{2}}; 
\draw(1,3) node {\small{3}}; 
\draw(1,4) node {\small{4}}; 
\draw(1,5) node {\small{5}}; 
\draw(1,6) node {\small{6}}; 
\draw(1,7) node {\small{7}}; 
\draw(1,8) node {\small{8}}; 
\draw(1,9) node {\small{9}}; 
\draw(1,10) node {\small{10}}; 
\draw(2,0) node {\small{1}}; 
\draw(2,1) node {\small{2}}; 
\draw(2,2) node {\small{1}}; 
\draw(2,3) node {\small{3}}; 
\draw(2,4) node {\small{6}}; 
\draw(2,5) node {\small{10}}; 
\draw(2,6) node {\small{15}}; 
\draw(2,7) node {\small{21}}; 
\draw(2,8) node {\small{28}}; 
\draw(2,9) node {\small{36}}; 
\draw(2,10) node {\small{45}}; 
\draw(3,0) node {\small{1}}; 
\draw(3,1) node {\small{3}}; 
\draw(3,2) node {\small{3}}; 
\draw(3,3) node {\small{1}}; 
\draw(3,4) node {\small{4}}; 
\draw(3,5) node {\small{10}}; 
\draw(3,6) node {\small{20}}; 
\draw(3,7) node {\small{35}}; 
\draw(3,8) node {\small{56}}; 
\draw(3,9) node {\small{84}}; 
\draw(3,10) node {\small{120}}; 
\draw(4,0) node {\small{1}}; 
\draw(4,1) node {\small{4}}; 
\draw(4,2) node {\small{6}}; 
\draw(4,3) node {\small{4}}; 
\draw(4,4) node {\small{1}}; 
\draw(4,5) node {\small{5}}; 
\draw(4,6) node {\small{15}}; 
\draw(4,7) node {\small{35}}; 
\draw(4,8) node {\small{70}}; 
\draw(4,9) node {\small{126}}; 
\draw(4,10) node {\small{210}}; 
\draw(5,0) node {\small{1}}; 
\draw(5,1) node {\small{5}}; 
\draw(5,2) node {\small{10}}; 
\draw(5,3) node {\small{10}}; 
\draw(5,4) node {\small{5}}; 
\draw(5,5) node {\small{1}}; 
\draw(5,6) node {\small{6}}; 
\draw(5,7) node {\small{21}}; 
\draw(5,8) node {\small{56}}; 
\draw(5,9) node {\small{126}}; 
\draw(5,10) node {\small{252}}; 
\draw(6,0) node {\small{1}}; 
\draw(6,1) node {\small{6}}; 
\draw(6,2) node {\small{15}}; 
\draw(6,3) node {\small{20}}; 
\draw(6,4) node {\small{15}}; 
\draw(6,5) node {\small{6}}; 
\draw(6,6) node {\small{1}}; 
\draw(6,7) node {\small{7}}; 
\draw(6,8) node {\small{28}}; 
\draw(6,9) node {\small{84}}; 
\draw(6,10) node {\small{210}}; 
\draw(7,0) node {\small{1}}; 
\draw(7,1) node {\small{7}}; 
\draw(7,2) node {\small{21}}; 
\draw(7,3) node {\small{35}}; 
\draw(7,4) node {\small{35}}; 
\draw(7,5) node {\small{21}}; 
\draw(7,6) node {\small{7}}; 
\draw(7,7) node {\small{1}}; 
\draw(7,8) node {\small{8}}; 
\draw(7,9) node {\small{36}}; 
\draw(7,10) node {\small{120}}; 
\draw(8,0) node {\small{1}}; 
\draw(8,1) node {\small{8}}; 
\draw(8,2) node {\small{28}}; 
\draw(8,3) node {\small{56}}; 
\draw(8,4) node {\small{70}}; 
\draw(8,5) node {\small{56}}; 
\draw(8,6) node {\small{28}}; 
\draw(8,7) node {\small{8}}; 
\draw(8,8) node {\small{1}}; 
\draw(8,9) node {\small{9}}; 
\draw(8,10) node {\small{45}}; 
\draw(9,0) node {\small{1}}; 
\draw(9,1) node {\small{9}}; 
\draw(9,2) node {\small{36}}; 
\draw(9,3) node {\small{84}}; 
\draw(9,4) node {\small{126}}; 
\draw(9,5) node {\small{126}}; 
\draw(9,6) node {\small{84}}; 
\draw(9,7) node {\small{36}}; 
\draw(9,8) node {\small{9}}; 
\draw(9,9) node {\small{1}}; 
\draw(9,10) node {\small{10}}; 
\draw(10,0) node {\small{1}}; 
\draw(10,1) node {\small{10}}; 
\draw(10,2) node {\small{45}}; 
\draw(10,3) node {\small{120}}; 
\draw(10,4) node {\small{210}}; 
\draw(10,5) node {\small{252}}; 
\draw(10,6) node {\small{210}}; 
\draw(10,7) node {\small{120}}; 
\draw(10,8) node {\small{45}}; 
\draw(10,9) node {\small{10}}; 
\draw(10,10) node {\small{1}}; 

\draw (-1,-.25) -- (10.5,-.25);
\draw (-.25,-1) -- (-.25,10.5);
\draw (-1,-1) -- (-.25,-.25);
\draw (-.5,-.75) node {\footnotesize $a$};
\draw (-.75,-.5) node {\footnotesize $b$};
\foreach \i in {0,...,10}{
\draw (-.75,\i) node {\small \i};
\draw (\i,-.75) node {\small \i};
}
\end{tikzpicture}
\label{100111data}
\caption{The number of minimal $S$-walks terminating at each point $(a,b)$ for $0 \leq a,b \leq 10$ and $S = \{(1,0), (0,1), (1,1)\}$.} 
\end{figure}

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

\begin{theorem}
Let $S = \{(1,0), (0,1), (1,1)\}$ and let $(a,b)$ be a point with $a,b \in \mathbb{N}$.  Then $|\mathcal{W}(a,b;S)| = \binom{\max(a,b)}{\min(a,b)}$. 
\end{theorem}

\begin{proof}
By symmetry, we may assume without loss of generality that $a \geq b$.  Note that $\dist(a,b;S) \geq a$ since an allowable step in $S$ increases the $x$-coordinate by at most $1$.  Conversely, $\dist(a,b;S) \leq 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 $\dist(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.

\end{proof}

\section{Minimal walks for steps of fixed length} \label{sec3}

Our next goal is to consider the set of allowable steps $$Q_n:= \{(1,0), (0,1)\} \cup \{(i,n-i) \ : \ 0 \leq i \leq n\},$$ for $n \geq 2$.  For example, $Q_3 = \{(1,0), (0,1), (0,3), (1,2), (2,1), (3,0)\}$, and Figure \ref{fig:q3} 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 \seqnum{A292435}.

\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=.9]
\draw(0,0) node {\footnotesize{1}}; 
\draw(0,1) node {\footnotesize{1}}; 
\draw(0,2) node {\footnotesize{1}}; 
\draw(0,3) node {\footnotesize{1}}; 
\draw(0,4) node {\footnotesize{2}}; 
\draw(0,5) node {\footnotesize{3}}; 
\draw(0,6) node {\footnotesize{1}}; 
\draw(0,7) node {\footnotesize{3}}; 
\draw(0,8) node {\footnotesize{6}}; 
\draw(0,9) node {\footnotesize{1}}; 
\draw(0,10) node {\footnotesize{4}}; 
\draw(1,0) node {\footnotesize{1}}; 
\draw(1,1) node {\footnotesize{2}}; 
\draw(1,2) node {\footnotesize{1}}; 
\draw(1,3) node {\footnotesize{4}}; 
\draw(1,4) node {\footnotesize{9}}; 
\draw(1,5) node {\footnotesize{2}}; 
\draw(1,6) node {\footnotesize{9}}; 
\draw(1,7) node {\footnotesize{24}}; 
\draw(1,8) node {\footnotesize{3}}; 
\draw(1,9) node {\footnotesize{16}}; 
\draw(1,10) node {\footnotesize{50}}; 
\draw(2,0) node {\footnotesize{1}}; 
\draw(2,1) node {\footnotesize{1}}; 
\draw(2,2) node {\footnotesize{4}}; 
\draw(2,3) node {\footnotesize{12}}; 
\draw(2,4) node {\footnotesize{3}}; 
\draw(2,5) node {\footnotesize{15}}; 
\draw(2,6) node {\footnotesize{48}}; 
\draw(2,7) node {\footnotesize{6}}; 
\draw(2,8) node {\footnotesize{36}}; 
\draw(2,9) node {\footnotesize{130}}; 
\draw(2,10) node {\footnotesize{10}}; 
\draw(3,0) node {\footnotesize{1}}; 
\draw(3,1) node {\footnotesize{4}}; 
\draw(3,2) node {\footnotesize{12}}; 
\draw(3,3) node {\footnotesize{4}}; 
\draw(3,4) node {\footnotesize{21}}; 
\draw(3,5) node {\footnotesize{72}}; 
\draw(3,6) node {\footnotesize{10}}; 
\draw(3,7) node {\footnotesize{64}}; 
\draw(3,8) node {\footnotesize{250}}; 
\draw(3,9) node {\footnotesize{20}}; 
\draw(3,10) node {\footnotesize{150}}; 
\draw(4,0) node {\footnotesize{2}}; 
\draw(4,1) node {\footnotesize{9}}; 
\draw(4,2) node {\footnotesize{3}}; 
\draw(4,3) node {\footnotesize{21}}; 
\draw(4,4) node {\footnotesize{84}}; 
\draw(4,5) node {\footnotesize{12}}; 
\draw(4,6) node {\footnotesize{88}}; 
\draw(4,7) node {\footnotesize{380}}; 
\draw(4,8) node {\footnotesize{31}}; 
\draw(4,9) node {\footnotesize{255}}; 
\draw(4,10) node {\footnotesize{1215}}; 
\draw(5,0) node {\footnotesize{3}}; 
\draw(5,1) node {\footnotesize{2}}; 
\draw(5,2) node {\footnotesize{15}}; 
\draw(5,3) node {\footnotesize{72}}; 
\draw(5,4) node {\footnotesize{12}}; 
\draw(5,5) node {\footnotesize{96}}; 
\draw(5,6) node {\footnotesize{460}}; 
\draw(5,7) node {\footnotesize{40}}; 
\draw(5,8) node {\footnotesize{355}}; 
\draw(5,9) node {\footnotesize{1830}}; 
\draw(5,10) node {\footnotesize{101}}; 
\draw(6,0) node {\footnotesize{1}}; 
\draw(6,1) node {\footnotesize{9}}; 
\draw(6,2) node {\footnotesize{48}}; 
\draw(6,3) node {\footnotesize{10}}; 
\draw(6,4) node {\footnotesize{88}}; 
\draw(6,5) node {\footnotesize{460}}; 
\draw(6,6) node {\footnotesize{44}}; 
\draw(6,7) node {\footnotesize{420}}; 
\draw(6,8) node {\footnotesize{2325}}; 
\draw(6,9) node {\footnotesize{135}}; 
\draw(6,10) node {\footnotesize{1416}}; 
\draw(7,0) node {\footnotesize{3}}; 
\draw(7,1) node {\footnotesize{24}}; 
\draw(7,2) node {\footnotesize{6}}; 
\draw(7,3) node {\footnotesize{64}}; 
\draw(7,4) node {\footnotesize{380}}; 
\draw(7,5) node {\footnotesize{40}}; 
\draw(7,6) node {\footnotesize{420}}; 
\draw(7,7) node {\footnotesize{2520}}; 
\draw(7,8) node {\footnotesize{155}}; 
\draw(7,9) node {\footnotesize{1740}}; 
\draw(7,10) node {\footnotesize{11046}}; 
\draw(8,0) node {\footnotesize{6}}; 
\draw(8,1) node {\footnotesize{3}}; 
\draw(8,2) node {\footnotesize{36}}; 
\draw(8,3) node {\footnotesize{250}}; 
\draw(8,4) node {\footnotesize{31}}; 
\draw(8,5) node {\footnotesize{355}}; 
\draw(8,6) node {\footnotesize{2325}}; 
\draw(8,7) node {\footnotesize{155}}; 
\draw(8,8) node {\footnotesize{1860}}; 
\draw(8,9) node {\footnotesize{12600}}; 
\draw(8,10) node {\footnotesize{546}}; 
\draw(9,0) node {\footnotesize{1}}; 
\draw(9,1) node {\footnotesize{16}}; 
\draw(9,2) node {\footnotesize{130}}; 
\draw(9,3) node {\footnotesize{20}}; 
\draw(9,4) node {\footnotesize{255}}; 
\draw(9,5) node {\footnotesize{1830}}; 
\draw(9,6) node {\footnotesize{135}}; 
\draw(9,7) node {\footnotesize{1740}}; 
\draw(9,8) node {\footnotesize{12600}}; 
\draw(9,9) node {\footnotesize{580}}; 
\draw(9,10) node {\footnotesize{7882}}; 
\draw(10,0) node {\footnotesize{4}}; 
\draw(10,1) node {\footnotesize{50}}; 
\draw(10,2) node {\footnotesize{10}}; 
\draw(10,3) node {\footnotesize{150}}; 
\draw(10,4) node {\footnotesize{1215}}; 
\draw(10,5) node {\footnotesize{101}}; 
\draw(10,6) node {\footnotesize{1416}}; 
\draw(10,7) node {\footnotesize{11046}}; 
\draw(10,8) node {\footnotesize{546}}; 
\draw(10,9) node {\footnotesize{7882}}; 
\draw(10,10) node {\footnotesize{63056}}; 

\draw (-1,-.25) -- (10.5,-.25);
\draw (-.25,-1) -- (-.25,10.5);
\draw (-1,-1) -- (-.25,-.25);
\draw (-.5,-.75) node {\footnotesize $a$};
\draw (-.75,-.5) node {\footnotesize $b$};
\foreach \i in {0,...,10}{
\draw (-2/3,\i) node {\footnotesize \i};
\draw (\i,-2/3) node {\footnotesize \i};
}
\end{tikzpicture}
\label{fig:q3}
\caption{The number of minimal $Q_3$-walks terminating at each point $(a,b)$ for $0 \leq a,b \leq 10$.}

\end{figure}


In Figure \ref{fig:q3}, we observe an interesting phenomenon.  If we fix a value $m = 3q+r$ with $0 \leq 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 \cdot 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)$ \textit{short} steps and the remaining steps of the form $(i,n-i)$ \textit{long} steps.  

\begin{lemma} \label{qlongrshort}
Let $a,b \in \mathbb{N}$ and write $a+b = n \cdot q + r$ with $0 \leq r < n$.  Then any minimal $Q_n$-walk terminating at $(a,b)$ uses exactly $q$ long steps and $r$ short steps.  Consequently, $\dist(a,b;Q_n) = q+r$. 
\end{lemma}

\begin{proof}
Let $\mbs$ be a  (not necessarily minimal) $Q_n$-walk terminating at $(a,b)$, and suppose $\mbs$ uses $q'$ long steps and $r'$ short steps.  If $r' \geq 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 $\mbs$.  We can simply remove them from $\mbs$ 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 $\mbs$ is a minimal $Q_n$-walk, then $r'  < n$.  By taking the vector sum of every step in $\mbs$, we see that $a+b = n \cdot q' + r'$.  Since the quotient and remainder in the division algorithm are unique, we must have $q' = q$ and $r' = r$, meaning $\mbs$ uses $q$ long steps and $r$ short steps. 
\end{proof}

Let $(a,b) \in \mathbb{N}^2$ and write $a+b = q\cdot n +r$ with $0 \leq r < n$.  We can now use Lemma \ref{qlongrshort} to see why $|\mathcal{W}(a,b;Q_n)|$ is divisible by $\binom{q+r}{r}$.  We can partition $\mathcal{W}(a,b;Q_n)$ into equivalence classes by declaring $\mbs \sim \mbs'$ if (1) $\mbs$ and $\mbs'$ 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 $\mbs$ is the same as that in $\mbs'$.  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 $\mbs$ 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. 

\begin{theorem}
For all $n \geq 2$, the number of minimal $Q_n$-walks can be computed by the generating function 
\begin{equation} \label{Sngenfun}
\sum_{(a,b) \in \mathbb{N}^2} |\mathcal{W}(a,b;Q_n)| x^ay^b = \sum_{q=0}^{\infty} \sum_{r=0}^{n-1} \binom{q+r}{r}\left(\sum_{i=0}^n x^iy^{n-i}\right)^q(x+y)^r.
\end{equation}
\end{theorem}

\begin{proof}
For fixed $q$ and $r$, let $\sigma = n\cdot q+r$. Expanding $\left(\sum_{i=0}^n x^iy^{n-i}\right)^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 = \sigma$. 
\end{proof}

\section{Minimal walks for $S = \{(1,0), (0,1), (u,v)\}$} \label{sec4}

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

Given a point $(a,b) \in \mathbb{N}^2$, let $m = m(a,b) = \min (\lfloor \frac{a}{u} \rfloor, \lfloor \frac{b}{v} \rfloor )$. Concretely, $m$ is the largest integer such that $m \cdot u \leq a$ and $m \cdot v \leq 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)$. 

\begin{theorem} \label{arbitrary-uv}
Let $S = \{(1,0), (0,1), (u,v)\}$ with $u,v \geq 1$, and let $(a,b) \in \mathbb{N}^2$. A minimal $S$-walk to the point $(a,b)$ uses exactly $m$ steps in the $(u,v)$-direction.  Consequently, $$\dist(a,b;S) = m + a-m\cdot u + b-m \cdot v,$$ and $$|\mathcal{W}(a,b;S)| = \binom{m+a-m\cdot u + b-m \cdot v}{m,a-m \cdot u, b-m \cdot v}.$$
\end{theorem}

\begin{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' \cdot u  + x \leq (m-1) \cdot u + x = m\cdot u + x-u \leq a + x-u,$$ it follows that $x \geq u$.  Similarly, $y \geq v$. Since $x \geq u$ and $y \geq 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 \cdot u$ steps in the $(1,0)$-direction and $b-m \cdot v$ steps in the $(0,1)$-direction.  This immediately implies the stated formulas for the distance and number of minimal $S$-walks.  


\end{proof} 

\begin{remark}
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 \ref{arbitrary-uv} generalizes the results in Section \ref{sec2}.
\end{remark}



\section{Minimal walks for $\overline{Q}_3 = \{(1,0), (0,1), (2,1), (1,2)\}$} \label{sec5}

Recall that in Section \ref{sec3}, 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 \cite{oeis} and seems interesting in its own right.  We have since added this data to OEIS as sequence \seqnum{A292436}.


Figure \ref{fig:q3barb} 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 \ref{fig:q3barb}.

\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=.9]
\draw[dashed] (0,0) -- (10,5);
\draw[dashed] (0,0) -- (5,10);
\draw(0,0) node {\footnotesize{1}}; 
\draw(0,1) node {\footnotesize{1}}; 
\draw(0,2) node {\footnotesize{1}}; 
\draw(0,3) node {\footnotesize{1}}; 
\draw(0,4) node {\footnotesize{1}}; 
\draw(0,5) node {\footnotesize{1}}; 
\draw(0,6) node {\footnotesize{1}}; 
\draw(0,7) node {\footnotesize{1}}; 
\draw(0,8) node {\footnotesize{1}}; 
\draw(0,9) node {\footnotesize{1}}; 
\draw(0,10) node {\footnotesize{1}}; 
\draw(1,0) node {\footnotesize{1}}; 
\draw(1,1) node {\footnotesize{2}}; 
\draw(1,2) node {\footnotesize{1}}; 
\draw(1,3) node {\footnotesize{2}}; 
\draw(1,4) node {\footnotesize{3}}; 
\draw(1,5) node {\footnotesize{4}}; 
\draw(1,6) node {\footnotesize{5}}; 
\draw(1,7) node {\footnotesize{6}}; 
\draw(1,8) node {\footnotesize{7}}; 
\draw(1,9) node {\footnotesize{8}}; 
\draw(1,10) node {\footnotesize{9}}; 
\draw(2,0) node {\footnotesize{1}}; 
\draw(2,1) node {\footnotesize{1}}; 
\draw(2,2) node {\footnotesize{4}}; 
\draw(2,3) node {\footnotesize{9}}; 
\draw(2,4) node {\footnotesize{1}}; 
\draw(2,5) node {\footnotesize{3}}; 
\draw(2,6) node {\footnotesize{6}}; 
\draw(2,7) node {\footnotesize{10}}; 
\draw(2,8) node {\footnotesize{15}}; 
\draw(2,9) node {\footnotesize{21}}; 
\draw(2,10) node {\footnotesize{28}}; 
\draw(3,0) node {\footnotesize{1}}; 
\draw(3,1) node {\footnotesize{2}}; 
\draw(3,2) node {\footnotesize{9}}; 
\draw(3,3) node {\footnotesize{2}}; 
\draw(3,4) node {\footnotesize{9}}; 
\draw(3,5) node {\footnotesize{24}}; 
\draw(3,6) node {\footnotesize{1}}; 
\draw(3,7) node {\footnotesize{4}}; 
\draw(3,8) node {\footnotesize{10}}; 
\draw(3,9) node {\footnotesize{20}}; 
\draw(3,10) node {\footnotesize{35}}; 
\draw(4,0) node {\footnotesize{1}}; 
\draw(4,1) node {\footnotesize{3}}; 
\draw(4,2) node {\footnotesize{1}}; 
\draw(4,3) node {\footnotesize{9}}; 
\draw(4,4) node {\footnotesize{36}}; 
\draw(4,5) node {\footnotesize{3}}; 
\draw(4,6) node {\footnotesize{16}}; 
\draw(4,7) node {\footnotesize{50}}; 
\draw(4,8) node {\footnotesize{1}}; 
\draw(4,9) node {\footnotesize{5}}; 
\draw(4,10) node {\footnotesize{15}}; 
\draw(5,0) node {\footnotesize{1}}; 
\draw(5,1) node {\footnotesize{4}}; 
\draw(5,2) node {\footnotesize{3}}; 
\draw(5,3) node {\footnotesize{24}}; 
\draw(5,4) node {\footnotesize{3}}; 
\draw(5,5) node {\footnotesize{24}}; 
\draw(5,6) node {\footnotesize{100}}; 
\draw(5,7) node {\footnotesize{4}}; 
\draw(5,8) node {\footnotesize{25}}; 
\draw(5,9) node {\footnotesize{90}}; 
\draw(5,10) node {\footnotesize{1}}; 
\draw(6,0) node {\footnotesize{1}}; 
\draw(6,1) node {\footnotesize{5}}; 
\draw(6,2) node {\footnotesize{6}}; 
\draw(6,3) node {\footnotesize{1}}; 
\draw(6,4) node {\footnotesize{16}}; 
\draw(6,5) node {\footnotesize{100}}; 
\draw(6,6) node {\footnotesize{6}}; 
\draw(6,7) node {\footnotesize{50}}; 
\draw(6,8) node {\footnotesize{225}}; 
\draw(6,9) node {\footnotesize{5}}; 
\draw(6,10) node {\footnotesize{36}}; 
\draw(7,0) node {\footnotesize{1}}; 
\draw(7,1) node {\footnotesize{6}}; 
\draw(7,2) node {\footnotesize{10}}; 
\draw(7,3) node {\footnotesize{4}}; 
\draw(7,4) node {\footnotesize{50}}; 
\draw(7,5) node {\footnotesize{4}}; 
\draw(7,6) node {\footnotesize{50}}; 
\draw(7,7) node {\footnotesize{300}}; 
\draw(7,8) node {\footnotesize{10}}; 
\draw(7,9) node {\footnotesize{90}}; 
\draw(7,10) node {\footnotesize{441}}; 
\draw(8,0) node {\footnotesize{1}}; 
\draw(8,1) node {\footnotesize{7}}; 
\draw(8,2) node {\footnotesize{15}}; 
\draw(8,3) node {\footnotesize{10}}; 
\draw(8,4) node {\footnotesize{1}}; 
\draw(8,5) node {\footnotesize{25}}; 
\draw(8,6) node {\footnotesize{225}}; 
\draw(8,7) node {\footnotesize{10}}; 
\draw(8,8) node {\footnotesize{120}}; 
\draw(8,9) node {\footnotesize{735}}; 
\draw(8,10) node {\footnotesize{15}}; 
\draw(9,0) node {\footnotesize{1}}; 
\draw(9,1) node {\footnotesize{8}}; 
\draw(9,2) node {\footnotesize{21}}; 
\draw(9,3) node {\footnotesize{20}}; 
\draw(9,4) node {\footnotesize{5}}; 
\draw(9,5) node {\footnotesize{90}}; 
\draw(9,6) node {\footnotesize{5}}; 
\draw(9,7) node {\footnotesize{90}}; 
\draw(9,8) node {\footnotesize{735}}; 
\draw(9,9) node {\footnotesize{20}}; 
\draw(9,10) node {\footnotesize{245}}; 
\draw(10,0) node {\footnotesize{1}}; 
\draw(10,1) node {\footnotesize{9}}; 
\draw(10,2) node {\footnotesize{28}}; 
\draw(10,3) node {\footnotesize{35}}; 
\draw(10,4) node {\footnotesize{15}}; 
\draw(10,5) node {\footnotesize{1}}; 
\draw(10,6) node {\footnotesize{36}}; 
\draw(10,7) node {\footnotesize{441}}; 
\draw(10,8) node {\footnotesize{15}}; 
\draw(10,9) node {\footnotesize{245}}; 
\draw(10,10) node {\footnotesize{1960}}; 

\draw (-1,-.25) -- (10.5,-.25);
\draw (-.25,-1) -- (-.25,10.5);
\draw (-1,-1) -- (-.25,-.25);
\draw (-.5,-.75) node {\footnotesize $a$};
\draw (-.75,-.5) node {\footnotesize $b$};
\foreach \i in {0,...,10}{
\draw (-2/3,\i) node {\footnotesize \i};
\draw (\i,-2/3) node {\footnotesize \i};
}
\end{tikzpicture}
\caption{The number of minimal $\overline{Q}_3$-walks terminating at each point $(a,b)$ for $0 \leq a,b \leq 10$.}
\label{fig:q3barb}
\end{figure}



We begin by establishing some notation that will be used throughout the proofs in this section.  Given a point $(a,b) \in \mathbb{N}^2$, consider a minimal $\overline{Q}_3$-walk, $\mbs$, 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 $\mbs$.  Thus 
\begin{equation} \label{eq:q3bar-linalg}
a = x+2z+w \qquad \text{and} \qquad b = y+z+2w.
\end{equation}  
As in Section \ref{sec3}, we will refer to the steps $(2,1)$ and $(1,2)$ in $\overline{Q}_3$ as \textit{long} steps and the steps $(1,0)$ and $(0,1)$ as \textit{short} steps.  

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

\begin{theorem}
Let $(a,b) \in \mathbb{N}^2$ with $a \geq 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, $$\dist(a,b;\overline{Q}_3) = a-b$$ and $$|\mathcal{W}(a,b;\overline{Q}_3)| = \binom{a-b}{b}.$$
\end{theorem}

\begin{proof}
Consider a minimal $\overline{Q}_3$-walk, $\mbs$, 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 \geq 2b$, it follows from Eq.~\eqref{eq:q3bar-linalg} that $x \geq 2y+3w.$  Therefore, if $y \geq 1$, then $x \geq 2$.  So if $\mbs$ 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 \geq 1$, then $x \geq 3$.  So if $\mbs$ 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.~\eqref{eq:q3bar-linalg} reduces to 
$$a = x+2z \qquad \text{and} \qquad b = z,$$ which is equivalent to $x = a-2b$ (which is nonnegative since $a \geq 2b$) and $z=b$.  Since $x+z$ is the total number of steps in $\mbs$, it follows that $\dist(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.
\end{proof}

Since $\overline{Q}_3$ is symmetric, the following corollary immediately handles the case that $b \geq 2a$.

\begin{corollary}
Let $(a,b) \in \mathbb{N}^2$ with $b \geq 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, $\dist(a,b;\overline{Q}_3) = b-a$ and $|\mathcal{W}(a,b;\overline{Q}_3)| = \binom{b-a}{a}$.
\end{corollary}

Now we turn our attention to the case that $(a,b)$ lies in the central region of Figure \ref{fig:q3barb}.

\begin{lemma} \label{q3bar-shortsteps}
Let $(a,b) \in \mathbb{N}^2$ with $\frac{1}{2}b \leq a \leq 2b$.  A minimal $\overline{Q}_3$-walk terminating at $(a,b)$ uses at most two short steps.
\end{lemma}

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

If $x \geq 2$ and $y \geq 1$ (or if $x \geq 1$ and $y \geq 2$), then $\mbs$ 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 \geq 3$ and $y=0$.  By symmetry, this will cover the case that $x=0$ and $y \geq 3$. 

Since $a \leq 2b$, it follows from Eq.~\eqref{eq:q3bar-linalg} that  $x \leq 2y + 3w$.  Since $y=0$ and $x \geq 3$, it follows that $w \geq 1$.  Thus $\mbs$ 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 $\mbs$ is minimal.  
\end{proof}

\begin{theorem}
Let $(a,b) \in \mathbb{N}^2$ with $\frac{1}{2}b \leq a \leq 2b$, and write $a+b = 3q+r$ with $0 \leq r \leq 2$.  Then $$\dist(a,b;\overline{Q}_3) = q+r$$ and $$|\mathcal{W}(a,b;\overline{Q}_3)| = \binom{q+r}{r}\binom{q+r}{a-q}.$$
\end{theorem}

\begin{proof}
As before, consider a minimal $\overline{Q}_3$-walk, $\mbs$, terminating at the point $(a,b)$.  Let $x,y,z,$ and $w$ be as defined above.  By Eq.~\eqref{eq:q3bar-linalg}, $a+b = x+y + 3(z+w)$.  By Lemma \ref{q3bar-shortsteps}, $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 $\mbs$, and hence $\dist(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 $\mbs$ be such a walk.  We know $\mbs$ uses $r$ short steps.  Define a new $\overline{Q}_3$-walk $\hat{\mbs}$ as follows: replace each $(1,0)$-step in $\mbs$ with a $(2,1)$-step and replace each $(0,1)$-step in $\mbs$ with a $(1,2)$-step. Note that $\hat{\mbs}$ is a $\overline{Q}_3$-walk that only uses long steps. Moreover, $\hat{\mbs}$ terminates at the point $(a+r,b+r)$ as each replacement increases the vector sum by $(1,1)$. 

Now let $\hat{w}$ and $\hat{z}$ respectively denote the number of $(2,1)$- and $(1,2)$-steps in $\hat{\mbs}$. Applying Eq.~\eqref{eq:q3bar-linalg} to $\hat{\mbs}$ gives rise to the system of equations 
\begin{eqnarray*}
2\hat{z}+\hat{w} &=& a+r\\
\hat{z}+2\hat{w} &=& b+r.
\end{eqnarray*}
The coefficient matrix $\begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$ is invertible, so this system has a unique solution.  We can easily verify that
\begin{eqnarray*}
\hat{z} &=& a-q \\
\hat{w} &=& b-q
\end{eqnarray*}
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 \leq a \leq 2b$.  Indeed, $3q+r = a+b \leq a+2a$, and hence $3(a-q) \geq r \geq 0$.  The same logic shows $3(b-q) \geq r \geq 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 = \dist(a,b;\overline{Q}_3)$. Thus $|\mathcal{W}(a,b;\overline{Q}_3)| = \binom{q+r}{r}\binom{q+r}{a-q},$ as desired.
\end{proof}


\section{Open problems} \label{sec6}

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



Based on the results in Section \ref{sec5}, 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 \geq 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 $\mathbb{N}$-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 $\mathbb{N}$-span of $\{(u,v),(v,u)\}$ that lies
weakly south and west of $(a,b)$ and filling in the rest of the walk\hfill
\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=.85]
\draw[dashed] (0,0) -- (0+3,0+5);
\draw[dashed] (0,0) -- (0+5,0+3);

\draw[dashed] (3,5) -- (3+3,5+5);
\draw[dashed] (3,5) -- (3+5,5+3);

\draw[dashed] (5,3) -- (5+3,3+5);
\draw[dashed] (5,3) -- (5+5,3+3);

\draw[dashed] (6,10) -- (6+3,10+5);
\draw[dashed] (6,10) -- (6+5,10+3);

\draw[dashed] (10,6) -- (10+3,6+5);
\draw[dashed] (10,6) -- (10+5,6+3);

\draw[dashed] (8,8) -- (8+3,8+5);
\draw[dashed] (8,8) -- (8+5,8+3);

\draw(0,0) node {\footnotesize{0}}; 
\draw(0,1) node {\footnotesize{1}}; 
\draw(0,2) node {\footnotesize{2}}; 
\draw(0,3) node {\footnotesize{3}}; 
\draw(0,4) node {\footnotesize{4}}; 
\draw(0,5) node {\footnotesize{5}}; 
\draw(0,6) node {\footnotesize{6}}; 
\draw(0,7) node {\footnotesize{7}}; 
\draw(0,8) node {\footnotesize{8}}; 
\draw(0,9) node {\footnotesize{9}}; 
\draw(0,10) node {\footnotesize{10}}; 
\draw(0,11) node {\footnotesize{11}}; 
\draw(0,12) node {\footnotesize{12}}; 
\draw(0,13) node {\footnotesize{13}}; 
\draw(0,14) node {\footnotesize{14}}; 
\draw(0,15) node {\footnotesize{15}}; 
\draw(1,0) node {\footnotesize{1}}; 
\draw(1,1) node {\footnotesize{2}}; 
\draw(1,2) node {\footnotesize{3}}; 
\draw(1,3) node {\footnotesize{4}}; 
\draw(1,4) node {\footnotesize{5}}; 
\draw(1,5) node {\footnotesize{6}}; 
\draw(1,6) node {\footnotesize{7}}; 
\draw(1,7) node {\footnotesize{8}}; 
\draw(1,8) node {\footnotesize{9}}; 
\draw(1,9) node {\footnotesize{10}}; 
\draw(1,10) node {\footnotesize{11}}; 
\draw(1,11) node {\footnotesize{12}}; 
\draw(1,12) node {\footnotesize{13}}; 
\draw(1,13) node {\footnotesize{14}}; 
\draw(1,14) node {\footnotesize{15}}; 
\draw(1,15) node {\footnotesize{16}}; 
\draw(2,0) node {\footnotesize{2}}; 
\draw(2,1) node {\footnotesize{3}}; 
\draw(2,2) node {\footnotesize{4}}; 
\draw(2,3) node {\footnotesize{5}}; 
\draw(2,4) node {\footnotesize{6}}; 
\draw(2,5) node {\footnotesize{7}}; 
\draw(2,6) node {\footnotesize{8}}; 
\draw(2,7) node {\footnotesize{9}}; 
\draw(2,8) node {\footnotesize{10}}; 
\draw(2,9) node {\footnotesize{11}}; 
\draw(2,10) node {\footnotesize{12}}; 
\draw(2,11) node {\footnotesize{13}}; 
\draw(2,12) node {\footnotesize{14}}; 
\draw(2,13) node {\footnotesize{15}}; 
\draw(2,14) node {\footnotesize{16}}; 
\draw(2,15) node {\footnotesize{17}}; 
\draw(3,0) node {\footnotesize{3}}; 
\draw(3,1) node {\footnotesize{4}}; 
\draw(3,2) node {\footnotesize{5}}; 
\draw(3,3) node {\footnotesize{6}}; 
\draw(3,4) node {\footnotesize{7}}; 
\draw(3,5) node {\footnotesize{1}}; 
\draw(3,6) node {\footnotesize{2}}; 
\draw(3,7) node {\footnotesize{3}}; 
\draw(3,8) node {\footnotesize{4}}; 
\draw(3,9) node {\footnotesize{5}}; 
\draw(3,10) node {\footnotesize{6}}; 
\draw(3,11) node {\footnotesize{7}}; 
\draw(3,12) node {\footnotesize{8}}; 
\draw(3,13) node {\footnotesize{9}}; 
\draw(3,14) node {\footnotesize{10}}; 
\draw(3,15) node {\footnotesize{11}}; 
\draw(4,0) node {\footnotesize{4}}; 
\draw(4,1) node {\footnotesize{5}}; 
\draw(4,2) node {\footnotesize{6}}; 
\draw(4,3) node {\footnotesize{7}}; 
\draw(4,4) node {\footnotesize{8}}; 
\draw(4,5) node {\footnotesize{2}}; 
\draw(4,6) node {\footnotesize{3}}; 
\draw(4,7) node {\footnotesize{4}}; 
\draw(4,8) node {\footnotesize{5}}; 
\draw(4,9) node {\footnotesize{6}}; 
\draw(4,10) node {\footnotesize{7}}; 
\draw(4,11) node {\footnotesize{8}}; 
\draw(4,12) node {\footnotesize{9}}; 
\draw(4,13) node {\footnotesize{10}}; 
\draw(4,14) node {\footnotesize{11}}; 
\draw(4,15) node {\footnotesize{12}}; 
\draw(5,0) node {\footnotesize{5}}; 
\draw(5,1) node {\footnotesize{6}}; 
\draw(5,2) node {\footnotesize{7}}; 
\draw(5,3) node {\footnotesize{1}}; 
\draw(5,4) node {\footnotesize{2}}; 
\draw(5,5) node {\footnotesize{3}}; 
\draw(5,6) node {\footnotesize{4}}; 
\draw(5,7) node {\footnotesize{5}}; 
\draw(5,8) node {\footnotesize{6}}; 
\draw(5,9) node {\footnotesize{7}}; 
\draw(5,10) node {\footnotesize{8}}; 
\draw(5,11) node {\footnotesize{9}}; 
\draw(5,12) node {\footnotesize{10}}; 
\draw(5,13) node {\footnotesize{11}}; 
\draw(5,14) node {\footnotesize{12}}; 
\draw(5,15) node {\footnotesize{13}}; 
\draw(6,0) node {\footnotesize{6}}; 
\draw(6,1) node {\footnotesize{7}}; 
\draw(6,2) node {\footnotesize{8}}; 
\draw(6,3) node {\footnotesize{2}}; 
\draw(6,4) node {\footnotesize{3}}; 
\draw(6,5) node {\footnotesize{4}}; 
\draw(6,6) node {\footnotesize{5}}; 
\draw(6,7) node {\footnotesize{6}}; 
\draw(6,8) node {\footnotesize{7}}; 
\draw(6,9) node {\footnotesize{8}}; 
\draw(6,10) node {\footnotesize{2}}; 
\draw(6,11) node {\footnotesize{3}}; 
\draw(6,12) node {\footnotesize{4}}; 
\draw(6,13) node {\footnotesize{5}}; 
\draw(6,14) node {\footnotesize{6}}; 
\draw(6,15) node {\footnotesize{7}}; 
\draw(7,0) node {\footnotesize{7}}; 
\draw(7,1) node {\footnotesize{8}}; 
\draw(7,2) node {\footnotesize{9}}; 
\draw(7,3) node {\footnotesize{3}}; 
\draw(7,4) node {\footnotesize{4}}; 
\draw(7,5) node {\footnotesize{5}}; 
\draw(7,6) node {\footnotesize{6}}; 
\draw(7,7) node {\footnotesize{7}}; 
\draw(7,8) node {\footnotesize{8}}; 
\draw(7,9) node {\footnotesize{9}}; 
\draw(7,10) node {\footnotesize{3}}; 
\draw(7,11) node {\footnotesize{4}}; 
\draw(7,12) node {\footnotesize{5}}; 
\draw(7,13) node {\footnotesize{6}}; 
\draw(7,14) node {\footnotesize{7}}; 
\draw(7,15) node {\footnotesize{8}}; 
\draw(8,0) node {\footnotesize{8}}; 
\draw(8,1) node {\footnotesize{9}}; 
\draw(8,2) node {\footnotesize{10}}; 
\draw(8,3) node {\footnotesize{4}}; 
\draw(8,4) node {\footnotesize{5}}; 
\draw(8,5) node {\footnotesize{6}}; 
\draw(8,6) node {\footnotesize{7}}; 
\draw(8,7) node {\footnotesize{8}}; 
\draw(8,8) node {\footnotesize{2}}; 
\draw(8,9) node {\footnotesize{3}}; 
\draw(8,10) node {\footnotesize{4}}; 
\draw(8,11) node {\footnotesize{5}}; 
\draw(8,12) node {\footnotesize{6}}; 
\draw(8,13) node {\footnotesize{7}}; 
\draw(8,14) node {\footnotesize{8}}; 
\draw(8,15) node {\footnotesize{9}}; 
\draw(9,0) node {\footnotesize{9}}; 
\draw(9,1) node {\footnotesize{10}}; 
\draw(9,2) node {\footnotesize{11}}; 
\draw(9,3) node {\footnotesize{5}}; 
\draw(9,4) node {\footnotesize{6}}; 
\draw(9,5) node {\footnotesize{7}}; 
\draw(9,6) node {\footnotesize{8}}; 
\draw(9,7) node {\footnotesize{9}}; 
\draw(9,8) node {\footnotesize{3}}; 
\draw(9,9) node {\footnotesize{4}}; 
\draw(9,10) node {\footnotesize{5}}; 
\draw(9,11) node {\footnotesize{6}}; 
\draw(9,12) node {\footnotesize{7}}; 
\draw(9,13) node {\footnotesize{8}}; 
\draw(9,14) node {\footnotesize{9}}; 
\draw(9,15) node {\footnotesize{3}}; 
\draw(10,0) node {\footnotesize{10}}; 
\draw(10,1) node {\footnotesize{11}}; 
\draw(10,2) node {\footnotesize{12}}; 
\draw(10,3) node {\footnotesize{6}}; 
\draw(10,4) node {\footnotesize{7}}; 
\draw(10,5) node {\footnotesize{8}}; 
\draw(10,6) node {\footnotesize{2}}; 
\draw(10,7) node {\footnotesize{3}}; 
\draw(10,8) node {\footnotesize{4}}; 
\draw(10,9) node {\footnotesize{5}}; 
\draw(10,10) node {\footnotesize{6}}; 
\draw(10,11) node {\footnotesize{7}}; 
\draw(10,12) node {\footnotesize{8}}; 
\draw(10,13) node {\footnotesize{9}}; 
\draw(10,14) node {\footnotesize{10}}; 
\draw(10,15) node {\footnotesize{4}}; 
\draw(11,0) node {\footnotesize{11}}; 
\draw(11,1) node {\footnotesize{12}}; 
\draw(11,2) node {\footnotesize{13}}; 
\draw(11,3) node {\footnotesize{7}}; 
\draw(11,4) node {\footnotesize{8}}; 
\draw(11,5) node {\footnotesize{9}}; 
\draw(11,6) node {\footnotesize{3}}; 
\draw(11,7) node {\footnotesize{4}}; 
\draw(11,8) node {\footnotesize{5}}; 
\draw(11,9) node {\footnotesize{6}}; 
\draw(11,10) node {\footnotesize{7}}; 
\draw(11,11) node {\footnotesize{8}}; 
\draw(11,12) node {\footnotesize{9}}; 
\draw(11,13) node {\footnotesize{3}}; 
\draw(11,14) node {\footnotesize{4}}; 
\draw(11,15) node {\footnotesize{5}}; 
\draw(12,0) node {\footnotesize{12}}; 
\draw(12,1) node {\footnotesize{13}}; 
\draw(12,2) node {\footnotesize{14}}; 
\draw(12,3) node {\footnotesize{8}}; 
\draw(12,4) node {\footnotesize{9}}; 
\draw(12,5) node {\footnotesize{10}}; 
\draw(12,6) node {\footnotesize{4}}; 
\draw(12,7) node {\footnotesize{5}}; 
\draw(12,8) node {\footnotesize{6}}; 
\draw(12,9) node {\footnotesize{7}}; 
\draw(12,10) node {\footnotesize{8}}; 
\draw(12,11) node {\footnotesize{9}}; 
\draw(12,12) node {\footnotesize{10}}; 
\draw(12,13) node {\footnotesize{4}}; 
\draw(12,14) node {\footnotesize{5}}; 
\draw(12,15) node {\footnotesize{6}}; 
\draw(13,0) node {\footnotesize{13}}; 
\draw(13,1) node {\footnotesize{14}}; 
\draw(13,2) node {\footnotesize{15}}; 
\draw(13,3) node {\footnotesize{9}}; 
\draw(13,4) node {\footnotesize{10}}; 
\draw(13,5) node {\footnotesize{11}}; 
\draw(13,6) node {\footnotesize{5}}; 
\draw(13,7) node {\footnotesize{6}}; 
\draw(13,8) node {\footnotesize{7}}; 
\draw(13,9) node {\footnotesize{8}}; 
\draw(13,10) node {\footnotesize{9}}; 
\draw(13,11) node {\footnotesize{3}}; 
\draw(13,12) node {\footnotesize{4}}; 
\draw(13,13) node {\footnotesize{5}}; 
\draw(13,14) node {\footnotesize{6}}; 
\draw(13,15) node {\footnotesize{7}}; 
\draw(14,0) node {\footnotesize{14}}; 
\draw(14,1) node {\footnotesize{15}}; 
\draw(14,2) node {\footnotesize{16}}; 
\draw(14,3) node {\footnotesize{10}}; 
\draw(14,4) node {\footnotesize{11}}; 
\draw(14,5) node {\footnotesize{12}}; 
\draw(14,6) node {\footnotesize{6}}; 
\draw(14,7) node {\footnotesize{7}}; 
\draw(14,8) node {\footnotesize{8}}; 
\draw(14,9) node {\footnotesize{9}}; 
\draw(14,10) node {\footnotesize{10}}; 
\draw(14,11) node {\footnotesize{4}}; 
\draw(14,12) node {\footnotesize{5}}; 
\draw(14,13) node {\footnotesize{6}}; 
\draw(14,14) node {\footnotesize{7}}; 
\draw(14,15) node {\footnotesize{8}}; 
\draw(15,0) node {\footnotesize{15}}; 
\draw(15,1) node {\footnotesize{16}}; 
\draw(15,2) node {\footnotesize{17}}; 
\draw(15,3) node {\footnotesize{11}}; 
\draw(15,4) node {\footnotesize{12}}; 
\draw(15,5) node {\footnotesize{13}}; 
\draw(15,6) node {\footnotesize{7}}; 
\draw(15,7) node {\footnotesize{8}}; 
\draw(15,8) node {\footnotesize{9}}; 
\draw(15,9) node {\footnotesize{3}}; 
\draw(15,10) node {\footnotesize{4}}; 
\draw(15,11) node {\footnotesize{5}}; 
\draw(15,12) node {\footnotesize{6}}; 
\draw(15,13) node {\footnotesize{7}}; 
\draw(15,14) node {\footnotesize{8}}; 
\draw(15,15) node {\footnotesize{9}}; 
\draw (-1,-.25) -- (15.5,-.25);
\draw (-.25,-1) -- (-.25,15.5);
\draw (-1,-1) -- (-.25,-.25);
\draw (-.5,-.75) node {\footnotesize $a$};
\draw (-.75,-.5) node {\footnotesize $b$};
\foreach \i in {0,...,15}{
\draw (-2/3,\i) node {\footnotesize \i};
\draw (\i,-2/3) node {\footnotesize \i};
}

\end{tikzpicture}
\caption{The distance $\dist(a,b;\{(1,0), (0,1), (3,5), (5,3)\})$ for $0 \leq a,b \leq 15$.}
\label{fig:3553dist}
\end{figure}

\noindent 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 \ref{fig:3553dist}. 

\begin{problem}
Let $S = \{(1,0), (0,1), (u,v), (v,u)\}$ with $u>v \geq 1$ arbitrary.  Determine $\dist(a,b;S)$ and $|\mathcal{W}(a,b;S)|$.
\end{problem}


\subsection{Catalan generalizations}

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

\begin{problem}
Let $a \geq 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$?
\end{problem}

For brevity, let us say that an \textit{$S$-Catalan walk} is a minimal $S$-walk that stays weakly below the line $y=x$.  For integers $a,b$ with $a \geq 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 \leq i \leq 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 \seqnum{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 \seqnum{A009766}. Krattenthaler \cite[Corollary 10.3.2]{Krattenthaler} gives a proof of this fact.


\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=0.75]
\draw(0,0) node {\footnotesize{1}}; 

\draw(1,0) node {\footnotesize{0}}; 
\draw(1,1) node {\footnotesize{0}}; 

\draw(2,0) node {\footnotesize{0}}; 
\draw(2,1) node {\footnotesize{1}}; 
\draw(2,2) node {\footnotesize{0}}; 

\draw(3,0) node {\footnotesize{1}}; 
\draw(3,1) node {\footnotesize{0}}; 
\draw(3,2) node {\footnotesize{0}}; 
\draw(3,3) node {\footnotesize{2}}; 

\draw(4,0) node {\footnotesize{0}}; 
\draw(4,1) node {\footnotesize{0}}; 
\draw(4,2) node {\footnotesize{2}}; 
\draw(4,3) node {\footnotesize{0}}; 
\draw(4,4) node {\footnotesize{0}}; 

\draw(5,0) node {\footnotesize{0}}; 
\draw(5,1) node {\footnotesize{2}}; 
\draw(5,2) node {\footnotesize{0}}; 
\draw(5,3) node {\footnotesize{0}}; 
\draw(5,4) node {\footnotesize{6}}; 
\draw(5,5) node {\footnotesize{0}}; 

\draw(6,0) node {\footnotesize{1}}; 
\draw(6,1) node {\footnotesize{0}}; 
\draw(6,2) node {\footnotesize{0}}; 
\draw(6,3) node {\footnotesize{7}}; 
\draw(6,4) node {\footnotesize{0}}; 
\draw(6,5) node {\footnotesize{0}}; 
\draw(6,6) node {\footnotesize{13}}; 

\draw(7,0) node {\footnotesize{0}}; 
\draw(7,1) node {\footnotesize{0}}; 
\draw(7,2) node {\footnotesize{5}}; 
\draw(7,3) node {\footnotesize{0}}; 
\draw(7,4) node {\footnotesize{0}}; 
\draw(7,5) node {\footnotesize{18}}; 
\draw(7,6) node {\footnotesize{0}}; 
\draw(7,7) node {\footnotesize{0}}; 

\draw(8,0) node {\footnotesize{0}}; 
\draw(8,1) node {\footnotesize{3}}; 
\draw(8,2) node {\footnotesize{0}}; 
\draw(8,3) node {\footnotesize{0}}; 
\draw(8,4) node {\footnotesize{21}}; 
\draw(8,5) node {\footnotesize{0}}; 
\draw(8,6) node {\footnotesize{0}}; 
\draw(8,7) node {\footnotesize{52}}; 
\draw(8,8) node {\footnotesize{0}}; 

\draw(9,0) node {\footnotesize{1}}; 
\draw(9,1) node {\footnotesize{0}}; 
\draw(9,2) node {\footnotesize{0}}; 
\draw(9,3) node {\footnotesize{16}}; 
\draw(9,4) node {\footnotesize{0}}; 
\draw(9,5) node {\footnotesize{0}}; 
\draw(9,6) node {\footnotesize{68}}; 
\draw(9,7) node {\footnotesize{0}}; 
\draw(9,8) node {\footnotesize{0}}; 
\draw(9,9) node {\footnotesize{120}}; 

\draw(10,0) node {\footnotesize{0}}; 
\draw(10,1) node {\footnotesize{0}}; 
\draw(10,2) node {\footnotesize{9}}; 
\draw(10,3) node {\footnotesize{0}}; 
\draw(10,4) node {\footnotesize{0}}; 
\draw(10,5) node {\footnotesize{64}}; 
\draw(10,6) node {\footnotesize{0}}; 
\draw(10,7) node {\footnotesize{0}}; 
\draw(10,8) node {\footnotesize{184}}; 

\draw(11,0) node {\footnotesize{0}}; 
\draw(11,1) node {\footnotesize{4}}; 
\draw(11,2) node {\footnotesize{0}}; 
\draw(11,3) node {\footnotesize{0}}; 
\draw(11,4) node {\footnotesize{50}}; 
\draw(11,5) node {\footnotesize{0}}; 
\draw(11,6) node {\footnotesize{0}}; 
\draw(11,7) node {\footnotesize{234}}; 

\draw(12,0) node {\footnotesize{1}}; 
\draw(12,1) node {\footnotesize{0}}; 
\draw(12,2) node {\footnotesize{0}}; 
\draw(12,3) node {\footnotesize{30}}; 
\draw(12,4) node {\footnotesize{0}}; 
\draw(12,5) node {\footnotesize{0}}; 
\draw(12,6) node {\footnotesize{212}}; 

\draw(13,0) node {\footnotesize{0}}; 
\draw(13,1) node {\footnotesize{0}}; 
\draw(13,2) node {\footnotesize{14}}; 
\draw(13,3) node {\footnotesize{0}}; 
\draw(13,4) node {\footnotesize{0}}; 
\draw(13,5) node {\footnotesize{158}}; 

\draw(14,0) node {\footnotesize{0}}; 
\draw(14,1) node {\footnotesize{5}}; 
\draw(14,2) node {\footnotesize{0}}; 
\draw(14,3) node {\footnotesize{0}}; 
\draw(14,4) node {\footnotesize{99}}; 

\draw(15,0) node {\footnotesize{1}}; 
\draw(15,1) node {\footnotesize{0}}; 
\draw(15,2) node {\footnotesize{0}}; 
\draw(15,3) node {\footnotesize{50}}; 

\draw(16,0) node {\footnotesize{0}}; 
\draw(16,1) node {\footnotesize{0}}; 
\draw(16,2) node {\footnotesize{20}}; 

\draw(17,0) node {\footnotesize{0}}; 
\draw(17,1) node {\footnotesize{6}}; 

\draw(18,0) node {\footnotesize{1}}; 


\draw (-1,-.25) -- (18.5,-.25);
\draw (-.25,-1) -- (-.25,9.5);
\draw (-1,-1) -- (-.25,-.25);
\draw (-.5,-.75) node {\footnotesize $a$};
\draw (-.75,-.5) node {\footnotesize $b$};
\foreach \i in {0,...,18}{
\draw (\i,-2/3) node {\footnotesize \i};
}
\foreach \i in {0,...,9}{
\draw (-2/3,\i) node {\footnotesize \i};
}
\end{tikzpicture}
\caption{Number of $S_3$-Catalan paths terminating at points $(a,b)$ with $0 \leq a+b \leq 18$. }
\label{s3catalan}
\end{figure}

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 \seqnum{A001006}.  Indeed, the map sending $(2,0) \mapsto (1,1)$, $(1,1) \mapsto (1,0)$, and $(0,2) \mapsto (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 \ref{s3catalan} shows the number of $S_3$-Catalan paths
terminating at points $(a,b)$ with $a \geq b$ and $a+b \leq 18$.

The sequence of nonzero numbers along the line $y=x$, which continues as $1, 2, 13, 120, 1288,$ $15046, \ldots$,  did not  appear in OEIS.  We have added it as sequence \seqnum{A292437}.

\begin{problem}
Determine the generating function for $$\sum_{a\geq b \geq 0} |C(a,b;S_3)|x^ay^b \qquad \text{or} \qquad \sum_{a = 0}^\infty |C(a,a;S_3)|t^a.$$
\end{problem}


\section{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. 


\bibliographystyle{jis}
\bibliography{klee2}



\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 05A15;
Secondary 05A19.

\noindent \emph{Keywords:}
lattice path enumeration, generating function, Catalan number, Motzkin number.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 9 2017;
revised version received March 27 2018.
Published in {\it Journal of Integer Sequences},
March 28 2018.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                






.