%   {R.A. Sulanke}
%   {\tt sulanke@math.boisestate.edu.}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   Attention editor:
%
%   The first page is spaced with a \newpage  
%     allowing space for the JIS Logo.
%
%   There are many .eps files required for the figures of this paper.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\documentclass[12pt,reqno]{amsart}
\usepackage{color}
\usepackage{float,amssymb,latexsym}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{fullpage}
\topmargin 16pt
%\textheight 9in
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

%\renewcommand{\baselinestretch}{1.1}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}


  \newtheorem{Note}{Note} 
 \newtheorem{EXAMPLE}{Example} 
  

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}


\title[]{Objects Counted by the Central Delannoy Numbers}
\vfill
\author[]{Robert A. Sulanke} 
% submitted Nov. 1, 2002, accepted Jan. 21, 2003 
\vfill
\address{Boise State University, Boise, ID, 83725, USA. 
}
\email{sulanke@math.boisestate.edu}




\begin{abstract}
%{\bf Abstract.} 
The central Delannoy numbers, $(d_n)_{n\ge0} = 1,3,13,63,321,
1683, 8989, 48639,   \ldots $
(A001850 of {\it The On-Line Encyclopedia of Integer Sequences})
 will be defined so that $d_n $  counts the 
lattice paths running 
from $(0,0)$ to $(n,n)$ that use  the  
steps $(1,0)$,  $(0,1)$, and $(1,1)$.  In a recreational spirit 
we give a  collection of 29 configurations that these numbers  count.

\




\end{abstract}

\maketitle


\section{Introduction}

In the late nineteenth century,\ Henri Delannoy \cite{Delannoychiquier} introduced
what we now call the \text{\it Delannoy array.}\ For  integers $i$ and $j$,
we define this array $d_{i,j}$ to satisfy
    $$ d_{i,j} = d_{i-1,j} + d_{i,j-1} + d_{i-1,j-1} $$
with  the conditions $d_{0,0} = 1$ and   $ d_{i,j} = 0 $ if $i<0$ or $j<0$.
The members of the sequence $(d_i)_{i\ge0} := (d_{i,i})_{i\ge0} = 
1, 3, 13, 63, 321, 1683, 8989, 48639, \ldots$ (A001850 of Sloane \cite{Sloane}),
are known as the (central) {\it Delannoy numbers.}\  

\

\begin{center}
\begin{tabular}{cc}
$d_{i,j} := $ &
\begin{tabular}{c|cccccc}
$i \setminus j$&   0   &    1    &    2   &  3   &4  \\
\hline
0     &            1   &    1&        1  &   1  &1  \\
1     &            1   &    3&        5  &   7  &9  \\
2     &            1   &    5&        13 &   25 &41  \\
3     &            1   &    7&        25 &   63 &129 \\
4     &            1   &   9 &        41  &  129      &321   \\
\end{tabular}
\end{tabular}
\end{center}

\

In Section 3 we will show that
the  generating function for the central Delannoy numbers satisfies
\begin{equation}
   \sum_{i\ge0} d_i z^i = \frac{1}{\sqrt{ 1 - 6 z + z^2 }}.
\label{genfundelnos}
\end{equation}
\noindent
An alternative derivation of this is given by Stanley 
 \cite[Sect. 6.3]{StanleyBookII}. 
These numbers
satisfy the recurrence, 
\begin{equation}
(n+2)d_{n+2} = 3(2n+3)d_{n+1} - ( n+1) d_n. 
\label{recurrencedelnos}
\end{equation}
subject to $d_0 = 1$ and $d_1 = 3$, as shown, e.g., by  Stanley \cite[Sect. 6.4]{StanleyBookII} 
and  the author \cite{Sul3Rec}. 
\newpage
We refer the question, ``Why
Delannoy numbers?'', to the survey on the life and works  of Delannoy
written by Banderier and Schwer \cite{BanderierWhy}. 
While  the (central) Delannoy numbers are known through the books of
Comtet \cite{Comtet} and Stanley \cite{StanleyBookII}, only a few examples of
objects enumerated by these numbers have been found in the literature.
These examples will appear
and be referenced in the following sections.  

After  Delannoy's 
introduction of the numbers, essentially as counting unrestricted paths 
that use the steps $(0,1)$,
$(1,0)$, and $(1,1)$, they appear again in 1952, 
when Lawden \cite{Lawden}, without
citing Delannoy, found 
them to be the values of the Legendre polynomials with argument
equaling 3.  However, the definition of the Legendre polynomials does not
appear to foster any combinatorial interpretation leading to  enumeration. 
See also   Moser and Zayachkowski \cite{Moser}.



In the following section we give a catalog of 29 configurations counted by
the (central) Delannoy numbers, ordered primarily as they were collected. 
In keeping with   Delannoy's interest in recreational mathematics,
this catalog is intended to constitute exercises inviting 
bijective, recursive, and generating functional
proofs that the  Delannoy numbers do indeed count the configurations.
Each example is accompanied by an illustration of  a set of configurations 
corresponding to  $d_2 =13$.
Section~3 contains intentionally incomplete notes regarding some 
bijective and generating functional verifications for the examples.


The collector wishes to thank Cyril Banderier, Emeric Deutsch, Enrica Duchi, 
Ira Gessel, Sylviane Schwer, Lou Shapiro, and Renzo Sprugnoli
for their contribution 
to this
project.  
He also appreciates the referee's generous
critique.







\section{A catalog of configurations}\label{catalog13}

In the integer plane, we will 
take lattice paths to be represented as 
concatenations  of the directed steps belonging to various specified sets.
When the steps are weighted, the weight of
a path  is the product of the weights of its steps, and the
weight of a path set is the sum of the weights of 
its paths. As noted in the remark following Example 3, the independent
coloring of substructures on paths is equivalent to weighting.
Throughout, we will denote the diagonal up and down steps 
as   $U := (1,1)$  and $D :=(1,-1)$.




\begin{EXAMPLE}\label{example1}
{\rm   A classic example is the set of paths from $(0,0)$ to $(2n,0)$
using the steps $U$, $D$, and $(2,0)$.  For the ``tilted'' 
version consider the
path from 
$(0,0)$ to $(n,n)$
using the steps $(0,1)$, $(1,0)$, and $(1,1)$.   
From this path model one can obtain a combinatorial proof that, for $n \ge 0$,
\begin{equation}\label{star}
d_n = \sum_{k=0}^n{{n}\choose{k}}{{n+k}\choose{k}}.
\end{equation}
\begin{figure}[H]
     \vspace{12pt}
     \begin{center}
       \leavevmode\psfig{figure=classic.eps,width=12cm}
       \vspace{6pt}
     \end{center}
     \caption{
     The   $d_2 = 13$  unrestricted 
     paths from $(0,0)$ to $(2n,0)$ using the steps $U$, $D$, and $(2,0)$. 
  }
     \label{figclassic}
     \end{figure}
}
\end{EXAMPLE}
\newpage
\renewcommand{\baselinestretch}{1.05}
% no 2
\begin{EXAMPLE}\label{example2}
{\rm The Delannoy number $d_n$  is  the weight of  the
set of paths from $(0,0)$ to $(n,0)$
using the steps  $U_2$, $D$, and  $(1,0)_3$, where the up step $ U_2$  and the 
horizontal step  $(1,0)_3$ have  
 weights 2 and 3, respectively.

Alternatively, $d_n$    counts the paths from $(0,0)$ to $(n,0)$
using the steps  $U$, $D$, and  $(1,0)$,  where the $U$ steps are
independently colored blue or red and the $(1,0)$ steps are 
independently colored blue, red, or green.   See the remark following
Example~\ref{example3}.
 \begin{figure}[H]
     \begin{center}
       \vspace{24pt}
     \leavevmode\psfig{figure=unrestricted23.eps,width=5cm}
       \vspace{12pt}
     \end{center}
     \caption{Here $2+2+3\cdot3 = d_2$
     }
     \label{figunrestricted23}
     \end{figure}
}
\end{EXAMPLE}

\

%%%%%  3
\begin{EXAMPLE}\label{example3}
 {\rm  Using the steps
$U$ and $D$, we find $d_n$ to be the weighted sum of the 
paths from $(0,0)$ to $(2n,0)$ 
where within each path the right-hand turns, or {\it peaks},
have
 weight  $2$.
Consequently, one can obtain  a combinatorial proof that, for $n \ge 0$,
\begin{equation}
\sum_{i=0}^n {n\choose i}^2 2^i = d_n. \label{sumsqtwo}
\end{equation}
\begin{figure}[H]
     \begin{center}
       \vspace{16pt}
     \leavevmode\psfig{figure=classicpeaks.eps,width=12cm}
       \vspace{6pt}
     \end{center}
     \caption{
    The sum of the weights of the paths is $2+4+2+2+2+1 = d_2$.
     }
     \label{figclassicpeaks}
     \end{figure}
}
\end{EXAMPLE}


\noindent{\bf Remark:} Often, as in Examples \ref{example3},  we will consider 
paths with substructures -- such as peaks, double ascents, etc. -- which make
a multiplicative contribution of  2 to the weight of each path.
Other such examples include  \ref{example4}, \ref{example5}, \ref{example14}, \ref{example20}, \ref{example21}, \ref{example24}, \ref{example25},
\ref{example26},  and \ref{example27}. 
If momentarily the weights of the substructures is reduced to 1, 
then the  weight of a set of such paths becomes a cardinality, namely 
the central binomial coefficient, ${{2n}\choose{n}}$. Indeed, in
the figures for the above named examples, 
there will be ${{4}\choose{2}} = 6$ shapes in each illustration.
However, 
when the substructures have weight  2, the weight of the set of such paths
is a Delannoy number, which in turn is 
the cardinality of the paths of same shapes on which the substructures are
independently colored Blue or Red.  In this catalog  we will
usually omit  versions of examples 
with Blue-Red substructures, which would yield 13 shapes instead of 6 shapes in 
the relevant
illustrations.


\newpage

%%%%%%%%%%%%%%%%% 4 
\begin{EXAMPLE}\label{example4}
 {\rm  Using the steps
$U$ and $D$, we find that  $d_n$ is the sum of the weights of 
the  paths from $(0,0)$ to $(2n+1,1)$ that begin with an up step and
where the intermediate vertices of double ascents  have
 weight  $2$.
\begin{figure}[H]
     \begin{center}
       \vspace{18pt}
     \leavevmode\psfig{figure=classicdoubleascents.eps,width=12cm}
       \vspace{12pt}
     \end{center}
     \caption{
    The sum of the weights of the paths is $4+2+2+2+1+2 = d_2$.
     }
     \label{figclassicdoubleascents}
     \end{figure}
}
\end{EXAMPLE}
%%%%%%%%%%%%  5
\begin{EXAMPLE}\label{example5}
 {\rm  Using the steps
$U$ and $D$, we find that $d_n$ is the weighted sum over 
the  paths from $(0,0)$ to $(2n,0)$ where  
each $U$ step which is oddly positioned along its path has 
 weight  $2$.  
\begin{figure}[H]
     \begin{center}
       \vspace{30pt}
     \leavevmode\psfig{figure=classicoddascents.eps,width=12cm}
       \vspace{12pt}
     \end{center}
     \caption{
    The sum over the weights of the paths is $2+4+2+2+1+2 = d_2$.
     }
     \label{figclassicoddascents}
     \end{figure}
}
\end{EXAMPLE}

%%%%%%%%%%%%%%%%% 6 
\begin{EXAMPLE}\label{example6} {\rm  
The product $2^{n-1}d_n$ counts the  set of all  paths from $(0,0)$ to $(n,n)$
with steps of the form $(x,y)$ where  $x$ and $y$ are nonnegative integers, not both $0$.
\begin{figure}[H]
     \begin{center}
       \vspace{18pt}
     \leavevmode\psfig{figure=diagonal.eps,width=12cm}
       \vspace{12pt}
     \end{center}
     \caption{ Here $2^{n-1}d_n = 2\cdot13$, for $n = 2$.
     }
     \label{figdiagonal}
     \end{figure}
}
\end{EXAMPLE}
\newpage
\renewcommand{\baselinestretch}{1.1}

% 7
\begin{EXAMPLE}\label{example7}
 {\rm  Using  the steps $ U_{2}$, $D$, and $(2,0)_{-1}$ 
where the  up step  and the
horizontal step have
 weights of\ $2$ and $-1$, respectively,   $d_n$ is the 
sum of the weights
of the paths running  from $(0,0)$ to $(2n,0)$.
\begin{figure}[H]
     \begin{center}
       \vspace{30pt}
     \leavevmode\psfig{figure=classicminus2.eps,width=12cm}
       \vspace{12pt}
     \end{center}
     \caption{
    The sum over the paths is 13.
     }
     \label{figclassicminus2}
     \end{figure}
}
\end{EXAMPLE}
%%%%%%%%%%%%%%%%%% 8
\begin{EXAMPLE}\label{example8}
 {\rm  Here we consider a {\it second moment}\ for a path set.
 Using  the steps  $U,$ $ D, $ and $(2,0)$, for the  
elevated (Schr\"{o}der) paths running from $(0,0)$ to $(2n+2,0)$,  we
 find that $d_n$ is   the sum, over its paths, of the
 average of the positive squared heights of the lattice points
 traced by each path.
 \begin{figure}[H]
     \begin{center}
       \vspace{30pt}
     \leavevmode\psfig{figure=classicsecmoment.eps,width=12cm}
       \vspace{12pt}
     \end{center}
     \caption{
     Within each path
      the squared
     heights are additive.  
     $\frac{11}{5}+\frac{19}{5}+ \frac{5}{5}+ \frac{8}{5}+ \frac{8}{5}+ \frac{14}{5}= \frac{65}{5}= d_2$.
     }
     \label{figclassicsecmoment}
     \end{figure}
}
\end{EXAMPLE}
%9
\begin{EXAMPLE}\label{example9}
{\rm We consider another {\it second moment}.   
Consider  the elevated Schr\"{o}der paths
running from $(0,0)$ to $(2n+2,0)$ 
where within each path the   noninitial up step
and the
horizontal steps have
 weights $2$ and $-1$, respectively. Here $d_n$ is  the  
 sum of the weighted average of the positive squared heights of the 
 lattice points
 traced by each path. 
\begin{figure}[H]
     \begin{center}
       \vspace{30pt}
     \leavevmode\psfig{figure=secmomnegup.eps,width=12cm}
       \vspace{12pt}
     \end{center}
     \caption{
     The sum over the paths is $
     \frac{44}{5} +\frac{76}{5} + \frac{5}{5} + \frac{(-16)}{5} + \frac{(-16)}{5} + \frac{(-28)}{5}= d_2$.
     }
     \label{figsecmomnegup}
     \end{figure}
}
\end{EXAMPLE}
\newpage

%10
\begin{EXAMPLE}\label{example10}
{\rm We consider one more {\it second moment}.  Take the elevated paths 
running from
$(0,0)$ to $(n+2,0)$ using the steps $U$, $D$, and $(1,0)$, 
where the noninitial  $U$ steps have 
      weight  $2$ and the unit horizontal steps have 
      weight  $3$. Here $d_n$ is  the  
 sum of the weighted average of the positive squared heights of the 
 lattice points
 traced by each path. 
 

 \begin{figure}[H]
     \begin{center}
       \vspace{12pt}
     \leavevmode\psfig{figure=secmomentlist23.eps,width=5cm}
       \vspace{12pt}
     \end{center}
     \caption{The sum over the paths is 
     $ \frac{2(1+4+1)}{3} + \frac{3 \cdot 3(1+1+1)}{3} = d_2$.}
     \label{figsecmomentlist2}
     \end{figure}
}
\end{EXAMPLE}

%11
\begin{EXAMPLE}\label{example11}
{\rm 
Here we will define a {\it zebra}\ 
to be a parallelogram polyomino whose noninitial columns are
either white or gray.  For any zebra, its {\it average diagonal 
thickness squared}\ will be the average of the
squares of the number  of  unit cells along  each --45 degree diagonal passing
through the center of the cells.  The sum,  over 
all zebras of a fixed perimeter $2n+4$,  of the average diagonal 
thickness squared  is the Delannoy number $d_n$.


\begin{figure}[H]
     \begin{center}
     \leavevmode\psfig{figure=zebras.eps,width=10cm}
       \vspace{12pt}
     \end{center}
     \caption{The sum of the average diagonal 
thickness squared  is 
     $\frac{1+1+1}{3}+ \frac{2(1+1+1)}{3} + \frac{2(1+4+1)}{3} + \frac{2(1+1+1)}{3} + \frac{4(1+1+1)}{3}=d_2$.}
     \label{figzebras}
     \end{figure}
}
\end{EXAMPLE}
%12
\begin{EXAMPLE}\label{example12}
{\rm 
%Here we put exercise 6.49 page 243 of \cite{StanleyBookII} for 
The number $d_n$ counts the 
domino tilings of the  Aztec diamond of width $2n$ 
having an additional center row.  
\begin{figure}[H]
     \begin{center}
       \vspace{24pt}
     \leavevmode\psfig{figure=stars.eps,width=12cm}
       \vspace{12pt}
     \end{center}
     \caption{$d_2$  tilings.
     }
     \end{figure}
}
\end{EXAMPLE}
%%%%%%%%%%%%%%%%%%%%%
\newpage
%13 from Emeric Deutsch
\begin{EXAMPLE}\label{example13}
{\rm 
Consider counting matchings in the comb graph.  
For a comb with $2n$ teeth, there are $d_n$ ways to have an
$n$-set of non-adjacent
edges. 
\begin{figure}[H]
     \begin{center}
       \vspace{24pt}
     \leavevmode\psfig{figure=combs.eps,width=12cm}
       \vspace{12pt}
     \end{center}
     \caption{The $d_2$  $2$-matchings in the comb with $2\cdot2$ teeth. 
     }
     \end{figure}

}
\end{EXAMPLE}
% 14   from Sulanke

\

\begin{EXAMPLE}\label{example14}
{\rm
In a lattice path using the steps
$U$ and $D$, a {\it long}, is a maximal subpath having 
at least two steps, all of the same 
type.  The number 
$d_n$ is the weighted sum over the paths running from $(0,0)$ to 
$(2n+1,1)$ which begin with a $U$ step and 
whose   nonfinal longs  have the 
 weight $2$.
\begin{figure}[H]
     \begin{center}
     \vspace{12pt}
     \leavevmode\psfig{figure=classiclongs.eps,width=12cm}
     \vspace{12pt}
     \end{center}
     \caption{
    The sum of the weights of the paths is $ 2+2+4+2+1+2 = d_2$.
     }
     \end{figure}
}
\end{EXAMPLE}

\

% private comm. from Shapiro July 11
% 15
\begin{EXAMPLE}\label{example15}
{\rm
Consider the walks that begin at the origin and use the unit steps: east ($E$), west ($W$), 
and north ($N$).  If these walks never start with $W$ and are self-avoiding,
that is, $E$ and $W$ are nonadjacent, then $d_n$ counts the walks with $2n$ steps 
and  
final height $n$.

\begin{figure}[H]
      \vspace{24pt}
     \begin{center}
     \leavevmode\psfig{figure=shapirowalks.eps,width=12cm}
     \vspace{12pt}
      \end{center}
     \caption{$d_2$ walks.
     }
     \end{figure}
}
\end{EXAMPLE}
\newpage
%  comm. from Jul 11 Sylviane R. Schwer
% 16
\begin{EXAMPLE}\label{example16}{\rm
The number $d_n$ counts the ways to distribute $n$ white and $n$ black
 balls into $r$ labeled urns  where   $r$  takes on the values
from $n$ to $2n$ and where each urn is nonempty 
and does not contain more than one ball of
each color. (The balls are unlabeled and are 
ordered so that white precedes black when two
are present in an urn.)
\begin{figure}[H]
     \begin{center}
       \vspace{12pt}
     \leavevmode\psfig{figure=ballsandurns.eps,width=12cm}
      \vspace{12pt}

       \end{center}
     \caption{$d_2$  balls-in-urns distributions.
     }
     \end{figure}
}
\end{EXAMPLE}
%  comm. from Jul 11 Sylviane R. Schwer
% 17
\begin{EXAMPLE}\label{example17}
{\rm
The number $d_n$ counts the words from the alphabet \{ a,b, \{a,b\} \}
where the total occurrences of $a$ and $b$ in each word is $n$. 
%For $n = 2$ the words are 
\begin{figure}[H]
\vspace{12pt}
     \begin{center}
$$ \{a,b\}\{a,b\},\  \{a,b\}ab,\  \{a,b\}ba,\  a\{a,b\}b,\  b\{a,b\}a,\
ab\{a,b\},\ ba\{a,b\},$$ 
$$aabb,\ abab,\ abba,\ baab,\ baba,\ bbaa$$
%\vspace{12pt}
     \end{center}
     \caption{$d_2$ words.
     }
     \end{figure}
}
\end{EXAMPLE}
%  comm. from Jul C.B.
% 18
\begin{EXAMPLE}\label{example18}
{\rm  
In ${\mathbb Z}^n$,
$d_n$ counts the $n$-dimensional lattice points inside or on the hyperoctahedron
with vertices on the axes located a distance $n$ from the  origin.
More specifically, for $z = (z_1, \ldots, z_n) \in {\mathbb R}^n$, let $||z||_1$ denote the norm $\sum_{i=1}^n |z_i|.$
Then $d_n = |\{ y \in  {\mathbb Z}^n : ||y||_1 \le n \}|$.  
\begin{figure}[H]
      \vspace{12pt}
     \begin{center}
     \leavevmode\psfig{figure=hyperoctahedron.eps,width=5cm}
     %
       
     \end{center}
\vspace{12pt}       
     \caption{For $n=2$, $d_2 =13$ is the number of lattice points inside the 
     square region $\{ (x,y) : |x|+|y| \le 2 \}$.
     }
     \end{figure}
}
\end{EXAMPLE}
\newpage
%%%%%%%%%%%%%%% 19
\begin{EXAMPLE}\label{example19}
{\rm The number $d_n$ counts the set of paths
using the three steps types, $U$, $D$, and $(2,0)$,
running from $(0,0)$ to the line $x = 2n$,  and
remaining weakly above the x-axis.
\begin{figure}[H]
\vspace{12pt}       
     \begin{center}
       \leavevmode\psfig{figure=classic19.eps,width=12cm}
       \vspace{12pt}
     \end{center}   
     \caption{The
     paths running from  $(0,0)$ to the line $x =4$ and  remaining weakly above the x-axis.
}
     \label{figclassic19}
     \end{figure}
}
\end{EXAMPLE}

%%%%% 20
\begin{EXAMPLE}\label{example20}
 {\rm  
For the steps
$U$ and $D$, $d_n$ is the weighted sum of the 
paths running from $(0,0)$  to the line $x = 2n$ and 
remaining weakly above the x-axis,   
where within each path the right-hand turns have
 weight  $2$.


\begin{figure}[H]
     \begin{center}
       \vspace{24pt}
     \leavevmode\psfig{figure=peaks20.eps,width=12cm}
       \vspace{12pt}
     \end{center}
     \caption{
    The sum of the weights of the paths is $4+2 + 1 + 2+2+2 = d_2$.
     }
     \label{figpeaks20}
     \end{figure}
}
\end{EXAMPLE}

%%%%% 21
\begin{EXAMPLE}\label{example21}
 {\rm  
For the steps
$U$ and $D$, $d_n$ is the weighted sum of the 
paths running from $(0,0)$  to the line $x = 2n$ and 
remaining weakly above the x-axis,   
where within each path each {\it long} has
 weight  $2$. Here a {\it long} is a maximal subpath of the same step type of length exceeding
one.
\begin{figure}[H]
     \begin{center}
     \vspace{18pt}
\leavevmode\psfig{figure=longs21.eps,width=12cm}
       \vspace{12pt}
     \end{center}
     \caption{
    The sum of the weights of the paths is $1+4+2+2+2+2 = d_2$.
     }
     \label{figpeaks21}
     \end{figure}
}
\end{EXAMPLE}
\newpage
%%%%% 22
\begin{EXAMPLE}\label{example22}
 {\rm  Consider the known array extending the large Schr{\"o}der numbers: 
 namely, 
for  integers $i$ and $j$, we define this array $r_{i,j}$ to satisfy
    $$ r_{i,j} = r_{i-1,j} + r_{i,j-1} + r_{i-1,j-1} $$
with  the conditions $r_{0,0} = 1$ and   $ r_{i,j} = 0 $ if $j<0$ or $i<j$.
The members of the sequence $(r_i)_{i\ge0} := (r_{i,i})_{i\ge0} = 1, 2, 6, 22, 90 \ldots$ are known as the large Schr{\"o}der  
numbers.  The central Delannoy number  $d_n$  is  the sum of the 
$2n+1$-{st} diagonal, that is $d_n = \sum_i r_{i,2n-i}$.  
\begin{figure}[H]
\vspace{12pt}
     \begin{center}
\begin{center}
\begin{tabular}{cc}
$r_{i,j} := $ &
\begin{tabular}{c|cccccc}
$i \setminus j$&   0   &    1    &    2   &  3    &  4    \\
\hline
0     &            1   &    0&        0  &   0   &   0 \\
1     &            1   &    2&        0  &   0   &   0 \\
2     &            1   &     4&       \fbox{6}  &    0   &   0 \\
3     &            1   &    \fbox{6}  &        16 &   22  &   0 \\
4     &            \fbox{1}   &    8&        30 &   68  &   90  \\
\end{tabular}
\end{tabular}
\end{center}

       
     
     \end{center}
     \caption{An array of the extended large Schr{\"o}der numbers.
     Here
      $\fbox{1}+\fbox{6}+\fbox{6} =d_2$.
                                       }
     \end{figure}

}
\end{EXAMPLE}

%%%%% 23
\begin{EXAMPLE}\label{example23}
 {\rm  
%from E. Deutsch July 29
Let $T(n)$ denote the set of plane trees
with $2n+1$ edges, with roots of odd degree,
with the non-root vertices having degree 1 (for the leaves), 2, or 3, and
with an even number of vertices of degree two
between any two vertices of odd degree.


\begin{figure}[H]
     \begin{center}
       \vspace{24pt}
     \leavevmode\psfig{figure=trees23.eps,width=10cm}
       \vspace{12pt}
     \end{center}
     \caption{
    The specified trees counted by $d_2$.
     }
     \label{figpeaks23}
     \end{figure}
}
\end{EXAMPLE}

%%%%% 24
\begin{EXAMPLE}\label{example24}
 {\rm  
A {\it high peak} is the intermediate vertex of a $UD$ pair
with ordinate exceeding 1.
Let $\mathcal{P}(n,k)$ denote  the set of paths 
using the steps $U$ and $D$,
running from $(0,0)$ to $(n,0)$,
remaining weakly above the x-axis,   
intersecting the x-axis $k$ times, and
having high peaks of weight 2.
%which are indendently colored by  red or blue.
Then  the Delannoy number counts a  union of sets:
$$d_n = \left|\bigcup_{i=1}^{n+1} \mathcal{P}(2n+2i,2i) \right|.$$


\begin{figure}[H]
     \begin{center}
     \vspace{12pt}
     \leavevmode\psfig{figure=peaks24.eps,width=14cm}
       \vspace{12pt}
     \end{center}
     \caption{ $4+2+2+2+2+1 = d_2$.
     }
     \label{figpeaks24}
     \end{figure}
}
\end{EXAMPLE}


%%%%% 25
\begin{EXAMPLE}\label{example25}
 {\rm
A {\it double ascent} (or {\it double rise})
is just a consecutive $UU$ pair.
Let $\mathcal{P}(n,k)$  denote  the set of paths 
using the steps $U$ and $D$,
running from $(0,0)$ to $(n,0)$,
remaining weakly above the x-axis,   
intersecting the x-axis $k$ times,  and 
having double ascents of weight 2.
Then  the Delannoy number counts a  union of sets:
$$d_n = \left|\bigcup_{i=1}^{n+1} \mathcal{P}(2n+2i,2i) \right|.$$


\begin{figure}[H]
     \begin{center}
      \vspace{12pt}
     \leavevmode\psfig{figure=doubleascents25.eps,width=14cm}
     
       \vspace{12pt}
     \end{center}
     \caption{ $ 2+4+2+2+2+1= d_2$.
     }
     \label{doubleascents25}
     \end{figure}
}
\end{EXAMPLE}



%%%%% 26
\begin{EXAMPLE}\label{example26}
 {\rm
Let $\mathcal{P}(n,k)$ denote  the set of paths 
using the steps $U$ and $D$,
running from $(0,0)$ to $(n,0)$,
remaining weakly above the x-axis,   
intersecting the x-axis $k$ times, and
evenly positioned ascents of weight 2.
%having  indendently colored,  red or blue, evenly positioned ascents.
Then  the Delannoy number counts a  union of sets:
$$d_n = \left|\bigcup_{i=1}^{n+1} \mathcal{P}(2n+2i,2i)\right|.$$

\begin{figure}[H]
      \vspace{12pt}
     \begin{center}
     \leavevmode\psfig{figure=evenascents26.eps,width=14cm}
       \vspace{12pt}
     \end{center}
     \caption{ $ 4+2+2+2+2+1= d_2$.
     }
     \label{evenascents26}
     \end{figure}
}
\end{EXAMPLE}



%%%%% 27
\begin{EXAMPLE}\label{example27}
 {\rm  On a path using the steps $U$ and $D$, a
{\it restricted long} is a maximal subpath of a single step type having
length exceeding 1, except when the subpath ends at the x-axis, in which case
the length of the subpath must exceed 2.
Let $\mathcal{P}(n,k)$ denote  the set of paths 
using the steps $U$ and $D$,
running from $(0,0)$ to $(n,0)$,
remaining weakly above the x-axis,   
intersecting the x-axis $k$ times and
having restricted longs of weight 2. 
%which are 
%indendently colored by  red or blue.
Then  the Delannoy number counts a  union of sets:
$$d_n = \left|\bigcup_{i=1}^{n+1} \mathcal{P}(2n+2i,2i)\right|.$$

\begin{figure}[H]
     \begin{center}
       \vspace{.4in}
     \leavevmode\psfig{figure=longs27.eps,width=14cm}
       \vspace{12pt}
     \end{center}
     \caption{ $ 2+4+2+2+2+1 = d_2$.
     }
     \label{longs27}
     \end{figure}
}
\end{EXAMPLE}


%%%%% 28
\begin{EXAMPLE}\label{example28} {\rm  The central Delannoy number $d_n$ 
 counts the  matrices with $2$ rows and entries 0 or 1 
such that there are exactly $n$ 1's in each row and at least one 1 in each
column.

\begin{figure}[H]
\vspace{12pt}
     \begin{center}
  {\small
$$ \begin{tabular}{c}
 \begin{tabular}{ccccccccc}
$\left[\begin{tabular}{ccc} $1$&$1$ \\ $1$&$1$ \end{tabular} \right]$
& \quad&
$\left[\begin{tabular}{ccccc} $1$&$1$&$0$ \\ $1$&$0$&$1$ \end{tabular} \right]$
& \quad&
$\left[\begin{tabular}{ccccc} $1$&$0$&$1$ \\ $1$&$1$&$0$ \end{tabular} \right]$
& \quad&
$\left[\begin{tabular}{ccccc} $1$&$1$&$0$ \\ $0$&$1$&$1$ \end{tabular} \right]$
& \quad&
$\left[\begin{tabular}{ccccc} $0$&$1$&$1$ \\ $1$&$1$&$0$ \end{tabular} \right]$
 \end{tabular} \\   \quad \\
 \begin{tabular}{ccccccc}
$\left[\begin{tabular}{ccccc} $1$&$0$&$1$ \\ $0$&$1$&$1$ \end{tabular} \right]$
& \quad\quad&$\left[\begin{tabular}{ccccccc} $0$&$1$&$1$ \\ $1$&$0$&$1$ \end{tabular} \right]$
&\quad \quad&
$\left[\begin{tabular}{ccccccc} $1$&$1$&$0$&$0$ \\$0$&$0$&$1$&$1$\end{tabular}\right]$ &\quad \quad&
$\left[\begin{tabular}{ccccccc} $1$&$0$&$1$&$0$ \\ $0$&$1$&$0$&$1$  \end{tabular} \right]$
 \end{tabular}
 \\  \quad \\
 \begin{tabular}{ccccccc}
$\left[\begin{tabular}{ccccccc} $1$&$0$&$0$&$1$ \\ $0$&$1$&$1$&$0$  \end{tabular} \right]$
& \quad&
$\left[\begin{tabular}{ccccccc} $0$&$1$&$1$&$0$ \\ $1$&$0$&$0$&$1$  \end{tabular} \right]$
& \quad&
$\left[\begin{tabular}{ccccccc} $0$&$1$&$0$&$1$ \\ $1$&$0$&$1$&$0$  \end{tabular} \right]$
& \quad&
$\left[\begin{tabular}{ccccccc} $0$&$0$&$1$&$1$ \\ $1$&$1$&$0$&$0$  \end{tabular} \right]$
\end{tabular}
\end{tabular}
$$
}
     \end{center}
     \caption{There are $d_2$ such matrices.
}
     \end{figure}
}
\end{EXAMPLE}
%%%%% 29 
\begin{EXAMPLE}\label{example29}
 {\rm  The   product  $2^{n-1}d_n$ 
 counts the  matrices having two rows and  nonnegative
 integer
 entries where
 each row sum is  $n$ and each column has at least one positive entry.

\begin{figure}[H]
     \begin{center}
\vspace{12pt}       
 {\small
 $$\begin{tabular}{c}
 \begin{tabular}{ccccccccc}
$\left[\begin{tabular}{c} $2$ \\ $2$ \end{tabular} \right]$
& \quad&
$\left[\begin{tabular}{cc} $2$&$0$ \\ $0$&$2$ \end{tabular} \right]$
& \quad&
$\left[\begin{tabular}{cc} $0$&$2$ \\ $2$&$0$ \end{tabular} \right]$
& \quad&
$\left[\begin{tabular}{ccc} $2$&$0$&$0$ \\ $0$&$1$&$1$ \end{tabular} \right]$
& \quad&
$\left[\begin{tabular}{ccc} $0$&$2$&$0$ \\ $1$&$0$&$1$ \end{tabular} \right]$
\end{tabular}
\\   \quad \\
\begin{tabular}{ccccccc}
$\left[\begin{tabular}{ccc} $0$&$0$&$2$ \\ $1$&$1$&$0$ \end{tabular} \right]$
& \quad&$\left[\begin{tabular}{ccccc} $0$&$1$&$1$ \\ $2$&$0$&$0$ \end{tabular} \right]$
& \quad&
$\left[\begin{tabular}{cccc} $1$&$0$&$1$ \\$0$&$2$&$0$\end{tabular}\right]$ & \quad&
$\left[\begin{tabular}{cccc} $1$&$1$&$0$ \\ $0$&$0$&$2$  \end{tabular} \right]$
\end{tabular} \\
\quad  \\
\begin{tabular}{ccccccc}
$\left[\begin{tabular}{cc} $2$&$0$ \\ $1$&$1$  \end{tabular} \right]$
&\quad \quad&
$\left[\begin{tabular}{cc} $0$&$2$ \\ $1$&$1$  \end{tabular} \right]$
&\quad \quad&
$\left[\begin{tabular}{cc} $1$&$1$ \\ $2$&$0$  \end{tabular} \right]$
& \quad\quad&
$\left[\begin{tabular}{cc} $1$&$1$ \\ $0$&$2$  \end{tabular} \right]$
\end{tabular}
\end{tabular}
$$
}
     \end{center}
     \caption{$2\cdot d_2$ counts the set formed by these matrices and those of
     Figure \ref{example28}.}
     \end{figure}}
\end{EXAMPLE}



\section{Notes regarding verifications}\label{solutions}



Before reviewing the above examples, let us look at a mildly general lattice
path model.  For fixed positive integer $h$, 
we will allow the three steps $U_t$, $D$, and $(h,0)_s$ which are
weighted by  $t$, 1,  and $s$, respectively.
For $n \ge 0$, let $\mathcal{U}(n)$ 
denote the set of all
{\it unrestricted} paths running from $(0,0)$  to $(n,0)$, and 
let  $\mathcal{C}(n)$ 
denote the set of paths in  $\mathcal{U}(n)$   {\it constrained} never
to pass beneath the horizontal axis.  We will use a well-known
decomposition of path sets  to 
derive formulas for  the  generating functions 
 $c(z) := \sum_{n\ge0} |\mathcal{C}(n)| z^n$
and $u(z) := \sum_{n\ge0} |\mathcal{U}(n)| z^n$.

Since each  path of $\mathcal{C}(n)$ must either (i) have zero length, (ii)  start  with 
an $(h,0)$ step followed by a constrained path, 
or  (iii) start with an $U$ step followed by the 
translation of a constrained path, 
then by  a $D$, and finally  by another constrained path
we have
$${c}(z)= 1+ sz^h{c}(z)+ tz^2{c}(z)^2. $$
Since every path in $\mathcal{U}(n)$
either (i) has zero 
length, (ii)  begins with an $(h,0)$ step followed by an unrestricted path, or (iii) begins with   $U$ (or with $D$)   followed by 
a constrained path (or its reflection) which
returns to the horizontal axis for the first time and then
is followed by an unrestricted path, 
$${u}(z) =
 1+ sz^h{u}(z) +2tz^2  {c}(z){u}(z) $$
Solving  these two equations simultaneously  yields
\begin{equation}
{u}(z) =\frac{1}{\sqrt{(1-sz^h)^2-4tz^2 }} =  
\frac{1}{\sqrt{1-2sz^h + s^2z^{2h} -4tz^2 }}.
\nonumber
\end{equation}
If this formula is to agree essentially with the formula of
(\ref{genfundelnos}), then either $h=1$ or $h=2$.  If $h=1$, then 
$u(z) = {1}/{\sqrt{1-2sz + (s^2 -4t)z^2 }},$  and it must be that
$s=3$ and $t=2$.  On the other hand, if $h=2$,  then 
$u(z) = {1}/{\sqrt{1-  (2s+4t)z^2 + s^2z^4  }},$  and thus either
$s=t=1$   or  $s=-1$ and $t = 2$.  

\

We number the subsequent Notes to agree with the numbering of 
the  examples of Section \ref{catalog13}.  Since the examples
may serve as exercises and since they are ordered as collected, these notes
may appear mildly haphazard.

\

\noindent{\bf Note \ref{example1}}
The introductory discussion  of this section gives
the generating function for Example 1.  One can find 
an alternate derivation of the generating
function and a recurrence in
\cite[Sect. 6]{Sulgen}.  Equation (\ref{star}) can be obtained by considering
all possible choices for the steps in the paths leading to $(n,0)$.

%note2 
\

\noindent{\bf Note \ref{example2}}
That the Delannoy numbers count
Example 2 follows from the initial discussion of this section.
In Note 5 we will see how Example 2 is bijectively related to  Example 1
via Examples 3 and 5.


%note3 
\

\noindent{\bf Note \ref{example3}}
Replicate the paths from $(0,0)$ to $(2n,0)$ using the  steps $U$ and
$D$ by independently coloring their right-hand turns by blue  or  red.
Replacing
each consecutive blue $UD$ by a $(2,0)$ step describes a bijection with
Example 1.


%note4 
\

\noindent{\bf Note \ref{example4}}
We will indicate a bijection from Example 4 to a reflected Example 3,
reflected about the horizontal axis.  The following proof is from  the
proof of \cite[equation (5)]{SulR40}.  We will also 
tilt our lattice paths by 45 degrees for the following.


Consider the steps $N := (0,1)$ and $E := (1,0)$. 
Let $A(n)$  denote the set of all paths from $(0,-1)$ to $ (n,n)$
which remain weakly above the horizontal axis except on the first step.
A 
{\it left turn} is the intermediate point of a consecutive $EN$ pair.
Let $A_{\ell}(n)$ ($A_d(n)$, resp.) 
denote the set of replicated  paths formed  from 
$A(n)$
so each  left turn (double ascent, resp.)
is independently colored blue or red.

We have a bijection 
$$ F: A_d(n) \longrightarrow A_{\ell}(n) $$
defined as follows:    Let $P \in A_d(n)$
 be determined by the set (perhaps empty) of the coordinates of its left turns, namely
$\{  (x_1, y_1), \ldots, (x_k, y_k)  \}$.  \  \  
Then $(x'_1, y'_1), \ldots, (x'_h, y'_h),$  
$ \ldots,(x'_{n-k}, y'_{n-k})$ are
 the left turns of the path  $F(P) \in  A_{\ell}(n)$ (This was mistyped in
 \cite{SulR40}.)
where 
\begin{eqnarray*}
  \{x'_1, \ldots, x'_{n-k}\}&=& \{1, \ldots, n\} - \{x_1, \ldots, x_k\}\\
\{y'_1, \ldots, y'_{n-k}\} &=&  \{0, \ldots, {n-1}\} - \{y_1, \ldots, y_k\}
\end{eqnarray*}
 with      $ x'_1  <x'_h  <  x'_{n-k}$ and $ y'_1 <y'_h <y'_{n-k}$  
and the left turn at $(x'_h, y'_h)$ has the color    blue (red, resp.) 
if, and only if,
$y'_h$ is the ordinate of the intermediate vertex of a blue (red, resp.) 
 double ascent on
 $P$.   

See also Note \ref{example14}.

%note5 
\

\noindent{\bf Note \ref{example5}}
 {\bf A.}  Each path in Example 5 is sequence of consecutive 
oddly-evenly positioned step pairs.  The morphism sending $UU$ to $U$,
$UD$ to $(1,0)_2$, $DU$ to $(1,0)_1$,  and $DD$ to $D$
(where its subscripts indicate the weights) determines a weight preserving
bijection from Example 5 to Example 2.

{\bf B.}  We  give  a bijection from Example 5 to Example 1, which constitutes
a combinatorial solution for the {\it Monthly} problem \cite{SulMonthlyProb}. 
Our bijective proof is in the {\it 45-degree tilted}\ environment.  In the
following 
we will encode  each    path from each of the two examples
as a triple of subsets of integers of the form
$(X,Y,H)$ where
$ X := \{ x_1, \ldots, x_h, \ldots, x_i \}
\subset  \{1,  \ldots, n\}$,
$ Y := \{ y_1, \ldots, y_h, \ldots, y_i \} \subset \{1,  \ldots, n\}$,  and
$ H := \{ h_1, \ldots, h_j \} \subset \{1,  \ldots, i\}$ where $i$ and
$j$ depend on the  path.  Since there will be a unique  encoding triple for each path
from each  model  we will have a bijection.

Let $\mathcal{A}(n)$  denote the set of lattice paths from $(0,0)$ to
$(n,n)$  that permit four step types:
the horizontal step $(1,0)$,
the uncolored step $(0,1)$
where this vertical step may assume  only even positions in a path,
and the steps $(0,1)_{\mbox{red}}$ or $(0,1)_{\mbox{green}}$
where these vertical steps may assume  only  odd positions in a path.
Any path in $\mathcal{A}(n) $ having $i$ of its horizontal steps in
the even  positions,
$2x_1, \ldots, 2x_h, \ldots, 2x_i $,
 having necessarily $i$ of its vertical  steps in the odd  positions,
$2y_1\!-\!1, \ldots, 2y_h\!-\!1, \ldots, 2y_i\!-\!1 $,
and having exactly
$j$ red steps in  positions,   $2y_{h_1}\!-\!1, \ldots, 2y_{h_j}\!-\!1$, can be encoded
as $(X,Y,H)$.

 Let $\mathcal{D}(n)$  denote the set of lattice paths from $(0,0)$ to
$(n,n)$  that permit the three step types:  $(1,0)$, $(0,1)$, and
the diagonal, $(1,1)$. 
By replacing each diagonal step with a blue $(0,1)(1,0)$ step pair (i.e., 
{\it a blue  right-hand turn}), we can match each path in $\mathcal{D}(n)$
having $j$ diagonal
steps and $i-j$ uncolored  right-hand turns  with a marked path from
$(0,0)$ to
$(n,n)$  that uses  the two steps,  $(1,0)$ and $(0,1)$, and has marked
right-hand turns.
Each resulting marked path is
determined by   the coordinates of the intermediate
vertices of its right-hand turns, say, $(x_1\!-\!1,y_1)$,
$\ldots,$  $(x_h\!-\!1,y_h)$,
$\ldots$ $(x_i\!-\!1,y_i)$,  where  those turns corresponding to   $y_{h_1},
\ldots, y_{h_j}$ are colored blue. Hence,  each  path can
be encoded
as $(X,Y,H)$.

See also Note 14.

%note6 
\

\noindent{\bf Note \ref{example6}}
This example appears as exercise  
\cite[6.16]{StanleyBookII} where a generating function proof is indicated.
A combinatorial proof, as requested in \cite{StanleyBookII}, appears in
\cite{SulR40} and uses 
some of the bijections of these notes.


%note7 
\

\noindent{\bf Note \ref{example7}}
That the Delannoy numbers count this example
follows from the initial discussion of Section 3.
Presently we have no ideas for bijective considerations.


%note8 
\

\noindent{\bf Note \ref{example8}}
A generating function argument, 
and consequently, the recurrence (\ref{recurrencedelnos}) for Example 8
 appear in \cite{Sulgen}. 
{\it The cut and paste bijection}\ of \cite{PPRScut} 
gives an immediate bijection between this example and  Example 1.


%note9 
\

\noindent{\bf Note \ref{example9}}
{\it The cut and paste bijection} \cite{PPRScut}  
gives an immediate bijection  between this example and  Example 7. 


%note10 
\

\noindent{\bf Note \ref{example10}}
{\it The cut and paste bijection} \cite{PPRScut}   
gives an immediate bijection between this example and  Example 2. 
See Note 11.


%note11 
\

\noindent{\bf Note \ref{example11}}
In \cite{Sul3Rec} a {\it zebra} is defined as a parallelogram polyomino having
all (not just the noninitial) columns colored either black or white.
In \cite{Sul3Rec} generation function methods  show that 
 the sum of the average of the squares of
the diagonal thicknesses of all zebras of a fixed perimeter is 
twice a Delannoy number.
By extending  the known bijection given in \cite{Delest} 
(See also  \cite[Sect. 5]{Sul3Rec}.),
we have a bijection between 
the configurations of Example 11 and those of Example
10.


%note12 
\

\noindent{\bf Note \ref{example12}}
 Sachs and Zernitz \cite{Sachs} discovered this example and its solution,
 giving them 
 in terms of counting perfect matchings. 
 Stanley \cite[Exercise 6.49]{StanleyBookII} records Dana Randell's
 restatement of the example and its solution in terms of Aztec diamonds.  
%note13

\

\noindent{\bf Note \ref{example13}}
 For $m = 1,2,3,\ldots,$
 let COMB$_m$ denote the {\it comb graph}\ with $m$
teeth. 
This graph has vertex set $\{1,2,\ldots, 2m\}$ and edge set 
$$\left\{ \{1,2\},  \{3,4\}, \ldots,  \{2m-1,2m\} \right\}\cup \left\{ \{2,4\} , \{4,6\} , 
\ldots,  \{2m-2,2m\} \right\}.$$
In addition to the example for $d_n$,
Emeric Deutsch \cite{DeutschprivJune2002}
discovered that the collection of sets of $k$ pairwise nonadjacent edges of
COMB$_m$ has cardinality $d_{k,m-k}$.  To see this one can establish a
bijection from this collection to the collection of paths from $(0,0)$ to 
$(k,m-k)$ using the steps $(0,1),(1,0),(1,1)$.  In particular, 
this bijection maps a set with
$j$ edges of the type $\{2i,2i+2\}$ to a path with $j$  steps of type $(1,1)$. 

%note14 
\

\noindent{\bf Note \ref{example14}}
For Dyck paths (i.e., paths running from $(0,0)$ to $(2n,0)$,
using the steps $U$ and $D$, and never running below the $x$-axis) 
there are many statistics which are distributed by the Narayana 
numbers  \cite{SulNar66}: namely, for $1\le k \le n$,
$$ \frac{1}{n}{{n}\choose{k-1}}{{n}\choose{k}}.  
$$ 
The three  classic statistics are (i) the {\it number of peaks}
(This is 
immediately equivalent both to number of valleys plus one and to the number of 
double ascents plus one.),  (ii) the {\it number of ascents which are 
oddly positioned along the path}, and
(iii) the {\it number of nonfinal longs} plus one.  (See Examples 3, 4, and 5. The 
{\it plus one}\ term is  unavoidable -- it is in agreement with the
need for both small and large Schr{\"o}der numbers.  (See
\cite{SulNarSTATPLANNING}.) 

For unrestricted paths, if
one assign a weight of 2 to each object (or substructure)
counted by those
statistics, computes the weight of each path, and then sums over the paths of a given length, one arrives at the
Delannoy number as in 
Examples 3, 4, 5, and 14.  That the assignment of
the weight  2 to 
each objects counted by certain statistics yields a Delannoy number is in
agreement with equation (\ref{sumsqtwo}).

Kreweras and
 Moszkowski \cite{KrewerasMoszkowski} introduced 
 the {\it number of nonfinal longs} statistic for Dyck paths. 
 Benchekroun and Moszkowski \cite{Benchekroun} then gave a bijective proof
 that this statistic indeed has the Narayana distribution:  The number of
 Dyck paths of length $2n$, having $k$ nonfinal longs is 
\begin{equation}\label{eqnnote21}
|\mathcal{D}(n,k)| = \frac{1}{n}{{n}\choose{k}}{{n}\choose{k+1}}.  
\end{equation} 
  We 
 use their proof to obtain a bijection between Example 14 and 
 a modified Example 3, modified as to be in  
 terms of  left-hand turns (i.e., valleys,
 not peaks). 
 To obtain the domain for this bijection we tilt the paths of Example 14 to run from $(0,-1)$
 to $(n,n)$ weakly above the x-axis except on the first step and to use the
 steps $(0,1)$ and $(1,0)$.  The codomain will be the
 set of paths from  $(0,0)$
 to $(n,n)$ with the unit steps $(0,1)$ and $(1,0)$.
 If  $(x_1,y_1)$, ...,  $(x_h,y_h)$, ..., $(x_j,y_j)$ denote the locations of
 the 
 next to the final lattice points on the long steps of a path in the  domain,
 then $(x_1+1,y_1)$, ...,  $(x_h+1,y_h)$ , ...,  $(x_j+1,y_{j-h})$   will be
 the locations of the left-hand turns of the image path. 

%note15 
\

\noindent{\bf Note \ref{example15}}
%comm by letter from shapiro July 11
Louis Shapiro \cite{ShapiroJuly} discovered this example. 
A bijection with the tilted version of Example 1 can be established
recursively.  Let $\mathcal{W}(x,y)$ 
denote the set of lattice walks of the Example
\ref{example15} that have $x+y$ steps and final height $y$. Let 
$\mathcal{U}(x,y)$
denote the set of lattice path running from $(0,0)$ to $(x,y)$ that
use the steps $E := (1,0)$, $N := (0,1)$, and $D:=(1,1)$.  We define
$f := \mathcal{W}(x,y) \rightarrow \mathcal{U}(x,y)$ so that 
$f(PE) = f(P)E$, $f(PWW) = f(PW)E$,
$f(PNW) = f(P)D$, and $f(PN) =f(P)N$.  With the obvious boundary conditions
for $x=0$ or $y=0$, $f$ can be shown to be bijective.



%note16 
%email from Sylviane on July 11
\

\noindent{\bf Note \ref{example16}}
This and the next example were found by Sylviane Schwer \cite{Schwersarrange}
and her interest in the Delannoy numbers
resulted in \cite{BanderierWhy}.
More generally, she considered unlabeled balls of $m$ colors with 
$p_i$ balls having color $i$, for $i = 1 \ldots m$. For $\ell = max(
p_1, p_2, \ldots, p_m)$ and $u = p_1+ p_2+ \cdots + p_m$, she made available
$u-\ell+1$ collections of urns where each collection has $r$ urns, labeled 
by $1,2, \ldots, r$, for $\ell \le r \le u$.  
With $D(p_1, p_2, \ldots, p_m)$ denoting the ways to distribute the balls so
that in each urn there is a ball  and  no two balls have the same color,
she showed that  $D(p_1, p_2, \ldots, p_m)$ is isomorphic to the lattice
paths in $m$-space that  run from 
$(0,0,\ldots,0)$ to $(p_1, p_2, \ldots, p_m)$ using the nonzero steps
of the form $(\epsilon_1, \epsilon_2,  \ldots, \epsilon_m)$ where $\epsilon_i \in \{0,1\}$.  (See 
\cite{Kaparthi} for a discussion of multidimensional Delannoy numbers.)
%note17 

\

\noindent{\bf Note \ref{example17}}
Continuing from note 16, Schwer formulated the enumeration of possible words
which take as their alphabet nonempty subsets of some set $X= \{x_1,
x_2,\ldots, x_m\}$.  If $||f||_x$ denotes the number of occurrences of $x$ 
in the subsets forming a word $f$, then  
the Parikh vector of $f$ is denoted by 
$(||f||_{x_1},||f||_{x_2},\ldots,||f||_{x_m})$.  
The set of words with  a Parikh vector equal to $(p_1, p_2, \ldots, p_m)$ 
has the cardinality of $D(p_1, p_2, \ldots, p_m)$.
%note18

\

\noindent{\bf Note \ref{example18}}
 This example was found by  M.~Vassilev  and
K.~Atanassov\cite{Vassilev}. See {\it Math Rev.:} 96b:05004.
More generally, their paper proves that
$d_{p,q}$  counts $\{ y \in  {\mathbb Z}^p : ||y||_1 \le q \}$.


% Mladen Vassilev and Krassimir Atanassov
% On Delanoy [{\it sic}] Numbers,
%{\it Annuaire de L'Universite de Sofia, ``St. Kliment Ohridski,''}
%Faculte de Mathematiques et Informatique,  Livre 1 -
%Math{\' e}matiques, Tome 81, (1987) 153-162.
% {\it Annuaire Univ. Sofia Fac. Math. Inform.} 81, no. 1, 153--162 (1994)
% 
% {\it Math Rev.:} 96b:05004

%%%note 19
\

\noindent{\bf Note \ref{example19}}
 Let $\mathcal{P}(x_0)$ denote the set of unweighted paths 
using the steps, $(1,1)$ and $(1,-1)$,
beginning at  $(0,0)$, ending on  the line $x = x_0$, and
remaining weakly above the x-axis. 
Then 
\begin{equation}
\label{lemmababy}
|\mathcal{P}(2k)| = {{2k} \choose k}.
\end{equation}
To see (\ref{lemmababy}), we first observe that the manner in which 
the paths of $P(2k-1)$ can be appended to form paths of $\mathcal{P}(2k)$ 
implies $|\mathcal{P}(2k)| = 
2 |\mathcal{P}(2k-1)|$.  Likewise,  $|\mathcal{P}(2k-1)|  =  2|\mathcal{P}(2k-2)| - c_{k-2}$,
where $c_{k-2} = {{2k-2}\choose {k-1}}/k$ is 
the Catalan number counting the paths in $\mathcal{P}(2k-2)$ which
terminate at $(k-2,0)$.  Since the central binomial coefficient satisfies
${{2k} \choose k}   = 4{{2k-2} \choose {k-1}} - 2c_{k-2}$, (\ref{lemmababy})
follows inductively. 

To verify this example we count the ways to insert $n-k$
$(2,0)$-steps into any path of $\mathcal{P}(2k)$.  Hence,
$$\sum_k {{2k} \choose k} {{ n+k}\choose {n-k}} =
\sum_k \frac{  (2n)!}{ k! k! (n-k)! } = 
\sum_k   {{n} \choose k}  {{ n+k}\choose {k}} = d_n.$$

%%%note 20
\

\noindent{\bf Note \ref{example20}}
 Example 20 follows  by labeling the peaks of
Example 19 red and replacing the $(2,0)$-steps by a blue $(1,1)(1,-1)$ pair.
It would be interesting to find a bijection involving an even earlier example.
%%%note 21

\

\noindent{\bf Note \ref{example21}}
Let $\mathcal{D}(n,k)$ denote the set of lattice paths running from $(0,0)$ to
$(n,0)$,  using the steps $U$ and $D$, never passing
beneath the $x$-axis, and having $k$ non-final longs. 
By Note 14, $|\mathcal{D}(n,k)|$ has the 
the Narayana distribution.
Let $\mathcal{L}(n,k)$ denote the set of lattice paths running from $(0,0)$,
having $n$ steps of types $U$ and $D$, never passing
beneath the $x$-axis, and having $k$ longs.

Since $\cup_{n>0} \mathcal{D}(n,k)$ can be decomposed with respect to the
point of first return to the $x$-axis, we have, for 
$d:= d(x,t) =\sum_{n\ge 0}\sum_{k\ge 0}|\mathcal{D}(n,k)|t^kx^n$,   
\begin{equation}\label{gflongs1}
d  =1+ x^2d + x^2t(d-1 + (t-1)x^2d)(d-1) + x^2(d+(t-1)x^2d).
\end{equation}
Here the next-to-the-last term corresponds to an intermediate first
return to the $x$-axis; hence the first $t$ is required to count the nonfinal long assumed
by the $D$ steps at that return.  
The $(t-1)x^2$ factors assure that  initial 
double ascents followed by  $D$ steps are counted as being long.

Since $\cup_{n>0} \mathcal{L}(n,k)$ can be decomposed with respect to whether
or not paths return to the $x$-axis for a last time, we have, for 
$\ell := \sum_{n\ge 0}\sum_{k\ge 0}|\mathcal{L}(n,k)|t^kx^n $, 
\begin{equation}\label{gflongs2}
  \ell    =1+ x^2\ell + x^2t(d-1+(t-1)x^2d)\ell 
+ x( \ell + (t-1) x + (t-1) x^2 \ell).
\end{equation}
The factors $t$, $(t-1)x$, and  $(t-1)x^2$ are required somewhat as
indicated in the above paragraph.  Equations 
(\ref{gflongs1}) and (\ref{gflongs2}) easily yield,
with the middle formula discounting paths of odd length,
$$\sum_n\sum_k |\mathcal{L}(2n,k)| 2^k x^n = \frac{\ell(z,2)+\ell(-z,2)}{2}=
\frac{ 1}{ \sqrt{  1 - 6z^2 +z^4} }. $$
%Duchi and rs aug 2002
%%%note 22
\

\noindent{\bf Note \ref{example22}} The reader  can establish a simple bijection between the
paths giving the counts in this array and the paths of Example \ref{example19}.

%%%note 23
\

\noindent{\bf Note \ref{example23}}
Emeric Deutsch \cite{DeutschprivJune2002} contributed this example,
which in turn motivated Examples \ref{example24} through \ref{example27}.  
Essentially these examples consist of attaching a root of odd degree to
a list of structures counted by the large Schr\"{o}der numbers.
One can establish a generating functional proof for this example
similar to that of Note 
\ref{example24}.
%%%note 24

\

\noindent{\bf Note \ref{example24}}
Let $\mathcal{D}(n,k)$ denote the set of lattice paths running from $(0,0)$ to
$(n,0)$,  using the steps $U$ and $D$, never passing
beneath the $x$-axis, and having $k$ peaks.
If $d := d(x,t) = \sum_{n\ge 0}\sum_{k\ge 0}|\mathcal{D}(n,k)|t^kx^n,$
one can decompose the paths with respect to the first return to the $x$-axis
to show
$$d =
1 + tx^2d + x^2(d-1)d.$$
For  $t = 2$, 
$$d(x,2) = \frac{ 1 - x^2 - \sqrt{ 1 - 6x^2 + x^4 }}{2x^2},$$
which is the generating function for the large Schr\"{o}der numbers.

Let $\mathcal{P}(2n+2i,2i)$ be as in the statement of Example \ref{example24}.
Since the paths of $\mathcal{P}(2n+2i,2i)$ are the concatenations of $2i-1$
elevated paths, each of which has generating function  $x^2d= x^2d(x,2) $,
we have 
$$  \sum_{m \ge 0} | \mathcal{P}(2m,2i)| x^2 = (x^2d)^{2i-1}.$$
Hence,
$$
\sum_{n\ge0}\sum_{i \ge 1} |\mathcal{P}(2n+2i,2i)| x^{2n}=
\sum_{i \ge 1}x^{-2i}\sum_{n\ge0} |\mathcal{P}(2n+2i,2i)| x^{2n+2i},
$$ which is equal 
$$\sum_{i \ge 1}x^{-2i} (x^2d)^{2i-1} =
\sum_{j \ge 0} x^{2j}d^{2j+1} =\frac{ d}{1-x^2d^2} = 
\frac{1}{\sqrt{ 1 - 6x^2+x^4}}.$$

\

\noindent{\bf Note \ref{example25}}
Refer to Notes  \ref{example23} and  \ref{example24}.
%%%note 26

\

\noindent{\bf Note \ref{example26}}
Refer to Notes  \ref{example23} and  \ref{example24}.

%%%note 27

\

\noindent{\bf Note \ref{example27}}
Refer to Notes  \ref{example23} and  \ref{example24}.


%%%note 28

\

\noindent{\bf Note \ref{example28}} The reader  can establish a simple bijection between  this example 
and Example \ref{example1} or \ref{example16}. 
%%%note 29

\

\noindent{\bf Note \ref{example29}}
The reader  can establish a simple bijection between  this example 
and Example \ref{example6}. 



\begin{thebibliography}{9}
\bibitem{BanderierWhy} 
C.~Banderier and S.~Schwer, Why Delannoy numbers?, Preprint, 2002\\
{\tt hhtp://algo.inria.fr/banderier}

\bibitem{Benchekroun} S.~Benchekroun and P.~Moszkowski,
A bijective proof of an enumerative property of legal bracketings, {\it
Eur. J. Combin.} {\bf 17} (1996) 605--611. 

\bibitem{Comtet}  L. Comtet, {\it Advanced Combinatorics}, D. Reidel
Publishing Co., 1974.

\bibitem{Delannoychiquier}  H. Delannoy,
Emploi de l'{\'e}chiquier pour la r{\'e}solution de certains probl{\`e}mes de
probabilit{\'e}s. {\it Assoc. Franc. Bordeaux,}\ {\bf 24} (1895) 70--90.


\bibitem{Delest} 
M-P. Delest and G.  Viennot, Algebraic languages and polyominoes
enumeration. {\it Theoret. Comput. Sci.}\  {\bf 34} (1984), 169--206.

\bibitem{DeutschprivJune2002} E. Deutsch, private communications, June and
July, 2002.

\bibitem{KrewerasMoszkowski}
G.~Kreweras and P.~Moszkowski,  A new enumerative property of the Narayana
numbers, {\it J. Stat. Plann. Inference}
{\bf 14} (1986),  63--67.

\bibitem{Lawden} D.F.~Lawden,  
On the solution of linear difference equations. {\it Math. Gaz.}
{\bf 36} (1952), 193--196.

\bibitem{Moser} L.~Moser and W.~Zayachkowski, Lattice paths with diagonal steps,
{\it Scripta Math.} {\bf 26} (1963), 223--229.

\bibitem{PPRScut}
E. Pergola,  R. Pinzani, S. Rinaldi, and R. A. Sulanke,  
Lattice path moments by cut and paste,
To appear, {\it Adv. in Appl. Math.}, 2003.

\bibitem{Sachs} H. Sachs and H. Zernitz,  Remark on the dimer problem. 
{\it Disc.\ Appl.\  Math.} {\bf 51} (1994), 171--179.

\bibitem{Schwersarrange} 
S.R.~Schwer, S-arrangements avec r\'{e}p\'{e}titions, 
{\it C. R. Acad. Sci. Paris,} Ser. I {\bf 334} (2002) 1--6.

\bibitem{ShapiroJuly}
L. Shapiro, private communication, July 2002.

\bibitem{Kaparthi}
S.~Kaparthi and H.R.~Rao, 
Higher-dimensional restricted lattice paths with diagonal steps. 
{\it Disc.\ Appl.\ Math.}\ {\bf 31} (1991), 279--289.

\bibitem{Sloane} N.J.A.~Sloane, 
{\it On-Line Encyclopedia of Integer Sequences},\\
{\tt http://www.research.att.com/\char'176njas/sequences/}

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

\bibitem{SulNar66}
R. A. Sulanke,
Catalan path statistics having the Narayana distribution,
{\it Disc.\ Math.}\ {\bf 180} (1998), 369--389.

\bibitem{Sul3Rec} R. A. Sulanke,
Three recurrences for parallelogram polyominoes, {\it J. of Difference
Eq. and its Appl.} {\bf 5} (1999), 155--176.

\bibitem{SulNarSTATPLANNING}
R. A. Sulanke, The Narayana distribution, 
{\it J. Statist. Plann. Inference}\ {\bf 101} (2002),
311--326.

\bibitem{Sulgen} R. A. Sulanke,  Moments of generalized Motzkin  paths, 
 {\it J.  Integer Seq.}, Vol. 3 (2000), Article 00.1.1   

\bibitem{SulR40}  R. A. Sulanke, Counting lattice paths by Narayana polynomials,
 {\it Electron. J.  Comb.}, {\bf 7} (1), (2000), \#R40.
   
\bibitem{SulMonthlyProb} 
R. A. Sulanke, Problem 10894, {\it Amer. Math. Monthly} {\bf 108} (2001), 770.

\bibitem{Vassilev} M.~Vassilev and K.~Atanassov,
% Mladen Vassilev and Krassimir Atanassov
On Delanoy [{\it sic}] numbers,
%{\it Annuaire de L'Universite de Sofia, ``St. Kliment Ohridski,''}
%Faculte de Mathematiques et Informatique,  Livre 1 -
%Math{\' e}matiques, Tome 81, (1987) 153-162.
{\it Annuaire Univ. Sofia Fac. Math. Inform.} {\bf 81} (1994) 153--162.
\end{thebibliography}

\bigskip
\hrule
\bigskip


\noindent 2000 {\it Mathematics Subject Classification}: 05A15 \

\noindent \emph{Keywords: 
Delannoy numbers, lattice paths, Narayana numbers, Schr{\"o}der
numbers.}

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence \seqnum{A001850}.)

\vspace*{+.1in} \noindent Received November 13, 2002;
revised version received  February 12, 2003.
Published in {\it Journal of Integer Sequences} March 2, 2003.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.


\end{document}