The Enumeration of Lattice Paths With Respect to Their Number of Turns

C. Krattenthaler

Institut für Mathematik der Universität Wien, Vienna, Austria

Abstract. We survey old and new results on the enumeration of lattice paths in the plane with a given number of turns, including the recent developments on the enumeration of nonintersecting lattice paths with a given number of turns. Motivations to consider such enumeration problems come from various fields, e.g. probability, statistics, combinatorics, and commutative algebra. We show that the appropriate tool for treating turn enumeration of lattice paths is the encoding of lattice paths in terms of two-rowed arrays.

Keywords and phrases: Turns, lattice paths, nonintersecting lattice paths, coin tossing, run statistics, non-crossing two-rowed arrays, determinantal rings, pfaffian rings, Hilbert series, tableaux, plane partitions

3.1 Introduction

In this article we consider lattice paths in the plane consisting of unit horizontal and vertical steps in the positive direction. We will be concerned with enumerating such lattice paths which have a given number of turns. By a turn, we mean a vertex of a path where the direction of the path changes. For example, the turns of the path P_{0} in Figure 3.1 are (1, 1), (2, 1), (2, 3), (5, 3), (5, 4), and (6, 4). Distinguishing between the two possible types of turns, we call a vertex of a path a North-East turn (NE-turn, for short) if it is the end point of a vertical step and at the same time the starting point of a horizontal step, and we call a vertex of a path an East-North turn (EN-turn, for short) if it is a point in a path P which is the end point of a horizontal step and at the same time the starting point of a vertical step. The NE-turns of the path in Figure 3.1 are (1, 1), (2, 3), and (5, 4), and the EN-turns of the path in Figure 3.1 are (2, 1), (5, 3), and (6, 4).

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

There are various motivations to be interested in the turn enumeration of lattice paths. We describe three such motivations, from probability, statistics, and commutative algebra, respectively, in more detail, in Section 13.3. The examples from probability and statistics (correlated random walk, run and Kolmogorov-Smirnov statistics) in Section 13.3 lead to the enumeration of paths, with given starting and end points, with a given number of turns, which are bounded by lines. This is classical today. The example from commutative algebra (Hilbert series of determinantal and pfaffian rings) however leads to the enumeration of families of nonintersecting lattice paths, with given starting and end points, with a given number of turns, and subject to certain restrictions. Interest in this subject arose only recently, mainly due to the path-breaking work of Abhyankar (1987, 1988). A number of remarkable formulas were discovered to solve most of these problems. But there are still some important open questions.

The problem of turn enumeration of lattice paths was attacked in many different ways. However, there is a uniform approach which is able to handle all these problems, which is by encoding paths in terms of two-rowed arrays. Actually, this is the way in which Narayana (1959, 1979, Section II.2), who probably was the first to count paths with respect to their turns, used to see turn enumeration problems. However, he did not use the combinatorics of tworowed arrays. His proofs are manipulatory and usually work by induction. The purpose of this survey article is to show that two-rowed arrays allow to handle turn enumeration in a purely combinatorial way. The combinatorics of tworowed arrays is able to explain all the existing formulas in a conceptual way. What is very appealing is that all the standard techniques from ordinary path counting, such as reflection principle, iterated reflection principle, interchanging procedure for nonintersecting lattice paths, have their analogues in the “world of two-rowed arrays.”

Another purpose of this survey is to show the wide diversity of connections and applications in other fields like combinatorics, representation theory, and q-series. Moreover, it is not unreasonable to expect that the recent subject of turn enumeration of nonintersecting lattice paths will also have its applications in probability, statistics, or physics. Evidence for this feeling comes from the fact that turn enumeration of (single) lattice paths is of importance in these fields, and (plain) enumeration of nonintersecting lattice paths is too [see, for example, Essam and Guttmann (1995), Fisher (1984), Karlin (1988) and Karlin and McGregor (1959a,b)].

This exposition brings together ideas from several papers of this author and Mohanty [see, for example, Krattenthaler (1989, 1993, 1995a, 1995b, 1996a) and Krattenthaler and Mohanty (1993)] . The proof of Theorem 13.4.2 is new.

The paper is organized in the following way. In the next section, we introduce some basic notations which we use throughout the paper. Section 13.3 contains the announced motivating examples. In Section 13.4, we address the turn enumeration of (single) lattice paths. The results of Section 13.4 are then applied in Section 13.5 to solve some of the problems in the mentioned examples. Finally, Section 13.6 is devoted to turn enumeration of nonintersecting lattice paths. The results of this section answer most of the problems of the third example in Section 13.3. Open problems are listed at the end of Section 13.6.

3.2 Notation

Given two lattice points A and E, we denote the set of all lattice paths from A to E by L(A → E). If P is a path from A to E, we will symbolize this sometimes by P : A → E. If R is some property of paths, we use the “probability-like” notation L(A → E | R) for the set of all paths from A to E satisfying property R.

3.3 Motivating Examples

Example 3.3.1 A two coin tossing game; correlated random walk. Mohanty (1966) considered the following game. Take two coins 1 and 2 with probabilities p_{1} and p_{2} of obtaining heads, respectively. The rules for the game are:

1. start with coin i, i = 1, 2; 2. if the last trial was a tail, then make the next trial with coin 1, otherwise

with coin 2;

3. stop making further trials when for the first time the total number of heads exceeds μ times the total number of tails by exactly a, with a fixed a > 0.

The question is: Provided the game was started by tossing coin i, i = 1 or 2, what is the distribution of the duration of the game?

This game has also an equivalent formulation in terms of a “correlated” random walk; see, for example, Mohanty (1979, Section 5.2). In sampling plan terminology [DeGroot (1959)], these games describe sequential sampling plans for binomial populations with y = μx + a as the boundary line.

It is an easy observation that any game can be represented in terms of a lattice path, by starting in (0, 0) and proceeding by a horizontal step if tail (T) was tossed and by a vertical step if head (H) was tossed. Thus, the game T HHHT HT HHHH (which is a game for μ = 2 and a = 2) would be represented by the lattice path P_{2} in Figure 3.2. The condition (3) is reflected by the fact that any such lattice path, except for the final vertical step, stays below the line y = μx + a − 1 (being allowed to touch it).

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; P_{2}; y = μx + a − 1] Figure 3.2

The probability of a game of length (μ + 1)n + a (n tails and μn + a heads) is given as follows. If the first toss was with coin 1, then the probability of a game, corresponding to a path P as described above, is

p_{1}^{NE(P)+1}(1 − p_{1})^{n−NE(P)}p_{2}^{μn+a−NE(P)−1}(1 − p_{2})^{NE(P)},  (3.1)

where NE(P) denotes the number of NE-turns of P. On the other hand, if the first toss was with coin 2, then the probability of a game, corresponding to path P, is

p_{1}^{NE(P)+1}(1 − p_{1})^{n−NE(P)−1}p_{2}^{μn+a−NE(P)−1}(1 − p_{2})^{NE(P)+1},  (3.2)

if the first toss resulted in tail, and

p_{1}^{NE(P)}(1 − p_{1})^{n−NE(P)}p_{2}^{μn+a−NE(P)}(1 − p_{2})^{NE(P)},  (3.3)

if the first toss resulted in head, respectively.

Therefore, to determine the probability of games of length (μ + 1)n + a, we need to enumerate lattice paths from (0, 0) to (n, μn + a − 1) staying below the line y = μx + a − 1, being allowed to touch it, which have a given number of NE-turns.

Example 3.3.2 Runs and Kolmogorov-Smirnov statistics. Two common rank order statistics for nonparametric testing problems in the two-sample case are the run statistics and the (one- and two-sided) Kolmogorov-Smirnov statistics. We consider just the case of equal sample size. Recall [see, for example, Mohanty (1979, Section 4.3)] that there are two sets of independent and identically distributed random variables X = {X_{1}, X_{2},…, X_{n}} and Y = {Y_{1}, Y_{2},…, Y_{n}} of size n. These are then put together and ordered into Z = (Z_{1}, Z_{2},…, Z_{2n}) according to size. The run statistics counts the number of maximal consecutive subsequences in Z the members of which belong to just one of the sets X or Y. Thus, if n = 5, and if Z = (X_{1}, Y_{1}, Y_{2}, Y_{3}, X_{2}, X_{3}, Y_{4}, X_{4}, X_{5}, Y_{5}), then the number of runs in Z is 6. The one-sided Kolmogorov-Smirnov statistic D_{n,n}^{+} is defined by

D_{n,n}^{+} = \frac{1}{n} max_{i}\{a_{i} − b_{i}\},

where a_{i} is the number of occurrences of X_{j}’s in the initial segment Z_{1}, Z_{2},…, Z_{i} of Z, while b_{i} is the number of occurrences of Y_{j}’s in this initial segment. The two-sided Kolmogorov-Smirnov statistic D_{n,n} is defined by

D_{n,n} = \frac{1}{n} max_{i} \{|a_{i} − b_{i}|\}.

Thus, we have for our combined sample Z that D_{5,5}^{+} = 1/5 and D_{5,5} = 2/5.

Each such sequence Z can be represented by a lattice path in the obvious way. Namely, start at (0, 0), then read through the sequence from left to right and proceed by a vertical step if some X_{j} is encountered and by a horizontal step if some Y_{j} is encountered. Thus, the above set Z corresponds to the lattice path P_{3} in Figure 3.3. The run statistics obviously translates into the number of maximal horizontal and vertical pieces in the corresponding path. The onesided Kolmogorov-Smirnov statistic is basically the maximal deviation from the main diagonal in direction (1, −1). The two-sided Kolmogorov-Smirnov statistic is basically the maximal deviation from the main diagonal, in either direction. So in Figure 3.4, paths which stay in the region between the indicated lines y = x+2 and y = x−2 correspond to sequences Z with two-sided Kolmogorov-Smirnov statistic D_{n,n} ≤ 2/5.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; P_{3}; y = x + 2; y = x − 2] Figure 3.3

Since the number of runs of a lattice path equals 1 plus the number of turns of the path, we see that to determine the distribution of the run statistics we need to count lattice paths from (0, 0) to (n, n) with a given number of turns (both, NE- and EN-turns). If, in addition, we want to know the joint distribution of runs and the Kolmogorov-Smirnov statistic, then we have to count paths from (0, 0) to (n, n) with a given number of turns which in addition stay below a line y = x + t for the one-sided Kolmogorov-Smirnov statistic and between lines y = x + t and y = x − t for the two-sided Kolmogorov-Smirnov statistic.

Example 3.3.3 Determinantal rings. Determinantal rings are frequently studied objects in commutative algebra and algebraic geometry. We start with the classical case. Let X = (X_{i,j})_{0≤i≤b, 0≤j≤a} be a (b + 1) × (a + 1) matrix of indeterminates. Let K[X] denote the ring of all polynomials over some field K in the X_{i,j}’s, 0 ≤ i ≤ b, 0 ≤ j ≤ a, and let I_{n+1}(X) be the ideal in K[X] that is generated by all (n + 1) × (n + 1) minors of X. The ideal I_{n+1}(X) is called a determinantal ideal. The associated determinantal ring is R_{n+1}(X) := K[X]/I_{n+1}(X). This is a graded ring. The obvious question to ask is what the dimensions of the homogeneous components R_{n+1}(X)_{ℓ} of dimension ℓ, ℓ = 0, 1,…, of R_{n+1}(X) are. This information is recorded in terms of the Hilbert series of R_{n+1}(X), which is simply the generating function ∑_{ℓ=0}^{∞} dim_{K} (R_{n+1}(X)_{ℓ}) z^{ℓ}. It was shown in several ways [Abhyankar (1988), Abhyankar and Kulkarni (1989), Conca and Herzog (1994), Kulkarni (1996), Modak (1992) and also Ghorpade (1996)] that this problem relates to counting lattice paths with respect to turns, more precisely, to counting families of nonintersecting lattice paths with respect to turns. A family (P_{1}, P_{2},…, P_{n}) of paths P_{i}, i = 1, 2,…, n, is called nonintersecting if no two paths in the family have a point in common, otherwise it is called intersecting.

Theorem 3.3.1 Let A_{i} = (0, n − i) and E_{i} = (a − n + i, b), i = 1, 2,…, n. Then, the Hilbert series of the determinantal ring R_{n+1}(X) = K[X]/I_{n+1}(X) equals

∑_{ℓ=0}^{∞} dim_{K} (R_{n+1}(X)_{ℓ}) z^{ℓ} = \frac{∑_{P} z^{NE(P)}}{(1 − z)^{(a+b+1)n−2\binom{n}{2}}} ,  (3.4)

where the sum on the right-hand side is over all families P = (P_{1}, P_{2},…, P_{n}) of nonintersecting lattice paths, with P_{i} running from A_{i} to E_{i}, i = 1, 2,…, n. Here, the number NE(P) is defined to be the total number ∑_{i=1}^{n} NE(P_{i}) of NEturns of the family P.

Figure 3.4 contains an example of such a family of nonintersecting lattice paths for a = 13, b = 15, and n = 4. The NE-turns are marked by bold dots.

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{E_{1}}^{E_{2}}^{E_{3}}^{E_{4}}^{A_{1}}^{A_{2}}^{A_{3}}_{A_{4}}  ^{P_{1}}^{P_{2}}  ^{P_{3}} ^{P_{4}} ∘ ∘ ∘ ∘  ∘ ∘ ∘ ∘ • • • • •  • • • •  • • • •  • • Figure 3.4

Several generalizations of this concept have also been considered. These pose even more difficult turn enumeration problems. We describe just one such generalization in detail. Let a = (a_{1}, a_{2},…, a_{n}) and b = (b_{1}, b_{2},…, b_{2}) be two vectors of nonnegative integers which are in strictly increasing order. Let Ia,b_{n+1}(X) denote the ideal in K[X] that is generated by all t × t minors of the restriction of X to rows 0, 1,…, a_{t} − 1 and columns 0, 1,…, b_{t} − 1, t = 1, 2,…, n, and by all (n + 1) × (n + 1) minors of X. What we considered before is the special case a = (0, 1,…, n − 1) and b = (0, 1,…, n − 1). Again, the associated determinantal ring is Ra,b_{n+1}(X) := K[X]/Ia,b_{n+1}(X). For more information on these rings, see Herzog and Trung (1992) and the references therein. In the papers by Abhyankar (1988), Abhyankar and Kulkarni (1989), Conca and Herzog (1994), and Kulkarni (1996), it is shown that this relates to counting lattice paths with respect to turns in much the same way. The difference is that the starting and end points of the lattice paths now depend on the vectors a and b, respectively.

Theorem 3.3.2 Let A_{i} = (0, a_{n−i+1}) and E_{i} = (a − b_{n−i+1}, b), i = 1, 2,…, n. Then, the Hilbert series of the determinantal ring Ra,b_{n+1}(X) = K[X]/Ia,b_{n+1}(X) equals

∑_{ℓ=0}^{∞} dim_{K} (Ra,b_{n+1}(X)_{ℓ}) z^{ℓ} = \frac{∑_{P} z^{NE(P)}}{(1 − z)^{(a+b+1)n−∑_{i=1}^{n}(a_{i}+b_{i})}} ,  (3.5)

where the sum on the right-hand side is over all families P = (P_{1}, P_{2},…, P_{n}) of nonintersecting lattice paths, with P_{i} running from A_{i} to E_{i}, i = 1, 2,…, n.

Finally, we remark that similar constructions are studied with minors of “ladder-shaped” matrices, of symmetric matrices, and with minors of pfaffians. It was shown by Abhyankar (1988) and Abhyankar and Kulkarni (1989) for the ladder case, by Conca (1994) for minors of a symmetric matrix, and by Ghorpade and Krattenthaler (1996) for minors of pfaffians, that the computation of Hilbert series for the resulting rings again requires enumeration of families of nonintersecting lattice paths, restricted to certain regions, with respect to their number of turns. In particular, the pfaffian case leads to the enumeration of families of nonintersecting lattice paths with given starting and end points which stay below a diagonal line.

3.4 Turn Enumeration of (Single) Lattice Paths

Examples 13.3.1 and 13.3.2 of the previous section, and the n = 1 case of Example 13.3.3, lead to the problem of turn enumeration of lattice paths, in some way, as explained above. In the next section, we show that if one knows the answer for the enumeration of lattice paths with a given number of NE-turns, then this implies solutions for all the aforementioned enumeration problems. Therefore, it is sufficient to concentrate on the enumeration of lattice paths with given starting and end points, satisfying certain restrictions, and with a given number of NE-turns. This is exactly what we do in this section.

The first question, namely ‘what is the number of paths from A = (a_{1}, a_{2}) to E = (e_{1}, e_{2}) with exactly ℓ NE-turns’, is immediately answered by

|L((a_{1}, a_{2}) → (e_{1}, e_{2}) | NE(.) = ℓ)| = \binom{e_{1} − a_{1}}{ℓ}\binom{e_{2} − a_{2}}{ℓ}.  (3.6)

This comes from the observation that any path from (a_{1}, a_{2}) to (e_{1}, e_{2}) is uniquely determined by its NE-turns. There are e_{1} − a_{1} integers from which we can choose the x-coordinates of the NE-turns, and there are e_{2} − a_{2} integers from which we can choose the y-coordinates. And, we have to choose ℓ for each of those. Thus (13.6) is explained.

The fact that paths with given starting and end points are uniquely determined by their NE-turns suggests that we should actually encode paths by their NE-turns themselves, more precisely, by the coordinates of their NE-turns. Let (p_{1}, q_{1}), (p_{2}, q_{2}), …, (p_{ℓ}, q_{ℓ}) be the NE-turns of a path P. Then the NE-turn representation of P is defined by the two-rowed array

\begin{matrix}p_{1} & p_{2} & … & p_{ℓ} \\ q_{1} & q_{2} & … & q_{ℓ}, \end{matrix}  (3.7)

which consists of two strictly increasing sequences. Sometimes, we will also use a one-line notation, (p_{1},…, p_{ℓ} | q_{1},…, q_{ℓ}), or even shorter (p | q) where p = (p_{1},…, p_{ℓ}) and q = (q_{1},…, q_{ℓ}).

Clearly, if P runs from (a_{1}, a_{2}) to (e_{1}, e_{2}), then a_{1} ≤ p_{1} < p_{2} < … < p_{ℓ} ≤ e_{1} − 1 and a_{2} + 1 ≤ q_{1} < q_{2} < … < q_{ℓ} ≤ e_{2}. If we wish to make this fact transparent, we write

\begin{aligned}a_{1} ≤ & p_{1} & p_{2} & … & p_{ℓ} & ≤ e_{1} − 1 \\ a_{2} + 1 ≤ & q_{1} & q_{2} & … & q_{ℓ} & ≤ e_{2}. \end{aligned}  (3.8)

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 example, the two-rowed array representation of the path in Figure 3.1 would be

\begin{matrix}1 & 2 & 5 \\ 1 & 3 & 4, \end{matrix}

or with bounds included,

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

Apparently, in order to find the distribution for the game of Example 13.3.1 with μ = 1, and to find the joint distribution for runs and one-sided Kolmogorov-Smirnov statistic, we need to count lattice paths, with given starting and end point, and with a given number of NE-turns, which stay below a given diagonal line. This is addressed in the following theorem.

Theorem 3.4.1 Let a_{1} ≥ a_{2} and e_{1} ≥ e_{2}. The number of all lattice paths from (a_{1}, a_{2}) to (e_{1}, e_{2}) staying below the diagonal line x = y (being allowed to touch it) with exactly ℓ NE-turns is given by

|L((a_{1}, a_{2}) → (e_{1}, e_{2}) | x ≥ y, NE(.) = ℓ)|
= \binom{e_{1} − a_{1}}{ℓ}\binom{e_{2} − a_{2}}{ℓ} − \binom{e_{1} − a_{2} − 1}{ℓ − 1}\binom{e_{2} − a_{1} + 1}{ℓ + 1}.  (3.9)

Remark 3.4.1 Before we sketch a proof of this theorem, a remark is in order. Recall that plain enumeration of lattice paths from (a_{1}, a_{2}) to (e_{1}, e_{2}) staying below x = y (without fixing the number of NE-turns) is usually done by means of the reflection principle [see, for example, Comtet (1974, p. 22)]. We promised to treat all the turn enumeration problems by using two-rowed arrays. In fact, the proof below can be considered as the reflection principle for two-rowed arrays.

Proof. The paths from (a_{1}, a_{2}) to (e_{1}, e_{2}) staying below x = y with exactly ℓ NE-turns by the NE-turn representation can be represented by

\begin{aligned}a_{1} ≤ & p_{1} & p_{2} & … & p_{ℓ} & ≤ e_{1} − 1 \\ a_{2} + 1 ≤ & q_{1} & q_{2} & … & q_{ℓ} & ≤ e_{2}, \end{aligned}  (3.10)

where

p_{i} ≥ q_{i},  i = 1, 2,…, ℓ.  (3.11)

The number of these two-rowed arrays is the number of all two-rowed arrays of the type (13.10) minus those two-rowed arrays of the type (13.10) which violate (13.11), i.e. where p_{i} < q_{i} for some i between 1 and ℓ. We know the first number from (13.6).

Concerning the second number, we claim that two-rowed arrays of the type (13.10) which violate (13.11) are in one-to-one correspondence with two-rowed arrays of the type

\begin{aligned}a_{2} + 1 ≤ & & & r_{2} & … & r_{ℓ} & ≤ e_{1} − 1 \\ a_{1} ≤ & s_{0} & s_{1} & s_{2} & … & s_{ℓ} & ≤ e_{2}. \end{aligned}  (3.12)

The number of all these two-rowed arrays is \binom{e_{1}−a_{2}−1}{ℓ−1}\binom{e_{2}−a_{1}+1}{ℓ+1}, as desired. So it only remains to construct the one-to-one correspondence.

Take a two-rowed array (p | q) of the type (13.10) such that p_{i} < q_{i} for some i. Let I be the largest integer such that p_{I} < q_{I}. Then map (p | q) to

\begin{aligned}& & q_{1} & . . . . . . & q_{I−1} & p_{I+1} & … & p_{ℓ} \\ p_{1} & p_{2} & . . . . . . & p_{I} & q_{I} & q_{I+1} & … & q_{ℓ}. \end{aligned}  (3.13)

Observe that both rows are strictly increasing because of q_{I−1} < q_{I} < q_{I+1} ≤ p_{I+1} (since I is largest with p_{I} < q_{I}) and p_{I} < q_{I}. By a case by case analysis, it can be seen that (13.13) is of type (13.12).

The inverse of this map is defined in the same way. Let (r | s) be a tworowed array of the type (13.12). Let J be the largest integer such that r_{J} < s_{J}. If there is no such J, take J = 1. Then map (r | s) to

\begin{matrix}s_{0} & . . . . . . & s_{J−1} & r_{J+1} & … & r_{ℓ} \\ r_{2} & … & r_{J} & s_{J} & . . . . . . . . . & s_{ℓ}. \end{matrix}  (3.14)

It is not difficult to check that the mappings (13.13) and (13.14) are inverses of each other. This completes the proof of (13.9).

In order to solve the generalized problem in Example 13.3.1 (where the game is stopped when the number of heads exceeds μ times the total number of tails by exactly a), we need to count lattice paths, with given starting and end points, and with a given number of NE-turns, which stay below a line of the form y = μx. As in the situation encountered for plain counting (i.e., disregarding the number of turns), there is no nice formula for arbitrary starting and end points. But, there is if the end point lies on the boundary line. Luckily, this is exactly our situation in Example 13.3.1.

We formulate the result in an equivalent form. Namely, we consider paths bounded by a line of the form x = μy (instead of y = μx) where the starting point lies on the boundary. That this is indeed equivalent is obvious from reversal of paths. Of course, we use two-rowed arrays in the proof. In contrast to the proof of Theorem 13.4.1, this proof is not purely bijective, as is pointed out in more detail after the proof. However, from the proof it can be seen very clearly where the limitations are, and in particular, why it does not generalize to an arbitrary location of the starting point.

Theorem 3.4.2 Let μ be a positive integer and let e_{1} ≥ μe_{2}. The number of all lattice paths from (0, 0) to (e_{1}, e_{2}) staying below the line x = μy (being allowed to touch it) with exactly ℓ NE-turns is given by

|L((0, 0) → (e_{1}, e_{2}) | x ≥ μy, NE(.) = ℓ)|
= \binom{e_{1}}{ℓ}\binom{e_{2}}{ℓ} − μ\binom{e_{1} − 1}{ℓ − 1}\binom{e_{2} + 1}{ℓ + 1}.  (3.15)

Proof. Again we represent our paths from (0, 0) to (e_{1}, e_{2}) staying below x = μy with exactly ℓ NE-turns, by their NE-turn representation. It is

\begin{aligned}0 ≤ & p_{1} & p_{2} & … & p_{ℓ} & ≤ e_{1} − 1 \\ 1 ≤ & q_{1} & q_{2} & … & q_{ℓ} & ≤ e_{2}, \end{aligned}  (3.16)

where

p_{i} ≥ μq_{i},  i = 1, 2,…, ℓ.  (3.17)

Once again, the number of these two-rowed arrays is the number of all tworowed arrays of the type (13.16) minus those two-rowed arrays of the type (13.16) which violate (13.17), i.e. where p_{i} < μq_{i} for some i between 1 and ℓ. We know the first number from (13.6).

This time, we claim that there are as many two-rowed arrays of the type (13.16) which violate (13.17) as μ times the number of two-rowed arrays of the type

\begin{aligned}1 ≤ & & & r_{2} & … & r_{ℓ} & ≤ e_{1} − 1 \\ 0 ≤ & s_{0} & s_{1} & s_{2} & … & s_{ℓ} & ≤ e_{2}. \end{aligned}  (3.18)

The number of all these two-rowed arrays is \binom{e_{1}−1}{ℓ−1}\binom{e_{2}+1}{ℓ+1}, as desired. What remains to be done is to find a (μ : 1) correspondence between the two-rowed arrays of type (13.16), violating (13.17), and those of type (13.18).

Take a two-rowed array (p | q) of the type (13.16) such that p_{i} < μq_{i} for some i. Let I be the largest integer such that p_{I} < μq_{I}. The two-rowed array (p | q) then looks like

\begin{aligned}0 ≤ & p_{1} & . . . . . . . . . & p_{I} & … & p_{ℓ} & ≤ e_{1} − 1 \\ 1 ≤ & q_{1} & … & q_{I−1} & q_{I} & … & q_{ℓ} & ≤ e_{2} \end{aligned} .  (3.19)

Now we fix the right portion, i.e., the entries p_{I+1},…, p_{ℓ} and q_{I},…, q_{ℓ}. With this fixed right portion, there are

\binom{μq_{I}}{I}\binom{q_{I} − 1}{I − 1}  (3.20)

possible left portions.

On the other hand, let (r | s) be a two-rowed array of the type (13.18). Let J be maximal with r_{J} < μs_{J} (if there is no such J, take J = 1), so that (r | s) looks like

\begin{aligned}1 ≤ & & & r_{2} & . . . . . . . . . & r_{J} & … & r_{ℓ} & ≤ e_{1} − 1 \\ 0 ≤ & s_{0} & s_{1} & s_{2} & … & s_{J−1} & s_{J} & … & s_{ℓ} & ≤ e_{2} \end{aligned} .  (3.21)

Again, fix the right portion, i.e., the entries r_{J+1},…, r_{ℓ} and s_{J},…, s_{ℓ}. Furthermore, assume that the right portion in (13.21) is equal to the right portion in (13.19), i.e., assume that J = I, r_{i} = p_{i}, i = I + 1,…, ℓ, and s_{i} = q_{i}, i = I,…, ℓ. With this fixed right portion in (13.21) there are

\binom{μq_{I} − 1}{I − 1}\binom{q_{I}}{I} = \frac{1}{μ}\binom{μq_{I}}{I}\binom{q_{I} − 1}{I − 1}  (3.22)

possible left portions. By comparing with (13.20), we see that, for a fixed right portion, there are μ times as many two-rowed arrays of the type (13.19), with p_{I} < μq_{I}, as there are two-rowed arrays of the type (13.21), with r_{I} < μs_{I} = μq_{I}. This proves our claim and hence completes the proof of the theorem.

Remark 3.4.2 The above proof could be made purely bijective if one could find a bijection for the binomial identity (13.22), i.e., for

μ\binom{μq_{I} − 1}{I − 1}\binom{q_{I}}{I} = \binom{μq_{I}}{I}\binom{q_{I} − 1}{I − 1}.  (3.23)

I have not been able to find any.

On the other hand, it is exactly identity (13.23) which constitutes the limitations towards a formula for an arbitrary starting point. One may check that there is no such binomial identity in this latter situation. The appearance of a factor μ on the left-hand side of (13.23) is rather special.

There is a companion of Theorem 13.4.2 for the enumeration with respect to EN-turns. By a rotation by 180^{∘}, it can easily be transformed into a result for counting paths which stay above the line x = μy with respect to NE-turns. We state the result without proof. It can be established in much the same way as Theorem 13.4.2.

Theorem 3.4.3 Let μ be a positive integer and let e_{1} ≥ μe_{2}. The number of all lattice paths from (0, 0) to (e_{1}, e_{2}) staying below the line x = μy (being allowed to touch it) with exactly ℓ EN-turns is given by

|L((0, 0) → (e_{1}, e_{2}) | x ≥ μy, EN(.) = ℓ)|
= \binom{e_{1} + 1}{ℓ}\binom{e_{2} − 1}{ℓ − 1} − μ\binom{e_{1}}{ℓ − 1}\binom{e_{2}}{ℓ}.  (3.24)

Now, in order to find the joint distribution of two-sided Kolmogorov-Smirnov and run statistics, we need to count lattice paths, with given starting and end points, and with a given number of NE-turns, which stay between two given diagonal lines. The result which solves this problem is as follows.

Theorem 3.4.4 Let a_{1} +t ≥ a_{2} ≥ a_{1} +s and e_{1} +t ≥ e_{2} ≥ e_{1} +s. The number of all paths from (a_{1}, a_{2}) to (e_{1}, e_{2}) staying below the line y = x + t and above the line y = x+s (being allowed to touch them) with exactly ℓ NE-turns is given by

|L((a_{1}, a_{2}) → (e_{1}, e_{2}) | x + t ≥ y ≥ x + s, NE(.) = ℓ)|
= ∑_{k=−∞}^{∞} \{\binom{e_{1} − a_{1} − k(t − s)}{ℓ + k}\binom{e_{2} − a_{2} + k(t − s)}{ℓ − k}

−\binom{e_{1} − a_{2} − k(t − s) + s − 1}{ℓ + k}\binom{e_{2} − a_{1} + k(t − s) − s + 1}{ℓ − k}\}.

(3.25)

Remark 3.4.3 Again, a remark is in order before we begin the proof. Recall that plain enumeration of lattice paths from (a_{1}, a_{2}) to (e_{1}, e_{2}) staying between two diagonal lines is usually done by means of iterated reflection principle [see, for example, Mohanty (1979, proof of Theorem 2 on p. 6)]. The proof below can be considered as the analogue of iterated reflection principle for two-rowed arrays.

Proof. By the NE-turn representation, the paths under consideration are in one-to-one correspondence with two-rowed arrays of the type

\begin{aligned}a_{1} ≤ & p_{1} & … & p_{ℓ} & ≤ e_{1} − 1 \\ a_{2} + 1 ≤ & q_{1} & … & q_{ℓ} & ≤ e_{2}, \end{aligned}  (3.26)

where

p_{i} + t ≥ q_{i} ≥ p_{i+1} + s.  (3.27)

The proof of this theorem is by a “cancelling” bijection on certain two-rowed arrays, which we introduce now. In fact, there are two types of arrays. Let us call two-rowed arrays of the type

\begin{aligned}a_{1} + k(t − s) ≤ & p_{1−k} & … & p_{1+k} & … & p_{ℓ} & ≤ e_{1} − 1 \\ a_{2} + 1 − k(t − s) ≤ & & & q_{1+k} & … & q_{ℓ} & ≤ e_{2} \end{aligned} for k ≥ 0

and

\begin{aligned}a_{1} + k(t − s) ≤ & & & p_{1−k} & … & p_{ℓ} & ≤ e_{1} − 1 \\ a_{2} + 1 − k(t − s) ≤ & q_{1+k} & … & q_{1−k} & … & q_{ℓ} & ≤ e_{2} \end{aligned} for k < 0

type I arrays. Similarly, we call two-rowed arrays of the type

\begin{aligned}a_{2} + 1 − s + k(t − s) ≤ & p_{1−k} & … & p_{1+k} & … & p_{ℓ} & ≤ e_{1} − 1 \\ a_{1} + s − k(t − s) ≤ & & & q_{1+k} & … & q_{ℓ} & ≤ e_{2} \end{aligned} for k ≥ 0

and

\begin{aligned}a_{2} + 1 − s + k(t − s) ≤ & & & p_{1−k} & … & p_{ℓ} & ≤ e_{1} − 1 \\ a_{1} + s − k(t − s) ≤ & q_{1+k} & … & q_{1−k} & … & q_{ℓ} & ≤ e_{2} \end{aligned} for k < 0

type II arrays. We shall set up a bijection between type I arrays not being of the type (13.26) – (13.27) [which means that (13.27) must be violated if both rows have equal length] and type II arrays. Given such a bijection, we could deduce

|{type I arrays}| − |{type II arrays}| = |{arrays of type (13.26) – (13.27)}|. (3.28)

The arrays of type (13.26) – (13.27) exactly correspond to the paths we are intending to enumerate. By definition of type I and type II arrays, the lefthand side in (13.28) equals the right-hand side in (13.25). Thus (13.25) would be established.

The definition of the bijection and its inverse can be given in a unified form. Let (p | q) be a type I array not of the type (13.26) – (13.27) or a type II array,

\begin{matrix}p_{1−k} & . . . . . . . . . . . . . & p_{ℓ} \\ q_{1+k} & … & q_{ℓ}. \end{matrix}

(This representation has to be understood symbolically. k could be also negative, whence the upper row would be shorter.) Let I be the largest integer, 1 ≤ I ≤ ℓ, such that either

q_{I} > p_{I} + t or I = −k,  (3.29)

or

q_{I} < p_{I+1} + s or I = k.  (3.30)

If (13.29) is satisfied, then map (p | q) to

\begin{matrix}(q_{1+k} − t) & . . . . . . . . . . . & (q_{I−1} − t) & p_{I+1} & … & p_{ℓ} \\ (p_{1−k} + t) & . . . . . . . . . . . . . . . . . . & (p_{I} + t) & q_{I} & . . . . . . . . . & q_{ℓ}. \end{matrix}

Note that both rows are strictly increasing because of q_{I−1} < q_{I+1} ≤ p_{I+1} + t and p_{I} + t < q_{I}. If (13.29) is not satisfied, and hence (13.30) is, map (p | q) to

\begin{matrix}(q_{1+k} − s) & … & (q_{I} − s) & p_{I+1} & … & p_{ℓ} \\ (p_{1−k} + s) & . . . . . . . . . . . . . . . . . . & (p_{I} + s) & q_{I+1} & … & q_{ℓ}. \end{matrix}

Again note that both rows are strictly increasing, this time because of q_{I} − s < p_{I+1} and p_{I} + s < p_{I+2} + s ≤ q_{I+1}.

It is not difficult to verify that this mapping maps type I arrays not being of type (13.26) – (13.27) to type II arrays not being of type (13.26) – (13.27), and vice versa. Besides, by applying this map to some array twice, one would obtain that array back. Therefore, this mapping is the desired bijection.

Theorem 13.4.4 and its proof are basically from Krattenthaler and Mohanty (1995). Actually, Theorem 1 of Krattenthaler and Mohanty (1995) provides a q-analogue. A closely related paper is by Burge (1993). There, “restricted partition pairs” are considered, which are nothing but two-rowed arrays with restrictions very similar to (13.27). Burge proves a generating function result for these restricted partitions. It turns out that the above proof generalizes to prove Burge’s main theorem, also. (Burge gives a different, slightly involved proof.) Remarkably, (among other results) Burge derives a number of identities expressing a Gaussian binomial coefficient as difference of two terminating basic hypergeometric sums. These identities combine two well-known but previously unrelated identities into a single one. In particular, he finds an identity which contains Rogers’ proof as well as Schur’s proof of the Rogers–Ramanujan identities, which were previously considered to be unrelated. Eventually, the notion of partition pairs was generalized to r-tuples of partitions and were investigated by Gessel and Krattenthaler (1996) under the name of “cylindric partitions”. Again, these objects could be used to derive identities in a simple way. The resulting identities are identities for multiple basic hypergeometric series, some of them known, but many of them new.

Counting paths subject to general boundaries with respect to NE-turns is what is needed to compute the Hilbert series of ladder determinantal rings generated by 2 × 2 minors. “Nice” formulas cannot be expected here in general. Solutions for “one-sided” ladders were proposed by Kulkarni (1993) and Krattenthaler and Prohaska (1996). A solution for two-sided ladders is proposed by Ghorpade (private communication). Niederhausen’s (1996) approach using umbral calculus methods is also worth mentioning here, though it is formulated only for EN-turns.

3.5 Applications

In this section, we apply the results from the previous section to solve (some of) the problems mentioned in Section 13.3.

ad Example 13.3.1. We saw that any game of length (μ+1)n+a corresponds to a path from (0, 0) to (n, μn + a − 1) staying below the line y = μx + a − 1. Equivalently, by reversal of paths, it corresponds to a path from (0, 0) to (μn + a − 1, n) staying below the line x = μy. Also, in (13.1)–(13.3), we expressed the probability of a game of length (μ + 1)n + a in terms of the NE-turns of the corresponding path. In particular, the probability that a game with first toss by coin 1 has length (μ + 1)n + a, is immediately obtained from Theorem 13.4.2 with e_{1} = μn + a − 1 and e_{2} = n:

A game starting with a toss of coin 1 has length (μ+1)n+a with probability

∑_{ℓ=0}^{n} \{\binom{μn + a − 1}{ℓ}\binom{n}{ℓ} − μ\binom{μn + a − 2}{ℓ − 1}\binom{n + 1}{ℓ + 1}\}
× p_{1}^{ℓ+1}(1 − p_{1})^{n−ℓ}p_{2}^{μn+a−ℓ−1}(1 − p_{2})^{ℓ}.  (3.31)

Of course, also games starting with a toss of coin 2 can be represented by a path from (0, 0) to (μn + a − 1, n) staying below the line x = μy. However, we have a split expression, namely (13.2) and (13.3), for the corresponding probabilities of the length of the game. The situation can be made uniform if we attach a horizontal step at the end of each path, so that we now consider paths P̄ from (0, 0) to (μn + a, n) ending with a horizontal step and staying below the line x = μy. Then it is easy to see that (13.2) and (13.3), in terms of P̄, become

p_{1}^{NE(P̄)}(1 − p_{1})^{n−NE(P̄)}p_{2}^{μn+a−NE(P̄)}(1 − p_{2})^{NE(P̄)}.  (3.32)

Since the number of paths in question which have ℓ NE-turns is just the difference of the number of paths from (0, 0) to (μn+a, n) staying below x = μy and having ℓ NE-turns, minus the number of paths from (0, 0) to (μn + a, n − 1) staying below x = μy and having ℓ NE-turns, we obtain from Theorem 13.4.2 by simplifying the difference:

A game starting with a toss of coin 2 has length (μ+1)n+a with probability

∑_{ℓ=0}^{n} \{\binom{μn + a}{ℓ}\binom{n − 1}{ℓ − 1} − μ\binom{μn + a − 1}{ℓ − 1}\binom{n}{ℓ}\}
× p_{1}^{ℓ}(1 − p_{1})^{n−ℓ}p_{2}^{μn+a−ℓ}(1 − p_{2})^{ℓ}.  (3.33)

ad Example 13.3.2. We have to convert our enumeration results for NEturns into ones for runs. Recall that the number of runs of a path is exactly one more than the number of turns (both, NE-turns and EN-turns). To avoid case by case formulation, depending on whether the number of runs is even or odd, we prefer to consider generating functions. Suppose we know the number of all paths from A to E satisfying some property R and containing a given number of NE-turns. Then we also know the generating function ∑_{P} x^{NE(P)}, where the sum is over all paths P from A to E satisfying R. Let us denote it by F (A → E | R; x). We define four refinements of F (A → E | R; x). Let F_{hv}(A → E | R; x) be the generating function ∑_{P} x^{NE(P)} where the sum is over all paths in L(A → E | R) that start with a horizontal step and end with a vertical step. Similarly define F_{hh}(A → E | R; x), F_{vh}(A → E | R; x), and F_{vv}(A → E | R; x). The relation between enumeration by runs and enumeration by NE-turns is given by

∑_{P ∈L(A→E|R)} x^{runs(P)} = xF_{hh}(A → E | R; x^{2}) + x^{2}F_{hv}(A → E | R; x^{2})
+ F_{vh}(A → E | R; x^{2}) + xF_{vv}(A → E | R; x^{2}).

(3.34)

All the four refinements of the NE-turn generating function can be expressed in terms of NE-turn generating functions. This is seen by setting up a few linear equations and solving them. Evidently,

F (A → E | R; x) = F_{hh}(A → E | R; x) + F_{hv}(A → E | R; x)
+ F_{vh}(A → E | R; x) + F_{vv}(A → E | R; x).

Besides, if E_{1} = (1, 0) and E_{2} = (0, 1) denote the standard unit vectors, we have

F_{hh}(A → E | R; x) + F_{hv}(A → E | R; x) = F (A + E_{1} → E | R; x),
F_{hv}(A → E | R; x) + F_{vv}(A → E | R; x) = F (A → E − E_{2} | R; x),
F_{hv}(A → E | R; x) = F (A + E_{1} → E − E_{2} | R; x).

Solving for F_{hh}, F_{hv}, F_{vh} and F_{vv}, we get

F_{hh}(A → E | R; x) = F (A + E_{1} → E | R; x) − F (A + E_{1} → E − E_{2} | R; x),

(3.35)

F_{hv}(A → E | R; x) = F (A + E_{1} → E − E_{2} | R; x),  (3.36)
F_{vh}(A → E | R; x) = F (A → E | R; x) + (A + E_{1} → E − E_{2} | R; x)

− F (A + E_{1} → E | R; x) − F (A → E − E_{2} | R; x),

(3.37)

F_{vv}(A → E | R; x) = F (A → E − E_{2} | R; x) − F (A + E_{1} → E − E_{2} | R; x).

(3.38)

Now, turning to the joint distribution of runs and two-sided Kolmogorov-Smirnov statistics, we noted earlier that we have to count paths from (0, 0) to (n, n) staying between the lines y = x+t and y = x−t and which contain r runs. We do this by using (13.34) with A = (0, 0), E = (n, n), R meaning the property to ‘stay between y = x + t and y = x − t’, then using Eqs. (13.35)–(13.38) for F_{hh}, F_{hv}, F_{vh}, F_{vv}, respectively, in (13.34), and finally applying Theorem 13.4.4 to obtain explicit expansions for various generating functions F (…). A comparison of coefficients of powers of z then gives, after some manipulation of binomials:

For the joint distribution of runs, denoted by R_{n,n}, and the two-sided Kolmogorov–Smirnov statistics D_{n,n}, we have

\binom{2n}{n} Pr[D_{n,n} ≤ t/n, R_{n,n} = 2r + 1]

= ∑_{k=−∞}^{∞} \{\binom{n − 2kt − 1}{r + k}\binom{n + 2kt − 1}{r − k − 1} + \binom{n − 2kt − 1}{r + k − 1}\binom{n + 2kt − 1}{r − k}

−2\binom{n − 2kt + t − 1}{r + k − 1}\binom{n + 2kt − t − 1}{r − k}\},

and

\binom{2n}{n} Pr[D_{n,n} ≤ t/n, R_{n,n} = 2r]

= ∑_{k=−∞}^{∞} \{2\binom{n − 2kt − 1}{r + k − 1}\binom{n + 2kt − 1}{r − k − 1} − \binom{n − 2kt + t − 1}{r + k − 2}\binom{n + 2kt − 1}{r − k}

−\binom{n − 2kt + t − 1}{r + k − 1}\binom{n + 2kt − t − 1}{r − k − 1}\}.

Thus, we recover the results of Vellore (1972, Theorems 8 and 9). She derived these results by very different means. (The expressions therefore look differently. But it is not difficult to show that they are really equivalent.) The path of derivation we have chosen here is from Krattenthaler and Mohanty (1993) where it was also used to obtain extensions and q-analogues of the above result.

ad Example 13.3.3. By Theorems 13.3.1 and 13.3.2, the case of n = 1 in Example 13.3.3, i.e., the case of rings generated by (at most) 2 × 2 minors in the way described above, leads to the problem of enumerating paths with given starting and end points which have a given number of NE-turns. Clearly, this is done by (13.6).

Besides, we indicated that the case of pfaffian rings generated by 4 × 4 pfaffians leads to the enumeration of paths with given starting and end points which have a given number of NE-turns and stay below a diagonal line. Clearly, this is done by Theorem 13.4.1.

3.6 Nonintersecting Lattice Paths and Turns

Here, we complete the solutions to our Examples of Section 13.3. More precisely, we address the problem of enumerating nonintersecting lattice paths with a given number of NE-turns, which is the problem to be solved in order to compute Hilbert series of determinantal and pfaffian rings, as we described earlier in Example 13.3.3. If one forgets about the number of turns, i.e., if one is interested in the plain enumeration of nonintersecting lattice paths with given starting and end points, then the solution is a certain determinant. This is a classical result now [cf. Gessel and Viennot (1985 and 1989, Corollary 2); Stembridge (1990, Theorem 1.2)]. In fact, it has been realized over the past ten years that nonintersecting lattice paths have innumerable applications in combinatorics, probability, statistics, physics, etc. [see the references in Krattenthaler (1996b) for combinatorial applications, and the references in the Introduction for applications in physics and probability; in fact, most of the determinantal formulas in probability and statistics, like “Steck’s determinants” [Mohanty (1971), Pitman (1972) and Steck (1969, 1974)] follow easily from nonintersecting lattice paths; see also Sulanke (1990)]. However, the method that is used for the plain enumeration [the “Gessel–Viennot involution”, which actually can be traced back to Lindström (1973) and Karlin and McGregor (1959a)], is not appropriate to keep track of turns. Still, the answers to “turn enumeration” are determinants. But, alternative methods are needed now. It is the combinatorics of two-rowed arrays which explains these determinants. In fact, it is the context of nonintersecting lattice paths in which the usefulness of working with two-rowed arrays becomes most striking. Interestingly, the techniques developed here arose in the study of plane partition and tableaux generating functions [Krattenthaler (1995a)] and of identities for Schur functions [Krattenthaler (1993)].

From Theorems 13.3.1 and 13.3.2, we know for the computation of the Hilbert series for the determinantal rings R_{n+1}(X) and Ra,b_{n+1}(X) that we need to enumerate families P = (P_{1}, P_{2},…, P_{n}) of nonintersecting lattice paths, where P_{i} runs from (0, a_{n−i+1}) to (a−b_{n−i+1}, b), i = 1, 2,…, n, where the total number of NE-turns in P is some fixed number. Here, the starting points are lined up vertically and the end points are lined up horizontally. In fact, we are able to answer the problem even if the starting and end points are (basically) in general position. Let A = (A_{1}, A_{2},…, A_{n}) and E = (E_{1}, E_{2},…, E_{n}) be points in the two-dimensional integer lattice Z^{2}. The restriction on the location of the points which we have to impose is the one which is always necessary with nonintersecting lattice paths [see Gessel and Viennot (1989) and Stembridge (1990)]. Namely, we assume that the starting points are lined up north-west to south-east, strictly from north to south, and that the end points are also lined up north-west to south-east, but strictly from west to east. We have the following theorem.

Theorem 3.6.1 Let A_{i} = (a_{1}^{(i)}, a_{2}^{(i)}) and E_{i} = (e_{1}^{(i)}, e_{2}^{(i)}), i = 1, 2,…, n, be lattice points satisfying

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

and

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

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} : A_{i} → E_{i}, equals

det_{1≤i,j≤n} \{ ∑_{k≥0} \binom{e_{1}^{(i)} − a_{1}^{(j)} + j − i}{k + j − i}\binom{e_{2}^{(i)} − a_{2}^{(j)} − j + i}{k}z^{k}\}.  (3.39)

Remark 3.6.1 This theorem was independently proved by Kulkarni (1993), who derived it from a theorem on determinantal rings due to Abhyankar, by Modak (1992), who found a manipulatory proof, and for the first time by combinatorial means by Krattenthaler (1995b, 1996a), using two-rowed arrays. See also Ghorpade (1996).

Sketch of proof. If we want to prove this theorem by means of two-rowed arrays, we have to first work out how the condition of two paths to be nonintersecting translates into the corresponding two-rowed arrays.

Let P_{1}, P_{2} be two paths, P_{1} : A → E, P_{2} : B → F, where A = (a_{1}, a_{2}), B = (b_{1}, b_{2}), E = (e_{1}, e_{2}), F = (f_{1}, f_{2}), A located in the north-west of B (strictly in direction north and weakly in direction west), and E located in the north-west of F (weakly in direction north and strictly in direction west), i.e., with

a_{1} ≤ b_{1}, a_{2} > b_{2}, e_{1} < f_{1}, e_{2} ≥ f_{2}.

Let the array representations of P_{1} and P_{2} be

P_{1} :  \begin{aligned}a_{1} ≤ & p_{1} & … & p_{k} & ≤ e_{1} − 1 \\ a_{2} + 1 ≤ & q_{1} & … & q_{k} & ≤ e_{2} \end{aligned}  (3.40)

and

P_{2} :  \begin{aligned}b_{1} ≤ & r_{1} & … & r_{l} & ≤ f_{1} − 1 \\ b_{2} + 1 ≤ & s_{1} & … & s_{l} & ≤ f_{2}, \end{aligned}  (3.41)

respectively.

Suppose that P_{1} and P_{2} intersect, i.e. have a point in common. Let M be a meeting point of P_{1} and P_{2}. For technical reasons, set p_{k+1} := e_{1} and q_{0} := a_{2}. (Note that the thereby augmented sequences a and b remain strictly increasing.)

• • •^{M}^{(r_{J}, s_{J})} _{(p_{I}, q_{I−1})}  ^{P_{1}}  ^{P_{2}} Figure 3.5

Considering the east-north turn (p_{I}, q_{I−1}) in P_{1} immediately preceding M (and being allowed to be equal to M) and the north-east turn (r_{J}, s_{J}) in P_{2} immediately preceding M (and being allowed to be equal to M), we get the inequalities (cf. Figure 3.5)

r_{J} ≤ p_{I},  (3.42)
q_{I−1} ≤ s_{J},  (3.43)

where

1 ≤ I ≤ k + 1, 1 ≤ J ≤ l.  (3.44)

Of course, k, l, p_{I}, q_{I}, r_{J}, s_{J}, etc., refer to the array representations of P_{1} and P_{2}. It now becomes apparent that the above assignments for p_{k+1} and q_{0} are needed for the inequalities (13.42) and (13.43) to make sense for I = 1 or I = k + 1. Note that M = (p_{I}, s_{J}). Vice versa, if (13.42) – (13.44) are 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 (13.42) – (13.44) characterize the array representations of intersecting pairs of paths. Therefore, we call tworowed arrays P_{1} and P_{2} of the form (13.40) and (13.41), respectively, intersecting if (13.42) – (13.44) are satisfied, for some I and J, otherwise nonintersecting. The point M = (p_{I}, s_{J}) is called their intersection point.

We also need to consider skew two-rowed arrays. For convenience, we introduce some terminology. Let j > 0. We say that the two-rowed array P is of the type j if P has the form

\begin{aligned}p_{−j+1} & p_{−j+2} & … & p_{−1} & p_{0} & p_{1} & … & p_{k} \\ & & & & & q_{1} & … & q_{k} \end{aligned}

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

\begin{aligned}& & & & & p_{1} & … & p_{k} \\ q_{−j+1} & q_{−j+2} & … & q_{−1} & q_{0} & q_{1} & … & q_{k} \end{aligned}

for some k ≥ 0. Note that the placement of indices is chosen such that nonpositive indices can occur only in one row of P, while the positive indices occur in both rows of P. The meaning of non-skew two-rowed arrays being intersecting, and nonintersecting, and of intersection points, is extended to skew two-rowed arrays in the obvious way. In abuse of its actual literal meaning, we define the “number of NE-turns” of a two-rowed array P to be one half of the number of entries of P. (Recall that, under the correspondence between paths and two-rowed arrays, the number of NE-turns of the path equals one half of the number of entries of the corresponding two-rowed array.) We use the same short notation NE(P) for this number.

Now, we are in the position to actually begin with the proof of (13.39). First, we give the combinatorial interpretation of the determinant (13.39) in terms of two-rowed arrays. Expanding the determinant in (13.39), we obtain

∑_{σ∈S_{n}} sgn σ ∏_{i=1}^{n} \binom{e_{1}^{(i)} − a_{1}^{(σ(i))} + σ(i) − i}{k_{i} + σ(i) − i}\binom{e_{2}^{(i)} − a_{2}^{(σ(i))} − σ(i) + i}{k_{i}}z^{k_{i}}

= ∑_{(σ,P)} sgn σ z^{NE(P)},  (3.45)

where S_{n} denotes the symmetric group of order n, and the sum on the righthand side is over all pairs (P, σ) of permutations σ in S_{n}, and families P = (P_{1}, P_{2},…, P_{n}) of two-rowed arrays, P_{i} being of type σ(i) − i, and the bounds for the entries of P_{i} being as follows:

\begin{aligned}a_{1}^{(σ(i))} + i − σ(i) ≤ & … & p_{ℓ_{i}}^{(i)} & ≤ e_{1}^{(i)} − 1 \\ a_{2}^{(σ(i))} − i + σ(i) + 1 ≤ & … & q_{ℓ_{i}}^{(i)} & ≤ e_{2}^{(i)}, \end{aligned}  (3.46)

i = 1, 2,…, n.

The outline of the proof is as follows. We show that in the sum on the right-hand side of (13.45) all contributions corresponding to pairs (P, σ) where P is an intersecting family of two-rowed arrays cancel. (We call a pair (P, σ) intersecting if P = (P_{1}, P_{2},…, P_{n}) contains two two-rowed arrays P_{i} and P_{i+1} with consecutive indices that have an intersection point. Otherwise it is called nonintersecting. In the sequel, two-rowed arrays with consecutive indices will be called neighbouring two-rowed arrays.) This is done by constructing a signreversing (with respect to sgn σ) involution on these pairs, which keeps the total number of entries in the two-rowed arrays fixed. (Recall that, under the correspondence between paths and two-rowed arrays, the number of NE-turns of the path equals one half of the number of entries of the corresponding tworowed array.) Finally, it is shown that, in a pair (P, σ) with σ ≠ id, the family P must be intersecting. This establishes that only pairs (P, id) where P is a nonintersecting family of two-rowed arrays contribute to the sum on the righthand side of (13.45). But these pairs correspond exactly to the families of nonintersecting paths under consideration, and hence Theorem 13.6.1 would be proved.

Let (P, σ) be a pair under consideration for the sum on the right-hand side of (13.45). Besides, we assume that P contains two neighbouring two-rowed arrays P_{i} and P_{i+1} that have an intersection point. Consider all intersection points of neighbouring arrays. Among these points, choose those with maximal x-coordinate, and among all those choose the intersection point with maximal y-coordinate. Denote this intersection point by M. Let i be minimal such that M is an intersection point of P_{i} and P_{i+1}. Let P_{i} = (a | b) = (… p_{ℓ_{i}} | … q_{ℓ_{i}}) and P_{i+1} = (c | d) = (… r_{ℓ_{i+1}} | … s_{ℓ_{i+1}}). Recall that P_{i} is of type σ(i) − i and P_{i+1} is of type σ(i + 1) − i − 1 and that the bounds of the entries in P_{i} and P_{i+1} are determined by (13.46). By (13.42) – (13.44), M being an intersection point of P_{i} and P_{i+1} means that there exist I and J such that P_{i} looks like

\begin{aligned}a_{1}^{(σ(i))} + i − σ(i) ≤ & … & p_{I−1} & p_{I} & … & p_{ℓ_{i}} & ≤ e_{1}^{(i)} − 1 \\ a_{2}^{(σ(i))} − i + σ(i) + 1 ≤ & … & q_{I−1} & q_{I} & … & q_{ℓ_{i}} & ≤ e_{2}^{(i)}, \end{aligned}  (3.47)

P_{i+1} looks like

\begin{aligned}a_{1}^{(σ(i+1))} + i + 1 − σ(i + 1) ≤ & . . . . . . . . . & r_{J} & r_{J+1} & … & r_{ℓ_{i+1}} & ≤ e_{1}^{(i+1)} − 1 \\ a_{2}^{(σ(i+1))} − i + σ(i + 1) ≤ & … & s_{J−1} & s_{J} & . . . . . . . . . & s_{ℓ_{i+1}} & ≤ e_{2}^{(i+1)}, \end{aligned}

(3.48)

M = (p_{I}, s_{J}),

r_{J} ≤ p_{I}  (3.49)
q_{I−1} ≤ s_{J}  (3.50)

and

1 ≤ I ≤ ℓ_{i} + 1, 0 ≤ J ≤ ℓ_{i+1}.  (3.51)

Because of the construction of M, the indices I and J are maximal with respect to (13.49) – (13.51).

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

\begin{matrix}… & r_{J} − 1 & p_{I} & … & p_{ℓ_{i}} \\ … & s_{J−1} + 1 & q_{I} & … & q_{ℓ_{i}}, \end{matrix}  (3.52)

P̄_{i+1} being given by

\begin{matrix}… & … & p_{I−1} + 1 & r_{J+1} & … & r_{ℓ_{i+1}} \\ … & q_{I−1} − 1 & s_{J} & … & … & s_{ℓ_{i+1}}. \end{matrix}  (3.53)

First of all, this operation is well-defined, i.e., all the rows in (13.52) and (13.53) are strictly increasing. To see this, we have to check r_{J} − 1 < p_{I}, s_{J−1} + 1 < q_{I}, p_{I−1} + 1 < r_{J+1}, and q_{I−1} − 1 < s_{J}. This is obvious for the first and last inequalities, because of (13.49) and (13.50). As for the second inequality, let us suppose s_{J−1} + 1 ≥ q_{I}. Then, by (13.49), we have r_{J} ≤ p_{I} < p_{I+1} and q_{I} ≤ s_{J−1} + 1 ≤ s_{J}. This means that (p_{I+1}, s_{J}) is an intersection point of P_{i} and P_{i+1}, with an x-coordinate larger than that of M = (p_{I}, s_{J}), contradicting the “maximality” of M. Similarly, if we assume p_{I−1} + 1 ≥ r_{J+1}, we have r_{J+1} ≤ p_{I−1} + 1 ≤ p_{I} and, by (13.50), q_{I−1} ≤ s_{J} < s_{J+1}. This means that (p_{I}, s_{J+1}) is an intersection point of P_{i} and P_{i+1}, with a y-coordinate larger than that of M = (p_{I}, s_{J}), again contradicting the “maximality” of M.

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

\begin{aligned}a_{1}^{(σ(i+1))} + i − σ(i + 1) ≤ & … & r_{J} − 1 & p_{I} & … & p_{ℓ_{i}} & ≤ e_{1}^{(i)} − 1 \\ a_{2}^{(σ(i+1))} − i + σ(i + 1) + 1 ≤ & … & s_{J−1} + 1 & q_{I} & … & q_{ℓ_{i}} & ≤ e_{2}^{(i)}, \end{aligned} (3.54)

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

\begin{aligned}a_{1}^{(σ(i))} + i + 1 − σ(i) ≤ & … & … & p_{I−1} + 1 & r_{J+1} & … & r_{ℓ_{i+1}} & ≤ e_{1}^{(i+1)} − 1 \\ a_{2}^{(σ(i))} − i + σ(i) ≤ & … & q_{I−1} − 1 & s_{J} & … & … & s_{ℓ_{i+1}} & ≤ e_{2}^{(i+1)}. \end{aligned}

(3.55)

The claims concerning the types of P̄_{i} and P̄_{i+1} are trivial. The claim concerning the bounds requires some case-by-case analysis, which we leave to the reader. One may also refer to Krattenthaler (1995b, 1996a). Obviously, the map (13.52)

– (13.53) reverses the sign of the associated permutation. Besides, it can be checked that it is an involution. The proof that, given a pair (P, σ), P = (P_{1}, P_{2},…, P_{n}), σ ≠ id, there exist neighbouring two-rowed arrays P_{i} and P_{i+1} having an intersection point, is slightly technical. We refer the reader to Krattenthaler (1995b, 1996a) for the details.

Remark 3.6.2 The map from (13.47) and (13.48) to (13.52) and (13.53) can be considered as the analogue in the “world of two-rowed arrays” for the interchanging of paths which is usually done with nonintersecting lattice paths [see, for example, Gessel and Viennot (1985), Stembridge (1990), and Krattenthaler (1995a, Section 2.2)].

Another problem that is posed by Example 13.3.3 is the enumeration of families of nonintersecting lattice paths which are bounded by a diagonal line with respect to their number of turns. Recall that this is necessary for the computation of the Hilbert series of pfaffian rings and of ladder determinantal rings where the ladder restriction is a diagonal boundary. Also here, we have a result where the location of the starting and end points is more general than needed.

Theorem 3.6.2 Let A_{i} = (a_{1}^{(i)}, a_{2}^{(i)}) and E_{i} = (e_{1}^{(i)}, e_{2}^{(i)}), i = 1, 2,…, n, be lattice points satisfying

a_{1}^{(1)} ≤ a_{1}^{(2)} ≤ ⋯ ≤ a_{1}^{(n)}, a_{2}^{(1)} > a_{2}^{(2)} > ⋯ > a_{2}^{(n)},
e_{1}^{(1)} < e_{1}^{(2)} < ⋯ < e_{1}^{(n)}, e_{2}^{(1)} ≥ e_{2}^{(2)} ≥ ⋯ ≥ e_{2}^{(n)},

and a_{1}^{(i)} ≥ a_{2}^{(i)}, e_{1}^{(i)} ≥ e_{2}^{(i)}, i = 1, 2,…, n. 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} : A_{i} → E_{i}, which stay below the line x = y (being allowed to touch it), equals

det_{1≤i,j≤n} (\{ ∑_{k≥0} \binom{e_{1}^{(i)} − a_{1}^{(j)} + j − i}{k + j − i}\binom{e_{2}^{(i)} − a_{2}^{(j)} − j + i}{k}

−\binom{e_{1}^{(i)} − a_{2}^{(j)} − j − i + 1}{k − i}\binom{e_{2}^{(i)} − a_{1}^{(j)} + j + i − 1}{k + j}\}z^{k}).

(3.56)

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

\begin{aligned}a_{1}^{(σ(i))} + i − σ(i) ≤ & … & ≤ e_{1}^{(i)} − 1 \\ a_{2}^{(σ(i))} − i + σ(i) + 1 ≤ & … & ≤ e_{2}^{(i)} \end{aligned} ,  for η = 1,  (3.57)

and

\begin{aligned}a_{2}^{(σ(i))} + i + σ(i) − 1 ≤ & … & ≤ e_{1}^{(i)} − 1 \\ a_{1}^{(σ(i))} − i − σ(i) + 2 ≤ & … & ≤ e_{2}^{(i)} \end{aligned} ,  for η = −1.  (3.58)

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

∑_{(P,σ,η)} sgn η sgn σ z^{NE(P)},  (3.59)

where the sum is over all triples which have been described above.

Now, the basic idea is as follows. We show that in the sum (13.59) all contributions cancel which correspond to triples (P, σ, η), where P is an intersecting family of two-rowed arrays, or where the two-rowed array P_{1} “crosses” y = x, by which we mean that there is an entry in the upper row of P_{1} which is smaller than its neighbour in the bottom row of P_{1}. Again, this is done by constructing a sign-reversing involution (with respect to sgn η sgn σ) on those triples. Roughly described, this involution combines the “reflection principle for two-rowed arrays” with the “interchanging procedure for two-rowed arrays”. Namely, this involution is defined to be the map (13.47) and (13.48) to (13.52) and (13.53) if P contains neighbouring two-rowed arrays which are intersecting, and if not, but the first two-rowed array P_{1} “crosses” y = x, then it is defined to be basically the map (13.13), applied to P_{1}. It can be shown that in a triple (P, σ, η) with σ ≠ id or η ≠ (1, 1,…, 1), the family P must be intersecting or P_{1} “crosses y = x”. This establishes that only triples (P, id, (1, 1,…, 1)), where P is a nonintersecting family of two-rowed arrays which do not cross y = x, contribute to the sum (13.59). But these triples exactly correspond to the families of nonintersecting paths under consideration, and hence Theorem 13.6.2 would be proved. We refer the reader to Krattenthaler (1995b, 1996a) for the details.

As mentioned before, Theorem 13.6.2 can be applied to the computation of the Hilbert series of certain ladder determinantal rings (one sided, with a diagonal upper bound) and also of pfaffian rings. The computation of Hilbert series of rings generated by minors of a symmetric matrix as considered by Conca (1994) can also be solved by using the method of two-rowed arrays; see Krattenthaler (1996a). For arbitrary one-sided ladders, there is a solution when the starting points, and end points, are located “successively” (such as in Figure 3.4) by Krattenthaler and Prohaska (1996) proving a remarkable formula conjectured by Conca and Herzog (1994). For “generally” located starting and end points, there is a solution in terms of a determinant with entries counting certain two-rowed arrays by Krattenthaler (1996a). The case of two-sided ladder determinantal rings appears to be out of reach by the method of two-rowed arrays. Perhaps, the extension of the dummy path idea in Krattenthaler and Mohanty (1995) will be useful in this context. Finally, we want to point the reader to a refined turn counting for pairs of paths [Krattenthaler and Sulanke (1996)] which relates this subject also to polyomino counting.

References

Abhyankar, S. S. (1987). Determinantal loci and enumerative combinatorics of Young tableaux, In Algebraic Geometry and Commutative Algebra in honor of M. Nagata, pp. 1-26.

Abhyankar, S. S. (1988). Enumerative Combinatorics of Young Tableaux, New York: Marcel Dekker.

Abhyankar, S. S. and Kulkarni, D. M. (1989). On Hilbertian ideals, Linear Algebra and its Applications, 116, 53-76.

Burge, W. H. (1993). Restricted partition pairs,Journal of Combinatorial Theory, Series A, 63, 210-222.

Comtet, L. (1974). Advanced Combinatorics, Dordrecht: Reidel.

Conca, A. (1994). Symmetric ladders, Nagoya Mathematical Journal, 136, 35-56.

Conca, A. and Herzog, J. (1994). On the Hilbert function of determinantal rings and their canonical module, Proceedings of the American Mathematical Society, 122, 677-681.

DeGroot, M. H. (1959). Unbiased sequential estimation for binomial populations, Annals of Mathematical Statistics, 30, 80-101.

Essam, J. W. and Guttmann, A. J. (1995). Vicious walkers and directed polymer networks in general dimensions, Physical Review E, 52, 5849-5862.

Fisher, M. E. (1984). Walks, walls, wetting, and melting, Journal of Statistical Physics, 34, 667-729.

Gessel, I. M. and Krattenthaler, C. (1996). Cylindric partitions, Transactions of the American Mathematical Society (to appear).

Gessel, I. M. and Viennot, X. (1985). Binomial determinants, paths, and hook length formulae, Advances in Mathematics, 58, 300-321.

Gessel, I. M. and Viennot, X. (1989). Determinants, paths, and plane partitions, Preprint.

Ghorpade, S. R. (1996). Young bitableaux, lattice paths and Hilbert functions, Journal of Statistical Planning and Inference 54, 55-66.

Ghorpade, S. R. and Krattenthaler, C. (1996). On pfaffian ideals, Preprint.

Herzog, J. and Trung, N. V. (1992). Gröbner bases and multiplicity of determinantal and Pfaffian ideals, Advances in Mathematics, 96, 1-37.

Karlin, S. (1988). Coincident probabilities and applications in combinatorics, Journal of Applied Probability, 25, 185-200.

Karlin, S. and McGregor, J. L. (1959a). Coincidence probabilities, Pacific Journal of Mathematics, 9, 1141-1164.

Karlin, S. and McGregor, J. L. (1959b). Coincidence properties of birth-and-death processes, Pacific Journal of Mathematics, 9, 1109-1140.

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

Krattenthaler, C. (1993). Non-crossing two-rowed arrays and summations for Schur functions, In Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics, Florence, 1993 (Eds., A. Barlotti, M. Delest and R. Pinzani), pp. 301-314, Università di Firenze: D.S.I.

Krattenthaler, C. (1995a). The Major Counting of Nonintersecting Lattice Paths and Generating Functions for Tableaux, Providence, Rhode Island: Memoirs of the American Mathematical Society, 115.

Krattenthaler, C. (1995b). Counting nonintersecting lattice paths with respect to weighted turns, Seminaire Lotharingien Combin., 34, paper B34i, 17 pp.

Krattenthaler, C. (1996a). Non-crossing two-rowed arrays, Preprint.

Krattenthaler, C. (1996b). Nonintersecting lattice paths and oscillating tableaux, Journal of Statistical Planning and Inference 54, 75-85.

Krattenthaler, C. and Prohaska, M. (1996). A remarkable formula for counting nonintersecting lattice paths in a ladder with respect to turns, Transactions of the American Mathematical Society (to appear).

Krattenthaler, C. and Mohanty, S. G. (1993). On lattice path counting by major and descents, European Journal of Combinatorics, 14, 43-51.

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

Krattenthaler, C. and Sulanke, R. A. (1996). Counting pairs of nonintersecting lattice paths with respect to weighted turns, Discrete Mathematics 153, 189-198.

Kulkarni, D. M. (1993). Hilbert polynomial of a certain ladder-determinantal ideal, Journal of Algebraic Combinatorics, 2, 57-72.

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

Lindström, B. (1973). On the vector representations of induced matroids, Bulletin of the London Mathematical Society, 5, 85-90.

Modak, M. R. (1992). Combinatorial meaning of the coefficients of a Hilbert polynomial, Proceedings of the Indian Academy of Science (Mathematical Sciences), 102, 93-123.

Mohanty, S. G. (1966). On a generalised two-coin tossing problem, Biometrische Zeitschrift, 8, 266-272.

Mohanty, S. G. (1971). A short proof of Steck’s result on two-sample Smirnov statistics, Annals of Mathematical Statistics, 42, 413-414.

Mohanty, S. G. (1979). Lattice Path Counting and Applications, New York: Academic Press.

Narayana, T. V. (1959). A partial order and its applications to probability theory, Sankhyā, 21, 91-98.

Narayana, T. V. (1979). Lattice path combinatorics with statistical applications, Mathematical Statistics Expositions, No. 23, Toronto: University of Toronto Press.

Niederhausen, H. (1996). Symmetric Sheffer sequences and their applications to lattice path counting, Journal of Statistical Planning and Inference 54, 87-100.

Pitman, E. J. G. (1972). Simple proofs of Steck’s determinantal expressions for probabilities in the Kolmogorov and Smirnov tests, Bulletin of the Astralian Mathematical Society, 7, 227-232.

Steck, G. P. (1969). The Smirnov tests as rank tests, Annals of Mathematical Statistics, 40, 1449-1466.

Steck, G. P. (1974). A new formula for P (R_{i} ≤ b_{i}, 1 ≤ i ≤ m | m, n, F = G^{k}), Annals of Probability, 2, 155-160.

Stembridge, J. R. (1990). Nonintersecting paths, pfaffians and plane partitions, Advances in Mathematics, 83, 96-131.

Sulanke, R. A. (1990). A determinant for q-counting lattice paths, Discrete Mathematics, 81, 91-96.

Vellore, S. (1972). Joint distributions of Kolmogorov–Smirnov statistics and runs, Studia Scientiarum Mathematica Hungarica, 7, 155-165.