Lattice paths, reflections, & dimension-changing bijections

Richard K. Guy C. Krattenthaler Bruce E. Sagan

Department of Mathematics and Statistics The University of Calgary Calgary, Alberta, Canada T2N 1N4

Institut für Mathematik der Universität Wien, Strudlhofgasse 4 A-1090 Wien, Austria

Department of Mathematics Michigan State University East Lansing, MI 48824-1027 USA

Abstract. We enumerate various families of planar lattice paths consisting of unit steps in directions N, S, E, or W, which do not cross the x-axis or both x- and y-axes. The proofs are purely combinatorial throughout, using either reflections or bijections between these NSEW-paths and linear NS-paths. We also consider other dimension-changing bijections.

1. Introduction. Consider lattice paths in the plane consisting of unit steps, each in a direction N, S, E, or W. Such NSEW-paths were first investigated by DeTemple & Robertson [DR] and Csáki, Mohanty & Saran [CMS]. The basic result of these papers is the following.

Theorem 1. The number of NSEW-paths with n steps from the origin to (c, d) is

(1.1)  \binom{n}{\frac{n+c+d}{2}}\binom{n}{\frac{n+c−d}{2}} ,

1980 Mathematics Subject Classification (1991 Revision). Primary 05A15; Secondary 05A10.

Key words and phrases. lattice paths, bijections, reflection principle.

Professor Sagan was supported in part by NSF grant DMS 8805574 .

where by convention the binomial coefficient \binom{n}{k} is assumed to be zero unless k is a an integer 0 ≤ k ≤ n.

The form of expression (1.1) suggests that there is a simple combinatorial explanation, although there is none in either [DR] or [CMS]. This will be our first objective in the next section.

We will consider NSEW-paths which do not cross the x-axis, or which cross neither the x-axis nor the y-axis. It turns out that there are simple and beautiful expressions for the cardinality of several sets of such NSEWpaths. A list of the simplest of these is given below, and more can be found in the next section. But first it is convenient to introduce some notation.

If a, b, c, d are integers, let P_{n}((a, b) → (c, d)) denote the set of all NSEWpaths from (a, b) to (c, d) consisting of n steps, let P_{n}^{+}((a, b) → (c, d)) denote that subset of P_{n}((a, b) → (c, d)) containing only paths which do not cross the x-axis, and let P_{n}^{++}((a, b) → (c, d)) denote that subset of P_{n}((a, b) → (c, d)) containing only paths which do not cross either the xaxis or the y-axis. We will also want to count sets of paths which can end at more than one point. For this, we will use two additional notational conventions. By “≥ c” in place of a coordinate of the final point of a set of paths, we mean that this coordinate may be any integer greater or equal c, by “∗” we mean that this coordinate may be any integer. For example, P_{n}^{+}((a, b) → (∗, ≥ d)) denotes the set of all NSEW-paths of n steps starting at (a, b) which do not cross the x-axis and finish at some point (x, y), where x is an arbitrary integer and y is an integer greater than or equal to d.

It will also be convenient to let L_{n}(b → d) denote the set of all linear NS-paths of length n from (0, b) to (0, d). Similarly, the other notational conventions of the preceding paragraph will be adapted for 1-dimensional paths.

Now, here is the promised list. For P_{n} we have the following formulas.

(1.2)  |P_{n}((a, b) → (c, d))| = \binom{n}{r}\binom{n}{s} ,

where r = \frac{1}{2}(n − a − b + c + d) and s = \frac{1}{2}(n − a + b + c − d).

(1.3)  |P_{n}((0, b) → (∗, d))| = \binom{2n}{n − d + b} .

For P_{n}^{+} we can prove the following results.

(1.4) |P_{n}^{+}((a, b) → (c, d))| = \binom{n}{r}\binom{n}{s} − \binom{n}{r + b + 1}\binom{n}{s − b − 1} ,

(1.5) |P_{n}^{+}((0, 0) → (c, ∗))| = \binom{n}{⌊\frac{n+c}{2}⌋}\binom{n}{⌊\frac{n−c}{2}⌋} .

(1.6) |P_{n}^{+}((0, b) → (∗, d))| = \binom{2n}{n − d + b} − \binom{2n}{n − d − b − 2} ,

in particular,

(1.7)  |P_{n}^{+}((0, 0) → (∗, d))| = \binom{2n + 1}{n − d} − \binom{2n + 1}{n − d − 1} .
(1.8)  |P_{n}^{+}((0, 0) → (∗, 0))| = C_{n+1} ,

where C_{n} is the nth Catalan number.

(1.9)  |P_{n}^{+}((0, 0) → (∗, ∗))| = \binom{2n + 1}{n} .
(1.10)  |P_{n}^{+}((0, 1) → (∗, ∗))| = \binom{2n + 2}{n} .

Finally, for paths confined to the first quadrant, we obtain the following.

|P_{n}^{++}((a, b) → (c, d))| = \binom{n}{r}\binom{n}{s} − \binom{n}{r + b + 1}\binom{n}{s − b − 1} (1.11)
−\binom{n}{r + a + 1}\binom{n}{s + a + 1} + \binom{n}{r + a + b + 2}\binom{n}{s + a − b} ,

with r, s as in (1.2). In particular,

|P_{n}^{++}((0, 0) → (c, d))| = \binom{n}{\frac{n+c−d}{2}}\binom{n + 2}{\frac{n−c−d}{2}} − \binom{n + 2}{\frac{n+c−d}{2} + 1}\binom{n}{\frac{n−c−d}{2} − 1} . (1.12)

|P_{n}^{++}((0, 0) → (c, ∗))| = \binom{n}{⌊\frac{n−c}{2}⌋}\binom{n + 1}{⌊\frac{n−c+1}{2}⌋} − \binom{n}{⌊\frac{n−c−1}{2}⌋}\binom{n + 1}{⌊\frac{n−c}{2}⌋} . (1.13)

|P_{n}^{++}((0, 0) → (∗, ∗))| = \binom{n}{⌊\frac{n}{2}⌋}\binom{n + 1}{⌊\frac{n+1}{2}⌋} . (1.14)

Equation (1.9) was first discovered by Sands [Sa] and was the starting point of our investigations.

In the next section we provide combinatorial proofs for all these formulas. We also derive counting results about NSEW-paths with lower bounds on the x- or y-coordinate of the final points. The techniques we use are either the so-called reflection principle [Mo] or certain bijections between NSEW-paths and NS-paths along the y-axis. In Section 3 we will look at some other dimension-changing bijections. We should note that Breckenridge, Bos, Calvert, Gastineau-Hills, Nelson & Wehrhahn [BBCGNW] have independently discovered essentially the same formulas and bijective proofs for (1.1) to (1.4), (1.6), (1.8) and (1.9). Related bijections have also been considered in [CMS] and by Gessel [private communication].

Of course, several of these results follow directly from others on the list by simple algebraic manipulations. For example, (1.9) can be deduced from (1.7) by summing up over all d ≥ 0. But such a proof does not really explain why this expression is the answer to the problem in the way that a bijection does. The second reason why purely combinatorial proofs are preferable is that very often they give insight into the connections between certain properties of lattice paths and the structure of the corresponding counting expressions (cf. the proofs of (1.5), (1.10), (1.13), (1.14)).

2. Reflections and bijections.

Proof of (1.1) and (1.2). We set up a correspondence between NSEWpaths, p, and pairs (p_{1}, p_{2}) of NS-paths. The m-th step of p will correspond to the pair of m-th steps from p_{1} and p_{2} according to the following table.

\underline{p} \underline{p_{1}} \underline{p_{2}}
N N N
E N S
W S N
S S S

Then the NSEW-paths of n steps from (0, 0) to (c, d) are in one-to-one correspondence with pairs (p_{1}, p_{2}) of n-step NS-paths, where p_{1} runs from (0, 0) to (0, c + d) and p_{2} from (0, 0) to (0, c − d). But the number of NS-paths from (0, 0) to (0, k) of length n is well-known [Mo, page 2] to be

(2.1)  |L_{n}(0 → k)| = \binom{n}{\frac{n+k}{2}} ,

and (1.1) follows at once.

Formula (1.2) now follows by translation. □

Proof of (1.3). Here we use another correspondence between NSEWpaths, p, and NS-paths, p̄, of twice the length. The m-th step of p determines the (2m − 1)-st and 2m-th step of p̄ according to the following table. Notice the similarity to the correspondence in the proof of (1.1).

\underline{p} \underline{p̄}
N NN
E NS
W SN
S SS

This sets up a one-to-one correspondence between NSEW-paths with n steps from (0, b) to (∗, d) and NS-paths with 2n steps from (0, 2b) to (0, 2d). Applying a translated version of formula (2.1), we are done. □

Proof of (1.4) and (1.6). These follow from (1.2) and (1.3) respectively by the reflection principle. For (1.4), note that the total number of NSEWpaths from (a, b) to (c, d) is given by \binom{n}{r}\binom{n}{s}. From this, we have to subtract off the number of paths which cross the x-axis. Each of these has a first point, say P, for which y = −1. Reflect the initial portion OP in the line y = −1, giving a one-to-one correspondence between paths which cross the x-axis and paths from (a, −b−2) to (c, d). Applying (1.2) we see that these paths are counted by \binom{n}{r+b+1}\binom{n}{s−b−1}.

Similarly, in (1.6) the first term counts all paths from (0, b) to (∗, d). Those that touch y = −1 are subtracted out by the second term. □

Proof of (1.7) and (1.8). We use the same correspondence as in the proof of (1.3), except that the m-th step of p determines the 2m-th and (2m+1)- st step of p̄. The first step of p̄ is always taken to be N so p̄ has total length 2n + 1 and ends at (0, 2d + 1). In addition, the fact that p always stays in the upper half plane translates to p̄ always staying on the upper half of the y-axis. The number of such paths is well-known [Mo, page 3] to be the right-hand side of (1.7). (In fact, the one-dimensional reflection principle is usually used to derive this from (2.1).) In particular, when d = 0 we obtain a Catalan number. □

Proof of (1.9) and (1.10). To prove (1.9) we first apply the correspondence in the proof of (1.7) to get a bijection

P_{n}^{+}((0, 0) → (∗, ∗)) ⟷ ⋃_{j≥0} L_{2n+1}^{+}(0 → 2j + 1).

In view of (2.1), it suffices to give a second bijection

(2.2)  L_{2n+1}(0 → 1) ⟷ ⋃_{j≥0} L_{2n+1}^{+}(0 → 2j + 1).

Given p ∈ L_{2n+1}(0 → 1) apply the map

p ⟶ \{ \begin{matrix}p & if p ∈ L_{2n+1}^{+}(0 → 1) \\ p′ & otherwise, where p′ is obtained from p by re- flecting the portion up to the first intersection with y = −1 in that line and then shifting the whole path 2 units upwards. \end{matrix}

Clearly this is a bijection

L_{2n+1}(0 → 1) ⟷ L_{2n+1}^{+}(0 → 1) ∪ L_{2n+1}(0 → 3) .

We now apply the same map to the elements of L_{2n+1}(0 → 3), and by iterating the process end up with the right-hand side of (2.2). We will see a similar map later in the proof of (1.5) and related identities.

The same idea will give a bijection

⋃_{j≥0} L_{2n}^{+}(2b + 1 → 2l + 1 + (4b + 4)j) ⟷ L_{2n}(2b + 1 → 2l + 1) .

Moreover, the last bijection also provides the following bijection,

⋃_{j≥0} L_{2n}^{+}(2b + 1 → 2j + 1) ⟷ ⋃_{l=0}^{2b+1} L_{2n}(2b + 1 → 2l + 1) .

Since, by the bijection used to establish (1.6), the set L_{2n}^{+}(2b+1 → 2j+1) is in one-to-one correspondence with P_{n}^{+}((0, b) → (∗, ∗)), we have a bijective proof of the formula

|P_{n}^{+}((0, b) → (∗, ∗))| = ∑_{j=0}^{2b+1} \binom{2n}{n + b − j} .

Using the symmetry relation

\binom{m}{k} = \binom{m}{m − k}

and recursion formula

(2.3)  \binom{m + 1}{k + 1} = \binom{m}{k} + \binom{m}{k + 1} ,

this can be rewritten

|P_{n}^{+}((0, b) → (∗, ∗))| = ∑_{j=0}^{b} [\binom{2n}{n + j} + \binom{2n}{n + j + 1}]

= ∑_{j=1}^{b+1} \binom{2n + 1}{n + j} .

In particular, for b = 0 we obtain (1.9) again, while for b = 1 we get (1.10) by reapplying the recursion. The algebraic step of transforming binomial coefficients by symmetry can be made bijective by considering the correspondence between L_{2n}(0 → k) and L_{2n}(0 → −k) given by reflection in the origin. Also, the recursion steps can be turned into a bijection by adjoining to the end of a path a N- or S-step as appropriate, corresponding to the first or second terms of (2.3). □

Proof of (1.11) and (1.12). The inclusion-exclusion principle shows that the number of paths being elements of P_{n}^{++}((a, b) → (c, d)) is equal to the number of all NSEW-paths of n steps from (a, b) to (c, d) minus the number of those which cross the x-axis minus the number of those which cross the y-axis plus the number of those which cross both of them. The paths crossing the x-axis have been already counted in the proof of (1.4) by using reflection in y = −1. Similarly, by reflection in x = −1, it is seen that n-step paths from (a, b) to (c, d) which cross the y-axis are in one-to-one correspondence with all n-step paths from (−a − 2, b) to (c, d). The set of n-step paths from (a, b) to (c, d) which cross both the x- and y-axes is in one-to-one correspondence with all paths from (−a − 2, −b − 2) to (c, d), which is seen by using reflection twice, first in y = −1, then in x = −1. Hence, by (1.2) the desired number is given by the right-hand side of (1.11). Setting a = b = 0 in (1.11) and using the binomial recursion repeatedly, we obtain (1.12). □

Proof of (1.5), (1.13) and (1.14). Let us introduce another correspondence, this time between families of NSEW-paths themselves. For a path p ∈ P_{n}((a, b) → (c, d)) we apply the map

p ⟶ \{ \begin{matrix}p & if p ∈ P_{n}^{+}((a, b) → (c, d)) \\ p′ & otherwise, where p′ is obtained from p by re- flecting the portion up to the first intersection with y = −1 in that line and then shifting the whole path 2b + 2 units upwards. \end{matrix}

This is a bijection

P_{n}((a, b) → (c, d)) ⟷ P_{n}^{+}((a, b) → (c, d)) ∪ P_{n}((a, b) → (c, d + (2b + 2))) .

Applying the same map to P_{n}((a, b) → (c, d + (2b + 2))), etc., we get a bijection

(2.4)  P_{n}((a, b) → (c, d)) ⟷ ⋃_{j≥0} P_{n}^{+}((a, b) → (c, d + (2b + 2)j)) .

Now, let a + b + c + d ≡ n (mod 2). Using the bijection in (2.4) for d successively replaced by d, d + 2, …, d + 2b, we obtain a bijection

⋃_{j=0}^{b} P_{n}((a, b) → (c, d + 2j)) ⟷ P_{n}^{+}((a, b) → (c, ≥ d)) .

In case a + b + c + d ≡ n + 1 (mod 2) use (2.4) for d replaced by d + 1, d + 3, …, d + 2b + 1, thus obtaining a bijection

⋃_{j=0}^{b} P_{n}((a, b) → (c, d + 1 + 2j)) ⟷ P_{n}^{+}((a, b) → (c, ≥ d)) .

Putting both together and using the basic result (1.2), leads to the following expression for the cardinality of P_{n}^{+}((a, b) → (c, ≥ d)):

(2.5)  |P_{n}^{+}((a, b) → (c, ≥ d))| = ∑_{j=0}^{b} \binom{n}{⌊r⌋ − j}\binom{n}{⌊s⌋ − j} .

In particular, for a = b = 0 we get

(2.6)  |P_{n}^{+}((0, 0) → (c, ≥ d))| = \binom{n}{⌊\frac{n+c−d}{2}⌋}\binom{n}{⌊\frac{n−c−d}{2}⌋} .

Setting d = 0 in (2.6) gives (1.5).

The same idea which was used to obtain (2.4) may also be applied to the right-hand side of (2.4) in “horizontal” direction. This provides a bijection (2.7)

P_{n}((a, b) → (c, d)) ⟷ ⋃_{i,j≥0} P_{n}^{++}((a, b) → (c + (2a + 2)i, d + (2b + 2)j)) .

Now, let a+b+c+d ≡ n (mod 2). In a similar manner as above, a bijection

⋃_{i=0}^{a} ⋃_{j=0}^{b} (P_{n}((a, b) → (c+2i, d+2j))∪P_{n}((a, b) → (c+1+2i, d+1+2j)))

⟷ P_{n}^{++}((a, b) → (≥ c, ≥ d))

can be constructed. In case a + b + c + d ≡ n + 1 (mod 2), analogously we construct a bijection

⋃_{i=0}^{a} ⋃_{j=0}^{b} (P_{n}((a, b) → (c+1+2i, d+2j))∪P_{n}((a, b) → (c+2i, d+1+2j)))

⟷ P_{n}^{++}((a, b) → (≥ c, ≥ d)) .

Again, putting both together and using the binomial recursion, simple considerations show that

(2.8) |P_{n}^{++}((a, b) → (≥ c, ≥ d))|

= ∑_{i=0}^{a} ∑_{j=0}^{b} \frac{n! (n + 1)!}{⌈r + i − j⌉! ⌈n − r − i + j⌉! ⌊s − i − j⌋! ⌊n − s + i + j + 1⌋!} .

The specialization a = b = 0 leads to the formula (2.9)

|P_{n}^{++}((0, 0) → (≥ c, ≥ d))| = \frac{n! (n + 1)!}{⌈\frac{n+c−d}{2}⌉! ⌈\frac{n−c+d}{2}⌉! ⌊\frac{n−c−d}{2}⌋! ⌊\frac{n+c+d+2}{2}⌋!} .

In particular, setting d = 0 results in

(2.10)  |P_{n}^{++}((0, 0) → (≥ c, ∗))| = \binom{n}{⌊\frac{n−c}{2}⌋}\binom{n + 1}{⌊\frac{n−c+1}{2}⌋} ,

which directly implies (1.13). Equation (1.14) is the special case c = 0 of (2.10). □

3. Higher dimensions.

It is easy to extend the idea of a dimension-changing bijection to higher dimensions. As an example, we will examine the case of lattice paths in dimension four. Let the four coordinates be denoted x, y, z, w and let X, Y, Z, W denote a positive unit step in those respective directions while X̄, Ȳ, Z̄, W̄ denote the corresponding negative step. Then there is a length-preserving bijection between 4-dimensional paths p and triples of 1-dimensional paths p_{1}, p_{2}, p_{3} by letting the m-th steps correspond according to the following table.

\underline{p} \underline{p_{1}} \underline{p_{2}} \underline{p_{3}}
X N N N
Y N N S
Z N S N
W N S S
W̄ S N N
Z̄ S N S
Ȳ S S N
X̄ S S S

Of course, given the ending points of p_{1}, p_{2} and p_{3} only gives us three conditions, and we need four to determine the ending point of p. Thus we will only be able to count paths that end on a given line.

Suppose p ends somewhere on the line l whose parametric equations are

(3.1)  l :  \begin{aligned}x & = a + t \\ y & = b − t \\ z & = c − t \\ w & = t . \end{aligned}

for some constants a, b, c and variable t. Next we eliminate t using pairs corresponding to two partitions of coordinates, namely {x, y} ∪ {z, w} and {x, z} ∪ {y, w}.

x + y = a + b
z + w = c
x + z = a + c
y + w = b

Now let x_{1} and x_{2} be the number of X-steps and X̄-steps, respectively, in p with similar notation for the other directions. Then the final x-coordinate of p is x_{1} − x_{2} and likewise for the other coordinates. This can be substituted into the equations above. Then add and subtract the equations corresponding to the same partition to obtain

x_{1} − x_{2} + y_{1} − y_{2} + z_{1} − z_{2} + w_{1} − w_{2} = a + b + c
x_{1} − x_{2} + y_{1} − y_{2} − z_{1} + z_{2} − w_{1} + w_{2} = a + b − c
x_{1} − x_{2} − y_{1} + y_{2} + z_{1} − z_{2} − w_{1} + w_{2} = a − b + c
x_{1} + x_{2} + y_{1} + y_{2} + z_{1} + z_{2} + w_{1} + w_{2} = n

where the last equation comes from the fact that p has length n. Finally we can solve for the number of N-steps on each of p_{1}, p_{2}, p_{3} which are given respectively by

x_{1} + y_{1} + z_{1} + w_{1} = \frac{n + a + b + c}{2}
x_{1} + y_{1} + z_{2} + w_{2} = \frac{n + a + b − c}{2}
x_{1} + y_{2} + z_{1} + w_{2} = \frac{n + a − b + c}{2} .

Thus we have proved the following theorem.

Theorem 2. The number of 4-dimensional paths with n steps ending on the line given by (3.1) is

\binom{n}{\frac{n+a+b+c}{2}}\binom{n}{\frac{n+a+b−c}{2}}\binom{n}{\frac{n+a−b+c}{2}} .

To describe other sets of paths let Q_{n}^{S}(0 → l) denote the set of 4dimensional paths of length n from the origin to the line l of (3.1) which stay in some subset S of Z^{4}. Define the following half-spaces.

H_{1} :x + y + z + w ≥ 0
H_{2} :x + y − z − w ≥ 0
H_{3} :x − y + z − w ≥ 0 .

Letting r = \frac{n+a+b+c}{2}, s = \frac{n+a+b−c}{2}, t = \frac{n+a−b+c}{2}, we have the following formulas.

(3.2)  |Q_{n}^{H_{1}}(0 → l)| = [\binom{n}{r} − \binom{n}{r + 1}] \binom{n}{s}\binom{n}{t} .

In particular, if a + b + c = 0 then

(3.3)  |Q_{n}^{H_{1}}(0 → l)| = C_{n/2}\binom{n}{s}\binom{n}{t} .

where the Catalan number is non-zero if and only if n is even. Similarly

(3.4) |Q_{n}^{H_{1}∩H_{2}}(0 → l)| = [\binom{n}{r} − \binom{n}{r + 1}] [\binom{n}{s} − \binom{n}{s + 1}] \binom{n}{t} .

In particular, if a + b = c = 0 then

(3.5)  |Q_{n}^{H_{1}∩H_{2}}(0 → l)| = C_{n/2}^{2}\binom{n}{t} .

Finally

|Q_{n}^{H_{1}∩H_{2}∩H_{3}}(0 → l)| = [\binom{n}{r} − \binom{n}{r + 1}] [\binom{n}{s} − \binom{n}{s + 1}]

[\binom{n}{t} − \binom{n}{t + 1}] . (3.6)

In particular, if a = b = c = 0 then

(3.7)  |Q_{n}^{H_{1}∩H_{2}∩H_{3}}(0 → l)| = C_{n/2}^{3} .

The proofs in all cases are quite simple. For example, to get (3.2) merely note that points of p always satisfy x + y + z + w ≥ 0 if and only if x_{1} + y_{1} + z_{1} + w_{1} ≥ x_{2} + y_{2} + z_{2} + w_{2} at each stage, which is equivalent to the number of N-steps of p_{1} always being at least the number of S-steps.

Clearly, the above construction can be carried out in general, although the description of the paths counted gets progressively more complicated. Every n-tuple (p_{1}, …, p_{n}) of linear paths corresponds to a path p in 2^{n−1} dimensions. One obtains the appropriate table by listing all the positive directions for p and then all the corresponding negative directions in reverse order. The rows for (p_{1}, …, p_{n}) are obtained by counting in base 2 from 0 to 2^{n} −1 and replacing 0’s and 1’s by N’s and S’s respectively. This ensures the crucial property that if a direction in Z^{2^{n−1}} corresponds to a given sequence of N’s and S’s then the sequence for the negative of that direction is obtained by changing each N to an S and vice versa. The ending points of the n linear paths only give us n constraints, so we will only be able to count paths that end in a certain affine subspace of dimension 2^{n−1} − n. It was a happy coincidence that when n = 2 this subspace was a point. However, the persevering reader should now be able to write down the equations for general n if they are desired.

For another method to enumerate paths staying in a given region defined by hyperplanes (this time in 3 dimensions) see the paper of Wimp and Zeilberger [WF].

4. Related problems. One of us [Gu] originally obtained some of the formulas in Section 2 by induction and other algebraic manipulations. The desire to obtain combinatorial proofs of these results was one of the stimuli for the current work. One such identity, which is considerably harder to prove bijectively is

|P_{2n−1}^{++}((0, 0) → (0, 1))| = \frac{1}{2}C_{n}C_{n+1}.

A combinatorial demonstration of this fact using trees and Baxter permutations will be found in the paper of Cori, Dulucq and Viennot [CDV]. They also use their techniques to explain the connection with Hamiltonian rooted maps on 2n vertices [Tu; Sl, sequence 1647].

An open problem is as follows. Let l be the line x + y = n − 2. Then, by summing the values in equation (1.12), we obtain

|P_{n}^{++}((0, 0) → l)| = (n − 2)2^{n} + 2.

It turns out that this is just twice the genus of the n-cube [Ri; BH; Sl, sequence 1587]. A combinatorial explanation would be welcome.

References

[BH] L. W. Beineke and F. Harary, The genus of the n-cube, Canad. Math. J. 17 (1965), 494–496.

[BBCGNW] W. Breckenridge, P. Bos, G. Calvert, H. Gastineau-Hills, A. Nelson and K. Wehrhahn, Lattice paths and Catalan numbers, Bulletin of the Institute of Combinatorics and Applications 1 (1991), 41–55.

[CDV] R. Cori, S. Dulucq and G. Viennot, Shuffle of parenthesis systems and Baxter permutations, J. Combin. Theory, Ser. A 43 (1986), 1–22.

[CMS] E. Csáki, S. G. Mohanty and S. Saran, On random walks in a plane, Ars Combin. 29 (1990), 309–318.

[DR] D. W. DeTemple and J. M. Robertson, Equally likely fixed length paths in graphs, Ars Combin. 17 (1984), 243–254.

[DJR] D. W. DeTemple, C. H. Jones and J. M. Robertson, A correction for a lattice path counting formula, Ars Combin. 25 (1988), 167–170.

[Gu] R. K. Guy, Catwalks, sandsteps & Pascal pyramids, preprint.

[Mo] S. G. Mohanty, Lattice Path Counting and Applications, Academic Press, New York, 1979, pp. 2–7.

[Ri] G, Ringel, Über drei kombinatorische Probleme am n-dimensionalen Würfel und Würfelgitter, Abh. Math. Sem. Univ. Hamburg 20, 10–19.

[Sa] B. Sands, Problem 1517*, Crux Mathematicorum 16 (1990), 44.

[Sl] N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, New York, 1973.

[Tu] W. T. Tutte, A census of Hamiltonian polygons, Canadian Math. J. 14 (1962), 402–417.

[WZ] J. Wimp and D. Zeilberger, How likely is Polya’s drunkard to stay in x ≥ y ≥ z?, J. Statistical Physics 57 (1989), 1129–1135.

Department of Mathematics and Statistics, The University of Calgary, Calgary, Alberta, Canada T2N 1N4

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.

Department of Mathematics, Michigan State University, East Lansing, MI 48824-1027