Delannoy Constructions

Steven Edwards and William Griffiths Department of Mathematics Kennesaw State University Marietta, GA 30060 USA

                     sedwar77@kennesaw.edu
                     wgriff17@kennesaw.edu

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.

1 Introduction

Henri Auguste Delannoy (1833–1915) was a French army officer and later an amateur mathematician, historian, and painter. Correspondence with Édouard 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 [1]. These Delannoy numbers count the number of 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 [2] 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 Delannoy 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 given by

D(m, n) = ∑_{j=0}^{n} \binom{m + n − j}{n}\binom{n}{j}.

The authors introduced [3] 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 generalized Delannoy numbers are defined, for m, n ≥ k ≥ 0, by

D_{k}(m, n) = ∑_{j=0}^{n} \binom{m + n − k − j}{n − k}\binom{n}{j}.

While we could allow k to be negative, it is more convenient to define, for m, n, k ≥ 0, by

D^{k}(m, n) = ∑_{j=0}^{n} \binom{m + n + k − j}{n + k}\binom{n}{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” [4] which relates these two types:

D_{k}(m, n) = 2^{k}D^{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.

\begin{matrix}\begin{matrix}D^{0} & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & \binom{0}{0} & \binom{1}{1} & \binom{2}{2} & \binom{3}{3} & \binom{4}{4} & \binom{5}{5} \\ 1 & \binom{1}{0} & 3 & 5 & 7 & 9 & 11 \\ 2 & \binom{2}{0} & 5 & 13 & 25 & 41 & 61 \\ 3 & \binom{3}{0} & 7 & 25 & 63 & 129 & 231 \\ 4 & \binom{4}{0} & 9 & 41 & 129 & 321 & 681 \\ 5 & \binom{5}{0} & 11 & 61 & 231 & 681 & 1683 \end{matrix} & \begin{matrix}D^{1} & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & \binom{1}{1} & \binom{2}{2} & \binom{3}{3} & \binom{4}{4} & \binom{5}{5} & \binom{6}{6} \\ 1 & \binom{2}{1} & 4 & 6 & 8 & 10 & 12 \\ 2 & \binom{3}{1} & 9 & 19 & 33 & 51 & 73 \\ 3 & \binom{4}{1} & 16 & 44 & 96 & 180 & 304 \\ 4 & \binom{5}{1} & 25 & 85 & 225 & 501 & 985 \\ 5 & \binom{6}{1} & 36 & 146 & 456 & 1182 & 2668 \end{matrix} \\ \begin{matrix}D^{2} & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & \binom{2}{2} & \binom{3}{3} & \binom{4}{4} & \binom{5}{5} & \binom{6}{6} & \binom{7}{7} \\ 1 & \binom{3}{2} & 5 & 7 & 9 & 11 & 13 \\ 2 & \binom{4}{2} & 14 & 26 & 42 & 62 & 86 \\ 3 & \binom{5}{2} & 30 & 70 & 138 & 242 & 390 \\ 4 & \binom{6}{2} & 55 & 155 & 363 & 743 & 1375 \\ 5 & \binom{7}{2} & 91 & 301 & 819 & 1925 & 4043 \end{matrix} & \begin{matrix}D^{3} & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & \binom{3}{3} & \binom{4}{4} & \binom{5}{5} & \binom{6}{6} & \binom{7}{7} & \binom{8}{8} \\ 1 & \binom{4}{3} & 6 & 8 & 10 & 12 & 14 \\ 2 & \binom{5}{3} & 20 & 34 & 52 & 74 & 100 \\ 3 & \binom{6}{3} & 50 & 104 & 190 & 316 & 490 \\ 4 & \binom{7}{3} & 105 & 259 & 553 & 1059 & 1865 \\ 5 & \binom{8}{3} & 196 & 560 & 172 & 2984 & 5908 \end{matrix} \end{matrix}

Table 1: Values of D^{0}, D^{1}, D^{2}, D^{3}. We use m to count rows, n to count columns.

2 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. Theorem 1. For k ≥ 0, the number D^{k}(m, n) counts paths from (0,0) to

• (m, n + k) with no diagonals above height n

• (n + k, m) with no diagonals past x = n

• (m + 1, n + k) with highest diagonal at height n

• (n + k, m + 1) with rightmost diagonal at x = n

• (m, n + k) where there are n or fewer diagonals, allowed only at n specified heights • (n + k, m) where there are n or fewer diagonals at n specified horizontal positions.

Proof. The authors proved the first pair in Proposition 1 [4]. 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}, … i_{n}, rather than positions 0, 1, 2, … n − 1 as the only positions where diagonals are allowed.

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 V H, although these of course consist of two steps.

Theorem 2. For k ≥ 0, the number D_{k}(m, n) counts paths from (0,0) to

• (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 ≤ i ≤ 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

• (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 ≤ i ≤ 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

• (m, n) where each of the last k steps with horizontal component is VH or D

• (n, m) where each of the last k steps with vertical component is either HV or D

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

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

Proof. The authors proved the first pair in Proposition 2 [4]. From Theorem 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 V H or D. The second pair now follows from the central theorem [4], which states that D_{k}(m, n) = 2^{k}D^{k}(n − k, m − k). By swapping the occurrences as mentioned in the last k steps of HV and V H in the second pair, we obtain the third pair.

3 New proofs from lattice arguments

Using the lattice path interpretations from the previous section, we provide proofs of some theorems previously proved [4]. We refer to the following properties as “relationship” theorems.

Theorem 3 (Horizontal sum). For m, n, k ≥ 0, we have D^{k}(m, n) + D^{k}(m, n + 1) = 2D^{k+1}(m, n).

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).

Theorem 4 (Vertical sum). For m, n, k ≥ 0, we have D^{k}(m, n) + D^{k}(m + 1, n) = D^{k−1}(m + 1, n + 1).

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).

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.

Corollary 5 (Horizontal Difference). For m ≥ 1, n, k ≥ 0, we have D^{k}(m, n + 1) − D^{k}(m, n) = 2D^{k+1}(m − 1, n).

Corollary 6 (Vertical Difference). For m, n, k ≥ 0, we have D^{k}(m + 1, n) − D^{k}(m, n) = D^{k−1}(m + 1, n).

The central theorem can be used to prove corresponding results for D_{k}(m, n).

Theorem 7. For m, n ≥ 0 and k ≥ 1, we have

D_{k}(m, n) + D_{k}(m, n + 1) = 2D_{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) = 2D_{k−1}(m − 1, n),
D_{k}(m + 1, n) − D_{k}(m, n) = D_{k+1}(m + 1, n).

4 Alternate formulas

We next prove alternate formulas for the Delannoy numbers using lattice path methods. For the first formula, which is known (see \underline{A008288} in [6]), 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.

Theorem 8. For all integers m, n ≥ 0, we have

D(m, n) = ∑_{j=0}^{min(m,n)} \binom{m}{j}\binom{n}{j}2^{j}.

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 \binom{m}{j} select which H’s are followed by V, and \binom{n}{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.

Theorem 9. For all integers m, n ≥ k ≥ 0, we have

D_{k}(m, n) = ∑_{j=0}^{min(m−k,n−k)} \binom{m − k}{j}\binom{n}{j + k}2^{j+k}.

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.

The next theorem follows immediately from the previous theorem and the central theorem.

Theorem 10. For all integers m, n, k ≥ 0, we have

D^{k}(m, n) = ∑_{j=0}^{min(m,n)} \binom{m + k}{j + k}\binom{n}{j}2^{j}.

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.

Theorem 11. For all integers k, and all integers m, n ≥ k, we have

D_{k}(m, n) = ∑_{j=max(0,k)}^{min(m,n)} \binom{m − k}{j − k}\binom{n}{j}2^{j}.

5 Delannoy constructions

Now we generalize our results to any array satisfying the Delannoy recurrence.

Definition 12. Let R(m, n) be any array of numbers, for m, n ≥ 0. We say that R(m, n) is a Delannoy array if it satisfies the Delannoy recurrence.

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

(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))

+ (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).

Thus the array R^{1}(m, n), for m, n ≥ 0 is also a Delannoy array.

We call the function h : R → R^{1} defined by

h(R(m, n)) = R(m, n) + R(m, n + 1) = R^{1}(m, n)

the 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 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} . . ..

We also have a 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 → R_{1}, the 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}, . . ..

Now consider

h(R_{1}(m, n)) = R_{1}(m, n) + R_{1}(m, n + 1)
= (R(m, n) + R(m + 1, n)) + (R(m, n + 1) + R(m + 1, n + 1))
= (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) = 2R(m + 1, n + 1).

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

⋯ → \frac{1}{2^{2}} R_{2} → \frac{1}{2}R_{1} → R → R^{1} → R^{2} → ⋯,

where all the maps are horizontal sum. Similar considerations give the sequence

⋯ → \frac{1}{2^{2}} R^{2} → \frac{1}{2}R^{1} → R → R_{1} → R_{2} → ⋯,

where all the maps are vertical sum.

We call these two types of sequences Delannoy constructions ℛ. 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

⋯ → \frac{1}{2^{2}} D_{2} → \frac{1}{2}D_{1} → D → 2D^{1} → 2^{2}D^{2} → ⋯,

⋯ → D^{2} → D^{1} → D → D_{1} → D_{2} → · · · .

So we conclude that 2^{k}D^{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.

Theorem 13. For all integers m ≥ 0, if R(m, 0) ≡ R(m + 1, 0) (mod 2), then for all i ≥ 0, we have R(m, i) ≡ R(m + 1, i) (mod 2). If R(m, 0) ≢ R(m + 1, 0) (mod 2), then for all i ≥ 0, we have R(m, i) ≢ R(m + 1, i) (mod 2).

Proof. We proceed by induction on i. The base case for both statements is true by hypothesis. If R(m, i) ≡ R(m + 1, i) (mod 2), then

R(m + 1, i + 1) = R(m, i) + R(m + 1, i) + R(m, i + 1) ≡ R(m, i + 1) (mod 2).

On the other hand, if R(m, i) ≢ R(m + 1, i) (mod 2), then

R(m + 1, i + 1) = R(m, i) + R(m + 1, i) + R(m, i + 1) ≡ 1 + R(m, i + 1) (mod 2).

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.

Corollary 14. For i ≥ 1, every row of R^{i} modulo 2 is identical to every other row of R^{i} modulo 2.

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.

Lemma 15. For m ≥ 0, k ≥ 1, we have \binom{n}{k} + \binom{n+1}{k} ≡ \binom{n}{k−1} (mod 2).

Proof. Pascal’s theorem says that \binom{n}{k−1} + \binom{n}{k} = \binom{n+1}{k}, so \binom{n}{k−1} + \binom{n}{k} ≡ \binom{n+1}{k} (mod 2). Equivalently, we have \binom{n}{k} + \binom{n+1}{k} ≡ \binom{n}{k−1} (mod 2).

Lemma 16. If the horizontal seeds of R are \binom{k}{k}, \binom{k+1}{k}, \binom{k+2}{k}, …, then every element of R^{k+1} is divisible by 2, but for j ≤ k, the array R^{j} has elements that are odd.

Proof. Working modulo 2 and using the horizontal sum, the rows of R^{1} are \binom{k}{k−1}, \binom{k+1}{k−1}, \binom{k+2}{k−1}, . . .. The rows of R^{2} are \binom{k}{k−2}, \binom{k+1}{k−2}, \binom{k+2}{k−2}, . . .. Continuing with the horizontal sum, the rows of R^{k} are \binom{k}{0}, \binom{k+1}{0}, \binom{k+2}{0}, …, i.e., every element of R^{k} is odd. The horizontal sum on R^{k} gives the divisibility result. Kung [5] has shown that \binom{2^{i}−1}{n} is odd for any n ≥ 0, so R^{j} has odd elements.

Theorem 17. If the horizontal seeds of R are \binom{k}{k}, \binom{k+1}{k}, \binom{k+2}{k}, …, then R^{1}, modulo 2, has identical rows, namely \binom{k}{k−1}, \binom{k+1}{k−1}, \binom{k+2}{k−1}, ….

Our final theorem generalizes the fact that every generalized Delannoy number D_{k}(m, n) is divisible by 2^{k}.

Theorem 18. If the horizontal seeds of R are \binom{k}{k}, \binom{k+1}{k}, \binom{k+2}{k}, …, then for i ≥ 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}.

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 ≥ 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}.

References

[1] Cyril Banderier and Sylviane Schwer, Why Delannoy numbers?, Journal of Statist. Plann. and Inference 135 (2005), 40–54.

[2] H. Delannoy, Emploi de l’échiquier pour la résolution de certains problèmes de probabilités, Assoc. Française pour l’Avancement des Sciences, Comptes Rendus 24 (1895), 70–90.

[3] Steven Edwards and William Griffiths, Generalizations of Delannoy and cross polytope numbers, Fibonacci Quart. 55 (2017), 357–366.

[4] Steven Edwards and William Griffiths, On generalized Delannoy numbers, J. Integer Sequences 23 (2020), Article 20.3.6.

[5] S. H. L. Kung, Parity triangles Of Pascal’s triangle, Fibonacci Quart. 14 (1976), 54.

[6] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2023. Available

    at https://oeis.org.

2020 Mathematics Subject Classification: Primary 05A19; Secondary 01A10, 11B37, 11B75. Keywords: Delannoy number, lattice path, recursion, binomial sum.

(Concerned with sequences \underline{A002415}, \underline{A005893}, \underline{A008288}, \underline{A034827}, \underline{A051890}, \underline{A058331}, \underline{A093328}, \underline{A097080}, and \underline{A142978}.)

Received May 24 2023; revised version received November 27 2023. Published in Journal of Integer Sequences, January 14 2024.

Return to Journal of Integer Sequences home page.