Séminaire Lotharingien de Combinatoire 51 (2004), Article B51c

The 2^{n−1} factor for multi-dimensional lattice paths with diagonal steps

E. Duchi^{∗} and R. A. Sulanke^{†}

Abstract In ℤ^{d}, let D(n) denote the set of lattice paths from the origin to (n, n, …, n) that use nonzero steps of the form (x_{1}, x_{2}, …, x_{d}) where x_{i} ∈ {0, 1} for 1 ≤ i ≤ d. Let S(n) denote the set of lattice paths from the origin to (n, n, …, n) that use nonzero steps of the form (x_{1}, x_{2}, …, x_{d}) where x_{i} ≥ 0 for 1 ≤ i ≤ d. For d = 3, we prove bijectively that the cardinalities satisfy |S(n)| = 2^{n−1}|D(n)| for n ≥ 1. One can extend our method to any dimension and obtain the same identity. We find an explicit formula for |D(n)| when d = 3.

Key words: Lattice paths, Delannoy numbers.

1 Introduction

In d-dimensional space ℤ^{d}, consider a lattice path to be represented as a concatenation of directed steps. Let D(n) denote the set of paths from (0, 0, …, 0) to (n, n, …, n) using nonzero steps of the form (x_{1}, x_{2}, …, x_{d}) where x_{i} ∈ {0, 1} for 1 ≤ i ≤ d. These steps are the positive steps, including the diagonal ones, between vertices of a unit hypercube. Let S(n) denote the set of paths from (0, 0, …, 0) to (n, n, …, n) using the steps of the form (x_{1}, x_{2}, …, x_{d}) where the x_{i}’s are nonnegative integers, not all zero. The paths of S(n) correspond to MacMahon’s [6, sect. IV] “compositions of the multipartite number (n, n, …, n)”.

Our main result is a bijective proof that, for any dimension and for n ≥ 1, the cardinalities |D(n)| and |S(n)| satisfy

|S(n)| = 2^{n−1}|D(n)|.  (1)

∗Dipartimento di Sistemi e Informatica, Università di Firenze, Firenze, It. duchi@dsi.unifi.it

†Dept. of Mathematics, Boise State University, Boise, ID, U.S.A. sulanke@math.boisestate.edu

In the 2-dimensional case, the numbers (|D(n)|)_{n≥0} = 1, 3, 13, 63, 321, 1683, 8989, … are the central Delannoy numbers with |D(n)| = ∑_{0≤k≤n} \binom{n}{k}^{2}2^{k}. For d = 2, explicit formulas and generating functions for (|D(n)|)_{n≥0} and (|S(n)|)_{n≥0} appear under A001850 and A052141 in [7]. For d = 2, identity (1) appears in an exercise in Stanley [8, Exercise 6.16] with a bijective proof appearing in [9]. Recently, Humphreys and Niederhausen [3] applied techniques of the umbral calculus to obtain (1) for d = 2. For further information regarding the Delannoy numbers, see the historical note on the work and life of Henri Delannoy given by Banderier and Schwer [1]. See also the collection of 29 configurations counted by the Delannoy numbers given by Sulanke [10]. Recently, he [11] has used different bijective techniques to show that identity (1) holds for any dimension when the sets D(n) and S(n) are restricted to contain those paths lying in the region {(x_{1}, x_{2}, …, x_{d}) : x_{1} ≤ x_{2} ≤ … ≤ x_{d}}.

For dimension d = 3 and n ≥ 0, formula (4) of Section 9 yields

|D(n)| = ∑_{i=0}^{n} ∑_{j=0}^{n−i} ∑_{k=0}^{n} \binom{n}{i}\binom{n − i}{j}\binom{n}{k}\binom{n + i}{i + j}\binom{n}{i + k}2^{i+j+k}.

One then finds that

(|D(n)|)_{n≥0} = 1, 13, 409, 16081, 699121, 32193253, 1538743249, …
(|S(n)|)_{n≥0} = 1, 13, 818, 64324, 5592968, 515092048, 49239783968, …

With the notation of Section 2, we prove identity (1) for dimension d = 3 by a series of bijections in a manner that can be routinely extended to any dimension:

S(n) ⟶ L′(n) ⟶ L^{∗}(n) × 2^{[n−1]} ⟶ ZL^{∗}(n) × 2^{[n−1]} ⟶ ZL^{∗∗}(n) × 2^{[n−1]}
⟶ Y L^{∗∗}(n) × 2^{[n−1]} ⟶ L′′(n) × 2^{[n−1]} ⟶ D(n) × 2^{[n−1]},  (2)

where 2^{[n−1]} is the power set of [n−1] = {1, 2, …, n−1}. In Section 2 we give an explanation of our notation and a more extensive overview of our proof of identity (1). Sections 3 through 8 define the bijections used in (2).

In the final section we consider the set of lattice paths from the origin to (n_{1}, n_{2}, n_{3}) using the unit steps X, Y, and Z. We discuss some statistics for paths in this set. We then generalize these statistics and outline the proof of identity (1) for dimensions d > 3. We briefly examine a generalization of identity (1) for the non-central case. For completeness, we mention some results on generating functions which appeared in MacMahon’s work [6].

2 Notation and overview of proof

From the context it will be clear whether the notation (x, y, z) denotes a point in ℤ^{3} or denotes a step from an arbitrary point (x_{0}, y_{0}, z_{0}) to the point (x_{0} +x, y_{0} +y, z_{0} +z). We will denote the unit steps as X, Y, and Z, where X = (1, 0, 0), Y = (0, 1, 0), and Z = (0, 0, 1).

Let L(n) denote the set of lattice paths from (0, 0, 0) to (n, n, n) using the unit steps X, Y, and Z. For any path, in order to mark the intermediate vertex between two adjacent steps S_{i} and S_{i+1} by a color c, c ∈ {b, r} = {blue, red}, we will replace S_{i}S_{i+1} by S_{i}cS_{i+1} in the concatenation representing the path.

Table 1 summarizes the notation for the various sets of lattice paths used in the proof. In the table, the term “section” refers to the section where the notation first appears. The phrase “colored pairs” refers to those step pairs having independently colored blue or red intermediate vertex. All other intermediate vertices and the point (n, n, n) are red. Notice that path sets with the same superscripting (i.e., asterisk, double asterisks, and double prime) have essentially the same vertex coloring schemes.

set  section steps  initial  final  colored pairs
used  point  point
L(n)  §2  X, Y, Z (0, 0, 0) (n, n, n)
L′(n)  §3  X, Y, Z (0, 0, 0) (n, n, n) XX, Y X, Y Y, ZX, ZY, ZZ
L^{∗}(n)  §4  X, Y, Z (0, 0, 0) (n, n, n)  Y Y, ZY, ZZ
ZL(n)  §5  X, Y, Z (0, 0, −1) (n, n, n)
ZL^{∗}(n)  §5  X, Y, Z (0, 0, −1) (n, n, n)  Y Y, ZY, ZZ
Y L_{2}(n)  §6  X, Y (0, −1, 0) (n, n, 0)
ZL_{2}(n)  §6  X, Z (0, 0, −1) (n, 0, n)
ZL^{∗∗}(n)  §7  X, Y, Z (0, 0, −1) (n, n, n) Y Y, ZY, non-origin ZX
Y L(n)  §7  X, Y, Z (0, −1, 0) (n, n, n)
Y L^{∗∗}(n)  §7  X, Y, Z (0, −1, 0) (n, n, n)  Y Y, ZX, ZY
Y L′′(n)  §7  X, Y, Z (0, −1, 0) (n, n, n) ZX, ZY, non-origin Y X
L′′(n)  §7  X, Y, Z (0, 0, 0) (n, n, n)  Y X, ZX, ZY

Table 1: Notation for path sets

This and the following paragraphs indicate an overview of our proof of identity (1). Through a series of bijections in Sections 3, 4, and 5, we encode each path in S(n), which uses steps of arbitrary length, by a pair, say (ZP^{∗}, A), where ZP^{∗} ∈ ZL^{∗}(n) and A is a subset of [n − 1]. On any path P′ ∈ L′(n), ignoring the first X step on any path, the set A encodes the coloring of the remaining n − 1 initial vertices of the X steps on P′. It is the cardinality of the collection of all such subsets which accounts for the factor 2^{n−1} of identity (1).

In Sections 6 and 7, we transform each path ZP^{∗} ∈ ZL^{∗}(n) into a path ZP^{∗∗} ∈ ZL^{∗∗}(n). Essentially, the colors on the intermediate vertices of the ZZ’s move to the non-origin vertices of ZX’s while the colors on the intermediate vertices of the Y Y ’s and ZY ’s are preserved under the transformation ZL^{∗}(n) ⟶ ZL^{∗∗}(n). To make this transformation we first keep unaltered, as labeling words, the Y steps and the colors appearing between successive (not necessarily adjacent) steps of types X and Z. E.g., we have underlined the labeling words in the following path:

Z\underline{b}Z\underline{bY bY rY r}X\underline{r}X\underline{r}X\underline{r}Z\underline{bY r}Z\underline{r}Z\underline{b}Z\underline{r}X\underline{r} ∈ ZL^{∗}(n).

We next project the path ZP^{∗} orthogonally onto the x-z-plane so that the labeling words become labels for intermediate vertices of the ZZ, ZX, XZ, and XX pairs on the resulting 2-dimensional path. Using the maps of Section 6, we then transform this 2-dimensional path to a new 2-dimensional path so that each ZZ pair, together with its labeling word, maps to a ZX pair, and vice-versa, and so that all other labeling words map similarly. Finally, we expand the labeling words on the new 2-dimensional path to obtain a 3-dimensional path ZP^{∗∗} ∈ ZL^{∗∗}(n).

After changing the initial step from Z to Y, analogously we transform each Y P^{∗∗} to a path P′′ ∈ L′′(n). We complete the proof of (1) in Section 8 by transforming each path P′′ into a path belonging to D(n) by changing blue colored step pairs and triples (i.e., ZbY bX) into diagonal steps.

3 The bijection S(n) to L′(n)

Let L′(n) denote the set of paths formed from the paths of L(n) by independently coloring with b and r the intermediate vertices of XX, Y X, Y Y, ZX, ZY, and ZZ, and by coloring with r the other intermediate vertices.

We define the bijection

α : S(n) ⟶ L′(n)

to be a morphism that sequentially applies the following replacement rules to each path: for x > 0, y > 0, and z > 0,

\begin{matrix}(x, 0, 0) & ⟶ & X(bX)^{x−1} \\ (0, y, 0) & ⟶ & Y (bY)^{y−1} \\ (0, 0, z) & ⟶ & Z(bZ)^{z−1} \\ (x, y, 0) & ⟶ & Y (bY)^{y−1}(bX)^{x} \\ (x, 0, z) & ⟶ & Z(bZ)^{z−1}(bX)^{x} \\ (0, y, z) & ⟶ & Z(bZ)^{z−1}(bY)^{y} \\ (x, y, z) & ⟶ & Z(bZ)^{z−1}(bY)^{y}(bX)^{x}, \end{matrix}

and then assigns color r to all non-b intermediate vertices on the resulting path. Here the exponents indicate multiple factors in the concatenation; the color b marks intermediate vertices. See Examples 1 and 2 in the following section. (One might glean the bijection α from an encoding for compositions of tripartite numbers given by MacMahon [6, sect. IV].)

4 The bijection L′(n) to L^{∗}(n) × 2^{[n−1]}

Let L^{∗}(n) denote the set of paths formed from the paths of L(n) by independently coloring with b and r the intermediate vertices of all Y Y, ZY, and ZZ pairs together with all vertices (0, 0, 0) that precede a Y or Z step. All other vertices, including (n, n, n) are red.

We now define a bijection

β : L′(n) ⟶ L^{∗}(n) × 2^{[n−1]}.

For P′ ∈ L′(n), let (P^{∗}, A) = β(P′), where

(i) The path P^{∗} traces the same points in ℝ^{3} as P′ does. Momentarily, give P^{∗} the coloring of P′.

(ii) If the first occurrence of an X step in the path P′ in L′(n) is immediately preceded by a b vertex, then color the point (0, 0, 0) on P^{∗} by b; if otherwise, color it by r.

(iii) Let A be the set of all i, 1 ≤ i ≤ n − 1, for which the initial vertex of the (i + 1)-st X on P′ is red. Equivalently, A is the set of all x, x > 0, such that (x, y, z) is an r colored initial vertex of an X step on P′.

(iv) Color red all the intermediate vertices of XX, XY, XZ, Y X, Y Z, and ZX pairs, together with (n, n, n) on P^{∗}. (Items (ii) and (iii) preserve any lost information.)

Example 1 If S = (0, 2, 1)(2, 1, 0)(1, 1, 1)(1, 0, 2) ∈ S(4), then

α(S) = P′ = ZbY bY rY bXbXrZbY bXrZbZbX ∈ L′(4)

and P^{∗} = bZbY bY rY rXrXrZbY rXrZbZrXr ∈ L^{∗}(4) with A = ∅. Here the origin is blue since the first X in P′ has a blue initial vertex; A = ∅ since none of the following X’s in P′ have a red initial vertex. This example will continue through the paper.

Example 2 If S = (0, 2, 1)(2, 0, 0)(1, 0, 0)(1, 2, 3), then

α(S) = P′ = ZbY bY rXbXrXrZbZbZbY bY bX ∈ L′(4)

and P^{∗} = rZbY bY rXrXrXrZbZbZbY bY rXr ∈ L^{∗}(4). Here the origin is red since the first X in P′ has a red initial vertex; also A = {2} since the third X in P′ has a red initial vertex.

5 Labeling words and the bijection ϵ : L^{∗}(n) to ZL^{∗}(n)

Let ZL(n) denote the set of paths using the steps X, Y, and Z, beginning with a Z step and running from (0, 0, −1), through (0, 0, 0), and on to (n, n, n). Let ZL^{∗}(n) denote the set of paths formed from the paths of ZL(n) by independently coloring with b and r the intermediate vertices of all Y Y, ZY, and ZZ pairs.

Here we introduce the notion of a labeling word and then define a simple bijection. Suppose that P^{∗} ∈ L^{∗}(n) is factored as

P^{∗} = Y_{0}S_{1}Y_{1}S_{2}Y_{2} ⋯ S_{i}Y_{i} ⋯ S_{2n}Y_{2n}

where

(i) S_{i} ∈ {X, Z} for 1 ≤ i ≤ 2n,

(ii) Y_{i} is a subpath that is just a color or appears as Y_{i} = c_{i0}Y c_{i1}Y c_{i2} ⋯ Y c_{ij_{i}} with c_{ih} ∈ {b, r}, for 0 ≤ h ≤ j_{i}, for 0 ≤ i ≤ 2n. We will refer to any such subpath as a labeling word.

(iii) Y_{0} = c_{00}Y c_{01}Y c_{02} ⋯ Y c_{0j_{0}} with c_{0h} ∈ {b, r}, for 0 ≤ h ≤ j_{0} if P^{∗} begins with a Y step,

(iv) Y_{0} = c_{00} if P^{∗} begins with an X or Z step.

We define a simple bijection:

ϵ : L^{∗}(n) ⟶ ZL^{∗}(n).

where

ϵ(P^{∗}) = ZP^{∗} = ZY_{0}S_{1}Y_{1}S_{2}Y_{2} ⋯ S_{i}Y_{i} ⋯ S_{2n}Y_{2n}  (3)

where the initial Z begins at (0, 0, −1). In effect, the notation of this section has mapped a path in L^{∗}(n) to a 2-dimensional path in the x − z plane with the labeling words marking the new path’s vertices.

Example 3 This continues Example 1. With the labeling words Y_{0} = b, Y_{1} = bY bY rY r, Y_{4} = bY r, Y_{6} = b, and Y_{2} = Y_{3} = Y_{5} = Y_{7} = Y_{8} = r,

ϵ(P^{∗}) = ϵ(bZbY bY rY rXrXrZbY rXrZbZrXr) = ZY_{0}ZY_{1}XY_{2}XY_{3}ZY_{4}XY_{5}ZY_{6}ZY_{7}XY_{8}.

6 Auxiliary bijections for two-dimensional paths.

Let Y L_{2}(n) denote the set of 2-dimensional paths restricted to the plane z = 0 using the steps X and Y and running from (0, −1, 0), through (0, 0, 0), to (n, n, 0). Similarly, let ZL_{2}(n) denote the set of paths restricted to the plane y = 0 using the steps X and Z and running from (0, 0, −1), through (0, 0, 0), to (n, 0, n).

For paths in Y L_{2}(n) (in ZL_{2}(n), resp.),

• A double rise is the intermediate vertex of a consecutive Y Y pair (ZZ, resp.).

• A non-origin descent is the intermediate vertex of a consecutive Y X (ZX, resp.) that is not (0, 0, 0).

• An otherwise point is an intermediate vertex which is absent from the above categories or the final vertex on a path. An ascent, i.e., the intermediate vertex of a consecutive XY (XZ, resp.), is an example of an otherwise point.

We now introduce two bijections for paths in the plane which will be applied in the following section. We define the first, denoted by δ_{y}, and indicate that the second, denoted by δ_{z}, is defined similarly.

Lemma 1 For any k, 0 ≤ k ≤ n, there is a bijection denoted as

γ_{1} : {P ∈ Y L_{2}(n) : P has k ascents }
⟶ {P ∈ Y L_{2}(n) : P has n-k ascents }.

To define this bijection, let P ∈ Y L_{2}(n) with k ascents, located at (x_{1}, y_{1}) … (x_{k}, y_{k}). These ascents completely determine P. Let (x′_{1}, y′_{1}), …, (x′_{n−k}, y′_{n−k}) be the increasing sequence of points satisfying

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

As ascents, the vertices (x′_{1}, y′_{1}), …, (x′_{n−k}, y′_{n−k}) completely determine the path γ_{1}(P) in a manner yielding the lemma. □

Lemma 2 For any P ∈ Y L_{2}(n), P has k double rises if, and only if, it has n − k ascents. Hence,

γ_{1} : {P ∈ Y L_{2}(n) : P has k double rises }
⟶ {P ∈ Y L_{2}(n) : P has k ascents }.

This from the fact that each noninitial Y step is preceded by either a Y or an X step and from Lemma 1. (Such a result fails on L_{2}(n); the Y at the start of each path in Y L_{2}(n) is required.) □

Lemma 3 For any k, 0 ≤ k ≤ n, there is a bijection denoted as

γ_{2} : {P ∈ Y L_{2}(n) : P has k ascents }
⟶ {P ∈ Y L_{2}(n) : P has k non-origin descents }.

For each P ∈ Y L_{2}(n), reflect about the line y = x the subpath of P running from (0, 0) to (n, n). □

Lemma 4 For any k, 0 ≤ k ≤ n, there is a bijection, δ_{y} : Y L_{2}(n) → Y L_{2}(n), such that P ∈ Y L_{2}(n) has j non-origin descents if, and only if, δ_{y}(P) has j double rises. Likewise, there is a bijection, δ_{z} : ZL_{2}(n) → ZL_{2}(n), such that P ∈ ZL_{2}(n) has j non-origin descents if, and only if, δ_{z}(P) has j double rises.

To see this for δ_{y}, define (δ_{z} is defined analogously.)

δ_{y} = γ_{2} ∘ γ_{1} : {P ∈ Y L_{2}(n) : P has k double rises}
⟶ {P ∈ Y L_{2}(n) : P has k non-origin descents}. □

A note on indexing the vertices of the paths of Y L_{2}(n) and ZL_{2}(n): For each path of Y L_{2}(n) having k double rises, index the intermediate vertices of its double rises by assigning 1, …, k, in order of their position on the path. Likewise, index its j non-origin descents by 1, …, j and index its otherwise points by 1, 2, …, in order of position on the path.

Example 4 In the case of δ_{z} we have δ_{z}(ZZXXZXZZX) = γ_{2}(γ_{1}(ZZXXZXZZX)) = γ_{2}(ZXZZZXXXZ) = ZZXXXZZZX, where the analog of Lemma 1 uses (x_{1}, z_{1}) = (2, 1), (x_{2}, z_{2}) = (3, 2), (x′_{1}, z′_{1}) = (1, 0), and (x′_{2}, z′_{2}) = (4, 3). Let Y_{0}, Y_{1}, …, Y_{8} denote vertex labels on the path. Requiring that the labels of the double rises maps sequentially to the labels of the non-origin descents, etc., we have

δ_{z}(ZY_{0}ZY_{1}XY_{2}XY_{3}ZY_{4}XY_{5}ZY_{6}ZY_{7}XY_{8}) = ZY_{1}ZY_{0}XY_{2}XY_{3}ZY_{5}XY_{4}ZY_{7}ZY_{6}XY_{8}.

7 The bijection ZL^{∗}(n) to L′′(n)

In any of the following colored paths, all unspecified intermediate vertices and the final vertex are colored r.

Let ZL^{∗∗}(n) denote the set of paths formed from the paths of ZL(n) by independently coloring with b and r the intermediate vertices of all Y Y, ZY, and non-origin ZX pairs (i.e., those ZX pairs whose intermediate vertex is not the origin).

Let Y L(n) denote the set of paths using the steps X, Y, and Z, beginning with a Y step and running from (0, −1, 0), through (0, 0, 0), and on to (n, n, n).

Let Y L^{∗∗}(n) denote the set of paths formed from the paths of Y L(n) by independently coloring with b and r the intermediate vertices of all Y Y, ZX, and ZY pairs.

Let Y L′′(n) denote the set of paths formed from the paths of Y L(n) by independently coloring with b and r the intermediate vertices of all ZX, ZY, and non-origin Y X pairs (i.e., those Y X pairs whose intermediate vertex is not the origin).

Let L′′(n) denote the set of paths formed from the paths of L(n) by independently coloring with b and r the intermediate vertices of Y X, ZX, and ZY.

We first define a bijection

η_{1} : ZL^{∗}(n) ⟶ ZL^{∗∗}(n)

(i) by first projecting orthogonally each path in ZL^{∗}(n), expressed as in the right side of (3), onto a path in ZL_{2}(n) in the x − z plane, so that the labeling words Y_{0}, Y_{1}, …, Y_{i}, …,Y_{2n}, (defined in Section 5) are contracted to become labels for the indexed vertices (as described at the end of Section 6) of the 2-dimensional path,

(ii) next, by applying bijection δ_{z}, so that each label Y_{i} is moved bijectively according to the indexing defined in Section 6, (Specifically, a label Y_{i} on a double rise ZZ indexed by h on a path P is moved to the non-origin descent ZX of index h of path δ_{z}(P); likewise, a label Y_{i} on a non-origin descent is moved to the double rise of the same index, and a label Y_{i} on an otherwise vertex is moved to the otherwise vertex with the same index.)

(iii) and finally by expanding each label Y_{i} as a subpath to obtain a 3-dimensional path in ZL^{∗∗}(n).

The bijection

η_{2} : ZL^{∗∗}(n) ⟶ Y L^{∗∗}(n)

simply changes the first step of each path in ZL^{∗∗}(n) into a Y step. It can be routinely checked that the coloring is transfered in a manner preserving the appropriate number of blue and red vertices. The composition η = η_{2} ∘ η_{1} bijectively maps ZL^{∗}(n) to Y L^{∗∗}(n).

Next we define

ϕ = ϕ_{2} ∘ ϕ_{1} : Y L^{∗∗}(n) ⟶ L′′(n)

where the map

ϕ_{1} : Y L^{∗∗}(n) ⟶ Y L′′(n)

is defined by mimicking the definition of η_{1} by now projecting the path onto the x − y plane and using the bijection δ_{y}, and the map

ϕ_{2} : Y L′′(n) ⟶ L′′(n)

is defined simply to delete the first step, together with the first and last colors (necessarily r), from each path in Y L′′(n).

Example 5 Continuing from the previous examples, we have the following. Here the underlined (double underlined and overlined, resp.) labeling words are transfered sequentially from double rises (e.g., ZZ) to non-origin descents (e.g., ZX), etc.

P^{∗} = bZbY bY rY rXrXrZbY rXrZbZrXr ∈ L^{∗}(4),
ϵ(P^{∗}) = Z\underline{\underline{b}}Z\underline{bY bY rY r}X\overline{r}X\overline{r}Z\underline{bY r}X\overline{r}Z\underline{\underline{b}}Z\underline{r}X\overline{r} ∈ ZL^{∗}(4),
η_{1}(ϵ(P^{∗})) = Z\underline{bY bY rY r}Z\underline{\underline{b}}X\overline{r}X\overline{r}X\overline{r}Z\underline{bY r}Z\underline{r}Z\underline{\underline{b}}X\overline{r} ∈ ZL^{∗∗}(4),
η(ϵ(P^{∗})) = Y \underline{\underline{b}}Y \underline{\underline{b}}Y \underline{\underline{r}}Y \underline{Zb}X\overline{r}X\overline{r}X\overline{Zbr}Y \underline{rZrZb}X\overline{r} ∈ Y L^{∗∗}(4),
ϕ_{1}(η(ϵ(P^{∗}))) = Y \underline{rZb}Y \underline{\underline{b}}X\overline{r}Y \underline{\underline{b}}X\overline{r}Y \underline{rZrZb}Y \underline{\underline{r}}X\overline{rZb}X\overline{r} ∈ Y L′′(4),
ϕ(η(ϵ(P^{∗}))) = ZbY bXrY bXrY rZrZbY rXrZbX ∈ L′′(4).

8 The bijection L′′(n) to D(n)

We define a bijection

μ : L′′(n) ⟶ D(n)

so that, for each P ∈ L′′(n), μ(P) is obtained by replacing sequentially each maximal factor of steps having consecutively b colored vertices by an oblique step having 0-1 coordinates according to the following rules:

\begin{matrix}Y bX & ⟶ & (1, 1, 0) \\ ZbX & ⟶ & (1, 0, 1) \\ ZbY & ⟶ & (0, 1, 1) \\ ZbY bX & ⟶ & (1, 1, 1) \end{matrix}

On the resulting path, keep the remaining unit steps and remove the color r.

Example 6 The last path in Example 5, ZbY bXrY bXrY rZrZbY rXrZbX ∈ L′′(4), is mapped under μ to the path

(1, 1, 1)(1, 1, 0)(0, 1, 0)(0, 0, 1)(0, 1, 1)(1, 0, 0)(1, 0, 1) ∈ D(4).

9 Appendix

Let L(n_{1}, n_{2}, …, n_{d}) denote the set of d-dimensional lattice paths running from the origin to (n_{1}, n_{2}, …, n_{d}) using the unit steps X_{k}, where X_{k} denotes the unit d-vector with 1 in position k. In this section we consider statistics on paths of L(n_{1}, n_{2}, …, n_{d}), a proof of identity (1) for d > 3, and an explicit formula for |D(n)| when d = 3. We also generalize (1) to the non-central case and mention some generating functions results.

Some Statistics: We order the steps so that X < Y < Z. We define the following statistics, the last two being the classical number of descents (called number of major contacts in [6]) and number of excedances considered by MacMahon. [6, sect. IV, chap. III] (See [4, chap. 10].) For any path P = p_{1}p_{2} … p_{m} in L(n_{1}, n_{2}, n_{3}), with ZP denoting Zp_{1}p_{2} … p_{m}, etc., define (with the choice of the subscripts made clear later)

(i) f_{3}(P) = #(Y Y, ZY, or ZZ pairs on ZP),

(ii) f_{2}(P) = #(Y Y, ZX, or ZY pairs on Y P),

(iii) des(P) = |{i : p_{i} > p_{i+1}}| = #(Y X, ZX, or ZY pairs on P).

(iv) exced(P) = |{i : p_{i} > q_{i}}| where q_{1}q_{2} … q_{m} is that path in L(n_{1}, n_{2}, n_{3}) for which q_{i} ≤ q_{i+1} for 1 ≤ i < m.

Notice that

exced(P) = #(Z in first n_{1} + n_{2} positions of P) + #(Y in first n_{1} positions of P).

The establishment of the maps η_{1} and ϕ_{1} in Section 7 yields the following.

Proposition 1 The statistics f_{3}, f_{2}, and des are equi-distributed on L(n, n, n).

In general we remark that this proposition does not hold on L(n_{1}, n_{2}, n_{3}) where n_{1}, n_{2}, n_{3} are unequal; hence a neat “2^{n−1} result” is only realized in the central cases where n_{i} ∈ {0, n}. We consider the non-central case later in Proposition 3.

Higher dimensions: In order to state and prove identity (1) or the analog of Proposition 1 for d = 4, we expand the definitions of the statistics so that, if X = (1, 0, 0, 0), Y = (0, 1, 0, 0), Z = (0, 0, 1, 0), and W = (0, 0, 0, 1), then

f_{4}(P) = #(Y Y, ZY, ZZ, W Y, W Z, W W on W P)
f_{3}(P) = #(Y Y, ZY, ZZ, W X, W Y, W Z on ZP)
f_{2}(P) = #(Y Y, ZX, ZY, W X, W Y, W Z on Y P)
f_{1}(P) = #(Y X, ZX, ZY, W X, W Y, W Z on XP)
des(P) = #(Y X, ZX, ZY, W X, W Y, W Z on P)

Analogously to Sections 3 and 4, we can encode each path of S(n) in terms of a path using X, Y, Z, and W having colored vertices related to the statistic f_{4} together with a set A ∈ 2^{[n−1]} corresponding to the colors preceding the X steps. Analogously to Section 8, we can encode each path of D(n) in terms of a path using X, Y, Z, and W having colored vertices related to the statistic des. By employing the scheme of the previous sections we can show sequentially that each of f_{4}, f_{3}, f_{2}, and des is equi-distributed with the next. Essentially, we transfer each path into and out of the x − w plane, into and out of the x − z plane, and then into and out of the x − y plane, each time using an analog of Lemma 4 on the 2-dimensional path at each stage to move the coloring on certain double rises to certain non-origin descents.

Next we indicate how this approach extends to higher dimensions. Let B_{k} denote a set of step pairs defined recursively (backwards) so that B_{d} = {X_{i}X_{j} : 2 ≤ j ≤ i ≤ d} and B_{k−1} = B_{k}∪{X_{k}X_{1}}\{X_{k}X_{k}} for 1 < k ≤ d. For 1 ≤ k ≤ d and any path X_{k}P = p_{0}p_{1} … p_{dn}, define the statistic f_{k}(P) = |{i : p_{i−1}p_{i} ∈ B_{k}, 1 ≤ i ≤ dn}|. We then encode each path of S(n) in terms of a path using X_{1}, …, X_{d} having colored vertices related to the statistic f_{d} together with a set A ∈ 2^{[n−1]}. Also we encode each path of D(n) in terms of a path using X_{1}, …, X_{d} having colored vertices related to the statistic des = f_{1}. By mimicking the scheme of the previous sections where sequentially the coloring on double rises X_{k}X_{k} is swapped for the coloring on descents X_{k}X_{1}, k running from d back to 2, we can show that each of f_{d}, f_{d−1}, … f_{2}, and des = f_{1} is equi-distributed with the next.

Explicit formulas and the non-central case: Now we establish an explicit formula for enumerating L(n_{1}, n_{2}, n_{3}) with respect to the number of descents, which appears in an equivalent form in MacMahon [6, p. 180]. However, since we have been considering equidistributed statistics, we will use a related result of MacMahon [6, sect. IV, ch. III] [5, p. 669], which is proved bijectively by Foata [4] and Clarke and Foata [2] (See also [5, pp. 455-6].) For d = 3, the result is

Proposition 2 The statistics des and exced are equi-distributed on L(n_{1}, n_{2}, n_{3}).

Thus

∑_{P ∈L(n_{1},n_{2},n_{3})} t^{des(P)} = ∑_{h} |{P : des(P) = h}|t^{h} = ∑_{h} |{P : exced(P) = h}|t^{h}.

Since |{P : exced(P) = h}| is the number of paths having i Z’s and j Y ’s in the first n_{1} positions and k Z’s and ℓ Y ’s in the next n_{2} positions, then, with h = i + j + k,

|{P : exced(P) = h}| =

∑_{i,j,k,ℓ} \frac{n_{1}!}{i!j!(n_{1} − i − j)!} \frac{n_{2}!}{k!ℓ!(n_{2} − k − ℓ)!} \frac{n_{3}!}{(n_{3} − i − k)!(n_{2} − j − ℓ)!(i + j + k + ℓ − n_{2})!}.

Hence, after some simplification, with the indices satisfying 0 ≤ i ≤ n_{1}, 0 ≤ j ≤ n_{1} − i, and 0 ≤ k ≤ n_{2}, we find

∑_{P ∈L(n_{1},n_{2},n_{3})} t^{des(P)} = ∑_{i,j,k} \binom{n_{1}}{i}\binom{n_{1} − i}{j}\binom{n_{2}}{k}\binom{n_{2} + i}{i + j}\binom{n_{3}}{i + k}t^{i+j+k}.  (4)

By setting n_{1} = n_{2} = n_{3} = n, by setting t = 2 corresponding to the blue or red choice at each descent, and by using the mapping μ of Section 8, formula (4) yields an explicit formula for |D(n)| for d = 3.

MacMahon in his book [6] comes close to formulating identity (1) for d = 2 and 3. He mentions the Delannoy numbers, without name, briefly on [6, p. 159], and records (1) for d = 1 on [6, p. 151]. Armed with the bijections of Sections 3 and 8, and now aware of his analysis, we will give a generalization of identity (1) for the non-central case.

Let D(n_{1}, n_{2}, …, n_{d}) denote the set of paths from the origin to (n_{1}, n_{2}, …, n_{d}) using nonzero steps of the form (x_{1}, x_{2}, …, x_{d}) where x_{i} ∈ {0, 1} for 1 ≤ i ≤ d. Let S(n_{1}, n_{2}, …, n_{d}) denote the set of paths from the origin to (n_{1}, n_{2}, …, n_{d}) using the steps of the form (x_{1}, x_{2}, …, x_{d}) where the x_{i}’s are nonnegative integers, not all zero.

Proposition 3 Let f(t; n_{1}, n_{2}, n_{3}) denote the polynomial in t of (4). For (n_{1}, n_{2}, n_{3}) ≠ (0, 0, 0),

|S(n_{1}, n_{2}, n_{3})| = 2^{n_{1}+n_{2}+n_{3}−1}f(\frac{1}{2}; n_{1}, n_{2}, n_{3})  (5)

while

|D(n_{1}, n_{2}, n_{3})| = f(2; n_{1}, n_{2}, n_{3}).  (6)

The proof of (6) was effectively covered in the paragraph following the formula (4). To prove (5), which is also stated and proven in [6, p. 180], we require some notation. On L(n_{1}, n_{2}, n_{3}) we define the following statistics (names borrowed from MacMahon’s equal contact and minor contact):

des(P)  = #(Y X, ZX, and ZY on P)
eqcon(P) = #(XX, Y Y, and ZZ on P)
mincon(P) = #(XY, XZ, and Y Z on P)

Let L′(n_{1}, n_{2}, n_{3}) denote the set of paths formed from the paths of L(n_{1}, n_{2}, n_{3}) by weighting the intermediate vertices of XX, Y X, Y Y, ZX, ZY, and ZZ with 2. Hence, by extending the map α of Section 3 to α : S(n_{1}, n_{2}, n_{3}) → L′(n_{1}, n_{2}, n_{3}), we obtain

|S(n_{1}, n_{2}, n_{3})| = ∑_{P ∈L(n_{1},n_{2},n_{3})} 2^{des(P)+eqcon(P)}.

That there are n_{1} + n_{2} + n_{3} − 1 interior lattice points on any path of L(n_{1}, n_{2}, n_{3}), together with symmetry, yields

∑_{P ∈L(n_{1},n_{2},n_{3})} t^{des(P)+eqcon(P)} = ∑_{P ∈L(n_{1},n_{2},n_{3})} t^{n_{1}+n_{2}+n_{3}−1−mincon(P)}
= t^{n_{1}+n_{2}+n_{3}−1} ∑_{P ∈L(n_{3},n_{2},n_{1})} t^{−des(P)}.  (7)

Thus formula (5) follows by the symmetry of |S(n_{1}, n_{2}, n_{3})| in n_{1}, n_{2}, and n_{3}. □

Generating functions and recurrences: For any d, the formulas for the generating functions for ∑_{n_{1},...,n_{d}} |D(n_{1}, …, n_{d})|x_{1}^{n_{1}} ⋯ x_{d}^{n_{d}} and ∑_{n_{1},...,n_{d}} |S(n_{1}, …, n_{d})|x_{1}^{n_{1}} ⋯ x_{d}^{n_{d}} are given by MacMahon on [6, p. 159, p. 156, resp.]. For d = 3 we find

∑_{m,n,p≥0} |D(m, n, p)|x^{m}y^{n}z^{p} = \frac{1}{1 − x − y − z − xy − xz − yz − xyz}
∑_{m,n,p≥0} |S(m, n, p)|x^{m}y^{n}z^{p} = \frac{1}{2} + \frac{1}{2(1 − 2(x + y + z − xy − xz − yz + xyz))},

which give rise to the recurrences:

|D(m, n, p)| = |D(m − 1, n, p)| + |D(m, n − 1, p)| + |D(m, n, p − 1)| + |D(m − 1, n − 1, p)|
+|D(m − 1, n, p − 1)| + |D(m, n − 1, p − 1)| + |D(m − 1, n − 1, p − 1)|
|S(m, n, p)| = 2(|S(m − 1, n, p)| + |S(m, n − 1, p)| + |S(m, n, p − 1)| − |S(m − 1, n − 1, p)|
−|S(m − 1, n, p − 1)| − |S(m, n − 1, p − 1)| + |S(m − 1, n − 1, p − 1)|)

For the second recurrence we require that m > 1 or n > 1 or p > 1.

A reciprocal polynomial: We conclude by noting that, in the central case and d = 3 (the proof for any d is similar), the polynomial ∑_{P ∈L(n)} t^{des(P)} is a reciprocal polynomial, i.e., if ∑_{h} c_{h}t^{h} denotes ∑_{P ∈L(n)} t^{des(P)} then c_{2n−h} = c_{h} for 0 ≤ h ≤ 2n. By exchanging the blue-red coloring for an indeterminate t, we can routinely modify our bijection proving (1) to show

∑_{P ∈L(n)} t^{des(P)+eqcon(P)} = t^{n−1} ∑_{P ∈L(n)} t^{des(P)}.

Combining this with the identity of (7) yields

∑_{P ∈L(n)} t^{2n−des(P)} = ∑_{P ∈L(n)} t^{des(P)}.

Acknowledgments. The authors thank C. Krattenthaler for leading them to Proposition 2 through the reference [2]. We are also grateful to the referees for their generous suggestions.

References

[1] C. Banderier and S. Schwer, Why Delannoy numbers?, J. Stat. Plann. Inference, to appear.

[2] R. J. Clarke and D. Foata, Eulerian calculus, I: Univariable statistics, Europ. J. Combinatorics, 15 (1994) 345–362.

[3] K. Humphreys and H. Niederhausen, Counting lattice paths taking steps in infinitely many directions under special access restrictions, Theoret. Comput. Sci., to appear.

[4] M. Lothaire, Combinatorics on words, Addison–Wesley, 1983.

[5] P.A. MacMahon, Collected Papers, vol I, [G.E. Andrews, ed.], Cambridge, Mass., The M.I.T. press, 1978.

[6] P.A. MacMahon, Combinatory Analysis, Cambridge, Cambridge Univ. Press, (Reprinted by Chelsea, New York, 1955) vol. I.

[7] N. J. A. Sloane, On-line Encyclopedia of Integer Sequences,

   http://www.research.att.com/∼njas/sequences/index.html

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

[9] R. A. Sulanke, Counting lattice paths by Narayana polynomials, Electron. J. Combin. 7 (2000), Art. R40, 9 pp.

[10] R. A. Sulanke, Objects counted by the central Delannoy numbers, J. Integer Sequences, (2003), Art. 03.1.5, 19 pp.

[11] R. A. Sulanke, Generalizing Narayana and Schröder numbers to higher dimensions, preprint 2003.