COUNTING PAIRS OF NONINTERSECTING LATTICE PATHS WITH RESPECT TO WEIGHTED TURNS

CHRISTIAN KRATTENTHALER AND ROBERT A. SULANKE

Abstract. A formula involving a difference of the products of four q-binomial coefficients is shown to count pairs of nonintersecting lattice paths having a prescribed number of weighted turns. The weights are assigned to account for the location of the turns according to the major and lesser indices. The result, which is a q-analogue of a variant of the formula of Kreweras and Poupard, is proved bijectively; however, when q ≠ 1 the bijection is defined inductively.

1. Introduction

In the coordinate plane consider lattice paths with positively directed vertical and horizontal unit steps. If 0 denotes a vertical step and 1 denotes a horizontal step, a 0-1-sequence will determine a path since it will always be clear where a given path starts. In any path a consecutive 10 is a left-hand turn, and a consecutive 01 is a right-hand turn. Define the major (or greater) index and the lesser index of any path π, where π = π_{1}π_{2} ⋯ π_{n} with π_{k} ∈ {0, 1}, by

maj(π) = ∑_{k} k · χ[π_{k} > π_{k+1}],
less(π) = ∑_{k} k · χ[π_{k} < π_{k+1}],

where χ[A] = 1 if A is true and χ[A] = 0, otherwise.

For nonnegative integers a, b, c, d, i, and j satisfying a ≤ c and d ≤ b, let N (a, b, c, d, i, j) denote the set of pairs of nonintersecting lattice paths, (P, Q), where each left path P runs from (0, 1) to (a, b+1) and has i left-hand turns, and where each right path Q runs from (1, 0) to (c+1, d) and has j right-hand turns. (As usual, two paths are nonintersecting if they have no point in common. Figure 1 shows a pair (P, Q) of nonintersecting lattice paths in N (4, 5, 6, 5, 2, 3). The left-hand turns of P and the right-hand turns of Q are circled.

There, maj(P) = 3 + 6 = 9 and less(Q) = 3 + 5 + 9 = 17.)

We will consider a bijective proof of the following result, first when q = 1 and then in general,

∑_{(P,Q)∈N (a,b,c,d,i,j)} q^{maj(P)+less(Q)} =

q^{i^{2}+j^{2}} \{[ \begin{matrix}a \\ i \end{matrix} ][ \begin{matrix}b \\ i \end{matrix} ][ \begin{matrix}c \\ j \end{matrix} ][ \begin{matrix}d \\ j \end{matrix} ] − [ \begin{matrix}a+1 \\ i+1 \end{matrix} ][ \begin{matrix}b−1 \\ i−1 \end{matrix} ][ \begin{matrix}c−1 \\ j−1 \end{matrix} ][ \begin{matrix}d+1 \\ j+1 \end{matrix} ]\} , (1)

where [ \begin{matrix}a \\ i \end{matrix} ] is the q-binomial coefficient (see [1]).

In 1955, Narayana [8] recorded such a result when the numbers of turns is ignored and q = 1. Formula (1) is a q-analogue of a symmetric form of a distribution in four parameters formulated by Kreweras and Poupard [6, 5] (see also [12]) for counting Catalan paths with a fixed number of valleys, certain long jumps and long landings. Sulanke [10, 11] related their distribution to counting N (a, b, c, d, i, j) as given in formula (12) below.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • •  • • ∘ ∘ ∘ ∘ ∘^{P}  ^{Q} ^{(c + 1, d)}^{(a, b + 1)}

A nonintersecting pair

Figure 1

Here we will be counting a set of pairs of nonintersecting paths as the difference of a set of pairs of unrestricted paths less a set of pairs of intersecting paths. Hence, our proofs of (1) and (12) will rely on encoding the pairs of intersecting paths as quadruples of sequences that we are able to count. This encoding will use insertions, deletions, shifts and a bijection between N (a, b, a, b, i, j) and N (a, b, a, b, j, i). For ordinary counting (i.e. q = 1) we use the “rotational” bijection

R_{a,b,i,j} : N (a, b, a, b, i, j) ↔ N (a, b, a, b, j, i) (2) where each pair of paths in N (a, b, a, b, i, j) is rotated into a pair of paths in N (a, b, a, b, j, i) by an 180 degree rotation centered at ((a + 1)/2, (b + 1)/2). When q ≠ 1, however, this simple rotation does not preserve weight. We have yet to find an explicit weight-preserving bijection; as in Section 5, we can only define the bijection inductively.

2. Narayana’s Result and the “Rotation Method”

Ignoring the number of turns on each path in this section, let A ≡ A(a, b, c, d) be the set of all pairs of lattice paths, (P, Q), where P runs from (0, 1) to (a, b + 1) and Q runs from (1, 0) to (c + 1, d). Let N (a, b, c, d) be the set of pairs of nonintersecting paths in A. To motivate our proof of Formula (1), we introduce the “rotation method” while proving a result due essentially to Narayana[8], which he recorded in an equivalent form for a = c and b = d:

|N (a, b, c, d)| = \binom{a+b}{a}\binom{c+d}{c} − \binom{a+b}{a−1}\binom{c+d}{c+1}. (3)

Proof of ( 3). Let I denote the set of all intersecting pairs in A. We will use

|N | = |A| − |I| = |A| − |J |, (4)

where J is a bijective image of I that we can count. Specifically, J will be the set of all pairs of lattice paths, (P′, Q′), where P′ runs from (1, 0) to (a, b + 1) and Q′ runs from (0, 1) to (c + 1, d).

For each (P, Q) ∈ I, let (α, β) denote the first point of intersection of P and Q.

(1) Let P_{1} be the initial subpath of P running from (0, 1) to (α − 1, β).

(2) Let P_{2} be the final subpath of P running from (α, β) to (a, b + 1).

(3) Let Q_{1} be the initial subpath of Q running from (1, 0) to (α, β − 1).

(4) Let Q_{2} be the final subpath of Q running from (α, β) to (c + 1, d).

(We have yet to mention the steps immediately preceding (α, β).) Let (Q̂_{1}, P̂_{1}) be the image of (P_{1}, Q_{1}) under the 180-degree rotation centered at (α/2, β/2). P̂_{1}0P_{2} runs from (1, 0) to (a, b + 1), and Q̂_{1}1Q_{2} runs from (0, 1) to (c + 1, d). Thus, we have a bijection Γ : I ↔ J where

Γ((P, Q)) = (P̂_{1}0P_{2}, Q̂_{1}1Q_{2}),

and this shows (4). Since there are \binom{a+b}{a}\binom{c+d}{c} ways to choose a (P, Q) in A and there are \binom{a+b}{a−1}\binom{c+d}{c+1} ways to choose a (P′, Q′) in J, result (3) follows.

We remark that this proof is a modification of the well-known “interchanging” method of Gessel and Viennot [3] (see [9, section 1] or [4, section 2.2]) for counting disjoint paths. However, in contrast to their method, here P and Q are required to start within one unit of (0, 0), and the pair (P̂_{1}0P_{2}, Q̂_{1}1Q_{2}) preserves, in essence, the “turn information” of (P, Q).

Figure 2 illustrates the bijection Γ : I ↔ J.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • •  • • ∘ ∘ ∘  ∘ ∘ ∘ ∘^{P_{1}}  ^{P_{2}}^{Q_{1}}  ^{Q_{2}}^{(0, 1)} _{(1, 0)}  ^{(α, β)}  ^{⟷} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • •  • • Q̂_{1}  ^{P_{2}} P̂_{1}  ^{Q_{2}}^{(0, 1)} _{(1, 0)}  ^{(α, β)}_{(P_{1}1P_{2}, Q_{1}0Q_{2}) ∈ I  (P̂_{1}0P_{2}, Q̂_{1}1Q_{2}) ∈ J} Figure 2

3. Notation

In the remainder of the paper, except when noted, a, b, c, d, i, and j are fixed integers satisfying 0 < i ≤ a ≤ c and 0 < j ≤ d ≤ b. The cases for i = 0 or j = 0 are handled separately.

Let A (≡ A(a, b, c, d, i, j)) denote the set of all pairs of paths, (P, Q), where P runs from (0, 1) to (a, b+1) and has i left-hand turns, and where Q runs from (1, 0) to (c+1, d) and has j right-hand turns. For any (P, Q) ∈ A, let the sequence (x_{1}, y_{1}), …, (x_{i}, y_{i}) denote the left-hand turns of P, and let the sequence (u_{1}, v_{1}), …, (u_{j}, v_{j}) denote the right-hand turns of Q. These sequences of turns completely specify (P, Q), and conversely. Henceforth, (P, Q) and (X, Y, U, V) will both denote the same pair of paths in A, where

X = (x_{1}, x_{2}, …, x_{i}), Y = (y_{1}, y_{2}, …, y_{i}), (5)

U = (u_{1}, u_{2}, …, u_{j}), V = (v_{1}, v_{2}, …, v_{j}), (6)

1 ≤ x_{1} < x_{2} < ⋯ < x_{i} ≤ a, 1 ≤ y_{1} < y_{2} < ⋯ < y_{i} ≤ b, (7)

1 ≤ u_{1} < u_{2} < ⋯ < u_{j} ≤ c, 1 ≤ v_{1} < v_{2} < ⋯ < v_{j} ≤ d. (8)

In the example in Figure 1 we have X = (1, 3), Y = (3, 4), U = (2, 3, 5), V = (2, 3, 5). If I denotes the set of pairs of intersecting lattice paths in A, then

(9) I = {(X, Y, U, V) ∈ A : x_{h} ≥ v_{k} and y_{h} ≤ v_{k} for some h and k}.

Let C denote the set of all quadruples, (X′, Y′, U′, V′), of finite sequences of the form (empty sequences are allowed)

X′ = (x′_{1}, x′_{2}, …, x′_{i}, x′_{i+1}), Y′ = (y′_{1}, y′_{2}, …, y′_{i−1}),
U′ = (u′_{1}, u′_{2}, …, u′_{j−1}), V′ = (v′_{1}, v′_{2}, …, v′_{j}, v′_{j+1}),

which satisfy

1 ≤ x′_{1} < x′_{2} < ⋯ < x′_{i+1} ≤ a + 1, 1 ≤ y′_{1} < y′_{2} < ⋯ < y′_{i−1} ≤ b − 1, (10)

1 ≤ u′_{1} < u′_{2} < ⋯ < u′_{j−1} ≤ c − 1, 1 ≤ v′_{1} < v′_{2} < ⋯ < v′_{j+1} ≤ d + 1. (11)

4. An Encoding

Here we give a bijective proof for

|N (a, b, c, d, i, j)| = \binom{a}{i}\binom{b}{i}\binom{c}{j}\binom{d}{j} − \binom{a+1}{i+1}\binom{b−1}{i−1}\binom{c−1}{j−1}\binom{d+1}{j+1}. (12)

Since N (a, b, c, d, i, j) = A − I, and since, by elementary counting, |A| and |C| are, respectively, the first term and second term of formula (12), we now complete the proof of (12) by exhibiting a bijection Γ : I ↔ C.

First, we consider the cases corresponding to i = 0 or j = 0. Formula (12) is clearly valid when i = j = 0. If j = 0, 0 < i ≤ a, and 0 < i ≤ b (and similarly, for i = 0, 0 < j ≤ c, and 0 < j ≤ d), the notation of (5) and (7) is meaningful and |A(a, b, c, d, i, 0)| = \binom{a}{i}\binom{b}{i}. Since N (a, b, c, d, i, 0) = A(a, b, c, d, i, 0), formula (12) follows in this case.

Assume 0 < i and 0 < j. For an arbitrary (X, Y, U, V) ∈ I, define I to be the least h and J to be the least k, such that x_{h} ≥ u_{k} and y_{h} ≤ v_{k}. Put (α, β) = (u_{J}, y_{I}); thus, (α, β) is the first point of intersection of the pair of paths (X, Y, U, V). (See Figure 2 where I = 4, J = 2; there we circled the left-hand turns of P and the right-hand turns of Q). Let ℕ denote the set of natural numbers with ℕ ^{0} being the singleton set containing the empty sequence.

To complete the proof of (12), we will show that the following map, adjusted so that C is its image, yields the desired bijection by exhibiting its inverse. Define Γ : I → ℕ ^{i+1} × ℕ ^{i−1} × ℕ ^{j−1} × ℕ ^{j+1} so that

Γ((X, Y, U, V)) = (X′, Y′, U′, V′)

satisfies

X′ = (x̂_{1}, …, x̂_{I−1}, α, x_{I} +1, …, x_{i}+1),
Y′ = (ŷ_{1}, …, ŷ_{I−1}, y_{I+1}−1, …, y_{i}−1),
U′ = (û_{1}, …, û_{J−1}, u_{J+1}−1, …, u_{j} −1),
V′ = (v̂_{1}, …, v̂_{J−1}, β, v_{J} +1, …, v_{j} +1),

where

x̂_{k} = α − x_{I−k} if 1 ≤ k < I,
ŷ_{k} = β − y_{I−k} if 1 ≤ k < I,
û_{k} = α − u_{J−k} if 1 ≤ k < J,
v̂_{k} = β − v_{J−k} if 1 ≤ k < J.

Notice that these last four formulas correspond precisely to the rotation R_{α−1,β−1,I−1,J−1} referred to in (2).

Lemma 1. Γ maps I into C.

Proof. The inequalities of (10) and (11) can be routinely checked for Γ(X, Y, U, V), particularly in light of the role of R_{α−1,β−1,I−1,J−1} within Γ.

We now propose a candidate for the inverse of Γ : I → C. For an arbitrary (X′, Y′, U′, V′) ∈ C, put y′_{i} = b and u′_{j} = c; and define I′ to be the least h and J′ to be the least k such that x′_{h} ≤ u′_{k} and y′_{h} ≥ v′_{k}. Since x′_{i} ≤ a ≤ c = u′_{j} and y′_{i} = b ≥ d ≥ v′_{j}, such integers I′ and J′ exist. Put (α′, β′) = (x′_{I′}, v′_{J′}).

Define Δ : C → ℕ ^{i} × ℕ ^{i} × ℕ ^{j} × ℕ ^{j} so that Δ((X′, Y′, U′, V′)) = (X, Y, U, V), where

\begin{aligned}X & = & (x̂′_{1}, & …, & x̂′_{I′−1}, & x′_{I′+1}−1, & …, & …, & x′_{i+1}−1), \\ Y & = & (ŷ′_{1}, & …, & ŷ′_{I′−1}, & β′, & y′_{I′} +1, & …, & y′_{i−1}+1), \\ U & = & (û′_{1}, & …, & û′_{J′−1}, & α′, & u′_{J′} +1, & …, & u′_{j−1}+1), \\ V & = & (v̂′_{1}, & …, & v̂′_{J′−1}, & v′_{J′+1}−1, & …, & …, & v′_{j+1}−1), \end{aligned}

with

x̂′_{k} = α′ − x′_{I′−k} if 1 ≤ k < I′,
ŷ′_{k} = β′ − y′_{I′−k} if 1 ≤ k < I′,
û′_{k} = α′ − u′_{J′−k} if 1 ≤ k < J′,
v̂′_{k} = β′ − v′_{J′−k} if 1 ≤ k < J′.

Lemma 2. Δ maps C into I.

Proof. The inequalities of ( 7) and ( 8) can easily be checked to show that Δ(C) ⊆ A. To see that Δ(C) ⊆ I, observe that x_{I′} = x′_{I′+1} − 1 ≥ x′_{I′} = α′ = u_{J′} and y_{I′} = β′ = v′_{J′} ≤ v′_{J′+1} − 1 = v_{J′}; and then recall (9).

Lemma 3. Δ : C → I is the inverse of Γ : I → C .

Proof. First examine Δ ∘ Γ : I → I. For any (X, Y, U, V) ∈ I, let (X′, Y′, U′, V′) = Γ((X, Y, U, V)). Using their previous definitions, we claim that (I, J) = (I′, J′) and (α, β) = (α′, β′). Any (h, k) satisfying 0 < h < I and 0 < k < J must satisfy x_{I−h} < u_{J−k} or y_{I−h} > v_{J−k}. Thus, x′_{h} = α − x_{I−h} > α − u_{J−k} = u′_{k} or y′_{h} = β − y_{I−h} < β − v_{J−k} = v′_{k}. This implies that (I′, J′) must satisfy I ≤ I′ and J ≤ J′. On the other hand, x′_{I} = α = u_{J} ≤ u_{J+1} − 1 = u′_{J} and y′_{I} = y_{I+1} − 1 ≥ y_{I} = β = v′_{J}, which implies I′ ≤ I and J′ ≤ J. α = x′_{I} = x′_{I′} = α′, and β = v′_{J} = v′_{J′} = β′. Now, since (I, J) = (I′, J′) and (α, β) = (α′, β′), a routine computation using the definitions of Γ and Δ shows that Δ(Γ(X, Y, U, V)) = (X, Y, U, V).

Next we examine Γ∘Δ : C → C. Put (X, Y, U, V) = Δ((X′, Y′, U′, V′)), for (X′, Y′, U′, V′) ∈ C. By Lemma 2, (X, Y, U, V) ∈ I. Thus defining I, J, I′, and J′ has before, we claim that (I′, J′) = (I, J) and (α′, β′) = (α, β). Any (h, k) satisfying h < I′ and k < J′ must satisfy x′_{I′−h} > u′_{J′−k} or y′_{I′−h} < v′_{J′−k}; and thus, x_{h} = α′ − x′_{I′−h} < α′ − u′_{J′−k} = u_{k} or y_{h} = β′ − y′_{I′−h} > β′ − v′_{J′−k} = v_{k}. This yields I′ ≤ I and J′ ≤ I. On the other hand, x_{I′} = x′_{I′+1} − 1 ≥ x′_{I′} = α′ = u_{J′} and y_{I′} = β′ = v′_{J′} ≤ v′_{J′+1} − 1 = v_{J′}; this condition implies I ≤ I′ and J ≤ J′. α = u_{J} = u_{J′} = α′, and β = y_{J} = v_{J′} = β′. A routine check of the definitions of Γ and Δ shows that Γ(Δ(X′, Y′, U′, V′)) = (X′, Y′, U′, V′).

5. Counting with respect to weighted turns

For any (P, Q) = (X, Y, U, V) ∈ A(a, b, c, d, i, j), maj(P) sums the number of steps to each left-hand turn on P and less(Q) sums the number of steps to each right-hand turn on Q. Alternatively,

(13)  maj(P) + i = (x_{1} + y_{1}) + ⋯ + (x_{i} + y_{i}),
(14)  less(Q) + j = (u_{1} + v_{1}) + ⋯ + (u_{j} + v_{j}),

where the terms i and j appear since P starts at (0, 1) and Q starts at (1, 0).

For any subset S of integers, define the weight of S to be

w(S) = q^{∥S∥}, where ∥S∥ = ∑_{s_{k}∈S} s_{k}.

For any pair (X, Y) and any quadruple (X, Y, U, V) of integer sequences, put

w(X, Y) = w(X)w(Y), and w(X, Y, U, V) = w(X)w(Y)w(U)w(V).

Define the generating function of a set S, on which this weight is defined, by

G(S) = ∑_{S∈S} w(S).

Equations (13) and (14) show that, for any B ⊆ A,

G(B) = ∑_{(P,Q)∈B} q^{maj(P)+i+less(Q)+j}.

On the other hand, we have Lemma 4.

G(A) = q^{i^{2}+i+j^{2}+j} [ \begin{matrix}a \\ i \end{matrix} ] [ \begin{matrix}b \\ i \end{matrix} ] [ \begin{matrix}c \\ j \end{matrix} ] [ \begin{matrix}d \\ j \end{matrix} ] .

Lemma 5.

G(C) = q^{i^{2}+i+j^{2}+j+2} [ \begin{matrix}a+1 \\ i+1 \end{matrix} ] [ \begin{matrix}b−1 \\ i−1 \end{matrix} ] [ \begin{matrix}c−1 \\ j−1 \end{matrix} ] [ \begin{matrix}d+1 \\ j+1 \end{matrix} ] .

Proof of Lemmas 4 and 5. Let P_{k}(n) denote the collection of k-element subsets of {1, 2, …, n}.

G(C) = ∑_{(X′,V′,U′,V′)∈C} q^{∥X′∥}q^{∥Y′∥}q^{∥U′∥}q^{∥V′∥}
= G(P_{i+1}(a + 1))G(P_{i−1}(b − 1))G(P_{j−1}(c − 1))G(P_{j+1}(d + 1)).

It is not difficult to show (See Andrews [1], Ch. 3) that

G(P_{k}(n)) = q^{\binom{k+1}{2}} [ \begin{matrix}n \\ k \end{matrix} ] ,

whence Lemma 5 follows. Lemma 4 is proved in the same fashion.

Proof of formula ( 1). In this proof we will give a procedure similar to the encoding Γ of section 4. Unfortunately, now we do not know an explicit formula for a weight preserving bijection N (a, b, a, b, i, j) ↔ N (a, b, a, b, j, i); hence, we will establish its definition recursively.

We can establish the case for i = 0 or j = 0 in a manner analogous to that used in the previous section. Our proof of (1) for 0 < i ≤ a and 0 < j ≤ d is by induction on a + d. It is easily checked that (1) holds for a + d = 2.

Our induction hypothesis is that formula (1) is valid for all values of a + d when 0 ≤ a, 0 ≤ d, and a + d < n for some integer n, n > 2. Before proving the case for a + d = n > 2, we will establish a specific weight preserving bijection, for a + b < n,

R_{q,a,b,i,j} : N (a, b, a, b, i, j) ↔ N (a, b, a, b, j, i), (15)

Since, by simple arithmetic,

[ \begin{matrix}a+1 \\ i+1 \end{matrix} ] [ \begin{matrix}b−1 \\ i−1 \end{matrix} ] [ \begin{matrix}a−1 \\ j−1 \end{matrix} ] [ \begin{matrix}b+1 \\ j+1 \end{matrix} ]
= \frac{(1 − q^{a+1})(1 − q^{a})(1 − q^{b+1})(1 − q^{b})}{(1 − q^{i+1})(1 − q^{i})(1 − q^{j+1})(1 − q^{j})} [ \begin{matrix}a−1 \\ i−1 \end{matrix} ] [ \begin{matrix}b−1 \\ i−1 \end{matrix} ] [ \begin{matrix}a−1 \\ j−1 \end{matrix} ] [ \begin{matrix}b−1 \\ j−1 \end{matrix} ]
= [ \begin{matrix}a+1 \\ j+1 \end{matrix} ] [ \begin{matrix}b−1 \\ j−1 \end{matrix} ] [ \begin{matrix}a−1 \\ i−1 \end{matrix} ] [ \begin{matrix}b+1 \\ i+1 \end{matrix} ] ,

the induction hypothesis, with a = c and b = d, implies

G(N (a, b, a, b, i, j)) = G(N (a, b, a, b, j, i)). (16)

Put N (a, b, i, j; m) = {(X, Y, U, V) ∈ N (a, b, a, b, i, j) : w((X, Y, U, V)) = q^{m}}. Upon comparing coefficients of q^{m} in (16), for any m,

|N (a, b, i, j; m)| = |N (a, b, j, i; m)|.

This equicardinality allows us to construct a specific bijection:

R_{q,a,b,i,j,m} : N (a, b, i, j; m) ↔ N (a, b, j, i; m),

which, just to be specific, preserves lexicographic order, where N (a, b, i, j; m) and N (a, b, j, i; m) are ordered lexicographically according to the quadruple notation of (X, Y, U, V). Finally, define R_{q,a,b,i,j} of (15) to be the union of these R_{q,a,b,i,j,m}’s.

Now turn to the case a + d = n > 2. Since

∑_{(P,Q)∈N} q^{maj(P)+i+less(Q)+j} = G(N (a, b, c, d, i, j))
= G(A) − G(I),

and since Lemmas 4 and 5 hold, it suffices to establish a bijection

Γ_{q} : I ↔ C,

such that

q^{2}w((X, Y, V, U)) = w(Γ_{q}((X, Y, U, V))), (17)

where the factor q^{2} corresponds to the same factor in G(C) given in Lemma 5. Using the notation associated with the bijection Γ : I ↔ C of the previous section, we define this new bijection so that Γ_{q}((X, Y, U, V)) = (X′, Y′, U′, V′) where

X′ = (x̄_{1}, …, x̄_{I−1}, α, x_{I} +1, …, x_{i}+1),
Y′ = (ȳ_{1}, …, ȳ_{I−1}, y_{I+1}−1, …, y_{i}−1),
U′ = (ū_{1}, …, ū_{J−1}, u_{J+1}−1, …, u_{j} −1),
V′ = (v̄_{1}, …, v̄_{J−1}, β, v_{J} +1, …, v_{j} +1),

with

((ū_{1}, …, ū_{J−1}), (v̄_{1}, …, v̄_{J−1}), (x̄_{1}, …, x̄_{I−1}), (ȳ_{1}, …, ȳ_{I−1}))

= R_{q,α−1,β−1,I−1,J−1}((x_{1}, …, x_{I−1}), (y_{1}, …, y_{I−1}), (u_{1}, …, u_{J−1}), (v_{1}, …, v_{J−1})).

Here, R_{q,α−1,β−1,I−1,J−1} is a specific weight preserving bijection of (15) guaranteed by the induction hypothesis since (α − 1) + (β − 1) ≤ (a − 1) + (d − 1) < n. Proofs very similar to those of section 4 show that Γ_{q} is indeed bijective. A simple check in the definition of Γ_{q} shows it to satisfy the weight property (17).

Finally, we mention two corollaries of Formula (1). First, if we sum the right side of (1) with respect to i and j, we obtain a q-analogue of Narayana’s result, Equation (3), as studied by Fürlinger and Hofbauer [2].

Secondly, if we put a = c = d = j = n ≤ b in Equation (1), the right paths are completely constrained to form, essentially, a diagonal boundary. The resulting formula counts superdiagonal paths from (0, 1) to (a, b + 1) with i valleys (i.e., left-hand turns). An equivalent q-ballot number was given by MacMahon ([7], p. 368; [2], section 4).

References

1. G.E. Andrews, Theory of Partitions, Addison-Wesley Pub. Co., New York, 1976.

2. J. Fürlinger and J. Hofbauer, q-Catalan numbers, J. of Comb. Th. (A), 40 (1985) 248-264.

3. I. Gessel and G. Viennot, Binomial determinants, paths, and plane partitions, unpublished manuscript.

4. C. Krattenthaler, The major counting of nonintersecting lattice paths and generating functions for tableaux, preprint.

5. G. Kreweras, Joint distributions of three descriptive parameters of bridges, Combinatoire énumérative (Proceedings, Montreal, 1985), Lect. Notes in Math., no. 1234, Springer, New York (1986) 177-191.

6. G. Kreweras and Y. Poupard, Subdivision des nombres des Narayana suivant deux paramètres supplémentaire, Europ. J. Combinatorics, 7 (1986) 141-149.

7. P.A. MacMahon, Memoir on the theory of the partitions of numbers.-Part VI, Phil. Trans., A, 211 (1911) 345-373. Reprinted in Collected Papers: Combinatorics, Vol. I. MIT Press, Cambridge Mass., 1978.

8. T.V. Narayana, Sur les treillis formés par les partitions d’un entier, Comptes Rendus Acad. Sci. Paris, Ser I, 240 (1955), 1188-89.

9. J. Stembridge, Nonintersecting paths, Pfaffians, and plane partitions, Adv. Math. 83, (1990) 96-131 10. R.A. Sulanke, Refinements of the Narayana Numbers, Bull. Inst. Comb. and its App., 7 (1993)

60-66.

11. R.A. Sulanke, A symmetric variation of a distribution of Kreweras and Poupard, J. of Stat. Plan. and Infer., 34 (1993) 291-303

12. D. Zeilberger, Six etudes in generating functions, Intern. J. Computer. Math., 29 (1989) 201-215.

Institut für Mathematik, Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria E-mail address: KRATT@pap.univie.ac.at

Department of Mathematics, Boise State University, Boise, Idaho 83725 USA E-mail address: sulanke@math.idbsu.edu