Between Broadway and the Hudson: A Bijection of Corridor Paths

Nachum Dershowitz School of Computer Science Tel Aviv University Ramat Aviv Israel

                   nachum@tau.ac.il

Abstract

We present a substantial generalization of the equinumeracy of Grand Dyck paths and Dyck-path prefixes, constrained within a band. The number of constrained paths starting at level i and ending in a window of size 2j + 2 is equal to the number starting at level j and ending in a window of size 2i + 2 centered around the same point. A new encoding of lattice paths provides a bijective proof.

Canal street, running across Broadway to the Hudson, near the centre of the city, is a spacious street, principally occupied by retail stores. … The streets are generally well paved, with good side walks,

lighted at night with lamps, and some of them supplied with gas lights. —The Treasury of Knowledge, and Library of Reference (1834)

1 Introduction

It has long been known that the Grand Dyck lattice paths—corresponding to ballot counting ending in a tie—and Dyck-path prefixes—when one candidate remains in the lead throughout the counting—are in bijection [10, p. 96]. More recently it has been shown that this is also true when steps are restricted to a band of restricted height [5, 14], sometimes called corridor paths [1]. Imagine walking in Manhattan, sticking west of Broadway (Figure 1). We set out to generalize this relationship between sets of paths to all possible starting points and ending ranges.

Figure 1: Manhattan neighborhoods, with east-west streets and north-south avenues, bounded by Broadway on the east and the Hudson River on the west, with Union Square serving as origin. (Image \begin{matrix}c \\ ◯ \end{matrix} Hagstrom Map Company, Inc.,

in the public domain at https://www.maps-of-the-usa.com/usa/new-york/new-york/
large-detailed-road-map-of-south-manhattan-nyc.)

Steps in monotonic lattice paths are diagonal: NE (northeast, ↗, a “rise”), taking ⟨x, y⟩ ↦ ⟨x + 1, y + 1⟩, and SE (southeast, ↘, a “fall”), taking ⟨x, y⟩ ↦ ⟨x + 1, y − 1⟩.

Let i �_{h}^{n} ℓ, or just i �^{n} ℓ (fixing h), denote the number of monotonic paths from ⟨0, i⟩ to ⟨n, ℓ⟩ with n steps that stay within (but may touch) the boundaries y = 0 and y = h, for some given (maximum) height h. Height here is the maximum length of a unidirectional path—just NE or just SE. (Some may prefer to say that the width of the corridor is h + 1, since h + 1 ordinate values are allowed.) Let H = [0 : h] = {0, 1, …, h} be the ordinate bounds within which steps are permissible, so steps ⟨x, y⟩ ↦ ⟨x + 1, y ± 1⟩ come now with the proviso regarding the new ordinate position that y ± 1 ∈ H, as the case may be. It is easy to see that the only nonzero counts of n-step paths starting at level i and ending at ℓ occur when n + i ≡ ℓ (mod 2). See Figure 2 for a sample path in 1 �_{4}^{12} 3, borrowing the same notation for the set of paths as for its cardinality.

h = k = i = ℓ } = J

Figure 2: A diagonal path (counted by) 1 �^{12} 3, which goes from i = 1 to ℓ = 3 in a dozen steps, consisting of 7 NE-steps and 5 SE-steps, with bound h = 4. The target region J is ⟦ 2 ± 1 ⟧ = [1 : 4]; its center is k = 2 (the dashed red line), and j = 1 determines its width. There is one feasible endpoint at or below k and one above.

0 1 2 3 4

Figure 3: A right-left version of the same constrained path 1 �_{4}^{12} 3, consisting of 7 right (+) steps (colored gray) and 5 left (−) steps (teal) along a 5-vertex point graph P_{5} (labeled 0,1,2,3,4), starting at vertex i = 1. It is an accordion fold of the blue path in Figure 2. The path in this representation is ++−++−−−−+++, based at 1. The green vertical line serves as a “center of attraction.” (See Section 5 and Figure 5.)

The basic recurrence is

i �^{n} ℓ = \begin{cases}0 , & if i ∉ H or ℓ ∉ H; \\ [i = ℓ] , & if n = 0; \\ (i �^{n−1} ℓ − 1) + (i �^{n−1} ℓ + 1) , & otherwise, \end{cases}

where the bracketed condition [i = ℓ] is Iverson’s notation for a characteristic function (1 when true; 0 when false), and the conditions are taken in order.

The ends of the paths we are interested in fall within a range J, not just a single point ℓ. For example, the window J = [5 : 10] has 6 possible landing spots, but only half of them are feasible, depending on whether n + i is odd or even. Only those ℓ ∈ J with the same parity as n + i are relevant. Our goal is to count

i �^{n} J = ∑_{ℓ∈J} i �^{n} ℓ = ∑_{\begin{matrix}ℓ∈J \\ ℓ≡n+i (mod 2) \end{matrix}} i �^{n} ℓ ,

the number of paths constrained to a corridor H = [0:h] and ending at any (feasible) ordinate in the window J.

These constrained lattice paths are equivalent to walks along a path graph, forward and backward. See Figure 3. When i = 0 (at the bottom) and J = H (anywhere), walks for h = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 are enumerated at \underline{A000007} (constant 0 after initial 1), \underline{A000012} (constant 1), \underline{A016116} (2^{⌊n/2⌋}), \underline{A000045} (Fibonacci), \underline{A038754} (\{1, 2\}3^{n}), \underline{A028495}, \underline{A030436}, \underline{A061551}, \underline{A178381}, \underline{A336675}, \underline{A336678}, respectively, in Sloane’s Encyclopedia of Integer Sequences (OEIS) [21]. (Most of this list was compiled by Bryant [1]. The sequences for h = 9, 10 were added recently by this author.)

Such paths in a path graph having h edges can also be viewed as prefixes of Dyck paths of bounded height h, since they start at the bottom but may end anywhere on or above the bottom line. Their number is known to be equal to that of Grand Dyck paths of the same length, which start in the middle of the band, may go above or below the middle line—as long as they stay within bounds, and which we allow to end up either in the middle or just above [5]. So, each of the above sequences also counts constrained Grand Dyck paths. This explains the inclusion also of even- and odd-indexed partitions of the corridor sequences in Sloane’s OEIS: They are enumerations of (combinatorial objects in bijection with) the Grand Dyck paths ending on the diagonal (in the middle of the corridor) and of those ending one row above. For example, sequence \underline{A336678} for h = 10 is the alternation of sequences \underline{A087944} and \underline{A087946}.

Usually, Grand Dyck paths are defined to be of even length and to end up back on the starting line—as in a tie vote. To be more inclusive, we are allowing odd-length Grand Dyck paths that terminate one line above—adopting the same moniker in the odd case, too (cf. [8]). Accordingly, we can say that the number of Grand Dyck paths of length 2n (“semilength” n) and even height h (with the up-down symmetry of the corridor) is always twice that for 2n − 1. See the middle case of Table 1. (The term “Grand Dyck” is often used for such paths [20]. The interest in these lattice paths is older [6, p. 81]. They are also referred to as “two-sided” or “bilateral” paths on account of their shape [16], as “binomial” or “central binomial” paths on account of their number [18], and as “free” Dyck paths [3]. They are classified as “bridges” [7, 2].)

i n = 0 1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 ℓ  OEIS
4  1  1  2  5  14  41  122  365  1094 4 \underline{A007051}
1  2  5  14  41  122  365  1094  3 \underline{A007051}
1  3  9  27  81  243  729  2187 2 \underline{A000244}
1  4  13  40  121  364  1093  1 \underline{A003462}
1  4  13  40  121  364  1093 0 \underline{A003462}
1  2  5  14  41  122  365  1094  4 \underline{A007051}
3  1  2  5  14  41  122  365  1094  3281 3 \underline{A007051}
1  3  9  27  81  243  729  2187  2 \underline{A000244}
1  4  13  40  121  364  1093  3280 1 \underline{A003462}
1  4  13  40  121  364  1093  0 \underline{A003462}
1  3  9  27  81  243  729  2187 4 \underline{A000244}
1  3  9  27  81  243  729  2187  3 \underline{A000244}
2  1  2  6  18  54  162  486  1458  4374 2 \underline{A025192}
1  3  9  27  81  243  729  2187  1 \underline{A000244}
1  3  9  27  81  243  729  2187 0 \underline{A000244}
1  4  13  40  121  364  1093  4 \underline{A003462}
1  4  13  40  121  364  1093  3280 3 \underline{A003462}
1  3  9  27  81  243  729  2187  2 \underline{A000244}
1  1  2  5  14  41  122  365  1094  3281 1 \underline{A007051}
1  2  5  14  41  122  365  1094  0 \underline{A007051}
1  4  13  40  121  364  1093 4 \underline{A003462}
1  4  13  40  121  364  1093  3 \underline{A003462}
1  3  9  27  81  243  729  2187 2 \underline{A000244}
1  2  5  14  41  122  365  1094  1 \underline{A007051}
0  1  1  2  5  14  41  122  365  1094 0 \underline{A007051}

Table 1: The number of paths i �_{4}^{n} ℓ for i, ℓ ∈ [0 : 4], n ∈ [0 : 16], is found in the subtable labeled i (in the first column), column n, and row ℓ (penultimate column) of that subtable. For example, 2 �^{16} 2 = 0 �^{16} [0 : 4] = 4374 and 3 �^{16} 3 = 4 �^{16} [2 : 4] = 3281. The former corresponds to 2 � ⟦ 2 ± 0 ⟧ = 0 � ⟦ 2 ± 2 ⟧ per Theorem 1; the latter follows from 3 � ⟦ 3 ± 0 ⟧ = 1 � ⟦ 0 ± 0 ⟧ by Lemma 2 and 1 � ⟦ 0 ± 0 ⟧ = 4 � ⟦ 3 ± 1 ⟧ by Corollary 3. As for a bishop on a chessboard, half the squares are unreachable from any given starting point; the few squares that require backward steps are likewise inaccessible. The particular path of Figures 2–4 is included in those counted by the numbers highlighted in blue boldface. Sloane (OEIS) numbers of the row sequences are provided in the last column.

More generally, walks can start anywhere in H (0 ≤ i ≤ h), with the ordinal positions along the route always staying within H. Table 1 (at the end) lists values for the number of paths through a corridor of height h = 4, with one subtable for each starting point (i = 0, 1, 2, 3, 4); Table 2 exhibits h = 5. These may be viewed as constrained versions of Pascal’s triangle, with each entry the sum of two prior entries (cf. [1]).

i n = 0 1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 ℓ  OEIS
5  1  1  2  5  14  42  131  417  1341 5 \underline{A080937}
1  2  5  14  42  131  417  1341  4 \underline{A080937}
1  3  9  28  89  286  924  2993 3 \underline{A094790}
1  4  14  47  155  507  1652  2 \underline{A094789}
1  5  19  66  221  728  2380 1 \underline{A005021}
1  5  19  66  221  728  0 \underline{A005021}
1  2  5  14  42  131  417  1341  5 \underline{A080937}
4  1  2  5  14  42  131  417  1341  4334 4 \underline{A080937}
1  3  9  28  89  286  924  2993  3 \underline{A094790}
1  4  14  47  155  507  1652  5373 2 \underline{a094789}
1  5  19  66  221  728  2380  1 \underline{A005021}
1  5  19  66  221  728  2380 0 \underline{A005021}
1  3  9  28  89  286  924  2993 5 \underline{A094790}
1  3  9  28  89  286  924  2993  4 \underline{A094790}
3  1  2  6  19  61  197  638  2069  6714 3 \underline{A052975}
1  3  10  33  108  352  1145  3721  2 \underline{A060557}
1  4  14  47  155  507  1652  5373 1 \underline{a094789}
1  4  14  47  155  507  1652  0 \underline{a094789}
1  4  14  47  155  507  1652  5 \underline{a094789}
1  4  14  47  155  507  1652  5373 4 \underline{a094789}
1  3  10  33  108  352  1145  3721  3 \underline{A060557}
2  1  2  6  19  61  197  638  2069  6714 2 \underline{A052975}
1  3  9  28  89  286  924  2993  1 \underline{A094790}
1  3  9  28  89  286  924  2993 0 \underline{A094790}
1  5  19  66  221  728  2380 5 \underline{A005021}
1  5  19  66  221  728  2380  4 \underline{A005021}
1  4  14  47  155  507  1652  5373 3 \underline{a094789}
1  3  9  28  89  286  924  2993  2 \underline{A094790}
1  1  2  5  14  42  131  417  1341  4334 1 \underline{A080937}
1  2  5  14  42  131  417  1341  0 \underline{A080937}
1  5  19  66  221  728  5 \underline{A005021}
1  5  19  66  221  728  2380 4 \underline{A005021}
1  4  14  47  155  507  1652  3 \underline{a094789}
1  3  9  28  89  286  924  2993 2 \underline{A094790}
1  2  5  14  42  131  417  1341  1 \underline{A080937}
0  1  1  2  5  14  42  131  417  1341 0 \underline{A080937}

Table 2: Paths i �_{5}^{n} ℓ constrained to height 5, n ∈ [0 : 16]. Sloane (OEIS) numbers of the row sequences are provided in the last column.

In addition to pointing to the formula (Theorem 6) enumerating these more general sets of corridor paths ending in an arbitrary window, we explore a beautiful symmetry between such sets of paths, those starting at level i and ending in a window of size 2j + 2 and those starting at level j and ending in a window of size 2i + 2 centered around the same point (Theorem 1). Three proofs are then provided for this symmetry: by induction (Section 3), by counting (Section 4), and by bijection (Section 5). The final section describes prior work leading up to these results. A brief history of lattice-path enumerations is given by Humphreys [15].

2 Main results

We use the notation ⟦ k ± j ⟧ as shorthand for a range [k − j : k + j + 1], which we make of even size, viz. 2j + 2, by stretching the upper end one spot, to include k + j + 1. Thus, the window ⟦ k ± j ⟧ covers j + 1 feasible endpoints—the odd ones or the even ones, as the case may be—centered about k.

Our main result is the following intriguing equivalence:

Theorem 1. For all n, h ∈ ℕ, k ∈ [0 : h], i, j ∈ [0 : min{k + 1, h − k}]:

i �_{h}^{n} ⟦ k ± j ⟧ = j �_{h}^{n} ⟦ k ± i ⟧ .  (1)

For example, 2 �_{4}^{9} ⟦ 2 ± 1 ⟧ = 162 = 1 �_{4}^{9} ⟦ 2 ± 2 ⟧; see Table 1. The bounds on i and j ensure that the starting points are in H = [0 : h] and that the target windows ⟦ k ± j ⟧ and ⟦ k ± i ⟧ do not extend more than one row above or below the corridor H. (The reason for allowing the window to slightly overextend the corridor is that—when h is even—there are an odd number of possible points in the full height of the corridor, all of which one may wish to include, whereas target windows necessarily cover an even number of landing points.)

Were i or j too big, k ± i or k ± j could extend too far beyond H, and the equality would not hold, as is the case for 2 �_{4}^{9} ⟦ 3 ± 1 ⟧ = 81 ≠ 1 �_{4}^{9} ⟦ 3 ± 2 ⟧ = 121. When k ≤ h/2, the theorem holds as long as i, j ≤ k.

The largest i and j can be is i = ⌊h/2⌋ and j = ⌈h/2⌉ (or vice versa), which gives

⌊h/2⌋ �^{n} H = ⌈h/2⌉ �^{n} H  (2)

and comes as no surprise.

This theorem also holds for the degenerate case k = −1 since the constraints impose i = j = 0, in which case the equivalence is true trivially, and the paths are Dyck paths of bounded height.

By up-down symmetry,

Lemma 2. For all n, h ∈ ℕ, i, j, k ∈ [0 : h],

i �_{h}^{n} ⟦ k ± j ⟧ = (h − i) �_{h}^{n} ⟦ h − k − 1 ± j ⟧ .  (3)

So, for instances when i > ⌊h/2⌋, we can combine this lemma with our theorem to obtain

Corollary 3. The equivalence

i �_{h}^{n} ⟦ k ± j ⟧ = j �_{h}^{n} ⟦ h − k − 1 ± h − i ⟧

holds for all n, h ∈ ℕ, k ∈ [0 : h], i ∈ [max{k, h − k − 1}: h], j ∈ [0 : min{k + 1, h − k}].

If no upper boundary on paths is imposed (effectively when h ≥ n), then we have the following:

Corollary 4. For all n, k ∈ ℕ, i, j ∈ [0 : k + 1]:

i �_{∞}^{n} ⟦ k ± j ⟧ = j �_{∞}^{n} ⟦ k ± i ⟧ .  (4)

The equivalence of unrestricted Grand Dyck and Dyck prefix paths is just one special case (i = k ≥ n/2, j = 0).

In terms of ballots, this means that the likelihood of candidate A never being behind B during the counting by more than j votes and then winning by ℓ . . ℓ + 2i + 1 votes (losing, when negative) is the same as the likelihood of A winning (or losing) by ℓ − j . . ℓ + j + 1 and never being behind B during the counting by more than i (ℓ + 1 ≥ j − i, −j). When j = 0, this translates into the following:

Corollary 5. The likelihood of candidate A never being behind candidate B by more than i votes during the counting of ballots and winning by exactly ℓ votes is equal to the likelihood of A never being behind at all and winning by ℓ to ℓ + 2i votes (for all feasible values of ℓ).

Feasible means that ℓ ≥ 0 and has the right parity (same as the number of steps) for an outcome.

Lastly, a closed-form formula for the paths of interest is as follows:

Theorem 6. The number of corridor paths i �_{h}^{n} ⟦ k ± j ⟧, for all n, h, i, j, k ∈ ℕ, i ≤ h, is

∑_{z=v}^{u} ∑_{\begin{matrix}s=0 \\ 0≤2s+p≤h \end{matrix}}^{j}(\binom{n}{r + z(h + 2) + s} − \binom{n}{r + z(h + 2) + i + s + 1}) ,

where q = n + k − i − j, r = ⌈q/2⌉, p = k − j + q mod 2, v = −⌊(r + i + j + 1)/(h + 2)⌋ and u = ⌊(n − r)/(h + 2)⌋.

3 Inductive proof

One can prove Theorem 1, namely that

i �_{h}^{n} ⟦ k ± j ⟧ = j �_{h}^{n} ⟦ k ± i ⟧ ,

by induction on the number of steps n, with height h fixed throughout.

Recall that the bounds on i and j are

i, j ≥ 0  (5)
i, j ≤ k + 1  (6)
i, j ≤ h − k .  (7)

The cases where either is out of bounds are excluded from the theorem.

For n = 0, the starting and ending points must be the same. The two boundary conditions, viz.

i �^{0} ⟦ k ± j ⟧ = [k − j ≤ i ≤ k + j + 1]
j �^{0} ⟦ k ± i ⟧ = [k − i ≤ j ≤ k + i + 1] ,

are equivalent since we are given that 0 ≤ i, j ≤ k + 1.

In the general case (n > 0), we could argue inductively in the following fashion:

i �^{n} ⟦ k ± j ⟧

= (i − 1 �^{n−1} ⟦ k ± j ⟧) + (i + 1 �^{n−1} ⟦ k ± j ⟧)  (basic recurrence)
= (j �^{n−1} ⟦ k ± i − 1 ⟧) + (j �^{n−1} ⟦ k ± i + 1 ⟧)  (induction)
= (j �^{n−1} ⟦ k − 1 ± i ⟧) + (j �^{n−1} ⟦ k + 1 ± i ⟧)  (definition)
= j �^{n} ⟦ k ± i ⟧  (basic recurrence).

But this only works if the two inductive cases also satisfy the theorem’s constraints. The problematic cases, when the inductive hypothesis cannot be applied, are three:

(a) i = 0, since then i − 1 < 0 violates (5) for the left inductive case i − 1 �^{n−1} ⟦ k ± j ⟧;

(b) i = k + 1, since then i + 1 > k + 1 in violation of (6) for the right inductive case

i + 1 �^{n−1} ⟦ k ± j ⟧;

(c) i = h − k, violating (7) for the right case. Fortuitously, the exact same argument may be applied in the opposite direction, with

the rôles of i and j exchanged, to prove the identical equivalence:

i �^{n} ⟦ k ± j ⟧ = (i �^{n−1} ⟦ k ± j − 1 ⟧) + (i �^{n−1} ⟦ k ± j + 1 ⟧)
= (j − 1 �^{n−1} ⟦ k ± i ⟧) + (j + 1 �^{n−1} ⟦ k ± i ⟧)
= j �^{n} ⟦ k ± i ⟧ .

The cases for which this version of the argument is problematic are analogous but different: (a’) j = 0; (b’) j = k + 1; or (c’) j = h − k.

For the first exception (a), when i = 0, all is well with just one induction:

0 �^{n} ⟦ k ± j ⟧ = 1 �^{n−1} ⟦ k ± j ⟧ = j �^{n−1} ⟦ k ± 1 ⟧ = j �^{n} ⟦ k ± 0 ⟧ .

In the extreme case that k = h, and the induction is invalid, it must also be that j = 0, and the equivalence holds immediately, sans induction. By the same token, case (a’) is also not an issue.

Furthermore, whenever i = j, the theorem holds trivially, so the two combined cases (b,b’), when i = j = k + 1, and (c,c’), when i = j = h − k, are fine, too.

So we only lack a proof for the following two combinations of the exceptions: (b,c’), when i = k + 1, j = h − k, and (c,b’), when j = k + 1 and i = h − k. These are symmetric, so let us delve just into the second. Taking constraints (6, 7) into account, we find that h = 2k + 1, i = k = ⌊h/2⌋, and j = ⌈h/2⌉. So all we have to establish is the case ⌊h/2⌋ �^{n} H = ⌈h/2⌉ �^{n} H, which we’ve already seen (Eq. 2).

4 Combinatorial proof

One can derive the enumeration of Theorem 6 using a standard result for bounded lattice paths. Our main theorem (Theorem 1) will then follow as a corollary.

s= t= ⟨a, b⟩

Figure 4: An orthogonal (“staircase”) path, starting at the origin and ending at ⟨a, b⟩ = ⟨5, 7⟩, consisting of 7 N-steps and 5 E-steps, staying strictly within bounds s = 4 (below y = x + 4) and t = 2 (above y = x − 2). This path and its constraints are analogues of those in Figure 2; see Section 4.

The number M(a, b, s, t) of “monotonic” paths from ⟨0, 0⟩ to ⟨a, b⟩, taking a ∈ ℕ steps to the east (E, →) and b ∈ ℕ steps to the north (N, ↑), while totally avoiding (not touching or crossing) the boundaries y = x + s and y = x − t (s, t ∈ ℤ^{+}), is known by a reflection argument to be

M(a, b, s, t) = ∑_{z∈ℤ}(\binom{a + b}{b + z(s + t)} − \binom{a + b}{b + z(s + t) + t}) ,  (8)

as long as −t < b − a < s, so the endpoint ⟨a, b⟩ is in bounds [11, 17, p. 6]. A closely related analytic enumeration of certain corridor paths is due to Ellis back in 1844 [9]. Figure 4 displays a path between boundary lines.

We note that Eq. (8), as stated, also holds for the cases when b − a is equal to s or to −t since then the two binomials cancel each other for different values of z (for −z when t = a − b; for −z − 1 when s = b − a). And indeed there are no admissible paths that end on the boundary. Thus, we need only limit the formula’s applicability to −t ≤ b − a ≤ s.

There is a straightforward relationship between these constrained N/E paths ⟨0, 0⟩ ⇝ ⟨a, b⟩ and those NE/SE paths ⟨0, i⟩ ⇝ ⟨n, ℓ⟩ that we have set out to study, as illustrated in Figure 2:

n = a + b  ℓ − i = b − a
t = i + 1  s + t = h + 2 .

Substituting the solution

a = \frac{n + i − ℓ}{2}  b = \frac{n − i + ℓ}{2}
s = h − i + 1  t = i + 1

into (8), we get the following:

i �_{h}^{n} ℓ = ∑_{z∈ℤ}(\binom{n}{\frac{n−i+ℓ}{2} + z(h + 2)} − \binom{n}{\frac{n−i+ℓ}{2} + z(h + 2) + i + 1})  (9)

as long as i, ℓ ≤ h [7]. For those ℓ for which \frac{n−i+ℓ}{2} is not a whole number, the binomial coefficients are taken to be 0, adopting the (nonstandard) convention that \binom{n}{m} = 0 whenever m ∉ ℕ.

Letting ℓ move along the window from k − j to k + j + 1, we get from Eq. (9) that

i �_{h}^{n} ⟦ k ± j ⟧ = ∑_{\begin{matrix}ℓ=k−j \\ 0≤ℓ≤h \end{matrix}}^{k+j+1} ∑_{z∈ℤ}(\binom{n}{\frac{n−i+ℓ}{2} + z(h + 2)} − \binom{n}{\frac{n−i+ℓ}{2} + z(h + 2) + i + 1}) .

Skipping over the impossible odd or even values of ℓ (for which the lower indices of the binomial coefficients are fractional) and shifting summation index, this is:

∑_{z∈ℤ} ∑_{\begin{matrix}s=0 \\ 0≤2s+p≤h \end{matrix}}^{j}(\binom{n}{r + z(h + 2) + s} − \binom{n}{r + z(h + 2) + i + s + 1}) ,  (10)

where q = n + k − i − j, r = ⌈q/2⌉, p = k − j + q mod 2. The different values s can take on correspond to the (at most) j + 1 possible endpoints in the window ⟦ k ± j ⟧. The sum for z can be restricted to go from v = −⌊(r + i + j + 1)/(h + 2)⌋ to u = ⌊(n − r)/(h + 2)⌋, or to laxer bounds, of course. We have, thus, arrived at the stated formula of Theorem 6.

From here on, consider only the cases considered in Theorem 1, which guarantee that k − j ≥ −1 and that k + j ≤ h + 1, so s may run from 0 to j without exception, being that −1 ≤ 2s + p ≤ h + 1 (all that is actually needed) necessarily holds.

When i = 0, the inner sum in Eq. (10) simplifies, leaving only

∑_{z=v}^{u}(\binom{n}{⌈\frac{n+k−j}{2} ⌉ + z(h + 2)} − \binom{n}{⌈\frac{n+k+j}{2} ⌉ + z(h + 2) + 1}) .  (11)

When also k = j = ⌊h/2⌋, this formula counts Dyck prefixes of bounded height:

∑_{z=v}^{u}(\binom{n}{⌈n/2⌉ + z(h + 2)} − \binom{n}{⌈n/2⌉ + ⌊h/2⌋ + z(h + 2) + 1}) ,  (12)

recovering (an equivalent of) Cigler’s formula [5, Eq. 1.1], derived by inclusion/exclusion. It likewise counts bounded Grand Dyck paths.

When h is n or more, the boundary has no impact on the allowed paths. Only z = 0 and the first binomial in Eq. (12) contribute to the count, yielding simply the central binomial coefficient

\binom{n}{⌈n/2⌉} = \binom{n}{⌊n/2⌋} ,

which enumerates unrestricted Dyck prefixes, as is well known.

When k = j = 0 and n = 2m, Eq. (11) gives the number of even-length Dyck paths of semi-length m and bounded height h:

∑_{z=−⌊m/(h+2)⌋}^{⌊m/(h+2)⌋}(\binom{2m}{m + z(h + 2)} − \binom{2m}{m + z(h + 2) + 1}) ,

an enumeration due to Grossman in his “Fun with lattice points” series [13]. See sequences \underline{A011782}, \underline{A001519}, \underline{A124302}, \underline{A080937}, \underline{A024175}, \underline{A080938}, \underline{A033191}, \underline{A211216} in Sloane [21] for h = 2, 3, 4, 5, 6, 7, 8, 9, and \underline{A080936} for a table for all h. The same formula counts Dyck prefixes of odd length 2m − 1 ending at y = 1.

Reversing the order of summation for the second binomial in (10), replacing s with j − s, we have

∑_{z∈ℤ}(∑_{s=0}^{j} \binom{n}{r + z(h + 2) + s} − ∑_{s=0}^{j} \binom{n}{r + z(h + 2) + i + j − s + 1}) .

When j > i, the inner sums overlap for all s > i and cancel each other, so one needs only sum for s until min{i, j}:

∑_{z∈ℤ} ∑_{s=0}^{min\{i,j\}}(\binom{n}{r + z(h + 2) + s} − \binom{n}{r + z(h + 2) + i + j − s + 1}) .

As this is symmetric in i and j, Theorem 1 is vindicated.

5 Bijective proof

A bijection can be inferred from the inductive proof of Section 3 for the equivalence of the enumerations:

i �^{n} ⟦ k ± j ⟧ = j �^{n} ⟦ k ± i ⟧ .  (13)

We use a novel representation for paths, which simplifies matters greatly.

Draw a line y = k + 1/2; we’ll call it the center of attraction. Each step starting out toward that line is labeled T; each heading away is labeled A. From any given point, exactly one outgoing step (↗ or ↘) will be T and one A. Usually, going backward along a T step is like an A step, except when crossing the center line, where it is T both ways. Going back along an A step is always T. We call this the TA representation of a lattice path (relative to k). See Figure 5.

Suppose the ordinate of a point along the path is in the window ⟦ k ± j ⟧ = [k − j : k + j + 1]. If we take an A step from there, then the next point is in the wider window ⟦ k ± j + 1 ⟧ = [k − j − 1 : k + j + 2]; so j has been incremented. Conversely, a T step brings it into the narrower range ⟦ k ± j − 1 ⟧ = [k − j + 1 : k + j], with decremented j, unless j is already 0, in which case it stays the same.

If we take this point of view and go through the cases of the inductive proof, we find that the correspondence simply reverses the order of steps, either moving the last step to the beginning or vice versa. When i = j, there is no need to do anything, since the two sides of the equivalence (13) are identical. We are led to the following bijection between a path P starting at y = i and ending in the range ⟦ k ± j ⟧ and its counterpart path P^{∗} starting at y = j and ending in ⟦ k ± i ⟧:

(=) If i = j, then P^{∗} = P.

(<) If i < j, follow the path from the start at level i until it reaches j, if ever. At that point, we have P = QR, where y = j is first reached at the end of prefix Q. Then P^{∗} = R^{⟵} Q, where ^{⟵} Q is the reverse sequence of Q in its TA representation. If level j is never attained, then R is empty, and P^{∗} =^{⟵} P.

(>) If i > j, follow the path from the end backward, starting with a target window of size j, moving leftwards until it grows to be i, if ever. A T step taken backward enlarges the window, while A shrinks it. If R is the shortest suffix such that the window size is i at its onset, so that we have P = QR, then we let P^{∗} = ^{⟵} RQ. If the window never attains size i, then P^{∗} =^{⟵} P.

h = k = i = j = ℓ } 0 } 1 } 2 A T A T A T T T T A T A T T A T A T T A T A T A

Figure 5: The 12-step (blue) path P from level i = 1 to level ℓ = 5 belongs to the class enumerated by 1 �^{12} ⟦ 3 ± 2 ⟧. Since k = 3, steps are labeled T when they start out toward the “attractor” y = 3.5 (the dashed green line), and A when they head away in the opposite direction. Accordingly, path P is labeled ATATATTTTATA. Windows of sizes 0, 1, and 2 around the green attractor are shown to the right of the grid. The target window size is j = 2, so we are in the (<) case of the bijection. After seven (solid blue) steps ATATATT, the path touches y = 2, so the remaining 5 (dotted) steps, TTATA, are copied as is and placed with ⟨0, 2⟩ as their initial point (dotted purple), followed by the first seven in reverse (solid purple), that is, TTATATA, to obtain the corresponding path P^{∗}. The result is TTATATTATATA, one of those counted by 2 �^{12} ⟦ 3 ± 1 ⟧, which all start from j = 2 and end in [2 : 5]. The lower path P minus its head, viz. 0 �^{11} 5, corresponds to the upper (purple) path P^{∗} minus its tail, 2 �^{11} 3, which ends in a size 0 window. The initial A step serves to extend that 11-step (purple) path with a downwards A step that enlarges the window but remains in bounds. The counterpart of this (purple) path is again the original (in blue), and is obtained by proceeding from the end toward the beginning until the window size becomes 2, per case (>). The actual windows at each point along the reversed (solid purple) segment are shown (as brown bars), going from size 2 at x = 5, through 1, 0, 1, 0, 1, 0, ending with size 1. On account of the unusual encoding, the reversed (solid) path segments do not actually resemble each other visually. See Section 5 for details.

The path in Figure 2 is its own counterpart as this is an instance of case (=) with i = j = 1. For a worked-out nontrivial example, see Figure 5.

Consider case (<), when i < j. A path in i �^{n} ⟦ k ± j ⟧ is composed of two parts: the Q part starting from y = i and never crossing y = j; and the R part, which—when nonempty— goes from y = j until y = ℓ ∈ ⟦ k ± j ⟧. Considering that i < j ≤ k + 1, all T steps in Q are upward, and all A’s are downward. So the net difference in ordinate value at the start and end of Q is at most j − i, and likewise the number of T’s in Q minus the number of A’s is at most j − i. The corresponding segment ^{⟵} Q in the path P^{∗} = R^{⟵} Q starts either at ℓ in the nonempty case or else at j. In either event, the starting point of ^{⟵} Q is within ⟦ k ± j ⟧. In the nonempty case, because R ends at ℓ; in the empty case, on account of the fact that j is higher than the end of P, which itself is in ⟦ k ± j ⟧. Each T step in ^{⟵} Q moves the path toward the center of attraction and shrinks the window; each A step enlarges it. Hence, the ending point is within ⟦ k ± j − (j − i) ⟧ = ⟦ k ± i ⟧, as required.

It is also not hard to verify that the transpositions involved keep the path within the bounded corridor, given that the original path satisfies 0 ≤ i, j ≤ min{k + 1, h − k}. The points along the Q segment all lie in the range [0 : j], reaching j only at the end—if ever. Thus, the corresponding path stays within the window ⟦ k ± j ⟧, and can only be at the edge of that window initially. Just as each T step increases the vertical position (since k lies above) along the given path but never exceeds j, so too the T step in ^{⟵} Q shrinks the window from its initial maximal size j, but never below 0. Likewise, an A step decreases the vertical position down to 0, while the A step in the corresponding path enlarges the window, but only up to size j. Those remaining steps R that are copied as is clearly remain in bounds. Figure 5 portrays how the window size changes along ^{⟵} Q.

The symmetric case, with j < i, is perfectly analogous, starting instead from the paths j �^{n} ⟦ k ± i ⟧ counted on the right side of (13).

Thus we have attained a bijective proof of Theorem 1. We note that the inductive proof allows for alternate bijections depending on the preferred order in which the different cases are to be considered.

6 Historical discussion

Theorem 1, our main result, is a significant generalization of the equality given by Cigler [5], namely,

0 �_{h}^{n} [0 : h] = ℏ �_{h}^{n} [ℏ: ℏ + 1]  (14)

for all heights h, where ℏ = ⌊h/2⌋ for short. Paths (counted by) ℏ �^{n} [ℏ: ℏ + 1] start in the middle of the swath and end either in the middle—when the number of steps is even, or just above—when odd. As noted earlier, these are called “Grand Dyck” paths. Dyck path prefixes 0 �^{n} [0 : h] start at the bottom and end anywhere within the swath. Cigler’s (14) asserts the equality of cardinality of these two sets of paths. As such, it is a particular instance of our more general result (1) with i = 0 and j = k = ℏ. Phrased in our notation, Cigler demonstrated:

0 �_{h}^{n} ⟦ ℏ ± ℏ ⟧ = ℏ �_{h}^{n} ⟦ ℏ ± 0 ⟧ .

Cigler solicited alternative proofs of his result. More specifically, he asked for a bijective proof of the height h = 3 case,

0 �_{3}^{n} [0 : 3] = 1 �_{3}^{n} [1 : 2] ,

which gives rise to the Fibonacci numbers [4]. The wished-for bijective solution to this very particular case was discovered shortly thereafter by Prellberg [4, Answer], followed by another due to Prodinger [19]. Most recently, Gu and Prodinger [14] have constructed a bijection for Cigler’s full case (14) by extending Prodinger earlier suggestion.

When there are no upper and lower bounds on paths, there are long-standing, well-known bijections between Grand Dyck paths and Dyck path prefixes,

0 �_{∞}^{n} ⟦ k ± k ⟧ = k �_{∞}^{n} ⟦ k ± 0 ⟧ ,

for k ≥ n/2, as mentioned earlier [10, 12]. Csáki and Mohanty [7, Theorem 3.1], in fact, already proved the following generalization to corridors by means of an inductively constructed bijection:

0 �_{h}^{n} ⟦ k ± k ⟧ = k �_{h}^{n} ⟦ k ± 0 ⟧ .

Our bijection in the previous section proves the substantially more general equivalence

i �_{h}^{n} ⟦ k ± j ⟧ = j �_{h}^{n} ⟦ k ± i ⟧ .

In particular, it supplies an alternative proof of Cigler’s instance (14). In that special case, the bijection amounts to simply reversing the order of steps in the TA representation. This works as is for even n in the Grand Dyck (i = k = ℏ and j = 0) to Dyck-prefix (i = 0 and j = k = ℏ) case of Cigler, as this is the (i > j) case of the bijection and the window never grows too big to continue all way to the beginning. (It may get to be ℏ; the maximum excess of T moves over A moves, but no larger.) Unfortunately, simple reversal does not do the trick when n is odd and h is even because proceeding only backward can lead to a window wider than ℏ = i. (For example, TAT is a valid path in 0 �^{3} [0 : 3], but TAT is not in 1 �^{3} [1 : 2]. The bijection of the previous section reverses only part and yields the valid ATT instead.) For the odd n case, it is possible to modify the bijection by first reversing the Grand Dyck path left to right (so it ends on y = ℏ but begins at i = ℏ + 1) before converting to the TA representation and reversing. This now covers all cases of (14). The second bijection also works for even h and even n. For odd h, regardless of the parity of n, the first bijection actually succeeds for all i, j meeting the requirements of the theorem. So, when n and h have the same parity, both bijections work. In the more general cases, when k ≠ ℏ, neither applies, and we resort to the slightly more complicated bijection of the previous section, wherein only part of the TA path is reversed.

We began our investigation seeking a bijective proof of (14). The simple bijection employing the TA path encoding did not work in all cases. This led us to a sequence of generalizations, commencing from Cigler’s (14):

0 �_{h}^{n} ⟦ ℏ ± ℏ ⟧ = ℏ �_{h}^{n} ⟦ ℏ ± 0 ⟧
i �_{h}^{n} ⟦ ℏ ± ℏ ⟧ = ℏ �_{h}^{n} ⟦ ℏ ± i ⟧
i �_{h}^{n} ⟦ ℏ ± j ⟧ = j �_{h}^{n} ⟦ ℏ ± i ⟧
i �_{h}^{n} ⟦ k ± j ⟧ = j �_{h}^{n} ⟦ k ± i ⟧ .

First we let i be anywhere (not just 0), then we let j be any size (not just ℏ), and finally allowed it to be centered at any k (not just ℏ). Concurrently, we programmed various enumerations and potential bijections to lend support to—or refute—conjectures as they arose. Casting the equivalence in a fashion that highlights its symmetry also contributed to finding the generalizations and proofs.

All the above variants share the basic idea that, as the starting point of one set of paths moves from the edge of the corridor toward the middle, the target range of the corresponding equinumerous set of paths grows wider and wider. This behavior is what suggested the TA encoding in the first place.

7 Acknowledgments

I gratefully thank Johann Cigler for encouragement, references, and advice, Christian Rinderknecht for first bringing Cigler’s interesting challenge to my attention, and a referee for her critique.

References

[1] S. V. Ault and C. Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Math. 332 (2014), 45–54.

[2] C. Banderier and P. Flajolet, Basic analytic combinatorics of directed lattice paths, Theoret. Comput. Sci. 281 (2002), 37–80.

[3] W. Y. C. Chen, S. X. M. Pang, E. X. Y. Qu, and R. P. Stanley, Pairs of noncrossing free Dyck paths and noncrossing partitions, Discrete Math. 309 (2009), 2834–2838.

[4] J. Cigler, Is there a simple bijection between the following sets A n and B n which are counted by the Fibonacci numbers?, 2015. ResearchGate post, https://www.

    researchgate.net/post/Is_there_a_simple_bijection_between_the_following_

    sets_A_n_and_B_n_which_are_counted_by_the_Fibonacci_numbers.

[5] J. Cigler, Some remarks and conjectures related to lattice paths in strips along the xaxis, preprint, 2015. Available at https://arXiv.org/abs/1501.04750, since revised.

[6] L. Comtet, Advanced Combinatorics, Reidel, 1974.

[7] E. Csáki and S. G. Mohanty, Excursion and meander in random walk, Canad. J. Statist. 9 (1981), 57–70.

[8] S. Elizalde, Bijections for pairs of non-crossing lattice paths and walks in the plane, European J. Combin. 49 (2015), 25–41.

[9] R. L. Ellis, On the solution of equations in finite differences, Cambridge Math. J. 4 (1844), 182–190. Reprinted in W. Walton, ed., The Mathematical and Other Writings of Robert Leslie Ellis, M.A., Deighton, Bell, and Co., 1863, pp. 202–211.

[10] W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, Wiley, 3rd edition, 1968.

[11] R. D. Fray and D. P. Roselle, Weighted lattice paths, Pacific J. Math. 37 (1971), 85–96.

[12] C. Greene and D. J. Kleitman, Strong versions of Sperner’s theorem, J. Combin. Theory Ser. A 20 (1976), 80–88.

[13] H. D. Grossman, Fun with lattice points, Scripta Math. 15 (1949), 79–81.

[14] N. S. S. Gu and H. Prodinger, Combinatorics on lattice paths in strips, preprint, 2020.

Available at https://arXiv.org/abs/2004.00684.

[15] K. Humphreys, A history and a survey of lattice path enumeration, J. Statist. Plann. Inference 140 (2010), 2237–2254.

[16] R. J. Lipton and Y. Zalcstein, Word problems solvable in logspace, J. Assoc. Comput. Mach. 24 (1977), 522–526.

[17] S. G. Mohanty, Lattice Path Counting and Applications, Vol. 37 of Probability and Mathematical Statistics, Academic Press, 1979.

[18] E. Pergola, Two bijections for the area of Dyck paths, Discrete Math. 241 (2001), 435–447.

[19] H. Prodinger, Height restricted lattice paths, Elenas, and bijections, preprint, 2016.

Available at https://arXiv.org/abs/1601.00230.

[20] L. W. Shapiro and W.-J. Woan, Some generating function proofs of old and new results in probability, Congr. Numer. 143 (2000), 193–205.

[21] N. J. A. Sloane et al., The on-line encyclopedia of integer sequences, 2020. Available at

https://oeis.org.

2010 Mathematics Subject Classification: Primary 05A15. Keywords: path enumeration, lattice path, corridor path, Grand Dyck path, Dyck prefix, bijection.

(Concerned with sequences \underline{A000007}, \underline{A000012}, \underline{A000045}, \underline{A000244}, \underline{A001519}, \underline{A003462}, \underline{A005021}, \underline{A007051}, \underline{A011782}, \underline{A016116}, \underline{A024175}, \underline{A025192}, \underline{A028495}, \underline{A030436}, \underline{A033191}, \underline{A038754}, \underline{A052975}, \underline{A060557}, \underline{A061551}, \underline{A080936}, \underline{A080937}, \underline{A080938}, \underline{A087944}, \underline{A087946}, \underline{A094789}, \underline{A094790}, \underline{A124302}, \underline{A178381}, \underline{A211216}, \underline{A336675}, and \underline{A336678}.)

Received January 13 2021; revised versions received January 14 2021; January 27 2021; January 30 2021. Published in Journal of Integer Sequences, January 30 2021.

Return to Journal of Integer Sequences home page.