\define\nt{\negthinspace}
\define\ul{\underline}
\define\ol{\overline}
\define\rom{\roman}
\define\pb{{\bar p}}
\define\Xb{{\B X}}
\define\Yb{{\B Y}}
\define\Zb{{\B Z}}
\define\Wb{{\B W}}
\define\llra{\longleftrightarrow}
\hsize4.5in
\vsize7.125in
%\input format
 
%\vskip6pt
\topmatter
\title
Lattice paths, reflections, \& dimension-changing bijections
\endtitle
\author Richard K. Guy \\
C.~Krattenthaler \\
Bruce E. Sagan
\endauthor
\affil
Department of Mathematics and Statistics\\
The University of Calgary\\
Calgary, Alberta, Canada T2N\,1N4\\
\vskip6pt
Institut f\"ur Mathematik der Universit\"at Wien,\\
Strudlhofgasse 4\\ A-1090 Wien, Austria\\
\vskip6pt
Department of Mathematics\\
Michigan State University\\
East Lansing, MI 48824-1027 USA
\endaffil
 
\thanks {Professor Sagan was supported
in part by NSF grant DMS 8805574 }\endthanks
 
\address
{Department of Mathematics and Statistics,
The University of Calgary,
Calgary, Alberta, Canada T2N\,1N4}
\endaddress
\address
{Institut f\"ur Mathematik der Universit\"at Wien,
Strudlhofgasse 4, A-1090 Wien, Austria.}
\endaddress
\address
{Department of Mathematics,
Michigan State University,
East Lansing, MI 48824-1027}
\endaddress
 
 
 
\subjclass
{Primary 05A15; Secondary 05A10}
\endsubjclass
\keywords
{lattice paths, bijections, reflection principle}
\endkeywords
\abstract
{We enumerate various families of planar lattice
paths  consisting of unit steps in directions N, S, E, or W,
which do not cross the $x$-axis or both $x$- and $y$-axes.
The proofs are purely combinatorial throughout, using either
reflections or bijections between these NSEW-paths and linear
NS-paths.  We also consider other dimension-changing bijections.}
\endabstract
\endtopmatter
\document
 
\NoBlackBoxes
 
\subheading{1. Introduction}Consider lattice paths in the plane
consisting of unit steps, each in a direction N, S, E, or W.
Such NSEW-paths were first investigated by
DeTemple \& Robertson~\cite{DR} and Cs\'aki, Mohanty \&
Saran~\cite{CMS}.
The basic result of these papers is the following.
\proclaim{Theorem 1}
The number of NSEW-paths with $n$ steps from the origin to $(c,d)$
is
$$\binom n {\frac{n+c+d}{2}}\binom n {\frac{n+c-d}{2}}\ ,\tag1.1$$
where by convention the binomial coefficient $\binom nk$ is assumed
to be zero unless $k$ is a an integer $0\leq k \leq n$.
\endproclaim
 
The form of expression (1.1) suggests that there is
a simple combinatorial explanation, although there is none in
either \cite{DR} or \cite{CMS}. This will be our
first objective in the next section.
 
We will consider NSEW-paths which do not cross the
$x$-axis, or which cross neither the $x$-axis nor the $y$-axis.
It turns out that there are
simple and beautiful expressions for the cardinality of several sets
of such NSEW-paths. A list of  the  simplest of these is given below,
and more can be found in the next section. But first it is
convenient to introduce some notation.
 
If $a,b,c,d$ are integers, let $P\sb
n((a,b)\to (c,d))$ denote the set
of all NSEW-paths from $(a,b)$ to $(c,d)$ consisting of $n$ steps,
let $P\sp +\sb n((a,b)\to (c,d))$
denote that subset of $P\sb
n((a,b)\to (c,d))$
containing only paths which do not cross the $x$-axis, and
let $P\sp
{++}\sb
n((a,b)\to (c,d))$ denote that subset of $P\sb
n((a,b)\to (c,d))$
containing only paths which do not cross either the $x$-axis or the
$y$-axis. We will also want to count sets of paths which can end at
more than one point.  For this, we will use two additional
notational conventions.   By ``$\ge c$" in place of a coordinate of the
final point of a set of paths, we mean that this coordinate may be
any integer greater or equal $c$, by ``$*$" we mean that this
coordinate may be any integer. For example, $P\sp
+\sb
n((a,b)\to (*,\ge d))$
denotes the set of all NSEW-paths of $n$ steps starting at $(a,b)$
which do not cross the $x$-axis and finish at some point $(x,y)$,
where $x$ is an arbitrary integer and $y$ is an integer greater than or
equal to $d$.
 
It will also be convenient to let
$L_n(b\to d)$ denote the set of all linear NS-paths of length $n$ from
$(0,b)$ to $(0,d)$.  Similarly, the other notational conventions of
the preceding paragraph will be adapted for 1-dimensional paths.
 
\medskip
Now, here is the promised list.  For $P_n$ we have the following formulas.
      $$\vert P\sb n((a,b)\to (c,d))\vert = \binom nr\binom ns\ , \tag1.2$$
where $r=\frac {1} {2}(n-a-b+c+d)$ and $s=\frac {1} {2}(n-a+b+c-d)$.
    $$\vert P\sb n((0,b)\to (*,d))\vert = \binom {2n}{n-d+b}\ . \tag1.3$$
 
For $P\sb n \sp +$ we can prove the following results.
    $$\align \vert P\sp+\sb n((a,b)\to (c,d))\vert&=\binom nr \binom ns-
    \binom n{r+b+1}  \binom n{s-b-1}\ ,\tag1.4\\
    \vert P\sp+\sb n((0,0)\to (c,*))\vert
      &=\binom n{\lfloor \frac {n+c} {2}\rfloor}
      \binom n{\lfloor\frac {n-c} {2}\rfloor}\ .\tag1.5\\
    \vert P\sp+\sb n((0,b)\to (*,d))\vert&=\binom {2n}{n-d+b}-
      \binom {2n}{n-d-b-2}\ ,\tag1.6
      \endalign$$
in particular,
    $$\align \vert P\sp+\sb
    n((0,0)\to (*,d))\vert&=\binom {2n+1}{n-d}-\binom
    {2n+1}{n-d-1}\ .\tag1.7\\
        \vert P\sp+\sb
    n((0,0)\to (*,0))\vert&=C_{n+1}\ ,\tag1.8
    \endalign$$
where $C_n$ is the $n$th Catalan number.
 
    $$\align \vert P\sp+\sb
    n((0,0)\to (*,*))\vert&=\binom {2n+1}n\ .\tag1.9\\
    \vert P\sp+\sb n((0,1)\to (*,*))\vert&=\binom {2n+2}n\ .\tag1.10
    \endalign$$
 
Finally, for paths confined to the first quadrant, we obtain the following.
    $$\align \vert P\sp{++}\sb
    n((a,b)\to (c,d))\vert&=\binom nr \binom ns - \binom
    n{r+b+1}\binom n{s-b-1}\tag1.11\\
    - \binom n{r+a+1}& \binom n{s+a+1} + \binom
    n{r+a+b+2} \binom n{s+a-b}\ ,
    \endalign$$
with $r,s$ as in (1.2). In particular,
    $$\align \vert P\sp{++}\sb
    n((0,0)\to (c,d))\vert&=\binom n{\frac {n+c-d}
    {2}} \binom {n+2}{\frac {n-c-d} {2}}-\binom {n+2}{\frac {n+c-d} {2}+1}
    \binom n{\frac {n-c-d} {2}-1}\ .\tag1.12\\
    \vert P\sp{++}\sb
    n((0,0)\to (c,*))\vert&=\binom n{\lfloor\frac {n-c} {2}\rfloor}
    \binom {n+1}{\lfloor\frac {n-c+1} {2}\rfloor} - \binom n{\lfloor\frac
    {n-c-1} {2}\rfloor}\binom {n+1}{\lfloor\frac {n-c} {2}\rfloor}\
    .\tag1.13\\
    \vert P\sp{++}\sb
    n((0,0)\to (*,*))\vert&=\binom {n}{\lfloor\frac {n} {2}\rfloor}
    \binom {n+1}{\lfloor\frac {n+1} {2}\rfloor}\ .\tag1.14
    \endalign$$
Equation (1.9) was first discovered by Sands \cite{Sa} and was the
starting point of our investigations.
 
In the next section we provide combinatorial proofs for all these
formulas. We also derive counting results about NSEW-paths with
lower bounds on the $x$- or $y$-coordinate of the final points.
The techniques we use are either the so-called
reflection principle \cite{Mo} or certain bijections between NSEW-paths and
NS-paths along the $y$-axis.  In Section 3 we will look at some other
dimension-changing bijections.  We should note that Breckenridge, Bos, Calvert,
Gastineau-Hills, Nelson \& Wehrhahn~\cite{BBCGNW} have independently
discovered essentially the same formulas and bijective proofs for
(1.1) to (1.4), (1.6), (1.8) and (1.9).
Related bijections
have also been considered in~\cite{CMS} and
by Gessel [private communication].
 
 
Of course, several of these results follow directly from others on the list
by simple algebraic manipulations. For example, (1.9) can be deduced
from (1.7) by summing up over all $d\ge 0$. But such a proof does not
really explain {\it why} this expression is the answer to the problem
in the way that a bijection does. The
second reason why purely combinatorial proofs are preferable is that
very often they give insight into the connections between certain
properties of lattice paths and the structure
of the corresponding counting expressions (cf. the proofs of (1.5), (1.10),
(1.13), (1.14)).
 
\subheading{2. Reflections and bijections}
 
Proof of (1.1) and (1.2). We set up a correspondence between NSEW-paths, $p$,
and pairs $(p\sb1,p\sb2)$ of NS-paths. The $m$-th step of $p$
will correspond to the pair of $m$-th steps from $p\sb1$ and
$p\sb2$ according to the following table.
    $$\matrix
    \ul{p} & \ul{p_1} & \ul{p_2} \\
    \rom{N} & \rom{N}   & \rom{N} \\
    \rom{E} & \rom{N}   & \rom{S} \\
    \rom{W} & \rom{S}   & \rom{N}  \\
    \rom{S} & \rom{S}   & \rom{S}
    \endmatrix$$
Then the NSEW-paths of $n$ steps from
$(0,0)$ to $(c,d)$ are in one-to-one correspondence with pairs
$(p\sb1,p\sb2)$ of $n$-step NS-paths, where $p\sb1$
runs from $(0,0)$ to $(0,c+d)$ and $p\sb2$
from $(0,0)$ to $(0,c-d)$.
But the number of NS-paths from $(0,0)$ to $(0,k)$ of length $n$
is well-known \cite{Mo, page 2} to be
    $$\vert L_n(0\to k) \vert =\binom {n}{\frac{n+k}{2}}\ , \tag2.1$$
and (1.1) follows at once.
 
Formula (1.2) now follows by translation.\quad \qed
 
\medpagebreak
Proof of (1.3).  Here we use another correspondence
between NSEW-paths, $p$, and NS-paths, $\bar p$, of twice the length.
The $m$-th step of $p$ determines the $(2m-1)$-st
and $2m$-th step of $\bar p$ according to the following table.  Notice
the similarity to the correspondence in the proof of (1.1).
    $$\matrix
    \ul{p} & \ul{\pb} \\
    \rom{N} & \rom{NN} \\
    \rom{E} & \rom{NS} \\
    \rom{W} & \rom{SN}  \\
    \rom{S} & \rom{SS}
    \endmatrix$$
This sets up a one-to-one correspondence between NSEW-paths with $n$ steps
from $(0,b)$ to $(*,d)$ and
NS-paths with $2n$ steps from $(0,2b)$ to $(0,2d)$.  Applying a
translated version of
formula (2.1), we are done.\quad \qed
 
\medpagebreak
Proof of (1.4) and (1.6). These follow from (1.2) and (1.3)
respectively by the
reflection principle.  For (1.4), note that the total number of
NSEW-paths from $(a,b)$
to $(c,d)$ is given by $\binom nr\binom ns$.  From this,  we have
to subtract off the number of paths which cross the $x$-axis. Each of
these has a first point, say $P$, for which $y=-1$. Reflect the
initial portion $OP$ in the line $y=-1$, giving a one-to-one
correspondence between paths which cross the $x$-axis and paths from
$(a,-b-2)$ to $(c,d)$. Applying (1.2) we see that these paths are
counted by
$\binom n{r+b+1}\binom n{s-b-1}$.
 
Similarly, in (1.6) the first term counts all paths from $(0,b)$ to
$(*,d)$.  Those that touch $y=-1$ are subtracted out by the second
term.\quad \qed
 
\medpagebreak
Proof of (1.7) and (1.8).  We use the same correspondence as in the
proof of (1.3), except that the $m$-th step of $p$ determines the
$2m$-th and $(2m+1)$-st step of $\pb$.  The first step of $\pb$ is
always taken to be N so $\pb$ has total length $2n+1$ and ends at
$(0,2d+1)$.  In addition,
the fact that $p$ always stays in the upper half plane translates to
$\pb$ always staying on the upper half of the $y$-axis.  The number of
such paths is well-known \cite{Mo, page 3} to be the right-hand side of (1.7).
(In fact, the one-dimensional reflection principle is usually used to
derive this from (2.1).)  In particular, when $d=0$ we obtain a Catalan
number.\quad \qed
 
 
\medpagebreak
Proof of (1.9) and (1.10).
To prove (1.9)  we first  apply the
correspondence in the proof of (1.7) to get a bijection
    $$P_n^{+}((0,0)\to(*,*)) \llra \bigcup_{j\geq0}
    L_{2n+1}^+(0\to  2j+1).$$
In view of (2.1), it suffices to give a second bijection
    $$L_{2n+1}(0\to1)\llra\bigcup_{j\geq0}
    L_{2n+1}^+(0\to  2j+1). \tag2.2$$
Given $p\in L_{2n+1}(0\to1)$ apply the map
    $$p\longrightarrow\cases p&\text {if }
        p\in L_{2n+1}^+(0\to1)\\
    p' &\topfoldedtext\foldedwidth{7cm}{otherwise,
    where $p'$ is obtained from $p$ by reflecting the
    portion up to the first intersection with $y=-1$ in that line and
    then shifting the whole path $2$ units upwards.}\endcases$$
Clearly this is a bijection
    $$L_{2n+1}(0\to1)\llra
    L_{2n+1}^+(0\to1) \cup L_{2n+1}(0\to3)\ .$$
We now apply the same map to the elements of $L_{2n+1}(0\to3)$, and by
iterating the process end up with the right-hand side of (2.2).
We will see a similar map later in the proof of (1.5)
and related identities.
 
\smallpagebreak
The same idea will give a bijection
    $$\bigcup \sb{j\ge 0}L\sb {2n} \sp{+}(2b+1\to 2l+1+(4b+4)j)\llra
    L\sb{2n}(2b+1\to 2l+1)\ .$$
Moreover, the last bijection also provides the following bijection,
    $$\bigcup \sb{j\ge 0}L\sb {2n} \sp{+}(2b+1\to 2j+1)\llra
    \bigcup \sb{l=0} \sp{2b+1}L\sb{2n}(2b+1\to 2l+1)\ .$$
Since, by the bijection used to establish (1.6), the set $L\sb {2n}
\sp{+}(2b+1\to 2j+1)$ is in one-to-one correspondence with $P\sp+\sb n((0,b)
\to (*,*))$, we have a bijective proof of the formula
    $$\vert P\sp+\sb n((0,b)\to (*,*))\vert = \sum \sb{j=0} \sp{2b+1}
    \binom {2n}{n+b-j}\ .$$
Using the symmetry relation
    $$\binom{m}{k} = \binom{m}{m-k}$$
and recursion formula
    $$\binom{m+1}{k+1} = \binom{m}{k}+\binom{m}{k+1}\ , \tag2.3$$
this can be rewritten
    $$\align \vert P\sp+\sb n((0,b)\to (*,*))\vert
    &= \sum \sb{j=0} \sp{b} \left[\binom {2n}{n+j} +
    \binom{2n}{n+j+1} \right] \\
    &= \sum \sb{j=1} \sp{b+1} \binom {2n+1}{n+j}\ .
    \endalign$$
In particular, for $b=0$ we obtain (1.9) again, while for $b=1$ we
get (1.10)  by reapplying the recursion. The algebraic step of transforming
binomial coefficients by symmetry can be made
bijective by considering the correspondence between $L_{2n}(0\to k)$
and $L_{2n}(0\to -k)$ given by reflection in the origin.  Also,
the recursion steps can be turned into a bijection by
adjoining to the end of a path a N- or S-step as appropriate, corresponding to
the first or second terms of (2.3).\quad \qed
 
\medpagebreak
Proof of (1.11) and (1.12). The inclusion-exclusion principle shows
that the number of paths being elements of $P\sp
{++}\sb
n((a,b)\to (c,d))$
is equal to the number of all NSEW-paths of $n$ steps from $(a,b)$ to
$(c,d)$ minus the number of those which cross the $x$-axis minus the
number of those which cross the $y$-axis plus the number of those
which cross both of them. The paths crossing the $x$-axis have been
already counted in the proof of (1.4)
 by using reflection in $y=-1$. Similarly, by
reflection in $x=-1$, it is seen that $n$-step paths from $(a,b)$ to
$(c,d)$ which cross the $y$-axis are in one-to-one correspondence
with all $n$-step paths from $(-a-2,b)$ to $(c,d)$. The set of
$n$-step paths from $(a,b)$ to $(c,d)$ which cross both the $x$- and
$y$-axes is in one-to-one correspondence with all paths from
$(-a-2,-b-2)$ to $(c,d)$, which is seen by using reflection twice,
first in $y=-1$, then in $x=-1$. Hence, by
(1.2) the desired number is
given by the right-hand side of (1.11). Setting $a=b=0$
in (1.11) and using the binomial recursion repeatedly,
we obtain (1.12).\quad \qed
 
\medpagebreak
Proof of (1.5), (1.13) and (1.14). Let us introduce another
correspondence, this time between families of NSEW-paths themselves.
For a path $p\in P\sb
n((a,b)\to (c,d))$ we apply the map
$$p\longrightarrow\cases p&\text {if }p\in P\sp
+\sb
n((a,b)\to (c,d))\\
p' &\topfoldedtext\foldedwidth{7cm}{otherwise,
where $p'$ is obtained from $p$ by reflecting the
portion up to the first intersection with $y=-1$ in that line and
then shifting the whole path $2b+2$ units upwards.}\endcases$$
This is a bijection
$$P\sb
n((a,b)\to (c,d))\longleftrightarrow P\sp
+\sb
n((a,b)\to (c,d))\cup P\sb
n((a,b)\to
(c,d+(2b+2)))\ .$$
Applying the same map to $P\sb
n((a,b)\to (c,d+(2b+2)))$, etc., we get a
bijection
$$P\sb
n((a,b)\to (c,d))\longleftrightarrow \bigcup \sb
{j\ge 0}P\sp
+\sb
n((a,b)\to
(c,d+(2b+2)j))\ .\tag2.4$$
Now, let $a+b+c+d\equiv n\pmod 2$. Using the bijection in (2.4)
for $d$ successively replaced by $d,d+2,\dots,d+2b$, we obtain a
bijection
$$\bigcup \sb
{j=0} \sp
{b}P\sb
n((a,b)\to (c,d+2j))\longleftrightarrow P\sp
+\sb
n((a,b)\to
(c,\ge d))\ .$$
In case $a+b+c+d\equiv n+1\pmod 2$ use (2.4) for $d$ replaced by
$d+1,d+3,\dots,d+2b+1$, thus obtaining a bijection
$$\bigcup \sb
{j=0} \sp
{b}P\sb
n((a,b)\to (c,d+1+2j))\longleftrightarrow P\sp
+\sb
n((a,b)\to
(c,\ge d))\ .$$
Putting both together and using the basic result (1.2),
leads to the following expression for the
cardinality of $P\sp
+\sb
n((a,b)\to
(c,\ge d))$:
$$\vert P\sp
+\sb
n((a,b)\to
(c,\ge d))\vert = \sum \sb
{j=0} \sp
{b}\binom n{\lfloor r\rfloor-j}\binom
n{\lfloor s\rfloor-j}\ .\tag2.5$$
In particular, for $a=b=0$ we get
$$\vert P\sp
+\sb
n((0,0)\to
(c,\ge d))\vert =\binom n{\lfloor\frac {n+c-d} {2}\rfloor} \binom
n{\lfloor\frac {n-c-d} {2}\rfloor}\ .\tag2.6$$
Setting $d=0$ in (2.6) gives (1.5).
 
\medpagebreak
The same idea which was used to obtain (2.4) may also be applied to
the right-hand side of (2.4) in
``horizontal" direction. This provides a bijection
$$P\sb
n((a,b)\to (c,d))\longleftrightarrow \bigcup \sb
{i,j\ge 0}P\sp
{++}\sb
n((a,b)\to
(c+(2a+2)i,d+(2b+2)j))\ .\tag2.7$$
Now, let $a+b+c+d\equiv n\pmod 2$. In a similar manner as above, a
bijection
$$\multline
\bigcup \sb
{i=0} \sp
{a}\bigcup \sb
{j=0} \sp
{b}\Big(P\sb
n((a,b)\to (c+2i,d+2j))
\cup P\sb
n((a,b)\to (c+1+2i,d+1+2j))\Big)\\
 \longleftrightarrow P\sp
{++}\sb
n((a,b)\to
(\ge c,\ge d))
\endmultline$$
can be constructed. In case $a+b+c+d\equiv n+1\pmod 2$, analogously
we construct a bijection
$$\multline
\bigcup \sb
{i=0} \sp
{a}\bigcup \sb
{j=0} \sp
{b}\Big(P\sb
n((a,b)\to (c+1+2i,d+2j))
\cup P\sb
n((a,b)\to (c+2i,d+1+2j))\Big)\\
 \longleftrightarrow P\sp
{++}\sb
n((a,b)\to
(\ge c,\ge d))\ .
\endmultline$$
Again, putting both together and using the binomial recursion,
simple considerations
show that
$$\multline
\vert P\sp
{++}\sb
n((a,b)\to
(\ge c,\ge d))\vert\\
 =\sum \sb
{i=0} \sp
{a}\sum \sb
{j=0} \sp
{b}\frac
{n!\,(n+1)!} {\lceil r+i-j\rceil!\,\lceil n-r-i+j\rceil!\,
\lfloor s-i-j\rfloor!\,\lfloor n-s+i+j+1\rfloor!}\ .
\endmultline\tag2.8$$
The specialization $a=b=0$ leads to the formula
$$\vert P\sp
{++}\sb
n((0,0)\to
(\ge c,\ge d))\vert =\frac
{n!\,(n+1)!} {\lceil \frac {n+c-d} {2}\rceil!\,\lceil \frac {n-c+d}
{2}\rceil!\,
\lfloor \frac {n-c-d} {2}\rfloor!\,\lfloor \frac {n+c+d+2} {2}\rfloor!}\
.\tag2.9$$
In particular, setting $d=0$ results in
$$\vert P\sp
{++}\sb
n((0,0)\to
(\ge c,*))\vert =\binom n{\lfloor\frac {n-c} {2}\rfloor}\binom
{n+1}{\lfloor\frac {n-c+1} {2}\rfloor}\ ,  \tag2.10$$
which directly implies (1.13). Equation (1.14) is the
special case $c=0$ of (2.10).\quad \qed
 
\subheading{3. Higher dimensions}
 
It is easy to extend the idea of a dimension-changing bijection to
higher dimensions.  As an example, we will examine the case of lattice
paths in dimension four.  Let the four coordinates be denoted
$x,y,z,w$ and let X, Y, Z, W denote a positive unit step in those
respective directions while \Xb, \Yb, \Zb, \Wb \ denote the
corresponding negative step.  Then there is a length-preserving
bijection between 4-dimensional paths $p$ and
triples of 1-dimensional paths $p_1,p_2,p_3$ by letting the $m$-th
steps correspond according to the following table.
    $$\matrix
    \ul{p} & \ul{p_1} & \ul{p_2} &\ul{p_3} \\
    \rom{X} & \rom{N} & \rom{N}   & \rom{N} \\
    \rom{Y} & \rom{N} & \rom{N}   & \rom{S} \\
    \rom{Z} & \rom{N} & \rom{S}   & \rom{N}  \\
    \rom{W} & \rom{N} & \rom{S}   & \rom{S} \\
    \rom{\text\Wb} & \rom{S} & \rom{N}   & \rom{N} \\
    \rom{\text\Zb} & \rom{S} & \rom{N}   & \rom{S} \\
    \rom{\text\Yb} & \rom{S} & \rom{S}   & \rom{N}  \\
    \rom{\text\Xb} & \rom{S} & \rom{S}   & \rom{S}
    \endmatrix$$
Of course, given the ending points of $p_1,p_2$ and $p_3$ only gives
us three conditions, and we need four to determine the ending point of
$p$.  Thus we will only be able to count paths that end on a given
line.
 
Suppose $p$ ends somewhere on the line $l$
whose parametric equations are
    $$l: \qquad
    \aligned
    x &= a+t \\
    y &=b-t \\
    z &=c-t \\
    w &=t\ .
    \endaligned\tag3.1$$
for some constants $a,b,c$ and variable $t$.  Next we eliminate $t$
using pairs corresponding to two partitions of coordinates, namely
$\{x,y\}\cup\{z,w\}$ and $\{x,z\}\cup\{y,w\}$.
    $$\align
    x+y &= a+b \\
    z+w &=c \\
    x+z &=a+c \\
    y+w &=b
    \endalign$$
Now let $x_1$ and $x_2$ be the number of X-steps and \Xb-steps,
respectively, in $p$ with similar notation for the other directions.
Then the final $x$-coordinate of $p$ is $x_1-x_2$ and likewise for the
other coordinates.  This can be substituted into the equations above.
Then add and subtract the equations corresponding to the same
partition to obtain
    $$\align
    x_1-x_2+y_1-y_2+z_1-z_2+w_1-w_2 &= a+b+c \\
    x_1-x_2+y_1-y_2-z_1+z_2-w_1+w_2 &= a+b-c \\
    x_1-x_2-y_1+y_2+z_1-z_2-w_1+w_2 &=a-b+c \\
    x_1+x_2+y_1+y_2+z_1+z_2+w_1+w_2 &=n
    \endalign$$
where the last equation comes from the fact that $p$ has length $n$.
Finally we can solve for the number of N-steps on each of
$p_1, p_2, p_3$ which are given respectively by
    $$\align
    x_1+y_1+z_1+w_1 &= \frac{n+a+b+c}{2} \\
    x_1+y_1+z_2+w_2 &= \frac{n+a+b-c}{2} \\
    x_1+y_2+z_1+w_2 &= \frac{n+a-b+c}{2}\ .
    \endalign$$
Thus we have proved the following theorem.
\proclaim{Theorem 2}  The number of 4-dimensional paths with $n$ steps
ending on the line  given by (3.1) is
    $$\binom n{\frac{n+a+b+c}{2}} \binom n{\frac{n+a+b-c}{2}}
    \binom n{\frac{n+a-b+c}{2}}\ .$$
\endproclaim
 
To describe other sets of paths let $Q_n^S(\bold{0}\to l)$
denote the set of 4-dimensional paths of length $n$
from the origin to the line $l$ of (3.1) which stay in
some subset $S$ of $\bold{Z}^4$.  Define the following half-spaces.
    $$\align
    H_1: &x+y+z+w\geq0 \\
    H_2: &x+y-z-w\geq0 \\
    H_3: &x-y+z-w\geq0\ .
    \endalign$$
Letting $r=\frac{n+a+b+c}{2},s=\frac{n+a+b-c}{2},t=\frac{n+a-b+c}{2}$,
we have the following formulas.
    $$\vert Q_n^{H_1}(\bold{0}\to l) \vert =
    \left[\binom n{r}-\binom n{r+1}\right]\binom n{s} \binom n{t}\ .
    \tag3.2$$
In particular, if $a+b+c=0$ then
    $$\vert Q_n^{H_1}(\bold{0}\to l)\vert =
    C_{n/2}\binom n{s} \binom n{t}\ .
    \tag3.3$$
where the Catalan number is non-zero if and only if n is even.
Similarly
    $$\vert Q_n^{H_1\cap H_2}(\bold{0}\to l) \vert =
    \left[\binom n{r}-\binom n{r+1}\right]
    \left[\binom n{s}-\binom n{s+1}\right] \binom n{t}\ .
    \tag3.4$$
In particular, if $a+b=c=0$ then
    $$\vert Q_n^{H_1\cap H_2}(\bold{0}\to l) \vert =
    C_{n/2}^2 \binom n{t}\ .
    \tag3.5$$
Finally
    $$\align \vert Q_n^{H_1\cap H_2\cap H_3}(\bold{0}\to l) \vert =
    \left[\binom n{r}-\binom n{r+1}\right]
    \left[\binom n{s}-\binom n{s+1}\right]\\
    \left[\binom n{t}-\binom n{t+1}\right]\ .
    \tag3.6\endalign$$
In particular, if $a=b=c=0$ then
    $$\vert Q_n^{H_1\cap H_2 \cap H_3}(\bold{0}\to l) \vert =
    C_{n/2}^3\ .
    \tag3.7$$
The proofs in all cases are quite simple.  For example, to get (3.2)
merely note that  points of $p$ always satisfy $x+y+z+w\geq0$ if and only if
$x_1+y_1+z_1+w_1\geq x_2+y_2+z_2+w_2$ at each stage,
which is equivalent to the
number of N-steps of $p_1$ always being at least the number of S-steps.
 
Clearly, the above construction can be carried out in general,
although the description of the paths counted gets progressively
more complicated.  Every $n$-tuple $(p_1,\dots,p_n)$ of linear
paths corresponds to a
path $p$ in $2^{n-1}$ dimensions.  One obtains the appropriate table
by listing all the positive directions for $p$ and then all the
corresponding negative directions in reverse order.  The rows for
$(p_1,\dots,p_n)$ are obtained by counting in base 2 from 0 to $2^n-1$
and replacing 0's and 1's by N's and S's respectively.  This ensures
the crucial property that if a direction in $\bold{Z}^{2^{n-1}}$
corresponds to a given sequence of N's and S's then the
sequence for the negative of
that direction is obtained by changing each N to an S and vice versa.
The ending points of the $n$ linear paths only give us $n$
constraints, so we will only be able to count paths that end in
a certain affine subspace of dimension $2^{n-1}-n$.  It was a happy
coincidence that when $n=2$ this subspace was a point.  However,
the persevering reader should now be able to write down the equations
for general $n$ if they are desired.
 
For another method to enumerate paths staying in a given region
defined by hyperplanes (this time in 3 dimensions) see the paper of
Wimp and Zeilberger~\cite{WF}.
 
\subheading{4. Related problems}
One of us \cite{Gu} originally obtained some of the formulas in Section
2 by induction and other algebraic manipulations.  The desire to
obtain combinatorial proofs of these results was one of the stimuli
for the current work.  One such identity, which is considerably harder
to prove bijectively is
    $$|P^{++}_{2n-1}((0,0)\to(0,1))|=\frac{1}{2}C_nC_{n+1}.$$
A combinatorial demonstration of this fact using trees and Baxter
permutations will be found in the paper of Cori, Dulucq and Viennot~\cite{CDV}.
They also use their techniques to explain the connection with
Hamiltonian rooted maps on $2n$
vertices~\cite{Tu; Sl, sequence 1647}.
 
An open problem is as follows.  Let $l$ be the line $x+y=n-2$.
Then, by summing the values in equation (1.12), we obtain
    $$|P^{++}_n((0,0)\to l)|=(n-2)2^n+2.$$
It turns out that this is just twice the genus of the
$n$-cube~\cite{Ri; BH; Sl, sequence 1587}.
A combinatorial explanation would be welcome.
 
\Refs
\ref\key{BH}\by L. W. Beineke and F. Harary\paper The genus of the
$n$-cube\jour Canad. Math. J.\vol 17\yr 1965\pages 494--496\endref
 
\ref\key{BBCGNW}\by W. Breckenridge, P. Bos, G. Calvert, H.
Gastineau-Hills, A. Nelson and K. Wehrhahn\paper Lattice paths and
Catalan numbers\jour Bulletin of the Institute of Combinatorics and
Applications\vol 1\yr 1991\pages 41--55\endref
 
\ref\key{CDV}\by R. Cori, S. Dulucq and G. Viennot \paper Shuffle of
parenthesis systems and Baxter permutations\jour J. Combin\. Theory,
Ser. A \vol 43\yr 1986\pages 1--22\endref
 
\ref\key{CMS}\by E. Cs\'aki, S. G. Mohanty and S. Saran\paper On random
walks in a plane\jour Ars Combin\.
\vol 29\yr 1990\pages 309--318\endref
 
\ref\key{DR}\by D. W. DeTemple and J. M. Robertson\paper Equally likely
fixed length paths in graphs\jour Ars Combin\.
\vol 17\yr 1984\pages 243--254\endref
 
\ref\key{DJR}\by D. W. DeTemple, C. H. Jones and J. M. Robertson\paper A
correction for a lattice path counting formula\jour Ars Combin\.
\vol 25\yr 1988\pages 167--170\endref
 
\ref\key{Gu}\by R. K. Guy\paper Catwalks, sandsteps \& Pascal
pyramids\jour preprint\endref
 
\ref\key{Mo}\by S. G. Mohanty\book Lattice Path Counting
and Applications
\publ Academic Press \publaddr New York \yr 1979 \pages2--7\endref
 
\ref\key{Ri}\by G, Ringel\paper \"Uber drei kombinatorische Probleme
am $n$-dimensionalen W\"urfel und W\"urfelgitter\jour Abh. Math. Sem.
Univ. Hamburg\vol 20\year 1955\pages 10--19\endref
 
\ref\key{Sa}\by B. Sands\paper Problem 1517*\jour Crux Mathematicorum
\vol 16\yr 1990\page 44\endref
 
\ref\key{Sl}\by N. J. A. Sloane\book A Handbook of Integer
Sequences\publ Academic Press\publaddr New York\yr 1973\endref
 
\ref\key{Tu}\by W. T. Tutte\paper A census of Hamiltonian
polygons\jour Canadian\ Math.\ J.\vol 14\yr 1962\pages 402--417\endref
 
\ref\key{WZ}\by J. Wimp and D. Zeilberger\paper How likely is Polya's
drunkard to stay in $x\geq y\geq z$? \jour J. Statistical Physics
\vol 57 \yr 1989 \pages 1129--1135\endref
\enddocument
 
