\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{mathrsfs}

\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}
\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}{\rm \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 Delannoy Constructions} 
\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 satisfy a recurrence in two variables and have been used to count lattice paths.  
We examine related arrays, the generalized Delannoy numbers.
We extend properties of the Delannoy numbers to these arrays using combinatorial methods associating these numbers with lattice paths.  
We generalize these results to any
array that satisfies the Delannoy recurrence.
\end{abstract}

\section{Introduction}

Henri Auguste Delannoy (1833--1915) was a French army officer and later an amateur mathematician, historian, and painter.  Correspondence with \'Edouard  Lucas led to eleven articles on recreational mathematics and probability theory.  Delannoy's work faded for a while into relative obscurity until more recent discoveries of applications of the numbers he discovered \cite{WhyDelannoy}.  These \emph{Delannoy numbers} count the number of {\it queen's walks}, paths a queen can take from one square to another on a chessboard, moving only right, up, or diagonally up to the right.  In the Cartesian plane, the number of queen's walks from $(0,0)$ to $(m,n)$ is known as the Delannoy number $D(m,n)$.  Equivalently, the number  $D(m,n)$ counts how many lattice paths go from (0,0) to $(m,n),$ using only the steps (0,1), (1,0), and (1,1), which we also denote, respectively, $H,$ $V,$ and $D$.  Delannoy's original results   \cite{Delannoy} in the area of lattice paths were published in 1895.

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 {\it Delannoy recurrenc}e $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 given by
$$D(m,n)=\sum_{j=0}^n {m+n-j \choose n}{n \choose j}.$$  

The authors introduced \cite{EdGriff2} the generalized Delannoy numbers by adding a parameter to the standard formula above.  Combinatorial interpretations were introduced, including counting certain lattice paths and counting certain types of words on three letters.  The \emph{generalized Delannoy numbers} are defined, for $m,n \geq k \geq 0$, by
$$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, $ by $$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 generalized Delannoy numbers. Obviously, we have $D(m,n) = D_0(m,n) = D^0(m,n)$.  The authors proved a ``central theorem''  \cite{EdGriff3} which relates these two types:
$$D_k(m,n)=2^kD^k(n-k,m-k).$$

Consequently, $D_k(m,n)$ is divisible by $2^k$.  In addition, a number of ``relationship'' theorems amongst the generalized Delannoy numbers were proved.  

Both $D_k(m,n)$ and $D^k(m,n)$ satisfy the Delannoy recurrence: $$D_k(m,n)=D_k(m-1,n)+D_k(m,n-1)+D_k(m-1,n-1)$$ and $$D^k(m,n)=D^k(m-1,n)+D^k(m,n-1)+D^k(m-1,n-1).$$

In this paper, we catalogue various lattice path interpretations, some known, some new, of the generalized Delannoy numbers.  Using these interpretations, we provide new proofs of some ``relationship" theorems, and we provide alternate formulas for the generalized Delannoy numbers.  Finally, we extend results about the generalized Delannoy numbers to all arrays that satisfy the Delannoy recurrence.

For reference we provide some tables of generalized Delannoy numbers $D^k(m,n)$ below.  
\renewcommand*\arraystretch{1.3}
\begin{table}   [ht]
\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 \choose 0}$&3&5&7&9&11\\  
   2&$ { 2 \choose 0}$&5&13&25&41&61\\ 
   3&$ { 3 \choose 0}$&7&25&63&129&231\\
   4&$ { 4 \choose 0}$&9&41&129&321&681\\
   5&$ { 5 \choose 0}$&11&61&231&681&1683\\
   \\
  \end{tabular} 
\quad\quad\quad
 \begin{tabular}{c|c c c c c c c c c}
    $D^1$&0 &1  & 2 & 3&4&5\\
    \hline 
0 &      $ { 1 \choose  1}  $&   $ {2  \choose 2 }  $&   $ { 3 \choose 3 }  $&   $ {4  \choose 4 }  $&   $ { 5 \choose 5 }  $&   $ {6  \choose  6}  $\\
   1 &  ${ 2 \choose 1}$  & 4&6&8&10&12\\  
   2&${ 3 \choose 1}$  &  9&19&33&51&73\\ 
   3&${ 4 \choose 1}$  & 16&44&96&180&304\\
   4&${ 5 \choose 1}$  & 25&85&225&501&985\\
   5&${ 6 \choose 1}$  & 36&146&456&1182&2668\\
   \\
  \end{tabular} \\
\ \\
 \begin{tabular}{c|c c c c c c c c c c c }
    $D^2$&0  &1&2&3& 4&5\\
    \hline 
0 &  ${ 2 \choose  2}$& $ { 3 \choose 3 }$& $ { 4 \choose4  }$& $ {5\choose 5 }$& ${6 \choose 6}$ & ${ 7 \choose 7}$ \\
1&${ 3 \choose 2}$ & 5 & 7 & 9 & 11 & 13\\
   2&   ${ 4 \choose 2}$  & 14&26&42&62&86\\ 
   3&    ${ 5 \choose 2}$  & 30 & 70 & 138 & 242& 390\\
   4&     ${ 6 \choose 2}$  &55&155&363 & 743 & 1375\\
   5&    ${ 7 \choose 2}$ & 91&301&819 & 1925 & 4043\\ 
  \end{tabular}
\quad\quad
 \begin{tabular}{c|c c c c c c c c c c c }
    $D^3$ &0 &1&2&3&4&5 \\
    \hline 
0 &  $ { 3 \choose3  }$ & $ {4\choose 4 }$& $ {5\choose 5 }$& ${6 \choose 6}$ & ${ 7 \choose 7}$ & ${ 8 \choose 8 }$&\\
1& ${4 \choose 3 }$& 6&8&10&12&14\\
   2& ${5 \choose 3}$ & 20 & 34 & 52 & 74& 100\\ 
   3& ${ 6 \choose 3}$ & 50 & 104 & 190&316&490\\
   4&${ 7 \choose 3}$ & 105 &259& 553 & 1059 & 1865\\
   5& ${ 8 \choose 3}$  &196 & 560 & 172 & 2984 & 5908\\
  \end{tabular}\\
  \end{tabular}  
  \caption{Values of $D^0,$ $D^1,$ $D^2,$ $D^3.$ We use $m$ to count rows, $n$ to count columns. }
\end{table}

\renewcommand*\arraystretch{1.0}

\section{Interpretations of generalized Delannoy numbers}

The lattice path interpretation of the Delannoy numbers inspires a number of interpretations for the generalized Delannoy numbers.  These interpretations occur in pairs which arise from reflecting a path about the line $y=x$.

\begin{theorem} \label{Theorem 2.1} For $k \geq 0$, the number $D^k(m,n)$ counts paths from (0,0) to
\begin{itemize}
\item  $(m,n+k)$ with no diagonals above height $n$
\item  $(n+k,m)$ with no diagonals past $x=n$
\item  $(m+1,n+k)$ with highest diagonal at height $n$
\item  $(n+k,m+1)$ with rightmost diagonal at $x=n$
\item  $(m,n+k)$ where there are $n$ or fewer diagonals, allowed only at $n$ specified heights
\item  $(n+k,m)$ where there are $n$ or fewer diagonals at $n$ specified horizontal positions.
\end{itemize}  \end{theorem}

\begin{proof}
The authors proved the first pair in Proposition 1 \cite{EdGriff3}.  The second pair follows directly from the first: change the vertical (1,0) step from height $n$ to a diagonal (1,1) step, or alter the horizontal (0,1) at $x=n$ to a diagonal,  to produce the desired lattice paths.  The third pair follows from the first by specifying positions $i_1, i_2, \dots i_n$, rather than positions $0,1, 2, \dots n-1$ as the only positions where diagonals are allowed.
\end{proof}
By step with ``vertical component" we mean vertical or diagonal.  By step with ``horizontal component" we mean horizontal or diagonal.  We sometimes for convenience speak of a ``step" $HV$ or $VH$, although these of course consist of two steps.
\begin{theorem}  For $k \geq 0$, the number $ D_k(m,n)$ counts paths from (0,0) to
\begin{itemize}
\item $(m,n)$ where each of the last $k$ horizontal steps H is followed by a D or V.  If there are fewer than k horizontal steps, say $i$, for $0 \leq i \leq k-1$,
then every horizontal step is followed by a step with vertical component, and the final $k-i + 1$
steps of the path are steps with a vertical component
\item $(n,m)$ where each of the last $k$ vertical steps V is followed by a D or H.  If there are fewer than k vertical steps, say $i$, for $0 \leq i \leq k-1$,
then every vertical step is followed by a step with horizontal component, and the final $k-i + 1$
steps of the path are steps with a horizontal component
\item $(m,n)$ where each of the last $k$ steps with horizontal component is VH or D
\item $(n,m)$ where each of the last $k$ steps with vertical component is either HV or D

\item $(m,n)$ where each of the last $k$ steps with horizontal component is either HV or D

\item $(n,m)$ where each of the last $k$ steps with vertical component is VH or D.


\end{itemize}
\end{theorem}

\begin{proof}
The authors proved the first pair in Proposition 2  \cite{EdGriff3}.  From Theorem \ref {Theorem 2.1}  above, we have that $D^k(n-k,m-k)$ counts the number of lattice paths to $(n-k,m)$ with no diagonals above height $m-k$.  For each of the last $k$ vertical steps $V$ in said paths, choose between adding a horizontal step after a $V$ or changing the $V$ to a diagonal step $D$.  We have $2^k$ choices, giving all paths to $(n,m)$ with the last $k$ steps with vertical component $VH$ or $D$.  The second pair now follows from the central theorem \cite{EdGriff3}, which states that  $D_k(m,n)=2^kD^k(n-k,m-k)$.  By swapping the occurrences as mentioned in the last $k$ steps of $HV$ and $VH$ in the second pair, we obtain the third pair. 
\end{proof}

\section{New proofs from lattice arguments}

Using the lattice path interpretations from the previous section, we provide proofs of some theorems previously proved \cite{EdGriff3}.  We refer to the following properties as ``relationship" theorems.

\begin{theorem} [Horizontal sum]  For $m,n,k\geq 0$,  we have $D^k(m,n) + D^k(m,n+1) =2 D^{k+1} (m,n).$
\end{theorem}

\begin{proof}   Interpret $D^k(m,n+1)$ as counting paths to $(m,n+k+1)$ with no $D$ above height $n+1$.  Such paths with no $D$ above height $n$ are exactly those counted by $ D^{k+1} (m,n)$.  The remaining paths have a $D$ at height $n$.  Change the $D$ to a $V$, then add an $H$ at the end, to get paths counted by $D^{k+1} (m,n)$ ending in $H$.  The remaining paths to $(m,n+k+1)$ end in $V$.  Remove the final V to get paths counted by $D^k(m,n)$.
\end{proof}

\begin{theorem}[Vertical sum]  For $m,n, k\geq 0$,  we have $D^k(m,n) + D^k(m+1,n) = D^{k-1} (m+1,n+1).$
\end{theorem}

\begin{proof}   Note that $ D^{k-1} (m+1,n+1)$ counts paths to $(m+1, n+k)$ with no $D$ above height $n+1$.  For every such path with a $D$ at height $n$, changing this $D$ to a $V$ results in a path to $(m,n+k)$ counted by $D^k(m,n)$.  Remaining paths have highest $D$ below height $n$.   These are counted by $D^k(m+1,n)$.
\end{proof}

The Delannoy recurrence states that $D^{k}(m,n) = D^{k}(m-1,n)+ D^{k}(m,n-1)+ D^{k}(m-1,n-1)$.  Using this and re-indexing gives two corollaries.

\begin{corollary}[Horizontal Difference]  For $m \geq 1,$ $n, k\geq 0$, we have $D^k(m,n+1) - D^k(m,n) =2 D^{k+1} (m-1,n).$
\end{corollary}

\begin{corollary}[Vertical Difference]  For $m,n,k\geq 0$, we have $D^k(m+1,n) - D^k(m,n) = D^{k-1} (m+1,n).$
\end{corollary}
The central theorem can be used to prove corresponding results for $D_k(m,n)$.
\begin{theorem}  For $m,n\geq 0$ and $k \geq 1,$ we have
\begin{align*}
D_k(m,n) + D_k(m,n+1) &=2 D_{k-1} (m,n),  \\
D_k(m,n) + D_k(m+1,n) &= D_{k+1} (m+1,n+1),  \\
D_k(m,n+1) - D_k(m,n) &=2 D_{k-1} (m-1,n), \\
D_k(m+1,n) - D_k(m,n) &= D_{k+1} (m+1,n). 
\end{align*}
\end{theorem}
\section{Alternate formulas}

We next prove alternate formulas for the Delannoy numbers using lattice path methods.  For the first formula,
which is known (see \seqnum{A008288} in \cite{Del}), we give a constructive proof using the usual  interpretation that  $D(m,n) $ counts lattice paths to $(m,n)$.    The idea is that the lattice path is completely determined by the location of a ``corner'', by which we mean $HV$ or $D$.
\begin{theorem}
For all integers $m,n \geq 0$, we have $$D(m,n)=\sum_{j=0}^{\min(m,n)}\binom{m}{j}\binom{n}{j}2^j.$$
\end{theorem}


\begin{proof} 
Postponing the use of $D$ for a moment, we interpret the binomial coefficients in the formula as specifying which of the $m$ horizontal steps $H$ are followed by which of the $n$ vertical steps $V$.  Here $j$ counts the number of instances of $HV$.  Let ${m \choose j}$ select which $H$'s are followed by $V$, and ${n \choose j}$ which $V$'s follow an $H$.  Any unselected $H$'s are either before another $H$ or at the end.  Likewise, any unselected $V$'s are either after a $V$ or at the beginning.  The factor $2^j$ counts the number of ways to change $HV$ to $D$.
\end{proof}

\begin{theorem} For all integers $m,n \geq k \geq 0$, we have $$D_k(m,n) = \sum_{j=0}^{\min (m-k, n-k)} {m-k \choose j} {n \choose j+k} 2^{j+k}.$$
\end{theorem}

\begin{proof}
Note that $D_k(m,n)$ counts paths to $(m,n)$ where the last $k$ steps with horizontal component are either $D$ or $HV$. As above, from the first $m-k$ $H$'s, choose $j$ to be followed by $V$.  From the $n$ $V$'s, choose $j+k$.  The first $j$ chosen $V$'s follow the chosen $j$ $H$'s.  The next $k$ chosen follow the last $k$ $H$'s.  Everything else works as in the proof above.
\end{proof}

The next theorem follows immediately from the previous theorem and the central theorem.
\begin{theorem}
For all  integers $m,n, k\geq 0$, we have $$D^k(m,n)=\sum_{j=0}^{\min (m,n)}\binom{m+k}{j+k}\binom{n}{j}2^j.$$
\end{theorem}

If we allow negative values of $k$ by interpreting, for $k$ positive, the expression $D_{-k}(m,n)$ as equal to the number $D^k(m,n)$, a version of this last form works for all cases. 
\begin{theorem} For all integers $k$, and all integers $m,n \geq k$, we have

$$D_k(m,n)=\sum_{j= \max ( 0,k)}^{\min (m,n)}\binom{m-k}{j-k}\binom{n}{j}2^j.$$
\end{theorem}

\section{Delannoy constructions}

Now we generalize our results to any array satisfying the Delannoy recurrence.
\begin{definition}  
Let $R(m,n)$ be any array of numbers, for $m,n \geq 0$.  We say that $R(m,n)$  is a {\it Delannoy array\/} if it satisfies the Delannoy recurrence.    
\end{definition}


If we set $R^1(m,n) = R(m,n) + R(m,n+1)$, then using this and the recurrence, we have that $R^1(m,n) $ equals
\begin{align*}
&( R(m-1,n) + R(m,n-1) + R(m-1,n-1)  ) +  (R(m-1,n+1) + R(m,n) + R(m-1,n)) \\ 
&= ( R(m-1,n) +  R(m-1,n+1) )+   (R(m,n-1) + R(m,n)  ) \\
&\quad +  ( R(m-1,n-1) + R(m-1,n) ) \\
&= R^1(m-1,n) + R^1(m,n-1) + R^1(m-1,n-1).
\end{align*}
Thus the array $R^1(m,n)$, for $m,n \geq 0$ is also a Delannoy array.

We call the function $h : R \to R^1$ defined by
$$ h(R(m,n))  = R(m,n) + R(m,n+1) =R^1(m,n)$$
the {\it horizontal sum function}.  Due to the recurrence, we have
$ R(m,n) + R(m,n+1) = R(m+1,n+1) - R(m+1,n)$ (the {\it horizontal identity}), so we could just as well define  $R^1(m,n) = R(m+1,n+1) - R(m+1,n)$.

We can continue this process to create subsequent arrays  $h(R^1(m,n))=R^2(m,n)$, $h(R^2(m,n))$ $=R^3(m,n)$, and so on, giving a sequence $R, R^1, R^2, R^3 \dots $.
  
We also have a {\it vertical identity}, $R(m,n) + R(m+1,n) = R(m+1,n+1) - R(m,n+1)$.  We define   $R_1(m,n) = R(m,n) + R(m+1,n) $, and $v: R \to R_1$, the {\it vertical sum}, by $v(R(m,n)) = R(m,n) + R(m+1,n)=R_1(m,n)$.  As above, $R_1$ is a Delannoy array, and as above we can define subsequent arrays by iterating $v$, giving  $R, R_1, R_2, R_3, \dots $.

Now consider 
\begin{align*}
&h(R_1(m,n))=R_1(m,n) + R_1(m,n+1)\\
&=\left (R(m,n) +  R(m+1,n) \right ) +\left ( R(m,n+1)+  R(m+1,n+1) \right )\\
&= (R(m,n) +  R(m,n+1) + R(m+1,n)) +  R(m+1,n+1) \\
&=  R(m+1,n+1) +  R(m+1,n+1) = 2 R(m+1,n+1).
\end{align*}
This shows that the horizontal sum maps $R_1$ onto $2R$, or, equivalently, it maps $ \frac 1 2 R_1$ onto $R$, and continuing in this fashion we have a sequence
$$ \cdots\to   \frac 1 {2^2} R_2 \to \frac 1 2 R_1 \to R \to R^1 \to R^2 \to \cdots, $$ where all the maps are horizontal sum.  Similar considerations give the sequence 
$$ \cdots \to  \frac 1 {2^2} R^2 \to \frac 1 2 R^1 \to R \to R_1 \to R_2 \to \cdots, $$ where all the maps are vertical sum.

 We call these two types of sequences  {\it Delannoy constructions} $\mathscr{ R}$.  In the case where the horizontal seeds for $R$ are identical to the vertical seeds, the arrays in the two sequences are transposes.  An example of this case is the Delannoy numbers, where all the seeds are $1$.  As a result of the relationship theorems, we have

$$ \cdots\to   \frac 1 {2^2} D_2 \to \frac 1 2 D_1 \to D \to 2D^1 \to 2^2D^2 \to \cdots, $$

$$ \cdots\to    D^2 \to  D^1 \to D \to D_1 \to D_2 \to \cdots. $$ 

So we conclude that $2^kD^k $ and $D_k$ are transposes, which is the central theorem of generalized Delannoy numbers.


We wish to consider the parity of  Delannoy constructions which have particular seeds, but we begin with some more general considerations.  Given a Delannoy array of numbers $R$, we have the following result.
\begin{theorem}  For all integers $m\geq 0$, if $ R(m,0) \equiv R(m+1,0)  \pmod{2}$, then for all $i \geq 0$, we have $ R(m,i) \equiv R(m+1,i)  \pmod{2}$.   If $ R(m,0) \not\equiv R(m+1,0)  \pmod{2}$, then  for all $i \geq 0$, we have $ R(m,i) \not\equiv R(m+1,i)  \pmod{2}$.
\end{theorem}

\begin{proof}  We proceed by induction on $i$. The base case for both statements is true by hypothesis.  If  $ R(m,i) \equiv R(m+1,i)  \pmod{2}$, then
$$R(m+1, i+1) = R(m,i) + R(m+1,i) + R(m,i+1) \equiv  R(m,i+1) ~  \pmod{2}.$$
On the other hand, if  $ R(m,i) \not\equiv R(m+1,i)  \pmod{2}$, then
$$R(m+1, i+1) = R(m,i) + R(m+1,i) + R(m,i+1) \equiv 1 + R(m,i+1) ~  \pmod{2}.$$
\end{proof}

This shows that the parities of $R(m,i)$ and  $R(m+1,i)$ either agree for all $i$ or disagree for all $i$.  Consequently, the parities of any two rows of $R$ are either identical in every term or differ in every term.  So modulo 2, there are only two different types of rows.  A consequence is that for both types of rows, and thus for all rows, the horizontal sum gives the same result modulo 2.

\begin{corollary}  
For $i \geq 1$, every row of $R^i$ modulo 2 is identical to every other row of $R^i$ modulo 2.
\end{corollary}


We next consider a family of examples where the seeds are binomial coefficients.  These examples give a generalization of properties enjoyed by the generalized Delannoy numbers.

\begin{lemma}  For $m \geq 0,$ $k \geq 1,$ we have $ { n \choose k } + { n+1 \choose k }  \equiv    { n \choose k-1 }    \pmod{2}$.
\end{lemma}

\begin{proof}  Pascal's theorem says that  $ { n \choose k -1} + { n \choose k }  =   { n+1 \choose k }    $, so $ { n \choose k-1 } + { n \choose k }  \equiv    { n+1 \choose k }    \pmod{2}$.    Equivalently, we have $ { n \choose k } + { n+1 \choose k }  \equiv    { n \choose k-1 }    \pmod{2}$.
\end{proof}



\begin{lemma}   If the horizontal seeds of $R$ are ${ k \choose k }$, ${ k+1 \choose k }$, ${ k+2 \choose k }, \dots $, then every element of $R^{k+1}$ is divisible by $2$, but for $j \leq k$, the array $R^j$ has elements that are odd.
\end{lemma}

\begin{proof}  Working modulo $2$ and using the horizontal sum, the rows of $R^1$ are ${ k \choose k-1 }$,  ${ k+1 \choose k-1 }$,  ${ k+2 \choose k-1 }, \dots $.   The rows of $R^2$ are ${ k \choose k-2 }$,  ${ k+1 \choose k-2 }$,  ${ k+2 \choose k-2 }, \dots $.  Continuing with the horizontal sum, the rows of $ R^k$ are 
 ${ k \choose 0 }$,  ${k+ 1 \choose 0 }$,  ${k+ 2\choose 0 }, \dots $, i.e., every element of $R^k$ is odd.  The horizontal sum on $R^k$ gives the divisibility result.  Kung  \cite {Kung} has shown that ${ 2^i -1 \choose n } $ is odd for any $n \geq 0,$ so $R^j$ has odd elements.
\end{proof}


\begin{theorem}  If the horizontal seeds of $R$ are ${ k \choose k }$, ${ k+1 \choose k }$, ${ k+2 \choose k }, \dots $, then $R^1$, modulo 2, has identical rows, namely ${ k \choose k-1 }$,  ${ k +1\choose k-1 }$,  ${ k+2 \choose k-1 }, \dots .$ \end{theorem}

Our final theorem generalizes the fact that every generalized Delannoy number $D_k(m,n)$ is divisible by $2^k$.
\begin{theorem}  If the horizontal seeds of $R$ are ${ k \choose k }$, ${ k+1 \choose k }$, ${ k+2 \choose k }, \dots $, then for $i \geq 1$, every element of $R^{k+i }$ is divisible by $2^i$, but  $R^{k+i }$ has elements that are not divisible by  $2^{i+1}$.  \end{theorem}


\begin{proof}  We show the divisibility by induction, where Lemma 5.5 has provided the base case.  Since every element of $R^k$ is odd, by the horizontal sum, every element of $R^{k+1}$ is even, and so divisible by $2^1.$ Suppose that for some integer $s \geq 1$, every element of $R^{k+s}$ is divisible by $2^s.$  Then by the horizontal sum, we have $R^{k+s+1}(m,n)=R^{k+s}(m,n) + R^{k+s}(m,n+1)$.  The two terms on the right are divisible by $2^{s}$, which makes $R^{k+s+1}(m,n)$ divisible by $2^{s+1}$.  Finally, every element in the first row of $R^{k+i}$ is $2^i$, which is not divisible by $2^{i+1}$. \end{proof}


\begin{thebibliography}{40}


\bibitem{WhyDelannoy} Cyril Banderier and Sylviane Schwer, Why Delannoy numbers?, {\it Journal of Statist. Plann. and Inference} \textbf{135} (2005), 40--54. 


\bibitem{Delannoy} H. Delannoy,
Emploi de l'\'echiquier pour la r\'esolution de certains
probl\`emes de probabilit\'es, {\it Assoc.
Fran\c{c}aise pour l'Avancement des Sciences, Comptes Rendus} \textbf{24} (1895), 70--90.

\bibitem{EdGriff2}  Steven Edwards and William Griffiths, Generalizations of Delannoy and cross polytope numbers, {\it Fibonacci Quart.} \textbf{55} (2017), 357--366.

\bibitem{EdGriff3}  Steven Edwards and William Griffiths, On generalized Delannoy numbers, 
{\it J. Integer Sequences} \textbf{23} (2020), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL23/Griffiths/griffiths51.html}{Article 20.3.6}.

\bibitem{Kung} S. H. L. Kung, Parity triangles Of Pascal's triangle,  {\it Fibonacci Quart.} \textbf{14} (1976),  54.

\bibitem{Del} N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2023.  Available at \url{https://oeis.org}.






\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\em Mathematics Subject Classification}:  Primary 05A19; Secondary 01A10, 11B37, 11B75.

\noindent{\em Keywords}:  Delannoy number, lattice path, recursion, binomial sum.


\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 May 24 2023;
revised version received  November 27 2023.
Published in {\it Journal of Integer Sequences}, January 14 2024.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

