OBJECTS COUNTED BY THE CENTRAL DELANNOY NUMBERS

ROBERT A. SULANKE

Abstract. The central Delannoy numbers, (d_{n})_{n≥0} = 1, 3, 13, 63, 321, 1683, 8989, 48639, … (A001850 of The On-Line Encyclopedia of Integer Sequences) will be defined so that d_{n} counts the lattice paths running from (0, 0) to (n, n) that use the steps (1, 0), (0, 1), and (1, 1). In a recreational spirit we give a collection of 29 configurations that these numbers count.

1. Introduction

In the late nineteenth century, Henri Delannoy [4] introduced what we now call the Delannoy array. For integers i and j, we define this array d_{i,j} to satisfy

d_{i,j} = d_{i−1,j} + d_{i,j−1} + d_{i−1,j−1}

with the conditions d_{0,0} = 1 and d_{i,j} = 0 if i < 0 or j < 0. The members of the sequence (d_{i})_{i≥0} := (d_{i,i})_{i≥0} = 1, 3, 13, 63, 321, 1683, 8989, 48639, … (A001850 of Sloane [15]), are known as the (central) Delannoy numbers.

d_{i,j} := \begin{matrix}i \ j & 0 & 1 & 2 & 3 & 4 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 3 & 5 & 7 & 9 \\ 2 & 1 & 5 & 13 & 25 & 41 \\ 3 & 1 & 7 & 25 & 63 & 129 \\ 4 & 1 & 9 & 41 & 129 & 321 \end{matrix}

In Section 3 we will show that the generating function for the central Delannoy numbers satisfies

∑_{i≥0} d_{i}z^{i} = \frac{1}{\sqrt{1 − 6z + z^{2}}} .  (1)

An alternative derivation of this is given by Stanley [16, Sect. 6.3]. These numbers satisfy the recurrence,

(n + 2)d_{n+2} = 3(2n + 3)d_{n+1} − (n + 1)d_{n}.  (2)

subject to d_{0} = 1 and d_{1} = 3, as shown, e.g., by Stanley [16, Sect. 6.4] and the author [18].

We refer the question, “Why Delannoy numbers?”, to the survey on the life and works of Delannoy written by Banderier and Schwer [1]. While the (central) Delannoy numbers are known through the books of Comtet [3] and Stanley [16], only a few examples of objects enumerated by these numbers have been found in the literature. These examples will appear and be referenced in the following sections.

After Delannoy’s introduction of the numbers, essentially as counting unrestricted paths that use the steps (0, 1), (1, 0), and (1, 1), they appear again in 1952, when Lawden [8], without citing Delannoy, found them to be the values of the Legendre polynomials with argument equaling 3. However, the definition of the Legendre polynomials does not appear to foster any combinatorial interpretation leading to enumeration. See also Moser and Zayachkowski [9].

In the following section we give a catalog of 29 configurations counted by the (central) Delannoy numbers, ordered primarily as they were collected. In keeping with Delannoy’s interest in recreational mathematics, this catalog is intended to constitute exercises inviting bijective, recursive, and generating functional proofs that the Delannoy numbers do indeed count the configurations. Each example is accompanied by an illustration of a set of configurations corresponding to d_{2} = 13. Section 3 contains intentionally incomplete notes regarding some bijective and generating functional verifications for the examples.

The collector wishes to thank Cyril Banderier, Emeric Deutsch, Enrica Duchi, Ira Gessel, Sylviane Schwer, Lou Shapiro, and Renzo Sprugnoli for their contribution to this project. He also appreciates the referee’s generous critique.

2. A catalog of configurations

In the integer plane, we will take lattice paths to be represented as concatenations of the directed steps belonging to various specified sets. When the steps are weighted, the weight of a path is the product of the weights of its steps, and the weight of a path set is the sum of the weights of its paths. As noted in the remark following Example 3, the independent coloring of substructures on paths is equivalent to weighting. Throughout, we will denote the diagonal up and down steps as U := (1, 1) and D := (1, −1).

Example 1. A classic example is the set of paths from (0, 0) to (2n, 0) using the steps U, D, and (2, 0). For the “tilted” version consider the path from (0, 0) to (n, n) using the steps (0, 1), (1, 0), and (1, 1). From this path model one can obtain a combinatorial proof that, for n ≥ 0,

d_{n} = ∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k}.  (3)

Figure 1. The d_{2} = 13 unrestricted paths from (0, 0) to (2n, 0) using the steps U, D, and (2, 0).

Example 2. The Delannoy number d_{n} is the weight of the set of paths from (0, 0) to (n, 0) using the steps U_{2}, D, and (1, 0)_{3}, where the up step U_{2} and the horizontal step (1, 0)_{3} have weights 2 and 3, respectively.

Alternatively, d_{n} counts the paths from (0, 0) to (n, 0) using the steps U, D, and (1, 0), where the U steps are independently colored blue or red and the (1, 0) steps are independently colored blue, red, or green. See the remark following Example 3.

Figure 2. Here 2 + 2 + 3 · 3 = d_{2}

Example 3. Using the steps U and D, we find d_{n} to be the weighted sum of the paths from (0, 0) to (2n, 0) where within each path the right-hand turns, or peaks, have weight 2. Consequently, one can obtain a combinatorial proof that, for n ≥ 0,

∑_{i=0}^{n} \binom{n}{i}^{2}2^{i} = d_{n}.  (4)

Figure 3. The sum of the weights of the paths is 2 + 4 + 2 + 2 + 2 + 1 = d_{2}.

Remark: Often, as in Examples 3, we will consider paths with substructures – such as peaks, double ascents, etc. – which make a multiplicative contribution of 2 to the weight of each path. Other such examples include 4, 5, 14, 20, 21, 24, 25, 26, and 27. If momentarily the weights of the substructures is reduced to 1, then the weight of a set of such paths becomes a cardinality, namely the central binomial coefficient, \binom{2n}{n}. Indeed, in the figures for the above named examples, there will be \binom{4}{2} = 6 shapes in each illustration. However, when the substructures have weight 2, the weight of the set of such paths is a Delannoy number, which in turn is the cardinality of the paths of same shapes on which the substructures are independently colored Blue or Red. In this catalog we will usually omit versions of examples with Blue-Red substructures, which would yield 13 shapes instead of 6 shapes in the relevant illustrations.

Example 4. Using the steps U and D, we find that d_{n} is the sum of the weights of the paths from (0, 0) to (2n + 1, 1) that begin with an up step and where the intermediate vertices of double ascents have weight 2.

Figure 4. The sum of the weights of the paths is 4 + 2 + 2 + 2 + 1 + 2 = d_{2}.

Example 5. Using the steps U and D, we find that d_{n} is the weighted sum over the paths from (0, 0) to (2n, 0) where each U step which is oddly positioned along its path has weight 2.

Figure 5. The sum over the weights of the paths is 2 + 4 + 2 + 2 + 1 + 2 = d_{2}.

Example 6. The product 2^{n−1}d_{n} counts the set of all paths from (0, 0) to (n, n) with steps of the form (x, y) where x and y are nonnegative integers, not both 0.

Figure 6. Here 2^{n−1}d_{n} = 2 · 13, for n = 2.

Example 7. Using the steps U_{2}, D, and (2, 0)_{−1} where the up step and the horizontal step have weights of 2 and −1, respectively, d_{n} is the sum of the weights of the paths running from (0, 0) to (2n, 0).

Figure 7. The sum over the paths is 13.

Example 8. Here we consider a second moment for a path set. Using the steps U, D, and (2, 0), for the elevated (Schröder) paths running from (0, 0) to (2n + 2, 0), we find that d_{n} is the sum, over its paths, of the average of the positive squared heights of the lattice points traced by each path.

Figure 8. Within each path the squared heights are additive. \frac{11}{5} + \frac{19}{5} + \frac{5}{5} +
\frac{8}{5} + \frac{8}{5} + \frac{14}{5} = \frac{65}{5} = d_{2}.

Example 9. We consider another second moment. Consider the elevated Schröder paths running from (0, 0) to (2n + 2, 0) where within each path the noninitial up step and the horizontal steps have weights 2 and −1, respectively. Here d_{n} is the sum of the weighted average of the positive squared heights of the lattice points traced by each path.

Figure 9. The sum over the paths is \frac{44}{5} + \frac{76}{5} + \frac{5}{5} + \frac{(−16)}{5} + \frac{(−16)}{5} + \frac{(−28)}{5} = d_{2}.

Example 10. We consider one more second moment. Take the elevated paths running from (0, 0) to (n + 2, 0) using the steps U, D, and (1, 0), where the noninitial U steps have weight 2 and the unit horizontal steps have weight 3. Here d_{n} is the sum of the weighted average of the positive squared heights of the lattice points traced by each path.

Figure 10. The sum over the paths is \frac{2(1+4+1)}{3} + \frac{3·3(1+1+1)}{3} = d_{2}.

Example 11. Here we will define a zebra to be a parallelogram polyomino whose noninitial columns are either white or gray. For any zebra, its average diagonal thickness squared will be the average of the squares of the number of unit cells along each –45 degree diagonal passing through the center of the cells. The sum, over all zebras of a fixed perimeter 2n + 4, of the average diagonal thickness squared is the Delannoy number d_{n}.

Figure 11. The sum of the average diagonal thickness squared is \frac{1+1+1}{3} + \frac{2(1+1+1)}{3} + \frac{2(1+4+1)}{3} + \frac{2(1+1+1)}{3} + \frac{4(1+1+1)}{3} = d_{2}.

Example 12. The number d_{n} counts the domino tilings of the Aztec diamond of width 2n having an additional center row.

Figure 12. d_{2} tilings.

Example 13. Consider counting matchings in the comb graph. For a comb with 2n teeth, there are d_{n} ways to have an n-set of non-adjacent edges.

Figure 13. The d_{2} 2-matchings in the comb with 2 · 2 teeth.

Example 14. In a lattice path using the steps U and D, a long, is a maximal subpath having at least two steps, all of the same type. The number d_{n} is the weighted sum over the paths running from (0, 0) to (2n + 1, 1) which begin with a U step and whose nonfinal longs have the weight 2.

Figure 14. The sum of the weights of the paths is 2 + 2 + 4 + 2 + 1 + 2 = d_{2}.

Example 15. Consider the walks that begin at the origin and use the unit steps: east (E), west (W), and north (N). If these walks never start with W and are self-avoiding, that is, E and W are nonadjacent, then d_{n} counts the walks with 2n steps and final height n.

Figure 15. d_{2} walks.

Example 16. The number d_{n} counts the ways to distribute n white and n black balls into r labeled urns where r takes on the values from n to 2n and where each urn is nonempty and does not contain more than one ball of each color. (The balls are unlabeled and are ordered so that white precedes black when two are present in an urn.)

Figure 16. d_{2} balls-in-urns distributions.

Example 17. The number d_{n} counts the words from the alphabet { a,b, {a,b} } where the total occurrences of a and b in each word is n.

{a, b}{a, b}, {a, b}ab, {a, b}ba, a{a, b}b, b{a, b}a, ab{a, b}, ba{a, b},
aabb, abab, abba, baab, baba, bbaa

Figure 17. d_{2} words.

Example 18. In ℤ^{n}, d_{n} counts the n-dimensional lattice points inside or on the hyperoctahedron with vertices on the axes located a distance n from the origin. More specifically, for z = (z_{1}, …, z_{n}) ∈ ℝ^{n}, let ||z||_{1} denote the norm ∑_{i=1}^{n} |z_{i}|. Then d_{n} = |{y ∈ ℤ^{n} : ||y||_{1} ≤ n}|.

Figure 18. For n = 2, d_{2} = 13 is the number of lattice points inside the square region {(x, y) : |x| + |y| ≤ 2}.

Example 19. The number d_{n} counts the set of paths using the three steps types, U, D, and (2, 0), running from (0, 0) to the line x = 2n, and remaining weakly above the x-axis.

Figure 19. The paths running from (0, 0) to the line x = 4 and remaining weakly above the x-axis.

Example 20. For the steps U and D, d_{n} is the weighted sum of the paths running from (0, 0) to the line x = 2n and remaining weakly above the x-axis, where within each path the right-hand turns have weight 2.

Figure 20. The sum of the weights of the paths is 4 + 2 + 1 + 2 + 2 + 2 = d_{2}.

Example 21. For the steps U and D, d_{n} is the weighted sum of the paths running from (0, 0) to the line x = 2n and remaining weakly above the x-axis, where within each path each long has weight 2. Here a long is a maximal subpath of the same step type of length exceeding one.

Figure 21. The sum of the weights of the paths is 1 + 4 + 2 + 2 + 2 + 2 = d_{2}.

Example 22. Consider the known array extending the large Schröder numbers: namely, for integers i and j, we define this array r_{i,j} to satisfy

r_{i,j} = r_{i−1,j} + r_{i,j−1} + r_{i−1,j−1}

with the conditions r_{0,0} = 1 and r_{i,j} = 0 if j < 0 or i < j. The members of the sequence (r_{i})_{i≥0} := (r_{i,i})_{i≥0} = 1, 2, 6, 22, 90 … are known as the large Schröder numbers. The central Delannoy number d_{n} is the sum of the 2n + 1-st diagonal, that is d_{n} = ∑_{i} r_{i,2n−i}.

r_{i,j} := \begin{matrix}i \ j & 0 & 1 & 2 & 3 & 4 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 2 & 0 & 0 & 0 \\ 2 & 1 & 4 & 6 & 0 & 0 \\ 3 & 1 & 6 & 16 & 22 & 0 \\ 4 & 1 & 8 & 30 & 68 & 90 \end{matrix}

Figure 22. An array of the extended large Schröder numbers. Here 1 + 6 + 6 = d_{2}.

Example 23. Let T (n) denote the set of plane trees with 2n + 1 edges, with roots of odd degree, with the non-root vertices having degree 1 (for the leaves), 2, or 3, and with an even number of vertices of degree two between any two vertices of odd degree.

Figure 23. The specified trees counted by d_{2}.

Example 24. A high peak is the intermediate vertex of a UD pair with ordinate exceeding 1. Let P(n, k) denote the set of paths using the steps U and D, running from (0, 0) to (n, 0), remaining weakly above the x-axis, intersecting the x-axis k times, and having high peaks of weight 2. Then the Delannoy number counts a union of sets:

d_{n} = |⋃_{i=1}^{n+1} P(2n + 2i, 2i)| .

Figure 24. 4 + 2 + 2 + 2 + 2 + 1 = d_{2}.

Example 25. A double ascent (or double rise) is just a consecutive UU pair. Let P(n, k) denote the set of paths using the steps U and D, running from (0, 0) to (n, 0), remaining weakly above the x-axis, intersecting the x-axis k times, and having double ascents of weight 2. Then the Delannoy number counts a union of sets:

d_{n} = |⋃_{i=1}^{n+1} P(2n + 2i, 2i)| .

Figure 25. 2 + 4 + 2 + 2 + 2 + 1 = d_{2}.

Example 26. Let P(n, k) denote the set of paths using the steps U and D, running from (0, 0) to (n, 0), remaining weakly above the x-axis, intersecting the x-axis k times, and evenly positioned ascents of weight 2. Then the Delannoy number counts a union of sets:

d_{n} = |⋃_{i=1}^{n+1} P(2n + 2i, 2i)| .

Figure 26. 4 + 2 + 2 + 2 + 2 + 1 = d_{2}.

Example 27. On a path using the steps U and D, a restricted long is a maximal subpath of a single step type having length exceeding 1, except when the subpath ends at the x-axis, in which case the length of the subpath must exceed 2. Let P(n, k) denote the set of paths using the steps U and D, running from (0, 0) to (n, 0), remaining weakly above the x-axis, intersecting the x-axis k times and having restricted longs of weight 2. Then the Delannoy number counts a union of sets:

d_{n} = |⋃_{i=1}^{n+1} P(2n + 2i, 2i)| .

Figure 27. 2 + 4 + 2 + 2 + 2 + 1 = d_{2}.

Example 28. The central Delannoy number d_{n} counts the matrices with 2 rows and entries 0 or 1 such that there are exactly n 1’s in each row and at least one 1 in each column.

[ \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ] [ \begin{matrix}1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix} ] [ \begin{matrix}1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix} ] [ \begin{matrix}1 & 1 & 0 \\ 0 & 1 & 1 \end{matrix} ] [ \begin{matrix}0 & 1 & 1 \\ 1 & 1 & 0 \end{matrix} ]

[ \begin{matrix}1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix} ]  [ \begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix} ]  [ \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{matrix} ]  [ \begin{matrix}1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{matrix} ]

[ \begin{matrix}1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{matrix} ] [ \begin{matrix}0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{matrix} ] [ \begin{matrix}0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix} ] [ \begin{matrix}0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{matrix} ]

Figure 28. There are d_{2} such matrices.

Example 29. The product 2^{n−1}d_{n} counts the matrices having two rows and nonnegative integer entries where each row sum is n and each column has at least one positive entry.

[ \begin{matrix}2 \\ 2 \end{matrix} ] [ \begin{matrix}2 & 0 \\ 0 & 2 \end{matrix} ] [ \begin{matrix}0 & 2 \\ 2 & 0 \end{matrix} ] [ \begin{matrix}2 & 0 & 0 \\ 0 & 1 & 1 \end{matrix} ] [ \begin{matrix}0 & 2 & 0 \\ 1 & 0 & 1 \end{matrix} ]

[ \begin{matrix}0 & 0 & 2 \\ 1 & 1 & 0 \end{matrix} ] [ \begin{matrix}0 & 1 & 1 \\ 2 & 0 & 0 \end{matrix} ] [ \begin{matrix}1 & 0 & 1 \\ 0 & 2 & 0 \end{matrix} ] [ \begin{matrix}1 & 1 & 0 \\ 0 & 0 & 2 \end{matrix} ]

[ \begin{matrix}2 & 0 \\ 1 & 1 \end{matrix} ]  [ \begin{matrix}0 & 2 \\ 1 & 1 \end{matrix} ]  [ \begin{matrix}1 & 1 \\ 2 & 0 \end{matrix} ]  [ \begin{matrix}1 & 1 \\ 0 & 2 \end{matrix} ]

Figure 29. 2 · d_{2} counts the set formed by these matrices and those of Figure 28.

3. Notes regarding verifications

Before reviewing the above examples, let us look at a mildly general lattice path model. For fixed positive integer h, we will allow the three steps U_{t}, D, and (h, 0)_{s} which are weighted by t, 1, and s, respectively. For n ≥ 0, let U(n) denote the set of all unrestricted paths running from (0, 0) to (n, 0), and let C(n) denote the set of paths in U(n) constrained never to pass beneath the horizontal axis. We will use a well-known decomposition of path sets to derive formulas for the generating functions c(z) := ∑_{n≥0} |C(n)|z^{n} and u(z) := ∑_{n≥0} |U(n)|z^{n}.

Since each path of C(n) must either (i) have zero length, (ii) start with an (h, 0) step followed by a constrained path, or (iii) start with an U step followed by the translation of a constrained path, then by a D, and finally by another constrained path we have

c(z) = 1 + sz^{h}c(z) + tz^{2}c(z)^{2}.

Since every path in U(n) either (i) has zero length, (ii) begins with an (h, 0) step followed by an unrestricted path, or (iii) begins with U (or with D) followed by a constrained path (or its reflection) which returns to the horizontal axis for the first time and then is followed by an unrestricted path,

u(z) = 1 + sz^{h}u(z) + 2tz^{2}c(z)u(z)

Solving these two equations simultaneously yields

u(z) = \frac{1}{\sqrt{(1 − sz^{h})^{2} − 4tz^{2}}} = \frac{1}{\sqrt{1 − 2sz^{h} + s^{2}z^{2h} − 4tz^{2}}} .

If this formula is to agree essentially with the formula of (1), then either h = 1 or h = 2. If h = 1, then u(z) = 1/\sqrt{1 − 2sz + (s^{2} − 4t)z^{2}}, and it must be that s = 3 and t = 2. On the other hand, if h = 2, then u(z) = 1/\sqrt{1 − (2s + 4t)z^{2} + s^{2}z^{4}}, and thus either s = t = 1 or s = −1 and t = 2.

We number the subsequent Notes to agree with the numbering of the examples of Section 2. Since the examples may serve as exercises and since they are ordered as collected, these notes may appear mildly haphazard.

Note 1 The introductory discussion of this section gives the generating function for Example 1. One can find an alternate derivation of the generating function and a recurrence in [20, Sect. 6]. Equation (3) can be obtained by considering all possible choices for the steps in the paths leading to (n, 0).

Note 2 That the Delannoy numbers count Example 2 follows from the initial discussion of this section. In Note 5 we will see how Example 2 is bijectively related to Example 1 via Examples 3 and 5.

Note 3 Replicate the paths from (0, 0) to (2n, 0) using the steps U and D by independently coloring their right-hand turns by blue or red. Replacing each consecutive blue UD by a (2, 0) step describes a bijection with Example 1.

Note 4 We will indicate a bijection from Example 4 to a reflected Example 3, reflected about the horizontal axis. The following proof is from the proof of [21, equation (5)]. We will also tilt our lattice paths by 45 degrees for the following.

Consider the steps N := (0, 1) and E := (1, 0). Let A(n) denote the set of all paths from (0, −1) to (n, n) which remain weakly above the horizontal axis except on the first step. A left turn is the intermediate point of a consecutive EN pair. Let A_{ℓ}(n) (A_{d}(n), resp.) denote the set of replicated paths formed from A(n) so each left turn (double ascent, resp.) is independently colored blue or red.

We have a bijection

F : A_{d}(n) ⟶ A_{ℓ}(n)

defined as follows: Let P ∈ A_{d}(n) be determined by the set (perhaps empty) of the coordinates of its left turns, namely {(x_{1}, y_{1}), …, (x_{k}, y_{k})}. Then (x′_{1}, y′_{1}), …, (x′_{h}, y′_{h}), …, (x′_{n−k}, y′_{n−k}) are the left turns of the path F (P) ∈ A_{ℓ}(n) (This was mistyped in [21].) where

{x′_{1}, …, x′_{n−k}} = {1, …, n} − {x_{1}, …, x_{k}}
{y′_{1}, …, y′_{n−k}} = {0, …, n − 1} − {y_{1}, …, y_{k}}

with x′_{1} < x′_{h} < x′_{n−k} and y′_{1} < y′_{h} < y′_{n−k} and the left turn at (x′_{h}, y′_{h}) has the color blue (red, resp.) if, and only if, y′_{h} is the ordinate of the intermediate vertex of a blue (red, resp.) double ascent on P.

See also Note 14.

Note 5 A. Each path in Example 5 is sequence of consecutive oddly-evenly positioned step pairs. The morphism sending UU to U, UD to (1, 0)_{2}, DU to (1, 0)_{1}, and DD to D (where its subscripts indicate the weights) determines a weight preserving bijection from Example 5 to Example 2.

B. We give a bijection from Example 5 to Example 1, which constitutes a combinatorial solution for the Monthly problem [22]. Our bijective proof is in the 45-degree tilted environment. In the following we will encode each path from each of the two examples as a triple of subsets of integers of the form (X, Y, H) where X := {x_{1}, …, x_{h}, …, x_{i}} ⊂ {1, …, n}, Y := {y_{1}, …, y_{h}, …, y_{i}} ⊂ {1, …, n}, and H := {h_{1}, …, h_{j}} ⊂ {1, …, i} where i and j depend on the path. Since there will be a unique encoding triple for each path from each model we will have a bijection.

Let A(n) denote the set of lattice paths from (0, 0) to (n, n) that permit four step types: the horizontal step (1, 0), the uncolored step (0, 1) where this vertical step may assume only even positions in a path, and the steps (0, 1)red or (0, 1)green where these vertical steps may assume only odd positions in a path. Any path in A(n) having i of its horizontal steps in the even positions, 2x_{1}, …, 2x_{h}, …, 2x_{i}, having necessarily i of its vertical steps in the odd positions, 2y_{1} −1, …, 2y_{h} −1, …, 2y_{i} −1, and having exactly j red steps in positions, 2y_{h_{1}} −1, …, 2y_{h_{j}} −1, can be encoded as (X, Y, H).

Let D(n) denote the set of lattice paths from (0, 0) to (n, n) that permit the three step types: (1, 0), (0, 1), and the diagonal, (1, 1). By replacing each diagonal step with a blue (0, 1)(1, 0) step pair (i.e., a blue right-hand turn), we can match each path in D(n) having j diagonal steps and i − j uncolored right-hand turns with a marked path from (0, 0) to (n, n) that uses the two steps, (1, 0) and (0, 1), and has marked right-hand turns. Each resulting marked path is determined by the coordinates of the intermediate vertices of its right-hand turns, say, (x_{1} −1, y_{1}), …, (x_{h} −1, y_{h}), … (x_{i} −1, y_{i}), where those turns corresponding to y_{h_{1}}, …, y_{h_{j}} are colored blue. Hence, each path can be encoded as (X, Y, H).

See also Note 14.

Note 6 This example appears as exercise [16, 6.16] where a generating function proof is indicated. A combinatorial proof, as requested in [16], appears in [21] and uses some of the bijections of these notes.

Note 7 That the Delannoy numbers count this example follows from the initial discussion of Section 3. Presently we have no ideas for bijective considerations.

Note 8 A generating function argument, and consequently, the recurrence (2) for Example 8 appear in [20]. The cut and paste bijection of [10] gives an immediate bijection between this example and Example 1.

Note 9 The cut and paste bijection [10] gives an immediate bijection between this example and Example 7.

Note 10 The cut and paste bijection [10] gives an immediate bijection between this example and Example 2. See Note 11.

Note 11 In [18] a zebra is defined as a parallelogram polyomino having all (not just the noninitial) columns colored either black or white. In [18] generation function methods show that the sum of the average of the squares of the diagonal thicknesses of all zebras of a fixed perimeter is twice a Delannoy number. By extending the known bijection given in [5] (See also [18, Sect. 5].), we have a bijection between the configurations of Example 11 and those of Example 10.

Note 12 Sachs and Zernitz [11] discovered this example and its solution, giving them in terms of counting perfect matchings. Stanley [16, Exercise 6.49] records Dana Randell’s restatement of the example and its solution in terms of Aztec diamonds.

Note 13 For m = 1, 2, 3, …, let COMB_{m} denote the comb graph with m teeth. This graph has vertex set {1, 2, …, 2m} and edge set

{{1, 2}, {3, 4}, …, {2m − 1, 2m}} ∪ {{2, 4}, {4, 6}, …, {2m − 2, 2m}} .

In addition to the example for d_{n}, Emeric Deutsch [6] discovered that the collection of sets of k pairwise nonadjacent edges of COMB_{m} has cardinality d_{k,m−k}. To see this one can establish a bijection from this collection to the collection of paths from (0, 0) to (k, m − k) using the steps (0, 1), (1, 0), (1, 1). In particular, this bijection maps a set with j edges of the type {2i, 2i + 2} to a path with j steps of type (1, 1).

Note 14 For Dyck paths (i.e., paths running from (0, 0) to (2n, 0), using the steps U and D, and never running below the x-axis) there are many statistics which are distributed by the Narayana numbers [17]: namely, for 1 ≤ k ≤ n,

\frac{1}{n}\binom{n}{k − 1}\binom{n}{k}.

The three classic statistics are (i) the number of peaks (This is immediately equivalent both to number of valleys plus one and to the number of double ascents plus one.), (ii) the number of ascents which are oddly positioned along the path, and (iii) the number of nonfinal longs plus one. (See Examples 3, 4, and 5. The plus one term is unavoidable – it is in agreement with the need for both small and large Schröder numbers. (See [19].)

For unrestricted paths, if one assign a weight of 2 to each object (or substructure) counted by those statistics, computes the weight of each path, and then sums over the paths of a given length, one arrives at the Delannoy number as in Examples 3, 4, 5, and 14. That the assignment of the weight 2 to each objects counted by certain statistics yields a Delannoy number is in agreement with equation (4).

Kreweras and Moszkowski [7] introduced the number of nonfinal longs statistic for Dyck paths. Benchekroun and Moszkowski [2] then gave a bijective proof that this statistic indeed has the Narayana distribution: The number of Dyck paths of length 2n, having k nonfinal longs is

|D(n, k)| = \frac{1}{n}\binom{n}{k}\binom{n}{k + 1}.  (5)

We use their proof to obtain a bijection between Example 14 and a modified Example 3, modified as to be in terms of left-hand turns (i.e., valleys, not peaks). To obtain the domain for this bijection we tilt the paths of Example 14 to run from (0, −1) to (n, n) weakly above the x-axis except on the first step and to use the steps (0, 1) and (1, 0). The codomain will be the set of paths from (0, 0) to (n, n) with the unit steps (0, 1) and (1, 0). If (x_{1}, y_{1}), ..., (x_{h}, y_{h}), ..., (x_{j}, y_{j}) denote the locations of the next to the final lattice points on the long steps of a path in the domain, then (x_{1} + 1, y_{1}), ..., (x_{h} + 1, y_{h}) , ..., (x_{j} + 1, y_{j−h}) will be the locations of the left-hand turns of the image path.

Note 15 Louis Shapiro [13] discovered this example. A bijection with the tilted version of Example 1 can be established recursively. Let W(x, y) denote the set of lattice walks of the Example 15 that have x + y steps and final height y. Let U(x, y) denote the set of lattice path running from (0, 0) to (x, y) that use the steps E := (1, 0), N := (0, 1), and D := (1, 1). We define f := W(x, y) → U(x, y) so that f(P E) = f(P)E, f(P W W) = f(P W)E, f(P NW) = f(P)D, and f(P N) = f(P)N. With the obvious boundary conditions for x = 0 or y = 0, f can be shown to be bijective.

Note 16 This and the next example were found by Sylviane Schwer [12] and her interest in the Delannoy numbers resulted in [1]. More generally, she considered unlabeled balls of m colors with p_{i} balls having color i, for i = 1 … m. For ℓ = max(p_{1}, p_{2}, …, p_{m}) and u = p_{1} + p_{2} + ⋯ + p_{m}, she made available u − ℓ + 1 collections of urns where each collection has r urns, labeled by 1, 2, …, r, for ℓ ≤ r ≤ u. With D(p_{1}, p_{2}, …, p_{m}) denoting the ways to distribute the balls so that in each urn there is a ball and no two balls have the same color, she showed that D(p_{1}, p_{2}, …, p_{m}) is isomorphic to the lattice paths in m-space that run from (0, 0, …, 0) to (p_{1}, p_{2}, …, p_{m}) using the nonzero steps of the form (ϵ_{1}, ϵ_{2}, …, ϵ_{m}) where ϵ_{i} ∈ {0, 1}. (See [14] for a discussion of multidimensional Delannoy numbers.)

Note 17 Continuing from note 16, Schwer formulated the enumeration of possible words which take as their alphabet nonempty subsets of some set X = {x_{1}, x_{2}, …, x_{m}}. If ||f||_{x} denotes the number of occurrences of x in the subsets forming a word f, then the Parikh vector of f is denoted by (||f||_{x_{1}}, ||f||_{x_{2}}, …, ||f||_{x_{m}}). The set of words with a Parikh vector equal to (p_{1}, p_{2}, …, p_{m}) has the cardinality of D(p_{1}, p_{2}, …, p_{m}).

Note 18 This example was found by M. Vassilev and K. Atanassov[23]. See Math Rev.: 96b:05004. More generally, their paper proves that d_{p,q} counts {y ∈ ℤ^{p} : ||y||_{1} ≤ q}.

Note 19 Let P(x_{0}) denote the set of unweighted paths using the steps, (1, 1) and (1, −1), beginning at (0, 0), ending on the line x = x_{0}, and remaining weakly above the x-axis. Then

|P(2k)| = \binom{2k}{k}.  (6)

To see (6), we first observe that the manner in which the paths of P (2k −1) can be appended to form paths of P(2k) implies |P(2k)| = 2|P(2k−1)|. Likewise, |P(2k−1)| = 2|P(2k−2)|− c_{k−2}, where c_{k−2} = \binom{2k−2}{k−1}/k is the Catalan number counting the paths in P(2k − 2) which terminate at (k − 2, 0). Since the central binomial coefficient satisfies \binom{2k}{k} = 4\binom{2k−2}{k−1} − 2c_{k−2},

(6) follows inductively.

To verify this example we count the ways to insert n − k (2, 0)-steps into any path of P(2k). Hence,

∑_{k} \binom{2k}{k}\binom{n + k}{n − k} = ∑_{k} \frac{(2n)!}{k!k!(n − k)!} = ∑_{k} \binom{n}{k}\binom{n + k}{k} = d_{n}.

Note 20 Example 20 follows by labeling the peaks of Example 19 red and replacing the (2, 0)-steps by a blue (1, 1)(1, −1) pair. It would be interesting to find a bijection involving an even earlier example.

Note 21 Let D(n, k) denote the set of lattice paths running from (0, 0) to (n, 0), using the steps U and D, never passing beneath the x-axis, and having k non-final longs. By Note 14, |D(n, k)| has the the Narayana distribution. Let L(n, k) denote the set of lattice paths running from (0, 0), having n steps of types U and D, never passing beneath the x-axis, and having k longs.

Since ∪_{n>0}D(n, k) can be decomposed with respect to the point of first return to the x-axis, we have, for d := d(x, t) = ∑_{n≥0} ∑_{k≥0} |D(n, k)|t^{k}x^{n},

d = 1 + x^{2}d + x^{2}t(d − 1 + (t − 1)x^{2}d)(d − 1) + x^{2}(d + (t − 1)x^{2}d).  (7)

Here the next-to-the-last term corresponds to an intermediate first return to the x-axis; hence the first t is required to count the nonfinal long assumed by the D steps at that return. The (t − 1)x^{2} factors assure that initial double ascents followed by D steps are counted as being long.

Since ∪_{n>0}L(n, k) can be decomposed with respect to whether or not paths return to the x-axis for a last time, we have, for ℓ := ∑_{n≥0} ∑_{k≥0} |L(n, k)|t^{k}x^{n},

ℓ = 1 + x^{2}ℓ + x^{2}t(d − 1 + (t − 1)x^{2}d)ℓ + x(ℓ + (t − 1)x + (t − 1)x^{2}ℓ).  (8)

The factors t, (t − 1)x, and (t − 1)x^{2} are required somewhat as indicated in the above paragraph. Equations (7) and (8) easily yield, with the middle formula discounting paths of odd length,

∑_{n} ∑_{k} |L(2n, k)|2^{k}x^{n} = \frac{ℓ(z, 2) + ℓ(−z, 2)}{2} = \frac{1}{\sqrt{1 − 6z^{2} + z^{4}}} .

Note 22 The reader can establish a simple bijection between the paths giving the counts in this array and the paths of Example 19.

Note 23 Emeric Deutsch [6] contributed this example, which in turn motivated Examples 24 through 27. Essentially these examples consist of attaching a root of odd degree to a list of structures counted by the large Schröder numbers. One can establish a generating functional proof for this example similar to that of Note 24.

Note 24 Let D(n, k) denote the set of lattice paths running from (0, 0) to (n, 0), using the steps U and D, never passing beneath the x-axis, and having k peaks. If d := d(x, t) = ∑_{n≥0} ∑_{k≥0} |D(n, k)|t^{k}x^{n}, one can decompose the paths with respect to the first return to the x-axis to show

d = 1 + tx^{2}d + x^{2}(d − 1)d.

For t = 2,

d(x, 2) = \frac{1 − x^{2} − \sqrt{1 − 6x^{2} + x^{4}}}{2x^{2}} ,

which is the generating function for the large Schröder numbers.

Let P(2n + 2i, 2i) be as in the statement of Example 24. Since the paths of P(2n + 2i, 2i) are the concatenations of 2i − 1 elevated paths, each of which has generating function x^{2}d = x^{2}d(x, 2), we have

∑_{m≥0} |P(2m, 2i)|x^{2} = (x^{2}d)^{2i−1}.

Hence,

∑_{n≥0} ∑_{i≥1} |P(2n + 2i, 2i)|x^{2n} = ∑_{i≥1} x^{−2i} ∑_{n≥0} |P(2n + 2i, 2i)|x^{2n+2i},

which is equal

∑_{i≥1} x^{−2i}(x^{2}d)^{2i−1} = ∑_{j≥0} x^{2j}d^{2j+1} = \frac{d}{1 − x^{2}d^{2}} = \frac{1}{\sqrt{1 − 6x^{2} + x^{4}}} .

Note 25 Refer to Notes 23 and 24.

Note 26 Refer to Notes 23 and 24.

Note 27 Refer to Notes 23 and 24.

Note 28 The reader can establish a simple bijection between this example and Example 1 or 16.

Note 29 The reader can establish a simple bijection between this example and Example 6.

References

[1] C. Banderier and S. Schwer, Why Delannoy numbers?, Preprint, 2002

   hhtp://algo.inria.fr/banderier

[2] S. Benchekroun and P. Moszkowski, A bijective proof of an enumerative property of legal bracketings, Eur. J. Combin. 17 (1996) 605–611.

[3] L. Comtet, Advanced Combinatorics, D. Reidel Publishing Co., 1974.

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

[5] M-P. Delest and G. Viennot, Algebraic languages and polyominoes enumeration. Theoret. Comput. Sci. 34 (1984), 169–206.

[6] E. Deutsch, private communications, June and July, 2002.

[7] G. Kreweras and P. Moszkowski, A new enumerative property of the Narayana numbers, J. Stat. Plann. Inference 14 (1986), 63–67.

[8] D.F. Lawden, On the solution of linear difference equations. Math. Gaz. 36 (1952), 193–196.

[9] L. Moser and W. Zayachkowski, Lattice paths with diagonal steps, Scripta Math. 26 (1963), 223–229.

[10] E. Pergola, R. Pinzani, S. Rinaldi, and R. A. Sulanke, Lattice path moments by cut and paste, To appear, Adv. in Appl. Math., 2003.

[11] H. Sachs and H. Zernitz, Remark on the dimer problem. Disc. Appl. Math. 51 (1994), 171–179.

[12] S.R. Schwer, S-arrangements avec répétitions, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 1–6.

[13] L. Shapiro, private communication, July 2002.

[14] S. Kaparthi and H.R. Rao, Higher-dimensional restricted lattice paths with diagonal steps. Disc. Appl. Math. 31 (1991), 279–289.

[15] N.J.A. Sloane, On-Line Encyclopedia of Integer Sequences,

   http://www.research.att.com/~njas/sequences/

[16] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[17] R. A. Sulanke, Catalan path statistics having the Narayana distribution, Disc. Math. 180 (1998), 369– 389.

[18] R. A. Sulanke, Three recurrences for parallelogram polyominoes, J. of Difference Eq. and its Appl. 5 (1999), 155–176.

[19] R. A. Sulanke, The Narayana distribution, J. Statist. Plann. Inference 101 (2002), 311–326.

[20] R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Seq., Vol. 3 (2000), Article 00.1.1 [21] R. A. Sulanke, Counting lattice paths by Narayana polynomials, Electron. J. Comb., 7 (1), (2000),

#R40.

[22] R. A. Sulanke, Problem 10894, Amer. Math. Monthly 108 (2001), 770.

[23] M. Vassilev and K. Atanassov, On Delanoy [sic] numbers, Annuaire Univ. Sofia Fac. Math. Inform. 81 (1994) 153–162.

2000 Mathematics Subject Classification: 05A15 Keywords: Delannoy numbers, lattice paths, Narayana numbers, Schröder numbers.

(Concerned with sequence \underline{A001850}.)

Received November 13, 2002; revised version received February 12, 2003. Published in Journal of Integer Sequences March 2, 2003.

Return to Journal of Integer Sequences home page.

Boise State University, Boise, ID, 83725, USA.

  E-mail address: sulanke@math.boisestate.edu