%\documentclass[12pt,reqno]{amsbook}
%\input pathlate.sty
%\input sekrl
%\input priv
%\makeindex
%\makeglossary

\textwidth35pc
\textheight47pc
\hoffset-1.5truecm

%\begin{document}

\section{Planar four-directional paths}
In this section we enumerate various families of planar lattice
paths consisting of unit steps in directions N, S, E, or W, see
Figure~\ref{Fnsew1} for an example of such a lattice path.
Let us denote the corresponding step set by $\NSEW$, i.e.,
$\NSEW=\{(0,1),(0,-1),(1,0),(-1,0)\}$.
Such planar four-directional paths were first investigated by
DeTemple and Robertson \cite{DTRoAA} and Cs\'aki, Mohanty and
Saran \cite{CsMoAA}. 

\begin{Figure} \label{Fnsew1}
$$
\Einheit1cm
\Gitter(4,4)(-1,-2)
\Koordinatenachsen(4,4)(-1,-2)
\raise-1.5pt\hbox{\Pfad(0,0),1\endPfad
\Pfad(1,-1),2\endPfad
\Pfad(1,-1),12\endPfad}
\raise1.5pt\hbox{\Pfad(1,0),1\endPfad}
\Pfad(1,0),2\endPfad
\raise-1.5pt\hbox{\Pfad(0,1),1\endPfad}
\raise1.5pt\hbox{\Pfad(0,1),112\endPfad}
\DickPunkt(0,0)
\DickPunkt(2,2)
\Label\ru{P}(2,1)
\hskip2cm
$$
\end{Figure}

Now the question of how many such paths are there from a given
starting point to a given end point makes no sense, because there are
clearly infinitely many, unless we also fix the number of steps of
the paths. The solution to this problem is our first result.

\begin{Theorem} \label{T8.1}
The number of planar four-directional
paths with $n$ steps from the origin to $(c,d)$ is
\begin{equation} \label{nsew1}
\v{\L{(a,b)\to (c,d);\NSEW\mid\text {$n$ steps}}}=
\binom n {\frac{n-a-b+c+d}{2}}\binom n {\frac{n-a+b+c-d}{2}}\ ,
\end{equation}
where by convention the binomial coefficient $\binom nk$ is assumed
to be zero unless $k$ is a an integer $0\leq k \leq n$.
\end{Theorem}
\begin{proof} 
Clearly it suffices to prove the formula for $(a,b)=(0,0)$, upon
which \eqref{nsew1} follows upon translation.

We set up a correspondence between the four-directional paths $P$
which run from $(0,0)$ to $(c,d)$ in $n$ steps
and pairs $(P_1,P_2)$ of simple paths, $P_1$ running from $(0,0)$ to
$\(\frac {n+c+d} {2},\frac {n-c-d} {2}\)$, $P_2$ running from $(0,0)$ to
$\(\frac {n-c+d} {2},\frac {n+c-d} {2}\)$. In view of \eqref{e1.1} it
is then obvious that such a
bijection immediately implies \eqref{nsew1} with $a=b=0$.

To define the correspondence, we move along the path $P$. When we
encounter the $m$-th step of $P$, then we adjoin $m$-th steps to $P_1$ and
$P_2$ according to the table below. In this table, we use the
(obvious) abbreviations $N=(0,1)$, $S=(0,-1)$, $E=(1,0)$, $W=(-1,0)$.
$$\begin{matrix}
    \underline{P} & \underline{P_1} & \underline{P_2} \\
    \text{N} & \text{N}   & \text{N} \\
    \text{E} & \text{N}   & \text{E} \\
    \text{W} & \text{E}   & \text{N}  \\
    \text{S} & \text{E}   & \text{E}
    \end{matrix}$$
Thus, the path $P$ in Figure~\ref{Fnsew1} is mapped to the pair of paths
shown in Figure~\ref{Fnsew2}.

\begin{Figure} \label{Fnsew2}
$$
\Gitter(4,8)(0,0)
\Koordinatenachsen(4,8)(0,0)
\Pfad(0,0),2122121222\endPfad
\DickPunkt(0,0)
\DickPunkt(3,7)
\Label\r{P_1}(1,1)
\hbox{\hskip6cm}
\Gitter(6,6)(0,0)
\Koordinatenachsen(6,6)(0,0)
\Pfad(0,0),1112222112\endPfad
\DickPunkt(0,0)
\DickPunkt(5,5)
\Label\ru{P_2}(2,1)
\hbox{\hskip2.5cm}
$$
\end{Figure}
It is easy to verify that this correspondence has all the required
properties.
\end{proof}
 
Next we consider four-directional 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 four-directional paths. A list of  the  simplest of these is given below,
and more can be found in the next section. 

Now, here is the promised list.  
\begin{equation} \label{nsew3}
\v{\L{(0,b)\to (*,d);\NSEW\mid\text {$n$ steps}}} 
= \binom {2n}{n-d+b}\ . 
\end{equation}
 
For four-directional paths which do not pass below the $x$-axis
we can prove the following results:
With $r=\frac {1} {2}(n-a-b+c+d)$ and $s=\frac {1} {2}(n-a+b+c-d)$ we
have
\begin{align} 
 \v{\L{(a,b)\to (c,d);\NSEW\mid y\ge0,\text { $n$ steps}}}&\notag\\
=\binom nr \binom ns&-
    \binom n{r+b+1}  \binom n{s-b-1}\ ,\label{nsew4}\\
    \v{\L{(0,0)\to (c,*);\NSEW\mid y\ge0,\text { $n$ steps}}}
      &=\binom n{\lfloor \frac {n+c} {2}\rfloor}
      \binom n{\lfloor\frac {n-c} {2}\rfloor}\ .\label{nsew5}\\
    \v{\L{(0,b)\to (*,d);\NSEW\mid y\ge0,\text { $n$ steps}}}&
=\binom {2n}{n-d+b}-
      \binom {2n}{n-d-b-2}\ ,\label{nsew6}
\end{align}
in particular,
\begin{align} 
\v{\L{(0,0)\to (*,d);\NSEW\mid y\ge0,\text { $n$ steps}}}&
=\binom {2n+1}{n-d}-\binom
    {2n+1}{n-d-1}\ .\label{nsew7}\\
        \v{\L{(0,0)\to (*,0);\NSEW\mid y\ge0,\text { $n$ steps}}}&
=C_{n+1},\label{nsew8}
\end{align}
where $C_n$ is the $n$th Catalan number.
 
\begin{align} 
\v{\L{(0,0)\to (*,*);\NSEW\mid y\ge0,\text { $n$ steps}}}&
=\binom {2n+1}n\ .\label{nsew9}\\
    \v{\L{(0,1)\to (*,*);\NSEW\mid y\ge0,\text { $n$ steps}}}&
=\binom {2n+2}n\ .\label{nsew10}
\end{align}
 
Finally, for four-directional
paths confined to the first quadrant, we obtain the following.
\begin{multline} 
\v{\L{(a,b)\to (c,d);\NSEW\mid x,y\ge0,\text { $n$ steps}}}\\
=\binom nr \binom ns - \binom
    n{r+b+1}\binom n{s-b-1}\\
    - \binom n{r+a+1} \binom n{s+a+1} + \binom
    n{r+a+b+2} \binom n{s+a-b}\ ,\label{nsew11}
\end{multline}
with $r,s$ as in \eqref{nsew2}. In particular,
\begin{align} \notag
\v{\L{(0,0)\to (c,d);\NSEW\mid x,y\ge0,\text { $n$ steps}}}&\\
=\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}\ .\label{nsew12}\\
\notag
    \v{\L{(0,0)\to (c,*);\NSEW\mid x,y\ge0,\text { $n$ steps}}}&\\
=\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}\
    .\label{nsew13}\\
    \v{\L{(0,0)\to (*,*);\NSEW\mid x,y\ge0,\text { $n$ steps}}}&
=\binom {n}{\lfloor\frac {n} {2}\rfloor}
    \binom {n+1}{\lfloor\frac {n+1} {2}\rfloor}\ .\label{nsew14}
\end{align}
Equation \eqref{nsew9} was first discovered by Sands \cite{SandAA} and was the
starting point of our investigations.
 
Results from Gouyou--Beauchamps \cite{GouyAB}:
\begin{align} \label{nsew15}
\v{\L{(0,0)\to (*,0);\NSEW\mid 0\le y\le x,\text { $2n$ steps}}}&
=C_nC_{n+1}.\\
\v{\L{(0,0)\to (*,0);\NSEW\mid 0\le y\le x,\text { $2n+1$ steps}}}&
=C_{n+1}^2.
\end{align}

In the next section we provide combinatorial proofs for all these
formulas. We also derive counting results about four-directional 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 four-directional paths and
simple 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 and Wehrhahn \cite{BrBCAA} have independently
discovered essentially the same formulas and bijective proofs for
\eqref{nsew1} to \eqref{nsew4}, \eqref{nsew6}, \eqref{nsew8} and \eqref{nsew9}.
Related bijections
have also been considered in~\cite{CsMoAA} and
by Gessel [private communication].
 
 
Of course, several of these results follow directly from others on the list
by simple algebraic manipulations. For example, \eqref{nsew9} can be deduced
from \eqref{nsew7} 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 \eqref{nsew5}, \eqref{nsew10},
\eqref{nsew13}, \eqref{nsew14}).
 
 
Proof of \eqref{nsew1} and \eqref{nsew2}.  
Formula \eqref{nsew2} now follows by translation.\quad \qed
 
\medskip
Proof of \eqref{nsew3}.  Here we use another correspondence
between four-directional paths, $p$, and simple 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 \eqref{nsew1}.
$$\begin{matrix}
    \underline{p} & \underline{{\bar p}} \\
    \text{N} & \text{NN} \\
    \text{E} & \text{NS} \\
    \text{W} & \text{SN}  \\
    \text{S} & \text{SS}
    \end{matrix}$$
This sets up a one-to-one correspondence between four-directional paths with $n$ steps
from $(0,b)$ to $(*,d)$ and
simple paths with $2n$ steps from $(0,2b)$ to $(0,2d)$.  Applying a
translated version of
formula (2.1), we are done.\quad \qed
 
\medskip
Proof of \eqref{nsew4} and \eqref{nsew6}. These follow from \eqref{nsew2} and \eqref{nsew3}
respectively by the
reflection principle.  For \eqref{nsew4}, note that the total number of
four-directional 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 \eqref{nsew2} we see that these paths are
counted by
$\binom n{r+b+1}\binom n{s-b-1}$.
 
Similarly, in \eqref{nsew6} 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
 
\medskip
Proof of \eqref{nsew7} and \eqref{nsew8}.  We use the same correspondence as in the
proof of \eqref{nsew3}, except that the $m$-th step of $p$ determines the
$2m$-th and $(2m+1)$-st step of ${\bar p}$.  The first step of ${\bar p}$ is
always taken to be N so ${\bar p}$ 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
${\bar p}$ 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 \eqref{nsew7}.
(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
 
 
\medskip
Proof of \eqref{nsew9} and \eqref{nsew10}.
To prove \eqref{nsew9}  we first  apply the
correspondence in the proof of \eqref{nsew7} to get a bijection
    $$P_n^{+}((0,0)\to(*,*)) \longleftrightarrow \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)\longleftrightarrow\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\begin{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.}\end{cases}$$
Clearly this is a bijection
    $$L_{2n+1}(0\to1)\longleftrightarrow
    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 \eqref{nsew5}
and related identities.
 
\medskip
The same idea will give a bijection
    $$\bigcup _{j\ge 0}L_{2n} ^{+}(2b+1\to 2l+1+(4b+4)j)\longleftrightarrow
    L_{2n}(2b+1\to 2l+1)\ .$$
Moreover, the last bijection also provides the following bijection,
    $$\bigcup _{j\ge 0}L_{2n} ^{+}(2b+1\to 2j+1)\longleftrightarrow
    \bigcup _{l=0} ^{2b+1}L_{2n}(2b+1\to 2l+1)\ .$$
Since, by the bijection used to establish \eqref{nsew6}, the set $L_{2n}
^{+}(2b+1\to 2j+1)$ is in one-to-one correspondence with $P^+_n((0,b)
\to (*,*))$, we have a bijective proof of the formula
    $$\v{P^+_n((0,b)\to (*,*))} = \sum _{j=0} ^{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
\begin{align} \notag
\v{P^+_n((0,b)\to (*,*))}
    &= \sum _{j=0} ^{b} \left[\binom {2n}{n+j} +
    \binom{2n}{n+j+1} \right] \\
    &= \sum _{j=1} ^{b+1} \binom {2n+1}{n+j}\ .\notag
\end{align}
In particular, for $b=0$ we obtain \eqref{nsew9} again, while for $b=1$ we
get \eqref{nsew10}  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
 
\medskip
Proof of \eqref{nsew11} and \eqref{nsew12}. The inclusion-exclusion principle shows
that the number of paths being elements of $P^{++}_n((a,b)\to (c,d))$
is equal to the number of all four-directional 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 \eqref{nsew4}
 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
\eqref{nsew2} the desired number is
given by the right-hand side of \eqref{nsew11}. Setting $a=b=0$
in \eqref{nsew11} and using the binomial recursion repeatedly,
we obtain \eqref{nsew12}.\quad \qed
 
\medskip
Proof of \eqref{nsew5}, \eqref{nsew13} and \eqref{nsew14}. Let us introduce another
correspondence, this time between families of four-directional paths themselves.
For a path $p\in P_n((a,b)\to (c,d))$ we apply the map
$$p\longrightarrow\begin{cases} p&\text {if }p\in P^+_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.}\end{cases}$$
This is a bijection
$$P_n((a,b)\to (c,d))\longleftrightarrow P^+_n((a,b)\to (c,d))\cup P_n((a,b)\to
(c,d+(2b+2)))\ .$$
Applying the same map to $P_n((a,b)\to (c,d+(2b+2)))$, etc., we get a
bijection
$$P_n((a,b)\to (c,d))\longleftrightarrow \bigcup _{j\ge 0}P^+_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 _{j=0} ^{b}P_n((a,b)\to (c,d+2j))\longleftrightarrow P^+_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 _{j=0} ^{b}P_n((a,b)\to (c,d+1+2j))\longleftrightarrow P^+_n((a,b)\to
(c,\ge d))\ .$$
Putting both together and using the basic result \eqref{nsew2},
leads to the following expression for the
cardinality of $P^+_n((a,b)\to
(c,\ge d))$:
$$\v{P^+_n((a,b)\to
(c,\ge d))} = \sum _{j=0} ^{b}\binom n{\lfloor r\rfloor-j}\binom
n{\lfloor s\rfloor-j}\ .\tag2.5$$
In particular, for $a=b=0$ we get
$$\v{P^+_n((0,0)\to
(c,\ge d))} =\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 \eqref{nsew5}.
 
\medskip
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_n((a,b)\to (c,d))\longleftrightarrow \bigcup _{i,j\ge 0}P^{++}_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
\begin{multline}
\bigcup _{i=0} ^{a}\bigcup _{j=0} ^{b}\Big(P_n((a,b)\to (c+2i,d+2j))
\cup P_n((a,b)\to (c+1+2i,d+1+2j))\Big)\\
 \longleftrightarrow P^{++}_n((a,b)\to
(\ge c,\ge d))
\end{multline}
can be constructed. In case $a+b+c+d\equiv n+1\pmod 2$, analogously
we construct a bijection
\begin{multline}
\bigcup _{i=0} ^{a}\bigcup _{j=0} ^{b}\Big(P_n((a,b)\to (c+1+2i,d+2j))
\cup P_n((a,b)\to (c+2i,d+1+2j))\Big)\\
 \longleftrightarrow P^{++}_n((a,b)\to
(\ge c,\ge d))\ .
\end{multline}
Again, putting both together and using the binomial recursion,
simple considerations
show that
\begin{multline}
\v{P^{++}_n((a,b)\to
(\ge c,\ge d))}\\
 =\sum _{i=0} ^{a}\sum _{j=0} ^{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!}\ .
\end{multline}
The specialization $a=b=0$ leads to the formula
$$\v{P^{++}_n((0,0)\to
(\ge c,\ge d))} =\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
$$\v{P^{++}_n((0,0)\to
(\ge c,*))} =\binom n{\lfloor\frac {n-c} {2}\rfloor}\binom
{n+1}{\lfloor\frac {n-c+1} {2}\rfloor}\ ,  \tag2.10$$
which directly implies \eqref{nsew13}. Equation \eqref{nsew14} is the
special case $c=0$ of (2.10).\quad \qed
 


\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{CoDVAA}.
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 \eqref{nsew12}, 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.
 
Gouyou-Beauchamps, LN~1234!!, \cite{GouyAA}??

Cs\'aki, Dulucq--Viennot--Guibert: Baxter permutations!!


%\end{document}
 
