Counting nonintersecting lattice paths with turns

C. Krattenthaler^{†}

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria. e-mail: KRATT@Pap.Univie.Ac.At

Abstract. We derive enumeration formulas for families of nonintersecting lattice paths with given starting and end points and a given total number of North-East turns. These formulas are important for the computation of Hilbert series for determinantal and pfaffian rings.

1. Introduction. Recent work of Abhyankar and Kulkarni [1, 2] and of Conca, Herzog and Trung [4, 5, 8] showed that the computation of Hilbert series for determinantal and pfaffian rings boils down to counting families of n nonintersecting lattice paths with given starting and end points and a given total number of turns in certain regions. If one forgets about the number of turns, i.e., if one is interested in the plain enumeration of nonintersecting lattice paths with given starting and end points, then the solution is a certain determinant. This is classical now (cf. [6; 7, Cor. 2; 17, Theorem 1.2]). However, the method that is used for the plain enumeration (the “Gessel–Viennot involution”, which actually can be traced back to Lindström [15] and Karlin and McGregor [9]), is not appropriate to keep track of turns. Still, the answers to “turn enumeration” are determinants. But new methods are needed now.

In this note we develop the basic theory of turn enumeration of nonintersecting lattice paths. Theorem 1 solves the turn enumeration of (unrestricted) nonintersecting lattice paths with given starting and end points, Theorem 4 provides a generalization. Theorem 2 solves the turn enumeration of nonintersecting lattice paths that stay below a diagonal line with given starting and end points, Theorem 5 provides a generalization. Finally, Theorem 3 solves a problem that is equivalent to the turn enumeration of nonintersecting lattice paths that stay above a diagonal line with given starting and end points, Theorem 6 provides a generalization. We also briefly indicate how these theorems are related to the computation of Hilbert series for determinantal and pfaffian rings.

1980 Mathematics Subject Classification (1991 Revision). Primary 05A15; Secondary 05A19, 13C40..

Key words and phrases. Nonintersecting lattice paths, turns, non-crossing two-rowed arrays, determinantal rings, pfaffian rings, Hilbert series.

†Supported in part by EC’s Human Capital and Mobility Program, grant CHRX-CT93-0400 and the Austrian Science Foundation FWF, grant P10191-PHY

What concerns the proofs of these results, it turns out that lattice paths are not the right objects to play with. The objects that are natural in the context of turn enumeration are two-rowed arrays. To prove the determinant formulas we construct operations on two-rowed arrays (the operations (24)/(25) → (28)/(29), (37a)/(37b) → (38a)/(38b), (32) → (33), (39) → (40)) that are in some sense analogous to the Gessel–Viennot involution for paths and the reflection principle for paths. These operations are inspired by operations from [10, 13].

A full account of this theory will be the subject of forthcoming papers [11, 12]. In particular, these papers contain more enumeration results concerning nonintersecting lattice paths with a given total number of turns. Besides, the impact of our results to the theory of determinantal and pfaffain rings is explained in detail there. Also, more general enumeration results for non-crossing two-rowed arrays are presented there that lead to summation theorems for Schur functions. An interesting feature is that it is the Robinson–Schensted–Knuth correspondence and its properties that constitute the link between “turn enumeration” of nonintersecting lattice paths and the above mentioned applications.

The paper is organized as follows. In the next section we explain our terminology and state our results (Theorems 1–6). Then, in section 3, we provide the proofs of Theorems 4–6. Theorems 1–3 follow as special cases.

2. The results. We consider lattice paths in the plane consisting of unit horizontal and vertical steps in the positive direction. In the sequel we shall call them shortly paths. Let P be a path from A = (A_{1}, A_{2}) to E = (E_{1}, E_{2}). Later we frequently abbreviate the fact that a path P goes from A to E by P : A → E.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • •^{P_{0}} Figure 1

A point in a path P which is the end point of a vertical step and at the same time the starting point of a horizontal step will be called a North-East turn (NE-turn for short) of the path P. The NE-turns of the path in Figure 1 are (1, 1), (2, 3), and (5, 4). Similarly, a point in a path P which is the end point of a horizontal step and at the same time the starting point of a vertical step will be called an East-North turn (EN-turn for short) of the path P. The EN-turns of the path in Figure 1 are (2, 1), (5, 3), and (6, 4).

The aim of this note is to prove the following three theorems about the enumeration of nonintersecting lattice paths with a given total number of turns. Here, as usual, paths are called nonintersecting if no two of them have a point in common.

Theorem 1. Let A_{i} = (A_{1}^{(i)}, A_{2}^{(i)}) and E_{i} = (E_{1}^{(i)}, E_{2}^{(i)}) be lattice points satisfying

A_{1}^{(1)} ≤ A_{1}^{(2)} ≤ ⋯ ≤ A_{1}^{(r)}, A_{2}^{(1)} > A_{2}^{(2)} > ⋯ > A_{2}^{(r)},

and

E_{1}^{(1)} < E_{1}^{(2)} < ⋯ < E_{1}^{(r)}, E_{2}^{(1)} ≥ E_{2}^{(2)} ≥ ⋯ ≥ E_{2}^{(r)}.

The number of all families P = (P_{1}, …, P_{r}) of nonintersecting lattice paths P_{i} : A_{i} → E_{i}, such that the paths of P altogether contain exactly K NE-turns, is

∑_{k_{1}+···+k_{r}=K} det_{1≤s,t≤r} (\binom{E_{1}^{(t)} − A_{1}^{(s)} + s − t}{k_{s} + s − t}\binom{E_{2}^{(t)} − A_{2}^{(s)} − s + t}{k_{s}}).  □ (1)

Remark. A special case of Theorem 1 is of relevance in the computation of Hilbert series for determinantal rings. This was shown by several authors [5, 14, 16]. In fact, Kulkarni [14, Main Theorem 5] derived this special case (r = p, K = E, A_{i} = (0, a_{p−i+1}), E_{i} = (m(2)−b_{p−i+1}, m(1))) from Abhyankar’s formula [1, (20.14.4), p. 484] for the Hilbert series for certain determinantal rings, while Conca and Herzog [5] used it to give an alternative proof of Abhyankar’s formula, see also [11]. On the other hand, Modak [16] gave an independent (manipulative) proof of this special case. Slight variations of Theorem 1 solve the computation of Hilbert series for rings generated by minors of a symmetric matrix as considered by Conca [4], see [11].

Theorem 2. Let A_{i} = (A_{1}^{(i)}, A_{2}^{(i)}) and E_{i} = (E_{1}^{(i)}, E_{2}^{(i)}) be lattice points satisfying

A_{1}^{(1)} ≤ A_{1}^{(2)} ≤ ⋯ ≤ A_{1}^{(r)}, A_{2}^{(1)} > A_{2}^{(2)} > ⋯ > A_{2}^{(r)},
E_{1}^{(1)} < E_{1}^{(2)} < ⋯ < E_{1}^{(r)}, E_{2}^{(1)} ≥ E_{2}^{(2)} ≥ ⋯ ≥ E_{2}^{(r)},

and A_{1}^{(i)} ≥ A_{2}^{(i)}, E_{1}^{(i)} ≥ E_{2}^{(i)}, i = 1, …, r. The number of all families P = (P_{1}, …, P_{r}) of nonintersecting lattice paths P_{i} : A_{i} → E_{i}, which do not cross the line x = y, and where the paths of P altogether contain exactly K NE-turns, is

∑_{k_{1}+···+k_{r}=K} det_{1≤s,t≤r} (\binom{E_{1}^{(t)} − A_{1}^{(s)} + s − t}{k_{s} + s − t}\binom{E_{2}^{(t)} − A_{2}^{(s)} − s + t}{k_{s}}

− \binom{E_{1}^{(t)} − A_{2}^{(s)} − s − t + 1}{k_{s} − t}\binom{E_{2}^{(t)} − A_{1}^{(s)} + s + t − 1}{k_{s} + s}). □ (2)

Remark. Theorem 2 can be applied for the computation of the Hilbert series for certain ladder determinantal rings (one sided, with a diagonal upper bound) and also for pfaffian rings, see [11]. For arbitrary one-sided ladders see [11, 12].

Theorem 3. Let A_{i} = (A_{1}^{(i)}, A_{2}^{(i)}) and E_{i} = (E_{1}^{(i)}, E_{2}^{(i)}) be lattice points satisfying

A_{1}^{(1)} < A_{1}^{(2)} < ⋯ < A_{1}^{(r)}, A_{2}^{(1)} ≥ A_{2}^{(2)} ≥ ⋯ ≥ A_{2}^{(r)},
E_{1}^{(1)} ≤ E_{1}^{(2)} ≤ ⋯ ≤ E_{1}^{(r)}, E_{2}^{(1)} > E_{2}^{(2)} > ⋯ > E_{2}^{(r)},

and A_{1}^{(i)} ≥ A_{2}^{(i)}, E_{1}^{(i)} ≥ E_{2}^{(i)}, i = 1, …, r. The number of all families P = (P_{1}, …, P_{r}) of nonintersecting lattice paths P_{i} : A_{i} → E_{i}, P_{i} : A_{i} → E_{i}, which do not cross the line x = y, and where the paths of P altogether contain exactly K EN-turns, is

∑_{k_{1}+···+k_{r}=K} det_{1≤s,t≤r} (\binom{E_{1}^{(t)} − A_{1}^{(s)} + s − t}{k_{s} + s − t}\binom{E_{2}^{(t)} − A_{2}^{(s)} − s + t}{k_{s}}

− \binom{E_{1}^{(t)} − A_{2}^{(s)} − s − t + 3}{k_{s} − t + 1}\binom{E_{2}^{(t)} − A_{1}^{(s)} + s + t − 3}{k_{s} + s − 1}). □ (3)

Actually, more general results can be shown (see Theorems 4,5,6 below). However, they are more conveniently formulated after before having modified the problem.

Suppose, P = (P_{1}, …, P_{r}) is a family of nonintersecting lattice paths P_{i} : A_{i} → E_{i}. Now we shift the i-th path P_{i} in the direction (−i + 1, i − 1) thus obtaining the new path P′_{i}, i = 1, …, r. The new family P′ = (P′_{1}, …, P′_{r}) might be intersecting, however it is non-crossing (see Figure 2).

• _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • • • • • • P_{1}P_{2}  P^{3}  ⟶  _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•  •} •  •^{•  •} P′_{1} P′_{2}  P′_{3}
nonintersecting lattice paths  non-crossing lattice paths

Figure 2

Before we make precise what the exact meaning of non-crossing in this context is (see (10) below), we introduce some notation.

Obviously, given the starting and the final point of a path, the North-East turns uniquely determine the path. Suppose that P is a path from A = (A_{1}, A_{2}) to E = (E_{1}, E_{2}) and let the North-East turns of P be (a_{1}, b_{1}), (a_{2}, b_{2}), …, (a_{k}, b_{k}), where we assume that the (a_{i}, b_{i}) are ordered from left to right, which is equivalent with A_{1} ≤ a_{1} < a_{2} < ⋯ < a_{k} ≤ E_{1} − 1, and A_{2} + 1 ≤ b_{1} < b_{2} < ⋯ < b_{k} ≤ E_{2}. Then P can be represented by the two-rowed array

\begin{matrix}a_{1} & a_{2} & … & a_{k} \\ b_{1} & b_{2} & … & b_{k} \end{matrix} ,  (4)

or, if we wish to make the bounds which are caused by the starting and the final point transparent,

\begin{aligned}A_{1} ≤ & a_{1} & a_{2} & … & a_{k} & ≤ E_{1} − 1 \\ A_{2} + 1 ≤ & b_{1} & b_{2} & … & b_{k} & ≤ E_{2} \end{aligned} .  (5)

For a given starting point and a given final point, by definition the empty array is the representation for the only path that has no North-East turn. For the path in Figure 1 we obtain the array representation

{1 2 5 \atop 1 3 4} ,

or with bounds included,

\begin{aligned}1 ≤ & 1 & 2 & 5 & ≤ 5 \\ 0 ≤ & 1 & 3 & 4 & ≤ 6 \end{aligned} .

Later, also two-rowed arrays with rows of unequal length will be considered. But these arrays also will have the property that the rows are strictly increasing. So by convention, whenever we speak of two-rowed arrays we mean two-rowed arrays with strictly increasing rows. We shall frequently use the short notation (a | b) for tworowed arrays, where a denotes the sequence (a_{i}) of elements of the first row, and b denotes the sequence (b_{i}) of elements of the second row.

Let P_{1}, P_{2} be two paths, P_{1} : A → E, P_{2} : B → F, where A = (A_{1}, A_{2}), B = (B_{1}, B_{2}), E = (E_{1}, E_{2}), F = (F_{1}, F_{2}) with

A_{1} ≤ B_{1}, A_{2} > B_{2}, E_{1} < F_{1}, E_{2} ≥ F_{2}.

Roughly speaking, these inequalities mean that A is located in the North-West of B (strictly in direction North and weakly in direction West), and E is located in the North-West of F (weakly in direction North and strictly in direction West). Let the array representations of P_{1} and P_{2} be

P_{1} : \begin{aligned}A_{1} ≤ & a_{1} & … & a_{k} & ≤ E_{1} − 1 \\ A_{2} + 1 ≤ & b_{1} & … & b_{k} & ≤ E_{2} \end{aligned}  (6)

and

P_{2} : \begin{aligned}B_{1} ≤ & c_{1} & … & c_{l} & ≤ F_{1} − 1 \\ B_{2} + 1 ≤ & d_{1} & … & d_{l} & ≤ F_{2} \end{aligned} ,  (7)

respectively.

Suppose that P_{1} and P_{2} intersect, i.e. have a point in common. Let S be a meeting point of P_{1} and P_{2}. By definition set a_{k+1} := E_{1} and b_{0} := A_{2}. (Note that the thereby augmented sequences a and b remain strictly increasing.)

• • •^{S}^{(c_{J}, d_{J})} _{(a_{I}, b_{I−1})}  ^{P_{1}}  ^{P_{2}} Figure 3

Considering the East-North turn (a_{I}, b_{I−1}) in P_{1} immediately preceding S (and being allowed to be equal to S) and the North-East turn (c_{J}, d_{J}) in P_{2} immediately preceding S (and being allowed to be equal to S), we get the inequalities (cf. Figure 3)

c_{J} ≤ a_{I},  (8a)
b_{I−1} ≤ d_{J},  (8b)

where

1 ≤ I ≤ k + 1, 1 ≤ J ≤ l.  (8c)

Of course, k, l, a_{I}, b_{I}, c_{J}, d_{J}, etc., refer to the array representations of P_{1} and P_{2}. It now becomes apparent that the above assignments for a_{k+1} and b_{0} are needed for the inequalities (8a,b) to make sense for I = 1 or I = k + 1. Note that S = (a_{I}, d_{J}). Vice versa, if (8a,b,c) is satisfied then there must be a meeting point between P_{1} and P_{2} (because of the particular location of the starting and end points A, B, E, F).

Summarizing, the existence of I, J satisfying (8a,b,c) characterize the array representations of intersecting pairs of paths.

Now, if P_{2} is shifted in direction (−1, 1), we obtain the path P′_{2} with array representation

\begin{aligned}B′_{1} ≤ & c′_{1} & … & c′_{l} & ≤ F′_{1} − 1 \\ B′_{2} + 1 ≤ & d′_{1} & … & d′_{l} & ≤ F′_{2} \end{aligned} ,  (9)

where c′_{i} = c_{i} − 1, d′_{i} = d_{i} + 1, B′_{1} = B_{1} − 1, B′_{2} = B_{2} + 1, F′_{1} = F_{1} − 1, F′_{2} = F_{2} + 1. The conditions (8a,b,c) become

c′_{J} < a_{I},  (10a)
b_{I−1} < d′_{J},  (10b)

where

1 ≤ I ≤ k + 1, 1 ≤ J ≤ l.  (10c)

We take (10a,b,c) as definition of two paths P_{1} and P_{2} with array representations (6) and (9), respectively, being non-crossing. We call the point (a_{I}, d′_{J}) crossing point of P_{1} and P_{2}.

Let x = (x_{1}, x_{2}, …) and y = (y_{1}, y_{2}, …) be sequences of indeterminates. Given a path P_{1} with array representation (6) we define a weight for P_{1} by

w_{x,y}(P_{1}) = ∏_{i=1}^{k} x_{a_{i}}y_{b_{i}}.  (11)

This weight is extended to families P = (P_{1}, …, P_{r}) of lattice paths by

w_{x,y}(P) = ∏_{j=1}^{r} w_{x,y}(P_{j}).  (12)

Now we are prepared to formulate the promised generalizations of Theorems 1,2,3.

A_{1}^{(1)} + 1 ≤ A_{1}^{(2)} + 2 ≤ ⋯ ≤ A_{1}^{(r)} + r, A_{2}^{(1)} ≥ A_{2}^{(2)} ≥ ⋯ ≥ A_{2}^{(r)},  (13)

and

E_{1}^{(1)} ≤ E_{1}^{(2)} ≤ ⋯ ≤ E_{1}^{(r)}, E_{2}^{(1)} − 1 ≥ E_{2}^{(2)} − 2 ≥ ⋯ ≥ E_{2}^{(r)} − r.  (14)

The generating function ∑_{P} w_{x,y}(P) where the sum is over all families P = (P_{1}, …, P_{r}) of non-crossing lattice paths P_{i} : A_{i} → E_{i}, is

det_{1≤s,t≤r}(f_{s−t}(x, A_{1}^{(s)}, E_{1}^{(t)} − 1, y, A_{2}^{(s)} + 1, E_{2}^{(t)})),  (15)

where f_{m}(x, a, b, y, c, d) = ∑_{k} e_{k+m}(x_{a}, …, x_{b})e_{k}(y_{c}, …, y_{d}) with e_{n}(z_{1}, …, z_{h}) denoting the elementary symmetric function in the variables z_{1}, …, z_{h}.

Theorem 5. Let A_{i} = (A_{1}^{(i)}, A_{2}^{(i)}) and E_{i} = (E_{1}^{(i)}, E_{2}^{(i)}) be lattice points satisfying (13) and (14) and

A_{1}^{(1)} ≥ A_{2}^{(1)} and E_{1}^{(1)} ≥ E_{2}^{(1)}.  (16)

The generating function ∑_{P} w_{x,x}(P) where the sum is over all families P = (P_{1}, …, P_{r}) of non-crossing lattice paths P_{i} : A_{i} → E_{i}, such that P_{1} does not cross the line x = y, is

det_{1≤s,t≤r}(f_{s−t}(x, A_{1}^{(s)}, E_{1}^{(t)} − 1, x, A_{2}^{(s)} + 1, E_{2}^{(t)})

− f_{−s−t}(x, A_{2}^{(s)} + 1, E_{1}^{(t)} − 1, x, A_{1}^{(s)}, E_{2}^{(t)})). (17)

Theorem 6. Let A_{i} = (A_{1}^{(i)}, A_{2}^{(i)}) and E_{i} = (E_{1}^{(i)}, E_{2}^{(i)}) be lattice points satisfying

A_{1}^{(1)} ≤ A_{1}^{(2)} ≤ ⋯ ≤ A_{1}^{(r)}, A_{2}^{(1)} − 1 ≥ A_{2}^{(2)} − 2 ≥ ⋯ ≥ A_{2}^{(r)} − r,  (18)
E_{1}^{(1)} + 1 ≤ E_{1}^{(2)} + 2 ≤ ⋯ ≤ E_{1}^{(r)} + r, E_{2}^{(1)} ≥ E_{2}^{(2)} ≥ ⋯ ≥ E_{2}^{(r)},  (19)

and (16). The generating function ∑_{P} w_{x,x}(P) where the sum is over all families P = (P_{1}, …, P_{r}) of non-crossing lattice paths P_{i} : A_{i} → E_{i}, such that P_{1} does not cross the line x = y, is

det_{1≤s,t≤r}(f_{s−t}(x, A_{1}^{(s)} + 1, E_{1}^{(t)}, x, A_{2}^{(s)}, E_{2}^{(t)} − 1)

− f_{−s−t+2}(x, A_{2}^{(s)}, E_{1}^{(t)}, x, A_{1}^{(s)} + 1, E_{2}^{(t)} − 1)). (20)

Clearly, Theorems 1,2,3 result from Theorems 4,5,6, respectively, by “unshifting”, i.e. by replacing A_{1}^{(i)} by A_{1}^{(i)} − i + 1, A_{2}^{(i)} by A_{2}^{(i)} + i − 1, etc., setting x_{i} = y_{i} = z and extracting the coefficient of z^{2K} in (15), (17), and (20), respectively.

3. The proofs.

Proof of Theorem 4. In the proof we are also considering skew two-rowed arrays. Let j > 0. We say that the two-rowed array P is of the type j if P has the form

\begin{aligned}a_{−j+1} & a_{−j+2} & … & a_{−1} & a_{0} & a_{1} & … & a_{k} \\ & & & & & b_{1} & … & b_{k} \end{aligned}

for some k ≥ 0. We say that P is of the type −j if P has the form

\begin{aligned}& & & & & a_{1} & … & a_{k} \\ b_{−j+1} & b_{−j+2} & … & b_{−1} & b_{0} & b_{1} & … & b_{k} \end{aligned}

for some k ≥ 0. Note that the placement of indices is chosen such that non-positive indices can occur only in one row of P, while the positive indices occur in both rows of P. We extend the weight function w_{x,y} to skew arrays in the obvious way,

w_{x,y}(P) = ∏_{i} x_{a_{i}} ∏_{j} y_{b_{j}}.

First we give the combinatorial interpretation of the determinant (15) in terms of two-rowed arrays. It is easy to see that (15) is the generating function

∑_{(P,σ)} sgn σ w_{x,y}(P),  (21)

where the sum is over all pairs (P, σ) of permutations σ in 𝔖_{r}, the symmetric group of order r, and families P = (P_{1}, …, P_{r}) of two-rowed arrays, P_{i} being of type σ(i)−i and the bounds for the entries of P_{i} being as follows,

\begin{aligned}A_{1}^{(σ(i))} ≤ & … a_{k_{i}}^{(i)} & ≤ E_{1}^{(i)} − 1 \\ A_{2}^{(σ(i))} + 1 ≤ & … b_{k_{i}}^{(i)} & ≤ E_{2}^{(i)} \end{aligned} ,  (22)

i = 1, …, r.

The outline of the proof is as follows. Next we extend the notion of being noncrossing to two-rowed arrays. We then show that in the sum (21) all contributions corresponding to pairs (P, σ), where P is a crossing family (to be explained below) of two-rowed arrays, cancel. This is done by constructing a weight-preserving, signreversing involution on those pairs. Finally we show that in a pair (P, σ) with σ ≠ id the family P must be crossing. This establishes that only pairs (P, id) where P is a non-crossing family of two-rowed arrays contribute to the sum (21). But these pairs exactly correspond to the families of non-crossing paths under consideration, hence Theorem 4 would be proved.

Let M_{1} and M_{2} be two-rowed arrays, given by

M_{1} : \begin{aligned}A_{1} ≤ & … a_{k} & ≤ E_{1} − 1 \\ A_{2} + 1 ≤ & … b_{k} & ≤ E_{2} \end{aligned}

and

M_{2} : \begin{aligned}B_{1} ≤ & … c_{l} & ≤ F_{1} − 1 \\ B_{2} + 1 ≤ & … d_{l} & ≤ F_{2} \end{aligned} ,

respectively. By definition we set a_{k+1} := E_{1}, we set b_{0} := A_{2} in case that the sequence … b_{0} is empty, and we set c_{0} := B_{1} − 1 in case that the sequence … c_{0} is empty. We say that (a_{I}, d_{J}) is a crossing point of M_{1} and M_{2} if

c_{J} < a_{I}  (23a)
b_{I−1} < d_{J}  (23b)

and

1 ≤ I ≤ k + 1, 0 ≤ J ≤ l.  (23c)

These inequalities should be understood to hold only if all variables are defined. In particular, if the sequence … d_{0} is empty the inequality (23b) does not make sense for J = 0. However, if the sequence … c_{0} is empty the inequality (23a) makes sense because of the conventional assignment for c_{0} above.

Let (P, σ) be a pair under consideration for the sum (21). Besides, we assume that P contains two two-rowed arrays P_{i} and P_{i+1} with consecutive indices that have a crossing point. In the sequel two-rowed arrays with consecutive indices will be called neighbouring two-rowed arrays. A pair (P, σ) where P contains neighbouring tworowed arrays with a crossing point will be called crossing. Otherwise it will be called non-crossing. We are going to construct a weight-preserving (with respect to the weight function w_{x,y}) and sign-reversing (with respect to sgn σ) involution on crossing pairs (P, σ). Consider all crossing points of neighbouring arrays. Among these points choose those with maximal x-coordinate, and among all those choose the crossing point with maximal y-coordinate. Denote this crossing point by S. Let i be minimal such that S is a crossing point of P_{i} and P_{i+1}. Let P_{i} = (a | b) = (… a_{k_{i}} | … b_{k_{i}}) and P_{i+1} = (c | d) = (… c_{k_{i+1}} | … d_{k_{i+1}}). Recall that P_{i} is of type σ(i) − i and P_{i+1} is of type σ(i + 1) − i − 1 and that the bounds of the entries in P_{i} and P_{i+1} are determined by (22). By (23), S being a crossing point of P_{i} and P_{i+1} means that there exist I and J such that P_{i} looks like

\begin{aligned}A_{1}^{(σ(i))} ≤ & … & a_{I−1} & a_{I} & … & a_{k_{i}} & ≤ E_{1}^{(i)} − 1 \\ A_{2}^{(σ(i))} + 1 ≤ & … & b_{I−1} & b_{I} & … & b_{k_{i}} & ≤ E_{2}^{(i)} \end{aligned} ,  (24)

P_{i+1} looks like

\begin{aligned}A_{1}^{(σ(i+1))} ≤ & . . . . . . . . & c_{J} & c_{J+1} & … & c_{k_{i+1}} & ≤ E_{1}^{(i+1)} − 1 \\ A_{2}^{(σ(i+1))} + 1 ≤ & … & d_{J−1} & d_{J} & . . . . . . . . & d_{k_{i+1}} & ≤ E_{2}^{(i+1)} \end{aligned} ,  (25)

S = (a_{I}, d_{J}),

c_{J} < a_{I}  (26a)
b_{I−1} < d_{J}  (26b)

and

1 ≤ I ≤ k_{i} + 1, 0 ≤ J ≤ k_{i+1}.  (26c)

Because of the construction of S the indices I and J are maximal with respect to (26a,b,c).

We map (P, σ) to the pair (P̄, σ ∘ (i, i + 1)) ((i, i + 1) denotes the transposition exchanging i and i+1), where P̄ = (P_{1}, …, P_{i−1}, P̄_{i}, P̄_{i+1}, P_{i+2}, …, P_{r}) with P̄_{i} being given by

\begin{matrix}… & c_{J} & a_{I} & … & a_{k_{i}} \\ … & d_{J−1} & b_{I} & … & b_{k_{i}} \end{matrix} ,  (27a)

P̄_{i+1} being given by

\begin{matrix}. . . . . . . & a_{I−1} & c_{J+1} & … & c_{k_{i+1}} \\ … & b_{I−1} & d_{J} & . . . . . . . . & d_{k_{i+1}} \end{matrix} .  (27b)

First of all, this operation is well-defined, i.e., all the rows in (27a) and (27b) are strictly increasing. To see this we have to check c_{J} < a_{I}, d_{J−1} < b_{I}, a_{I−1} < c_{J+1}, and b_{I−1} < d_{J}. This is obvious for the first and last inequality, because of (26a) and (26b). As for the second inequality, let us suppose d_{J−1} ≥ b_{I}. Then, by (26a), we have c_{J} < a_{I} < a_{I+1} and b_{I} ≤ d_{J−1} < d_{J}. This means that (a_{I+1}, d_{J}) is a crossing point of P_{i} and P_{i+1}, with an x-coordinate larger than that of S = (a_{I}, d_{J}), contradicting the “maximality” of S. Similarly, if we assume a_{I−1} ≥ c_{J+1}, we have c_{J+1} ≤ a_{I−1} < a_{I} and, by (26b), b_{I−1} < d_{J} < d_{J+1}. This means that (a_{I}, d_{J+1}) is a crossing point of P_{i} and P_{i+1}, with a y-coordinate larger than that of S = (a_{I}, d_{J}), again contradicting the “maximality” of S.

We claim that (P̄, σ∘(i, i+1)) is again a pair under consideration for the generating function (21). That is, we claim that P̄_{i} is of type (σ ∘ (i, i + 1))(i) − i = σ(i + 1) − i, that P̄_{i+1} is of type (σ ∘ (i, i + 1))(i + 1) − i − 1 = σ(i) − i − 1, and that the bounds for the entries of P̄_{i} are given by

\begin{aligned}A_{1}^{(σ(i+1))} ≤ & … & c_{J} & a_{I} & … & a_{k_{i}} & ≤ E_{1}^{(i)} − 1 \\ A_{2}^{(σ(i+1))} + 1 ≤ & … & d_{J−1} & b_{I} & … & b_{k_{i}} & ≤ E_{2}^{(i)} \end{aligned} ,  (28)

and that those for P̄_{i+1} are given by

\begin{aligned}A_{1}^{(σ(i))} ≤ & . . . . . . . . & a_{I−1} & c_{J+1} & … & c_{k_{i+1}} & ≤ E_{1}^{(i+1)} − 1 \\ A_{2}^{(σ(i))} + 1 ≤ & … & b_{I−1} & d_{J} & . . . . . . . . & d_{k_{i+1}} & ≤ E_{2}^{(i+1)} \end{aligned} .  (29)

The claims concerning the types of P̄_{i} and P̄_{i+1} are trivial. Therefore let us consider the bounds. We distinguish between several cases.

(a) If 2 ≤ I ≤ k_{i} and 2 ≤ J ≤ k_{i+1} − 1 there is no problem, since then the sequences … a_{I−1}, a_{I} … a_{k_{i}}, … b_{I−1}, b_{I} … b_{k_{i}}, … c_{J}, c_{J+1} … c_{k_{i+1}}, … d_{J−1}, d_{J} … d_{k_{i+1}} are all nonempty and therefore the constraints in (28) and (29) obviously hold.

(b) If I = 1 and the sequence … a_{0} is empty we have to prove c_{J+1} ≥ A_{1}^{(σ(i))}. Suppose a_{1} > c_{J+1}. The inequality (26b) implies b_{0} < d_{J} < d_{J+1} therefore the point (a_{1}, d_{J+1}) would also be a crossing point of P_{i} and P_{i+1} which violates the maximality of J with respect to (26a,b,c). Hence, by (24) we have c_{J+1} ≥ a_{1} ≥ A_{1}^{(σ(i))}.

(c) If I = 1 and the sequence … b_{0} is empty we have to prove d_{J} ≥ A_{2}^{(σ(i))} + 1. In this case the assignment b_{0} := A_{2}^{(σ(i))} applies. Because of (26b) we have A_{2}^{(σ(i))} = b_{0} < d_{J}.

(d) If J = 0 and the sequence … c_{0} is empty we have to prove a_{I} ≥ A_{1}^{(σ(i+1))}. In this case the assignment c_{0} := A_{1}^{(σ(i+1))} − 1 applies. Because of (26a) we have A_{1}^{(σ(i+1))} − 1 = c_{0} < a_{I}.

(e) If J = 1 and the sequence … d_{0} is nonempty nothing has to be proved.

(f) If J = 1 and the sequence … d_{0} is empty we have to prove b_{I} ≥ A_{2}^{(σ(i+1))} + 1. Suppose d_{1} > b_{I}. The inequality (26a) implies c_{J} < a_{I} < a_{I+1} therefore the point (a_{I+1}, d_{J}) would also be a crossing point of P_{i} and P_{i+1} which violates the maximality of I with respect to (26a,b,c). Hence, by (25) we have b_{I} ≥ d_{1} ≥ A_{2}^{(σ(i+1))} + 1.

(g) If I = k_{i} + 1 we have to prove c_{J} ≤ E_{1}^{(i)} − 1 and d_{J−1} ≤ E_{2}^{(i)}. In this case the assignment a_{k_{i}+1} := E_{1}^{(i)} applies. By (26a) we have c_{J} < a_{k_{i}+1} = E_{1}^{(i)}. By (25) and (14), we have d_{J−1} < d_{J} ≤ E_{2}^{(i+1)} ≤ E_{2}^{(i)} + 1.

(h) If J = k_{i+1} we have to prove a_{I−1} ≤ E_{1}^{(i+1)} − 1. By (24) and (14) we have a_{I−1} ≤ E_{1}^{(i)} − 1 ≤ E_{1}^{(i+1)} − 1.

Obviously the map (27) is weight-preserving with respect to w_{x,y} and reverses the signs of the associated permutations.

Next we claim that the map (27) is an involution. To establish this claim it suffices to show that S is also a crossing point of P̄_{i} and P̄_{i+1}, and also maximal in the sense explained above. Once this is shown it easily seen that an application of our mapping (27) to (P̄, σ∘(i, i+1)) gives (P, σ) again. Suppose that P̄_{i} = (ā | b̄) = (… āk̄_{i} | … b̄k̄_{i}) and P̄_{i+1} = (c̄ | d̄) = (… c̄k̄_{i+1} | … d̄k̄_{i+1}). Let Ī and J̄ be chosen such that āĪ = a_{I} and d̄J̄ = d_{J} (compare with (27)). Then we have b̄_{Ī−1} = d_{J−1} and c̄J̄ = a_{I−1}. Because of a_{I−1} < a_{I} and d_{J−1} < d_{J} we conclude c̄J̄ < āĪ and b̄_{Ī−1} < d̄J̄. By (23) this is equivalent to saying that (āĪ, d̄J̄) = (a_{I}, d_{J}) = S is a crossing point of P̄_{i} and P̄_{i+1}. (These arguments also hold in the “degenerate” cases I = 1, J = 0, 1, etc.) That S is also maximal for P̄ follows from the fact that when applying the map (27) to P_{i} and P_{i+1} nothing was changed to the right of a_{I}, b_{I}, d_{J}, and c_{J+1}.

Finally we have to show that, given a pair (P, σ), P = (P_{1}, …, P_{r}), σ ≠ id, there exist neighbouring two-rowed arrays P_{i} and P_{i+1} having a crossing point. If σ ≠ id then there must exist an i with σ(i + 1) < i + 1. Without loss of generality we may assume that i is minimal with this property. Then we have σ(i) ≥ i. Besides, from σ(i) ≥ i ≥ σ(i + 1) it follows that σ(i) > σ(i + 1). Let P_{i} = (a | b) = (… a_{k_{i}} | … b_{k_{i}}) and P_{i+1} = (c | d) = (… c_{k_{i+1}} | … d_{k_{i+1}}). Because of σ(i) − i ≥ 0 the sequence … b_{0} is empty, hence the assignment b_{0} := A_{2}^{(σ(i))} applies. Because of σ(i + 1) − i − 1 < 0 the sequence … c_{0} is empty, hence the assignment c_{0} := A_{1}^{(σ(i+1))} −1 applies. Because of σ(i) > σ(i + 1) and (13) the inequalities c_{0} = A_{1}^{(σ(i+1))} − 1 ≤ A_{1}^{(σ(i))} < a_{1} and b_{0} = A_{2}^{(σ(i))} ≤ A_{2}^{(σ(i+1))} < d_{0} hold. By (23) this means that (a_{1}, d_{0}) is a crossing point of P_{i} and P_{i+1}. □

Remark. The operation (24)/(25) → (28)/(29) that is the backbone of the preceding proof and is an analogue of the Gessel–Viennot involution in the context of two-rowed arrays is inspired by [10, operation (5.3.6)/(5.3.10)].

Proof of Theorem 5. Again we work with families of two-rowed arrays. This time we consider triples (P, σ, η), where σ is a permutation in 𝔖_{r}, η ∈ {−1, 1}^{r}, and P = (P_{1}, …, P_{r}) is a family of two-rowed arrays, with P_{i} being of type η_{i}σ(i) − i and the bounds of P_{i} being given by

\begin{aligned}A_{1}^{(σ(i))} ≤ & … & ≤ E_{1}^{(i)} − 1 \\ A_{2}^{(σ(i))} + 1 ≤ & … & ≤ E_{2}^{(i)} \end{aligned} , for η = 1,  (30a)

respectively

\begin{aligned}A_{2}^{(σ(i))} + 1 ≤ & … & ≤ E_{1}^{(i)} − 1 \\ A_{1}^{(σ(i))} ≤ & … & ≤ E_{2}^{(i)} \end{aligned} , for η = −1.  (30b)

Define sgn η := ∏_{i=1}^{r} η_{i}. It is easy to see that (17) is the generating function

∑_{(P,σ,η)} sgn η sgn σ w_{x,x}(P)  (31)

where the sum is over all triples which were described above.

We adopt the notion of “crossing of neighbouring arrays” from the previous proof. In addition, we have to consider crossings of P_{1} with the line x = y. Let P_{1} = (a | b), or with bounds included

\begin{aligned}L_{1} ≤ & . . . . . . . . & a_{I} & a_{I+1} & … & a_{k_{1}} & ≤ E_{1}^{(1)} − 1 \\ L_{2} ≤ & … & b_{I−1} & b_{I} & . . . . . . . . & b_{k_{1}} & ≤ E_{2}^{(1)} \end{aligned} .  (32)

Recall that L_{1} and L_{2} are A_{1}^{(σ(1))} + 1 and A_{2}^{(σ(1))} or the other way round, depending on whether η_{1} = 1 or η = −1. Let us, by convention, set a_{0} := L_{1} − 1. We say that (b_{I}, b_{I}) is a crossing point of P_{1} and x = y if I ≥ 0 and a_{I} < b_{I}. Again it is understood that this inequality only holds if both a_{I} and b_{I} are defined. In particular, this means that in case I = 0 the inequality only makes sense if the sequence … a_{0} is empty (in which case the assignment a_{0} := L_{1} − 1 applies). We say that a family P = (P_{1}, …, P_{r}) is a crossing family if either their is a crossing of neighbouring arrays or their is a crossing of P_{1} and x = y.

Similarly to the proof of Theorem 4 we shall show that in the sum (31) all contributions corresponding to triples (P, σ, η) where P is a crossing family of two-rowed arrays cancel by constructing a weight-preserving (with respect to w_{x,x}), sign-reversing (with respect to sgn η sgn σ) involution on those triples. Finally we show that in a triple (P, σ, η) with (σ, η) ≠ (id, (1, 1, …, 1)) the family P must be crossing. This establishes that only triples (P, id, (1, 1, …, 1)) where P is a non-crossing family of two-rowed arrays contribute to the sum (31). But these triples exactly correspond to the families of non-crossing paths under consideration, hence Theorem 5 would be proved.

Let (P, σ, η) be a triple where P = (P_{1}, …, P_{r}) is a crossing family of two-rowed arrays. Consider all crossing points of neighbouring arrays and all crossing points of P_{1} and x = y. Among these points choose those with maximal x-coordinate, and among all those choose the crossing point with maximal y-coordinate. Denote this crossing point by S. If S is a crossing point of neighbouring arrays let i be minimal such that S is a crossing point of P_{i} and P_{i+1}. Map (P, σ, η) to (P̄, σ∘(i, i+1), η^{(i,i+1)}), where η^{(i,i+1)} = (η_{1}, …, η_{i+1}, η_{i}, …, η_{r}) and P̄ = (…, P̄_{i}, P̄_{i+1}, …) with P̄_{i} and P̄_{i+1} being constructed by (28) and (29), respectively, as in the proof of Theorem 4. Note that sgn η^{(i,i+1)} sgn (σ ∘(i, i+1)) = − sgn η sgn σ so that the map indeed changes the sign of the corresponding terms in the generating function (31).

If S is no crossing point of neighbouring arrays, then it has to be a crossing point of P_{1} and x = y. In this case we map (P, σ, η) to the triple (P̄, σ, η^{(1)}) where η^{(1)} = (−η_{1}, η_{2}, …, η_{r}) and P̄ = (P̄_{1}, P_{2}, …, P_{r}) with P̄_{1} being constructed as follows. Let P_{1} be given by (32) and let I be the index such that S = (b_{I}, b_{I}). Then P̄_{1} is defined by

\begin{aligned}L_{2} ≤ & . . . . . & b_{I−1} & a_{I+1} & … & a_{k_{1}} & ≤ E_{1}^{(1)} − 1 \\ L_{1} ≤ & … & a_{I} & b_{I} & . . . . . . . . & b_{k_{1}} & ≤ E_{2}^{(1)} \end{aligned} .  (33)

To check that this is well-defined we have to verify b_{I−1} < a_{I+1}. In fact, if we assume b_{I−1} ≥ a_{I+1}, we have a_{I+1} < b_{I+1} (because otherwise a_{I+1} ≥ b_{I+1} > b_{I} > b_{I−1}, which is a contradiction to our assumption). But this means that (b_{I+1}, b_{I+1}) is a crossing point of P_{1} and x = y with larger coordinates than S = (b_{I}, b_{I}), which contradicts the “maximality” of S. Also for being well-defined, we have to check L_{1} ≤ b_{0} in case that I = 0 and … a_{0} is empty. But in this case the assignment a_{0} := L_{1} − 1 applies. And, since I = 0 we have a_{0} < b_{0}. But this is exactly equivalent to L_{1} ≤ b_{0}.

Next we note that the type of P̄_{1} is −η_{1}σ(1) + 1 − 2 = −η_{1}σ(1) − 1 = η_{1}^{(1)}σ(1) − 1. Trivially, sgn η^{(1)} = − sgn η so also this mapping changes the sign of the corresponding terms in the generating function (31). Therefore (P̄, σ, η^{(1)}) is indeed again a triple under consideration for the generating function (31).

That (b_{I}, b_{I}) is also a crossing point of P̄_{1} is obvious. It is also maximal in the sense explained above since the entries to the right of a_{I+1} and b_{I} were not changed. Therefore, applying the map again to the triple (P̄, σ, η^{(1)}) gives (P, σ, η).

Finally we have to show that if (σ, η) ≠ (id, (1, 1, …, 1)) in the triple (P, σ, η) the family P must be a crossing family. Let η ≠ (1, 1, …, 1). Let i be minimal with η_{i} = −1. If i = 1 then either there is an I ≥ 1 with a_{I} < b_{I}, i.e. a crossing of P_{1} and x = y. Or for all I ≥ 1 there holds a_{I} ≥ b_{I}. By (13) and (16) we have b_{0} ≥ L_{2} + σ(1) = A_{1}^{(σ(1))} + σ(1) ≥ A_{1}^{(1)} + 1 > A_{2}^{(1)} ≥ A_{2}^{(σ(1))} = L_{1} − 1 = a_{0}. Hence (b_{0}, b_{0}) is a crossing of P_{1} and x = y. (Note that b_{−1} and b_{0} exist since for η_{1} = −1 the type of P_{1} is −σ(1) − 1 ≤ −2.) Now suppose that i ≥ 2. In addition assume that there is no crossing point of neighbouring arrays. We claim that again there must be a crossing point of P_{1} and x = y. Because of η_{i} = −1, P_{i} is of the type −σ(i) − i. Let P_{i−1} = (a | b) and P_{i} be given by

\begin{aligned}A_{2}^{(σ(i))} + 1 ≤ & & & c_{1} & … & c_{k_{i}} & ≤ E_{1}^{(i)} − 1 \\ A_{1}^{(σ(i))} ≤ & … & d_{0} & d_{1} & … & d_{k_{i}} & ≤ E_{2}^{(i)} \end{aligned} .

By assumption P_{i} and P_{i−1} are non-crossing. Because … c_{0} is empty the assignment c_{0} := A_{2}^{(σ(i))} applies. By (13) there hold the inequalities d_{0} ≥ A_{1}^{(σ(i))} + σ(i) + i − 1 ≥ A_{1}^{(1)} + 1 + i − 1 > A_{2}^{(1)} ≥ A_{2}^{(σ(i))} = c_{0}. Now let j be maximal with a_{j} ≤ c_{0}. Then there holds c_{0} < a_{j+1}. If b_{j} < d_{0} then (a_{j+1}, d_{0}) would be a crossing point of P_{i−1} and P_{i} which contradicts our assumptions. Hence we have a_{j} ≤ c_{0} < d_{0} ≤ b_{j}. The same argument is repeated with P_{i−2} and P_{i−1}, etc., until we arrive at P_{1}. Obviously, this gives us a crossing point of P_{1} and x = y, as was claimed.

If σ ≠ id and η = (1, 1, …, 1), the same arguments as in the proof of Theorem 4 apply to establish that there must be a crossing of neighbouring arrays. □

Remark. The operation (32) → (33) that is an analogue of the reflection principle (see e.g. [3, p. 22]) for two-rowed arrays is inspired by [13, (2.12); 10, (5.2.4)].

Sketch of Proof of Theorem 6. Here we encode paths by their EN-turns. For example the two-rowed array representation of the path in Figure 1 would be

{2 5 6 \atop 1 3 4} ,

or with bounds included,

\begin{aligned}2 ≤ & 2 & 5 & 6 & ≤ 6 \\ −1 ≤ & 1 & 3 & 4 & ≤ 5 \end{aligned} .

For the combinatorial interpretation of the determinant (20) we consider triples (P, σ, η), where σ is a permutation in 𝔖_{r}, η ∈ {−1, 1}^{r}, and P = (P_{1}, …, P_{r}) is a family of two-rowed arrays, with P_{i} being of type η_{i}σ(i) − i + 1 − η_{i} and the bounds of P_{i} being given by

\begin{aligned}A_{1}^{(σ(i))} + 1 ≤ & … & ≤ E_{1}^{(i)} \\ A_{2}^{(σ(i))} ≤ & … & ≤ E_{2}^{(i)} − 1 \end{aligned} , for η = 1,  (34a)

respectively

\begin{aligned}A_{2}^{(σ(i))} ≤ & … & ≤ E_{1}^{(i)} \\ A_{1}^{(σ(i))} + 1 ≤ & … & ≤ E_{2}^{(i)} − 1 \end{aligned} , for η = −1.  (34b)

It is easy to see that (20) is the generating function

∑_{(P,σ,η)} sgn η sgn σ w_{x,x}(P)  (35)

where the sum is over all triples which were described above.

Since now we are considering EN-turns, we have to redefine what we mean by a crossing of two-rowed arrays and a crossing of a two-rowed array and x = y. Let M_{1} and M_{2} be two-rowed arrays, given by

M_{1} : \begin{aligned}A_{1} + 1 ≤ & … a_{k} & ≤ E_{1} \\ A_{2} ≤ & … b_{k} & ≤ E_{2} − 1 \end{aligned}

and

M_{2} : \begin{aligned}B_{1} + 1 ≤ & … c_{l} & ≤ F_{1} \\ B_{2} ≤ & … d_{l} & ≤ F_{2} − 1 \end{aligned} ,

respectively. By definition we set d_{l+1} := F_{2}, we set c_{0} := B_{1} in case that the sequence … c_{0} is empty, and we set b_{0} := A_{2} − 1 in case that the sequence … b_{0} is empty. We say that (a_{I}, d_{J}) is a crossing point of M_{1} and M_{2} if

c_{J−1} < a_{I}  (36a)
b_{I} < d_{J}  (36b)

and

0 ≤ I ≤ k, 1 ≤ J ≤ l + 1.  (36c)

To define crossings of a two-rowed array M with x = y, let M be given by

\begin{aligned}L_{1} ≤ & … & a_{k_{1}} & ≤ U_{1} \\ L_{2} ≤ & … & b_{k_{1}} & ≤ U_{2} \end{aligned} .

By convention we set b_{k_{1}+1} := U_{2} +1. The point (b_{I+1}, b_{I+1}) is called a crossing point of M and x = y if 1 ≤ I ≤ k_{1} + 1 and a_{I} < b_{I+1}. Note that if M_{1}, M_{2}, M correspond to lattice paths (by the EN-turn encoding) P_{1}, P_{2}, P, respectively, the first definition exactly is equivalent to P_{1} and P_{2} having a crossing, while the second is equivalent to P and x = y having a crossing.

The arguments are now completely analogous to those in the proof of Theorem 5. So we shall not give all the details. Again we construct a weight-preserving (with respect to w_{x,x}), sign-reversing (with respect to sgn η sgn σ) involution on triples (P, σ, η) where P is a crossing (in the new sense) family. Also here we have to distinguish between two cases. Either there is a crossing of neighbouring paths, P_{i} and P_{i+1} say. Or else their is a crossing of P_{1} and x = y. In the first case assume that P_{i} is given by

\begin{matrix}… & a_{I−1} & a_{I} & . . . . . . . \\ . . . . . . . . & b_{I} & b_{I+1} & … \end{matrix} ,  (37a)

and P_{i+1} be given by

\begin{matrix}… & c_{J−1} & c_{J} & … \\ … & d_{J−1} & d_{J} & … \end{matrix} .  (37b)

As in the proof of Theorem 5 it is assumed that S = (a_{I}, d_{J}) is a “maximal” crossing point, and in particular a crossing point of P_{i} and P_{i+1}. Then we map (P, σ, η) to (P̄, σ ∘ (i, i + 1), η^{(i,i+1)}) where P = (P_{1}, …, P̄_{i}, P̄_{i+1}, …, P_{r}) with P̄_{i} being given by

\begin{matrix}… & c_{J−1} & a_{I} & . . . . . . . \\ . . . . . . . . & d_{J−1} & b_{I+1} & … \end{matrix} ,  (38a)

and P̄_{i+1} being given by

\begin{matrix}… & a_{I−1} & c_{J} & … \\ … & b_{I} & d_{J} & … \end{matrix} .  (38b)

In the second case let P_{1} be given by

\begin{matrix}… & a_{I} & a_{I+1} & … \\ … & b_{I} & b_{I+1} & … \end{matrix} .  (39)

Here we assume that S = (b_{I+1}, b_{I+1}) is a “maximal” crossing point of P_{1} and x = y. Then we map (P, σ, η) to (P̄, σ, η^{(1)}) where P = (P̄_{1}, P_{2}, …, P_{r}) with P̄_{1} being given by

\begin{matrix}… & b_{I} & a_{I+1} & … \\ … & a_{I} & b_{I+1} & … \end{matrix} .  (40)

It can be shown that this mapping is a weight-preserving, sign-reversing involution and that “non-crossing triples” can only occur for (σ, η) = (id, (1, 1, …, 1)). These exactly correspond to the families of non-crossing paths under consideration. □

Remark. The operation (37a)/(37b) → (38a)/(38b) that is another analogue of the Gessel–Viennot involution in the context of two-rowed arrays is again inspired by [10, operation (5.3.6)/(5.3.10)]. (In fact, it is a simple translation of the operation (24)/(25) → (28)/(29)). The operation (39) → (40) that is another analogue of the reflection principle (see e.g. [3, p. 22]) for two-rowed arrays is inspired by [13, (2.11); 10, (5.2.24)].

References

1. S. S. Abhyankar, Enumerative combinatorics of Young tableaux, Marcel Dekker, New York, Basel, 1988.

2. S. S. Abhyankar and D. M. Kulkarni, On Hilbertian ideals, Linear Alg. Appl. 116 (1989), 53–76.

3. L. Comtet, Advanced Combinatorics, D. Reidel, Dordrecht, Holland, 1974.

4. A. Conca, Symmetric ladders, Nagoya Math. J. 136 (1994), 35–56.

5. A. Conca and J. Herzog, On the Hilbert function of determinantal rings and their canonical module, Proc. Amer. Math. Soc. 122 (1994), 677–681.

6. I. M. Gessel and X. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), 300—321.

7. I. M. Gessel and X. Viennot, Determinants, paths, and plane partitions, preprint.

8. J. Herzog and N. V. Trung, Gröbner bases and multiplicity of determinantal and Pfaffian ideals, Adv. in Math. 96 (1992), 1–37.

9. S. Karlin and J. L. McGregor, Coincidence probabilities, Pacific J. Math. 9 (1959), 1141–1164.

10. C. Krattenthaler, The major counting of nonintersecting lattice paths and generating functions for tableaux, to appear in Mem. Amer. Math. Soc..

11. C. Krattenthaler, Non-crossing two-rowed arrays, in preparation.

12. C. Krattenthaler and M. Prohaska, A remarkable formula for counting nonintersecting lattice paths in a ladder with respect to turns, in preparation.

13. C. Krattenthaler and S. G. Mohanty, On lattice path counting by major and descents, Europ. J. Combin. 14 (1993), 43–51.

14. D. M. Kulkarni, Counting of paths and coefficients of Hilbert polynomial of a determinantal ideal, preprint.

15. B. Lindström, On the vector represenations of induced matroids, Bull. London Math. Soc. 5 (1973), 85–90.

16. M. R. Modak, Combinatorial meaning of the coefficients of a Hilbert polynomial, Proc. Indian Acad. Sci. (Math. Sci.) 102 (1992), 93–123.

17. J. R. Stembridge, Nonintersecting paths, pfaffians and plane partitions, Adv. in Math. 83 (1990), 96—131.

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