A remarkable formula for counting nonintersecting

lattice paths in a ladder with respect to turns

C. Krattenthaler^{†} and M. Prohaska

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

Abstract. We prove a formula, conjectured by Conca and Herzog, for the number of all families of nonintersecting lattice paths with certain starting and end points in a region that is bounded by an upper ladder. Thus we are able to compute explicitly the Hilbert series for certain one-sided ladder determinantal rings.

1. Introduction. Recent work of Abhyankar and Kulkarni [1, 2, 18, 19], Bruns, Conca, Herzog, and Trung [3, 5, 6, 10] showed that the computation of the Hilbert series for ladder determinantal rings (see section 3 for the definition) boils down to counting families of n nonintersecting lattice paths with a given total number of turns in a certain laddershaped region. For one-sided ladders, Conca and Herzog [6, last paragraph] conjectured a remarkable formula that reduces the problem to counting the number of all single lattice paths with a given number of turns in the ladder region. We state this conjecture in section 2 (our Theorem 1), and prove it in section 4. The crucial idea in the proof of the conjecture is to encode lattice paths by two-rowed arrays, and then play with these two-rowed arrays. This idea was introduced in [11, 16] and developed to full power in [13, 14, 15]. The implication of Theorem 1 to the computation of Hilbert series of ladder determinantal rings is developed in section 3, see Theorem 2. An extension of Theorem 1 can be found in section 5. In section 6 we address the problem of counting single lattice paths with a given number of turns in a ladder region. Finally, in section 7, we comment on some more general problems and related results.

2. Statement of the formula. To be able to state Conca and Herzog’s conjecture, we have to introduce a few 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 1. We shall frequently abbreviate the fact that a lattice path P goes from A to E by P : A → E.

1991 Mathematics Subject Classification. Primary 05A15, 13C40; Secondary 05A19, 13F50, 13H10.

Key words and phrases. Nonintersecting lattice paths, turns, non-crossing two-rowed arrays, ladder determinantal 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-MAT

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

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

Our lattice paths will be restricted to a certain ladder shaped region, L say, which is described next. Let a, b be positive integers, and let f be a weakly increasing function from [0, a] to [1, b + 1]. Here, by [c, d] we mean the set of all integers ≥ c and ≤ d. Then, by definition,

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

An example with a = 13, b = 15, and f 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, is displayed in Figure 2.

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •_{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}_{Figure 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 lattice points lie in the ladder region L. Similarly, by P_{L}(A → E) (respectively P_{L}^{+}(A → E)) we mean the set of all families (P_{1}, P_{2}, …, P_{n}) of lattice paths (respectively nonintersecting lattice paths), where P_{i} runs from A_{i} to E_{i} and where all the lattice points of P_{i} lie in the ladder region L.

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 1 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. Finally, given any weight function w defined on a set M, by the generating function GF(M; w) we mean ∑_{x∈M} w(x).

Now we are in the position to state Conca and Herzog’s conjecture which becomes a theorem by our proof in section 4.

Theorem 1. Let n, a, b be positive integers. Furthermore, let L be a ladder-shaped region determined by the weakly increasing function f : [0, a] → [1, b + 1] by means of (2.1), with f satisfying f(x) ≥ n for all x, and f(x) = b + 1 for a − n < x ≤ a. Also, let A_{i} = (0, n − i) and E_{i} = (a − n + i, b), i = 1, 2, …, n, be lattice points. Then for the generating function ∑ z^{NE(P)}, where the sum is over all families P = (P_{1}, P_{2}, …, P_{n}) of nonintersecting lattice paths lying in the region L, P_{i} : A_{i} → E_{i}, i = 1, 2, …, n, there holds

GF(P_{L}^{+}(A → E); z^{NE(.)}) = z^{−\binom{n}{2}} det_{1≤s,t≤n} ( GF(P_{L}(A_{t} → E_{s}); z^{NE(.)})).  (2.2)

Remarks. (1) Note that the starting points A_{i} are lined up vertically along the y-axis, top to bottom, while the end points E_{i} are lined up horizontally along the horizontal line y = b, from left to right. The assumptions about the function f are needed to make the enumeration problem non-degenerate, i.e., to guarantee that there exists at least one family of nonintersecting lattice paths in the corresponding region L that connects the starting points A with the end points E.

(2) Conca and Herzog state their conjecture in a different way, but it is easily seen that the above statement is equivalent to theirs. (It is actually simply the translation into generating functions.)

(3) Conca and Herzog proved Theorem 1 for n = 2 (private communication), but for generic n only if f(x) ≡ b + 1 (i.e., if there is no ladder restriction; see [6, next-to-last paragraph]).

(4) The formula (2.2) clearly reduces the problem of enumerating families of nonintersecting lattice paths in the ladder region L with respect to NE-turns to the problem of enumerating single lattice paths in L with respect to NE-turns. We are going to address this problem in section 6.

3. Ladder determinantal rings. As mentioned in the Introduction, the above enumeration problem occurs in the determination of the Hilbert series of certain ladder determinantal rings. Ladder determinantal rings arise for instance in Abhyankar’s study on the singularities of Schubert varieties of flag manifolds. Let us recall the definition of a ladder determinantal ring. 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 3.

( _{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}} )_{Figure 3}

(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}. Thus in particular, the set of all such points for the special matrix in Figure 3 is exactly the ladder region of Figure 2. (It should be apparent from comparison of Figures 3 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.

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, and let I_{n+1}(Y) be the ideal in K[Y] that is generated by all (n+1)×(n+1) minors of Y that contain only nonzero entries. The ideal I_{n+1}(Y) is called a ladder determinantal ideal. The associated ladder determinantal ring is R_{n+1}(Y) := K[Y]/I_{n+1}(Y). (We remark that the definition of ladder is more general in [1, 2, 5, 10]. However, there is in effect no loss of generality since the ladders of [1, 2, 5, 10] can always be reduced to our definition by discarding superfluous 0’s.) Combining results of Abhyankar [1, 2] or Herzog and Trung [10] with our Theorem 1, we are able to give an explicit formula for the Hilbert series of the ladder determinantal ring R_{n+1}(Y) in the case of one-sided ladders, which can be effectively used computationally. By a one-sided ladder, we mean a ladder Y where either Y_{0,0} = X_{0,0} or Y_{b,a} = X_{b,a}. In the first case we call Y a lower ladder, in the second an upper ladder. Thus, the matrix in Figure 3 is an upper ladder. Without loss of generality we state the result for the case of upper ladders only.

Theorem 2. Let Y = (Y_{i,j})_{0≤i≤b, 0≤j≤a} be an upper ladder, 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.1), i.e., Y_{i,j} = X_{i,j} if and only if b − i < f(j). Furthermore, as in Theorem 1 we let A_{i} = (0, n − i) and E_{i} = (a − n + i, b), i = 1, 2, …, n. Then the Hilbert series of the ladder determinantal ring R_{n+1}(Y) = K[Y]/I_{n+1}(Y) equals

∑_{ℓ=0}^{∞} dim_{K} R_{n+1}(Y)_{ℓ} z^{ℓ} = \frac{z^{−\binom{n}{2}} det_{1≤s,t≤n} ( GF(P_{L}(A_{t} → E_{s}); z^{NE(.)}))}{(1 − z)^{(a+b+1)n−2\binom{n}{2}}},  (3.1)

where R_{n+1}(Y)_{ℓ} denotes the homogeneous component of degree ℓ in R_{n+1}(Y).

Proof. We describe two ways to establish the Theorem. One is by use of work of Abhyankar [1] (see also [2]), the other is by use of work of Herzog and Trung [10].

First proof. We follow basically the considerations of Kulkarni [18, 19] (see also [8]). In Theorem (20.10) of [1] (see also Theorem (6.7) in [7]; for our purposes it is sufficient to consider the special case a = (1, 2, …, n | 1, 2, …, n) in these theorems, cf. Example (1) on p. 10 of [10]) Abhyankar proves that the monomials ∏_{(i,j)∈S} X_{b−j,i} form a basis of R_{n+1}(Y), where S ranges over the following multisets:

(1) Y_{b−j,i} = X_{b−j,i} for all (i, j) ∈ S (i.e., (i, j) is a point in the ladder region L associated to Y),

(2) Define a partial order on the points in the plane by

(x_{1}, y_{1}) ≤ (x_{2}, y_{2}) if and only if x_{1} ≤ x_{2} and y_{1} ≥ y_{2},

i.e., if and only if (x_{2}, y_{2}) is located weakly to the right and below of (x_{1}, y_{1}). Then the length of a chain (i_{1}, j_{1}) < (i_{2}, j_{2}) < ⋯ < (i_{k}, j_{k}) of elements of S, in this partial order, is at most n.

An example of such a set S, with a = 13, b = 15, n = 4, the ladder region being the one from Figure 2, is

{(0,1),(0,5),(2,4),(2,6),(3,0),(3,3),(4,4),(4,6),(4,6),(4,6),(4,6),(5,8),(5,8),(6,1),(6,6), (7,2),(7,2),(7,2),(8,6),(8,6),(8,6),(8,10),(8,13),(8,13),(8,15),(9,2),(9,5),(9,8),(9,11),(9,11), (10,2),(10,7),(10,9),(10,13),(10,15),(11,4),(12,4),(12,4),(12,7),(13,10),(13,10),(13,11),(13,15)} (3.2)

A geometric realization of this set is contained in Figure 4, the elements of the multiset S being indicated by bold dots, numbers in parentheses attached to dots indicating multiplicities. (For the moment the reader should ignore the lattice paths in Figure 4.)

By Abhyankar’s theorem, the dimension dim_{K} R_{n+1}(Y)_{ℓ} of the homogeneous component of degree ℓ in R_{n+1}(Y) equals the number of all such multisets S of size ℓ.

Let S be such a multiset. By Viennot’s “light and shadow procedure” with the sun in the top-left corner (see [10, 22, 23]) we can associate a family (P_{1}, P_{2}, …, P_{n}) of n nonintersecting lattice paths to S, P_{i} running from A_{i} = (0, n − i) to E_{i} = (a − n + i, b) and staying in the ladder region L, i = 1, 2, …, n. The result of “light and shadow” when applied to our example in (3.2) is displayed in Figure 4.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•}_{0} _{1} _{2} _{3} _{4} _{5} _{6} _{7} _{8} _{9} _{10} _{11} _{12} _{13}^{4}^{5}^{6}^{7}^{8}^{9}^{10}^{11}^{12}^{13}^{14}^{15}  ^{E_{1}}^{E_{2}}^{E_{3}}^{E_{4}}^{A_{1}}^{A_{2}}^{A_{3}}_{A_{4}}  ^{P_{1}}^{P_{2}}  ^{P_{3}} ^{P_{4}}^{(4)}  ^{(2)}  ^{(2)}^{(2)}^{(3)}^{(3)}  ^{(2)}^{(2)} ∘ ∘ ∘ ∘  ∘ ∘ ∘ ∘ • • • • •  • • • •  • • • •  • • • • • •  • • • • • • • • • • • • Figure 4

Each path P_{i} contains a few (possibly multiple) points of S. However, in each NE-turn of P_{i} there has to be at least one element of S, i = 1, 2, …, n. Therefore, given a family (P_{1}, P_{2}, …, P_{n}) of n nonintersecting lattice paths, P_{i} running from A_{i} to E_{i} and staying in the ladder region L, i = 1, 2, …, n, with a total number of exactly m NE-turns, there are exactly \binom{d+ℓ−m−1}{ℓ−m} multisets S of cardinality ℓ that reduce to (P_{1}, P_{2}, …, P_{n}) under light and shadow, where

d = (a + b + 1)n − 2\binom{n}{2}  (3.3)

is the total number of lattice points on the lattice paths P_{1}, P_{2}, …, P_{n}.

Hence, if we let h_{m} denote the number of all families (P_{1}, P_{2}, …, P_{n}) of n nonintersecting lattice paths, P_{i} running from A_{i} to E_{i} and staying in the ladder region L, i = 1, 2, …, n, with a total number of exactly m NE-turns, we obtain for the Hilbert series,

∑_{ℓ=0}^{∞} dim_{K} R_{n+1}(Y)_{ℓ} z^{ℓ} = ∑_{ℓ=0}^{∞} ( ∑_{m=0}^{ℓ} \binom{d + ℓ − m − 1}{ℓ − m}h_{m})z^{ℓ}

= ∑_{m=0}^{∞} h_{m} ∑_{ℓ=m}^{∞} \binom{d + ℓ − m − 1}{ℓ − m}z^{ℓ}

= ∑_{m=0}^{∞} h_{m}z^{m} ∑_{ℓ=0}^{∞} \binom{d + ℓ − 1}{ℓ}z^{ℓ}

= \frac{∑_{m=0}^{∞} h_{m}z^{m}}{(1 − z)^{d}} .

Now, the generating function ∑_{m=0}^{∞} h_{m}z^{m} is exactly the left-hand side of (2.2). Finally, if we substitute the right-hand side of (2.2) for ∑ h_{m}z^{m} in the last line of the above computation we obtain exactly (3.1).

Second proof. We use results of Herzog and Trung [10]. In section 4 of [10], ladder determinantal rings are introduced and investigated. The situation that we consider here is the special case M = (1, 2, …, n | 1, 2, …, n) of the considerations in [10, section 4] (cf. Example (1) on p. 10 of [10]). It is shown in [10, section 4] that for a suitable term order (order of monomials) the ideal I_{n+1}(Y)^{∗} of leading monomials of I_{n+1}(Y) is generated by square-free monomials. Thus K[Y]/I_{n+1}(Y)^{∗} may be viewed as a Stanley-Reisner ring of a certain simplicial complex Δ. The faces of this simplicial complex Δ are described in Lemma 4.4 of [10]. Namely, translated into a less formal language, the faces are sets (not multisets!) S of points, such that (1) and (2) at the beginning of the first proof hold. (Note that the pictures of [10] have to be reflected in a horizontal line to be conformable to ours.)

As usual, let f_{i} be the number of i-dimensional faces of Δ, i.e., the number of such sets S of cardinality i + 1. By Corollary 4.3 of [10], there holds

dim_{K} R_{n+1}(Y)_{ℓ} = ∑_{i≥0} \binom{ℓ − 1}{i}f_{i}.

As in the first proof, light and shadow can be applied to any such set S. Here, we infer that, given a a family (P_{1}, P_{2}, …, P_{n}) of n nonintersecting lattice paths, P_{i} running from A_{i} to E_{i} and staying in the ladder region L, i = 1, 2, …, n, with a total number of exactly m NEturns, there are exactly \binom{d−m}{i+1−m} sets S of cardinality i + 1 that reduce to (P_{1}, P_{2}, …, P_{n}) under light and shadow, where, as before, d is the total number of lattice points one the lattice paths P_{1}, P_{2}, …, P_{n}, and thus given by (3.3).

Hence, if again h_{m} denotes the number of all families (P_{1}, P_{2}, …, P_{n}) of n nonintersecting lattice paths, P_{i} running from A_{i} to E_{i} and staying in the ladder region L, i = 1, 2, …, n, with a total number of exactly m NE-turns, we obtain for the Hilbert series,

∑_{ℓ=0}^{∞} dim_{K} R_{n+1}(Y)_{ℓ} z^{ℓ} = ∑_{ℓ=0}^{∞} ( ∑_{i≥0} \binom{ℓ − 1}{i}f_{i})z^{ℓ}

= ∑_{ℓ=0}^{∞} ∑_{i≥0} \binom{ℓ − 1}{i}( ∑_{m=0}^{i+1} \binom{d − m}{i + 1 − m}h_{m})z^{ℓ}

= ∑_{m=0}^{∞} h_{m} ∑_{ℓ=0}^{∞} z^{ℓ} ∑_{i≥0} \binom{ℓ − 1}{i}\binom{d − m}{d − i − 1},

and if we sum the inner sum by means of the Vandermonde summation (see e.g. [9, sec. 5.1, (5.27)]),

∑_{ℓ=0}^{∞} dim_{K} R_{n+1}(Y)_{ℓ} z^{ℓ} = ∑_{m=0}^{∞} h_{m} ∑_{ℓ=0}^{∞} z^{ℓ}\binom{d + ℓ − m − 1}{d − 1}

= \frac{∑_{m=0}^{∞} h_{m}z^{m}}{(1 − z)^{d}} .

The rest of the arguments is as in the first proof.

There is also a different argument that uses the shellability of the simplicial complex Δ and the McMullen–Walkup formula (cf. [4, ch. 5, Def. 5.1.11, Cor. 5.1.14] for information on these topics). It avoids computations such as the above ones. Instead, one concludes by properties of facets of Δ alone, that ∑_{m=0}^{∞} h_{m}z^{m}/(1−z)^{d} is the Hilbert series of R_{n+1}(Y), where h_{m} has the same definition as before. These arguments are described in detail in the proof of Theorem 2.4 in [3] (see also [6]). Although, there are no ladders in [3, 6], everything goes through word for word. □

Example. Let Y = (Y_{i,j}) be the matrix of Figure 3. Our formula (3.1) gives for the Hilbert series of R_{5}(Y) = K[Y]/I_{5}(Y), using (6.10) for determining the generating function ∑ z^{NE(P)} for paths P in the corresponding ladder region L of Figure 2,

(1+66z+2211z^{2}+50116z^{3}+864501z^{4}+11928939z^{5}+134672548z^{6}+1260746851z^{7}+9885072697z^{8}+65397111347z^{9}
+367074699427z^{10}+1755530258028z^{11}+7177561951667z^{12}+25154724107849z^{13}+75731455361773z^{14}
+196211938959224z^{15}+438134985445560z^{16}+844176184685583z^{17}+1404677025713433z^{18}
+2019619018869110z^{19}+2509471858669986z^{20}+2694052295102592z^{21}+2497084208937285z^{22}
+1995888618034374z^{23}+1373221471734161z^{24}+811310035353064z^{25}+410273584338378z^{26}
+176833645375538z^{27}+64602317617558z^{28}+19856458222365z^{29}+5082859828078z^{30}+1068090678468z^{31}
+180378873471z^{32}+23682607189z^{33}+2283692607z^{34}+144671625z^{35}+4539150z^{36})/(1−z)^{104}.

4. Proof of Theorem 1.

Lattice paths and two-rowed arrays. For the proof of Theorem 1 we rely on the encoding of lattice paths in terms of two-rowed arrays, which was introduced and used in [11, 13, 14, 15, 16]. Obviously, given the starting and the end point of a path, the NE-turns uniquely determine the path. Suppose that P is a path from A = (α_{1}, α_{2}) to E = (η_{1}, η_{2}) and let the NE-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 α_{1} ≤ a_{1} < a_{2} < ⋯ < a_{k} < η_{1}, and α_{2} < b_{1} < b_{2} < ⋯ < b_{k} ≤ η_{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.1)

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

\begin{aligned}α_{1} ≤ & a_{1} & a_{2} & … & a_{k} & < η_{1} \\ α_{2} < & b_{1} & b_{2} & … & b_{k} & ≤ η_{2} \end{aligned} .  (4.2)

For a given starting point and a given end point, by definition the empty array is the representation for the only path that has no NE-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 & < 6 \\ −1 < & 1 & 3 & 4 & ≤ 6 \end{aligned} .

It is obvious that under this correspondence there holds the following relation for any path P:

NE(P) = \frac{1}{2}(number of entries in the two-rowed array corresponding to P ).  (4.3)

Later, also two-rowed arrays of different “shape” will be considered. But these arrays will also 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.

Nonintersecting two-rowed arrays. Since we consider nonintersecting lattice paths in Theorem 1, we have to figure out what to be nonintersecting means in terms of the corresponding two-rowed arrays. We do this for more general starting and end points then we actually need.

Let P_{1}, P_{2} be two paths, P_{1} : A → E, P_{2} : B → F, where A = (α_{1}, α_{2}), B = (β_{1}, β_{2}), E = (η_{1}, η_{2}), F = (ϕ_{1}, ϕ_{2}) with

α_{1} ≤ β_{1}, α_{2} > β_{2}, η_{1} < ϕ_{1}, η_{2} ≥ ϕ_{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), which will always be true for the cases we consider. Let the array representations of P_{1} and P_{2} be

P_{1} : \begin{aligned}α_{1} ≤ & a_{1} & … & a_{k} & < η_{1} \\ α_{2} < & b_{1} & … & b_{k} & ≤ η_{2} \end{aligned}  (4.4a)

and

P_{2} : \begin{aligned}β_{1} ≤ & c_{1} & … & c_{l} & < ϕ_{1} \\ β_{2} < & d_{1} & … & d_{l} & ≤ ϕ_{2} \end{aligned} ,  (4.4b)

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} := η_{1} and b_{0} := α_{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 5

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 5)

c_{J} ≤ a_{I},  (4.4c)
b_{I−1} ≤ d_{J},  (4.4d)

where

1 ≤ I ≤ k + 1, 1 ≤ J ≤ l.  (4.4e)

Of course, k, l, a_{I}, b_{I−1}, c_{J}, d_{J}, etc., refer to the array representations (4.4a,b) 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 (4.4c,d) to make sense for I = 1 or I = k + 1. Note that S = (a_{I}, d_{J}). Vice versa, if (4.4c,d,e) 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 (4.4c,d,e) characterize the array representations of intersecting pairs of paths. Equivalently, P_{1} and P_{2} are nonintersecting if and only if there does not exist I, J such that (4.4c,d,e) is satisfied for the corresponding two-rowed arrays.

The two-rowed array interpretation of the left-hand side of (2.2). Let P = (P_{1}, P_{2}, …, P_{n}) be an element of P_{L}^{+}(A → B), i.e., P = (P_{1}, P_{2}, …, P_{n}) is a family of nonintersecting lattice paths, P_{i} running from A_{i} to E_{i} and lying in the ladder region L. We encode each lattice path P_{i} by its corresponding two-rowed array, LT_{i} say. So we have to figure out what the above properties of the family P mean in terms of two-rowed arrays. First, observe that it is sufficient to require only P_{1} to lie in the ladder region L since nonintersectingness forces all other paths to lie below P_{1} and thus also to lie in L. Secondly, note that for all i the lattice path P_{i} has to start with i−1 horizontal steps and has to end with i−1 vertical steps, because otherwise (P_{1}, P_{2}, …, P_{n}) would not be nonintersecting. Therefore the first NE-turn of P_{i} must be in the region north-east of (i − 1, n − i + 1), and the last NE-turn of P_{i} must be in the region south-west of (a − n + i − 1, b − i + 1), i = 1, 2, …, n. Hence, by the encoding of lattice paths in terms of two-rowed arrays, the family (P_{1}, P_{2}, …, P_{n}) in P_{L}^{+}(A → E) corresponds to the family (LT_{1}, LT_{2}, …, LT_{n}) of two-rowed arrays,

....._{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....} LT_{1} : LT_{2} : LT_{n} :  0 ≤ n − 1 < 1 ≤ n − 2 < n − 1 ≤ 0 <  < a − n + 1 ≤ b < a − n + 2 ≤ b − 1 < a ≤ b − n + 1 ,  (4.5)

(each representing a two-rowed array, both rows of which containing the same

number of entries and obeying the indicated bounds), such that (l1) LT_{i} and LT_{i+1} are nonintersecting for all i, meaning that if LT_{i} is given by

\begin{aligned}i − 1 ≤ & a_{1} & a_{2} & … & a_{k} & < a − n + i \\ n − i < & b_{1} & b_{2} & … & b_{k} & ≤ b − i + 1 \end{aligned} ,

and if LT_{i+1} is given by

\begin{aligned}i ≤ & c_{1} & c_{2} & … & c_{l} & < a − n + i + 1 \\ n − i − 1 < & d_{1} & d_{2} & … & d_{l} & ≤ b − i \end{aligned} ,

then there is no I, J such that (4.4c,d,e) holds, (l2) the array LT_{1}, say

LT_{1} = \begin{matrix}x_{1} & x_{2} & … & x_{k} \\ y_{1} & y_{2} & … & y_{k} \end{matrix} ,  (4.6a)

“lies in the ladder”, meaning

y_{s} < f(x_{s})  (4.6b)

for all s.

Of course, (4.6b) comes from the definition (2.1) of L.

Summarizing, taking into account (4.3), the left-hand side of (2.2) can be written as

∑ z^{(number of entries in (LT_{1},LT_{2},...,LT_{n}))/2},  (4.7)

where the sum is over all families (LT_{1}, LT_{2}, …, LT_{n}) of two-rowed arrays (4.5) satisfying (l1) and (l2) above.

The two-rowed array interpretation of the right-hand side of (2.2). Now we turn our attention to the right-hand side of (2.2). It is obvious that the right-hand side is the generating function

∑ sgn σ z^{NE(P)},  (4.8)

where the sum is over all pairs (σ, P), with σ being a permutation in 𝔖_{n} (𝔖_{n} is the symmetric group of order n) and P = (P_{1}, P_{2}, …, P_{n}) being a family of lattice paths, P_{i} running from A_{σ(i)} = (0, n − σ(i)) to E_{i} = (a − n + i, b) and lying in the ladder region L. Thus, by encoding each lattice path P_{i} by its corresponding two-rowed array, RT_{i} say, each family (P_{1}, P_{2}, …, P_{n}) of such lattice paths corresponds to the family (RT_{1}, RT_{2}, …, RT_{n}) of two-rowed arrays,

....._{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....} RT_{1} : RT_{2} : RT_{n} :  0 ≤ n − σ(1) < 0 ≤ n − σ(2) < 0 ≤ n − σ(n) <  < a − n + 1 ≤ b < a − n + 2 ≤ b < a ≤ b  (4.9)

with the same permutation σ, where RT_{i} “lies in the ladder region L”, meaning that if

RT_{i} = \begin{matrix}x_{1} & x_{2} & … & x_{k} \\ y_{1} & y_{2} & … & y_{k} \end{matrix} ,  (4.10a)

then

y_{s} < f(x_{s})  (4.10b)

for all s. Of course, (4.10b) comes from the definition (2.1) of L.

However, it is more convenient to represent these two-rowed arrays in a shifted manner. To be precise, the first row of RT_{i} is shifted i − 1 units to the right relative to the second row. Thus we obtain the family

....._{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....} . . . . .  . . . . . . . . . .  . . . . . RT_{1} : RT_{2} : RT_{n} :  0 ≤ n − σ(1) < 0 ≤ n − σ(2) < 0 ≤ n − σ(n) <  < a − n + 1 ≤ b < a − n + 2 ≤ b < a ≤ b . ^{1}  _{1} ^{n−1}  _{n−1} M_{1} M_{2} M_{n} F^{2} F_{n}  B_{2} B_{n}  (4.11)

(For the moment the reader should ignore the vertical dotted lines and the labels M_{1}, F_{2}, M_{2}, B_{2}, etc.) Originally, (4.10a,b) was satisfied for all i. By the shifting procedure, (4.10a,b) transformed into the property that if

RT_{i} = ^{i−1}  _{i−1} … x_{j} x_{j+1} . . . . . . y_{j} y_{j+1} …  (4.12a)

then

y_{s} < f(x_{s+i−1})  (4.12b)

for all s.

There is one point to be made precise. The alert reader will ask, how to understand shifting the first row of RT_{i} in (4.9) by i − 1 units if RT_{i} contains less than i − 1 entries in each row. In this case we simply say that some entries in the “shifted” RT_{i} in (4.11) are empty. To be more specific, divide each RT_{i} in (4.11) into its front part F_{i} (consisting of the first i − 1 entries of the second row of RT_{i}), its back part B_{i} (consisting of the last i − 1 entries of the first row of RT_{i}), and its middle part M_{i} (consisting of the rest), as indicated in (4.11). Then, if the original RT_{i} in (4.9) contained less than i − 1 entries in each row, then the middle part M_{i} will be empty, and the front and back parts F_{i} and B_{i} will contain some empty entries, but both F_{i} and B_{i} will contain the same number of nonempty entries, and hence also the same number of empty entries. By convention, we always assume that the nonempty entries of the front part F_{i} occupy the first of the i − 1 entries, and that the nonempty entries of the back part B_{i} occupy the last of the i − 1 entries. Note that both F_{i} and B_{i} cannot contain an empty entry if M_{i} is nonempty.

Summarizing, taking into account (4.3), the right-hand side of (2.2), which can be rewritten as (4.8), equals

∑ sgn σ z^{(number of entries in (RT_{1},RT_{2},...,RT_{n}))/2},  (4.13)

where the sum is over all pairs (σ, (RT_{1}, RT_{2}, …, RT_{n})), where σ is a permutation in 𝔖_{n}, and where (RT_{1}, RT_{2}, …, RT_{n}) is a family of two-rowed arrays of the form (4.11), with RT_{i} satisfying (4.12a,b) and

(e1) RT_{i}’s front and back parts F_{i} and B_{i} contain the same number of empty entries, but contain no empty entries if RT_{i}’s middle part M_{i} is nonempty. The nonempty entries in F_{i} occupy the first of the i − 1 entries, while the nonempty entries in B_{i} occupy the last of the i − 1 entries.

The front, middle, and back part of (RT_{1}, RT_{2}, …, RT_{n}). We shall frequently refer to the collection (F_{1}, F_{2}, …, F_{n}) of all front parts as the front part of (RT_{1}, RT_{2}, …, RT_{n}), and think of it to be arranged as

\begin{aligned}& & & n−σ(1) \\ & & n−σ(2) & F_{2} \\ n−σ(3) & F_{3} \\ & ... & & ⋮ \\ n−σ(n) & & F_{n} \end{aligned} .  (4.14)

Note that we include the (lower) bounds in the picture. This has several advantages. One immediate advantage is that the information about the permutation σ is thus encoded in the front part. So we do not have to mention it separately all the time. Note that still all the rows in (4.14) are strictly increasing.

Similar conventions are made when we speak of the middle part and the back part of (RT_{1}, RT_{2}, …, RT_{n}). In particular, we think of the middle part as

....._{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....} M_{1} M_{2} M_{n} 0 ≤ ff_{1} < 0 ≤ ff_{2} < 0 ≤ ff_{n} <  < bb_{1} ≤ b < bb_{2} ≤ b < bb_{n} ≤ b ,  (4.15)

where ff_{i} is the right-most nonempty entry in F_{i}, if there is no nonempty entry in F_{i} then ff_{i} = n−σ(i), and where bb_{i} is the left-most nonempty entry in B_{i}, if there is no nonempty entry in B_{i} then bb_{i} = a − n + i.

Finally, we think of the back part to be arranged as

\begin{aligned}a−n+1 \\ B_{2} & a−n+2 \\ B_{3} & & a−n+3 \\ ⋮ & & & ... \\ & B_{n} & & & a \end{aligned} .  (4.16)

Note that similar as with the front part we include the (upper) bounds in the picture. In (4.16) also, all the rows are still strictly increasing.

Recall that in both (4.14) and (4.16) some entries are allowed to be empty, according to the rules in (e1).

Outline of the proof. Our strategy of proving (2.2) consists of showing that the total contribution to the sum (4.13) of the families (RT_{1}, RT_{2}, …, RT_{n}) of two-rowed arrays (4.11) satisfying (4.12a,b) and (e1), that

(b1) either contain an entry ≥ n or an empty entry in the front part,

(b2) or contain two middle parts with consecutive indices, say M_{i} and M_{i+1}, M_{i} represented by

\begin{aligned}0 ≤ & a_{1} & a_{2} & … & a_{k} & < bb_{i} \\ ff_{i} < & b_{1} & b_{2} & … & b_{k} & ≤ b \end{aligned} ,  (4.17a)

and M_{i+1} represented by

\begin{aligned}0 ≤ & c_{1} & c_{2} & … & c_{l} & < bb_{i+1} \\ ff_{i+1} < & d_{1} & d_{2} & … & d_{l} & ≤ b \end{aligned} ,  (4.17b)

that cross (see the remark below explaining this terminology; recall (4.15) for the meaning of ff_{i}, bb_{i}, etc.), meaning that there exist I and J such that

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

and

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

Here, by convention a_{k+1} is defined to be bb_{i} (the first nonempty entry of B_{i}, or a − n + i if there is no nonempty entry in B_{i}; recall (4.15)), b_{0} is defined to be ff_{i} (the last nonempty entry in F_{i}, or n − σ(i) if there is no nonempty entry in F_{i}), c_{0} is defined to be −1, and d_{0} is defined to be ff_{i+1} (the last nonempty entry of F_{i+1}, or n − σ(i + 1) if there is no nonempty entry in F_{i+1}). We call the point (a_{I}, d_{J}) a crossing point of M_{i} and M_{i+1},

(b3) or contain an entry ≤ a − n or an empty entry in the back part, equals 0.

The terminology “crossing of M_{i} and M_{i+1}” comes from the fact that when M_{i} and M_{i+1} are interpreted as paths, the path corresponding to M_{i} running from (0, ff_{i}) to (bb_{i}, b), the one corresponding to M_{i+1} running from (0, ff_{i+1}) to (bb_{i+1}, b), then they would cross if and only if (4.17c,d,e) is satisfied for some I and J (at least if ff_{i} ≥ ff_{i+1}). This is easily derived from (4.4c,d,e) and the observation that, given two nonintersecting lattice paths, by shifting the lower path in direction (−1, 1) one obtains two paths that might touch but do not cross. (The subtle discrepancy between (4.17e) and (4.4e) in the range of J has its explanation in that we will also have to deal with cases in which ff_{i} < ff_{i+1}. In case that ff_{i} ≥ ff_{i+1} the “crossing condition” (4.17c,d,e) cannot hold with J = 0. Hence, in this case (4.17e) and (4.4e) are really the same.)

Suppose that we would have shown that the contribution to (4.13) of these families of two-rowed arrays equals zero. It implies that only those families (RT_{1}, RT_{2}, …, RT_{n}) of two-rowed arrays (4.11) satisfying (4.12a,b) and (e1) contribute to (4.13) that

(g1) contain only nonempty entries, all of them < n, in the front part, (g2) have a “non-crossing” middle part, (g3) and contain only nonempty entries, all of them > a − n, in the back part.

Now, item (g1) says in particular that the last entry in F_{i} is < n. But because of the bounds in (4.11) and the strict increase along rows it is also ≥ n − σ(i) + i − 1. Hence we have i ≤ σ(i) for all i. This implies that σ must be the identity permutation, and that the front part looks like

\begin{aligned}& & & & n−1 \\ & & & n−2 & n−1 \\ & & n−3 & n−2 & n−1 \\ & ... & & & ⋮ \\ 0 & 1 & … & n−2 & n−1 \end{aligned} .  (4.18)

Similarly, item (g3) implies that the back part looks like

\begin{matrix}a−n+1 \\ a−n+1 & a−n+2 \\ a−n+1 & a−n+2 & a−n+3 \\ ⋮ & & & ... \\ a−n+1 & a−n+2 & … & a−1 & a \end{matrix} .  (4.19)

So, front part and back part are uniquely determined. Besides, they impose the following bounds on the middle part,

....._{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....} 0 ≤ n − 1 < 0 ≤ n − 1 < 0 ≤ n − 1 <  < a − n + 1 ≤ b < a − n + 1 ≤ b < a − n + 1 ≤ b M_{1} M_{2} M_{n}  (4.20)

16

It is now easily seen that these families (M_{1}, M_{2}, …, M_{n}) of middle parts are in bijection with the “left-hand side” families (4.5) satisfying (l1) and (l2). Namely, for each M_{i} add i−1 to the entries of the first row and subtract i − 1 from the entries of the second row. Then, obviously, the bounds are shifted into the bounds of (4.5). Moreover, the non-crossing condition (4.17c,d,e) translates into the nonintersectingness condition (4.4c,d,e) (recall the remark concerning the discrepancy between (4.17e) and (4.4e), which disappears in the case of (4.20), since in (4.20) we have ff_{i} = ff_{i+1} = n − 1 for all i), therefore (l1) is satisfied after this addition/subtraction. Also, M_{1} is not changed by the addition/subtraction procedure. And, M_{1} = RT_{1} satisfies (4.12a,b) with i = 1. Therefore (l2) (with LT_{1} replaced by RT_{1} = M_{1}) is satisfied after this addition/subtraction.

Finally note that the factor z^{−\binom{n}{2}} in (2.2) corrects the contribution to z^{(number of entries in (RT_{1},RT_{2},...,RT_{n}))/2} (cf. (4.7) and (4.13)) of the 2\binom{n}{2} discarded entries in the superfluous front and back parts (4.18) and (4.19).

Thus Theorem 1 would be proved.

The involution φ. To show that the contribution of the families (RT_{1}, RT_{2}, …, RT_{n}) of two-rowed arrays (4.11) satisfying (4.12a,b), (e1), and at least one of (b1), (b2), or (b3), equals 0, we construct an involution, φ say, on this set of families that maps a family (RT_{1}, RT_{2}, …, RT_{n}) with associated permutation σ to a family (\overline{RT}_{1}, \overline{RT}_{2}, …, \overline{RT}_{n}) with associated permutation \overline{σ}, such that

(i1) sgn σ = − sgn \overline{σ}, and such that

(i2)

(number of entries in (RT_{1}, RT_{2}, …, RT_{n}))
= (number of entries in (\overline{RT}_{1}, \overline{RT}_{2}, …, \overline{RT}_{n})).

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

So it remains to construct this involution φ. To give an outline, we partition the set of all families (RT_{1}, RT_{2}, …, RT_{n}) that satisfy (4.12a,b), (e1), and one of (b1), (b2), or (b3) into two disjoint subsets, namely B^{1}, the set of all families satisfying (b3), and B^{2}, the set of all families not satisfying (b3) (i.e., satisfying (g3)) but satisfying (b1) or (b2). Then we define involutions φ^{1} and φ^{2} on each of B^{1} and B^{2}, respectively. The involution φ then is simply the union of the two “subinvolutions” φ^{1} and φ^{2}. Basically, φ^{1} is defined by the operation (4.21)/(4.22) (which is inspired by [12, operation φ_{1,0} on pp. 181/182]), and φ^{2} is defined by the operation (4.23)/(4.24) (which is inspired by [13, operation (5.3.6)/(5.3.10); 15, 14, operation (24),(25)/(27)]).

The subinvolution φ^{1}. Let (RT_{1}, RT_{2}, …, RT_{n}) be an element of B^{1}, i.e., it is a family of two-rowed arrays of the form (4.11) satisfying (4.12a,b), (e1), and (b3).

Consider the north-west to south-east diagonals in the back part (i.e., the diagonals running parallel to the right border of the back part, consult (4.16)). Search for the rightmost such diagonal that contains an entry that is empty or smaller than the corresponding entry in the “maximal back part” (4.19) (which must exist by (b3)). Call these entries violation entries. Among the entries of the next diagonal to the right, pick the bottom-most element that has such a violation entry below. (There must be at least one by assumption). Let this entry, a_{I} say, be in B_{i}. Let the violation entry below be c_{I}, say. We then have the following situation,

.....^{.....}^{.....}  . . . . . RT_{i} :  n−σ(i)  F_{i}  M_{i}^{1} M_{i}^{2} … a_{I−1} a_{I} … a−n+i ≤ b 0 ≤  ^{i−1} _{i−1}_{.....}_{.....}_{.....}  . . . . . RT_{i+1} :  n−σ(i+1)  F_{i+1}  M_{i+1}^{1} M_{i+1}^{2}  … c_{I} c_{I+1} … a−n+i+1 ≤ b 0 ≤  ^{i} _{i}  (4.21)

where c_{I} is empty or smaller than the corresponding entry in (4.19). M_{i}^{1} and M_{i}^{2} denote the first and second row of M_{i}, respectively, while M_{i+1}^{1} and M_{i+1}^{2} denote the first and second row of M_{i+1}, respectively. Then, by definition, φ^{1} maps (RT_{1}, …, RT_{i}, RT_{i+1}, …, RT_{n}) to (RT_{1}, …, RT′_{i}, RT′_{i+1}, …, RT_{n}), where

.....^{.....}^{.....}  . . . . . RT′_{i} :  n−σ(i+1)  F_{i+1}  M_{i+1}^{1} M_{i+1}^{2}  … c_{I} a_{I} … a−n+i ≤ b 0 ≤  ^{i−1} _{i−1} _{.....}_{.....}_{.....}  . . . . . RT′_{i+1} :  n−σ(i)  F_{i}  M_{i}^{1} M_{i}^{2}  … a_{I−1} c_{I+1} … a−n+i+1 ≤ b 0 ≤  ^{i} _{i}  (4.22)

It should be observed that the permutation \overline{σ} corresponding to φ^{1}((RT_{1}, …, RT_{n})) = (RT_{1}, …, RT′_{i}, RT′_{i+1}, …, RT_{n}) is \overline{σ} = σ ∘ (i, i + 1). ((i, i + 1) is the transposition interchanging i and i + 1.) We remark that the displays (4.21)/(4.22) should be understood in the sense that a_{I} and c_{I+1} (which are shown to be located inside the back part) could also be the bounds a − n + i and a − n + i + 1, respectively. A similar remark applies to a_{I−1}, which could also be the last entry of M_{i}^{1}, the first row of the middle part M_{i}. However, the operation (4.21)/(4.22) is still well-defined in all these cases.

We must show that φ^{1} is well-defined, i.e., that the new family (RT_{1}, …, RT′_{i}, RT′_{i+1}, …, RT_{n}) again belongs to B^{1}, and that φ^{1} is an involution that satisfies (i1) and (i2).

For being well-defined, we have to check that the rows in RT′_{i} and RT′_{i+1} are still strictly increasing, and that (4.12a,b), (e1), and (b3) are satisfied.

For the first property, we have to show c_{I} < a_{I} (if c_{I} is nonempty, if otherwise nothing is to show) and a_{I−1} < c_{I+1} (if a_{I−1} is nonempty, if otherwise nothing is to show). Assuming that c_{I} is nonempty, the first inequality holds because a_{I} equals its corresponding entry in (4.19), but c_{I} is less than the corresponding entry in (4.19), which is also a_{I} (because entries in (4.19) are the same along columns). The second inequality holds since we must have a_{I+1} = c_{I+1} (again, because entries in (4.19) are the same along columns), and hence a_{I−1} < a_{I} < a_{I+1} ≤ c_{I+1}.

Next we check (e1) for RT′_{i} and RT′_{i+1}. By assumption, a_{I} and c_{I+1} are nonempty. Therefore the correct number of entries will be empty in both RT′_{i} and RT′_{i+1} since it is in RT_{i} and RT_{i+1}.

In order to see that (4.12a,b) holds for RT′_{i} and RT′_{i+1}, observe that, because of the shift of the first rows relative to the second rows when passing from (4.21) to (4.22), entries in RT_{i} and RT_{i+1} related to each other by (4.12b) are still related to each other in RT′_{i} and RT′_{i+1}, except for a_{I} and c_{I+1} and the entries to the right of these in the same rows, together with their related “partners” in the second rows, respectively. But a_{I} and c_{I+1} and all the entries to the right are > a − n (compare with (4.19)), in which case (4.12b) is satisfied automatically because of our assumption f(x) = b + 1 for x > a − n.

Finally, also (b3) is satisfied by the new family. For, either the first entry in the back part of RT′_{i+1} is empty. Or it is nonempty. In this case also a_{I−1} is nonempty and so is smaller than a_{I}. Therefore a_{I−1} (as entry in RT′_{i+1}) is already smaller than its corresponding entry in (4.19) (which is exactly a_{I}). By strict increase along rows this implies that the first entry in the back part of RT′_{i+1} has to be ≤ a − n.

Next we want to establish that φ^{1} is an involution, i.e., that by applying φ^{1} to (RT_{1}, …, RT′_{i}, RT′_{i+1}, …, RT_{n}) one obtains again (RT_{1}, …, RT_{i}, RT_{i+1}, …, RT_{n}). As already observed, a_{I−1} (as entry in RT′_{i+1}) is either empty or smaller than its corresponding entry in (4.19). Furthermore, the diagonal containing a_{I−1} is also the right-most diagonal in the back part of φ^{1}((RT_{1}, …, RT_{n})) that contains such a “violation entry”, because the diagonals to the right were not changed under application of φ^{1}. And, a_{I} (as entry in RT′_{i}) is still the bottom-most entry in the next diagonal to the right that has such a violation entry below, because nothing was changed below or to the right of c_{I+1} under application of φ^{1}. But this exactly means that we come back by applying φ^{1} a second time, as required. Hence, φ^{1} is an involution on B^{1}. That φ^{1} satisfies (i1) is obvious since σ is mapped to \overline{σ} = σ ∘ (i, i + 1), as mentioned before. Also, the numbers of entries in the families of two-rowed arrays are the same before and after application of φ^{1}, which settles (i2).

The subinvolution φ^{2}. Let (RT_{1}, RT_{2}, …, RT_{n}) be an element of B^{2}, i.e., it is a family of two-rowed arrays of the form (4.11) satisfying (4.12a,b), (e1), (g3), and at least one of (b1) or (b2). Recall that (g3) implies that the back part of (RT_{1}, RT_{2}, …, RT_{n}) looks like (4.19). In particular, there are no empty entries in the back part, and hence there are no empty entries in the front part either.

We claim that if (RT_{1}, RT_{2}, …, RT_{n}) satisfies (b1) then it already satisfies (b2). Suppose that there is an entry ≥ n in the front part. Consider the top-most row of the front part, F_{i+1} say, containing such an entry. In particular, the last entry in F_{i+1}, ff_{i+1}, is ≥ n, and the last entry in F_{i}, ff_{i}, is < n. Hence, ff_{i} < ff_{i+1}. But then (0, ff_{i+1}) is a crossing point of M_{i} and M_{i+1} (choose I = 1, J = 0 in (4.17a,b,c,d,e)). So (b2) is satisfied.

Now consider all crossing points of middle parts with consecutive indices. Among these points choose those with maximal x-coordinate, and among all these 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 M_{i} and M_{i+1}. We have the following situation,

. . . . .. . . . .^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....} RT_{i} :  n−σ(i)  F_{i}  B_{i} … a_{I−1} a_{I} . . . . . . b_{I−1} b_{I} …  a−n+i ≤ b 0 ≤  ^{i−1} _{i−1}  . . . . . . . . . ._{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....} RT_{i+1} :  n−σ(i+1) F_{i+1}  B_{i+1} … c_{J} c_{J+1} . . . . . . d_{J−1} d_{J} …  a−n+i+1 ≤ b 0 ≤  ^{i} _{i}  (4.23)

where S = (a_{I}, d_{J}) and where (4.17a,b,c,d,e) is satisfied for the middle parts M_{i} and M_{i+1}. Then, by definition, φ^{2} maps (RT_{1}, …, RT_{i}, RT_{i+1}, …, RT_{n}) to (RT_{1}, …, RT′′_{i}, RT′′_{i+1}, …, RT_{n}), where RT′′_{i} and RT′′_{i+1} are given by

. . . . .. . . . .^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....} RT′′_{i} :  n−σ(i+1) F_{i+1}  B_{i} … c_{J} a_{I} . . . . . . d_{J−1} b_{I} …  a−n+i ≤ b 0 ≤  ^{i−1} _{i−1}  . . . . . . . . . ._{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....} RT′′_{i+1} :  n−σ(i)  F_{i}  B_{i+1} … a_{I−1} c_{J+1} . . . . . . b_{I−1} d_{J} …  a−n+i+1 ≤ b 0 ≤  ^{i} _{i}  (4.24)

Again, observe that the permutation \overline{σ} corresponding to the new family of two-rowed arrays is \overline{σ} = σ ∘ (i, i + 1). We remark that for I = 1, k + 1 or J = 0, 1, l (consult (4.17a,b) for the meaning of k and l) the displays (4.23)/(4.24) should be understood in the sense that some entries that in the displays are shown to be located in the middle part could be actually located in the front or back part (e.g. b_{I−1} for I = 1 would be located in the front part, while a_{I−1} for I = 1 would even be non-existent). However, the operation (4.23)/(4.24) is still well-defined in all these cases.

Also here, we have to show that φ^{2} is well-defined, i.e., that (RT_{1}, …, RT′′_{i}, RT′′_{i+1}, …, RT_{n}) belongs to B^{2}, and that φ^{2} is an involution that satisfies (i1) and (i2).

For being well-defined, we have to check that the rows in RT′′_{i} and RT′′_{i+1} are still strictly increasing, and that (4.12a,b), (e1), (g3), and (b2) are satisfied.

For proving that the rows of RT′′_{i} and RT′′_{i+1} are strictly increasing we have to show c_{J} < a_{I}, d_{J−1} < b_{I}, a_{I−1} < c_{J+1} (if I > 1, there is nothing to show if I = 1), and b_{I−1} < d_{J}. The first and the last inequality hold by (4.17c) and (4.17d), respectively. Supposing that the second inequality does not hold, we obtain c_{J} < a_{I} < a_{I+1} and b_{I} ≤ d_{J−1} < d_{J}. But by (4.17c,d,e) this means that (a_{I+1}, d_{J}) is a crossing point of M_{i} and M_{i+1}, contradicting the “maximality” of S = (a_{I}, d_{J}). Similarly, if we suppose that the third inequality does not hold, we obtain c_{J+1} ≤ a_{I−1} < a_{I} and b_{I−1} < d_{J} < d_{J+1}. By (4.17c,d,e) this means that (a_{I}, d_{J+1}) is a crossing point of M_{i} and M_{i+1}, again contradicting the “maximality” of S = (a_{I}, d_{J}).

The property (e1) is trivially satisfied since, as we already observed, there are no empty entries in RT_{i} and RT_{i+1}, and so there are no empty entries in RT′′_{i} and RT′′_{i+1}.

The next property to be checked is (4.12a,b). Of course, there is no problem with entries in the second rows to the right of the cuts in RT′′_{i} and RT′′_{i+1} (indicated by vertical dotted lines in (4.24)) and their “partners” related by (4.12b) in the first rows, since this part was not affected by φ^{2}. Also there is no problem with entries in the first rows to the left of the cuts in RT′′_{i} and RT′′_{i+1} and their partners related by (4.12b) in the second rows because of the shift of the first rows relative to the second rows that happens in these parts when passing from (4.23) to (4.24). However, there could be a problem if partners were “divorced” under application of φ^{2}. This is the situation of one entry (being in a first row to the right of the cut) staying at its place, the related other entry (being in a second row to the left of the cut) moving to the other two-rowed array.

The following is the typical situation,

. . . . .. . . . .^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....} RT_{i} :  … a_{I−1} a_{I} … a_{I+r−1} b_{I+r−i} … b_{I−1} b_{I} . . . . . . . . . . . . ._{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....} RT_{i+1} :  … c_{J} c_{J+1} … c_{J+r} d_{J+r−i} … d_{J−1} d_{J} …  (4.25)

and after application of φ^{2},

. . . . .. . . . .^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....} RT′′_{i} :  … c_{J} a_{I} … a_{I+r−1} d_{J+r−i} … d_{J−1} b_{I} . . . . . . . . . . . . ._{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....}_{.....} RT′′_{i+1} :  … a_{I−1} c_{J+1} … c_{J+r} b_{I+r−i} … b_{I−1} d_{J} …  (4.26)

where r satisfies 1 ≤ r ≤ i − 1. Of course, any of a_{I+r−1}, b_{I+r−i}, c_{J+r}, d_{J+r−i} could be non-existent. We shall take care of these possibilities, too.

Since RT_{i} satisfies (4.12a,b) we have b_{s} < f(a_{s+i−1}) for all s, and since RT_{i+1} also satisfies (4.12a,b) we have d_{s} < f(c_{s+i}) for all s. In particular, there hold b_{I+r−i} < f(a_{I+r−1}) (provided both a_{I+r−1} and b_{I+r−i} exist) and d_{J+r−i} < f(c_{J+r}) (provided both c_{J+r} and d_{J+r−i} exist), for 1 ≤ r ≤ i − 1.

We have to show that RT′′_{i} and RT′′_{i+1} also satisfy (4.12a,b), i.e., that

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

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

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

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

For convenience, if a_{I+r−1} does not exist we put f(a_{I+r−1}) := b + 1, and if c_{J+r} does not exist we put f(c_{J+r}) := b + 1. Also, we put b_{k+1} := b + 1 (consult (4.17a) for the meaning of k).

We distinguish between two cases.

Case 1: f(a_{I+r−1}) ≤ f(c_{J+r}). This immediately proves (4.28), since if both b_{I+r−i} and c_{J+r} exist then we have b_{I+r−i} < f(a_{I+r−1}) ≤ f(c_{J+r}). For proving (4.27), first consider the case I = k + 1 (consult (4.17a,e) for the meaning of k). Then a_{I+r−1} = a_{k+r} is in the back part B_{i} of RT_{i}, hence a_{I+r−1} > a − n (recall that the back part has to equal (4.19)). By one of the assumptions about f, this implies f(a_{I+r−1}) = b + 1 in which case (4.27) is automatically satisfied. Therefore, in the sequel we may assume I ≤ k. Now suppose that (4.27) does not hold, i.e., that both a_{I+r−1} and d_{J+r−i} exist and that d_{J+r−i} ≥ f(a_{I+r−1}). We claim that d_{J+r−i} ≤ b_{I}. For suppose d_{J+r−i} > b_{I}. By (4.17c) we have c_{J} < a_{I} < a_{I+1}, and by our assumption b_{I} < d_{J+r−i} < d_{J}. But by (4.17c,d,e) this means that (a_{I+1}, d_{J}) is a crossing point of M_{i} and M_{i+1}, contradicting the “maximality” of S = (a_{I}, d_{J}). Therefore, we have indeed d_{J+r−i} ≤ b_{I}. This implies b_{I} ≥ d_{J+r−i} ≥ f(a_{I+r−1}) ≥ f(a_{I}), the last inequality being true because of a_{I+r−1} ≥ a_{I} and the monotonicity of f. This says that (a_{I}, b_{I}) is a point outside the ladder region L. Now, to give an intuitive argument first, view the middle parts M_{1}, M_{2}, …, M_{i} as paths, P_{1}, P_{2}, …, P_{i} say, P_{j} running from (0, ff_{j}) to (a − n + 1, b), j = 1, 2, …, i (recall (4.15) for the meaning of ff_{j} and bb_{j}, also recall that for all j we have bb_{j} = a−n+1 because the back part looks like (4.19)). The point (a_{I}, b_{I}) is a NE-turn of the path P_{i} corresponding to M_{i}. Furthermore, M_{1}, M_{2}, …, M_{i} cannot have a crossing point strictly to the right of (a_{I}, b_{I}) because (a_{I}, d_{J}) is the “maximal” crossing point. Therefore the subpath of P_{i} from (a_{I}, b_{I}) to its end point (a − n + 1, b) forms a barrier above which all the other paths P_{1}, …, P_{i−1} have to stay, being allowed to touch P_{i} but not being allowed to cross. The point (a_{I}, b_{I}) lies outside (to be precise: above) the ladder region L. Therefore all the other paths, staying above or on (a_{I}, b_{I}), have to leave L. In particular, the first path P_{1}, which corresponds to M_{1}, would leave the ladder region L. This contradicts the fact that M_{1} = RT_{1} satisfies (4.12a,b) with i = 1.

To give a rigorous argument, consider M_{i−1} and M_{i}. Let M_{i−1} be given by

\begin{aligned}0 ≤ & x_{1} & x_{2} & … & x_{m} & < a − n + 1 \\ ff_{i−1} < & y_{1} & y_{2} & … & y_{m} & ≤ b \end{aligned} ,

and, as before, let M_{i} be given by

\begin{aligned}0 ≤ & a_{1} & a_{2} & … & a_{k} & < a − n + 1 \\ ff_{i} < & b_{1} & b_{2} & … & b_{k} & ≤ b \end{aligned} .

For convenience, set x_{0} := −1, y_{0} := ff_{i−1}, and x_{m+1} := a − n + 1. Let s be maximal such that x_{s} ≤ a_{I}. Since I ≤ k, and so a_{I} ≤ a − n, we have s ≤ m. Suppose that y_{s} < b_{I}. By (4.17a,b,c,d,e) (with the appropriate replacements, namely applied to M_{i−1} and M_{i}) it follows that (x_{s+1}, b_{I}) is a crossing point of M_{i−1} and M_{i}, where x_{s+1} > a_{I}. Once more this contradicts the “maximality” of S = (a_{I}, d_{J}). Therefore we actually have y_{s} ≥ b_{I}. Continuing in this manner with M_{i−2} and M_{i−1}, …, M_{1} and M_{2}, we would find a sequence (a_{I}, b_{I}), (x_{s}, y_{s}), …, (u_{t}, v_{t}), with a_{I}, b_{I} being entries in M_{i}, a_{I} exactly above b_{I}, with x_{s}, y_{s} being entries in M_{i−1} (also being allowed to be −1, ff_{i−1}), x_{s} exactly above y_{s}, …, with u_{t}, v_{t} being entries in M_{1} (also being allowed to be −1, ff_{1}), u_{t} exactly above v_{t}, and with a_{I} ≥ x_{s} ≥ ⋯ ≥ u_{t} and b_{I} ≤ y_{s} ≤ ⋯ ≤ v_{t}. Since (a_{I}, b_{I}) lies outside L, the latter inequality chains imply that also (u_{t}, v_{t}) lies outside L. But this is impossible since M_{1} = RT_{1} satisfies (4.12a,b) with i = 1. (Also v_{t} = ff_{1} is impossible since then we would have ff_{1} = v_{t} ≥ b_{I} ≥ f(a_{I}), but also ff_{1} = n − σ(1) ≤ n − 1 < f(a_{I}), the last inequality being due to one of the assumptions about f.) Therefore it follows that d_{J+r−i} < f(a_{I+r−1}), which settles (4.27).

Case 2: f(a_{I+r−1}) ≥ f(c_{J+r}). This immediately proves (4.27), since if both a_{I+r−1} and d_{J+r−i} exist then we have d_{J+r−i} < f(c_{J+r}) ≤ f(a_{I+r−1}). For proving (4.28), first consider the case J = l (consult (4.17b,e) for the meaning of l). Then c_{J+r} = c_{l+r} is in the back part B_{i+1} of RT_{i+1}, hence c_{J+r} > a−n (recall that the back part has to equal (4.19)). By one of the assumptions about f, this implies f(c_{J+r}) = b + 1 in which case (4.28) is automatically satisfied. Therefore, in the sequel we may assume J < l. Now suppose that (4.28) does not hold, i.e., that both b_{I+r−i} and c_{J+r} exist and that b_{I+r−i} ≥ f(c_{J+r}). First observe that there holds a_{I} ≤ c_{J+1}, because otherwise we would have c_{J+1} < a_{I} and by (4.17d) also b_{I−1} < d_{J} < d_{J+1}, which by (4.17c,d,e) means that (a_{I}, d_{J+1}) is a crossing point of M_{i} and M_{i+1}, contradicting the “maximality” of S = (a_{I}, d_{J}). Therefore, by monotonicity of f, we have f(a_{I}) ≤ f(c_{J+1}) ≤ f(c_{J+r}) ≤ b_{I+r−i} < b_{I}. Again, this says that (a_{I}, b_{I}) is a point outside the ladder region L. Also here we have I ≤ k since a_{I} ≤ c_{J+1} ≤ a − n, the last inequality being true because of J < l. As before, this contradicts the fact that M_{1} = RT_{1} satisfies (4.12a,b) with i = 1.

Finally, condition (g3) is certainly satisfied for RT′′_{i} and RT′′_{i+1} since they have the same back parts as RT_{i} and RT_{i+1}, respectively. And, because of a_{I−1} < a_{I} and d_{J−1} < d_{J}, condition (b2) is satisfied for RT′′_{i} and RT′′_{i+1}, again with crossing point (a_{I}, d_{J}).

The last observation, together with the fact that under application of φ^{2} nothing is changed to the right of a_{I}, b_{I}, c_{J+1}, d_{J}, shows that application of φ^{2} to (RT_{1}, …, RT′′_{i}, RT′′_{i+1}, …, RT_{n}) gives back (RT_{1}, …, RT_{i}, RT_{i+1}, …, RT_{n}). Hence, φ^{2} is an involution on B^{2}. It satisfies (i1) since σ is mapped to \overline{σ} = σ ∘ (i, i + 1), as observed before. Also, the numbers of entries in the families of two-rowed arrays are the same before and after application of φ^{2}, which settles (i2).

This finishes the proof of Theorem 1. □

5. A weighted generalization of Theorem 1. Examining the proof of Theorem 1, it is easily seen that we actually proved a stronger result.

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

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

For example, the weight of the path displayed in Figure 1 is w_{x,y}(P_{0}) = x_{1}x_{2}x_{5}y_{1}y_{3}y_{4}. This weight is extended in a shifted manner to families P = (P_{1}, P_{2}, …, P_{n}) of lattice paths by

w_{x,y}(P) = ∏_{j=1}^{r} w_{(x_{−j+1},x_{−j+2},...),(y_{j−1},y_{j},...)}(P_{j}).  (5.2)

Then we have the following generalization of Theorem 1.

Theorem 3. With the assumptions of Theorem 1 there holds

GF(P_{L}^{+}(A → E); w_{x,y})

= (x_{a−1}^{1}x_{a−2}^{2} ⋯ x_{a−n+1}^{n−1}y_{n−1}^{n−1} ⋯ y_{2}^{2}y_{1}^{1})^{−1} · det_{1≤s,t≤n} ( GF(P_{L}(A_{t} → E_{s}); w_{x,y})). (5.3)

□

Clearly, Theorem 3 specializes to Theorem 1 by setting x_{i} = z^{1/2} and y_{i} = z^{1/2} for all i.

6. Enumeration of single lattice paths in a ladder with respect to turns. The entries in the determinant in (2.2) are all generating functions ∑ z^{NE(P)} for single lattice paths P with given starting and end point that stay in the ladder region L, where L is of the form (2.1). 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 (6.4)), and the case of a ladder determined by a diagonal boundary (i.e., f(x) = x + D + 1, for some positive integer D; see (6.6)). In all other cases one has to be satisfied with answers of recursive nature.

Actually, the problem was already treated by Kulkarni [18]. We restate his formula here, and include a proof since the proof in [18] is obscured by notation. Then we derive an alternative formula, which has the same complexity as Kulkarni’s formula, but is superior for ladder regions of a particular kind. This is discussed in more detail in the paragraph after (6.10).

Kulkarni’s formula [18, Theorem 4] reads as follows. (Note that Kulkarni considers onesided lower ladders instead of one-sided upper ladders as we do. It is however no difficulty to translate everything by a rotation by 180^{∘}.) It is formulated only with the starting point of the lattice paths being (0, 0) and the end point being (a, b), the top-right corner of the ladder L. Of course, this is sufficient to determine the generating function for lattice paths inside the ladder region L with an arbitrary starting point and an arbitrary end point, since a change of coordinates will always bring us into this situation.

Proposition 4. Let the ladder region L be given by the weakly increasing function f : [0, a] → [1, b + 1] by means of (2.1), as before. Furthermore, let −1 = a_{k} < a_{k−1} < ⋯ < a_{1} < a_{0} = a−1 be a partition of the (integer) interval [0, a] such that f is constant on each subinterval [a_{i} + 1, a_{i−1}], i = k, k − 1, …, 1. Then the generating function ∑ z^{NE(P)} for all lattice paths P from (0, 0) to (a, b) in the ladder region L equals

GF_{L}(P((0, 0) → (a, b)); z^{NE(.)}) = _{∑_{e≥f≥0} ; e_{k}=f_{k}}z^{e_{k}} ∏_{i=1}^{k} \binom{a_{i−1} − a_{i}}{e_{i} − e_{i−1}}\binom{f(a_{i−1}) − f(a_{i})}{f_{i} − f_{i−1}}, (6.1)

where e = (e_{1}, e_{2}, …, e_{k}) and f = (f_{1}, f_{2}, …, f_{k}), where, by definition, e_{0} = f_{0} = f(−1) = 0, and where e ≥ f ≥ 0 means e_{i} ≥ f_{i} ≥ 0, i = 1, 2, …, k.

Proof. Let P be a lattice path from (0, 0) to (a, b) that stays in the ladder region L. Let the NE-turns of P be (x_{1}, y_{1}), (x_{2}, y_{2}), …, (x_{ℓ}, y_{ℓ}), ordered from top-right to bottom-left, i.e., x_{1} > x_{2} > ⋯ > x_{ℓ} and y_{1} > y_{2} > ⋯ > y_{ℓ}. Suppose that there are e_{i} NE-turns with x-coordinates in the interval [a_{i} + 1, a_{0}] = [a_{i} + 1, a − 1], and that there are f_{i} NE-turns with y-coordinates in the interval [f(a_{i}) + 1, f(a_{0})] = [f(a_{i}) + 1, f(a − 1)], i = 1, 2, …, k. In particular, there holds e_{k} = f_{k} = ℓ. Equivalently, we have

a − 1 = a_{0} ≥ x_{1} > ⋯ > x_{e_{1}} > a_{1} ≥ x_{e_{1}+1} > ⋯ > x_{e_{2}} > a_{2} ≥ ⋯ > a_{k−1} ≥ x_{e_{k−1}+1} > ⋯ > x_{e_{k}} > a_{k} = −1 (6.2)

and

b = f(a_{0}) ≥ y_{1} > ⋯ > y_{e_{1}} > f(a_{1}) ≥ y_{e_{1}+1} > ⋯ > y_{e_{2}} > f(a_{2}) ≥ ⋯ > f(a_{k−1}) ≥ y_{e_{k−1}+1} > ⋯ > y_{e_{k}} > f(a_{k}) = 0. (6.3)

It is immediate that we must have e_{i} ≥ f_{i} ≥ 0. (This is most easily seen by considering a picture of some ladder.) Conversely, given integer vectors e and f with e_{i} ≥ f_{i} ≥ 0 and e_{k} = f_{k}, by (6.2) and (6.3) there are

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

possible choices for the x- and y-coordinates of the NE-turns of a lattice path that has e_{i} NE-turns with x-coordinates in the interval [a_{i} +1, a_{0}], and f_{i} NE-turns with y-coordinates in the interval [f(a_{i}) + 1, f(a_{0})]. Thus, (6.1) is established. □

Now we describe the announced alternative method to compute the generating function ∑ z^{NE(P)} for lattice paths P with given starting point A and given end point E that stay in the ladder region L, where L is of the form (2.1). Let P^{h}(A → E) (respectively P_{L}^{h}(A → E)) denote the subset of P(A → E) (respectively P_{L}(A → E)) consisting of all lattice paths that start with a horizontal step. Similarly, let P^{v}(A → E) (respectively P_{L}^{v}(A → E)) denote the subset of P(A → E) (respectively P_{L}(A → E)) consisting of all lattice paths that start with a vertical step.

This second method is based on the following simple facts.

Proposition 5. Let A = (α_{1}, α_{2}) and E = (η_{1}, η_{2}) be lattice points. Then there hold

GF(P(A → E); z^{NE(.)}) = ∑_{k≥0} \binom{η_{1} − α_{1}}{k}\binom{η_{2} − α_{2}}{k}z^{k},  (6.4)

GF(P^{v}(A → E); z^{NE(.)}) = \{ \begin{matrix}∑_{k≥0} \binom{η_{1} − α_{1} − 1}{k − 1}\binom{η_{2} − α_{2}}{k}z^{k} & η_{1} > α_{1} \\ 1 & η_{1} = α_{1}. \end{matrix} (6.5)

Proposition 6. Let L_{D} be a “diagonal” ladder determined by the function f(x) = x + D + 1 by means of (2.1). Let A = (α_{1}, α_{2}) and E = (η_{1}, η_{2}) be lattice points in the ladder L_{D}. Then there hold

GF(P_{L_{D}}(A → E); z^{NE(.)}) = ∑_{k≥0} (\binom{η_{1} − α_{1}}{k}\binom{η_{2} − α_{2}}{k}

− \binom{η_{1} − α_{2} + D − 1}{k − 1}\binom{η_{2} − α_{1} − D + 1}{k + 1})z^{k},  (6.6)

GF(P_{L_{D}}^{v}(A → E); z^{NE(.)}) = \{ \begin{matrix}∑_{k≥0} & ( & \binom{η_{1} − α_{1} − 1}{k − 1} & \binom{η_{2} − α_{2}}{k} \\ & −\binom{η_{1} − α_{2} + D − 1}{k − 1}\binom{η_{2} − α_{1} − D}{k})z^{k} & η_{1} > α_{1} \\ 1 & & η_{1} = α_{1}. \end{matrix}

(6.7)

Proposition 7. Let L be an arbitrary ladder of the form (2.1), and let A, E be lattice points in L. Then, for all x ∈ [0, a] there holds

GF(P_{L}(A → E); z^{NE(.)}) = ∑_{j>x} GF(P_{L}(A → (j, f(x) − 1)); z^{NE(.)})
· GF(P_{L}^{v}((j, f(x) − 1) → E); z^{NE(.)}).  (6.8)

Proof of the Propositions. Identity (6.4) is immediate from a glance at (4.4a). For (6.5) we observe

GF(P^{v}(A → E); z^{NE(.)}) = GF(P(A → E); z^{NE(.)}) − GF(P^{h}(A → E); z^{NE(.)})
= GF(P(A → E); z^{NE(.)}) − GF(P(A + (1, 0) → E); z^{NE(.)}).

(6.9)

Application of (6.4) in the right-hand side of (6.9) then leads to (6.5).

Identity (6.6) is the special case q = 1, μ_{i} = α_{i}, λ_{i} = η_{i}, c → ∞, d = D, of [16, Theorem 1]. Equation (6.9) is also true with P_{L_{D}} instead of P. Application of (6.6) in the right-hand side of (6.9), with P replaced by P_{L_{D}}, then leads to (6.7).

The proof of (6.8) more or less consists only of Figure 6 (the dots indicating some ladder L) and the observation that any path from A to E has to run through exactly one of the marked vertical pieces.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} •  • ∘^{A}  ^{E}^{(x, f(x))}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•}

Figure 6

□

Now, here is the second method for determining GF(P_{L}(A → E); z^{NE(.)}) for any given ladder L of the form (2.1), 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 (6.8) in succession with x = x_{m−1}, x_{m−2}, …, x_{1} and use (6.4)–(6.7) to compute all the occuring 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(P_{L}(A → E); z^{NE(.)}) = ∑_{j=4}^{13} ∑_{l=8}^{13} ∑_{k_{1},k_{2},k_{3}≥0}z^{k_{1}+k_{2}+k_{3}} \binom{j − α_{1}}{k_{1}}\binom{6 − α_{2}}{k_{1}}  (6.10a)

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

(6.10b)

(\binom{η_{1} − l − 1}{k_{3} − 1}\binom{η_{2} − 12}{k_{3}}) ,  (6.10c)

where, in abuse of notation, the expression in (6.10b) is understood to be 1 if j = l and the expression in (6.10c) is understood to be 1 if l = η_{1} (compare with (6.5) and (6.7)).

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 preferable in case of long diagonal portions in the border of L, since then Kulkarni’s formula involves a lot more summations. 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 1 and instead try to extend the dummy path method in [17] such that it also applies to the enumeration of nonintersecting lattice paths with respect to turns.

We remark that the above methods that we proposed for the computation of GF(P_{L}(A → E); z^{NE(.)}) also apply for computing the more general GF(P_{L}(A → E); w_{x,y}) from section 5. Then the binomials in (6.1), (6.4)–(6.7) would be replaced by elementary symmetric functions (cf. [20, p. 19]) in certain subsets of x and y, respectively. For sake of brevity, we omit the details.

7. Conclusion. When examining our proof of Theorem 1, it can be realized that the validity of formula (2.2) is an almost incredible coincidence. There is no freedom for generalizations whatsoever. For example, in order to compute the Hilbert series of more general one-sided ladder determinantal rings than mentioned in this paper, it is necessary to solve the same enumeration problem as in Theorem 1, but with more general starting and end points, namely A_{i} = (0, α_{i}) and E_{i} = (η_{i}, b) for some α_{i}, η_{i} with α_{1} > α_{2} > ⋯ > α_{n} and η_{1} < η_{2} < ⋯ < η_{n}. One could write down the determinant in (2.2) in this case, too, and one could also give it a combinatorial meaning in terms of two-rowed arrays by using basically the same involution as in our proof of Theorem 1. But now the front and back part would not be uniquely determined and can therefore not be discarded. Hence, there is no lattice path meaning for the determinant in this more general case. Still, the enumeration problem with general starting and end points for one-sided ladders has been solved by the first author [15]. The solution cannot be formulated in terms of lattice paths any more, but in terms of two-rowed arrays only.

As we mentioned in section 3, more generally, also two-sided ladder determinantal rings are considered [1, 2, 5, 10]. In the associated enumeration problem one counts nonintersecting lattice paths in a two-sided ladder region, meaning that there is also a ladder-shaped lower boundary, but it is not a boundary for the paths but only for their NE-turns. We do not know how to generalize Theorem 1 to this situation.

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. W. Bruns and J. Herzog, On the computation of a-invariants, Manuscripta Math. 77 (1992), 201–213.

4. W. Bruns and J. Herzog, Cohen–Macaulay rings, Cambridge University Press, Cambridge, 1993.

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, 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 (to appear).

9. R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, Massachusetts, 1989.

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

11. C. Krattenthaler, Counting lattice paths with a linear boundary I, II, Sitz.ber. d. ÖAW, Math-natur-wiss. Klasse 198 (1989), 87–107; 171–199.

12. C. Krattenthaler, Generating functions for plane partitions of a given shape, Manuscripta Math. 69 (1990), 173–202.

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 respect to weighted turns, Seminaire Lotharingien Combin. 34 (1995), paper B34i.

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

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

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

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

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

20. I. G. Macdonald, Symmetric Functions and Hall Polynomials, second edition, Oxford University Press, New York/London, 1995.

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

22. B. E. Sagan, The symmetric group, Wadsworth & Brooks/Cole, Pacific Grove, California, 1991.

23. X. Viennot, Une forme géométrique de la correspondance de Robinson–Schensted, Combinatoire et Représentation du Groupe Symétrique (D. Foata, ed.), Lecture Notes in Math., Vol. 579, Springer–Verlag, New York, 1977, pp. 29—58.

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