\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \usepackage{mathrsfs} \usepackage{color} \definecolor{lightgray}{rgb}{0.8, 0.8, 0.8} \definecolor{darkgray}{rgb}{0.7, 0.7, 0.7} \definecolor{darkblue}{rgb}{0, 0, .4} \newcommand{\note}[1]{ \marginpar{{\footnotesize\it #1\/}} } \newcommand{\case}[1]{ \bigskip\noindent\underline{\bf #1:} } \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf On Generalized Delannoy Numbers} \vskip 1cm \large Steven Edwards and William Griffiths \\ Department of Mathematics\\ Kennesaw State University\\ Marietta, GA 30060\\ USA\\ \href{mailto:sedwar77@kennesaw.edu}{\tt sedwar77@kennesaw.edu}\\ \href{mailto:wgriff17@kennesaw.edu}{\tt wgriff17@kennesaw.edu} \end{center} \vskip .2 in \begin{abstract} The Delannoy numbers and the figurate numbers for $n$-dimensional cross polytopes are doubly-recursive sequences that satisfy the same recursion, and indeed have similar formulae, differing by one parameter. Further varying that parameter, we discover an infinite collection of doubly recursive sequences that satisfy the same recursion. These sequences enumerate certain types of lattice paths using the steps $(1,0)$, $(0,1)$, and $(1,1)$ and certain types of words on three letters. We use these combinatorial interpretations to prove relationships among the sequences. \end{abstract} \section{Introduction} Henri-Auguste Delannoy came to mathematics after a career as a French military officer, eventually establishing a correspondence with Edouard Lucas and publishing recreational mathematics \cite {WhyDelannoy}. He is best known for his Delannoy numbers (see sequence \seqnum{A008288} in \cite{OEIS}), which count {\it queen's walks}: paths a queen can take from one square to another on a chessboard. The number of queen's walks from $(0,0)$ to $(m,n)$ is known as the Delannoy number $D(m,n)$. Equivalently, $D(m,n)$ counts the number of lattice paths using only the steps $(1,0)$, $(0,1)$, and $(1,1)$. His original results in the area of lattice paths \cite{Delannoy} were published in 1895. Through combinatorial proofs inspired by Delannoy's work, we generalize his results. Note first that any lattice path from $(0,0)$ to $(m,n)$ has three possible final steps: a horizontal step from $(m-1,n)$, a vertical step from $(m,n-1)$, or a diagonal step from $(m-1,n-1)$. The recurrence $D(m,n)=D(m-1,n)+D(m,n-1)+D(m-1,n-1)$ follows immediately. The standard formula, due to Delannoy, is $$D(m,n)=\sum_{j=0}^n {m+n-j \choose n}{n \choose j}.$$ We can verify the standard formula by letting $j$ count the number of diagonal steps. With $j$ diagonal steps to $(m,n)$, the path has $m+n-j$ total steps. Choose $n$ of the steps to have a vertical component (either $(0,1)$ or $(1,1)$) in ${m+n-j \choose n}$ ways. (The remaining $m-j$ steps are horizontal steps.) Choose $j$ of those $n$ steps with vertical component to be diagonal steps in ${n \choose j}$ ways. The remaining $n-j$ steps are vertical (0,1) steps. Sum through all values of $j$ to get the formula. Another array of numbers satisfying the same recursion as the Delannoy numbers is the cross polytope numbers (or the figurate numbers of the cross polytopes), usually denoted $T(m,n)$. A cross polytope is a type of regular, convex polytope \cite[\S 7.21, pp.\ 121--122]{Coxeter}. Kim \cite{K} constructed the cross polytope numbers. The standard formula for the cross polytope numbers is $T(m,n)=\sum_{j=0}^{m-1} {n+j \choose m}{m-1 \choose j}$; see \seqnum{A142978} in \cite{OEIS}. Edwards and Griffiths \cite{EdGriff} found two additional formulas for the cross polytope numbers, which are as follows: $$T(m,n)=\sum_{j=0}^{ \left \lfloor \frac n 2 \right \rfloor} {m+n-1-2j \choose n-1}{n \choose 2j}=\sum_{j=0}^{ \left \lfloor \frac { n-1} 2 \right \rfloor} {m+n-1-(2j+1) \choose n-1}{n \choose 2j+1}.$$ The cross polytope numbers are partial row sums of the Delannoy numbers (\seqnum{A142978} in \cite{OEIS}): $$\sum_{j=0}^{n-1}D(m,j)= T(m+1,n)$$. Also, adjacent cross polytope numbers sum to a Delannoy number: $T(m,n)+T(m,n+1)=D(m,n)$. We will give generalizations of these identities in section~\ref{section:relat}. Summing the two versions of $T(m,n)$ above gives $$T(m,n)= \frac{1}{2} \sum _{j=0}^n {m+n-1-j \choose n-1}{n \choose j},$$ which is tantalizingly similar to the formula for $D(m,n)$. Besides the factor of $\frac 1 2$, the other difference is the occurrences of $1$ in the first binomial coefficient. We generalize $T(m,n)$ by replacing the $1$'s by an arbitrary integer $k$. We define, for $m,n \geq k \geq 0$, $$D_k(m,n) = \sum _{j=0}^n {m+n-k-j \choose n-k}{n \choose j}.$$ While we could allow $k$ to be negative, it is more convenient to define, for $m, n, k \geq 0,$ $$D^k(m,n) = \sum _{j=0}^n {m+n+k-j \choose n+k}{n \choose j}.$$ We refer to both $D_k(m,n)$ and $D^k(m,n)$ as {\it generalized Delannoy numbers}. Note that $D_0(m,n)=D^0(m,n)=D(m,n)$. Furthermore, $T(m,n)= \frac 1 2 D_1(m,n)$. We also define, generalizing the formulas for $T(m,n)$ above: \begin{align*} E_k(m,n) &= \sum _{j=0}^{ \left \lfloor \frac n 2 \right \rfloor} {m+n-k-2j \choose n-k}{n \choose 2j} \\ O_k(m,n) &= \sum _{j=0}^{ \left \lfloor \frac { n-1} 2 \right \rfloor} {m+n-k-(2j+1) \choose n-k}{n \choose 2j+1}\\ E^k(m,n) &= \sum _{j=0}^{ \left \lfloor \frac n 2 \right \rfloor} {m+n+k-2j \choose n+k}{n \choose 2j} \\ O^k(m,n) &= \sum _{j=0}^{ \left \lfloor \frac { n-1} 2 \right \rfloor} {m+n+k-(2j+1) \choose n+k}{n \choose 2j+1}. \end{align*} Clearly $E_1(m,n)=O_1(m,n)=T(m,n)$. Some identities involving these numbers, including their recursion formulas, have been previously realized \cite{EdGriff2}. \section{Combinatorial interpretations} We next give applications of generalized Delannoy numbers to counting lattice paths. We first show that $D^k(m,n)$ counts the number of paths to $(m,n+k)$, but with a restriction on diagonal steps. In what follows, we will use, as convenient, $V$, $H$, and $D$ for vertical, horizontal, or diagonal steps in a lattice path. Also, we will use a step with {\it vertical component} to mean either $V$ or $D$. \begin{proposition} The number $D^k(m,n)$ counts the number of lattice paths from $(0,0)$ to $(m,n+k)$ with no diagonals allowed after the path reaches height $n$. \end{proposition} \begin{proof} As with $D(m,n)$, let $j$ be the number of diagonals in such a path. There are $m+(n+k)-j$ steps in the path. We choose $n+k$ steps to have a vertical component in ${m+n+k-j \choose n+k}$ ways, leaving $m-j$ steps to be $H$. Then, from the first $n$ steps with vertical component, we choose $j$ steps to be $D$ in ${n\choose j}$ ways. The remaining $m+k-j$ steps are $V$, including each of the last $k$ steps with vertical component. In this way, we obtain all paths to $(m,n+k)$ with no diagonals after reaching height $n$. \end{proof} There are multiple lattice path interpretations of $D_k(m,n)$. We begin with the lattice path interpretation most similar to the one above for $D^k(m,n)$. \begin{proposition} The number $D_k(m,n)$ counts the number of lattice paths from $(0,0)$ to $(m,n)$ with the following restriction: Each of the last $k$ horizontal steps is immediately followed by a step with vertical component. If there are fewer than $k$ horizontal steps, say $k-i$, $1\leq i\leq k$, then every horizontal step is followed by a step with vertical component, and the final $i+1$ steps of the path are steps with a vertical component. \end{proposition} \begin{proof} Again allowing $j$ to be the number of diagonals, there will be $m+n-j$ total steps in a path from $(0,0)$ to $(m,n)$ with $j$ diagonals. If such a path has $k$ or more horizontal steps, first choose $n-k$ steps to have vertical component in ${m+n-k-j \choose n-k}$ ways, leaving $m-j$ steps to be $H$. To such a path, add a step with vertical component after each of the last $k$ horizontal steps. If a path has $k-i$ horizontal steps, $1\leq i\leq k$, add a step with vertical component after each H, and the remaining $i$ steps with vertical component to the end of the path. Finally, from the now $n$ steps with vertical component, choose $j$ of them to be diagonal. If the path has $k-i$ horizontal steps, it follows that step $m+n-j-i$ must not be horizontal. Hence we obtain lattice paths to $(m,n)$ with either the last $k$ horizontal $(1,0)$ steps being followed by a step with vertical component, or all $k-i$ horizontal steps followed by a step with vertical component, and ending with $i+1$ steps with vertical component. \end{proof} The number $E_k(m,n)$ as defined above is the number of paths as described for $D_k(m,n)$, with an even number of diagonals, and $O_k(m,n)$ those with an odd number of diagonals. The numbers $E^k(m,n)$ and $O^k(m,n)$ are interpreted similarly. It is useful to provide an alternate combinatorial interpretation for these number collections, inspired by Delannoy's original work in interpreting his queen's walks as words in the letters $D$, $H$, and $V$. \section{The word interpretation} The number $D_k(m,n)$ can be also be interpreted as the number of words of length $m+n-k$ using the letters $\{D, H, V\}$, with the property that there are $n-k$ occurrences of $V$, and $D$ can only appear in the first $n$ letters. Certainly there are $D_k(m,n) = \sum _{j=0}^n {m+n-k-j \choose n-k}{n \choose j}$ such words: choose $j$ of the first $n$ letters to be $D$, and then from the remaining $m+n-k-j$ letters, choose $n-k$ to be $V$, with the remainder $H$. Then $E_k(m,n)$ and $O_k(m,n)$ are the numbers of such words with an even or odd number of occurrences of $D$, respectively. Similarly, we can interpret $D^k(m,n)$ as the number of words of length $m+n+k$ with $n+k$ occurrences of $V,$ and with $D$ appearing only in the first $n$ letters. Note that the word interpretation is distinct from the path interpretation. For example, each word has the same length ($m+n-k$ or $m+n+k$), but the paths have varying numbers of steps ( $m+n-j$ or $m+n+k-j$, where $j$ is the number of diagonal steps). The following three theorems use the word interpretations for generalized Delannoy numbers, beginning by showing that $E_k(m,n)$ and $O_k(m,n)$ are each exactly half of $D_k(m,n)$. \begin{proposition}\label{half} For all integers $m,n\geq k\geq 1$ we have $E_k(m,n)=O_k(m,n)=\frac{1}{2}D_k(m,n)$. \end{proposition} \begin{proof} Begin with a word from the set enumerated by $E_k(m,n)$. Since there are fewer than $n$ occurrences of $V$, one of the first $n$ letters must be a $D$ or an $H$. Toggling the first such $D$ to $H$ or $H$ to $D$, we now have a word with an odd number of $D$'s. The toggle creates a bijection between the set of words enumerated by $E_k(m,n)$ and the set of words enumerated by $O_k(m,n)$. \end{proof} The numbers $E^k(m,n)$ and $O^k(m,n)$ are not equal, but differ by a binomial coefficient. \begin{proposition} For all integers $m,n\geq k \geq 0$ we have $E^k(m,n)=O^k(m,n)+{m+k \choose k}$. \end{proposition} \begin{proof} For any word in the set enumerated by $E^k(m,n)$, if there is a non-$V$ letter in the first $n$ letters, toggle that letter from $H$ to $D$ or $D$ to $H$. The resulting word belongs to the set enumerated by $O^k(m,n)$. The mapping described by this toggling is easily reversible. Thus, for words where the first $n$ letters are not all $V$, the number of words with an even number of $D$'s is the same as the number of words with an odd number of $D$'s. The $E^k(m,n)$ also count words which have $V$ for the first $n$ letters, and hence no occurrences of $D$. Such a word would have $k$ more occurrences of $V$ in the final $m+k$ letters, so there are ${m+k \choose k}$ such words. \end{proof} As a consequence of interest, note that $E^0(m,n)=O^0(m,n)+1$. As $D^0(m,n)=E^0(m,n)+O^0(m,n)$, every Delannoy number is odd. The proposition also shows that, to any given point, the number of lattice paths with an even number of diagonals is always one more than the number of paths with an odd number of diagonals. We now proceed to prove the recurrence for $D_k(m,n)$. By Proposition~\ref{half}, $D$ can be replaced by $E$ or $O$ in the following: \begin{theorem}\label{wordthree} For all integers $m,n > k \geq 0$ we have $$D_k(m,n)=D_k(m-1,n)+D_k(m,n-1)+D_k(m-1,n-1).$$ \end{theorem} \begin{proof} We consider words counted by $D_k(m,n)$ as being of four types which can be denoted $XXH$, $VXX$, $HXV$, $DXV$. The first two types have words in common. We consider each type in turn. In the first type, the last letter is $H$, leaving $m-1$ additional $H$'s. The number of potential $D$'s is still $n$, and there are still $n-k$ $V$'s, which makes $D_k(m-1,n)$ words with the last letter $H$. For the second type, the first letter is $V$. Then $(n-1)-k$ more $V$'s are needed, and the first $V$ means only $n-1$ $D$'s are possible. Discounting the first V, the remaining word has length $m+(n-1)-k$. So there are $D_k(m,n-1)$ words with first letter $V$. The first two terms have counted words where the first letter is $V$ and the last letter is $H$ twice, but the number of such words is exactly the same as the number with the first letter $H$ and the last letter $V$. Thus the first two terms on the right count the first three types of words. Finally, when the first letter is $D$ and the last is $V$, $m+n-k-2$ letters remain, and of these $n-1$ may be $D$. There are $D_k(m-1,n-1)$ such words. \end{proof} While we can use a similar argument to prove the same recurrence for $D^k(m,n)$, we prefer to describe a bijection between the set of words enumerated by $D^k(m,n)$ and the set of lattice paths enumerated by $D^k(m,n)$: given a word of length $m+n+k$ with $n+k$ occurrences of $V$ and $D$ appearing only in the first $n$ letters, create a lattice path to $(m,n+k)$ by reading the word from left to right, with an $H$ contributing a $(1,0)$ step and a $V$ contributing a $(1,1)$ step if it is the $i$th $V$ and the $i$th letter of the word is $D$ and a $(0,1)$ step otherwise. In this way, we will obtain all lattice paths to $(m,n+k)$ which have no diagonals after the path reaches a height of $n$. We end this section by using the lattice path interpretation to prove the recurrence for $D^k(m,n)$. \begin{theorem} For all integers $m, n, k$, with $m,n >0, k \geq 0$ we have $$D^k(m,n)=D^k(m-1,n)+D^k(m,n-1)+D^k(m-1,n-1).$$ \end{theorem} \begin{proof} The terms on the RHS count, in turn, paths that begin with a horizontal step, a vertical step, and a diagonal step. \end{proof} \begin{center} \begin{table}[ht] \centering \begin{tabular}{ll} \begin{tabular}{c|c c c c c c c c } $D_0$ &0&1 & 2 & 3&4&5\\ \hline 0&$ { 0 \choose 0} $& ${ 1 \choose 1 }$ & ${ 2 \choose 2}$& $ { 3 \choose 3 }$& $ { 4 \choose4 }$& $ {5\choose 5 }$\\ 1 &1&3&5&7&9&11&\\ 2&1&5&13&25&41&61&\\ 3&1&7&25&63&129&231&\\ 4&1&9&41&129&321&681&\\ 5&1&11&61&231&681&1683\\ \end{tabular} \quad \begin{tabular}{c|c c c c c c c c c c c } $\frac 1 2 D_1$ &1 & 2 & 3&4&5&6\\ \hline 1 & ${1 \choose 1}$ &${2 \choose 1}$ &${3 \choose 1}$& ${4 \choose 1}$ & $ {5 \choose 1}$ &$ {6 \choose 1}$ \\ 2&1&4&9&16&25&36\\ 3&1&6&19&44&85&146\\ 4&1&8&33&96&225&456\\ 5&1&10&51&180&501&1182\\ 6&1&12&73&304&985&2668\\ \end{tabular}\\ \\ \begin{tabular}{c|c c c c c c c c } $\frac 1 {2^2} D_2$ & 2 & 3&4&5&6&7\\ \hline 2&${2 \choose 2}$&${3 \choose 2}$ & ${4 \choose 2}$ & ${5 \choose 2}$ & ${6 \choose 2}$& ${7 \choose 2}$\\ 3&1 & 5 & 14 & 30 & 55 & 91 \\ 4&1& 7&26&70&155&301\\ 5&1&9&42&138&363&819\\ 6&1&11&62&242&743&1925\\ 7&1& 13&86&390&1375&4043\\ \end{tabular} \quad \begin{tabular}{c|c c c c c c c c c c c} $\frac 1 {2^3} D_3$ & 3&4&5&6&7&8\\ \hline 3&${3 \choose 3}$ &${4 \choose 3}$ &${5 \choose 3}$ &${6 \choose 3}$ &${7 \choose 3}$ &${8 \choose 3}$ \\ 4&1&6&20&50&105&196\\ 5&1&8&34&104&259&560\\ 6&1& 10&52&190&553&1372\\ 7&1&12 & 74&316&1059&2984 \\ 8&1&14&100&490&1865&5908 \\ \end{tabular} \end{tabular} \caption{Values of $D_0$, $D_1$, $D_2$, $D_3$. Rows correspond to $m$ is row and columns to $n$.} \end{table} \end{center} \section{The central theorem} We turn our attention to relationships among these numbers. Note that $D_1(m,n)$ is even, $D_2(m,n)$ is divisible by 4, $D_3(m,n)$ is divisible by 8, and so on. We will see that by dividing $D_k$ by $2^k$, we obtain the collection $D^k$, albeit with a shift. We begin with a lemma \cite[5.28, p.\ 171]{Concrete}, one of the few identities known for a product of two binomial coefficients. A combinatorial/probabilistic proof of the lemma is known \cite{Andrews}. We find it likely there is an easier proof of the lemma using lattice paths, but have not yet found one. \begin{lemma}\label{form} $ {a \choose b} { c \choose d} = \sum_{j=0}^{a+d-c } {a+d-j \choose a+d-b} { a+d-c \choose j } {c-b \choose d-j}.$ \end{lemma} We use Lemma~\ref{form} for a simple proof of the central theorem relating $D_k(m,n)$ and $D^k(m,n)$. As a consequence, we get a second lattice path interpretation of $D_k(m,n)$. \begin{theorem}[The central theorem] For all $m$, $n$, and $k$ positive integers, we have $$ D^k(m,n) =\frac 1 {2^k} D_k (n+k,m+k) .$$ \end{theorem} \begin{proof} We have, using the lemma, \begin{align*} D_k(n+k,m+k) &= \sum _{i=0} ^{m+k} {m+n+k-i \choose m}{m+k \choose i} \\ &= \sum _{i=0} ^{m+k} \sum _{j=0} ^n {m+n+k-j \choose n+k }{n \choose j} {k \choose i-j} \\ &= \sum _{j=0} ^n {m+n+k-j \choose n+k}{n \choose j} \sum _{i=0} ^{m+k}{k \choose i-j} \\ &= \sum _{j=0} ^n {m+n+k-j \choose n+k}{n \choose j} \sum _{s=0} ^{k}{k \choose s} \\ &= 2^k D^k(m,n). \end{align*} \end{proof} \begin{corollary} The number $D_k(m,n)$ is divisible by $2^k.$ \end{corollary} Consider now the terms of the proof. These terms have a natural interpretation as certain words in the letters $H$, $D$, and $V$, and in lattice paths corresponding to these words. We let $ {m+n+k-j \choose n+k} = {m+n+k-j \choose m-j} $ count words with $m+n+k-j$ letters, of which $m-j$ are $H$. Let ${n \choose j}$ choose $j$ from the first $n$ non-$H$ letters to be $D$. If we let the remaining $n+k-j$ letters be $V$, we have $D^k(m,n)$. But now let ${k \choose i-j}$ choose $i-j$ of the last $k$ $V$'s and change them to $D$. The remaining last $k-(i-j)$ V's are changed to $VH$. Thus, while $D^k(m,n)$ counts paths to $(m, n+k)$ with no diagonal above $n$, the number $D_k(n+k,m+k)$ counts paths to $(m+k,n+k)$ where each of the last $k$ steps with vertical component is either a $V$ followed by an $H$, or a $D$. More directly, the number $D_k(m,n)$ counts paths to $(n,m)$ where the last $k$ ``steps" with vertical component are either $VH$ or $D$. Because of this second interpretation of $D_k$, in what follows, for convenience we will speak of paths with ``step" $VH$, although of course $VH$ is two steps in the path. The second line of the proof also gives a natural correspondence between a path to $(m,n+k)$ counted by $D^k(m,n)$ and the corresponding $2^k$ paths to $(m+k,n+k)$ counted by $D_k(n+k,m+k)$. Given such a path to $(m,n+k)$, after reaching a height of $n$, there are $k$ more $V$'s. Paths to $(m+k,n+k)$ can be obtained by altering the last $k$ $V$'s in two ways: either by changing a $V$ to a $D$, or by inserting an $H$ after a $V$. The $ {k \choose i-j}$ term counts the number of $V$'s changed to $D$ (versus inserting an $H$). The number of $V$'s changed to $D$ could be between 0 and $k$. In all, there are $2^k$ choices, and so $2^k$ times as many paths. \section{Relationships among generalized Delannoy numbers} \label{section:relat} A consequence of the central theorem is that every result about $D_k(m,n)$ has a corresponding result for $D^k(n-k,m-k)$. We focus on $D_k(m,n)$, bearing in mind corresponding results about $D^k$. Our second interpretation of $D_k(m,n)$ is that it counts paths to $(n,m)$ with the last $k$ vertical steps either $D$ or $VH$. We use this interpretation to prove results in this section, including a simpler proof of Theorem~\ref{wordthree}, the recurrence for $D_k(m,n)$: For $m,n>k\geq 0$ we have $D_k(m,n) = D_k(m-1,n) + D_k(m,n-1) + D_k(m-1,n-1).$ \begin{proof} Each path to $(n,m)$ must start with $H$, $V$, or $D$. As $m>k$, the first step is not one of the last $k$ vertical steps. Hence removing the first step results in paths counted by the three expressions on the right. \end{proof} The ``first'' row of $\frac 1 {2^k} {D_k(m,n)}$ consists of binomial coefficients. Row $D_k(k,n)$ is the first which has an interpretation as counting lattice paths. Higher rows ($D_k(m,n)$ with $mk\geq 0$ we have $$D_k(m,n)-D_k(m-1,n) = D_{k+1}(m,n).$$ \end{theorem} \begin{proof} The numbers $D_k(m,n)$ and $D_{k+1}(m,n)$ count paths to $(n,m)$ with the last $k$ or $k+1$ vertical steps, respectively, either $D$ or $VH$. Thus $D_k(m,n) - D_{k+1}(m,n)$ counts paths to $(n,m)$ with the last $k$ verticals $D$ or $VH$, but at height $m-(k+1)$ there must be a $V$ not followed by $H$. Remove this $V$ to get a path to $(n,m-1)$ with the last $k$ verticals $D$ or $VH$, counted by $D_k (m-1,n).$ This process is reversible, which shows that $D_k(m,n)- D_{k+1}(m,n) = D_k(m-1,n)$, or $D_k(m,n)- D_k(m-1,n) = D_{k+1}(m,n).$ \end{proof} The preceding two theorems give the following theorem. \begin{theorem}[horizontal sum] For $m,n>k\geq 1$ we have $$D_k(m,n) + D_k(m,n-1) =2 D_{k-1}(m,n-1).$$ \end{theorem} \begin{proof} $D_k(m,n) + D_k(m,n-1) = (2D_{k-1}(m-1, n-1) + D_k(m,n-1)) + D_k(m,n-1) $ by the horizontal difference theorem. Now use the vertical difference theorem to get $$2(D_{k-1}(m-1, n-1) + D_k(m,n-1)) = 2 D_{k-1}(m,n-1).$$ \end{proof} The horizontal sum theorem is a generalization of the fact that the sum of two adjacent cross polytope numbers is a Delannoy number. \begin{theorem}[vertical sum] For $m , n \geq k \geq 0$ we have $$D_k(m,n) + D_k(m-1,n) = D_{k+1}(m,n+1).$$ \end{theorem} \begin{proof} If we add the formulas for horizontal difference and horizontal sum, we have $$D_{k-1}(m,n-1)+D_{k-1}(m-1,n-1)=D_k(m,n).$$ Re-indexing gives the result. \end{proof} The preceding four theorems are, in turn, special cases of the following four identities. Each of these four identities can be proved by induction, using the theorems above as base case. \begin{theorem} \begin{align*} 2^r D_k(m,n) &= \sum _{i=0}^r (-1)^{r+i} {r \choose i} D_{k+r}(m+r, n+i) \\ D_k(m,n) &= \sum _{i=0}^r(-1)^i {r \choose i} D_{k-r}(m-i, n) \\ 2^r D_k(m,n) &= \sum _{i=0}^r {r \choose i} D_{k+r}(m, n+i) \\ D_k(m,n) &= \sum _{i=0}^r {r \choose i} D_{k-r}(m-i, n-r). \end{align*} \end{theorem} It is not hard to see, looking at tables for $D_k(m,n)$, that twice the sum of the first row entries of $D_k$ is equal to an entry in $D_{k+1}$, e.g., $2(D_2(4,2) + D_2(4,3) + D_2 (4,4)) = D_3(5,5)$. This is a particular instance of a more general theorem, which breaks down paths to $(n,m$) counted by $D_k(m,n)$ into subcollections determined by the rightmost point at which the paths are at various heights. \begin{theorem} For $j=1, \ldots, k$ we have $D_k(m,n) =2^j \sum_{i=0}^{n-k} {j+i-1 \choose i} D_{k-j} (m-j, n-j-i).$ \end{theorem} \begin{proof} Fix $m$, $n$, $k$, $j$. For $i= 0, 1, \dots n-k$, the expression $ D_{k-j} (m-j, n-j-i)$ counts paths to $(n-j-i,m-j)$ such that the last $k-j$ steps with vertical component are either $D$ or $VH$, while $D_k(m,n)$ counts paths to $(n,m)$ with the last such $k$ $D$ or $VH$. Paths from $(n-j-i,m-j)$ to $(n,m)$ are equivalent to those from $(0,0)$ to $(j+i,j)$. Now given a path whose rightmost position at height $m-j$ is at the point $(n-j-i,m-j)$, the path can be extended to a desired path to $(n,m)$ by adding $j$ ``steps" of either $D$ or $VH$, plus $i$ steps that are $H$. Now the first added step cannot be $H$, because this violates the rightmost condition. This leaves $j+i-1$ steps, of which $i$ are $H$, and the rest either $D$ or $VH$. Thus there are ${j+i-1 \choose i}$ ways to choose which steps are $H$, and $2^j$ choices of either $D$ or $VH$ for the $j$ diagonal steps. \end{proof} From the proof, we see that the expression $2^j \sum_{i=0}^{n-k} {j+i-1 \choose i} D_{k-j} (m-j, n-j-i)$ gives an account of paths at height $m-j$ that reach $(n,m)$, namely that there are $2^j {j+i-1 \choose i} D_{k-j} (m-j, n-j-i)$ such paths, requiring still that the point $(n-j-i,m-j)$ is the rightmost point of the path at height $m-j$. This theorem generalizes the fact that partial row sums of Delannoy numbers give a cross polytope number. The case $j=1$ gives the result about sums of the first entries in a row: \begin{corollary} For $k \geq 1$ we have $$D_k(m,n) = 2 \left( D_{k-1}(m-1,n-1)+D_{k-1}(m-1,n-2)+ \cdots +D_{k-1}(m-1,k-1)\right ).$$ \end{corollary} The case $j=k$ gives every generalized Delannoy number directly in terms of traditional Delannoy numbers, and we see again that $D_k(m,n)$ must be divisible by $2^k$: \begin{corollary} For $k\geq 1$ we have \begin{equation*}D_k(m,n)=2^k \sum_{j=0}^{n-k} {k-1+j \choose j}D_0(m-k,n-k-j).\end{equation*} \end{corollary} The next theorem groups the paths counted by $D_k(m,n)$ according to the highest diagonal below $m-k$. \begin{theorem} $D_k(m,n) = \frac 1 {2^m}D_m(m,n+m-k)+ \sum_{j=1}^{m-k}\frac 1 {2^j} D_{k+j}(m, n+j-1) . $ \end{theorem} \begin{proof} For $j = 1, 2, \dots m-k$, we have the following $2^j$ to one mappings from lattice paths counted by $D_{k+j}(m,n+j-1)$ to those counted by $D_k(m,n)$. Denote by $\mathscr{D}$ a part of a lattice path that is either a $D$ or a $VH$. Then a path counted by $D_{k+j}(m,n+j-1))$ has its last $k+j$ verticals steps as $\mathscr{D}$. Leave the last $k$ $\mathscr{D}$'s alone, and but for the remaining $j$ $\mathscr{D}$'s change the first to $D$, and change the next $j-1$ to V. Then $2^j$ paths from $D_{k+j}(m,n+(j-1))$ map to the same path, which is counted by $D_k(m,n)$, since the $j-1$ $\mathscr{D}$'s which are changed to $V$ move the end of the path horizontally from $(n+(j-1),m)$ to $(n,m)$. For different values of $j$, the paths obtained from $D_{k+j}(m,n+j-1)$ are distinct, since, for each $j$, the highest diagonal below the height of $m-k$ is at the height $m-(k+j)$. For $D_m(m,n+m-k)$, map each of the first $m-k$ $\mathscr{D}$'s to $V$, giving the paths from $D_k(m,n)$ with no diagonals below the height of $m-k$. \end{proof} As a consequence of the theorem, we get a new interpretation: for $i = 1, \dots, m-k$, the expression $ \frac 1 {2^i} D_k(m,n)$ counts paths to $(n-i+1,m$) with the last $k-i$ vertical steps D or VH, and the highest diagonal below height $m-(k-i)$ is at height $m-k$. \section{Summary and conclusions} Our applications of generalized Delannoy numbers to lattice paths involve paths where the last $k$ vertical steps have a certain form. We note that in each of these interpretations, {\it last $k$} can be replaced by {\it specified $k$} to give further interpretations. Also, paths can be reflected through $y=x$ and $V$ and $H$ swapped for further applications. Using such a reflection, we can therefore express $D_k(m,n)$ as lattice paths from $(0,0)$ to $(m,n)$ such that the last $k$ steps with horizontal component are either $D$ or $HV$. We also note that most of our results can be stated in terms of a binomial identity. For example, the central theorem could be restated as $$2^c \sum _{j=0}^b {a-j \choose b+c} {b \choose j} = \sum_{j=0}^{a-b} { a-j \choose a-(b+c)} {a-b \choose j}.$$ There are as many directions to proceed from here as sequences in this collection. The generalized Delannoy numbers include many known number sequences \cite{OEIS}. Identities from this paper can be applied to these integer sequences, providing an underlying, unifying theory. Examples of such sequences follow. These examples illustrate the appearance of generalized Delannoy numbers in a variety of fields such as physics, graph theory, geometry, and permutation pattern avoidance. These examples are primarily columns in the $D_k(m,n)$ tables, which, due to the central theorem, are also rows of the $D^k(m,n)$ tables. $\frac{1}{2}D_1(m,3)$, or \seqnum{A058331} in the {\it On-Line Encyclopedia of Integer Sequences} (OEIS) gives the maximal number of regions in the plane that can be formed with $n$ hyperbolae. This sequence also finds the number of different determinants obtainable in all $2\times 2$ matrices with integer entries from 0 to $n$. $\frac{1}{4}D_2(m,4)$, or \seqnum{A051890} in the OEIS, gives the number of regions into which the plane is divided when n ellipses are drawn in the plane, with any two meeting in 4 points. This sequence also shows numerical differences between filled spin-split suborbitals sharing all quantum numbers except the principal quantum number n, for neutron shell filling in spherical atomic nuclei. $\frac{1}{4}D_2(m,5)$, or \seqnum{A034827} in the OEIS, is the number of pairs of non-intersecting lines when each of $n$ points around a circle is joined to every other point by straight lines. It also gives the orchard crossing number of the complete graph $K_n$. $\frac{1}{8}D_3(m,5)$, or \seqnum{A005893} in the OEIS, is the sum of 4 consecutive triangular numbers. It is also the number of $n$-matchings of the wheel graph $W_{2n}$. $\frac{1}{16}D_4(m,6)$, or \seqnum{A097080} in the OEIS, is the sum of the pairwise averages of five consecutive triangular numbers. Their doubles are the curvatures of the touching circle of the large semicircle and the $n$th and $(n-1)$st circles of the Pappus chain of the symmetric arbelos. $\frac{1}{32}D_5(m,7)$, or \seqnum{A093328} in the OEIS, is the number of 132-avoiding two-stack sortable permutations which also avoid 4321. It has been conjectured that this sequence contains no perfect powers. $D^3(m,1)=\frac{1}{8}D_3(4,m+3)$, or \seqnum{A002415} in the OEIS, is the 4-dimensional pyramidal numbers. It is the number of ways to legally insert two pairs of parentheses into a string of length $m+1$. It is also the number of permutations with exactly 2 descents that avoid the pattern 132. Many of the identities for the generalized Delannoy numbers provide a common structure to the varying objects enumerated here. Other identities will find relationships and suggest bijections among these objects. In this unifying theory, a relationship between the number of $n$-matchings of the wheel graph and the orchard crossing number of $K_n$ is revealed to a graph theorist while a geometer may be fascinated by the same connection between pairs of non-intersecting lines around a circle being connected to the maximal number of regions formed by hyperbolae. As everything we learn about these families of sequences has interesting applications, this is a rich area for further study. \section{Acknowledgment} The authors wish to thank the referee for helpful suggestions and comments which have improved the content of this paper. \begin{thebibliography}{9} \bibitem{Andrews} George E. Andrews, Identities in combinatorics, I: on sorting two ordered sets, {\it Discrete Math.} \textbf{11} (1975), 97--106. \bibitem{WhyDelannoy} Cyril Banderier and Sylviane Schwer, Why Delannoy numbers?, {\it J. Statist. Plann. Inference} \textbf{135} (2005), 40--54. \bibitem{Coxeter} H. S. M. Coxeter, {\it Regular Polytopes}, Dover Publications, 1973. \bibitem{Delannoy} H. Delannoy, Emploi de l'\'echiquier pour la r\'esolution de divers probl\`emes de probabilit\'e, {\it Assoc. Franc. Bordeaux} \textbf{24} (1895), 70--90. \bibitem {Concrete} R. L. Graham, D. E. Knuth, and O. Patashnik, {\it Concrete Mathematics}, 2nd edition, Addison-Wesley, 1998. \bibitem{EdGriff} Steven Edwards and William Griffiths, A binomial identity related to cross polytope numbers, {\it Fibonacci Quart.} \textbf{54} (2016), 253--256. \bibitem{EdGriff2} Steven Edwards and William Griffiths, Generalizations of Delannoy and cross polytope numbers, {\it Fibonacci Quart.} \textbf{55} (2017), 357--366. \bibitem{K} Hyun Kwang Kim, On regular polytope numbers, {\it Proc. Amer. Math. Soc.} \textbf{131} (2003), 65--75. \bibitem{OEIS} N. J. A. Sloane et al., {\it The On-line Encyclopedia of Integer Sequences}, 2020. Available at \url{https://oeis.org}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\em Mathematics Subject Classification}: Primary 05A19; Secondary 01A10, 11B37, 11B75. \noindent{\em Keywords}: Delannoy number, lattice path, recursion, binomial sum, cross polytope. \bigskip \hrule \bigskip \noindent(Concerned with sequences \seqnum{A002415}, \seqnum{A005893}, \seqnum{A008288}, \seqnum{A034827}, \seqnum{A051890}, \seqnum{A058331}, \seqnum{A093328}, \seqnum{A097080}, and \seqnum{A142978}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received October 30 2019; revised version received March 16 2020. Published in {\it Journal of Integer Sequences}, March 17 2020. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}