\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://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#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}