
% Final submission of Duchi and Sulanke to Sem.  Lotharingien
% April 2004

\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{amsmath}

\setlength{\topmargin}{22pt}
\setlength{\textheight}{595pt}





\newcommand{\alphaa}{\alpha}
\newcommand{\betaa}{\beta}
\newcommand{\gammaa}{\gamma}
\newcommand{\deltaa}{\delta}
\newcommand{\epsilonn}{\epsilon}
\newcommand{\etaa}{\eta}
\newcommand{\phii}{\phi}
\newcommand{\kappaa}{\kappa}
\newcommand{\lambdaa}{\lambda}
\newcommand{\muu}{\mu}
\newcommand{\nuu}{\nu}
\newcommand{\pii}{\pi}
\newcommand{\rhoo}{\rho}
\newcommand{\sigmaa}{\sigma}
\newcommand{\tauu}{\tau}


\renewcommand{\baselinestretch}{1.1}
\newtheorem{Lemma}{Lemma}
\newtheorem{Proposition}{Proposition}
\newtheorem{Example}{Example}

\begin{document}

\title{
The $2^{n-1}$ factor for multi-dimensional lattice paths\\ with diagonal steps
}


\author{E.~Duchi\footnote{Dipartimento di Sistemi e Informatica,
 Universit\`a di Firenze, Firenze, It. {\tt duchi@dsi.unifi.it}} \ 
and R.~A.~Sulanke\footnote{Dept. of Mathematics, Boise State University,
 Boise, ID, U.S.A. {\tt sulanke@math.boisestate.edu}} }

\date{}
\maketitle



     


\begin{abstract}
In  $\mathbb{Z}^d$,
let 
$\mathcal{D}(n)$ denote the set of lattice  paths from the origin to
$(n,n,\ldots,n)$ that use nonzero steps of the form $(x_1,x_2, \ldots, x_d)$ where
$x_i \in \{ 0,1\}$ for $1 \le i \le d$.
Let $\mathcal{S}(n)$ denote the set of lattice paths from the origin  to
$(n,n,\ldots,n)$ that use  nonzero steps of the form  $(x_1,x_2, \ldots, x_d)$
where   $x_i \ge 0$ for  $1 \le i \le d$.
For  $d=3$, we prove  bijectively that  the cardinalities 
satisfy  
$|\mathcal{S}(n)| = 2^{n-1}  |\mathcal{D}(n)|$  
for $n
\ge 1$.  One can extend our  method to any dimension  and obtain the same
identity.  We find an explicit formula for $|\mathcal{D}(n)|$ when $d=3$.

\

\noindent Key words: Lattice paths, Delannoy numbers.
\end{abstract}

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 51 \rms (2004), Article~B51c\hfill}
\def\thepage{}
%
%

\section{Introduction}
\label{Introduction}

\indent

In
 $d$-dimensional space $\mathbb{Z}^d$, consider  a lattice path 
 to be  represented as a
 concatenation  of  directed steps.
 Let $\mathcal{D}(n)$ denote the set of paths from $(0,0,\ldots,0)$ to
 $(n,n,\ldots,n)$ using nonzero steps of the form $(x_1,x_2, \ldots, x_d)$ where
 $x_i \in \{ 0,1\}$ for $1 \le i \le d.$  These steps are the positive steps, including the diagonal ones, between
vertices of a unit hypercube. 
 Let $\mathcal{S}(n)$ denote the set of paths from $(0,0,\ldots,0)$ to
 $(n,n,\ldots,n)$ using the steps of the form  $(x_1,x_2, \ldots, x_d)$
 where  the $x_i$'s are nonnegative integers, not all zero.  
 The paths of $\mathcal{S}(n)$ correspond to 
 MacMahon's \cite[sect. IV]{MacMahonComb} 
 ``compositions of the  multipartite number $(n,n,\ldots, n)$''.
 
 Our main result is a bijective proof  
 that, for any dimension and  for $n
 \ge 1$, the cardinalities $|\mathcal{D}(n)|$ and $|\mathcal{S}(n)|$  satisfy 
 \begin{equation}\label{mainresult}  
     |\mathcal{S}(n)| = 2^{n-1}  |\mathcal{D}(n)|.
 \end{equation}
 
In the 2-dimensional case,  the numbers $(|\mathcal{D}(n)|)_{n\ge0} =
1, 3, 13, 63, 321, 1683, 8989, \ldots$ are the central Delannoy numbers with
   $|\mathcal{D}(n)| = \sum_{0\le k\le n}{\binom n  k}^2 2^k$.
For $d=2$, explicit formulas and generating functions for  $(|\mathcal{D}(n)|)_{n \ge 0}$
and     $(|\mathcal{S}(n)|)_{n \ge 0}$ appear under  A001850 and A052141
 in \cite{Sloane}.   
  For $d=2$,   identity~(1) 
 appears in an exercise in Stanley \cite[Exercise 6.16]{StanleyBookII}
 with a   bijective proof appearing  in 
 \cite{SulNarPol}.  
Recently, Humphreys and Niederhausen \cite{HumphreysNiederhausen}
applied techniques of the umbral calculus to obtain (1) for $d=2$.
 For further information regarding the Delannoy numbers, see the
historical note on the work and life of Henri Delannoy given by Banderier and Schwer \cite{BanSch}.  See also the collection
of 29 configurations counted by the Delannoy numbers given 
by Sulanke \cite{SulColl}.
Recently, he  \cite{SulNarMany} has used
different bijective techniques to show that  identity~(1) holds for any
dimension when the sets $\mathcal{D}(n)$ and  $\mathcal{S}(n)$ are restricted
to contain 
those paths lying in the region $\{(x_1,x_2,\ldots,x_d) : x_1 \le x_2 \le \ldots \le x_d \}$.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
%\markboth{\SMALL ROLAND BACHER AND LAURENT MANIVEL}{\SMALL HOOKS AND POWERS OF\ PARTS IN PARTITIONS}
%
%

For dimension $d=3$ and $n \ge 0$, 
formula (\ref{bigsum}) of Section \ref{finalsection} yields 
$$|\mathcal{D}(n)| =   
\sum_{i=0}^n\sum_{j=0}^{n-i}\sum_{k=0}^n 
{\binom n i} 
 {\binom {n-i}  j}
 {\binom n  k} 
{\binom {n+i }  {i+j}}
{\binom n  {i+k}}  2^{i+j+k}. $$
One then finds that 
\begin{eqnarray*}
    (|\mathcal{D}(n)|)_{n\ge0} &=&1, 13, 409, 16081, 699121, 32193253, 1538743249, \ldots  \\
(|\mathcal{S}(n)|)_{n\ge0} &=& 1, 13,818,64324,5592968,515092048,49239783968, \ldots 
\end{eqnarray*}

With  the notation of Section \ref{Notation},
we  prove identity~(1) for dimension $d=3$ by a series of bijections
in a manner that can be routinely
extended to any dimension:
 $$ \mathcal{S}(n)\longrightarrow \mathcal{L}'(n)
 \longrightarrow \mathcal{L}^*(n)\times 2^{[n-1]}
 \longrightarrow Z\mathcal{L}^*(n)\times 2^{[n-1]} 
 \longrightarrow Z\mathcal{L}^{**}(n)\times 2^{[n-1]}  
  $$ 
  \begin{equation}\label{threedelnumber} 
 \longrightarrow Y\mathcal{L}^{**}(n)\times 2^{[n-1]}
 \longrightarrow \mathcal{L}''(n)\times 2^{[n-1]}
 \longrightarrow \mathcal{D}(n)\times 2^{[n-1]}, 
\end{equation}
 where $2^{[n-1]}$ is the power set of $[n-1] = \{1,2,
 \ldots, n-1\}$.  
In Section \ref{Notation} we give an explanation of  our notation 
and a more extensive overview of our proof of identity~(1).
Sections \ref{bijection1} through \ref{bijection3}
define the bijections used in
(\ref{threedelnumber}).  

In the final section we consider 
the set of lattice paths from the origin to $(n_1,n_2,n_3)$ 
using the unit steps $X,
 Y$, and $Z$.  We discuss some statistics  
 for  paths in this set. We then generalize these  statistics
 and outline 
 the proof  of identity~(\ref{mainresult}) for  dimensions $d > 3$.
 We  briefly examine a generalization  of 
 identity~(\ref{mainresult}) for the
 non-central case. 
 For completeness, 
 we mention some results on 
 generating functions which appeared in MacMahon's work \cite{MacMahonComb}.
 


\section{Notation and overview of proof}\label{Notation}  

\indent

From the context it will be clear whether the notation $(x,y,z)$  
denotes  a point in $\mathbb{Z}^3$
or denotes   a step  from an arbitrary point $(x_0,y_0,z_0)$ to
the point $(x_0+x,y_0+y,z_0+z)$.
We will denote the unit steps as $X$, $Y$, and $Z$, where 
$X  = (1,0,0)$, $Y  = (0,1,0)$, and $Z  = (0,0,1)$.

Let $\mathcal{L}(n)$ denote the set of lattice paths from $(0,0,0)$ to
$(n,n,n)$ using the unit steps $X$, $Y$, and $Z$.  For any path, 
in order to mark the intermediate  vertex
between two adjacent steps $S_i$ and  $S_{i+1}$  
by a color $c$, $c \in \{ b,r\}=\{\mbox{blue},\mbox{red}\}$,  we will replace $S_iS_{i+1}$ by $S_icS_{i+1}$ in the
concatenation representing the path.  

Table \ref{table1} summarizes 
the notation for the various sets of lattice
paths used in the proof.  
In the table, the term  ``section'' refers to the section where the notation
first appears. The phrase 
``colored pairs'' refers to those step pairs having independently
colored blue or red intermediate vertex.  All other intermediate vertices 
and the point $(n,n,n)$ are red.
Notice that path sets with the same superscripting (i.e., 
asterisk,  double asterisks, and double prime) 
have essentially the same vertex coloring schemes.



\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
 set &section & steps  & initial & final & colored pairs \\
        &          & used   & point   & point &          \\
        \hline
$\mathcal{L}(n)$ & \S 2 & $X$, $Y$, $Z$ & $(0,0,0)$ & $(n,n,n)$ &   \\
$\mathcal{L}'(n)$&\S 3& $X$, $Y$, $Z$ &$(0,0,0)$ &$(n,n,n)$& $XX, YX,
YY,ZX,ZY,ZZ$ \\
$\mathcal{L}^*(n)$&\S 4& $X$, $Y$, $Z$ &$(0,0,0)$ &$(n,n,n)$& $
YY,ZY,ZZ$ \\
$Z\mathcal{L}(n)$&\S 5& $X$, $Y$, $Z$ &$(0,0,-1)$ &$(n,n,n)$&\\
$Z\mathcal{L}^*(n)$&\S 5& $X$, $Y$, $Z$ &$(0,0,-1)$ &$(n,n,n)$&$
YY,ZY,ZZ$  \\
$Y\mathcal{L}_2(n)$&\S 6& $X$, $Y$  &$(0,-1,0)$ &$(n,n,0)$&\\
$Z\mathcal{L}_2(n)$&\S 6& $X$,  $Z$ &$(0,0,-1)$ &$(n,0,n)$&\\
$Z\mathcal{L}^{**}(n)$&\S 7& $X$, $Y$, $Z$ &$(0,0,-1)$ &$(n,n,n)$&$
YY,ZY,\mbox{\it non-origin $ZX$}$\\
$Y\mathcal{L}(n)$&\S 7& $X$, $Y$, $Z$ &$(0,-1,0)$ &$(n,n,n)$&
\\
$Y\mathcal{L}^{**}(n)$&\S 7& $X$, $Y$, $Z$ &$(0,-1,0)$ &$(n,n,n)$&$
YY,ZX,ZY$\\
$Y\mathcal{L}''(n)$&\S 7& $X$, $Y$, $Z$ &$(0,-1,0)$ &$(n,n,n)$&
$
ZX, ZY,\mbox{\it non-origin $YX$}$ \\
$\mathcal{L}''(n)$ &\S 7&$X$, $Y$, $Z$ &$(0,0,0)$ &$(n,n,n)$& 
$
YX,ZX, ZY$\\ 
\hline
\end{tabular}
\end{center}
\caption{Notation for path sets}
\label{table1}
\end{table}


This and the following  paragraphs indicate  an overview
of 
our proof of identity~(1).  
Through a series of bijections in Sections \ref{bijection1}, 
\ref{bijection2}, and \ref{funbegins},  
we  encode each path in $\mathcal{S}(n)$, which uses  
 steps  of arbitrary length,
by a pair, say  $(ZP^*,A) $, where 
 $ZP^* \in Z\mathcal{L}^*(n)$
and  $A$ is  a subset of $[n-1]$.       On any path 
$P' \in \mathcal{L}'(n)$, ignoring  the first $X$ step on any
path,
the set $A$ encodes the coloring of the remaining $n-1$
initial vertices of the $X$ steps on $P'$. 
 It is 
 the cardinality of the 
 collection of all such subsets which accounts 
 for the factor $2^{n-1}$ of identity~(1). 


In Sections \ref{bijectionaux} and \ref{bijectioneta},
we transform each path $ZP^* \in Z\mathcal{L}^{*}(n)$ into
a path 
 $ZP^{**} \in Z\mathcal{L}^{**}(n)$.  Essentially, the
 colors on the intermediate vertices of the $ZZ$'s
move to the non-origin vertices
of $ZX$'s while the colors on the intermediate vertices of the
$YY$'s and $ZY$'s are preserved under the transformation
$Z\mathcal{L}^*(n)
 \longrightarrow Z\mathcal{L}^{**}(n)$.  
To make this transformation   we first keep unaltered, as 
{\it labeling words},
 the $Y$ steps and the colors appearing between successive 
 (not necessarily adjacent)  steps of types
 $X$ and  $Z$. 
 E.g., we have underlined the labeling words in the following
 path: $$Z\underline{b}Z\underline{bYbYrYr}X \underline{r}
X \underline{r}X \underline{r}Z \underline{bYr}Z\underline{r}
Z\underline{b}Z\underline{r}X\underline{r}
\in Z\mathcal{L}^*(n).$$
We next   
 project the path  $ZP^*$ orthogonally onto the $x$-$z$-plane  so that 
the labeling words  become
labels for intermediate vertices of 
 the $ZZ$, $ZX$, $XZ$, and $XX$ pairs on the resulting 2-dimensional path.
Using the maps of Section \ref{bijectionaux}, we then transform this
2-dimensional path to a  new 2-dimensional path
 so that each $ZZ$ pair, together with its labeling word, 
maps  to a $ZX$ pair, and vice-versa,
 and so that all other  labeling words  map similarly.
Finally, we expand the labeling words on the new 2-dimensional path
to obtain a 3-dimensional path $ZP^{**} \in Z\mathcal{L}^{**}(n)$.

 After changing the initial step from $Z$ to $Y$,  analogously 
we transform
 each $YP^{**}$ to a path $P'' \in \mathcal{L}''(n)$.
 We complete the proof  of (\ref{mainresult}) in Section \ref{bijection3}
by transforming each path $P''$ into 
a path belonging to $\mathcal{D}(n)$ by
changing blue colored step  pairs and triples (i.e., $ZbYbX$) into diagonal steps.




\section{The bijection 
$\mathcal{S}(n)$ to $\mathcal{L}'(n)$}\label{bijection1}


 \indent 
 
 Let $\mathcal{L}'(n)$  denote the set of paths formed from the paths of 
$\mathcal{L}(n)$  by independently coloring with $b$ and $r$
the intermediate vertices of 
$XX$, $YX$, $YY$, $ZX$, $ZY$, and  $ZZ$, and by coloring with $r$
the other intermediate vertices. 

We define the bijection 
     $$ \alphaa  : \mathcal{S}(n) \longrightarrow  \mathcal{L}'(n) $$
to be a morphism that   sequentially  applies  
the following replacement rules to each path: for $x>0$,  $y>0$, and  $z>0$,

$$
\begin{tabular}{lll}
    $(x,0,0)$ & $\longrightarrow$ & $X(bX)^{x-1}$ \\
         $(0,y,0)$ & $\longrightarrow$ & $Y(bY)^{y-1}$ \\
         $(0,0,z)$ & $\longrightarrow$ & $Z (bZ)^{z-1}$ \\
          $(x,y,0)$ & $\longrightarrow$ & $Y(bY)^{y-1}(bX)^{x}$ \\
          $(x,0,z)$ & $\longrightarrow$ & $Z(bZ)^{z-1}(bX)^{x}$ \\
          $(0,y,z)$ & $\longrightarrow$ & $Z(bZ)^{z-1}(bY)^{y}$ \\
           $(x,y,z)$ & $\longrightarrow$ & $Z(bZ)^{z-1}(bY)^{y}(bX)^{x}$, \\
\end{tabular} 
$$
and then assigns color  $r$  
to all non-$b$ intermediate vertices on the resulting path.
Here the exponents indicate multiple factors in the
concatenation; the color $b$  marks intermediate vertices.
See  Examples 1 and 2
 in the following section. (One might glean the bijection 
 $\alpha$ from an encoding for compositions of
tripartite numbers given by MacMahon \cite[sect. IV]{MacMahonComb}.)
   





\section{The bijection 
$\mathcal{L}'(n)$   to $\mathcal{L}^{*}(n) \times 2^{[n-1]}$}
\label{bijection2}


\indent 

Let $\mathcal{L}^*(n)$ denote the set of paths formed from the paths of 
$\mathcal{L}(n)$
by independently coloring with $b$ and $r$ the intermediate vertices of
all $YY$,   $ZY$, and $ZZ$ pairs together with all  vertices  $(0,0,0)$
that precede a $Y$ or $Z$  step.  All other vertices, including $(n,n,n)$
are red.

We now define a bijection  
     $$ \betaa : \mathcal{L}'(n)  
           \longrightarrow \mathcal{L}^{*}(n) \times 2^{[n-1]}.  $$
For $P' \in \mathcal{L}'(n)$,  let $(P^{*}, A) = \betaa(P')$, where
  \begin{itemize}
  \item[(i)]   The path $P^{*}$ traces the same 
  points  in $\mathbb{R}^3$ as $P'$ does.   Momentarily, give $P^{*}$ 
  the coloring of $P'$.
\item[(ii)]   If the first occurrence of an $X$ step  in the 
path $P'$ in $\mathcal{L}'(n)$ is immediately preceded 
  by    a $b$ vertex, then color the point $(0,0,0)$  on   $P^{*}$ 
  by   $b$; if otherwise, color it  
  by   $r$.  
  
  \item[(iii)]   Let $A$  be the set of all $i$,  $1 \le i \le n-1$,
  for which the initial vertex of the $(i+1)$-st $X$ on $P'$ is red. Equivalently,  $A$  is 
  the set of all $x$, $x>0$, such that  $(x,y,z)$ is an  $r$ colored initial vertex of an $X$ step on $P'$.
  \item[(iv)] Color red  all the intermediate 
  vertices of $XX$, $XY$, $XZ$, $YX$, $YZ$, and $ZX$ pairs, together with
  $(n,n,n)$ on  $P^{*}$. 
(Items (ii) and  (iii) preserve  any lost information.)
  \end{itemize}

\begin{Example} 
{\rm  If
  $S = (0,2,1)(2,1,0)(1,1,1)
(1,0,2) \in \mathcal{S}(4)$, then 
$$\alpha(S) = P' = ZbYbYrYbXbXrZbYbXrZbZbX \in \mathcal{L}'(4)$$ and 
$ P^* = bZbYbYrYrXrXrZbYrXrZbZrXr \in \mathcal{L}^*(4)$ 
with $A = \emptyset$. Here  the origin is blue since the first 
$X$ in $P'$ has a blue initial vertex; 
$A = \emptyset$ since  none of the following  $X$'s in $P'$ have
a red initial vertex.  This example will  continue through the paper.}
\end{Example}


\begin{Example}{\rm  If $S = ( 0,2,1)( 2,0,0)( 1,0,0)(1,2,3)$, then  
 $$\alpha(S) = P' =  ZbYbYrXbXrXrZbZbZbYbYbX \in \mathcal{L}'(4)$$ and
$ P^* =    rZbYbYrXrXrXrZbZbZbYbYrXr \in \mathcal{L}^*(4)$.
Here  the origin is red since the first $X$ in $P'$ has a red initial vertex; 
also $A = \{ 2 \}$ since  the third $X$ in $P'$ has a red initial vertex.}
\end{Example}







\section{Labeling words and the bijection
$\epsilonn:\mathcal{L}^{*}(n) $  to
$Z\mathcal{L}^*(n)$} \label{funbegins}

 \indent 
 
 Let $Z\mathcal{L}(n)$ 
 denote the set of paths using the steps $X$, $Y$, and $Z$,  
 beginning with a $Z$ step and running from $(0,0,-1)$, through $(0,0,0)$, 
 and on to $(n,n,n)$.
Let $Z\mathcal{L}^{*}(n)$ 
 denote the set of paths formed from the paths of 
$Z\mathcal{L}(n)$
by independently coloring with $b$ and $r$ the intermediate vertices of
 all  $YY$,   $ZY$, and $ZZ$ pairs.

 

Here we introduce the notion of a {\it labeling word} and 
then define a simple bijection.
Suppose that $P^* \in  \mathcal{L}^{*}(n)$ is factored as
$$ P^* = Y_0S_1Y_1S_2Y_2\cdots S_iY_i \cdots S_{2n}Y_{2n}
$$
 where 
 \begin{itemize}
\item[(i)]   $S_i \in \{X,Z\}$ for $1 \le i \le 2n$,
\item[(ii)]  $Y_i$ is a subpath
that  is just a color or 
     appears as $Y_i = c_{i0}Yc_{i1}Yc_{i2} \cdots Yc_{ij_i}$ with $c_{ih} \in \{b,r\}$,
       for  $0 \le h \le j_i$,
        for  $0 \le i \le 2n$.  We will refer to any such subpath  as a {\it labeling word}.
\item[(iii)]  $Y_0 = c_{00}Yc_{01}Yc_{02}
\cdots Yc_{0j_0}$ with $c_{0h} \in \{b,r\},$
        for  $0 \le h \le j_0$ if $P^*$ begins with a $Y$ step,
\item[(iv)]     $Y_0 = c_{00}$  if $P^*$ begins with an $X$ or $Z$ step.
\end{itemize}

We define a simple  bijection:
$$\epsilonn:\mathcal{L}^{*}(n)\longrightarrow  Z\mathcal{L}^*(n).$$
where 
\begin{equation}
\epsilonn(P^*) =  
ZP^* =  ZY_0S_1Y_1S_2Y_2\cdots S_iY_i \cdots S_{2n}Y_{2n}
\label{expressed} 
\end{equation}
where the initial $Z$ begins at $(0,0,-1)$.
In effect, the notation of this section has mapped a path in $\mathcal{L}^{*}(n)$ to a 2-dimensional path in the $x-z$ plane with the labeling words marking
the new path's vertices.

\begin{Example}\label{Example3}{\rm  
This continues Example 1.  With  the labeling words 
$Y_0 =b $, $Y_1 =bYbYrYr $,  $Y_4 =bYr $, 
$Y_6 =b $,  and $Y_2= Y_3 = Y_5 = Y_7 =  Y_8 = r $,   
$$\epsilon(P^*) = \epsilon(bZbYbYrYrXrXrZbYrXrZbZrXr) = ZY_0ZY_1XY_2XY_3ZY_4XY_5ZY_6ZY_7XY_8.$$}
\end{Example}



\section{Auxiliary bijections for two-dimensional paths.}
\label{bijectionaux}


 \indent 
 
 Let $Y\mathcal{L}_2(n)$   denote the set of 
2-dimensional paths restricted to the
 plane $z=0$
 using the steps $X$ and $Y$ and running from $ (0,-1,0)$, 
 through $(0,0,0)$, 
 to $(n,n,0)$.
Similarly, let $Z\mathcal{L}_2(n)$   denote the set of paths restricted to the
 plane $y=0$ 
 using the steps $X$ and $Z$ and running from $(0,0,-1)$, through $(0,0,0)$, 
  to $(n,0,n)$. 
  
 For paths in   $Y\mathcal{L}_2(n)$ (in $Z\mathcal{L}_2(n)$, resp.),  \begin{itemize}
\item A {\it double rise}\ is the intermediate vertex of a consecutive $YY$
pair ($ZZ$, resp.).
\item A {\it non-origin descent} \ is
    the intermediate vertex of a consecutive $YX$ ($ZX$, resp.) that is not
    $(0,0,0)$.
\item An {\it otherwise point} \ is an intermediate vertex 
which is absent from  the above categories or the final vertex on a path.
An {\it ascent}, i.e.,
the intermediate vertex of a consecutive $XY$ ($XZ$, resp.), is an
 example of an  otherwise point.
\end{itemize}

We now introduce two bijections for paths in the plane which will be applied in  the following section.  We define the first, denoted by $\delta_y$, and indicate that the second,  denoted by $\delta_z$,
is defined  similarly. 
\begin{Lemma}\label{lemmaone}    
For any $k$, $0 \le k \le n$, there is a bijection denoted as 
$$\gammaa_1 : \{P \in Y\mathcal{L}_2(n) : P \mbox{ has k ascents }\}\quad \quad \quad \quad \quad  \quad 
$$$$\quad \quad  \quad  \quad \quad  \quad  \longrightarrow    \{P \in Y\mathcal{L}_2(n) : P \mbox{ has n-k
ascents }\}.$$
\end{Lemma}

To define this bijection, let $P \in Y\mathcal{L}_2(n)$ with $k$ ascents,
located at 
$(x_1,y_1) \ldots (x_k,y_k)$.  These  ascents completely determine 
$P$.    Let $(x'_1,y'_1), \ldots, (x'_{n-k} ,y'_{n-k})$ be the increasing
sequence of points  satisfying
\begin{eqnarray*}
\{ x'_1, x'_2, \ldots, x'_{n-k} \} &=& \{1,2  \ldots, n \} -
\{ x_1, x_2, \ldots, x_{k} \}   \mbox{\  and }\\
\{ y'_1, y'_2, \ldots, y'_{n-k} \}  &=& \{0, 1,  \ldots, n-1 \} -
\{ y_1, y_2, \ldots, y_{k} \}.
\end{eqnarray*}
As ascents, the vertices
$(x'_1,y'_1), \ldots, (x'_{n-k} ,y'_{n-k})$ completely determine the path
$\gammaa_1(P)$
in a manner yielding the lemma. $\square$


\begin{Lemma}\label{lemmatwo} For any $P \in Y\mathcal{L}_2(n)$, 
$P$  has $k$ double rises if, and only if, it has $n-k$ ascents.
Hence, 
$$\gammaa_1 : \{P \in Y\mathcal{L}_2(n) : 
P \mbox{ has k double rises }\}\quad \quad \quad \quad \quad  \quad 
$$
$$\quad \quad  \quad  \quad \quad  \quad  \longrightarrow    
\{P \in Y\mathcal{L}_2(n) : P \mbox{ has k
ascents }\}.$$
\end{Lemma}

This from the fact that each noninitial $Y$ step is  preceded by either
a  $Y$ or an $X$ step and from Lemma \ref{lemmaone}.
(Such a result fails on $\mathcal{L}_2(n)$;
the $Y$ at the start of each path in $Y\mathcal{L}_2(n)$ is required.) $\square$


\begin{Lemma}\label{lemma3}
For any $k$, $0 \le k \le n$, there is a bijection denoted as 
$$\gammaa_2 : \{P \in Y\mathcal{L}_2(n) : P \mbox{ has k ascents }\}\quad \quad \quad \quad \quad  \quad 
$$$$\quad \quad  \quad  \quad \quad  \quad  \longrightarrow    \{P \in Y\mathcal{L}_2(n) : P \mbox{ has k
non-origin descents }\}.$$
\end{Lemma}

For each  $P \in Y\mathcal{L}_2(n)$, reflect about the line $y=x$
the subpath of $P$ running from $(0,0)$ to $(n,n)$. $\square$
 
 
\begin{Lemma}\label{lemma4}
 For any $k$, $0 \le k \le n$, there is a bijection, 
 $\deltaa_y : Y\mathcal{L}_2(n) \rightarrow  Y\mathcal{L}_2(n)$,
 such that  $P \in Y\mathcal{L}_2(n)$ has $j$ non-origin  descents if, and only if, 
$\deltaa_y(P)$ has $j$ double rises.  Likewise,
there is a bijection, 
 $\deltaa_z : Z\mathcal{L}_2(n) \rightarrow  Z\mathcal{L}_2(n)$,
 such that  $P \in Z\mathcal{L}_2(n)$ has $j$ non-origin  descents if, and only if, 
$\deltaa_z(P)$ has $j$ double rises.
\end{Lemma}

To see this for $\deltaa_y$, define ($\deltaa_z$ is defined analogously.) 
 $$\deltaa_y =\gammaa_2 \circ \gammaa_1: \{P \in Y\mathcal{L}_2(n) :  \mbox{\it P has k double rises}\}\quad \quad \quad \quad \quad  \quad 
$$
$$\quad \quad  \quad  \quad \quad  \quad  \longrightarrow    \{P \in Y\mathcal{L}_2(n) :  \mbox{\it P has k
  non-origin  descents}\}.  \quad \square$$ 

\

{\bf A note on  indexing the vertices  of the  paths  of $Y\mathcal{L}_2(n)$ and
$Z\mathcal{L}_2(n)$:} 
For each path of $Y\mathcal{L}_2(n)$ having $k$ double rises, index the
intermediate vertices of its double rises  by assigning 
 $1, \ldots, k$,  in order of their position on the path.
Likewise, index its $j$  non-origin  descents by $1, \ldots , j$ and 
index its otherwise points by   $1, 2, \ldots ,$ 
in  order of position on the path.
%The maps $\deltaa_y$ naturally extends to the sets of such
%indexed paths in $Y\mathcal{L}_2(n)$.
%We remark that $k+j$ is not a constant over all paths of $Y\mathcal{L}_2(n)$.


\begin{Example}{\rm  In the case of $\delta_z$ we have
$\delta_z( ZZXXZXZZX) = $
$\gamma_2(\gamma_1( ZZXXZXZZX))$ $ = \gamma_2(ZXZZZXXXZ) =$ $ ZZXXXZZZX$,
where the analog of Lemma 1 uses  $(x_1,z_1)=(2,1)$, $(x_2,z_2)=(3,2)$,
$(x_1',z_1')=(1,0)$, and $(x_2',z_2')=(4,3)$.   Let $Y_0, Y_1, \ldots,  Y_8$ denote vertex  labels  on the path.  
Requiring that the labels of the double rises 
maps sequentially to the labels of
the  non-origin  descents, etc., we have 
$$\delta_z( ZY_0ZY_1XY_2XY_3ZY_4XY_5ZY_6ZY_7XY_8) = 
ZY_1ZY_0XY_2XY_3ZY_5XY_4ZY_7ZY_6XY_8.$$  
}
\end{Example}

\section{The bijection 
$Z\mathcal{L}^*(n) $ to $\mathcal{L}''(n) $}
\label{bijectioneta}



 \indent

 In any of the following colored paths, all unspecified intermediate vertices
 and the final vertex are colored $r$.
 
 Let $Z\mathcal{L}^{**}(n)$ 
 denote the set of paths formed from the paths of 
$Z\mathcal{L}(n)$
by independently coloring with $b$ and $r$ the intermediate vertices of
 all    $YY$, $ZY$, and {\it non-origin} $ZX$  pairs (i.e., those $ZX$ 
 pairs whose intermediate vertex is not the origin).

  Let  $Y\mathcal{L}(n)$ 
 denote the set of paths using the steps $X$, $Y$, and $Z$,  
 beginning with a $Y$ step and running from $(0,-1,0)$, through $(0,0,0)$, 
 and on to $(n,n,n)$.
 
 Let $Y\mathcal{L}^{**}(n)$ 
 denote the set of paths formed from the paths of 
$Y\mathcal{L}(n)$
by independently coloring with $b$ and $r$ the intermediate vertices of
 all    $YY$, $ZX$, and $ZY$ pairs.
 
Let $Y\mathcal{L}''(n)$ 
 denote the set of paths formed from the paths of 
$Y\mathcal{L}(n)$
by independently coloring with $b$ and $r$ the intermediate vertices of
 all   $ZX$,  $ZY$, and  {\it non-origin} $YX$ pairs (i.e., those $YX$ 
 pairs whose intermediate vertex is not the origin).


 
Let $\mathcal{L}''(n)$  denote the set of paths formed from the paths of 
$\mathcal{L}(n)$  by independently coloring with $b$ and $r$
 the intermediate vertices of 
$YX$, $ZX$, and   $ZY$.

We first define a  bijection 
 $$\etaa_1 :Z\mathcal{L}^*(n) \longrightarrow  Z\mathcal{L}^{**}(n) $$

\begin{itemize}
\item[(i)] by first projecting orthogonally each path in  $Z\mathcal{L}^*(n)$,
expressed as in the right side of (\ref{expressed}),
onto a path in $Z\mathcal{L}_2(n)$ in the $x-z$ plane, 
%which has been indexed as described at the end of Section \ref{bijectionaux}, 
so that the labeling words $Y_0,Y_1, \ldots,Y_i,$  $\ldots,$$Y_{2n}$, (defined
in Section \ref{funbegins}) are contracted to become labels for 
the indexed vertices (as described at the end of Section \ref{bijectionaux})
of the 2-dimensional path,
\item[(ii)] next,   by 
applying  bijection $\deltaa_z$, so that each label $Y_i$  is
moved bijectively according to the indexing defined in Section \ref{bijectionaux},
(Specifically, a label $Y_i$  on a double rise $ZZ$ indexed by $h$ on a path
$P$ is moved to the  non-origin  descent $ZX$ of index  $h$ of path $\deltaa_z(P)$;
likewise, a label $Y_i$ on a  non-origin  descent is moved to the double rise of the same
index, and  a label $Y_i$ on an otherwise vertex  is moved to the otherwise vertex with the same
index.)
\item[(iii)] and finally
by expanding  each  label $Y_i$ as a subpath to obtain a  3-dimensional path in 
$Z\mathcal{L}^{**}(n)$.
\end{itemize}

The bijection $$\etaa_2:Z\mathcal{L}^{**}(n) \longrightarrow  Y\mathcal{L}^{**}(n) $$
simply  changes the first step of each path in $Z\mathcal{L}^{**}(n)$
into a $Y$ step.  It can be routinely checked that the coloring
is  transfered in a manner preserving the appropriate number   of blue and red
vertices.
The composition $\etaa = \etaa_2\circ\etaa_1$ bijectively
maps $Z\mathcal{L}^*(n) $ to  $ Y\mathcal{L}^{**}(n) $.

\

Next we define   $$\phii =\phii_2\circ \phii_1: Y\mathcal{L}^{**}(n) \longrightarrow \mathcal{L}''(n)$$
where  the map 
$$\phii_1: Y\mathcal{L}^{**}(n) \longrightarrow Y\mathcal{L}''(n)$$
is defined by  mimicking the definition of $\etaa_1$ by now projecting the
path onto the $x-y$ plane and using the bijection $\delta_y$, and 
the map 
$$\phii_2: Y\mathcal{L}''(n) \longrightarrow \mathcal{L}''(n)$$
is defined simply to delete the first step, together with the first and last colors (necessarily $r$), from each path in $Y\mathcal{L}''(n) $.

\begin{Example}\label{Example5}{\rm 
Continuing from the previous examples, we have the following.  Here
the underlined (double underlined and overlined, resp.)
labeling words are transfered sequentially from double rises (e.g., $ZZ$) 
to non-origin descents (e.g., $ZX$), etc.  
\begin{eqnarray*}
        P^* &=& bZbYbYrYrXrXrZbYrXrZbZrXr \in  \mathcal{L}^*(4),\\
        \epsilon(P^*) &=&Z\underline{\underline{b}}
                         Z\underline{bYbYrYr}
                          X\overline{r} 
                         X\overline{r}
                         Z\underline{bYr}
                         X\overline{r}
                         Z\underline{\underline{b}}
                         Z\underline{r}
                         X\overline{r} \in  Z\mathcal{L}^*(4),\\
       \eta_1(\epsilon(P^*)) &=& Z\underline{bYbYrYr}
                         Z\underline{\underline{b}}
                         X\overline{r}
                         X\overline{r}
                         X\overline{r}
                         Z\underline{bYr}
                         Z\underline{r}
                         Z\underline{\underline{b}}
                         X\overline{r}
                         \in Z\mathcal{L}^{**}(4), \\ 
       \eta(\epsilon(P^*)) &=& Y\underline{\underline{b}}
                               Y\underline{\underline{b}}
                               Y\underline{\underline{r}}
                               Y\underline{Zb}
                               X\overline{r}
                               X\overline{r}
                               X\overline{Zbr}
                               Y\underline{rZrZb}
                               X\overline{r} \in
                               Y\mathcal{L}^{**}(4),\\  
                               \phi_1(\eta(\epsilon(P^*))) &=& 
                               Y\underline{rZb}
                               Y\underline{\underline{b}}
                               X\overline{r}
                               Y\underline{\underline{b}}
                               X\overline{r}
                               Y\underline{rZrZb}
                               Y\underline{\underline{r}}
                               X\overline{rZb}
                               X\overline{r} \in Y\mathcal{L}''(4), \\
        \phi(\eta(\epsilon(P^*))) &=& 
        ZbYbXrYbXrYrZrZbYrXrZbX \in \mathcal{L}''(4).
\end{eqnarray*}
}
\end{Example}


\section{The bijection 
$\mathcal{L}''(n)$ to  
$\mathcal{D}(n)$  }
\label{bijection3} 


\indent

We define a bijection 
     $$\muu: \mathcal{L}''(n)    \longrightarrow \mathcal{D}(n)$$
so that, for  each $P \in \mathcal{L}''(n)$, $\muu(P)$ is obtained     
     by replacing   sequentially   each maximal factor of steps having 
     consecutively $b$ colored vertices by an oblique 
     step having  0-1 coordinates
 according to the following rules: 
$$
\begin{tabular}{lll}
    $YbX $ & $\longrightarrow$ & $(1,1,0)$ \\
          $ZbX $ & $\longrightarrow$ & $(1 ,0 ,1)$ \\
          $ZbY $ & $\longrightarrow$ & $( 0,1,1)$ \\
          $ ZbYbX $ & $\longrightarrow$ & $(1,1,1)$ \\
\end{tabular} 
$$
On the resulting path,
keep the remaining unit
steps and remove the color $r$.

\begin{Example}
{\rm  The last path in Example 5,
        $ZbYbXrYbXrYrZrZbYrXrZbX \in \mathcal{L}''(4)$, is mapped under $\mu$ to the path

$$(1,1,1)(1,1,0)(0,1,0)(0,0,1)(0,1,1)(1,0,0)(1,0,1) \in \mathcal{D}(4).$$}
\end{Example}
\

\section{Appendix
}
\label{finalsection}

\indent

Let $\mathcal{L}(n_1, n_2, \ldots, n_d)$ denote the set of $d$-dimensional 
lattice paths running from the origin to $(n_1,n_2, \ldots, n_d)$ using the unit steps $X_k$, where  $X_k$ denotes the unit 
$d$-vector with 1 in position $k$. 
In this section we consider statistics on paths of
 $\mathcal{L}(n_1, n_2,   \ldots, n_d)$,   
 a  proof of identity~(\ref{mainresult}) for $d>3$, and
 an explicit formula for $|\mathcal{D}(n)|$ when $d=3$. 
 We also  generalize (\ref{mainresult}) to the non-central case 
 and mention some generating functions results.

\medskip
  {\bf Some Statistics:} 
  We order the steps so that $X<Y<Z$. We define the following statistics, the last two  being the classical  {\it number of descents} 
(called {\it number of major contacts} in \cite{MacMahonComb}) and 
{\it number of excedances} 
considered by MacMahon. \cite[sect. IV, chap. III]{MacMahonComb} 
(See  \cite[chap. 10]{Lothaire}.) 
For any path $P=p_1p_2\ldots p_m$ in  $\mathcal{L}(n_1, n_2, n_3)$, with 
$ZP$ denoting $Zp_1p_2\ldots p_m$, etc., define (with the choice of the
subscripts made clear later)
\begin{itemize}
\item[(i)] $f_3(P)= \#(YY, ZY, \textrm{ or } ZZ \textrm{ pairs on } ZP)$,
\item[(ii)] $f_2(P)= \# (YY, ZX, \textrm{ or } ZY \textrm{ pairs on }YP)$,
\item[(iii)] $des(P)=
 |\{i  :   p_i > p_{i+1} \}|=
 \#(YX ,ZX, \textrm{ or } ZY \textrm{ pairs on }P)$.
\item[(iv)] $exced(P)= |\{i  :    p_i > q_i \}|$ where  $q_1q_2 \ldots q_m$ is that path in $\mathcal{L}(n_1,n_2,n_3)$
for which $q_i \le q_{i+1}$ for $1 \le i < m$. 
\end{itemize}
Notice that
 $$exced(P)=\#(Z \mbox{ in  first $n_1+n_2$ positions of }P )+ \#(Y \mbox{ in  first $n_1$ positions of }P).$$

The establishment of the maps $\eta_1$ and $\phi_1$ 
in Section \ref{bijectioneta}  
yields the following.  
\begin{Proposition}\label{propo1}
The statistics $f_3$, $f_2$, and $des$ are equi-distributed on $\mathcal{L}(n,n,n)$.
\end{Proposition}

 In general we  remark that this proposition  does not hold 
 on $\mathcal{L}(n_1,n_2,n_3)$ where $n_1$, $n_2$, $n_3$ are unequal; hence
  a neat ``$2^{n-1}$ result'' is only realized in the central cases where
  $n_i \in \{ 0, n \}$.  We consider the non-central case later 
  in Proposition
  \ref{prop3}.
  
\medskip
 {\bf Higher dimensions:}
In order to state and prove  identity~(\ref{mainresult}) or
 the analog of Proposition \ref{propo1}   for $d=4$, 
 we  expand the definitions of the statistics so that, if $X=(1,0,0,0)$, $Y=(0,1,0,0)$, $Z=(0,0,1,0)$, and $W=(0,0,0,1)$, then 
$$
\begin{array}{lll}
f_4(P)&=&  \#(YY, ZY, ZZ, WY, WZ, WW \textrm{ on } WP)\\
f_3(P)&=&  \#(YY, ZY, ZZ, WX, WY, WZ  \textrm{ on } ZP)\\
f_2(P)&=&  \#(YY, ZX, ZY, WX, WY, WZ  \textrm{ on } YP)\\
f_1(P)&=&  \#(YX, ZX, ZY, WX, WY, WZ  \textrm{ on } XP)\\
des(P)&=&  \#(YX, ZX, ZY, WX, WY, WZ  \textrm{ on } P)\\
\end{array}
$$
Analogously to  Sections \ref{bijection1} and \ref{bijection2},
we  can  encode each path of $\mathcal{S}(n)$ in terms of a path
using $X, Y, Z,$ and $W$ 
having  colored vertices related to the statistic $f_4$ together with 
a set $A \in 2^{[n-1]}$ corresponding to the colors preceding the $X$ steps.
Analogously to Section \ref{bijection3},   we can encode
 each path of $\mathcal{D}(n)$ in terms of a path 
 using $X, Y, Z,$ and $W$ having colored vertices 
 related to the statistic $des$. 
 By employing the scheme of the previous sections 
 we can  show  sequentially  that each of
 $f_4$, $f_3$, $f_2$, and $des$ is equi-distributed with the next.
 Essentially, we  transfer each path into and out of the 
 $x-w$ plane, into and out of the 
 $x-z$ plane, and then into and out of the 
 $x-y$ plane, each time using an analog of Lemma 4 on the 2-dimensional path 
 at each stage to move the coloring on 
 certain double rises to certain non-origin descents. 

Next we indicate   how  this 
approach extends to higher dimensions. Let $B_k$ denote a set of step pairs
defined recursively (backwards)
so that $B_d = \{X_iX_j : 2\le j \le i \le d \}$ and 
$B_{k-1} =B_{k}  \cup  \{X_{k}X_{1}\} \setminus \{X_{k}X_{k}\} $ for
$1 < k \le d$.  For   $1 \le k \le d$ and any path $X_kP = p_0p_1\ldots p_{dn}$, define  
the statistic $f_k(P) = |\{ i : p_{i-1}p_{i} \in B_k, 1\le i\le dn \}|$.
We  then encode each path of $\mathcal{S}(n)$ in terms of a path using 
$X_1, \ldots, X_d$ having  colored vertices related to the statistic $f_d$
together with a set $A \in 2^{[n-1]}$. Also we encode
each path of $\mathcal{D}(n)$ in terms of a path  
using $X_1, \ldots, X_d$   
having colored vertices related to the statistic $des = f_1$.
By mimicking the scheme of the previous sections where
sequentially the coloring on double
rises $X_kX_k$ is swapped for the coloring on descents $X_kX_1$,
$k$ running from $d$ back to 2,  
we can  show    that each of
$f_d$, $f_{d-1}$, \ldots $f_2$, and $des = f_1$ 
is equi-distributed with the next.  


\medskip
{\bf Explicit formulas and the non-central case:}
Now we establish an explicit formula for enumerating $\mathcal{L}(n_1,n_2,n_3)$ with 
respect to the number of descents, which
appears in an equivalent form in MacMahon  
\cite[p. 180]{MacMahonComb}.  However, since we have been
considering equi-distributed statistics, we will use a
related result of  MacMahon \cite[sect. IV, ch. III]{MacMahonComb}
\cite[p. 669]{MacMahonCollected}, which
 is  proved  bijectively by Foata \cite{Lothaire} and Clarke and Foata
 \cite{ClarkeFoataI}
 (See also \cite[pp. 455-6]{MacMahonCollected}.)  For $d=3$, the result is
\begin{Proposition}\label{propo2}
The statistics $des$ and $exced$ are equi-distributed on $\mathcal{L}(n_1,n_2,n_3)$.
\end{Proposition}

Thus
$$
\sum_{P \in \mathcal{L}(n_1,n_2,n_3)}t^{des(P)}=\sum_{h} |\{P\, : \, des(P)=h\}|t^h= \sum_{h} |\{P\, : \,exced(P)=h\}|t^h.
$$
Since $|\{P\, : \,exced(P)=h\}|$ is the number of paths having $i$ $Z$'s and $j$ $Y$'s in the first $n_1$ positions and $k$ $Z$'s and $\ell$ $Y$'s in the next $n_2$ positions, then, with $h=i+j+k$, 
$$
|\{P \, :  \,exced(P)=h \}|  = \hspace{10cm}$$
$$
 \sum_{i,j,k,\ell} \frac{n_1 !}{i!j!(n_1-i-j)!} \ \frac{n_2!}{k!\ell! (n_2-k-\ell)!} \ \frac{n_3!}{(n_3-i-k)!(n_2-j-\ell)! (i+j+k+\ell-n_2)!}.
$$
%&=&
% \sum_{i,j,k,\ell}  
% {n_1\choose i} 
% {{n_1-i} \choose j}
% {n_2 \choose k} 
%{{n_2-k} \choose \ell}
%{n_3 \choose {n_3-i-k}} {{i+k} \choose{ n_2-j-\ell}}.
%\end{eqnarray*}
Hence, after some simplification, with the indices satisfying
$0\le i \le n_1$, $0\le j \le n_1-i$, and  $0\le k \le n_2$, we find
\begin{equation}\label{bigsum}
\sum_{P \in \mathcal{L}(n_1,n_2,n_3)}t^{des(P)} = 
\sum_{i,j,k} 
{\binom {n_1} i} 
 {\binom {n_1-i}  j}
 {\binom {n_2 } k} 
{\binom {n_2+i }  {i+j}}
{\binom {n_3 } {i+k}}  t^{i+j+k}.
\end{equation}

By setting $n_1=n_2=n_3=n$, by setting
 $t=2$ corresponding to the blue or red choice at each descent, and by using the
 mapping  $\mu$ of Section \ref{bijection3},
 formula (\ref{bigsum}) yields  an explicit formula for 
$|\mathcal{D}(n)|$ for $d=3$.

MacMahon in his book \cite{MacMahonComb} comes close to formulating 
identity~(\ref{mainresult}) for $d = 2$ and $3$. He mentions 
the Delannoy numbers, without name,  briefly on
\cite[p. 159]{MacMahonComb},
and  records (\ref{mainresult}) for $d=1$ 
on \cite[p. 151]{MacMahonComb}.  
Armed with the bijections of Sections \ref{bijection1} and 
\ref{bijection3}, and now aware of his analysis, we will give a 
generalization
of identity~(\ref{mainresult}) for the non-central case.  


 Let $\mathcal{D}(n_1,n_2,\ldots, n_d)$ denote the set of paths from the origin to
 $(n_1,n_2,\ldots, n_d)$ using nonzero steps of the form $(x_1,x_2,\ldots, x_d)$ where
 $x_i \in \{ 0,1\}$ for $1 \le i \le d.$  
  Let $\mathcal{S}(n_1,n_2,\ldots, n_d)$ 
  denote the set of paths from the origin to
 $(n_1,n_2,\ldots, n_d)$ using the steps of the form $(x_1,x_2,\ldots, x_d)$
 where  the $x_i$'s are nonnegative integers, not all zero. 
 \begin{Proposition}\label{prop3} Let $f(t;n_1,n_2,n_3)$ denote the
 polynomial in $t$ of \eqref{bigsum}. For  $(n_1,n_2,n_3) \neq \\ (0,0,0)$, 
 \begin{equation}\label{forS}
 |\mathcal{S}(n_1,n_2,n_3)| = 2^{n_1+n_2+n_3-1} 
   f(\frac{1}{2};n_1,n_2,n_3)
\end{equation}
while 
\begin{equation}\label{forD}
|\mathcal{D}(n_1,n_2,n_3)| =f(2;n_1,n_2,n_3).
\end{equation}
\end{Proposition}
The proof of (\ref{forD}) was effectively covered in the paragraph following
the formula (\ref{bigsum}).  To prove (\ref{forS}), which is also stated and
proven in \cite[p. 180]{MacMahonComb}, we  require some
notation.
On $\mathcal{L}(n_1,n_2,n_3)$ we define the following statistics
(names borrowed from MacMahon's 
{\it equal contact} and {\it minor contact}):
$$
\begin{array}{lcl}
des(P)  & =& \#( YX, ZX,  \mbox{ and } ZY  \mbox{ on } P) \\
eqcon(P) & =& \#( XX, YY,   \mbox{ and } ZZ \mbox{ on } P) \\
mincon(P) & =& \#( XY, XZ,   \mbox{ and } YZ \mbox{ on } P) 
\end{array}
$$
Let $\mathcal{L}'(n_1,n_2,n_3)$ denote
the set of paths formed from the paths of 
$\mathcal{L}(n_1,n_2,n_3)$  by weighting
the intermediate vertices of 
$XX$, $YX$, $YY$, $ZX$, $ZY$, and  $ZZ$ with $2$.
 Hence, by extending the map $\alpha$ of Section \ref{bijection1} to 
 $\alpha : \mathcal{S}(n_1,n_2,n_3) \rightarrow \mathcal{L}'(n_1,n_2,n_3)$,
 we obtain
        $$
        |\mathcal{S}(n_1,n_2,n_3)| =  
\sum_{P \in \mathcal{L}(n_1,n_2,n_3)}2^{des(P)+eqcon(P)}.$$
That there are  ${n_1+n_2+n_3-1}$ interior lattice points on any path 
of  $\mathcal{L}(n_1,n_2,n_3) $, together with   symmetry,  yields
\begin{eqnarray}
\sum_{P \in \mathcal{L}(n_1,n_2,n_3)}t^{des(P)+eqcon(P)} &=&
\sum_{P \in \mathcal{L}(n_1,n_2,n_3)}t^{n_1+n_2+n_3-1-mincon(P)}
  \nonumber   \\
&=&
t^{n_1+n_2+n_3-1}\sum_{P \in \mathcal{L}(n_3,n_2,n_1)}t^{-des(P)}\label{guy1}.
\end{eqnarray}
Thus formula (\ref{forS}) follows by the symmetry of $|\mathcal{S}(n_1,n_2,n_3)|$ in $n_1,n_2,$ and $n_3.$ $\square$  

\medskip
{\bf Generating functions and recurrences:}
For any $d$, the formulas for the generating functions for 
$\sum_{n_1,\ldots,n_d}|\mathcal{D}(n_1,\ldots,n_d)|x_1^{n_1}\cdots x_d^{n_d}$ and 
$\sum_{n_1,\ldots,n_d}|\mathcal{S}(n_1,\ldots,n_d)|x_1^{n_1}\cdots x_d^{n_d}$
are given by MacMahon on \cite[p.~159, p.~156, resp.]{MacMahonComb}.
For $d=3$  we find 
\begin{eqnarray*}
\sum_{m,n,p \ge 0}|\mathcal{D}(m,n,p)|x^my^nz^p 
&=& \frac{1}{1-x-y-z-xy-xz-yz-xyz}\\
\sum_{m,n,p \ge 0}|\mathcal{S}(m,n,p)|x^my^nz^p
&=& \frac{1}{2} + \frac{1}{2(1-2(x+y+z-xy-xz-yz+xyz))},
\end{eqnarray*}
which give rise to the recurrences:
\begin{eqnarray*}
|\mathcal{D}(m,n,p)| \! &\!=\!&\! |\mathcal{D}(m-1,n,p)|+
                         |\mathcal{D}(m,n-1,p)|+ 
                         |\mathcal{D}(m,n,p-1)|+
                         |\mathcal{D}(m-1,n-1,p)|\\ &&\! +
                         |\mathcal{D}(m-1,n,p-1)|+
                         |\mathcal{D}(m,n-1,p-1)|+
                         |\mathcal{D}(m-1,n-1,p-1)| \\
|\mathcal{S}(m,n,p)|\!&\!=\!&\!  2(|\mathcal{S}(m-1,n,p)|+
                         |\mathcal{S}(m,n-1,p)|+ 
                         |\mathcal{S}(m,n,p-1)|-
                         |\mathcal{S}(m-1,n-1,p)|\\ &&\! -
                         |\mathcal{S}(m-1,n,p-1)|-
                         |\mathcal{S}(m,n-1,p-1)|+
                         |\mathcal{S}(m-1,n-1,p-1)|) 
\end{eqnarray*}
For the second recurrence we require that $m>1$ or $n>1$ or $p>1$.

\medskip
{\bf A reciprocal polynomial:}
We conclude by noting that, in the central case and $d=3$ (the proof for any
$d$ is similar), the polynomial 
$\sum_{P \in \mathcal{L}(n)}t^{des(P)}$
is a reciprocal polynomial, i.e., if $\sum_h c_h t^h$ 
denotes $ \sum_{P \in \mathcal{L}(n)}t^{des(P)}$ then $c_{2n-h} =c_{h}$ for $0\le h \le 2n$.
By exchanging the blue-red coloring for an indeterminate $t$, 
we can routinely modify
our bijection proving (\ref{mainresult}) to show 
$$\sum_{P \in \mathcal{L}(n)}t^{des(P)+eqcon(P)}= t^{n-1}
  \sum_{P \in \mathcal{L}(n)}t^{des(P)}.$$
Combining this with the identity of (\ref{guy1}) yields 
$$\sum_{P \in \mathcal{L}(n)}t^{2n-des(P)}=
  \sum_{P \in \mathcal{L}(n)}t^{des(P)}.
$$
\

\bigskip
\noindent {\bf Acknowledgments.}  The authors thank  C.~Krattenthaler
for leading them to  Proposition~\ref{propo2} through the reference \cite{ClarkeFoataI}.  We are also grateful to the referees for their generous suggestions.

\


\begin{thebibliography}{9}
\bibitem{BanSch} C.~Banderier and S.~Schwer, Why Delannoy numbers?, {\it 
J. Stat. Plann. Inference}, to appear.


\bibitem{ClarkeFoataI} R.~J.~Clarke and D.~Foata,  Eulerian calculus, I:
Univariable statistics, {\it Europ.~J.~Combinatorics}, 15 (1994) 345--362.

\bibitem{HumphreysNiederhausen}
K.~Humphreys and H.~Niederhausen,
Counting lattice paths taking steps in infinitely
many directions under special access restrictions,
{\it Theoret. Comput. Sci.}, to appear. 

\bibitem{Lothaire}  M.~Lothaire, {\it Combinatorics on words}, Addison--Wesley, 1983. 

\bibitem{MacMahonCollected} P.A.~MacMahon,
{\it Collected Papers}, vol I, [G.E.~Andrews, ed.],
Cambridge, Mass., The M.I.T. press, 1978. 


\bibitem{MacMahonComb} P.A.~MacMahon, {\it Combinatory Analysis},   Cambridge,
Cambridge Univ. Press, 
(Reprinted by Chelsea, New York, 1955) vol.~I. 


 \bibitem{Sloane} N.~J.~A.~Sloane, {\it On-line Encyclopedia of Integer
 Sequences}, \\
 {\tt http://www.research.att.com/$\sim$njas/sequences/index.html}


\bibitem{StanleyBookII}
 R.~P.~Stanley, {\it Enumerative Combinatorics},
Vol.~2,  Cambridge University Press, 1999.

\bibitem{SulNarPol}
R.~A.~Sulanke, Counting lattice paths by Narayana polynomials, 
{\it Electron. J.
Combin.}\ 7 (2000), Art.~R40, 9~pp.

\bibitem{SulColl} R.~A.~Sulanke,  Objects counted by the central 
Delannoy numbers,
{\it J. Integer Sequences}, (2003), Art. 03.1.5,  19 pp.

\bibitem{SulNarMany} R.~A.~Sulanke, 
Generalizing Narayana and Schr\"oder numbers to higher dimensions, 
preprint 2003.

\end{thebibliography}
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

