On Generalized Delannoy Numbers

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

1 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 [2]. He is best known for his Delannoy numbers (see sequence \underline{A008288} in [9]), which count 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 [4] 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) = ∑_{j=0}^{n} \binom{m + n − j}{n}\binom{n}{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 \binom{m+n−j}{n} ways. (The remaining m − j steps are horizontal steps.) Choose j of those n steps with vertical component to be diagonal steps in \binom{n}{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 [3, §7.21, pp. 121–122]. Kim [8] constructed the cross polytope numbers. The standard formula for the cross polytope numbers is T (m, n) = ∑_{j=0}^{m−1} \binom{n+j}{m}\binom{m−1}{j}; see \underline{A142978} in [9]. Edwards and Griffiths [6] found two additional formulas for the cross polytope numbers, which are as follows:

T (m, n) = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{m + n − 1 − 2j}{n − 1}\binom{n}{2j} = \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{m + n − 1 − (2j + 1)}{n − 1}\binom{n}{2j + 1}.

The cross polytope numbers are partial row sums of the Delannoy numbers (\underline{A142978} in [9]):

∑_{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 5. Summing the two versions of T (m, n) above gives

T (m, n) = \frac{1}{2} ∑_{j=0}^{n} \binom{m + n − 1 − j}{n − 1}\binom{n}{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 ≥ k ≥ 0,

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,

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

E_{k}(m, n) = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{m + n − k − 2j}{n − k}\binom{n}{2j}

O_{k}(m, n) = \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{m + n − k − (2j + 1)}{n − k}\binom{n}{2j + 1}

E^{k}(m, n) = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{m + n + k − 2j}{n + k}\binom{n}{2j}

O^{k}(m, n) = \begin{matrix}⌊ & \frac{n−1}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} \binom{m + n + k − (2j + 1)}{n + k}\binom{n}{2j + 1}.

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 [7].

2 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 vertical component to mean either V or D.

Proposition 1. 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.

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 \binom{m+n+k−j}{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 \binom{n}{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.

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

Proposition 2. 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 ≤ i ≤ 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.

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 \binom{m+n−k−j}{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 ≤ i ≤ 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.

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.

3 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) = ∑_{j=0}^{n} \binom{m+n−k−j}{n−k}\binom{n}{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).

Proposition 3. For all integers m, n ≥ k ≥ 1 we have E_{k}(m, n) = O_{k}(m, n) = \frac{1}{2}D_{k}(m, n).

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

The numbers E^{k}(m, n) and O^{k}(m, n) are not equal, but differ by a binomial coefficient.

Proposition 4. For all integers m, n ≥ k ≥ 0 we have E^{k}(m, n) = O^{k}(m, n) + \binom{m+k}{k}.

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 \binom{m+k}{k} such words.

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 3, D can be replaced by E or O in the following:

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

D_{k}(m, n) = D_{k}(m − 1, n) + D_{k}(m, n − 1) + D_{k}(m − 1, n − 1).

Proof. We consider words counted by D_{k}(m, n) as being of four types which can be denoted XXH, V XX, 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.

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 ith V and the ith 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).

Theorem 6. For all integers m, n, k, with m, n > 0, k ≥ 0 we have

D^{k}(m, n) = D^{k}(m − 1, n) + D^{k}(m, n − 1) + D^{k}(m − 1, n − 1).

Proof. The terms on the RHS count, in turn, paths that begin with a horizontal step, a vertical step, and a diagonal step.

\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 & 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{matrix} & \begin{matrix}\frac{1}{2}D_{1} & 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & \binom{1}{1} & \binom{2}{1} & \binom{3}{1} & \binom{4}{1} & \binom{5}{1} & \binom{6}{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{matrix} \\ \begin{matrix}\frac{1}{2^{2}} D_{2} & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & \binom{2}{2} & \binom{3}{2} & \binom{4}{2} & \binom{5}{2} & \binom{6}{2} & \binom{7}{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{matrix} & \begin{matrix}\frac{1}{2^{3}} D_{3} & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & \binom{3}{3} & \binom{4}{3} & \binom{5}{3} & \binom{6}{3} & \binom{7}{3} & \binom{8}{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{matrix} \end{matrix}

Table 1: Values of D_{0}, D_{1}, D_{2}, D_{3}. Rows correspond to m is row and columns to n.

4 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 [5, 5.28, p. 171], one of the few identities known for a product of two binomial coefficients. A combinatorial/probabilistic proof of the lemma is known [1]. We find it likely there is an easier proof of the lemma using lattice paths, but have not yet found one.

Lemma 7. \binom{a}{b}\binom{c}{d} = ∑_{j=0}^{a+d−c} \binom{a+d−j}{a+d−b}\binom{a+d−c}{j}\binom{c−b}{d−j}.

We use Lemma 7 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).

Theorem 8 (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).

Proof. We have, using the lemma,

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

= ∑_{i=0}^{m+k} ∑_{j=0}^{n} \binom{m + n + k − j}{n + k}\binom{n}{j}\binom{k}{i − j}

= ∑_{j=0}^{n} \binom{m + n + k − j}{n + k}\binom{n}{j} ∑_{i=0}^{m+k} \binom{k}{i − j}

= ∑_{j=0}^{n} \binom{m + n + k − j}{n + k}\binom{n}{j} ∑_{s=0}^{k} \binom{k}{s}

= 2^{k}D^{k}(m, n).

Corollary 9. The number D_{k}(m, n) is divisible by 2^{k}.

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 \binom{m+n+k−j}{n+k} = \binom{m+n+k−j}{m−j} count words with m + n + k − j letters, of which m − j are H. Let \binom{n}{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 \binom{k}{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 V H. 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 V H or D. Because of this second interpretation of D_{k}, in what follows, for convenience we will speak of paths with “step” V H, although of course V H 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 \binom{k}{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.

5 Relationships among generalized Delannoy numbers

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 V H. We use this interpretation to prove results in this section, including a simpler proof of Theorem 5, the recurrence for D_{k}(m, n):

For m, n > k ≥ 0 we have D_{k}(m, n) = D_{k}(m − 1, n) + D_{k}(m, n − 1) + D_{k}(m − 1, n − 1).

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.

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 m < k) involve terms with negative integers.

Theorem 10. For n ≥ k ≥ 0 we have D_{k}(k, n) = 2^{k}\binom{n}{k}.

Proof. A path to (n, k) has k steps with vertical component, so the interpretation that the last k steps are either D or V H means every vertical step is such. So \binom{n}{k} counts the placement of the k steps with vertical component, each of which has two choices, D or V H.

We now begin cataloging results relating the D_{k}(m, n) tables for different values of k:

Theorem 11 (horizontal difference). For m, n ≥ k ≥ 1 we have

D_{k}(m, n) − D_{k}(m, n − 1) = 2D_{k−1}(m − 1, n − 1).

Proof. A path to (n, m) cannot come from (n, m − 1), since the last vertical step must be D or V H and not just V. If the path comes from (n − 1, m − 1), it can get to (n, m) either by adding D or V H to the end. If the path comes from (n − 1, m), add an H as the last step. Thus, D_{k}(m, n) = 2D_{k−1}(m − 1, n − 1) + D_{k}(m, n − 1).

Theorem 12 (vertical difference). For m, n > k ≥ 0 we have

D_{k}(m, n) − D_{k}(m − 1, n) = D_{k+1}(m, n).

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 V H. Thus D_{k}(m, n) − D_{k+1}(m, n) counts paths to (n, m) with the last k verticals D or V H, 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 V H, 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).

The preceding two theorems give the following theorem.

Theorem 13 (horizontal sum). For m, n > k ≥ 1 we have

D_{k}(m, n) + D_{k}(m, n − 1) = 2D_{k−1}(m, n − 1).

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

The horizontal sum theorem is a generalization of the fact that the sum of two adjacent cross polytope numbers is a Delannoy number.

Theorem 14 (vertical sum). For m, n ≥ k ≥ 0 we have

D_{k}(m, n) + D_{k}(m − 1, n) = D_{k+1}(m, n + 1).

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.

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.

Theorem 15.

2^{r}D_{k}(m, n) = ∑_{i=0}^{r}(−1)^{r+i}\binom{r}{i}D_{k+r}(m + r, n + i)

D_{k}(m, n) = ∑_{i=0}^{r}(−1)^{i}\binom{r}{i}D_{k−r}(m − i, n)

2^{r}D_{k}(m, n) = ∑_{i=0}^{r} \binom{r}{i}D_{k+r}(m, n + i)

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

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.

Theorem 16. For j = 1, …, k we have D_{k}(m, n) = 2^{j} ∑_{i=0}^{n−k} \binom{j+i−1}{i}D_{k−j}(m − j, n − j − i).

Proof. Fix m, n, k, j. For i = 0, 1, … 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 V H, while D_{k}(m, n) counts paths to (n, m) with the last such k D or V H. 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 V H, 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 V H. Thus there are \binom{j+i−1}{i} ways to choose which steps are H, and 2^{j} choices of either D or V H for the j diagonal steps.

From the proof, we see that the expression 2^{j} ∑_{i=0}^{n−k} \binom{j+i−1}{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}\binom{j+i−1}{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:

Corollary 17. For k ≥ 1 we have

D_{k}(m, n) = 2 (D_{k−1}(m − 1, n − 1) + D_{k−1}(m − 1, n − 2) + ⋯ + D_{k−1}(m − 1, k − 1)) .

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}:

Corollary 18. For k ≥ 1 we have

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

The next theorem groups the paths counted by D_{k}(m, n) according to the highest diagonal below m − k.

Theorem 19. D_{k}(m, n) = \frac{1}{2^{m}} D_{m}(m, n + m − k) + ∑_{j=1}^{m−k} \frac{1}{2^{j}} D_{k+j}(m, n + j − 1).

Proof. For j = 1, 2, … 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 𝒟 a part of a lattice path that is either a D or a V H. Then a path counted by D_{k+j}(m, n + j − 1)) has its last k+j verticals steps as 𝒟. Leave the last k 𝒟’s alone, and but for the remaining j 𝒟’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 𝒟’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 𝒟’s to V, giving the paths from D_{k}(m, n) with no diagonals below the height of m − k.

As a consequence of the theorem, we get a new interpretation: for i = 1, …, 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.

6 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, last k can be replaced by 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} ∑_{j=0}^{b} \binom{a − j}{b + c}\binom{b}{j} = ∑_{j=0}^{a−b} \binom{a − j}{a − (b + c)}\binom{a − b}{j}.

There are as many directions to proceed from here as sequences in this collection. The generalized Delannoy numbers include many known number sequences [9]. 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 \underline{A058331} in the 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×2 matrices with integer entries from 0 to n.

\frac{1}{4}D_{2}(m, 4), or \underline{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 \underline{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 \underline{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 \underline{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 nth and (n − 1)st circles of the Pappus chain of the symmetric arbelos.

\frac{1}{32}D_{5}(m, 7), or \underline{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 \underline{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 nonintersecting 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.

7 Acknowledgment

The authors wish to thank the referee for helpful suggestions and comments which have improved the content of this paper.

References

[1] George E. Andrews, Identities in combinatorics, I: on sorting two ordered sets, Discrete Math. 11 (1975), 97–106.

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

[3] H. S. M. Coxeter, Regular Polytopes, Dover Publications, 1973.

[4] H. Delannoy, Emploi de l’échiquier pour la résolution de divers problèmes de probabilité, Assoc. Franc. Bordeaux 24 (1895), 70–90.

[5] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1998.

[6] Steven Edwards and William Griffiths, A binomial identity related to cross polytope numbers, Fibonacci Quart. 54 (2016), 253–256.

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

[8] Hyun Kwang Kim, On regular polytope numbers, Proc. Amer. Math. Soc. 131 (2003), 65–75.

[9] N. J. A. Sloane et al., The On-line Encyclopedia of Integer Sequences, 2020. Available at

   https://oeis.org.

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

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

Received October 30 2019; revised version received March 16 2020. Published in Journal of Integer Sequences, March 17 2020.

Return to Journal of Integer Sequences home page.