Counting Lattice Paths by Narayana Polynomials

Robert A. Sulanke Boise State University Boise, Idaho, USA

                       <sulanke@math.boisestate.edu>

Submitted: April 15, 2000; Accepted: August 3, 2000

Abstract

Let d(n) count the lattice paths from (0, 0) to (n, n) using the steps (0,1), (1,0), and (1,1). Let e(n) count the lattice paths from (0, 0) to (n, n) with permitted steps from the step set ℕ × ℕ − {(0, 0)}, where ℕ denotes the nonnegative integers. We give a bijective proof of the identity e(n) = 2^{n−1}d(n) for n ≥ 1. In giving perspective for our proof, we consider bijections between sets of lattice paths defined on various sets of permitted steps which yield path counts related to the Narayana polynomials.

Mathematical Reviews Subject Classification: 05A15

Key words: Lattice paths, Narayana numbers, Delannoy numbers.

1 Introduction

In the plane ℤ × ℤ let D(n) denote the set of all lattice paths from (0, 0) to (n, n) using steps from the step set {(0, 1), (1, 0), (1, 1)}. The path counts (|D(n)|)_{n≥0} = (1, 3, 13, 63, 321, 1683, …) are the well-known central Delannoy numbers. Let E(n) denote the set of all lattice paths from (0, 0) to (n, n) with permitted steps from the step set ℕ × ℕ − {(0, 0)}, where ℕ denotes the nonnegative integers. Figure 1a (1f, resp.) illustrates a path in E(8) (D(8), resp.) if the first step is ignored.

We will give a bijective proof for the identity

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

for n ≥ 1, as requested in Stanley’s [4] Exercise 6.16. (A proof using generating functions appears in [4].) To give perspective for our proof, we will consider bijections between various sets of lattice paths which have path counts related to Narayana polynomials. The known results of the first two sections serve as background for the results of the last two sections.

This paper will consider six step sets which are labeled arbitrarily by S_{i} for i = 1 … 6. Table 1 contains a list of these step sets and an index to the path sets considered. Given a specific step set S_{i}, let A_{i}(n) denote the set of all lattice paths running from (0, −1) to (n, n) that use the steps in S_{i} and that remain strictly above the line y = −1 except initially. Let L_{i}(n) denote that subset of A_{i}(n) whose member paths remain strictly above the line y = x − 1 except initially.

We complete this section by introducing the Narayana polynomials in terms of lattice paths. For the step set S_{1} = ℙ × ℙ, with ℙ denoting the positive integers, let A_{1}(n, k) (L_{1}(n, k), resp.) denote the set of paths in A_{1}(n) (L_{1}(n), resp.) having k steps. For example, A_{1}(2, 1) contains just one path formed by the single step (2, 3). Further, A_{1}(2, 2) = {(1, 1)(1, 2), (1, 2)(1, 1)}, L_{1}(2, 1) = {(2, 3)}, and L_{1}(2, 2) = {(1, 2)(1, 1)}.

Proposition 1 For 0 < k ≤ n,

|A_{1}(n, k)| = \binom{n − 1}{k − 1}\binom{n}{k − 1}  (1)

|L_{1}(n, k)| = \frac{1}{k}\binom{n − 1}{k − 1}\binom{n}{k − 1} = \frac{1}{n}\binom{n}{k − 1}\binom{n}{k}.  (2)

Proof. The right side of (1) simply counts the ways to assign the coordinates of the end points of the steps constituting a path in A_{1}(n, k). E.g., consider the path (2, 1)(1, 1)(1, 3) ∈ L_{1}(4, 3), expressed as a sequence of steps; here the endpoints of the steps have coordinates (2, 0), (3, 1), and (4, 4), so that {2, 3} ⊂ {1, 2, 3} and {0, 1} ⊂ {0, 1, 2, 3}.

Since exactly one of the k cyclic permutations of any path in A_{1}(n, k) lies in L_{1}(n, k), the middle formula of (2) follows from (1). See [5] for details of this use of the cycle lemma. □

With V denoting the unit vertical step (0, 1) and H denoting the unit horizontal step (1, 0), let S_{2} be the common step set {V, H}. Here, for example, L_{2}(2) = {V V V HH, V V HV H, }. Observe that each step (u, v) ∈ S_{1} determines a vertical step (0, v) followed by a horizontal step (u, 0), and conversely. Hence there is an immediate matching between A_{1}(n, k) and A_{2}(n, k), where A_{2}(n, k) is that subset of A_{2}(n) in which each path has k peaks (i.e., consecutive V H pairs or right turns). Thus |A_{1}(n)| = |A_{2}(n)|. Likewise, there is an immediate matching between L_{1}(n, k)

section step set  path sets
1 S_{1} = ℙ × ℙ A_{1}(n), A_{1}(n, k), L_{1}(n), L_{1}(n, k)
S_{2} = { (0, 1), (1, 0)}  A_{2}(n), A_{2}(n, k), L_{2}(n), L_{2}(n, k)
2  S_{3} = {(0, 1), (1, 0), (1, 1)} L_{2}(n), L_{2}^{c}(n; z), L_{2}^{cc}(n; z), L_{3}(n)
3  S_{4} = (ℙ × {0}) ∪ ({0} × ℙ) L_{4}(n), L_{4}^{0}(n), L_{2}^{∗}(n)
4 S_{5} = ℕ × ℕ − {(0, 0)} A_{5}(n), A_{5}^{0}(n), L_{5}(n), L_{5}^{0}(n), A_{3}^{0}(n)
S_{6} = ({0} × ℙ) ∪ {(1, 0)} L_{6}(n), A_{2}^{ℓ}(n), A_{2}^{cc}(n), A_{6}(n), A_{6}^{0}(n)

Table 1: This table gives the definitions for six step sets together with the symbols for various path sets, each of which is introduced in the corresponding section. Here ℕ (ℙ, resp.) denotes the set of nonnegative (positive, resp.) integers.

and L_{2}(n, k) where L_{2}(n, k) is that subset of L_{2}(n) in which each path has k peaks; thus |L_{1}(n)| = |L_{2}(n)|.

The count, |L_{2}(n, k)| = \frac{1}{n} \binom{n}{k−1}\binom{n}{k}, is known as a Narayana number, and

N_{n}(z) = ∑_{k=1}^{n} \frac{1}{n}\binom{n}{k − 1}\binom{n}{k}z^{k}

is known as the n^{th}-Narayana polynomial. Studies of these polynomials are given by Bonin, Shapiro, and Simion [1] and the author [6]. The sequence (N_{n}(1))_{n≥0} = (1, 1, 2, 5, 14, …) is well known as the Catalan numbers, while the sequence (N_{n}(2))_{n≥0} = (1, 2, 6, 22, 90, …) is known as the large Schröder numbers.

2 Peaks, double ascents, and large Schröder paths

For positive integer z, replicate each path in L_{2}(n) by independently coloring its peaks with colors from a set of z colors where we require blue (b) and red (r) to be present whenever z ≥ 2. Let L_{2}^{c}(n; z) denote the set of all such paths with colored peaks. For example, the six paths of L_{2}^{c}(2; 2) can be listed as V V V bHH, V V V rHH, V V bHV bH, V V bHV rH, V V rHV bH, and V V rHV rH. ¿From the previous section we have that the restricted paths with colored peaks are counted in terms of the Narayana polynomials as follows.

Proposition 2

|L_{2}^{c}(n; z)| = N_{n}(z).

On any path the intermediate vertex of a consecutive V V pair is called a double ascent. Let L_{2}^{cc}(n; z) denote the set of paths replicated from L_{2}(n) by independently coloring each double ascent from the same set of z colors that were available for the peaks. For example, the six paths of L_{2}^{cc}(2; 2) can be listed as V bV bV HH, V bV rV HH, V rV bV HH, V rV rV HH, V bV HV H, and V rV HV H.

We define can a bijection

f : L_{2}^{cc}(n; z) ⟶ L_{2}^{c}(n; z)  (3)

as follows: Let R ∈ L_{2}^{cc}(n; z) be determined by the coordinates of its peaks, say, (x_{1}, y_{1}), …, (x_{k}, y_{k}). (The coordinates of a peak are the coordinates of the vertex between the V and H steps.) Then (x′_{1}, y′_{1}), …, (x′_{h}, y′_{h}), …, (x′_{n+1−k}, y′_{n+1−k}) will be the coordinates of the peaks of the path f(R) where

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

with x′_{1} < x′_{h} < x′_{n+1−k} and y′_{1} < y′_{h} < y′_{n+1−k} so that the peak at (x′_{h}, y′_{h}) has the same color as the intermediate vertex of the double ascent on R with ordinate x′_{h}. Hence Proposition 2 implies the following:

Proposition 3

|L_{2}^{cc}(n; z)| = N_{n}(z).

As an example of the map f, let R = V bV rV HV bV HV HHV rV HHHV H ∈ L_{2}^{cc}(8; 2) with peak set {(0, 2), (1, 4), (2, 5), (4, 7), (7, 8)}. The image path is f(R) = V V V V bHV V rHHV bHHHV V rHH ∈ L_{2}^{c}(8; 2) where now the colors b and r label peaks. We illustrate the bijection f for these paths in Figures 1d and 1e. (We use “A = {1, 5}” in Section 4. )

For the step set, S_{3} = {V, H, D}, where D = (1, 1), the paths of L_{3}(n) are known as large Schröder paths since |L_{3}(n)| = N_{n}(2), which is a Schröder number. (Usually in the literature the initial vertical step from (0, −1) to (0, 0) is omitted.) This last equation follows from the bijection

g : L_{2}^{c}(n; 2) ⟶ L_{3}(n)

where, for P ∈ L_{2}^{c}(n; 2), the path f(P) is simply obtained by replacing each blue peak, i.e., blue VH pair, with the step D and by removing the color from each red peak. Figures 1e and 1f give an example of the map g with “A = {1,5}” ignored. the electronic journal of combinatorics 7 (2000), #R40 5

Figure 2.1: Related paths

3 Arbitrary vertical and horizontal steps

Here we consider paths with vertical and horizontal steps of varying lengths, which can be viewed as “positive rook” moves. Take S_{4} = (ℙ × {0}) ∪ ({0} × ℙ). For example, L_{4}(1) = {(0, 1)(0, 1)(1, 0), (0, 2)(1, 0)}.

Proposition 4

|L_{4}(n)| = N_{n}(4)/2.

We remark that, if L_{4}^{0}(n) denotes the set of those paths in L_{4}(n) that begin with unit vertical step, then clearly, for n > 0, |L_{4}^{0}(n)| = |L_{4}(n)|/2. We find that (|L_{4}^{0}(n)|)_{n≥0} = (1, 1, 5, 29, 185, 1257, 8925, …). Deutsch’s [2] interest in counting L_{4}^{0}(n) motivated this section.

Proof. Replicate each path in L_{2}(n) by independently labeling the intermediate vertices of its noninitial double ascents with one of the markings ‘pp’, ‘pa’, ‘ap’, or ‘aa’ and labeling the initial double ascent with either ‘p’ or ‘a’. (The purpose for these markings will be clear below.) With L_{2}^{∗}(n) denoting the set of all paths with such labels, we see that |L_{2}^{∗}(n)| = N_{n}(4)/2.

Hence to obtain the proposition, we require a bijection L_{4}(n) ⟶ L_{2}^{∗}(n). We note that each path P ∈ L_{4}(n) determines a path Q ∈ L_{2}(n) which traces the same points in the plane. On the path Q we label the intermediate vertex of each double ascent and each double descent (i.e., HH) by a ‘p’ or an ‘a’ according to the presence or absence of an end point of a step at the same lattice point on the path P. Note also that, on Q, with the exception of the necessary initial double ascent, each double ascent can be matched with the first subsequent double descent for which the intermediate vertices lie on the same line of slope 1. Next let the path Q′ be obtained from Q by relabeling each noninitial double ascent of Q by one of four pairs, pp, pa, ap, or aa, where each pair of letters designates the presence of respective singleton labels on a double ascent and its matching double descent. For Q′ we also remove the labels from the double descents while keeping the label for the initial double ascent. □

As an example of L_{4}(4) ⟶ L_{2}^{∗}(4), take P = (0, 1)(0, 2)(1, 0)(0, 1)(0, 2)(3, 0)(1, 0) ∈ L_{4}(4). Then initially Q = V pV aV HV pV aV HaHaHpH which gets relabeled as the path Q′ = V pV apV HV paV aaV HHHH ∈ L_{2}^{∗}(4).

4 Arbitrary steps

For S_{5} = ℕ×ℕ−{(0, 0)} where ℕ denotes the non-negative integers, let A_{5}^{0}(n) (L_{5}^{0}(n), resp.) denote the set of paths in A_{5}(n) (L_{5}(n), resp.) that begin with a unit vertical step. Let A_{3}^{0}(n) denote the subset of those paths in A_{3}(n) that begin with a unit vertical step, where S_{3} = {V, H, D} as before.

Proposition 5 For n ≥ 1,

|L_{5}^{0}(n)| = 2^{n−1}|L_{3}(n)| = 2^{n−1}N_{n}(2)  (4)
|A_{5}^{0}(n)| = 2^{n−1}|A_{3}^{0}(n)|.  (5)

We remark that without the initial vertical unit step, A_{5}^{0}(n) is essentially E(n) and A_{3}^{0}(n) is essentially D(n) of Section 1. The bijective proof of (5) answers Exercise 6.16 in [4]. For reference we note that (|L_{5}^{0}(n)|)_{n≥0} = (1, 2, 12, 88, 720, 6304, …) and that (|E(n)|)_{n≥0} = (1, 3, 26, 252, 2568, 26928 …).

Proof of (4). We will obtain (4) by establishing a bijection

L_{5}^{0}(n) ⟶ L_{3}(n) × 2^{[n−1]}

where 2^{[n−1]} denotes the collection of subsets of {1, 2, …, n − 1}. The intermediate bijections composing this bijection are illustrated in Figure 1. Written details for the figure follows this proof.

We first define a bijection

h : L_{5}^{0}(n) ⟶ L_{6}(n) × 2^{[n−1]}  (6)

where S_{6} = ({0} × ℙ) ∪ {H}. Let P ∈ L_{5}^{0}(n) and let A be the set of abscissae of the initial points of the horizontal steps of P excepting any step that departs from the y-axis; certainly, A ⊆ {1, …, n − 1}. Let P′ be the path obtained from P by replacing each diagonal step (u, v) by the consecutive pair (0, v)(u, 0) and by leaving the vertical and horizontal steps of P unaltered. Let Q be obtained from P′ by two operations: (1) Replace each horizontal step, say (u, 0), by a string of u H steps. (2) Whenever P departs the y-axis with a non-horizontal step, join the first two steps of P′ to create a new initial vertical step. Equivalently, Q will begin with a unit vertical step (ending at (0, 0)) if, and only if, P leaves the y-axis by a horizontal step. See Figures 1a, 1b, and 1c. Define h(P) to be the pair, h(P) = (Q, A) ∈ L_{6}(n) × 2^{[n−1]}.

Recalling the notation of Section 2, we define a bijection

K : L_{6}(n) ⟶ L_{2}^{cc}(n; 2)  (7)

where Q ∈ L_{5}(n) is matched with a path R ∈ L_{2}^{cc}(n; 2) so that the two paths trace the same points in the plane and each intermediate vertex of a double ascent on Q becomes a red double ascent of R and each lattice point that is interior to a vertical step of Q becomes a blue double ascent of R. With id denoting the identity map,

(g × id) ∘ (f × id) ∘ (K × id) ∘ h : L_{5}^{0}(n) ⟶ L_{3}(n) × 2^{[n−1]}

is the desired bijection yielding (4). □

Below we spell out the example appearing in Figure 1 for this composite bijection:

- P = (0, 1)(0, 1)(1, 1)(0, 2)(1, 0)(2, 1)(0, 1)(1, 1)(2, 0)(1, 1) ∈ L_{5}^{0}(8)

- P′ = (0, 1)(0, 1)(0, 1)(1, 0)(0, 2)(1, 0)(0, 1)(2, 0)(0, 1)(0, 1)(1, 0)(2, 0)(0, 1)(1, 0) with A = {1, 5} ⊂ {1, …, 7} and the knowledge that P departed the y-axis by the non-horizontal step (1, 1)

- Q = (0, 2)(0, 1)H(0, 2)H(0, 1)HH(0, 1)(0, 1)HHH(0, 1)H ∈ L_{6}(8) with A = {1, 5}

- R = V bV rV HV bV HV HHV rV HHHV H ∈ L_{2}^{cc}(8; 2) with A = {1, 5}

- f(R) = V V V V bHV V rHHV bHHHV V rHH ∈ L_{2}^{c}(8; 2) with A = {1, 5}

- g(f(R)) = V V V DV V rHHDHHV V rHH ∈ L_{3}(8) with A = {1, 5}

Proof of (5). We modify the bijections proving (4) to prove (5). A left turn is the intermediate point of a consecutive HV pair. Let A_{2}^{ℓ}(n) (A_{2}^{cc}(n), resp.) denote the set of replicated paths formed from A_{2}(n) so each left turn (double ascent, resp.) is independently colored blue or red. We have a bijection

F : A_{2}^{cc}(n) ⟶ A_{2}^{ℓ}(n)

defined as follows: Let R ∈ A_{2}^{cc}(n) be determined by the set (perhaps empty) of the coordinates of its left turns, namely {(x_{1}, y_{1}), …, (x_{k}, y_{k})}. Then (x′_{1}, y′_{1}), …, (x′_{h}, y′_{h}), …, (x′_{n−k}, y′_{n−k}) are the left turns of the path F (R) ∈ A_{2}^{cc}(n) where

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

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

(We note the reason that the map of (3) is defined with respect to peaks (right turns) while the map F is defined with respect to left turns. On any path of L_{2}(n) the number of V H’s plus the number of V V ’s is n, while the number of HV ’s plus the number of V V depends on the path. On the other hand, on any path of A_{2}(n) the number of HV ’s plus the number of V V ’s is n, while the number of V H’s plus the number of V V ’s depends on the path.)

We have a bijection

G : A_{2}^{ℓ}(n) ⟶ A_{3}^{0}(n)

where, for P ∈ A_{2}^{ℓ}(n), G(P) is obtained by replacing each blue HV pair by D step and by removing the color from any red turns. Finally, with the maps

h : A_{5}^{0}(n) ⟶ A_{6}(n) × 2^{[n−1]} and K : A_{6}(n) ⟶ A_{2}^{cc}(n)

defined in the same ways as the maps are defined in (6) and (7), we have

(G × id) ∘ (F × id) ∘ (K × id) ∘ h : A_{5}^{0}(n) ⟶ A_{3}^{0}(n) × 2^{[n−1]}

is a bijection yielding (5). □

We remark that Shapiro gave a problem [3, vol. 89, Problem 6391] asking for a formula for (|A_{6}^{0}(n)|)_{n≥0} = (1, 2, 9, 44, 225, 1182, 6321, …), where A_{6}^{0}(n) is the set of all paths from (0, 0) to (n, n) that use step set S_{6}. An interesting solution appears in [3, vol. 90].

References

[1] J. Bonin, L. Shapiro, R. Simion, Some q-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths, J. Stat. Plann. and Infer. 34 (1993) 35–55.

[2] E. Deutsch, personal communication, 1999

[3] L.W. Shapiro, Amer. Math. Monthly, 89 (1982) p. 339, and 90 (1983) p. 714-715.

[4] R.P. Stanley, Enumerative Combinatorics, Vol II, Cambridge University, Cambridge, UK, Press, 1999.

[5] R.A. Sulanke, A symmetric variation of distribution of Kreweras and Poupard, J. Stat. Plann. and Infer., 34 (1993) 291–303

[6] R.A. Sulanke, The Narayana distribution, to appear in J. Stat. Plann. and Infer.