A determinantal formula for the Hilbert series of one-sided ladder determinantal rings

C. Krattenthaler^{∗} and M. Rubey^{⋆}

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria. e-mail: KRATT@Ap.Univie.Ac.At, a9104910@unet.univie.ac.at

WWW: http://www.mat.univie.ac.at/~kratt

Dedicated to Shreeram Abhyankar

Abstract. We give a formula that expresses the Hilbert series of one-sided ladder determinantal rings, up to a trivial factor, in form of a determinant. This allows the convenient computation of these Hilbert series. The formula follows from a determinantal formula for a generating function for families of nonintersecting lattice paths that stay inside a one-sided ladder-shaped region, in which the paths are counted with respect to turns.

1 Introduction

Work of Abhyankar and Kulkarni [1,2,20,21], Bruns, Conca, Herzog, and Trung [4–6,11] showed that the computation of the Hilbert series of ladder determinantal rings (see Section 2 for precise definitions and background) boils down to counting families of n nonintersecting lattice paths with a given total number of turns in a certain ladder-shaped region. Thus, this raises the question of establishing an explicit formula for the number of these families of nonintersecting lattice paths.

In the case that there is no ladder restriction, Abhyankar [1, (20.14.4)] has found a determinantal formula for the Hilbert series (actually not just one, but a great number of them). As was made explicit in [6,7,21,22], he thereby solved the aforementioned counting problem in the case of no ladder restriction. For direct proofs of the corresponding counting formula see [14,22]. In the case of one-sided ladders, Kulkarni [20] established an explicit solution to the counting problem for n = 1 (i.e., if there is just one path; this corresponds to considering one-sided ladder determinantal rings defined by 2 × 2 minors). For arbitrary n, a determinantal formula for the number of families of n nonintersecting lattice paths in a one-sided ladder, where the starting and end points of the paths are successive, was given by the first author and Prohaska [17] (this corresponds to one-sided ladder determinantal rings defined by (n + 1) × (n + 1) minors), thereby proving a conjecture by Conca

⋆ Research partially supported by the Austrian Science Foundation FWF, grant P12094-MAT.

and Herzog [6, last paragraph]. Finally, Ghorpade [9] has recently proposed a solution to the counting problem with more general starting and end points of the paths, even in the case of two-sided ladders (this corresponds to twosided ladder determinantal rings cogenerated by a given minor). This solution is based on an explicit formula for the counting problem for one path (i.e., n = 1), which is then summed over a large set of indices with complicated dependencies. Thus, this solution cannot be regarded as equally satisfying as the determinantal formula of Abhyankar and the determinantal formula of the first author and Prohaska, which are, however, only formulas in the case of a trivial ladder and in the case of a one-sided ladder, respectively.

The purpose of this paper is to provide a determinantal formula for the case of one-sided ladders where the starting and end points are more general than in [17] (see Corollary 1; this corresponds to one-sided ladder determinantal rings cogenerated by a given minor). This formula must be considered as superior to the aforementioned one by Ghorpade [9] in this case (i.e., the case of one- instead of two-sided ladders). It specializes directly to Abhyankar’s formula [1, (20.14.4), L = 2, k = 2, with F^{(22)}(m, p, a, V) defined on p. 50] in the case of no ladder restriction. On the other hand, if starting and end points are successive, then it does not specialize to the formula in [17]. (As already mentioned in Section 7 of [17], it seems that the formula in [17] cannot be extended in any direction.)

The entries in the determinant in our formula (5), respectively (6), are given by certain generating functions for two-rowed arrays, which are easy to compute as we show in Section 5. (The concept of two-rowed arrays was introduced in [12,18] and developed to full power in [13,14]. Also the proof of the main theorem in [17] depended heavily on two-rowed arrays.)

In the next section we recall the basic setup. In particular, we define ladder determinantal rings and state, in Theorem 1, the connection between the Hilbert series of such rings and the enumeration of nonintersecting lattice paths with respect to turns. Our main result, the determinantal formula for the Hilbert series of one-sided ladder determinantal rings cogenerated by a given fixed minor, is stated in Corollary 1 in Section 3. It follows from a determinantal formula for counting nonintersecting lattice paths in a onesided ladder with respect to turns, where the starting and end points are allowed to be even more general than is needed for our main result. This counting formula is stated in Theorem 2, and it is proved in Section 4. In Section 5 we show how to compute the generating functions for two-rowed arrays that appear in the determinant of our formula.

2 Ladder determinantal rings and the enumeration of nonintersecting lattice paths with respect to turns

Let X = (X_{i,j})_{0≤i≤b, 0≤j≤a} be a (b + 1) × (a + 1) matrix of indeterminates. Let = (Y_{i,j})_{0≤i≤b, 0≤j≤a} be another (b+1)×(a+1) matrix with the property that Y_{i,j} = X_{i,j} or 0, and if Y_{i,j} = X_{i,j} and Y_{i′j′} = X_{i′j′}, where i ≤ i′ and j ≤ j′, then Y_{s,t} = X_{s,t} for all s, t with i ≤ s ≤ i′ and j ≤ t ≤ j′. An example for such a matrix Y, with b = 15 and a = 13 is displayed in Figure 1. (Note that there could be 0’s in the bottom-right corner of the matrix also.) Such a “submatrix” Y of X is called a ladder. This terminology is motivated by the identification of such a matrix Y with the set of all points (j, b − i) in the plane for which Y_{i,j} = X_{i,j}. For example, the set of all such points for the special matrix in Figure 1 is shown in Figure 2. (It should be apparent from comparison of Figures 1 and 2 that the reason for taking (j, b − i) instead of (i, j) is to take care of the difference in “orientation” of row and column indexing of a matrix versus coordinates in the plane.) In general, this set of points looks like a (two-sided) ladder-shaped region. If, on the other hand, we have either Y_{0,0} = X_{0,0} or Y_{b,a} = X_{b,a} then we call Y a one-sided ladder. In the first case we call Y a lower ladder, in the second an upper ladder. Thus, the matrix in Figure 1 is an upper ladder.

( _{X_{15,0}} _{X_{15,1}} _{X_{15,2}} _{X_{15,3}} _{X_{15,4}} _{X_{15,5}} _{X_{15,6}} _{X_{15,7}} _{X_{15,8}} _{X_{15,9}}_{X_{15,10}}_{X_{15,11}}_{X_{15,12}}_{X_{15,13}}_{X_{14,0}} _{X_{14,1}} _{X_{14,2}} _{X_{14,3}} _{X_{14,4}} _{X_{14,5}} _{X_{14,6}} _{X_{14,7}} _{X_{14,8}} _{X_{14,9}}_{X_{14,10}}_{X_{14,11}}_{X_{14,12}}_{X_{14,13}}_{X_{13,0}} _{X_{13,1}} _{X_{13,2}} _{X_{13,3}} _{X_{13,4}} _{X_{13,5}} _{X_{13,6}} _{X_{13,7}} _{X_{13,8}} _{X_{13,9}}_{X_{13,10}}_{X_{13,11}}_{X_{13,12}}_{X_{13,13}}_{X_{12,0}} _{X_{12,1}} _{X_{12,2}} _{X_{12,3}} _{X_{12,4}} _{X_{12,5}} _{X_{12,6}} _{X_{12,7}} _{X_{12,8}} _{X_{12,9}}_{X_{12,10}}_{X_{12,11}}_{X_{12,12}}_{X_{12,13}}_{X_{11,0}} _{X_{11,1}} _{X_{11,2}} _{X_{11,3}} _{X_{11,4}} _{X_{11,5}} _{X_{11,6}} _{X_{11,7}} _{X_{11,8}} _{X_{11,9}}_{X_{11,10}}_{X_{11,11}}_{X_{11,12}}_{X_{11,13}}_{X_{10,0}} _{X_{10,1}} _{X_{10,2}} _{X_{10,3}} _{X_{10,4}} _{X_{10,5}} _{X_{10,6}} _{X_{10,7}} _{X_{10,8}} _{X_{10,9}}_{X_{10,10}}_{X_{10,11}}_{X_{10,12}}_{X_{10,13}}_{X_{9,0}} _{X_{9,1}} _{X_{9,2}} _{X_{9,3}} _{X_{9,4}} _{X_{9,5}} _{X_{9,6}} _{X_{9,7}} _{X_{9,8}} _{X_{9,9}} _{X_{9,10}} _{X_{9,11}} _{X_{9,12}} _{X_{9,13}}_{0} _{0} _{0} _{0} _{X_{8,4}} _{X_{8,5}} _{X_{8,6}} _{X_{8,7}} _{X_{8,8}} _{X_{8,9}} _{X_{8,10}} _{X_{8,11}} _{X_{8,12}} _{X_{8,13}}^{0} ^{0} ^{0} ^{0} ^{X_{7,4}} ^{X_{7,5}} ^{X_{7,6}} ^{X_{7,7}} ^{X_{7,8}} ^{X_{7,9}} ^{X_{7,10}} ^{X_{7,11}} ^{X_{7,12}} ^{X_{7,13}}^{0} ^{0} ^{0} ^{0} ^{X_{6,4}} ^{X_{6,5}} ^{X_{6,6}} ^{X_{6,7}} ^{X_{6,8}} ^{X_{6,9}} ^{X_{6,10}} ^{X_{6,11}} ^{X_{6,12}} ^{X_{6,13}}^{0} ^{0} ^{0} ^{0} ^{0} ^{X_{5,5}} ^{X_{5,6}} ^{X_{5,7}} ^{X_{5,8}} ^{X_{5,9}} ^{X_{5,10}} ^{X_{5,11}} ^{X_{5,12}} ^{X_{5,13}}^{0} ^{0} ^{0} ^{0} ^{0} ^{0} ^{X_{4,6}} ^{X_{4,7}} ^{X_{4,8}} ^{X_{4,9}} ^{X_{4,10}} ^{X_{4,11}} ^{X_{4,12}} ^{X_{4,13}}^{0} ^{0} ^{0} ^{0} ^{0} ^{0} ^{0} ^{X_{3,7}} ^{X_{3,8}} ^{X_{3,9}} ^{X_{3,10}} ^{X_{3,11}} ^{X_{3,12}} ^{X_{3,13}}^{0} ^{0} ^{0} ^{0} ^{0} ^{0} ^{0} ^{0} ^{X_{2,8}} ^{X_{2,9}} ^{X_{2,10}} ^{X_{2,11}} ^{X_{2,12}} ^{X_{2,13}}^{0} ^{0} ^{0} ^{0} ^{0} ^{0} ^{0} ^{0} ^{X_{1,8}} ^{X_{1,9}} ^{X_{1,10}} ^{X_{1,11}} ^{X_{1,12}} ^{X_{1,13}}^{0} ^{0} ^{0} ^{0} ^{0} ^{0} ^{0} ^{0} ^{X_{0,8}} ^{X_{0,9}} ^{X_{0,10}} ^{X_{0,11}} ^{X_{0,12}} ^{X_{0,13}} ) Fig. 1.

Now fix a “bivector” M = [u_{1}, u_{2}, …, u_{n} | v_{1}, v_{2}, …, v_{n}] of positive integers with u_{1} < u_{2} < ⋯ < u_{n} and v_{1} < v_{2} < ⋯ < v_{n}. Let K[Y] denote the ring of all polynomials over some field K in the Y_{i,j}’s, 0 ≤ i ≤ b, 0 ≤ j ≤ a,

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •_{0} _{1} _{2} _{3} _{4} _{5} _{6} _{7} _{8} _{9} _{10}_{11}_{12}_{13}^{1}^{2}^{3}^{4}^{5}^{6}^{7}^{8}^{9}^{10}^{11}^{12}^{13}^{14}^{15} Fig. 2.

and let I_{M}(Y) be the ideal in K[Y] that is generated by those t × t minors of Y that contain only nonzero entries, whose rows form a subset of the last u_{t} − 1 rows, or whose columns form a subset of the last v_{t} − 1 columns, t = 1, 2, …, n + 1. Here, by convention, u_{n+1} is set equal to b + 2, and v_{n+1} is set equal to a + 2. (Thus, for t = n + 1 the rows and columns of minors are unrestricted.) The ideal I_{M}(Y) is called a ladder determinantal ideal cogenerated by the minor M. (That one speaks of ‘the minor M’ has its explanation in the identification of the bivector M with a particular minor of Y, cf. [11, Sec. 2]. It should be pointed out that our conventions here deviate slightly from the ones in [11]. In particular, we defined the ideal I_{M}(Y) by restricting rows and columns of minors to a certain number of last rows or columns, while in [11] it is first rows, respectively columns. Clearly, a rotation of the matrix by 180^{∘} transforms one convention into the other.) The associated ladder determinantal ring cogenerated by M is R_{M}(Y) := K[Y]/I_{M}(Y). (We remark that the definition of ladder is more general in [1,2,5,11]. However, there is in effect no loss of generality since the ladders of [1,2,5,11] can always be reduced to our definition by discarding superfluous 0’s.)

When Abhyankar introduced ladder determinantal rings in the early 1980s, he was motivated by the study of singularities of Schubert varieties. Indeed, as was shown recently by Gonciulea and Lakshmibai in [10] (see also [3, Ch. 12]), the associated varieties (called ladder determinantal varieties) can be identified with opposite cells of certain Schubert varieties of type A. This connection allowed them to identify the irreducible components of such Schubert varieties in many cases, thus making substantial progress on a long-standing problem in algebraic geometry.

Results of Abhyankar [1,2] or Herzog and Trung [11] allow to express the Hilbert series of the ladder determinantal ring R_{M}(Y) in combinatorial terms. Before we can state the corresponding result, we need to introduce a few more terms.

When we say lattice path we always mean a lattice path in the plane consisting of unit horizontal and vertical steps in the positive direction, see Figure 3 for an example. We shall frequently abbreviate the fact that a lattice path P goes from A to E by P : A → E.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • •^{P_{0}}^{Fig. 3.}

Also, given lattice points A and E, we denote the set of all lattice paths from A to E by P(A → E). A family (P_{1}, P_{2}, …, P_{n}) of lattice paths P_{i}, i = 1, 2, …, n, is said to be nonintersecting if no two lattice paths of this family have a point in common. Given n-tuples of lattice points A = (A^{(1)}, A^{(2)}, …, A^{(n)}) and E = (E^{(1)}, E^{(2)}, …, E^{(n)}), we denote the set of all families (P_{1}, P_{2}, …, P_{n}) of nonintersecting lattice paths, where P_{i} runs from A^{(i)} to E^{(i)}, i = 1, 2, …, n, by P^{+}(A → E).

A point in a lattice 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 lattice path P. The NE-turns of the lattice path in Figure 3 are (1, 1), (2, 3), and (5, 4). We write NE(P) for the number of NE-turns of P. Also, given a family P = (P_{1}, P_{2}, …, P_{n}) of paths P_{i}, we write NE(P) for the number ∑_{i=1}^{n} NE(P_{i}) of all NE-turns in the family.

Our lattice paths will be restricted to ladder-shaped regions L corresponding to the nonzero entries of a given matrix Y in the way that was explained earlier (cf. Figures 1 and 2). We extend our lattice path notation in the following way. By P_{L}(A → E) we mean the set of all lattice paths P from A to E all of whose NE-turns lie in the ladder region L. (It should be noted that, in the case of a two-sided ladder, it is possible that a path is not totally inside L while its NE-turns are. However, in the case of an upper ladder L, which is the case of interest in our paper, a path is inside L if and only if all of its NE-turns are.) Similarly, by P_{L}^{+}(A → E) we mean the set of all families (P_{1}, P_{2}, …, P_{n}) of nonintersecting lattice paths, where P_{i} runs from A^{(i)} to E^{(i)} and where all the NE-turns of P_{i} lie in the ladder region L.

Finally, given any weight function w defined on a set M, by the generating function GF(M; w) we mean ∑_{x∈M} w(x).

Theorem 1. Let Y = (Y_{i,j})_{0≤i≤b, 0≤j≤a} be a one-sided ladder, and let L be the associated ladder region, i.e., Y_{i,j} = X_{i,j} if and only if (j, b − i) ∈ L. Let M = [u_{1}, u_{2}, …, u_{n} | v_{1}, v_{2}, …, v_{n}] be a bivector of positive integers with u_{1} < u_{2} < ⋯ < u_{n} and v_{1} < v_{2} < ⋯ < v_{n}. Furthermore, let A^{(i)} = (0, u_{n+1−i}−1) and E^{(i)} = (a − v_{n+1−i} + 1, b), i = 1, 2, …, n. Then, under the assumption that all of the points A^{(i)} and E^{(i)}, i = 1, 2, …, n, lie inside the ladder region L, the Hilbert series of the ladder determinantal ring R_{M}(Y) = K[Y]/I_{M}(Y) equals

∑_{ℓ=0}^{∞} dim_{K} R_{M}(Y)_{ℓ} z^{ℓ} = \frac{GF(P_{L}^{+}(A → E); z^{NE(.)})}{(1 − z)^{(a+b+3)n−∑_{i=1}^{n}(u_{i}+v_{i})}} ,  (1)

where R_{M}(Y)_{ℓ} denotes the homogeneous component of degree ℓ in R_{M}(Y), and where, according to our definitions, GF(P_{L}^{+}(A → E); z^{NE(.)}) is the generating function ∑_{P} z^{NE(P)} for all families P = (P_{1}, P_{2}, …, P_{n}) of nonintersecting lattice paths, P_{i} running from A^{(i)} to E^{(i)}, such that all of its NE-turns stay inside the ladder region L.

Remark 1. (a) The condition that all of the points A^{(i)} and E^{(i)} lie inside the ladder region L restricts the choice of ladders. In particular, for an upper ladder it means that Y_{b−u_{n}+1,0} = X_{b−u_{n}+1,0} and Y_{0,a−v_{n}+1} = X_{0,a−v_{n}+1}, which will be relevant for us. Still, one could prove an analogous result even if this condition is dropped. In that case, however, the points A^{(i)} and E^{(i)} have to be modified in order to lie inside L and, thus, make the right-hand side of formula (1) meaningful.

(b) For an extension of Theorem 1 for the case of two-sided ladders see [24, Theorem 3.1].

Sketch of Proof. In [17, proof of Theorem 2], we gave two proofs of this assertion in the special case of a one-sided ladder and u_{i} = v_{i} = i, i = 1, 2, …, n (cf. Example (1) on p. 10 of [11]). The first proof followed basically considerations by Kulkarni [20,21] (see also [8]), and was based on an explicit basis for R_{M}(Y) given by Abhyankar [1, Theorem (20.10)(5)]. The second proof was based on combinatorial descriptions of the dimensions R_{M}(Y)_{ℓ} of the homogeneous components of R_{M}(Y) due to Herzog and Trung [11, Cor. 4.3 + Lemma 4.4]. Both proofs carry over verbatim to our more general situation because both Abhyankar’s as well as Herzog and Trung’s results are in fact theorems for the general ladder determinantal rings that we consider here. (However, the reader must be warned that the explicit form of Abhyankar’s basis was misquoted in [17]. The correct assertion is that, given a multiset S as described in [17], the associated basis element is the product of a certain monomial in the X_{ij}’s and a certain minor of the matrix Y, see [1, definition of w_{v}(t) in Theorem (20.10)] or [8, Theorem (6.7)(iii)] Also, the definition of the multisets S contained an error: Item 2 at the bottom of p. 1019 in [17] must be replaced by: The length of any sequence (i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{k}, j_{k}) of elements of S is at most n. The subsequent argument was however based on this corrected definition.) ⊓ ⊔

3 The determinantal formula

In view of Theorem 1, the computation of Hilbert series of ladder determinantal rings requires to solve the problem of counting families of nonintersecting lattice paths in a ladder-shaped region with respect to turns. We provide such a solution for one-sided ladders in Theorem 2. In order to formulate the result, we need to introduce the notion of two-rowed arrays.

From now on we restrict our attention to one-sided ladders. Without loss of generality it suffices to consider upper ladders. We encode upper laddershaped regions (such as the one in Figure 2) concisely by means of weakly increasing functions as follows: given an upper ladder region L, let f be the weakly increasing function from [0, a] to [1, b + 1] with the property that it describes L by means of

L = {(x, y) : x ∈ [0, a] and 0 ≤ y < f(x)}.  (2)

Here, by [c, d] we mean the set of all integers ≥ c and ≤ d. In essence, the function f describes the upper border of the region L. For example, the function f corresponding to the ladder region in Figure 2 (where a = 13 and b = 15) is given by f(0) = 7, f(1) = 7, f(2) = 7, f(3) = 7, f(4) = 10, f(5) = 11, f(6) = 12, f(7) = 13, f(8) = 16, f(9) = 16, f(10) = 16, f(11) = 16, f(12) = 16, f(13) = 16.

By a two-rowed array we mean two rows of integers

\begin{aligned}a_{−l+1} & a_{−l+2} & … & a_{−1} & a_{0} & a_{1} & … & a_{k} \\ & & & & & b_{1} & … & b_{k}, \end{aligned}  (3)

where entries along both rows are strictly increasing. We call l the type of the two-rowed array. We allow l to be also negative. In this case the representation (3) has to be taken symbolically, in the sense that the first row of the tworowed array is (by −l) shorter than the second row, i.e., looks like

\begin{aligned}& & & & a_{−l+1} & … & a_{k} \\ b_{1} & b_{2} & … & b_{−l} & b_{−l+1} & … & b_{k}. \end{aligned}  (4)

We define the size |T | of a two-rowed array T to be the number of its entries. (Thus, the size of the two-rowed array in (3) is l + 2k, as is the size of the one in (4).) We extend this definition and notation to families T = (T_{1}, T_{2}, …, T_{n}) of two-arrays by letting |T| denote the total number |T_{1}| + |T_{2}| + ⋯ + |T_{n}| of entries in T.

Now we define the basic set of objects which is crucial in our formulas. Given a function f as above, and pairs A = (α_{1}, α_{2}) and E = (ε_{1}, ε_{2}), we denote by TA(l; A, E; f, d) the set of all two-rowed arrays of type l such that

• the entries in the first row are bounded below by α_{1} and bounded above by ε_{1},

• the entries in the second row are bounded below by α_{2} and bounded above by ε_{2},

• if the two-rowed array is represented as in (3) (respectively (4)), we have

b_{s} < f(a_{s+d}),  (5)

for all s such that both b_{s} and a_{s+d} exist in the two-rowed array.

If we want to make the lower and upper bounds transparent, then we will write such two-rowed arrays in the form

\begin{aligned}α_{1} ≤ & a_{−l+1} & a_{−l+2} & … & a_{−1} & a_{0} & a_{1} & … & a_{k} & ≤ ε_{1} \\ α_{2} ≤ & & & & & & b_{1} & … & b_{k} & ≤ ε_{2}. \end{aligned}  (6)

Our key theorem is the following.

Theorem 2. Let n, a, b be positive integers and let L be an upper laddershaped region determined by the weakly increasing function f : [0, a] → [1, b + 1] by means of (2). For convenience, extend f to all negative integers by setting f(x) := f(0) for x < 0. Furthermore, let A^{(i)} = (A_{1}^{(i)}, A_{2}^{(i)}) and E^{(i)} = (E_{1}^{(i)}, E_{2}^{(i)}) for i = 1, 2, …, n be lattice points in the region L satisfying

f(x) = f(A_{1}^{(1)}) for all x ≤ A_{1}^{(1)},  (7)

and

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

and

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

Then the generating function ∑ z^{NE(P)}, where the sum is over all families P = (P_{1}, P_{2}, …, P_{n}) of nonintersecting lattice paths P_{i} : A^{(i)} → E^{(i)}, i = 1, 2, …, n lying in the region L, can be expressed as

GF(P_{L}^{+}(A → E); z^{NE(.)})

= det_{1≤s,t≤n} ( GF(TA(t − s; Ã^{(t)}, Ẽ^{(s)}; f, s − 1); z^{|.|/2})), (10)

where Ã^{(i)} = A^{(i)} + (−i + 1, i) and Ẽ^{(i)} = E^{(i)} + (−i, i − 1), i = 1, 2, …, n. Here, by our definitions, GF(TA(t − s; Ã^{(t)}, Ẽ^{(s)}; f, s − 1); z^{|.|/2}) is the generating function ∑_{T} z^{|T |/2}, where the sum is over all two-rowed arrays of the form (6) with l = t − s, d = s − 1, α_{1} = A_{1}^{(i)} − i + 1, α_{2} = A_{2}^{(i)} + i, ε_{1} = E_{1}^{(i)} − i, and ε_{2} = E_{2}^{(i)} + i − 1, which satisfy (5).

Remark 2. (a) The condition (7) is equivalent to saying that to the left of A^{(1)}, which by (8) is the left-most starting point of the lattice paths, the boundary of the ladder region is horizontal. Clearly, this can be assumed without loss of generality because this part of the ladder (i.e., the ladder to the left of A^{(1)}) does not impose any restriction on the lattice paths, and, hence, on the left-hand side of (10).

(b) The formula (10) clearly reduces the problem of enumerating families of nonintersecting lattice paths in the ladder region L with respect to NEturns to the problem of enumerating certain two-rowed arrays. We are going to address this problem in Section 5.

Thus, if we combine Theorems 1 and 2, we obtain the promised determinantal formula for the Hilbert series of one-sided ladder determinantal rings.

Corollary 1. Let Y = (Y_{i,j})_{0≤i≤b, 0≤j≤a} be an upper ladder, and let L be the associated ladder region, i.e., Y_{i,j} = X_{i,j} if and only if (j, b − i) ∈ L, and let f : [0, a] → [1, b + 1] be the function that describes this ladder region by means of (2), i.e., Y_{i,j} = X_{i,j} if and only if b − i < f(j). For convenience, extend f to all negative integers by setting f(x) := f(0) for x < 0. Let M = [u_{1}, u_{2}, …, u_{n} | v_{1}, v_{2}, …, v_{n}] be a bivector of positive integers with u_{1} < u_{2} < ⋯ < u_{n} and v_{1} < v_{2} < ⋯ < v_{n} such that Y_{b−u_{n}+1,0} = X_{b−u_{n}+1,0} and Y_{0,a−v_{n}+1} = X_{0,a−v_{n}+1} (cf. Remark 1.(a) after Theorem 1). Furthermore, we let Ã^{(i)} = (−i + 1, u_{n+1−i} + i − 1) and Ẽ^{(i)} = (a − v_{n+1−i} − i + 1, b + i − 1), i = 1, 2, …, n. Then the Hilbert series of the ladder determinantal ring R_{M}(Y) = K[Y]/I_{M}(Y) equals

∑_{ℓ=0}^{∞} dim_{K} R_{M}(Y)_{ℓ} z^{ℓ}

= \frac{det_{1≤s,t≤n} ( GF(TA(t − s; Ã^{(t)}, Ẽ^{(s)}; f, s − 1); z^{|.|/2}))}{(1 − z)^{(a+b+3)n−∑_{i=1}^{n}(u_{i}+v_{i})}}. (11)

Remark 3. (a) Theorem 2 specializes to Theorem 1 in [14] in the case of a trivial ladder (i.e., if the function f is equal to b + 1 for all x). For, in that case, by (37) the generating functions GF(TA(t−s; Ã_{t}, Ẽ_{s}; f, s−1); z^{|.|/2}) can be expressed in terms of binomial sums. To see that the resulting formula is indeed equivalent, one extracts the coefficient of z^{K}.

(b) For the same reason, Corollary 1 specializes to Abhyankar’s formula [1, (20.14.4), L = 2, k = 2, with F^{(22)}(m, p, a, V) defined on p. 50] in the case of a trivial ladder. Although Abhyankar’s formula gives an expression for the Hilbert function (instead of for the Hilbert series), it is easy to see that it is equivalent to ours in this special case.

(c) The formula for the Hilbert series in [17, Theorem 2] addresses the special case u_{i} = v_{i} = i, i = 1, 2, …, n. However, Corollary 1 does not generalize this formula, as it does not directly specialize to Theorem 2 in [17]. Whereas in the latter formula the entries of the determinant are generating functions for paths, there is no such interpretation for the entries of the determinant in (11).

(d) Unfortunately, we do not know how to generalize Theorem 2, and, thus, Corollary 1, to the case of two-sided ladders. It seems that a completely new idea is needed to find such a generalization. In particular, the combinatorial formula [24, Theorem 3.1] for the Hilbert series in the case of two-sided ladders, on which such a generalization would have to be based, is already considerably more complicated than its special case for the case of one-sided ladders, stated in Theorem 1.

(e) More modest, but equally desirable, would it be to find an extension of Corollary 1 in the one-sided case to ladders L and bivectors M which do not satisfy the conditions of the statement, i.e., for which either Y_{b−u_{n}+1,0} = 0, or Y_{0,a−v_{n}+1} = 0, or both. This would require to find an extension of Theorem 2 to situations where the inequality chains (8) and (9) may be relaxed so that some starting and end points are allowed to lie on the boundary of the ladder region L (cf. Remark 1.(a) after Theorem 1). It seems again that a completely new idea is needed to find such an extension.

(f) In Section 5 of [17] it is shown that the proof of the main counting theorem yields in fact a weighted generalization thereof. An analogous weighted generalization of Theorem 2 can be obtained as well, which is again directly implied by the proof of Theorem 2 in Section 4. However, we omit the statement of this generalization for the sake of brevity.

Example 1. Let a = 13, b = 15, n = 4, let Y = (Y_{i,j}) be the matrix of Figure 1 and M = [1, 2, 4, 6 | 1, 2, 3, 6]. Our formula (11) gives for the Hilbert series of R_{M}(Y) = K[Y]/I_{M}(Y), using (45) for determining the generating function ∑_{T ∈TA(l;A,E;f,d)} z^{|.|/2} for two-rowed arrays T in the corresponding ladder region L of Figure 2,

(1+71z+2556z^{2}+61832z^{3}+1115762z^{4}+15750005z^{5}+178390279z^{6}+1647137174z^{7}

+12534233703z^{8}+79245271879z^{9}+418852424787z^{10}+1859941402206z^{11}+6965987806143z^{12} +22071622313567z^{13}+59298706514083z^{14}+135299444287353z^{15}+262400571075662z^{16} +432640455645309z^{17}+606103694379729z^{18}+720535170430557z^{19}+725289798304502z^{20} +616230022969392z^{21}+439998448014899z^{22}+262469031030333z^{23}+129776697745621z^{24} +52622863698472z^{25}+17241967478923z^{26}+4468021840695z^{27}+885721405230z^{28} +126901720400z^{29}+11760999250z^{30}+532021875z^{31})/(1−z)^{99}.

4 Proof of Theorem 2

The basic idea of the proof is simple. It largely follows the proof of Theorem 4 in [14]. As a first step, we expand the determinant on the right-hand side of (10) according to the definition of a determinant, see Subsection 4.1. Thus, we obtain a sum of terms, each of which is indexed by a family of two-rowed arrays, see (12). Some of the terms have positive sign, some of them negative sign. In the second step, we identify the terms which cancel each other, see Subsection 4.2. Finally, in the third step, we identify the remaining terms with the families of nonintersecting lattice paths in the statement of the theorem, see Subsection 4.3.

However, the details are sometimes intricate. To show that the terms described in Subsection 4.2 do indeed cancel, we define an involution on families of two-rowed arrays in Subsection 4.4. (This involution is copied from [14, Proof of Theorem 4].) In order that our claims follow, this involution must have several properties, which are listed in Subsection 4.5. While most of these are either obvious or are already established in [14] and [23], we are only able to provide a rather technical justification of the one pertaining to the ladder condition. This is done in Subsection 4.6.

4.1 Expansion of the determinant

Let 𝔖_{n} denote the symmetric group of order n. We start by expanding the determinant on the right-hand side of (10), to obtain

det_{1≤s,t≤n} ( GF(TA(t − s; Ã^{(t)}, Ẽ^{(s)}; f, s − 1); z^{|.|/2}))

= ∑_{σ∈𝔖_{n}} sgn σ ∏_{i=1}^{n} GF(TA(σ(i) − i; Ã^{(σ(i))}, Ẽ^{(i)}; f, i − 1); z^{|.|/2})

= ∑_{(T,σ)} sgn σ z^{|T|},  (12)

where the sum is over all pairs (T, σ) of permutations σ in 𝔖_{n}, and families T = (T_{1}, T_{2}, …, T_{n}) of two-rowed arrays, T_{i} being of type σ(i) − i (i.e., the second row containing k_{i} entries and the first row containing k_{i} + σ(i) − i entries, for some k_{i}), and the bounds for the entries of T_{i} being as follows,

\begin{aligned}Ã_{1}^{(σ(i))} ≤ & a_{−σ(i)+i+1}^{(i)} … & a_{1}^{(i)} & … & a_{k_{i}}^{(i)} & ≤ Ẽ_{1}^{(i)} \\ Ã_{2}^{(σ(i))} ≤ & & b_{1}^{(i)} & … & b_{k_{i}}^{(i)} & ≤ Ẽ_{2}^{(i)}, \end{aligned}  (13)

with the property that

b_{s}^{(i)} < f(a_{s+i−1}^{(i)}),  s = 1, 2, …, k_{i} − i + 1,  (14)

i = 1, …, n.

4.2 Which terms in (12) cancel?

Now we claim that the total contribution to the sum (12) of the families (T_{1}, T_{2}, …, T_{n}) of two-rowed arrays as above which have the property that there exist T_{i} and T_{i+1}, T_{i} represented by

\begin{aligned}Ã_{1}^{(σ(i))} ≤ & a_{−σ(i)+i+1} … & a_{1} & … & a_{k} & ≤ Ẽ_{1}^{(i)} \\ Ã_{2}^{(σ(i))} ≤ & & b_{1} & … & b_{k} & ≤ Ẽ_{2}^{(i)}, \end{aligned}  (15a)

and T_{i+1} represented by

\begin{aligned}Ã_{1}^{(σ(i+1))} ≤ & c_{−σ(i+1)+i+2} … & c_{1} & … & c_{l} & ≤ Ẽ_{1}^{(i+1)} \\ Ã_{1}^{(σ(i+1))} ≤ & & d_{1} & … & d_{l} & ≤ Ẽ_{1}^{(i+1)}, \end{aligned}  (15b)

and indices I and J such that

c_{J} < a_{I}  (15c)
b_{I−1} < d_{J}  (15d)

and

1 ≤ I ≤ k + 1, 0 ≤ J ≤ l,  (15e)

equals 0. The inequalities (15c) and (15d) should be understood to hold only if all variables are defined, including the conventional definitions a_{k+1} := Ẽ_{1}^{(i)} + 1, b_{0} := Ã_{2}^{(σ(i))} − 1, and c_{−σ(i+1)+i+1} := Ã_{1}^{(σ(i))} − 1. (These artificial settings apply for I = k + 1, I = 1, and J = −σ(i + 1) + i + 1, respectively. It should be noted that the indexing conventions that we have chosen here deviate slightly from [14, Sec. 3, proof of Theorem 4], but are completely equivalent.)

We call the point (a_{I}, d_{J}) a crossing point of T_{i} and T_{i+1}, and, more generally, a crossing point of the family T.

4.3 The remaining terms correspond to nonintersecting lattice paths

Suppose that we would have shown that the contribution to (12) of these families of two-rowed arrays equals zero. It implies that only those families T = (T_{1}, T_{2}, …, T_{n}) of two-rowed arrays, T_{i} being of the form (13) and satisfying (14), contribute to (12) where T_{i} and T_{i+1} have no crossing point for all i.

So, let T be such a family of two-rowed arrays without any crossing point. By using the arguments from [23]^{1} (with A_{1}^{(i)}, A_{2}^{(i)}, E_{1}^{(i)}, E_{2}^{(i)} in [23] replaced

1 The proof in the original paper [14, last paragraph of the proof of Theorem 4] contained an error at this point. The inequality A_{1}^{(σ(i+1))} −1 ≤ A^{(σ(i))} on page 12 of [14] is not true in general.

by our Ã_{1}^{(i)}, Ã_{2}^{(i)}−1, Ẽ_{1}^{(i)}+1, Ẽ_{2}^{(i)}, respectively, i = 1, 2, …, n), it then follows that the permutation σ associated to T must be the identity permutation. Thus, the two-rowed array T_{i} has the form (recall (13))

\begin{aligned}Ã_{1}^{(i)} ≤ & a_{1}^{(i)} & … & a_{k_{i}}^{(i)} & ≤ Ẽ_{1}^{(i)} \\ Ã_{2}^{(i)} ≤ & b_{1}^{(i)} & … & b_{k_{i}}^{(i)} & ≤ Ẽ_{2}^{(i)}, \end{aligned}  (16)

and satisfies (14). Moreover, we assumed that there is no crossing point, meaning that there are no consecutive two-rowed arrays T_{i} and T_{i+1} and indices I and J such that (15) holds.

By interpreting the two-rowed array (16) as a lattice path P̃_{i} from Ã^{(i)} − (0, 1) to Ẽ^{(i)} + (1, 0) whose NE-turns are exactly (a_{1}^{(i)}, b_{1}^{(i)}), …, (a_{k_{i}}^{(i)}, b_{k_{i}}^{(i)}), i = 1, 2, …, n, the family T of two-rowed arrays is translated into a family P̃ = (P̃_{1}, P̃_{2}, …, P̃_{n}) of paths. Clearly, under this translation we have |T|/2 = NE(P̃), and, hence,

z^{|T|/2} = z^{NE(P̃)}.  (17)

The fact that (15) does not hold simply means that the paths P̃_{i} and P̃_{i+1} do not cross each other (that is, they may touch each other, but they never change sides), i = 1, 2, …, n − 1. We refer the reader to the explanations in Section 2 (between Theorems 3 and 4) in [14]. Here, we content ourselves with an illustration. Suppose two paths Q_{1} and Q_{2} cross each other (see Figure 4). Furthermore suppose that the NE-turns of Q_{1} are (a_{1}, b_{1}), (a_{2}, b_{2}), …, (a_{k}, b_{k}), and the NE-turns of Q_{2} are (c_{1}, d_{1}), (c_{2}, d_{2}), …, (c_{l}, d_{l}). Then it is obvious from Figure 4 that there exist I and J such that (15c)–(15e) hold.

• • •^{(c_{J}, d_{J})}  _{(a_{I}, b_{I−1})}  ^{Q_{1}}  ^{Q_{2}}^{Fig. 4.}

To finally match with the claim of Theorem 2, we shift P̃_{i} by (i−1, −i+1), i = 1, 2, …, n. Thus we obtain a family (P_{1}, P_{2}, …, P_{n}) of lattice paths, P_{i} running from A^{(i)} to E^{(i)}. Clearly, under this shift, the condition that P̃_{i} and P̃_{i+1} do not cross each other translates into the condition that P_{i} and P_{i+1} do not touch each other, i = 1, 2, …, n − 1. If we combine this fact with the observation that the first path, P_{1} = P̃_{1}, stays inside the ladder region L because of (14) with i = 1, then we conclude that all the P_{i}’s must also stay inside L because P_{1} forms a barrier.

Thus, in view of (17), we have proved that the right-hand side of (10) is equal to the generating function ∑_{P} z^{NE(P)}, where the sum is over all families P = (P_{1}, P_{2}, …, P_{n}) of nonintersecting lattice paths, P_{i} running from A^{(i)} to E^{(i)} and staying inside the ladder region L. But this is exactly the left-hand side of (10). Thus Theorem 2 would be proved.

4.4 The involution

To show that the contribution to the sum (12) of the families T = (T_{1}, T_{2}, …, T_{n}) of two-rowed arrays, T_{i} being of the form (13) and satisfying (14) for i = 1, 2, …, n, which contain consecutive arrays T_{i} and T_{i+1} that have a crossing point (cf. (15)), indeed equals 0, we construct an involution, φ say, on this set of families that maps a family (T_{1}, T_{2}, …, T_{n}) with associated permutation σ to a family \overline{T} = (\overline{T}_{1}, \overline{T}_{2}, …, \overline{T}_{n}) with associated permutation \overline{σ}, such that

sgn σ = − sgn \overline{σ},  (18)

and such that

|T| = |\overline{T}|.  (19)

Clearly, this implies that the contribution to (12) of families that are mapped to each other cancels.

The definition of the involution φ can be copied from [14, Sec. 3, proof of Theorem 4]. For convenience, we repeat it here. Let (T, σ) be a pair under consideration for the sum (12). Besides, we assume that T has a crossing point. Consider all crossing points of two-rowed arrays with consecutive indices (see (15)). 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 T_{i} and T_{i+1}. Let T_{i} and T_{i+1} be given by (15a) and (15b), respectively. By (15), S being a crossing point of T_{i} and T_{i+1} means that there exist I and J such that T_{i} looks like

\begin{aligned}Ã_{1}^{(σ(i))} ≤ & … & a_{I−1} & a_{I} & … & a_{k_{i}} & ≤ Ẽ_{1}^{(i)} \\ Ã_{2}^{(σ(i))} ≤ & … & b_{I−1} & b_{I} & … & b_{k_{i}} & ≤ Ẽ_{2}^{(i)}, \end{aligned}  (20)

T_{i+1} looks like

\begin{aligned}Ã_{1}^{(σ(i+1))} ≤ & . . . . . . . . & c_{J} & c_{J+1} & … & c_{k_{i+1}} & ≤ Ẽ_{1}^{(i)} \\ Ã_{2}^{(σ(i+1))} ≤ & … & d_{J−1} & d_{J} & . . . . . . . . & d_{k_{i+1}} & ≤ Ẽ_{2}^{(i)}, \end{aligned}  (21)

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

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

and

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

Because of the construction of S, the indices I and J are maximal with respect to (22).

We map (T, σ) to the pair (\overline{T}, σ ∘ (i, i + 1)) ((i, i + 1) denotes the transposition exchanging i and i + 1), where \overline{T} = (\overline{T}_{1}, \overline{T}_{2}, …, \overline{T}_{n}), with \overline{T}_{j} = T_{j} for all j ≠ i, i + 1, with \overline{T}_{i} being given by

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

and with \overline{T}_{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}  (23b)

4.5 The properties of the involution

What we have to prove is that this operation is well-defined, i.e., that all the rows in (23a) and (23b) are strictly increasing, that \overline{T}_{i} is of type (σ ∘ (i, i + 1))(i) − i = σ(i + 1) − i, that \overline{T}_{i+1} is of type (σ ∘ (i, i + 1))(i + 1) − i − 1 = σ(i) − i − 1, that the bounds for the entries of \overline{T}_{i} are given by

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

that those for \overline{T}_{i+1} are given by

\begin{aligned}Ã_{1}^{(σ(i))} ≤ & . . . . . . . . & a_{I−1} & c_{J+1} & … & c_{k_{i+1}} & ≤ Ẽ_{1}^{(i+1)} \\ Ã_{2}^{(σ(i))} ≤ & … & b_{I−1} & d_{J} & . . . . . . . . & d_{k_{i+1}} & ≤ Ẽ_{2}^{(i+1)}, \end{aligned}

and that (14) is satisfied for \overline{T}_{i} and \overline{T}_{i+1}. Furthermore we have to prove that φ is indeed an involution (for which it suffices to show that (22) also holds for \overline{T}_{i} and \overline{T}_{i+1}), and finally we must prove (18) (with \overline{σ} = σ ∘ (i, i + 1)) and (19).

The claim that (18) and (19) hold is trivial. All other claims, except for the claim about (14), can be proved by copying the according arguments from the proof of Theorem 4 in [14] (see the paragraphs after [14, Eq. (27)]).

4.6 The involution respects the ladder condition

It remains to show that (14) is satisfied for \overline{T}_{i} and \overline{T}_{i+1}. Unfortunately, it is necessary to supplement and refine the according arguments in the proof of the main theorem in [17] (see the proof of (4.27) and (4.28) in [17, pp. 1035– 37]) substantially in order to cope with the situation that we encounter here. Besides, we use the opportunity to correct an inaccuracy in [17].

We have to prove that for 1 ≤ r ≤ i − 1 we have

d_{J−i+r} < f(a_{I−1+r}),  (24)

provided both a_{I−1+r} and d_{J−i+r} exist (if either a_{I−1+r} or d_{J−i+r} does not exist there is nothing to show), and

b_{I−i+r} < f(c_{J+r}),  (25)

provided both b_{I−i+r} and c_{J+r} exist (if either b_{I−i+r} or c_{J+r} does not exist there is nothing to show).

Proof of (24). In the following, let r be fixed. We distinguish between two cases. If E_{1}^{(1)} ≤ a_{I}, then we have the following chain of inequalities:

d_{J−i+r} ≤ d_{J−1} + 1 − i + r ≤ b_{I} − i + r ≤ b_{I−1+r} − i + 1

≤ Ẽ_{2}^{(i)} − i + 1 = E_{2}^{(i)} ≤ E_{2}^{(1)} < f(E_{1}^{(1)}) ≤ f(a_{I}) ≤ f(a_{I−1+r}), (26)

as required. (The second inequality in (26) follows from the fact that the rows in (23a) are strictly increasing.)

Otherwise, if E_{1}^{(1)} > a_{I}, let us assume for the purpose of contradiction that (24) does not hold. Then, because of the first two inequalities in (26) we have d_{J−i+r} ≤ b_{I}, and hence

f(a_{I}) ≤ f(a_{I−1+r}) ≤ d_{J−i+r} ≤ b_{I}.  (27)

In more colloquial terms, the point (a_{I}, b_{I}) lies outside the ladder region L defined by (2).

For the following, we make the conventional definitions a_{−σ(j)+j}^{(j)} :=

Ã_{1}^{(σ(j))} − 1, a_{k_{j}+1}^{(j)} := Ẽ_{1}^{(j)} + 1 (which is in accordance with the conventional

definition for a_{k+1} in (15)), and b_{0}^{(j)} := Ã_{2}^{(σ(j))} − 1 (which is in accordance with the conventional definition for b_{0} in (15)).

For any j < i we claim that, if for the two-rowed array T_{j+1} (given by (13) with i replaced by j + 1) we find a pair (a_{s_{j+1}}^{(j+1)}, b_{s_{j+1}}^{(j+1)}) of entries (i.e., a_{s_{j+1}}^{(j+1)} and b_{s_{j+1}}^{(j+1)} exist in T_{j+1} or are defined by means of one of the above conventional definitions) such that^{2}

a_{I} ≥ a_{s_{j+1}}^{(j+1)} and b_{I} ≤ b_{s_{j+1}}^{(j+1)},  (28)

then we can find an h ≤ j such that the two-rowed array T_{h} contains a pair (a_{s_{h}}^{(h)}, b_{s_{h}}^{(h)}) satisfying the same condition, that is

a_{I} ≥ a_{s_{h}}^{(h)} and b_{I} ≤ b_{s_{h}}^{(h)}.  (29)

In other words, we claim that if in T_{j+1} we find a pair of entries which, when considered as a lattice point, is located (weakly) northwest of (a_{I}, b_{I}), then we will also find such a pair in T_{h} for some h ≤ j.

Let us for the moment assume that we have already established the claim. Clearly, for j = i − 1 the condition (28) is satisfied with s_{j+1} = I, in which case we have a_{s_{j+1}}^{(j+1)} = a_{I}^{(i)} = a_{I} and b_{s_{j+1}}^{(j+1)} = b_{I}^{(i)} = b_{I}. Then, by iterating the assertion of our claim, we will find that (29) is satisfied for h = 1 and some s_{1}. Using this and (27) we obtain

f(a_{s_{1}}^{(1)}) ≤ f(a_{I}) ≤ b_{I} ≤ b_{s_{1}}^{(1)}.

However, this inequality contradicts the fact that T_{1} obeys the ladder condition (14) with i = 1 and s = s_{1}. Hence, inequality (24) must be actually true.

For the proof of the claim, we distinguish between four cases:

(i) σ(j) ≥ j and a_{1}^{(j)} ≤ a_{I}; (ii) σ(j) < j and a_{−σ(j)+j+1}^{(j)} ≤ a_{I};

(iii) σ(j) ≥ j and a_{1}^{(j)} > a_{I}; (iv) σ(j) < j and a_{−σ(j)+j+1}^{(j)} > a_{I}.

Case σ(j) ≥ j and a_{1}^{(j)} ≤ a_{I}. Because we are assuming E_{1}^{(1)} > a_{I}, we have a_{I} ≤ E_{1}^{(1)} − 1 = Ẽ_{1}^{(1)} ≤ Ẽ_{1}^{(j)}. Therefore it is impossible that a_{1}^{(j)} = Ẽ_{1}^{(j)} + 1 (by one of our conventional assignments), and hence a_{1}^{(j)} does indeed exist, i.e., k_{j} ≥ 1 (cf. (13) with i replaced by j).

Let s_{j} be maximal such that a_{s_{j}}^{(j)} ≤ a_{I}. By the above we have 1 ≤ s_{j} ≤ k_{j}. Therefore b_{s_{j}}^{(j)} exists. If b_{s_{j}}^{(j)} < b_{I}, then we have a_{s_{j+1}}^{(j+1)} ≤ a_{I} < a_{s_{j}+1}^{(j)} and b_{s_{j}}^{(j)} <

b_{I} ≤ b_{s_{j+1}}^{(j+1)}. But that means that (a_{s_{j}+1}^{(j)}, b_{s_{j+1}}^{(j+1)}) is a crossing point of T_{j} and T_{j+1} (cf. (15c)–(15e)) with larger x-coordinate than (a_{I}, d_{J}), contradicting the maximality of the crossing point (a_{I}, d_{J}). Hence, we actually have b_{s_{j}}^{(j)} ≥ b_{I}, and thus (29) holds with h = j and with s_{j} as above.

2 It is at the corresponding place where the inaccuracy in [17] occurs. On p. 1036 the inequality chain a_{I} ≥ x_{s} ≥ ⋯ ≥ u_{t} has to be replaced by a_{I} ≥ x_{s}, …, a_{i} ≥ u_{t}, and the inequality chain b_{I} ≤ y_{s} ≤ ⋯ ≤ v_{t} has to be replaced by b_{I} ≤ y_{s}, …, b_{I} ≤ v_{t}.

Case σ(j) < j and a_{−σ(j)+j+1}^{(j)} ≤ a_{I}. The arguments from the above

case apply verbatim if one replaces a_{1}^{(j)} by a_{−σ(j)+j+1}^{(j)} everywhere.

Case σ(j) ≥ j and a_{1}^{(j)} > a_{I}. We show that this case actually cannot occur. Because of (7), we have f(A_{1}^{(1)}) ≤ f(a_{I}), and therefore

b_{0}^{(j)} = Ã_{2}^{(σ(j))} − 1 ≤ Ã_{2}^{(1)} − 1 = A_{2}^{(1)} < f(A_{1}^{(1)}) ≤ f(a_{I}) ≤ b_{I} ≤ b_{s_{j+1}}^{(j+1)},

the two last inequalities being due to (27) and (28). On the other hand, we have a_{s_{j+1}}^{(j+1)} ≤ a_{I} < a_{1}^{(j)}. This means that (a_{1}^{(j)}, b_{s_{j+1}}^{(j+1)}) is a crossing point of T_{j} and T_{j+1} with larger x-coordinate than (a_{I}, d_{J}), which contradicts again the maximality of (a_{I}, d_{J}).

Case σ(j) < j and a_{−σ(j)+j+1}^{(j)} > a_{I}. If b_{−σ(j)+j}^{(j)} < b_{I}, then we have

a_{s_{j+1}}^{(j+1)} ≤ a_{I} < a_{−σ(j)+j+1}^{(j)} and b_{−σ(j)+j}^{(j)} < b_{I} ≤ b_{s_{j+1}}^{(j+1)}. This means that

(a_{−σ(j)+j+1}^{(j)}, b_{s_{j+1}}^{(j+1)}) is a crossing point of T_{j} and T_{j+1} with larger x-coordinate

than (a_{I}, d_{J}), a contradiction. Therefore we actually have b_{−σ(j)+j}^{(j)} ≥ b_{I}.

If a_{−σ(j)+j}^{(j)} = Ã_{1}^{(σ(j))} − 1 ≤ a_{I} then (29) is satisfied with h = j and

s_{j} = −σ(j) + j. If, on the other hand, a_{−σ(j)+j}^{(j)} > a_{I}, then of course (29) cannot be satisfied for h = j and any legal s_{j}. However, we can show that it is satisfied for some smaller h.

Let us pause for a moment and summarize the conditions that we are encountering in the current case:

σ(j) < j, a_{−σ(j)+j}^{(j)} > a_{I} and b_{−σ(j)+j}^{(j)} ≥ b_{I}.  (30)

Clearly, there is a maximal s with s ≤ σ(j) ≤ σ(s). We are going to show that we can either find an h ≤ j and a legal s_{h} such that (29) is satisfied, or we find an index ℓ < j such that (30) is satisfied with j replaced by ℓ (in which case we repeat the subsequent arguments), or we can construct a sequence of pairs (a_{r_{ℓ}}^{(ℓ)}, b_{r_{ℓ}}^{(ℓ)}), r_{ℓ} ∈ {1, 2, …, k_{ℓ}} for ℓ ∈ {s + 1, s + 2, …, j − 1} that satisfy

a_{r_{ℓ+1}}^{(ℓ+1)} ≥ a_{r_{ℓ}}^{(ℓ)} > a_{I} and b_{r_{ℓ}}^{(ℓ)} ≥ b_{r_{ℓ+1}}^{(ℓ+1)} ≥ b_{I},  (31)

where, in order that (31) makes sense for ℓ = j − 1, we set r_{j} = −σ(j) + j.

However, if we have found such pairs for ℓ ∈ {s + 1, s + 2, …, j − 1}, then we have

a_{I} < a_{r_{s+1}}^{(s+1)} < a_{−σ(j)+j}^{(j)} + 1 = Ã_{1}^{(σ(j))}

≤ Ã_{1}^{(σ(j))} + σ(j) − s ≤ Ã_{1}^{(σ(s))} + σ(s) − s ≤ a_{1}^{(s)} and

b_{0}^{(s)} = Ã_{2}^{(σ(s))} − 1 ≤ Ã_{2}^{(σ(j))} − 1 < b_{−σ(j)+j}^{(j)} = b_{r_{j}}^{(j)} ≤ b_{r_{s+1}}^{(s+1)}.

This means that (a_{1}^{(s)}, b_{r_{s+1}}^{(s+1)}) is a crossing point of T_{s} and T_{s+1} with larger x-coordinate than (a_{I}, d_{J}), contradicting again the maximality of (a_{I}, d_{J}). Therefore we will actually find an h ≤ j such that (29) is satisfied.

We prove our claim in (31) by a reverse induction on ℓ. (The last two inequalities in (30) guarantee that the induction can be started.) Suppose that we have already found indices r_{j−1}, r_{j−2}, …, r_{ℓ+1} satisfying (31). Then we distinguish between the two cases σ(ℓ) ≥ ℓ and σ(ℓ) < ℓ.

First let us consider the case σ(ℓ) ≥ ℓ. If a_{1}^{(ℓ)} > a_{r_{ℓ+1}}^{(ℓ+1)}, then we have a_{I} < a_{r_{ℓ+1}}^{(ℓ+1)} < a_{1}^{(ℓ)} and, if in addition ℓ ≥ σ(j), we have

b_{0}^{(ℓ)} = Ã_{2}^{(σ(ℓ))} − 1 ≤ Ã_{2}^{(σ(j))} − 1 < b_{−σ(j)+j}^{(j)} = b_{r_{j}}^{(j)} ≤ b_{r_{ℓ+1}}^{(ℓ+1)},

where the first inequality is due to σ(ℓ) ≥ ℓ ≥ σ(j). This means that (a_{1}^{(ℓ)}, b_{r_{ℓ+1}}^{(ℓ+1)}) is a crossing point of T_{ℓ} and T_{ℓ+1} with larger x-coordinate than (a_{I}, d_{J}), again a contradiction.

If ℓ < σ(j), we can also prove that b_{0}^{(ℓ)} < b_{r_{ℓ+1}}^{(ℓ+1)}, giving the same contradiction. However, this time we must argue differently. Since ℓ > s, all of σ(ℓ + 1), σ(ℓ + 2), …, σ(σ(j)) must be less than σ(j). For that reason, because of σ(ℓ) ≥ ℓ and the pigeon hole principle, there must be a t ∈ {ℓ + 1, ℓ + 2, …, σ(j)} with σ(t) < σ(ℓ). Then, by (31), we obtain

b_{0}^{(ℓ)} = Ã_{2}^{(σ(ℓ))} − 1 ≤ Ã_{2}^{(σ(t))} − 1 < b_{r_{t}}^{(t)} ≤ b_{r_{ℓ+1}}^{(ℓ+1)}.

Hence, we actually have a_{1}^{(ℓ)} ≤ a_{r_{ℓ+1}}^{(ℓ+1)}.

We also have Ẽ_{1}^{(s)} ≥ Ã_{1}^{(σ(s))} + σ(s) − s − 1, because otherwise there would not be any two-rowed array T_{s} (see (13) with i = s), i.e., the family T of two-rowed arrays that we are considering would not exist, which is absurd. This implies the inequality chain

Ẽ_{1}^{(ℓ)} ≥ Ẽ_{1}^{(s)} ≥ Ã_{1}^{(σ(s))} + σ(s) − s − 1

≥ Ã_{1}^{(σ(j))} + σ(j) − s − 1 ≥ Ã_{1}^{(σ(j))} − 1 = a_{−σ(j)+j}^{(j)} ≥ a_{r_{ℓ+1}}^{(ℓ+1)}.

Therefore it is impossible that a_{1}^{(ℓ)} = Ẽ_{1}^{(ℓ)} + 1 (by one of our conventional assignments), and hence a_{1}^{(ℓ)} does indeed exist, i.e., k_{ℓ} ≥ 1.

Now let r_{ℓ} be maximal, such that a_{r_{ℓ}}^{(ℓ)} ≤ a_{r_{ℓ+1}}^{(ℓ+1)}. By the above we have 1 ≤ r_{ℓ} ≤ k_{ℓ}. If b_{r_{ℓ}}^{(ℓ)} < b_{r_{ℓ+1}}^{(ℓ+1)}, then we have a_{I} < a_{r_{ℓ+1}}^{(ℓ+1)} < a_{r_{ℓ}+1}^{(ℓ)} and b_{r_{ℓ}}^{(ℓ)} < b_{r_{ℓ+1}}^{(ℓ+1)}. This means that (a_{r_{ℓ}+1}^{(ℓ)}, b_{r_{ℓ+1}}^{(ℓ+1)}) is a crossing point of T_{ℓ} and T_{ℓ+1} with larger x-coordinate than (a_{I}, d_{J}), which is once more a contradiction.

Hence, we actually have b_{r_{ℓ}}^{(ℓ)} ≥ b_{r_{ℓ+1}}^{(ℓ+1)}. Therefore, if a_{r_{ℓ}}^{(ℓ)} ≤ a_{I} then (29) is satisfied with h = ℓ and s_{h} = r_{ℓ}, and otherwise, if a_{r_{ℓ}}^{(ℓ)} > a_{I} then (31) is satisfied.

As a last subcase, we must consider σ(ℓ) < ℓ. Again we have to distinguish between two cases: if a_{−σ(ℓ)+ℓ+1}^{(ℓ)} ≤ a_{r_{ℓ+1}}^{(ℓ+1)}, we argue exactly as in the above

case where σ(ℓ) ≥ ℓ and a_{1}^{(ℓ)} ≤ a_{r_{ℓ+1}}^{(ℓ+1)}. (We just have to replace a_{1}^{(ℓ)} by a_{−σ(ℓ)+ℓ+1}^{(ℓ)} there.) Otherwise, if a_{−σ(ℓ)+ℓ+1}^{(ℓ)} > a_{r_{ℓ+1}}^{(ℓ+1)}, we get b_{−σ(ℓ)+ℓ}^{(ℓ)} ≥ b_{r_{ℓ+1}}^{(ℓ+1)},

because otherwise a_{I} < a_{r_{ℓ+1}}^{(ℓ+1)} < a_{−σ(ℓ)+ℓ+1}^{(ℓ)} and b_{−σ(ℓ)+ℓ}^{(ℓ)} < b_{r_{ℓ+1}}^{(ℓ+1)}, and thus

(a_{−σ(ℓ)+ℓ+1}^{(ℓ)}, b_{r_{ℓ+1}}^{(ℓ+1)}) is a crossing point with larger x-coordinate than (a_{I}, d_{J}), again a contradiction.

Now, if a_{−σ(ℓ)+ℓ}^{(ℓ)} ≤ a_{I} then (29) is satisfied with h = ℓ and s_{h} = −σ(ℓ) + ℓ.

On the other hand, if a_{−σ(ℓ)+ℓ}^{(ℓ)} > a_{I} then (30) is satisfied with j replaced by ℓ. In addition we have ℓ < j. Consequently, we repeat the arguments subsequent to (30) with j replaced by ℓ. In that manner, we may possibly perform several such iterations. However, these iterations must come to an end because σ(1) ≥ 1, and, hence, the conditions (30) cannot be satisfied for j = 1.

Proof of (25). We proceed similarly. We first observe that we must have a_{I} ≤ c_{J+1}, because otherwise we would have c_{J+1} < a_{I} and by (15d) also b_{I−1} < d_{J} < d_{J+1}, which means that (a_{I}, d_{J+1}) is a crossing point of T_{i} and T_{i+1}, contradicting the maximality of (a_{I}, d_{J}). Now we distinguish again between the same two cases as in the proof of (24). If E_{1}^{(1)} ≤ a_{I}, then we have the following chain of inequalities:

b_{I−i+r} ≤ b_{I−1} + 1 − i + r ≤ d_{J} − i + r ≤ d_{J+r} − i

≤ Ẽ_{2}^{(i+1)} − i = E_{2}^{(i+1)} ≤ E_{2}^{(1)} < f(E_{1}^{(1)}) ≤ f(a_{I}) ≤ f(c_{J+1}) ≤ f(c_{J+r}), (32)

as required. (The second inequality in (32) follows from the fact that the rows in (23b) are strictly increasing.) If on the other hand we have E_{1}^{(1)} > a_{I}, then let us assume for the purpose of contradiction that (25) does not hold. This implies

f(a_{I}) ≤ f(c_{J+r}) ≤ b_{I−i+r} < b_{I}.

Again, this simply means that the point (a_{I}, b_{I}) lies outside the ladder region L defined by (2). We are thus in the same situation as in the above proof of (24), which, in the long run, led to a contradiction.

This completes the proof of the theorem.

5 Enumeration of two-rowed arrays

The entries in the determinant in (10) and (11) are all generating functions ∑ z^{|T |/2} for two-rowed arrays T. Hence, we have to say how these can be computed. Of course, a “nice” formula cannot be expected in general. There are only two cases in which “nice” formulas exist, the case of the trivial ladder (i.e., f(x) ≡ b+1; see (37)), and the case of a ladder determined by a diagonal boundary (i.e., f(x) = x + D + 1, for some positive integer D; see (39)). In all other cases one has to be satisfied with answers of recursive nature.

We will describe two approaches to attack this problem. The first leads to an extension of a formula due to Kulkarni [20] (see also [17, Prop. 4]) for the generating function of lattice paths with given starting and end points in a one-sided ladder region. The second extends the alternative to Kulkarni’s formula that was proposed in [17, Prop. 5–7]. The first approach has the advantage of producing a formula (see Proposition 1 below) that can be compactly stated. The second approach is always at least as efficient as the first, but is by far superior for ladder regions of a particular kind. This is discussed in more detail after the proof of Proposition 4.

Proposition 1. Let f be a weakly increasing function f : [0, a] → [1, b + 1] corresponding to a ladder region L by means of (2), as before. Extend f to all integers by setting f(x) := α_{2} for x < 0 and f(x) := ε_{2} + 1 for x > a. Let α_{1} − 1 < s_{k−1} < ⋯ < s_{1} < ε_{1} be a partition of the (integer) interval [α_{1} − 1, ε_{1}] such that f is constant on each subinterval [s_{i} + 1, s_{i−1}], i = k, k − 1, …, 1, with s_{k} := α_{1} − 1 and s_{0} := ε_{1}. Then the generating function ∑ z^{|T |/2} for all two-rowed arrays T of the form (6) and satisfying (5) is given by

GF(TA(l; (α_{1}, α_{2}), (ε_{1}, ε_{2}); f, d); z^{|.|/2})

= _{∑_{e+d≥f≥0} ; e_{k}−f_{k}=l}z^{e_{k}} ∏_{i=1}^{k} \binom{s_{i−1} − s_{i}}{e_{i} − e_{i−1}}\binom{f′(s_{i−1}) − f′(s_{i})}{f_{i} − f_{i−1}}, (33)

where e = (e_{1}, e_{2}, …, e_{k}) and f = (f_{1}, f_{2}, …, f_{k}), where, by definition, e_{0} = f_{0} = 0, where e + d ≥ f ≥ 0 means e_{i} + d ≥ f_{i} ≥ 0, i = 1, 2, …, k, and where f′(x) agrees with f(x) for α_{1} ≤ x < ε_{1}, but where f′(α_{1} − 1) = α_{2} and f′(ε_{1}) = ε_{2} + 1. (All other values of f′ are not needed for the formula (33)).

Proof. Let T be a two-rowed array in TA(l; (α_{1}, α_{2}), (ε_{1}, ε_{2}); f, d), represented as in (6). Suppose that there are e_{i} entries in the first row of T that are larger than s_{i}, and that there are f_{i} entries in the second row of T that are larger than or equal to f(s_{i}), i = 1, 2, …, k. Equivalently, we have

ε_{1} = s_{0} ≥ a_{1} > ⋯ > a_{e_{1}} > s_{1} ≥ a_{e_{1}+1} > ⋯ > a_{e_{2}} > s_{2} ≥ ⋯ > s_{k−1} ≥ a_{e_{k−1}+1} > ⋯ > a_{e_{k}} > s_{k} = α_{1} − 1, (34) and

f′(s_{0}) = ε_{2} + 1 > b_{1} > ⋯ > b_{f_{1}} ≥ f(s_{1}) > b_{f_{1}+1} > ⋯ > b_{f_{2}} ≥ f(s_{2}) > ⋯ ≥ f(s_{k−1}) > b_{f_{k−1}+1} > ⋯ > b_{f_{k}} ≥ f′(s_{k}) = α_{2}. (35)

In particular, we have e_{k} −f_{k} = l. From (5) it is immediate that we must have e_{i} +d ≥ f_{i} ≥ 0. Conversely, given integer vectors e and f with e_{i} +d ≥ f_{i} ≥ 0 and e_{k} − f_{k} = l, by (34) and (35) there are

∏_{i=1}^{k} \binom{s_{i−1} − s_{i}}{e_{i} − e_{i−1}}\binom{f(s_{i−1}) − f(s_{i})}{f_{i} − f_{i−1}}

possible choices for the entries a_{i} and b_{i}, i = 1, 2, …, in the first and second row of a two-rowed array which satisfies (34) and (35), and thus (5). This establishes (33). ⊓ ⊔

Remark 4. If in Proposition 1 we set l = d = 0, then we recover Kulkarni’s formula [20, Theorem 4] (see also [17, Prop. 4]), because the two-rowed arrays in TA(0; (α_{1}, α_{2}), (ε_{1}, ε_{2}); f, 0) can be interpreted as lattice paths with starting point (α_{1}, α_{2} − 1) and end point (ε_{1} + 1, ε_{2}) which stay in the ladder region defined by f.

Now we describe the announced alternative method to compute the generating function ∑ z^{|T |/2} for two-rowed arrays T of the form (6) which satisfy (5). For sake of convenience, for A = (α_{1}, α_{2}) and E = (ε_{1}, ε_{2}) as before, α_{1} ≤ ε_{1}, we introduce the set

TA^{∗}(l; A, E; f, d) = TA(l; A, E; f, d) \ TA(l; A + (1, 0), E; f, d),  (36)

which is simply the set of those two-rowed arrays of the given form whose first entry in the first row equals α_{1}.

This second method is based on the simple facts that are summarized in Propositions 2–4. The propositions extend in turn Propositions 5–7 in [17]. In the following, all binomial coefficients \binom{n}{k} are understood to be equal to zero if n is negative and k is positive.

Proposition 2. Let L be the trivial ladder determined by the function f(x) ≡ b + 1 by means of (2). Let A = (α_{1}, α_{2}) and E = (ε_{1}, ε_{2}) be lattice points and l and d arbitrary integers. Then we have

GF (TA(l; A, E; f, d); z^{|.|/2}) = ∑_{k} \binom{ε_{1} − α_{1} + 1}{k + l}\binom{ε_{2} − α_{2} + 1}{k}z^{k+l/2},

(37)

and if α_{1} ≤ ε_{1} we have

GF (TA^{∗}(l; A, E; f, d); z^{|.|/2}) = ∑_{k} \binom{ε_{1} − α_{1}}{k + l − 1}\binom{ε_{2} − α_{2} + 1}{k}z^{k+l/2}. (38)

Proposition 3. Let L_{D} be a “diagonal” ladder determined by the function f(x) = x + D + 1 for an integer D by means of (2). Let d be a nonnegative integer and l an integer such that l+d ≥ 0. Let A = (α_{1}, α_{2}) and E = (ε_{1}, ε_{2}) be lattice points such that α_{1} + D + 1 + l + d ≥ α_{2} and ε_{1} + D + 1 + d ≥ ε_{2}. Then we have

GF (TA(l; A, E; f, d); z^{|.|/2}) = ∑_{k} (\binom{ε_{1} − α_{1} + 1}{k + l}\binom{ε_{2} − α_{2} + 1}{k}

− \binom{ε_{1} − α_{2} + D + 1}{k − d − 1}\binom{ε_{2} − α_{1} − D + 1}{k + l + d + 1})z^{k+l/2}, (39)

and if α_{1} ≤ ε_{1} we have

GF (TA^{∗}(l; A, E; f, d); z^{|.|/2}) = ∑_{k} (\binom{ε_{1} − α_{1}}{k + l − 1}\binom{ε_{2} − α_{2} + 1}{k}

− \binom{ε_{1} − α_{2} + D + 1}{k − d − 1}\binom{ε_{2} − α_{1} − D}{k + l + d})z^{k+l/2}. (40)

Proof of Propositions 2 and 3. Identities (37) and (38) are immediate from the definitions.

To prove identity (41), we note that the number of two-rowed arrays

\begin{aligned}α_{1} ≤ & a_{−l+1} & a_{−l+2} & … & a_{0} & a_{1} & … & a_{k} & ≤ ε_{1} \\ α_{2} ≤ & & & & & b_{1} & … & b_{k} & ≤ ε_{2} \end{aligned}  (41a)

that obey

b_{i} < a_{i+d} + D + 1, i = 1, 2, …, k,  (41b)

is the number of all two-rowed arrays of the form (41a) minus those that violate the condition (41b). Clearly, the generating function for the former two-rowed arrays is given by the first term in the sum on the right hand side of (39). We claim that the two-rowed arrays of the form (41a) that violate (41b) are in one-to-one correspondence with two-rowed arrays of the form

\begin{aligned}α_{2} − D ≤ & & & & & c_{1} & … & c_{k−d−1} & ≤ ε_{1} \\ α_{1} + D ≤ & d_{−l−2d−1} & d_{−l−2d} & … & d_{0} & d_{1} & … & d_{k−d−1} & ≤ ε_{2}. \end{aligned}  (42)

(In particular, if k ≤ d then there is no two-rowed array of the form (42), in agreement with the fact that there cannot be any two-rowed array of the form (41a) violating (41b) in that case.) The generating function for the two-rowed arrays in (42) is

∑_{k} \binom{ε_{1} − α_{2} + D + 1}{k − d − 1}\binom{ε_{2} − α_{1} − D + 1}{k + l + d + 1}z^{k+l/2},

which is exactly the negative of the second term on the right-hand side of (39). This would prove (39). So it remains to construct the one-to-one correspondence.

The correspondence that we are going to describe is gleaned from [18], see also [15, Sec. 13.4] and [16]. Take a two-rowed array of the form (41a) that violates condition (41b), i.e., there is an index i such that b_{i} ≥ a_{i+d} + D + 1. Let I be the largest integer with this property. Then map this two-rowed array to

\begin{aligned}α_{2}−D ≤ & (b_{1}−D) & . . . . . . . . . . . . . & (b_{I−1}−D) & a_{I+d+1} & … & a_{k} & ≤ ε_{1} \\ α_{1}+D ≤ & (a_{−l+1}+D) & . . . . . . . . & (a_{I+d}+D) & b_{I} & . . . . . . . . . . . . . . . . . . . . . & b_{k} & ≤ ε_{2}. \end{aligned}

Note that both rows are strictly increasing because of b_{I−1} − D ≤ b_{I+1} − D − 2 < a_{I+d+1}. If I = 1, we have to check in addition that α_{2} − D ≤ a_{d+2}, which is indeed the case, because

a_{d+2} ≥ a_{d+1} + 1 ≥ ⋯ ≥ a_{−l+1} + 1 + l + d ≥ α_{1} + 1 + l + d ≥ α_{2} − D.

Similarly, it can be checked that b_{I−1} − D ≤ ε_{1} if I = k − d. It is easy to see that the array is of the form (42).

The inverse of this map is defined in the same way. Take a two-rowed array of the form (42). Let J be the largest integer such that d_{J} ≥ c_{J+d} + D + 1, if existent. If there is no such integer, then let J = −d. We map this two-rowed array to

\begin{aligned}α_{1} ≤ & (d_{−l−2d−1}−D) & . . . . . . . . . . . . . . . . . & (d_{J−1}−D) & c_{J+d+1} & … & c_{k−d−1} & ≤ ε_{1} \\ α_{2} ≤ & (c_{1}+D) & … & (c_{J+d}+D) & d_{J} & . . . . . . . . . . . . . . . . . . . . . & d_{k−d−1} & ≤ ε_{2} \end{aligned}

Since we required l + d ≥ 0 the entry d_{J−1} − D exists even if J = −d. This implies that the two-rowed array we obtained violates condition (41b), since d_{J} ≥ d_{J−1} + 1 = (d_{J−1} − D) + D + 1. As above, it can be checked that both rows are strictly increasing, even in the case J = −d, and that the array is of the correct form.

Equation (40) is an immediate consequence of (39) and the definition (36) of TA^{∗}(l; A, E; f, d). ⊓ ⊔

Proposition 4. Let L be an arbitrary ladder given by a function f by means of (2), let A = (α_{1}, α_{2}), E = (ε_{1}, ε_{2}) be lattice points in L, and let d be a nonnegative integer and l an integer such that l+d ≥ 0. Then for all x ∈ [0, a] such that α_{2} ≤ f(x) ≤ ε_{2} + 1 we have

GF (TA(l; A, E; f, d); z^{|.|/2})
= ∑_{j=x+1}^{ε_{1}} GF (TA(l + d; A, (j − 1, f(x) − 1); f, 0); z^{|.|/2})
· GF (TA^{∗}(−d; (j, f(x)), E; f, d); z^{|.|/2})
+ ∑_{e=0}^{d} GF (TA(l + d − e; A, (ε_{1}, f(x) − 1); f, e); z^{|.|/2})

·\binom{ε_{2} − f(x) + 1}{d − e}z^{(d−e)/2}.  (43)

Proof. We show this recurrence relation by decomposing an array

\begin{aligned}α_{1} ≤ & a_{−l+1} & a_{−l+2} & … & a_{−1} & a_{0} & a_{1} & … & a_{k} & ≤ ε_{1} \\ α_{2} ≤ & & & & & & b_{1} & … & b_{k} & ≤ ε_{2} \end{aligned}  (44)

in TA(l; A, E; f, d) — the generating function of which is the left-hand side of (43) — into two parts. Let I be the smallest integer with b_{I} ≥ f(x), or, if all b_{I} are smaller than f(x), let I = k + 1. Now we have to distinguish between two cases.

If I + d < k + 1, we decompose such an array into the array

\begin{aligned}α_{1} ≤ & a_{−l+1} & a_{−l+2} & … & a_{−1} & a_{0} & a_{1} & … & a_{d+1} & … & a_{I−1+d} & ≤ a_{I+d} − 1 \\ α_{2} ≤ & & & & & & & & b_{1} & … & b_{I−1} & ≤ f(x) − 1 \end{aligned}

in TA(l + d; A, (a_{I+d} − 1, f(x) − 1); f, 0), and the array

\begin{aligned}a_{I+d} ≤ & & & a_{I+d} & … & a_{k} & ≤ ε_{1} \\ f(x) ≤ & b_{I} & … & b_{I+d} & … & b_{k} & ≤ ε_{2} \end{aligned}

in TA^{∗}(−d; (a_{I+d}, f(x)), E; f, d). Clearly, this is a pair of two-rowed arrays enumerated by the first sum in the right hand side of (43), with the summation index j equal to a_{I+d}.

If I + d ≥ k + 1, we decompose (44) into the array

\begin{aligned}α_{1} ≤ & a_{−l+1} & a_{−l+2} & … & a_{−1} & a_{0} & a_{1} & … & a_{k−I+2} & … & a_{k} & ≤ ε_{1} \\ α_{2} ≤ & & & & & & & & b_{1} & … & b_{I−1} & ≤ f(x) − 1 \end{aligned}

in TA(l − I + k + 1; A, (ε_{1}, f(x) − 1); f, d + I − k − 1), and a single row

f(x) ≤ b_{I} … b_{k} ≤ ε_{2}.

Note that, if I = k + 1, this row is empty. These pairs are enumerated by the second sum on the right hand side of (43), with the summation index e equal to d + I − k − 1. ⊓ ⊔

Now, here is the second method for determining GF(TA(l; (α_{1}, α_{2}), (ε_{1}, ε_{2}); f, d)); z^{|.|/2}) for any given ladder L of the form (2), with points A = (α_{1}, α_{2}) and E = (ε_{1}, ε_{2}) located inside L: partition the border of L, i.e., the set of points {(x, f(x)) : x ∈ [0, a]} into horizontal and diagonal pieces, say L^{1}, L^{2}, …, L^{m}, where L^{i} = {(x, f(x)) : x_{i−1} < x ≤ x_{i}}, for some −1 = x_{0} < x_{1} < x_{2} < ⋯ < x_{m} = a, each L^{i} being either horizontal or diagonal. Then apply the recurrence (43) in succession with x = x_{m−1}, x_{m−2}, …, x_{1} and use (37)–(40) to compute all the occurring generating functions.

To give an example, in the case of the ladder of Figure 2 we would choose m = 3, x_{1} = 3, x_{2} = 7, x_{3} = 13, and the resulting formula reads

GF (TA(l; A, E; f, d); z^{|.|/2}) = ∑_{j=8}^{ε_{1}} ∑_{k≥0} z^{k−d/2}\binom{ε_{1} − j}{k − d − 1}\binom{ε_{2} − 12}{k}

· ( ∑_{i=4}^{j−1} ∑_{k_{1},k_{2}≥0} z^{k_{1}+k_{2}+(l+d)/2}\binom{i − α_{1}}{k_{1} + l + d}\binom{7 − α_{2}}{k_{1}}

· (\binom{j − i − 1}{k_{2} − 1}\binom{6}{k_{2}} − \binom{7 − i}{k_{2}}\binom{j − 2}{k_{2} − 1})

+ ∑_{k_{1}≥0} z^{k_{1}+(l+d)/2}\binom{j − α_{1}}{k_{1} + l + d}\binom{7 − α_{2}}{k_{1}})

+ ∑_{e=0}^{d}z^{(d−e)/2}\binom{ε_{2} − 12}{d − e}

· ( ∑_{i=4}^{ε_{1}} ∑_{k_{1},k_{2}≥0} z^{k_{1}+k_{2}+(l+d−e)/2}\binom{i − α_{1}}{k_{1} + l + d}\binom{7 − α_{2}}{k_{1}}

· (\binom{ε_{1} − i}{k_{2} − e − 1}\binom{6}{k_{2}} − \binom{7 − i}{k_{2}}\binom{ε_{1} − 1}{k_{2} − e − 1})

+ ∑_{f=0}^{e} ∑_{k≥0} z^{k+(l+d+e)/2−f} \binom{ε_{1} − α_{1} + 1}{k + l + d − f}\binom{7 − α_{2}}{k}\binom{6}{e − f}). (45)

If L consists of not too many pieces, both methods are feasible methods, see our Example in Section 3. Both methods yield (2m − 1)-fold sums if the partition of the border consists of horizontal pieces throughout. However, the second method is by far superior in case of long diagonal portions in the border of L, since then Kulkarni’s formula involves a lot more summations. For example, when we implemented formula (45) (in Mathematica) it was by a factor of 40.000 (!) faster than the corresponding implementation of formula (33). (Indeed, the “simplicity” of the formula (33) in comparison to (45) is deceptive, as (33) involves an 11-fold summation in that case, whereas (45) has only 3-fold, 4-fold, and 5-fold sums.) Of course, in the worst case, when L consists of 1-point pieces throughout, both methods are nothing else than plain counting, and therefore useless. For computation in case of such “fractal” boundaries it is more promising to avoid Theorem 2 and instead try to extend the dummy path method in [19] such that it also applies to the enumeration of nonintersecting lattice paths with respect to turns.

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. S. C. Billey and V. Lakshmibai, Singular loci of Schubert varieties, Birkhäuser, Boston, 2000.

4. W. Bruns and J. Herzog, On the computation of a-invariants, Manuscripta Math. 77 (1992), 201–213.

5. A. Conca, Ladder determinantal rings, J. Pure Appl. Algebra 98 (1995), 119– 134.

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

7. S. R. Ghorpade, Abhyankar’s work on Young tableaux and some recent developments, in: Proc. Conf. on Algebraic Geometry and Its Applications (Purdue Univ., June 1990), Springer–Verlag, New York, 1994, pp. 215–249.

8. S. R. Ghorpade, Young bitableaux, lattice paths and Hilbert functions, J. Statist. Plann. Inference 54 (1996), pp. 55–66.

9. S. R. Ghorpade, Hilbert functions of ladder determinantal varieties, Discrete Math. (to appear).

10. N. Gonciulea and V. Lakshmibai, Singular loci of Schubert varieties and ladder determinantal varieties, J. Algebra 229 (2000), 463–497.

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

12. C. Krattenthaler, Counting lattice paths with a linear boundary, Part 2: q-ballot and q-Catalan numbers, Sitz.ber. d. ÖAW, Math-naturwiss. Klasse 198 (1989), 171–199.

13. C. Krattenthaler, The major counting of nonintersecting lattice paths and generating functions for tableaux, Mem. Amer. Math. Soc. 115, no. 552, Providence, R. I., 1995.

14. C. Krattenthaler, Counting nonintersecting lattice paths with turns, Séminaire Lotharingien Combin. 34 (1995), paper B34i, 17 pp.

15. C. Krattenthaler, The enumeration of lattice paths with respect to their number of turns, in: Advances in Combinatorial Methods and Applications to Probability and Statistics, N. Balakrishnan, ed., Birkhäuser, Boston, 1997, pp. 29–58.

16. C. Krattenthaler and H. Niederhausen, Lattice paths with weighted left turns above a parallel to the diagonal, Congr. Numer. 124 (1997), 73–80.

17. C. Krattenthaler and M. Prohaska, A remarkable formula for counting nonintersecting lattice paths in a ladder with respect to turns, Trans. Amer. Math. Soc. 351 (1999), 1015–1042.

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

19. C. Krattenthaler and S. G. Mohanty, Counting tableaux with row and column bounds, Discrete Math. 139 (1995), 273–286.

20. D. M. Kulkarni, Hilbert polynomial of a certain ladder-determinantal ideal, J. Alg. Combin. 2 (1993), 57–72.

21. D. M. Kulkarni, Counting of paths and coefficients of Hilbert polynomial of a determinantal ideal, Discrete Math. 154 (1996), 141–151.

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

23. M. Rubey, Comment on ‘Counting nonintersecting lattice paths with turns’ by C. Krattenthaler, Séminaire Lotharingien Combin. 34, Comment on paper B34i, 2001.

24. M. Rubey, The h-vector of a ladder determinantal ring cogenerated by 2 × 2 minors is log-concave, preprint, math.RA/0205212.