% 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 §ion & 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 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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%