\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}

\newcommand{\bin}{\left (\!\!\! \begin{array}{c}}
\newcommand{\ebin}{\end{array} \!\!\! \right )}
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newsavebox{\savepar}
\newenvironment{boxit}{\begin{lrbox}{\savepar}
\begin{minipage}[b]{150mm}}
{\end{minipage}\end{lrbox}\fbox{\usebox{\savepar}}}


\newtheorem{theo}{Theorem}[section]
\newtheorem{lem}[theo]{Lemma}
\newtheorem{cor}[theo]{Corollary}
\newtheorem{defi}[theo]{Definition}
\newtheorem{ex}[theo]{Example}
\newtheorem{rem}[theo]{Remark}
\newtheorem{prob}[theo]{Problem}



\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}



\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf
Generalized Schr\"oder Numbers and the \\
\vskip .1in
Rotation Principle
}
\vskip 1cm
\large
Joachim Schr\"oder \\
Universiteit van die Vrystaat \\
Departement van Wiskunde\\
Posbus 339 \\
Bloemfontein 9300 \\
South Africa \\
\href{mailto:schroderjd@qwa.uovs.ac.za}{\tt schroderjd@qwa.uovs.ac.za}
\footnote{web page: {\tt http://www16.brinkster.com/jodis}}
\end{center}
\vskip .2 in



\begin{abstract}
Given a point-lattice $(m+1) \times (n+1) \subseteq \mathbb N
\times \mathbb N$ and $l \in \mathbb N$, we determine the number of
royal paths from $(0,0)$ to $(m,n)$ with unit steps $(1,0)$, $(0,1)$
and $(1,1)$, which never go below the line $y = lx$, by means of the
rotation principle. Compared to the method of ``penetrating
analysis'', this principle has here the advantage of greater clarity
and enables us to find meaningful additive decompositions of
Schr\"oder numbers. It also enables us to establish a connection to
coordination numbers and the crystal ball in the cubic lattice
$\mathbb Z^d$. As a by-product we derive a recursion for the number
of North-East turns of rectangular lattice paths and construct a
WZ-pair involving coordination numbers and Delannoy numbers.
\end{abstract}



\section{ Introduction} Given a $m \times n$
chess board we can ask ourselves in how many different ways a king
can walk from the lower left corner $(0,0)$ to the upper right
corner $(m,n)$. The king may only take single steps to the north,
east, and north-east; see Fig.\ref{DS} for $m=n=2$. Such paths are
called royal. The (known) answer to this question is given by the
{\em Delannoy numbers}
\begin{equation} D(n,m) = \sum_{\nu =0}^{m} \bin m\\\nu \ebin \bin n+\nu\\m \ebin
= \sum_{\nu =0}^{\min\{m,n\}} 2^\nu \bin m\\ \nu \ebin \bin n\\ \nu \ebin
\label{noy}
\end{equation}
The sequence of central Delannoy numbers $(D(n,n))_{n \in \mathbb
N}$ is the Legendre transform of the constant sequence $(1,1,
\ldots)$ and the close relation to Legendre polynomials is often
noticed: $D(n,n) = P_n(3)$. Early references are Moser \cite{Moser}
and Lawden \cite{Lawden}. This relation is usually regarded as an
isolated incident (see, e.g., Banderier and Schwer \cite[p.\ 41]{why},
and Sulanke \cite[p.\ 2]{Sulanke}). Compare, however, the
different opinion of Hetyei \cite{Hetyei}. Sulanke alone lists 30
combinatorial structures counted by the Delannoy numbers in
\cite{Sulanke,Sulanke2}. Banderier \& Schwer \cite{why}
give additional information about the origin and use of this number
sequence.

\begin{figure}
\setlength{\unitlength}{1mm}

\begin{picture}(140,40)
%
\thicklines
\put(0,24){\line(0,1){16}}
\put(0,40){\line(1,0){16}}
%
\put(20,24){\line(0,1){8}}
\put(20,32){\line(1,1){8}}
\put(28,40){\line(1,0){8}}
%
\put(40,24){\line(0,1){8}}
\put(40,32){\line(1,0){8}}
\put(48,32){\line(0,1){8}}
\put(48,40){\line(1,0){8}}
%
\put(60,24){\line(0,1){8}}
\put(60,32){\line(1,0){8}}
\put(68,32){\line(1,1){8}}
%
\put(80,24){\line(1,1){8}}
\put(88,32){\line(0,1){8}}
\put(88,40){\line(1,0){8}}
%
\put(100,24){\line(1,1){8}}
\put(108,32){\line(1,1){8}}
\thinlines
%
\put(0,5){\line(1,0){16}}
\put(16,5){\line(0,1){16}}
%
\put(20,5){\line(1,0){8}}
\put(28,5){\line(1,1){8}}
\put(36,13){\line(0,1){8}}
%
\put(40,5){\line(1,0){8}}
\put(48,5){\line(0,1){8}}
\put(48,13){\line(1,0){8}}
\put(56,13){\line(0,1){8}}
%
\put(60,5){\line(1,0){8}}
\put(68,5){\line(0,1){8}}
\put(68,13){\line(1,1){8}}
%
\put(80,5){\line(1,1){8}}
\put(88,13){\line(1,0){8}}
\put(96,13){\line(0,1){8}}
%
\put(100,5){\line(0,1){8}}
\put(100,13){\line(1,0){16}}
\put(116,13){\line(0,1){8}}
%
\put(120,5){\line(1,0){8}}
\put(128,5){\line(0,1){16}}
\put(128,21){\line(1,0){8}}

\end{picture}
\caption{$D(2,2) = 13$ and $\mbox{Schr}(2,2,1) = 6$ \label{DS}}

\end{figure}

A companion of the  Delannoy sequence and of independent interest is
the sequence of (large) {\em  Schr\"oder-numbers}
$(\mbox{Schr}(n,m))_{n,m \in \mathbb N}$: The number of royal
superdiagonal paths from $(0,0)$ to $(m,n)$, i.e., the number of
king walks which may touch but not go below the diagonal $y = x$.
(see bold paths in Fig.\ref{DS}). The history of (small) Schr\"oder
numbers $1/2 \times \mbox{Schr}(n,n), n \geq 1$, probably reaches
tack as far as 200 {\sc B.C.E.} \cite{Stan1}.
Stanley \cite[Exercise 6.39]{Stan2} gives 11
combinatorial objects counted by $(\mbox{Schr}(n,n))_{n \in \mathbb
N}$.

Constrained lattice paths are closely related to the enumeration
of trees, ballot sequences, pattern avoiding permutations,
parallelogram polyominoes and polygon dissections \cite{Stan2}.

There are general methods of deriving complicated formulae
for restricted lattice paths \cite{Krew1,Biz,GV}.
However, one might be interested in an expression of closed form.

Goulden \& Serrano \cite{GouSer}, using the step set
$\{(0,1),(1,0)\}$, noticed that Andr\'e\,'s reflection principle
\cite{refl} can successfully be replaced by the rotation principle
\cite{KrattSul,GouSer}, when the restricting line has an
integer slope strictly larger than $1$. We will apply their method
to lattice paths with the step set $\{(0,1),(1,0), (1,1)\}$, i.e.,
we will be dealing with generalized Schr\"oder numbers. They have
been investigated before by Rogers \cite{Rogers1,Rogers2},
Rogers \& Shapiro \cite{RS} and Sulanke \cite{Sulanke3} within the
framework of general convolution arrays in Example 6A.

Our approach is geometrically appealing and establishes a connection
to Delannoy and {\em  coordination numbers} [ see Def. \ref{coord}.5
]. There are other methods suited for this type of enumeration
problems, but the geometric meaning is less obvious. They are
variously termed `penetrating analysis' (aka `cycle lemma
application' \cite{DvoMotz}, `conjugacy principle' \cite{Ran},
`radiation scheme' \cite{Sulanke3}), the elegant `two rowed arrays'
\cite{Kratten} and `balls into cells' \cite{GoodNara},
\cite[p.\ 20]{Mohanty}, if the slope of the restricting line equals
$1$. Note that Goulden \& Serrano \cite{GouSer} forced a geometric
bijection between two-rowed-arrays and paths with a fixed number of
turns.

After presenting preliminary facts and results about NE- and
EN-turns in section 2, we address the main purpose of this paper as
indicated in the title in section 3 and derive two additive
decompositions of Schr\"oder numbers. Section 4 deals with
miscellaneous aspects such as generating functions, Delannoy numbers and
coordination numbers. Calculations were carried out with
Maple$^\copyright$ 9.1.
\section{Prerequisites}
\begin{defi} \em{
\begin{description}
\item[1.]A nonempty subset $S \subseteq \mathbb N\times \mathbb N \setminus \{(0,0)\}$
is called {\em  step set}. \item[2.]A {\em  path} in $(m+1) \times
(n+1)$ from $(0,0)$ to $(m,n)$ is a finite sequence of points
\newline $((x_1,y_1),(x_2,y_2), ... , (x_k,y_k))$ such that
$(x_i,y_i) \in S$ for all $i, 1 \leq i \leq k$ and $\sum x_i= m,
\sum y_i = n$.
\item[3.]A path is called {\em  $l$-path}, $l \in \mathbb N$, if for all $j, 1
\leq j \leq k$ we have $\sum_{i=1}^j y_i \geq l \sum_{i=1}^j x_i$;
i.e., an $l$-path may touch but may not go below the line $y=lx$.
\item[4.]The set of all $l$-paths from $(0,0)$ to $(m,n)$ with the
step set $S$ is denoted by $_lL_S(m,n)$.
\item[5.] Let $L \in$$_lL_S(m,n)$. An up-step $(0,1)$ of $L$ immediately followed by a right-step $(1,0)$
is called {\em  North-East-turn} (NE-turn for short) or {\em
up-right corner} of $L$. A right-step $(1,0)$ of $L$ immediately
followed by an up-step $(0,1)$ is called {\em  EN-turn} or {\em
right-up corner} of $L$. The number of NE-turns (EN-turns) of $L$ is
denoted by $NE(L)$ ($EN(L)$). We will use the coordinate of the
corner to specify a turn.
\item[6.] $|A|$ denotes the cardinality of a set
$A$ or the absolute value of a number $A$.
\end{description} }
\end{defi}
\begin{defi} \em{ Let $S=\{(0,1),(1,0),(1,1)\}$.
\begin{description}
\item[1.] Define $D(n,m):= |\;_0L_S(m,n)|$ (Delannoy numbers)
\item[2.] Define $Schr(n,m,l):=|\;_lL_S(m,n)|, l\geq 1$ (Schr\"oder numbers)
\item[3.] If $f: D \rightarrow \mathbb Z, D\subseteq \mathbb Z,$ is a function, then the (forward) {\em  difference operator} $\Delta$
is defined by $\Delta f(n) = f(n+1) -f(n).$ For instance $\Delta
{n\choose \nu} = {n+1\choose \nu}-{n\choose \nu}={n\choose \nu-1},$
where ${n\choose \nu}$ is the usual binomial coefficient.
\item[4.] Let $ {\bf x}=(x_1,x_2,...,x_d) \in \mathbb Z^d, d \in \mathbb N$. The
{\em  $L^1$-norm} $|{\bf{x}}|_1$ of $ \bf{x}$ is defined by $|{\bf
x}|_1 :=\sum|x_i|$.
\item[5.] ${\cal S}_{d}(n):= \{ {\bf x}\,|\;{\bf x}\in \mathbb Z^d \mbox{ and } |{\bf x}|_1=n\}$ is called
{\em  $d-1$-dimensional crystal sphere} of radius $n$. We set
$S_{d}(n) := |\,{\cal S}_{d}(n)|$. The sequence $(S_{d}(n))_{n \in
\mathbb N}$ is called a {\em  coordination sequence} (or {\em
coordination numbers}). cf. \seqnum{A035597} pp. and \seqnum{A035607} in the
\href{http://www.research.att.com/~njas/sequences/index.html}{\it
Encyclopedia of Integer Sequences}, EIS, \cite{online}


The union $ \bigcup_{\nu = 0}^n {\cal S}_{d}(\nu)=: {\cal G}_d(n)$
is called {\em  $d$-dimensional crystal ball} of radius $n$. We put
$|\,{\cal G}_d(n)| =: G_d(n)= \sum_{\nu = 0}^n S_{d}(\nu)$.
\end{description} } \label{coord}
\end{defi}

\begin{rem}\em{
In the case of $l=0$ or $l=1$ or $n=m$ beautiful intuitive methods
are available to show why the specified enumeration problem has the
specific solution. In the sequel we will need the fact that the
solution to the classical ballot problem reads (cf. \cite{Mohanty})
 \begin{equation}|_lL_{\{(0,1),(1,0)\}}(m,n)| =  \frac{n-lm+1}{n+1}{m+n \choose n} = {m+n \choose n} - l{m+n \choose n+1} \label{classball}\end{equation}
 and the number of paths $L \in$ $_lL_{\{(0,1),(1,0)\}}(m,n)$ with $c$ NE-turns is (cf. \cite{Kratten,GouSer})

$NE^{\leftarrow}_{(n,m,l)}(c):= |\{L| L \in \,_lL_{\{(0,1),(1,0)\}}(m,n)\mbox{ and } NE(L) = c \}| =$ \begin{equation}
{m-1 \choose c-1}{n+1 \choose c}-l{m \choose c}{n \choose c-1} = \frac{n-lm+1}{n+1}{m-1 \choose c-1}{n+1 \choose c}\label{turnNE} \end{equation}
Whereas the corresponding formula for EN-turns reads (cf.\ \cite{Kratten,GouSer}) \newline
$EN^{\leftarrow}_{(n,m,l)}(c):= |\{L| L \in\; _lL_{\{(0,1),(1,0)\}}(m,n)\mbox{ and } EN(L) = c \}| =$ \begin{equation}
{m \choose c}{n \choose c}-l{m +1\choose c+1}{n-1 \choose c-1} \label{turnEN}\end{equation}
We note in passing that a separate calculation (cf.\ \cite{Kratten,GouSer}) of the NE-turn- and EN-turn- statistics is
not necessary, because there is a fixed relation between the number of NE-turns and the number of EN-turns:
$|NE(L)-EN(L)| \leq 1$, depending on the type of the first and the last step. For instance, if the first step is an up-step
and the last step is a right step, we have $NE(L)=EN(L)+1$. An appropriate classification of paths by the type of the last
step before hitting the right edge (respectively upper edge) leads to
}
\end{rem}
\begin{theo}
\begin{equation}NE^{\leftarrow}_{(n,m,l)}(c) = \sum_{v=lm}^n EN^{\leftarrow}_{(v,m-1,l)}(c-1)  \label{NE}\end{equation}
\begin{equation}EN^{\leftarrow}_{(n,m,l)}(c) = \sum_{\mu=1}^m NE^{\leftarrow}_{(n-1,\mu,l)}(c) \label{EN}\end{equation}
\label{thNE}
\end{theo}
{\bf Proof:} Every path above $y = lx, l \geq 1,$ commences with an
up step. A path $L$ with first step up and last step right has one
NE-turn more than EN-turns. Every path has to reach the line segment
joining $(m,lm)$ and $(m,n)$ and does so with a right step, see Fig.
\ref{ENENE}(a). A path $L'$ from $(0,0)$ to $(m-1,\nu), lm \leq \nu
\leq n$ with $c-1$ EN-turns corresponds to a path $L$ from $(0,0)$
to $(m,n)$ with $c$ NE-turns and a right step at $(m-1,\nu)$.
Summing over $\nu$ shows Equation \ref{NE}. To show Equation
\ref{EN} we apply a similar argument and observe that a path $L'$
from $(0,0)$ to $(\mu,n), 1 \leq \mu \leq n $\footnote{The case $\mu
= 0$ does not contribute to the number of EN-turns.}, with last step
up has equal numbers of NE- and EN-turns,
 see Fig. \ref{ENENE}(b). $\Box$



\begin{figure}[t]
\setlength{\unitlength}{1mm}

\begin{picture}(150,80)(-15,0)

%Rahmen
\put(0,15){\dashbox{1}(40,60){}}
\put(39,75){$^{(m,n)}$}
\put(42,54){$^{y=lm}$}
\put(25,20){(a)}

%Diagonale
\put(0,15){\line(1,1){40}}

%Pfad
\thicklines
\put(35,55){\line(1,0){5}} \put(35,60){\line(1,0){5}}
\put(35,65){\line(1,0){5}} \put(35,70){\line(1,0){5}}
\put(35,75){\line(1,0){5}} \put(-0.15,15){\line(0,1){6}}
\put(0.15,15){\line(0,1){6}}

\thinlines
\put(5,35){$\vdots$}\put(25,55){$\ldots$}
\put(10,45){\line(0,1){5}} \put(10,50){\line(1,0){5}}
\put(15,50){\line(0,1){5}} \put(15,55){\line(1,0){5}}

%Rahmen
\put(75,15){\dashbox{1}(40,60){}}
\put(114,75){$^{(m,n)}$}
\put(117,54){$^{y=lm}$}
\put(100,20){(b)}

%Diagonale
\put(75,15){\line(1,1){40}}

%Pfad

 \thicklines
 \put(74.85,15){\line(0,1){6}}\put(75.15,15){\line(0,1){6}}
 \put(80,70){\line(0,1){5}}
 \put(85,70){\line(0,1){5}}\put(90,70){\line(0,1){5}}
 \put(95,70){\line(0,1){5}}\put(100,70){\line(0,1){5}}
 \put(105,70){\line(0,1){5}}\put(110,70){\line(0,1){5}}
 \put(115,70){\line(0,1){5}}

 \thinlines
 \put(80,35){$\vdots$}\put(95,60){$\vdots$}
 \put(85,45){\line(0,1){5}} \put(85,50){\line(1,0){5}}
 \put(90,50){\line(0,1){5}} \put(90,55){\line(1,0){5}}

\end{picture}
\caption{ Classification of paths by right edge (a) and by upper
edge (b), see the proof of Theorem \ref{thNE}. \label{ENENE}}

\end{figure}




\begin{cor}
\begin{equation}\frac{n-lm+1}{n+1}{m-1 \choose c-1}{n+1 \choose c} = \sum_{v=lm}^n \left [{m-1\choose c-1}{v\choose c-1}-l{m\choose c}{v-1\choose c-2}\right ]
 \label{N_by_E} \end{equation}
 \begin{equation} {m\choose c}{n\choose c}-l{m+1\choose c+1}{n-1\choose c-1}  = \sum_{\mu=1}^m \frac{n-l\mu}{n}{\mu-1\choose c-1}{n\choose c}
 \label{E_by_N}\end{equation}
\label{corNE}
\end{cor}
{\bf Proof:} Substitute Equations (\ref{turnNE}), (\ref{turnEN}) into Equations  (\ref{EN}), (\ref{NE}) of Theorem \ref{thNE}. $\Box$
\begin{cor}
\begin{equation}NE^{\leftarrow}_{(n,m,l)}(c) = \sum_{v=lm}^n \sum_{\mu=1}^{m-1}NE^{\leftarrow}_{(v-1,\mu,l)}(c-1)\label{NN} \end{equation}
\begin{equation}EN^{\leftarrow}_{(n,m,l)}(c) = \sum_{\mu=1}^m\sum_{v=l\mu}^{n-1} EN^{\leftarrow}_{(v,\mu-1,l)}(c-1)\label{EE} \end{equation}
\label{NNEE}
\end{cor}
{\bf Proof:} Substitution of Equation (\ref{EN}) in (\ref{NE}) and of Equation (\ref{NE}) in (\ref{EN}). $\Box$
\begin{cor}
\begin{equation} \frac{n-lm+1}{n+1}{m-1 \choose c-1}{n+1 \choose c} = \sum_{v=lm}^n\sum_{\mu=1}^{m-1}\frac{v-l\mu}{v}
{\mu-1\choose c-2}{v\choose c-1} \label{binNE}\end{equation}
\begin{equation} {m \choose c}{n \choose c}-l{m +1\choose c+1}{n-1 \choose c-1}= \sum_{\mu=1}^m \sum_{v=l\mu}^{n-1}
\left [ {\mu-1 \choose c-1}{v \choose c-1}-l{\mu \choose c}{v-1 \choose c-2} \right ] \label{binEN}\end{equation}
\end{cor}
{\bf Proof:} Easy substitution of  Equations \ref{turnNE} and \ref{turnEN} in Corollary \ref{NNEE}. $\Box$
\vspace{3mm}

These formulae, but in general not their interpretation as number of
turns, are also correct for $l\leq 0$.

In the following we will repeatedly make use of
\begin{lem}
Let $m, n \in \mathbb N, p \in \mathbb Z$. Then \[ \sum_{\nu =p}^{m} 2^{\nu}{m
\choose \nu}{n \choose \nu - p} = \sum_{\nu =0}^{m} {m \choose
\nu}{n + \nu \choose m-p}\]\label{power 2}
\end{lem}
{\bf Proof:} We know from Equ.\ref{noy} that  $ \sum_{\nu
=0}^{\min\{m,n\}} 2^\nu {m\choose \nu}  { n\choose \nu}= \sum_{\nu
=0}^{m} {m\choose\nu}  {n+\nu\choose m}  $. The (forward) difference
operator $\Delta$ applied $p$ times yields 

$\sum 2^{\nu}{m
\choose \nu}{n \choose \nu - p} = \Delta^p \sum 2^{\nu}{m \choose
\nu}{n \choose \nu} =$ $\Delta^p \sum {m \choose \nu}{n + \nu
\choose m}= \sum{m \choose \nu}{n + \nu \choose m-p}$. $\Box$
\vspace{3mm}

Our purpose is to extend the reach of the rotation principle beyond Goulden \&
Serrano \cite{GouSer} and to use it to find a meaningful additive decomposition of Schr\"oder numbers.
First, here is what we can get without geometric principles and penetrating analysis:

\begin{theo} \label{Schr_rect}
The number of superdiagonal royal paths from $(0,0)$ to $(m,n)$,
$n \geq lm > 0$, $l \geq 1$, on a $m \times n$ grid is
\[ \mbox{Schr}(n,m,l) =
\frac{n-lm+1}{n+1}\sum_{\nu =1}^m 2^{\nu}\bin m-1\\\nu -1 \ebin
 \bin n+1\\\nu \ebin
  =  \frac{n-lm+1}{m}\sum_{\nu =1}^m 2^{\nu}\bin m\\\nu \ebin \bin n\\\nu -1 \ebin\]
\[ =\frac{n-lm+1}{m}\sum_{\nu =0}^m \bin m\\\nu \ebin \bin n+\nu\\m-1 \ebin =
 \frac{n-lm+1}{n+1}\sum_{\nu =0}^{n+1} \bin n+1\\\nu \ebin
\bin m-1+\nu\\n \ebin \] \[=\frac{n-lm+1}{n+1}\sum_{v =0}^{m} {n+1\choose m-v}{n+v\choose v}\]

\end{theo}
{\bf Proof:} (compare with the proof in Sulanke \cite{Sulanke3})
We know from Equ. \ref{turnNE} that there are
$\frac{n-lm+1}{n+1}{m-1 \choose v-1}{n+1 \choose v}$ paths weakly
above $y=lx$ with $v$ NE-turns. NE-turns may be changed
independently into diagonal steps or left as they are without
interfering with the line $y=lx$. We can do this in $2^v$
different ways. Summing the term $\frac{n-lm+1}{n+1}2^v{m-1
\choose v-1}{n+1 \choose v}$ over $v$ proves the first equation.
The remaining equations follow by easy term manipulations and by
means of Lemma \ref{power 2}. $\Box$ \vspace{3mm}


Table \ref{smallSchr} displays $\mbox{Schr}(n,m,l)$ for small-sized
input. Whereas some sequences contained in this Table can be found
in Sloane's
\href{http://www.research.att.com/~njas/sequences/index.html} {\em
EIS} \cite{online} (e.g., the diagonals \seqnum{A006318},
\seqnum{A006319}, ... and concatenated rows \seqnum{A106579},
\seqnum{A033877}),  columns $\mbox{Schr}(*,m,l)$ and diagonals for
$l>2$ are not contained in the database \cite{online}.




\begin{table}
\[
\begin{array}{lrrrrr rrrrr rrrrr rrrrr }
l=&1&&&&&2&&&&&3&&&&&4&&&\\
n\backslash m&0&1&2&3 &&0&1&2&3  &&0&1&2&3           &&0&1&2&3&  \\
0 &1&&&             &&1&&&                 &&1&&&              &&1&&&&     \\
1 &1&2&&            &&1&&&                 &&1&&&              &&1&&&&     \\
2 &1&4&6&           &&1&2&&                &&1&&&              &&1&&&&     \\
3 &1&6&16&22        &&1&4&&                &&1&2&&             &&1&&&&     \\
4 &1&8&30&68        &&1&6&10&              &&1&4&&             &&1&2&&&    \\
5 &1&10&48&146      &&1&8&24&              &&1&6&&             &&1&4&&&    \\
6 &1&12&70&264      &&1&10&42&66           &&1&8&14&           &&1&6&&&    \\
7 &1&14&96&430      &&1&12&64&172          &&1&10&32&          &&1&8&&&    \\
8 &1&16&126&652     &&1&14&90&326          &&1&12&54&          &&1&10&18&& \\
9 &1&18&160&938     &&1&16&120&536         &&1&14&80&134       &&1&12&40&& \\
10&1&20&198&1296    &&1&18&154&810         &&1&16&110&324      &&1&14&66&& \\
11&1&22&240&1734    &&1&20&192&1156        &&1&18&144&578      &&1&16&96&& \\
12&1&24&286&2260    &&1&22&234&1582        &&1&20&182&904  &&1&18&130&226& \\
\end{array}
\]
\caption{$\mbox{Schr}(n,m,l)$ for small $n,m,l$. \label{smallSchr}}
\end{table}

\section{Two Decompositions of Schr\"oder Numbers}

\begin{theo}\label{thSc}
Let $l,m,n \in \mathbb N$, $l > 0, n \geq lm$. Then the number of royal paths
on the $m \times n$ grid above the line $y = lx$ from $(0,0)$ to $(m,n)$ is

\[Schr(n,m,l)= D(n,m) -lD(n+1,m-1)-(l-1)D(n,m-1)\]

\end{theo}
{\bf Proof:} If a path crosses the line $y=lx$, there will be a
first segment $C$ whose right end-point is below $y=lx$. This
end-point has to lie on one of the lines $y=lx-s$, $1 \leq s \leq
l$. As usual, we will subtract the number of bad paths (i.e., paths,
which cross the line) from the number of all paths, which is given
by the Delannoy numbers. There are two possibilities: The crucial
segment $C$ is a right step ({\rm I}, see Fig.\ref{bad} Case \rm I),
or it is a diagonal step (\rm{II}, see Fig.\ref{bad} Case \rm II).
\newline
\begin{figure}[t]
\setlength{\unitlength}{1mm}

\begin{picture}(150,100)(-15,0)

%Rahmen
\multiput(0,15)(2,0){20}{\line(1,0){1}}
\multiput(40,15)(0,2){43}{\line(0,1){1}}
\multiput(40,100)(-2,0){20}{\line(-1,0){1}}
\multiput(0,100)(0,-2){43}{\line(0,-1){1}} \put(10,80){Case I}

%Diagonale
%\put(0,15){\line(1,1){60}}
 \put(0,15){\line(1,2){40}}
%2x-1, 2x -2
 \put(42,88){$^{y = 2x-1}$}
 \put(42,83){$^{y = 2x-2}$}
 \multiput(-.43,10)(.5,1){80}{\tiny .}
 \multiput(-.43,5)(.5,1){80}{\tiny .}
 %\put(-.43,0){\tiny .}
 %\put(0,0){\line(0,0){.1}}
%x-1
%\put(50,56){$^{y = x-1}$} \multiput(0,10)(.5,.5){119}{\tiny .}

%Pfad
\put(39,100){$^{(m,n)}$} \thicklines \put(0,15){\line(0,1){10}}
\put(0,25){\line(1,1){5}} \put(5,30){\line(0,1){10}}
\put(5,40){\line(1,0){5}} \put(10,40){\line(0,1){10}}
\put(10,50){\line(1,0){5}} \put(15,50){\line(0,1){15}}
\put(15,65){\line(1,1){5}} \put(20,70){\line(1,0){5}}
\put(25,70){\line(1,0){5}} \put(30,70){\line(0,1){5}}
\put(30,75){\line(0,1){5}} \put(30,80){\line(1,1){5}}
\put(35,85){\line(0,1){15}} \put(35,100){\line(1,0){5}}

%path with the same image-path under rotation
%{\color{webred} \put(0,15){\line(0,1){5}} \put(0,20){\line(1,1){5}}
%\put(5,25){\line(0,1){10}} \put(5,35){\line(1,0){5}}
%\put(10,35){\line(0,1){10}} \put(10,45){\line(1,0){5}}
%\put(15,45){\line(0,1){15}} \put(15,60){\line(1,1){5}}
%\put(20,65){\line(1,0){5}} \put(25,65){\line(1,0){5}}
%}


%rotierter Pfad
 \thinlines
\multiput(30,70)(0,-.5){11}{\line(0,-1){.1}}
\put(30,65){\line(0,-1){10}} \put(30,55){\line(-1,-1){5}}
\put(25,50){\line(0,-1){10}} \put(25,40){\line(-1,0){5}}
\put(20,40){\line(0,-1){10}} \put(20,30){\line(-1,0){5}}
\put(15,30){\line(0,-1){15}} \put(15,15){\line(-1,-1){5}}
\put(10,10){\line(-1,0){5}} \put(2,7){$_{(1,-1)}$}
%Rahmen
\multiput(75,15)(2,0){20}{\line(1,0){1}}
\multiput(115,15)(0,2){43}{\line(0,1){1}}
\multiput(115,100)(-2,0){20}{\line(-1,0){1}}
\multiput(75,100)(0,-2){43}{\line(0,-1){1}} \put(85,80){Case II}

%Diagonale
%\put(75,15){\line(1,1){60}}
 \put(75,15){\line(1,2){40}}
%2x-1, 2x -2
 \put(117,88){$^{y = 2x-1}$}
 \put(117,83){$^{y = 2x-2}$}
 \multiput(74.57,10)(.5,1){80}{\tiny .}
 \multiput(74.57,5)(.5,1){80}{\tiny .}

%Pfad
 \put(114,100){$^{(m,n)}$}
 \thicklines
 \put(75,15){\line(0,1){15}}
 \put(75,30){\line(1,1){5}} \put(80,35){\line(0,1){10}}
 \put(80,45){\line(1,0){5}}
 \put(85,45){\line(1,1){5}} \put(90,50){\line(0,1){15}}
 \put(90,65){\line(1,0){5}} \put(95,65){\line(0,1){5}}
 \put(95,70){\line(1,1){5}} \put(100,75){\line(1,0){5}}
 \put(105,75){\line(1,1){5}} \put(110,80){\line(0,1){10}}
 \put(110,90){\line(1,1){5}} \put(115,95){\line(0,1){5}}


\thinlines

%rotiert
 \multiput(110,80)(0,-.5){11}{\line(0,-1){.1}}
 \put(110,75){\line(0,-1){15}} \put(110,60){\line(-1,-1){5}}
 \put(105,55){\line(0,-1){10}} \put(105,45){\line(-1,0){5}}
 \put(100,45){\line(-1,-1){5}} \put(95,40){\line(0,-1){15}}
 \put(95,25){\line(-1,0){5}} \put(90,25){\line(0,-1){5}}
 \put(90,20){\line(-1,-1){5}} \put(85,15){\line(-1,0){5}}
 \put(79,12){$_{(1,0)}$}


\end{picture}
\caption{ Two bad paths with their rotated portion, one for each
case. See the proof of Theorem \ref{thSc}.\label{bad}}

\end{figure}


{\it Case {\rm I}}) We can follow the approach of Goulden \& Serrano
\cite{GouSer}. The right end-point of $C = [(\alpha -
1,\beta),(\alpha, \beta)]$ has a horizontal distance to $y=lx$ of
$p/l$ for some $p \in \{ 1, 2, \ldots , l \}$. Rotating the portion
of the path from $(0,0)$ to $(\alpha -1,\beta)$ by $180^o$, shifting
the resulting path down and right by one step each and filling the
empty gap between the points $(\alpha, \beta -1)$ and $(\alpha,
\beta)$ by adding a vertical step, establishes a bijection for every
$p \in \{ 1, 2, \ldots , l \}$ between all paths from $(1,-1)$ to
$(m,n)$ and bad paths with horizontal $C$ from $(0,0)$ to $(m,n)$.
Instead of repeating details from \cite{GouSer}, we turn to \newline
{\it Case {\rm II}}) Now C is a diagonal step: $C = [(\alpha -
1,\beta -1),(\alpha, \beta)]$ and $C$ is part of a straight line
$y=x+k$, $0 \leq k \leq n-1$. $(\alpha, \beta)$ lies on one of the
lines $y=lx-s$, $1 \leq s \leq l$. The case $s=l$ (and only that
one) can be refuted, using $\beta = l\alpha - s$ and $\beta -1 \geq
l (\alpha -1)$. Hence there are $\beta -1 \geq l\alpha -l$, $\beta
-1 \geq \beta + s -l$, $s \leq l - 1$. On the other hand, if $\beta
-1 = l(\alpha -1)$, then $\beta = l\alpha - (l-1)$. Hence there are
only $l-1$ different types of diagonal $C$ to consider, compared to
$l$ types of horizontal $C$ in the previous case {\rm I}. For each
of these $l-1$ types we will construct a bijection to the set of all
royal path from $(1,0)$ to $(m,n)$.
\newline Let $y = lx - s$ for fixed $s \in \{ 1, 2, \ldots , l-1 \}$
and let $P'$ be a (unrestricted) royal path from $(1,0)$ to $(m,n)$.
Since $n \geq lm$ there is a smallest $\alpha$, $\alpha \geq 1$,
where $P'$ hits the line $y = lx -s$ at $(\alpha, l\alpha
-s)=(\alpha,\beta)$. $(\alpha, \beta)$ has to be the end-point of an
up step $U=[(\alpha,\beta -1),(\alpha,\beta)]$ of $P'$. We take the
portion of $P'$ from $(1,0)$ to $(\alpha,\beta -1)$, rotate it by
$180^o$ about the centre of the line from $(1,0)$ to $(\alpha,\beta
-1)$ and shift it one unit to the left, which yields a path from
$(0,0)$ to $(\alpha -1,\beta -1)$. Then $(\alpha -1,\beta -1)$ is
joined to $(\alpha,\beta)$ by a diagonal step and $(\alpha,\beta)$
is joined to $(m,n)$ using the remainder of $P'$. On the other hand,
given a bad path $P$ from $(0,0)$ to $(m,n)$ with crossing segment
$C= [(\alpha -1,\beta -1),(\alpha,\beta)]$, $\beta = l\alpha -s$, we
rotate the portion of $P$ from $(0,0)$ to $(\alpha -1,\beta -1)$
about the mid-point of the line segment $[(0,0),(\alpha -1,\beta
-1)]$. The resulting partial path is shifted one step to the right,
the gap between $(\alpha,\beta -1)$ and $(\alpha,\beta)$ is filled
with an up-step. The remainder of $P$ from $(\alpha,\beta)$ to
$(m,n)$ completes the construction. $\Box$

\begin{theo} \label{thco} Let $l,m,n \in \mathbb N$, $l > 0, n \geq lm$. Then
\[Schr(n,m,l)= S_{n+1}(m) - l S_m(n+1),\] i.e., $\mbox{Schr}(n,m,l)$
equals the coordination number of distance $m$ in the
$(n+1)$-dimensional cubic lattice $\mathbb Z^{n+1}$ minus $l$ times
the coordination number of distance $n+1$ in the $m$-dimensional
cubic lattice $\mathbb Z^m$
\end{theo}
{\bf Proof:} By Theorem \ref{thSc}, the number of point-lattice
paths above $y = l x$ is
\[Schr(n,m,l) = D(n,m) - lD(n+1,m-1) -(l-1)D(n,m-1) =\]
\[\sum_{\nu =0}^m 2^\nu \bin m\\ \nu \ebin \bin n\\ \nu \ebin -
l\sum_{\nu =0}^{m-1} 2^\nu \bin m-1\\ \nu \ebin \bin n+1\\ \nu \ebin
- (l-1)\sum_{\nu =0}^{m-1} 2^\nu \bin m-1\\ \nu \ebin \bin n\\ \nu
\ebin =\]
\[\sum_{\nu = 0}^{m}2^{\nu}\bin n \\ \nu\ebin
\left [\bin m \\ \nu  \ebin +\bin m-1 \\ \nu \ebin \right ] -
l\sum_{\nu = 0}^{m-1}2^{\nu}\bin m-1 \\ \nu\ebin \left [\bin n+1 \\
\nu \ebin +\bin n \\ \nu \ebin \right ] =\]
\begin{equation}= S_{n+1}(m) - l S_m(n+1). \label{SS}\end{equation}
Indeed, Conway \& Sloane show in \cite{ConSlo}, p. 9, Equ. (16),
that
\[S_d(n) =
\sum_{k=0}^d {d \choose k}{n+d-k-1 \choose d-1} \;\;\;\;(=
\sum_{k=0}^d {d \choose k}{n+k-1 \choose d-1}) \] is the
coordination number of distance $n$ in $\mathbb Z^d$. To establish
equality in Equ. \ref{SS} we only need
\begin{lem}
\[ S_{a+1}(b)  = \sum_{\nu \geq 0}\bin a+1\\
\nu\ebin\bin b-1+\nu\\a \ebin = \sum_{\nu \geq 1}2^\nu \bin a+1\\\nu
\ebin\bin b-1\\\nu - 1 \ebin \]
\[= \sum_{\nu \geq 0} \bin a\\\nu\ebin \left [\bin b+\nu\\a\ebin +\bin b+\nu-1\\ a\ebin \right ]
= \sum_{\nu \geq 0}2^\nu \bin a\\\nu \ebin \left [\bin b\\\nu \ebin
+\bin b-1\\\nu \ebin\right ]\] \label{simp}
\end{lem}
{\bf Proof:} It is
\[\sum_{\nu \geq 0} \bin a\\\nu \ebin \bin b+\nu\\a \ebin=
\sum_{\nu \geq 1} \bin a\\\nu-1 \ebin \bin b+\nu-1\\a \ebin=
\sum_{\nu \geq 0}\bin b+\nu-1\\a\ebin \left [\bin a+1\\\nu\ebin
-\bin a\\\nu\ebin \right ],\] thus
\[\sum_{\nu \geq 0} \bin a\\\nu\ebin \left [\bin b+\nu\\a\ebin +\bin b+\nu-1\\ a\ebin \right ] =
\sum_{\nu \geq 0}\bin a+1\\ \nu\ebin\bin b-1+\nu\\a \ebin =
S_{a+1}(b)
 \;\;\;\Box\]
The remaining identities follow from the preparatory Lemma
\ref{power 2}. $\Box$
\begin{cor}\label{SDD}
\[S_{a+1}(b) = D(a,b) + D(a,b-1)\]
 {\em Compare Corollary \ref{WZ}.}
\end{cor}
{\bf Proof:} This is trivially true because of Lemma \ref{simp}
and Equation \ref{noy}. $\Box$
 \vspace{3mm}

It is an interesting detail that a contribution to the investigation of $\mbox{Schr}(2m,m,2)$ was
made, though unknowingly, in the problem section of the American
Mathematical Monthly \cite{problem,solution} by D. Callan and the proposer
E. Deutsch, when they submitted their (different) solutions to
problem 10658; see also sequence \seqnum{A027307} in the EIS \cite{online}.
 In fact, as the subsequent Theorem~\ref{1stqua}
shows, they gave a first quadrant representation of
$\mbox{Schr}(2m,m,2)$ in the following way: Let $a_m$ denote the
number of lattice paths in $\mathbb Z \times \mathbb Z$ which stay in the first
quadrant, commence at $(0,0)$ and terminate at $(3m,0)$ with unit
steps $(1,2)$, $(2,1)$ and $(1,-1)$. Then


\begin{theo}
\label{1stqua} $\;\;\;\;\;\;\;a_m = Schr(2m,m,2), \;m \in \mathbb
N\;\;\;\;\;\; \;\;\;\;\;\;\;\;\;\;\;\;\Box$
\end{theo}
Instead of proving this Theorem we show the more general

\begin{theo}\label{gen1stqua}
Let $Q(k,m,l)$ denote the number of point-lattice paths in $\mathbb Z
\times \mathbb Z$ which stay in the first quadrant, start at $(0,k)$, end
at $((l+1)m+k,0)$ and with unit steps $(1,l)$, $(2,l-1)$,
$(1,-1)$. Then $Q(k,m,l) = \mbox{Schr}(n,m,l)$, where $k = n -
ml$, $ n, m, l \in \mathbb N,$ $n \geq ml$.
\end{theo}

{\bf Proof:}  The similarity between the reversed path in the first
quadrant and the superdiagonal royal path in Fig.~\ref{Fig_gen1stqua}
is apparent and suggests finding an affine map
between the two, but a bijective proof is preferable. The bijection
is established by means of certain areas defined above a lattice
path in the first quadrant and above a Schr\"oder path in the $m
\times n$ grid. The factor of proportionality between these areas is
$1/(l+1)$. Instead of tedious details, Fig.~\ref{Fig_gen1stqua} might
suffice as a proof.  $\Box$

\begin{figure}[t]
\setlength{\unitlength}{1mm}

\begin{picture}(150,75)(-17,-5)
%\graphpaper[5](0,0)(95,75) \graphpaper[5](120,0)(20,70)

%Rahmen
\thicklines
\multiput(0,0)(0,5){15}{\begin{picture}(90,5)\multiput(-0.1,0)(5,0){19}{\line(1,0){.2}}\end{picture}}
%\multiput(0,0)(5,0){19}{\begin{picture}(80,5)\multiput(0,0)(0,2){35}{\line(0,1){.5}}\end{picture}}
\thinlines

 \put(90,0){\line(-1,1){70}}
\put(20,70){\line(-1,-3){20}}

 \multiput(0,10)(1,-1){10}{$_.$}
\multiput(5,25)(1,-1){25}{$_.$}
 \multiput(10,40)(1,-1){40}{$_.$}
\multiput(15,55)(1,-1){55}{$_.$}

 \thicklines
\put(0,10){\line(1,-1){5}} \put(5,5){\line(1,1){10}}
\put(15,15){\line(1,3){5}} \put(20,30){\line(1,-1){10}}
\put(30,20){\line(1,1){10}} \put(40,30){\line(1,-1){15}}
\put(55,15){\line(1,3){5}} \put(60,30){\line(1,-1){30}} \thinlines

%Schrvder Pfad
\put(110,0){\line(1,3){20}} \thicklines
\put(130,70){\line(0,-1){5}} \put(130,65){\line(-1,-1){5}}
\put(120,60){\line(0,-1){10}} \put(125,60){\line(-1,-0){5}}
\put(120,50){\line(-1,-1){5}} \put(115,45){\line(0,-1){15}}
\put(115,30){\line(-1,0){5}} \put(110,30){\line(0,-1){30}}
\multiput(110,0)(0,5){15}{\begin{picture}(20,5)\multiput(-0.1,0)(5,0){5}{\line(1,0){.25}}\end{picture}}
%\multiput(120,0)(5,0){5}{\begin{picture}(5,80)\multiput(0,0)(0,5){15}{\line(0,1){.2}}\end{picture}}
\thinlines
%Beschriftung
\put(-16,3.5){ $ k = 2\left \{ \begin{picture}(1,6) \end{picture}
\right.$}

\put(0.5,61){ $l = 3\left \{ \begin{picture}(1,9)
\end{picture} \right.$}

\put(117.8,21){ $\left. \begin{picture}(1,9)
\end{picture} \right \}l = 3$}

 \put(129,-2.5){$_{4 \,= \,m}$}
 \put(90.5,70){$^{14=lm+k=n}$}
 \put(68,-5){$(l+1)m + k=18$}
 \put(10,0){$^2$}
 \put(30,0){$^6$}
 \put(50,0){$^{10}$}
 \put(70,0){$^{14}$}
 \put(90,0){$^{18}$}
 \put(3,24){$^1$}
 \put(8.3,39){$^{2}$}
 \put(17,54){$^{3}$}
 \put(20.3,70){$^{4\, =\, m}$}
 \put(2,13.5){$F_1 \!=\! 6$}
 \put(6,26){$F_2 = 8$}
 \put(21,31){$F_3 = 18$}
 \put(36,36){$F_4 = 32$}

 \put(125,72){$\frac{F_1}{4}$}
 \put(120,72){$\frac{F_2}{4}$}
 \put(115,72){$\frac{F_3}{4}$}
 \put(110,72){$\frac{F_4}{4}$}

 \put(130.5,59){$^{12}$}

 \put(92,40){$F_i \mapsto \frac{F_i}{l+1}$}

 \multiput(110,30)(0,1){40}{\line(0,1){.1}}
 \multiput(115,45)(0,1){25}{\line(0,1){.1}}
 \multiput(120,60)(0,1){10}{\line(0,1){.1}}
 \multiput(125,60)(0,1){10}{\line(0,1){.1}}

\end{picture}
\caption{The case $n=14, m=4, l=3$. \label{Fig_gen1stqua}}

\end{figure}

\section{GF, Delannoy and Coordination Numbers}

\begin{rem} {\em
In the last section of this article we address
miscellaneous results surrounding Schr\"oder numbers such as their
generating function (GF) and a recursion involving the slope $l$. A
general result as regards GFs of convolution arrays was discovered
by Sulanke \cite[1.8, 1.9]{Sulanke3}. We also establish a connection
between Delannoy numbers and crystal spheres and construct a
WZ-pair.

 The special case
$\mbox{Schr}(2m,m,2)$ was treated in Deutsch et al. \cite{solution}.
Our GF is two-variate  (see Theorem \ref{GFSchr}) and accomplished
by combining two results from Sulanke \cite{Sulanke3}. We will need
the GF of Delannoy numbers $D(n,m)$ (cf. \cite{Stan2}):
 \[ \mbox{GF}((D(n,m))_{n,m \geq 0}) = \sum_{n,m \geq 0} D(n,m)x^ny^m =
\frac {1}{1-x-y-xy}\] In essence the first result describes the GF
of the coordination sequence of the cubic lattice $\mathbb Z^d$. It
is the GF version of Corollary \ref{SDD}.}
\end{rem}
\begin{theo} \label{GF_Sc}
\[\mbox{GF}((S_{a+1}(b))_{a,b \geq 0}) = \sum_{a,b \geq 0} S_{a+1}(b)x^ay^b = \frac {1+y}{1-x-y-xy}\]
\end{theo}

{\bf Proof:} We will use Lemma \ref{simp} and a result of Conway
\& Sloane \cite{ConSlo}, p 9, stating that for fixed $d=a+1$
\[\mbox{GF}(\left (\sum_{\nu = 0}^{a+1} {{a+1}\choose {\nu}}{{b +\nu -
1}\choose {a}}\right )_{b \geq 0}) = \left (\frac{1+y}{1-y}\right
)^{a+1}\] and then
\[\sum_{a,b \geq 0} S_{a+1}(b)x^ay^b = \sum_{a,b \geq 0}\sum_{\nu = 0}^{a+1}
{{a+1}\choose {\nu}}{{b +\nu - 1}\choose {a}}y^bx^a =
\sum_{a \geq 0}\left (\frac{1+y}{1-y}\right )^{a+1}x^a = \] \[
\frac{1+y}{1-y}\;\frac{1}{1-\frac{1+y}{1-y}x}= \frac {1+y}{1-y-x-xy}\]
$\Box$

\begin{theo}
\[ D(a,b) = \sum_{\mu = 0}^b S_a(\mu)= G_a(b)\]
{\em see  Fig. \ref{D=C}} \label{D=G}
\end{theo}
{\bf Proof:} We have \[ \frac {1}{1-x-y-xy} =
\frac{1}{1-y}\;\frac{1}{1 - x\frac{1+y}{1-y}} =
\frac{1}{1-y}\sum_{a \geq 0} \left (\frac{1+y}{1-y}\right )^a x^a =\]
\[ \frac{1}{1-y} \sum_{a,b \geq 0} S_a(b)y^bx^a = \sum_{a,b \geq 0}
\sum_{\mu = 0}^b S_a(\mu)y^bx^a = \sum_{a,b \geq 0}
G_a(b)y^bx^a ,\] see Definition \ref{coord}.5.
$\Box$
\begin{figure}
\setlength{\unitlength}{1mm}

\begin{picture}(40,40)(-60,0)
%
\thicklines
\multiput(0.75,1)(0,5){7}{\begin{picture}(60,5)\multiput(-0.1,0)(5,0){7}{\line(1,0){.2}}\end{picture}}

\put(15,15){$\bullet$} \put(10,15){$\bullet$} \put(15,10){$\bullet$}
\put(10,10){$\bullet$} \put(15,20){$\bullet$} \put(20,15){$\bullet$}
\put(10,20){$\bullet$} \put(20,10){$\bullet$} \put(20,20){$\bullet$}
\put(15,25){$\bullet$} \put(15,05){$\bullet$} \put(25,15){$\bullet$}
\put(05,15){$\bullet$}

\end{picture}
\caption{Thirteen points witnessing $G_2(2) = 13$ in agreement with
thirteen lattice paths in Fig. \ref{DS}.\label{D=C}}

\end{figure}

\begin{cor} \label{WZ}
\[ D(a,b) - D(a,b-1) = S_a(b)\]
\[D(a,b) = \frac{S_{a+1}(b) + S_a(b)}{2}\]
\[D(a,b-1) = \frac{S_{a+1}(b) - S_a(b)}{2}\]
\end{cor}

 {\bf Proof:} Note $G_a(b) - G_a(b-1) = S_a(b)$ and Corollary \ref{SDD} $\Box$
\begin{rem} {\em
\begin{description}
\item [1.]
Thus there is a strong relation between Delannoy numbers and
coordination numbers $S$ in $\mathbb Z^{a+1}$. If we put $E(n,b) := \Delta D(n,b)= D(n+1,b)
- D(n,b)$, then $(S,E)$ is a WZ pair, as defined in the HDCM \cite{HB}, p
209.
\item [2.]Theorem \ref{D=G} confirms in a new way the opinion of Mohanty \cite{Mohanty}, p 54,
 {\it ``... that paths with diagonal steps might ... be related to higher
 dimensional paths without diagonal steps''}.
 Note that we may swap dimension $d$ and distance $n$, because
 $G_d(n)=G_n(d)$.
 \item [3.]The author learned from Sulanke \cite{Sulanke}, that Theorem \ref{D=G} is
 also contained in the paper of Vassilev\&Atanassov \cite{vass}. Our
 proof is considerably shorter.
\end{description}
}
\end{rem}

\begin{lem}
Let $m,l \in \mathbb N,\, l \geq 1, n \geq ml.$ Then
\begin{equation} \label{recl}
\mbox{Schr}(n,m,l) - \mbox{S}_{m}(n+1) = \mbox{Schr}(n,m,l+1),
\end{equation} as long as the left side of Equ.\ref{recl} is not
negative.
\end{lem}

{\bf Proof:} by easy calculation with Theorem \ref{thco}. $\Box$

\begin{theo} Let $A_l(z) = GF((\mbox{Schr}(lm,m,l))_{m \in \mathbb N}).$
Then \[GF((\mbox{Schr}(n,m,l))_{n,m \in \mathbb N}) = \sum_{n,m \geq 0}
\mbox{Schr}(n,m,l)w^nz^m = \frac {A_l(w^lz)}{1-wA_l(w^lz)}\]
\label{GFSchr}
\end{theo}
{\bf Proof:} We know that $GF((\mbox{Schr}(lm+k,m,l))_{m \geq 0}) =
A_l^{k+1}(z)$ (cf. \cite{Sulanke3}), consequently
\[GF((\mbox{Schr}(lm+k,m,l))_{k,m \in \mathbb N}) = \sum_{k\geq 0}
A_l^{k+1}(z)w^k = A_l(z) \frac{1}{1 - wA_l(z)}\] The index shift $k
\rightarrow lm+k$ is achieved by the replacement $z \rightarrow
w^lz$. $\Box$

%REFERENCES

\begin{thebibliography}{99}

\bibitem{Aign} M. Aigner, {\it Diskrete Mathematik,} Vieweg, Braunschweig,
1993.

\bibitem{refl} D. Andr\'{e}, {\rm Calcul des probabilit\'es. Solution directe du
probl\`eme r\'esolu par M. Bertrand,} {\it C. R. Math. Acad. Sci.
Paris,} {\bf 105} (1887), 436. \label{_refl}

\bibitem{why} C. Banderier and S. R. Schwer, {\rm Why Delannoy
numbers?} {\it J. Statist. Plann. Inference} {\bf 135} (2005),
40--54.  Electronic version available at
\href{http://arxiv.org/abs/math/0411128}{\tt http://arxiv.org/abs/math/0411128}.

\bibitem{class} J. Bertrand, {\rm Calcul des probabilit\'es. Solution d'un
probl\`eme,} {\it C. R. Math. Acad. Sci. Paris,} {\bf 105}
(1887), 369.  \label{_class}

\bibitem{Biz} M. T. L. Bizley, {\rm Derivation of a new formula for
the number of minimal lattice paths from ${(0,0)}$ to ${(k m, k n)}$
having just $t$ contacts with the line ${m y = n x}$ and having no
points above this line; and a proof of Grossman's formula for the
number of paths which may touch but do not rise above this line,}
{\it J. Inst. Actuaries} {\bf 80} (1954), 55--62.\label{_Biz}

\bibitem{solution} D. Callan,
{\rm Solution to Problem 10658,} {\it Amer. Math. Monthly}
{\bf 107} (2000), 368--371.
\label{_solution}

\bibitem{ConSlo} J. H. Conway and N. J. A. Sloane, 
{\rm Low
Dimensional Lattices VII: Coordination Sequences,} {\it Proc. Roy.
Soc. Lond. Ser. A Math. Phys. Eng. Sci.} {\bf 453} (1997),
2369--2389.  Electronic version available at
\href{http://citeseer.ist.psu.edu/article/conway96lowdimensional.html}{\tt 
http://citeseer.ist.psu.edu/article/conway96lowdimensional.html}.\label{_ConSlo}

\bibitem{dela} H. Delannoy, {\rm Emploi de l'\'echiquier pour la r\'esolution de
certains probl\`emes de probabilit\'es,} {\it Association Francaise
pour l'Avancement des Sciences}, Bordeaux 24 (1895), 70--90.
\label{_dela}

\bibitem{problem} E. Deutsch, {\rm Problem 10658,} {\it Amer. Math. Monthly}
{\bf 105} (1998), 366. \label{_problem}


\bibitem{DvoMotz}  A. Dvoretzky and T. Motzkin,
{\rm A problem of arrangements,}
{\it Duke Math. J.} {\bf 14} (1947), 305--313.\label{_DvoMotz}

\bibitem{GV} I. Gessel and G.
Viennot, {\rm Binomial determinants, paths, and hook length
formulae,} {\it Adv. Math.} {\bf 58} (1985), 300--321. \label{_GV}

\bibitem{GoodNara} E. Goodman and T. V. Narayana,
{\rm Lattice paths with diagonal
steps,} {\it Canad. Math. Bull.} {\bf 12} (1969), 847--855.
\label{_GoodNara}

\bibitem{GouSer} I. P. Goulden and L. G. Serrano,
{\rm Maintaining the spirit of
the reflection principle when the boundary has arbitrary integer
slope,} {\it J. Combin. Theory Ser. A} {\bf 104} (2003), 317--326.
\label{_GouSer}

\bibitem{Hetyei} G. Hetyei, {\rm Central Delannoy numbers
and balanced Cohen-Macaulay complexes,}
{\it Ann. Comb.} {\bf 10} (2006), 443--462. \label{_Hetyei}

\bibitem{Kratten} C. Krattenthaler, {\rm The enumeration of 
lattice paths with respect to their
number of turns,} in N. Balakrishnan, ed.,
{\it Advances in Combinatorial Methods and
Applications to Probability and Statistics}
Birkh\"auser, 1997, pp.\ 29--58. \label{_Kratten}

\bibitem{KrattSul} C. Krattenthaler and R. A. Sulanke,
{\rm Counting pairs of non-intersecting
lattice paths with respect to weighted turns,} {\it Discrete Math.}
{\bf 153} (1996), 189--198. \label{_KrattSul}

\bibitem{Krew1} G. Kreweras, {\rm Sur une classe de probl\`emes de d\'enombrement li\'es au
treillis des partitions de entiers,} Thesis, Universit\'{e} Paris,
1965 \label{_Krew1}

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

\bibitem{Mohanty} S. G. Mohanty, {\it Lattice Path Counting and Applications,}
Academic Press, 1979. \label{_Mohanty}

\bibitem{Moser} L. Moser, {\rm King paths on a
chessboard,} {\it Math. Gaz.} {\bf 39} (1955), 54.\label{_Moser}

\bibitem{aPS} E. Pergola and R. A. Sulanke, \href{http://www.cs.uwaterloo.ca/journals/JIS/PergolaSulanke/}{\rm
Schr\"oder triangles, paths, and parallelogram polyominoes}, {\it J.
Integer Seq.} {\bf 1} (1998), Article 98.1.7.\label{_aPS}

\bibitem{Ran} G. N. Raney,
{\rm Functional composition patterns and power series reversion,}
{\it Trans. Amer. Math. Soc.} {\bf 94} (1960), 441--451.\label{_Ran}

\bibitem{Rogers2} D. G. Rogers, {\rm A Schr\"oder triangle,} in
{\it Combinatorial Mathematics V: Proceedings of the Fifth Australian
Conference}, {\it Lecture Notes in Mathematics}  {\bf 622},
Springer-Verlag, 1977, pp.\ 175--196. \label{_Rogers2}

\bibitem{Rogers1}
D. G. Rogers, {\rm Pascal triangles, Catalan numbers and renewal
arrays,} {\it Discrete Math.} {\bf 22} (1978), 301--310.
\label{_Rogers1}

\bibitem{RS} D. G. Rogers and L. W. Shapiro, {\rm Some
correspondences involving the Schr\"oder numbers and relations,} in
{\it Comb. Math., Proc. of the Intern. Conf., Canberra 1977}, {\it Lecture
Notes in Mathematics} {\bf 686}, Springer-Verlag, 1978,
pp.\ 267--276. \label{_RS}

\bibitem{HB} K. H. Rosen et al., eds.,
{\it Handbook of Discrete and Combinatorial
Mathematics,}  CRC Press, 2000. \label{_HB}

\bibitem{schr} E. Schr\"oder, {\rm Vier combinatorische Probleme,} {\it
Z. Math. Phys.} {\bf 15} (1870), 361--376. \label{_schr}

\bibitem{fill} J. Schr\"oder, {\rm Filling boxes densely and
disjointly,} {\it Comment. Math. Univ. Carolin.} {\bf 44} (2003),
187--196.

\bibitem{online} N. J. A. Sloane, {\rm The On-Line Encyclopedia of Integer
Sequences,} 
\href{http://www.research.att.com/$\sim$njas/sequences/}{\tt http://www.research.att.com/$\sim$njas/sequences/}.
\label{online}

\bibitem{Stan1} R. P. Stanley, {\rm
Hipparchus, Plutarch, Schr\"oder and Hough,} {\it Amer. Math.
Monthly} {\bf 104} (1997), 344--350. \label{_Stan1}

\bibitem{Stan2}  R. P. Stanley, {\it Enumerative Combinatorics,} Vol.\ 2,
Cambridge University Press, Cambridge, 1999. \label{_Stan2}

\bibitem{Sulanke3} R. A. Sulanke,
{\rm A recurrence restricted by a diagonal condition:
generalized Catalan arrays,} {\it Fibonacci Quart.} {\bf 27} (1989),
33--46. \label{_Sulanke3}

\bibitem{Sulanke2} R. A. Sulanke, {\rm Problem 10894,} {\it
Amer. Math. Monthly} {\bf 108} (2001), 770. \label{_Sulanke2}


\bibitem{Sulanke} R. A. Sulanke, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Sulanke/delannoy.html}{\rm Objects counted by the central Delannoy
Numbers}, {\it J. Integer Seq.} {\bf 6} (2003), Article
03.1.5. \label{_Sulanke}

\bibitem{vass} M. Vassilev and K. Atanassov, {\rm On Delanoy [!] numbers,}
{\it Annuaire Univ. Sofia Fac. Math. Inform.} {\bf 81} (1987),
153--162. \label{_vass}

\bibitem{wilf} H. S. Wilf, {\it Generatingfunctionology,} Academic Press, 1994. \label{_wilf}

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
05A10; Secondary  05A15, 05A19.

\noindent \emph{Keywords: } Delannoy
numbers, Schr\"oder numbers, royal path, king path, point lattice,
integer slope, coordination sequence, crystal sphere, generating
function, recursion, rotation principle, WZ-pair, NE-turn, up-right
corner.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A006318},
\seqnum{A006319}, \seqnum{A006320}, \seqnum{A006321},
\seqnum{A027307}, \seqnum{A032349}, \seqnum{A033296},
\seqnum{A033877}, \seqnum{A035597}, \seqnum{A035598},
\seqnum{A035599}, \seqnum{A035600}, \seqnum{A035601},
\seqnum{A035602}, \seqnum{A035603}, \seqnum{A035604},
\seqnum{A035605}, \seqnum{A035606}, \seqnum{A035607}, and
\seqnum{A106579}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 8 2007;
revised version received May 8 2007; July 25 2007.
Published in {\it Journal of Integer Sequences}, July 25 2007.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                


