ON LATTICE PATH COUNTING BY MAJOR AND DESCENTS

C. Krattenthaler S. G. Mohanty

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

McMaster University, Hamilton, Ontario, Canada L8S 4K1

Abstract. A formula for counting lattice paths in the plane from μ = (μ_{1}, μ_{2}) to λ = (λ_{1}, λ_{2}) which do not cross the lines y = x + d and y = x + c, where c, d ∈ ℤ and d > c, by descents and major index is given. The proof, which is purely combinatorial, uses a bijection on certain two–rowed tableaux. As application, formulas for the joint distribution of Kolmogorov–Smirnov and run statistics are derived.

1. Introduction. In this paper we consider lattice paths in the plane consisting of unit horizontal and vertical steps in the positive direction. In the sequel we shall call them shortly paths.

The number of paths from μ = (μ_{1}, μ_{2}) to λ = (λ_{1}, λ_{2}), λ, μ ∈ ℤ^{2}, which do not cross the lines y = x + d and y = x + c, where c, d ∈ ℤ and d > c, is

(1.1) ∑_{k∈ℤ} \{\binom{λ_{1} + λ_{2} − μ_{1} − μ_{2}}{λ_{1} − μ_{1} − k(d − c + 2)} − \binom{λ_{1} + λ_{2} − μ_{1} − μ_{2}}{λ_{1} − μ_{2} + k(d − c + 2) + c − 1}\} ,

provided λ_{1} + c ≤ λ_{2} ≤ λ_{1} + d and μ_{1} + c ≤ μ_{2} ≤ μ_{1} + d. This is easily proved by iterated reflection (cf. [9, pp. 6,7,121] for the proof and statistical applications).

In Theorem 1 below, we generalize this result to counting lattice paths by major and descents, thus continuing previous work of one of the authors [3,4,5]. First we give the relevant definitions.

The major index (or “greater index”) of a multiset permutation π = π_{1}π_{2} … π_{n}, π_{i} ∈ ℕ_{0} (set of nonnegative integers), is defined by

maj π = ∑_{i=1}^{n−1} i · χ(π_{i} > π_{i+1}) .

1980 Mathematics Subject Classification (1991 Revision). Primary 05A15; Secondary 05A10, 05A17, 05A30, 62G30..

Key words and phrases. Lattice paths, major index, descents, runs, turns, Kolmogorov–Smirnov statistics.

(χ(A) = 1 if A is true, and χ(A) = 0 otherwise.) McMahon [7] was the first to consider major counting. He was led to introduce this notion, while investigating the problem of finding generating functions for plane partitions.

A pair π_{i}π_{i+1} with π_{i} > π_{i+1} is called a descent of π. The number of descents of π,

des π = ∑_{i=1}^{n−1} χ(π_{i} > π_{i+1}) ,

is another important statistics on multiset permutations. Stanley [10] showed that maj and des are crucial for the computation of partition generating functions.

Any path in a natural way corresponds to a multiset permutation consisting of 0’s and 1’s. Let p be a path from μ to λ. p may be represented by a pair (μ, π), where μ is the starting point of p and π = π_{1}π_{2} … π_{λ_{1}+λ_{2}−μ_{1}−μ_{2}}, where π_{i} = 0 if the i’th step in the path p is a horizontal one and π_{i} = 1 if the i’th step in the path p is a vertical one. π is a multiset permutation consisting of λ_{1} −μ_{1} entries of 0 and λ_{2} −μ_{2} entries of 1. For example, the path in Figure 1 is represented by ((0, 0), 100100). Of course, this representation of paths is unique. Hence, we may identify each path with its representation. Given a path p = (μ, π), we extend maj and des to p by defining maj p := maj π and des p := des π.

•• • •• • •

Figure 1

Now we are able to formulate the generalization of formula (1.1) to counting by maj and des.

Theorem 1. Given c, d ∈ ℤ, d > c, let L_{c,d}^{+}(λ, μ) be the set of all lattice paths from μ = (μ_{1}, μ_{2}) to λ = (λ_{1}, λ_{2}) which do not cross the lines y = x+d and y = x+c. If λ_{1} + c ≤ λ_{2} ≤ λ_{1} + d and μ_{1} + c ≤ μ_{2} ≤ μ_{1} + d, then

(1.2) ∑_{p∈L_{c,d}^{+}(λ,μ)} x^{des p}q^{maj p}

= ∑_{n≥0} x^{n} ∑_{k∈ℤ} q^{n^{2}+k^{2}(d−c+1)−k(1−c+μ_{2}−μ_{1})}

× ([ \begin{matrix}λ_{1} − μ_{1} − k(d − c) \\ n + k \end{matrix} ] [ \begin{matrix}λ_{2} − μ_{2} + k(d − c) \\ n − k \end{matrix} ]

− [ \begin{matrix}λ_{2} − μ_{1} − k(d − c) − c + 1 \\ n + k \end{matrix} ] [ \begin{matrix}λ_{1} − μ_{2} + k(d − c) + c − 1 \\ n − k \end{matrix} ]) ,

where [ \begin{matrix}a \\ b \end{matrix} ] is the Gaussian binomial coefficient

[ \begin{matrix}a \\ b \end{matrix} ] = (1 − q^{a})(1 − q^{a−1}) ⋯ (1 − q^{a−b+1})/(1 − q^{b})(1 − q^{b−1}) ⋯ (1 − q).

Previous results of McMahon [8, p.1429] and of one of the authors [4, Theorems 5-7] are special cases of this theorem.

In the next section we give the proof of Theorem 1, which essentially is an extension of iterated reflection. It is inspired by a correspondence on tableaux which was used in [6] for the computation of plane partition generating functions. In section 3 special cases of Theorem 1 are discussed. We derive a formula for counting lattice paths only bounded by a single line by maj and des (Corollary 2). q–Vandermonde summation [1, 3.3.10] is used to obtain formulas for the maj–counting in the two and one boundary case, respectively (Corollaries 3 and 4). Finally, we give an application of our formulas to counting lattice paths by their number of turns. Thus, we provide an alternative proof for the expressions for the joint distribution of run statistics and (one- and two-sided) Smirnov statistics, which were earlier obtained by Vellore [11].

2. Proof of Theorem 1. Any path p from μ to λ may be represented by an array

(2.1)  \begin{matrix}a_{n} & a_{n−1} & … & a_{1} \\ b_{n} & b_{n−1} & … & b_{1} & , \end{matrix}

where n is equal to des p, the number of descents of p, a_{i} is equal to the x–coordinate of the i’th descent of p, and b_{i} is the y–coordinate of the i’th descent of p. More precisely, if p = (μ, π) and π_{ν}π_{ν+1} is the i’th descent of π, then

a_{i} = μ_{1} + |{j : π_{j} = 0 and j ≤ ν}|

and

b_{i} = μ_{2} + |{j : π_{j} = 1 and j ≤ ν}| .

For example, the path in Figure 1 would be represented by

2 0 2 1 .

We shall frequently use the short notation (a | b), where a = (a_{n}, a_{n−1}, …, a_{1}) and b = (b_{n}, b_{n−1}, …, b_{1}), for an array of the form (2.1). By definition, for a path p which is represented by (a | b) we have

(2.2)  a_{i} < a_{i+1}, μ_{1} ≤ a_{i} ≤ λ_{1} − 1 ,

and

(2.3)  b_{i} < b_{i+1}, μ_{2} + 1 ≤ b_{i} ≤ λ_{2} .

Besides, if p ∈ L_{c,d}^{+}(λ, μ), then the inequalities

(2.4)  b_{i} ≤ a_{i} + d for i = n, n − 1, …, 1

and

(2.5)  b_{i} ≥ a_{i+1} + c for i = n, n − 1, …, 1, 0 ,

with the conventions a_{n+1} := λ_{1} and b_{0} := μ_{2}, hold. In turn, given a double–array of the form (2.1), which satisfies (2.2)–(2.5), there is a uniquely determined path p ∈ L_{c,d}^{+}(λ, μ), which corresponds to this array.

If we let w(a | b) := ∑_{i} a_{i} +∑_{i} b_{i}, then, obviously, for a path p with representation (a | b) the equation

maj p = w(a | b) − n(μ_{1} + μ_{2})

is true. Therefore, in order to prove Theorem 1, we have to show that the generating function ∑ q^{w(a|b)}, where the sum is over all (a | b), a = (a_{n}, …, a_{1}) and b = (b_{n}, …, b_{1}), which satisfy (2.2)–(2.5), is equal to

(2.6) ∑_{k∈ℤ} q^{n(μ_{1}+μ_{2})+n^{2}+k^{2}(d−c+1)−k(1−c+μ_{2}−μ_{1})}

× ([ \begin{matrix}λ_{1} − μ_{1} − k(1 − c) \\ n + k \end{matrix} ] [ \begin{matrix}λ_{2} − μ_{2} + k(d − c) \\ n − k \end{matrix} ]

− [ \begin{matrix}λ_{2} − μ_{1} − k(d − c) − c + 1 \\ n + k \end{matrix} ] [ \begin{matrix}λ_{1} − μ_{2} + k(d − c) + c − 1 \\ n − k \end{matrix} ]) .

First we introduce some more sets of double–arrays. For k ∈ ℤ let L_{c,d}^{(1)}(λ, μ; k) denote the set of all “skew” arrays of the form

(2.7)(a)  \begin{aligned}a_{n+k} … & a_{n−k} & … & a_{1} \\ & b_{n−k} & … & b_{1} \end{aligned}  for k ≥ 0

and

(2.7)(b)  \begin{aligned}& a_{n+k} & … & a_{1} \\ b_{n−k} … & b_{n+k} & … & b_{1} \end{aligned}  for k < 0

satisfying a_{i+1} > a_{i} and b_{i+1} > b_{i}, and

(2.8)  \begin{aligned}μ_{1} ≤ & a_{i} & ≤ λ_{1} − k(d − c) − 1 \\ μ_{2} + 1 ≤ & b_{i} & ≤ λ_{2} + k(d − c) . \end{aligned}

Analogously, for k ∈ ℤ let L_{c,d}^{(2)}(λ, μ; k) denote the set of all arrays of the form (2.7) satisfying a_{i+1} > a_{i} and b_{i+1} > b_{i}, and

(2.9)  \begin{aligned}μ_{1} & ≤ a_{i} & ≤ λ_{2} − k(d − c) − c \\ μ_{2} + 1 & ≤ b_{i} & ≤ λ_{1} + k(d − c) + c − 1 . \end{aligned}

Note that L_{c,d}^{+}(λ, μ) is a subset of L_{c,d}^{(1)}(λ, μ; 0), if we identify each path with its representing array. Let L_{c,d}^{−}(λ, μ) be the set difference

L_{c,d}^{(1)}(λ, μ; 0)\L_{c,d}^{+}(λ, μ) .

L_{c,d}^{−}(λ, μ) is the set of all arrays of the form (2.1) with rows decreasing, such that either condition (2.4) or condition (2.5) is violated. We extend the weight w to arrays (a^{(n+k)} | b^{(n−k)}) of the form (2.7), with a^{(n+k)} = (a_{n+k}, …, a_{1}) and b^{(n−k)} = (b_{n−k}, …, b_{1}), by

(2.10)  w(a^{(n+k)} | b^{(n−k)}) = k^{2}d − (k^{2} − k)c + ∑_{i} a_{i} + ∑_{i} b_{i} .

Next we construct a weight–preserving involution φ on the set

L_{c,d} = ⋃_{k∈ℤ}(L_{c,d}^{(1)}(λ, μ; k) ∪ L_{c,d}^{(2)}(λ, μ; k))\L_{c,d}^{+}(λ, μ) .

Given an element (a^{(n+k)} | b^{(n−k)}) of L_{c,d}, let J be the smallest nonnegative integer such that either

(I)  b_{J} < a_{J+1} + c or J = n + k + 1

or

(II)  b_{J} > a_{J} + d or J = n − k + 1 .

Note that in (I) the choice J = 0 would be legal while in (II) it would be not (cf. the convention after (2.5)). For any (a^{(n+k)} | b^{(n−k)}) ∈ L_{c,d} it is possible to find such a J, because if b_{i} ≤ a_{i} + d and b_{i} ≥ a_{i+1} + c is satisfied for all i = 1, 2, …, n − |k|, then for k > 0 we have J = n − k + 1 and for k < 0 we have J = n + k + 1. In the case k = 0 there must be a J, J ≤ n, with either b_{J} > a_{J} + d or b_{J} < a_{J+1} + c, since any element (a^{(n)} | b^{(n)}) of L_{c,d} belongs to L_{c,d}^{−}(λ, μ).

The map φ is defined as follows: If (a^{(n+k)} | b^{(n−k)}) is the array

\begin{aligned}a_{n+k} … & a_{n−k} … a_{J+1} & a_{J} & … & a_{1} \\ & b_{n−k} … b_{J+1} & b_{J} & … & b_{1} & , \end{aligned}

where J is the above defined uniquely determined integer, then, if condition (I) holds, φ(a^{(n+k)} | b^{(n−k)}) is defined by

(2.11)  \begin{aligned}& (b_{n−k} − c) & … & (b_{J+1} − c) & a_{J} & … & a_{1} \\ (a_{n+k} + c) … & (a_{n−k} + c) & … & (a_{J+1} + c) & b_{J} & … & b_{1} & , \end{aligned}

if condition (I) does not hold (but, hence, condition (II) does), φ(a^{(n+k)} | b^{(n−k)}) is defined by

(2.12)  \begin{aligned}& (b_{n−k} − d) & … & (b_{J} − d) & a_{J} & a_{J−1} & … & a_{1} \\ (a_{n+k} + d) … & (a_{n−k+2} + d) & … & (a_{J+2} + d) & (a_{J+1} + d) & b_{J−1} & … & b_{1} & . \end{aligned}

More precisely, the arrray (A^{(n−k)} | B^{(n+k)}) in (2.11) is given by

A_{i} = \{ \begin{matrix}a_{i} & 1 ≤ i ≤ J \\ b_{i} − c & J < i ≤ n − k \end{matrix}

and

B_{i} = \{ \begin{matrix}b_{i} & 1 ≤ i ≤ J \\ a_{i} + c & J < i ≤ n + k , \end{matrix}

while the array (C^{(n−k+1)} | D^{(n+k−1)}) in (2.12) is given by

C_{i} = \{ \begin{matrix}a_{i} & 1 ≤ i ≤ J \\ b_{i−1} − d & J < i ≤ n − k + 1 \end{matrix}

and

D_{i} = \{ \begin{matrix}b_{i} & 1 ≤ i < J \\ a_{i+1} + d & J ≤ i ≤ n + k − 1 . \end{matrix}

One can readily verify the following properties of φ:

(1) If (a^{(n+k)} | b^{(n−k)}) ∈ L_{c,d}^{(i)}(λ, μ; k), i = 1, 2, and φ(a^{(n+k)} | b^{(n−k)}) is given by

(2.11), then φ(a^{(n+k)} | b^{(n−k)}) ∈ L_{c,d}^{(3−i)}(λ, μ; −k).

(2) If (a^{(n+k)} | b^{(n−k)}) ∈ L_{c,d}^{(i)}(λ, μ; k), i = 1, 2, and φ(a^{(n+k)} | b^{(n−k)}) is given by

(2.12), then φ(a^{(n+k)} | b^{(n−k)}) ∈ L_{c,d}^{(3−i)}(λ, μ; −k + 1).

(3) φ is an involution on L_{c,d}.

(4) φ is weight–preserving with respect to the weight w given in (2.10). Items (1)–(4) imply the generating function identity

(2.13) _{∑_{k∈ℤ} ; k≠0} ∑_{p∈L_{c,d}^{(1)}(λ,μ;k)} q^{w(p)} + ∑_{p∈L_{c,d}^{−}(λ,μ,k)} q^{w(p)} =

= ∑_{k∈ℤ} ∑_{p∈L_{c,d}^{(2)}(λ,μ;k)} q^{w(p)} .

Besides, by definition we have

(2.14)  ∑_{p∈L_{c,d}^{−}} q^{w(p)} = ∑_{p∈L_{c,d}^{(1)}(λ,μ;0)} q^{w(p)} − ∑_{p∈L_{c,d}^{+}(λ,μ)} q^{w(p)} .

Obviously, because of (2.10) the generating function

∑_{p∈L_{c,d}^{(1)}(λ,μ;k)} q^{w(p)}

is equal to q^{k^{2}d−(k^{2}−k)c} times the product of two partition generating functions, namely the generating function for all (linear) partitions with (n + k) distinct parts, each part at least μ_{1} and at most λ_{1} − 1 − k(d − c) times the generating function for all partitions with (n − k) distinct parts, each part at least (μ_{2} + 1) and at most λ_{2} + k(d − c). Therefore, by applying the classical result [1, Theorem 3.1] for the generating function for linear partitions, we obtain

(2.15) ∑_{p∈L_{c,d}^{(1)}(λ,μ;k)} q^{w(p)} = q^{N(k)} [ \begin{matrix}λ_{1} − μ_{1} − k(d − c) \\ n + k \end{matrix} ] [ \begin{matrix}λ_{2} − μ_{2} + k(d − c) \\ n − k \end{matrix} ] ,

where

N(k) = k^{2}d − (k^{2} − k)c + ( \begin{matrix}n + k \\ 2 \end{matrix} ) + ( \begin{matrix}n − k \\ 2 \end{matrix} ) + μ_{1}(n + k) + (μ_{2} + 1)(n − k) .

Analogously, we get

(2.16) ∑_{p∈L_{c,d}^{(2)}(λ,μ;k)} q^{w(p)}

= q^{N(k)} [ \begin{matrix}λ_{2} − μ_{1} − k(d − c) − c + 1 \\ n + k \end{matrix} ] [ \begin{matrix}λ_{1} − μ_{2} + k(d − c) + c − 1 \\ n − k \end{matrix} ] .

Finally, substitution of (2.14)–(2.16) into (2.13) yields (2.6), which is equivalent to Theorem 1.

3. Special cases and applications. In this section we discuss some special choices of the parameters occuring in Theorem 1.

If we choose c = μ_{2} − λ_{1} in Theorem 1, the terms with k ∉ {0, 1} vanish. Besides, any path from μ = (μ_{1}, μ_{2}) to λ = (λ_{1}, λ_{2}) cannot cross the line y = x+μ_{2} −λ_{1}. Thus we obtain the result for lattice path counting by maj and des for the one boundary case.

Corollary 2. Given d ∈ ℤ, let L_{d}^{+}(λ, μ) be the set of all lattice paths from μ = (μ_{1}, μ_{2}) to λ = (λ_{1}, λ_{2}) not crossing the line y = x+d. If λ_{2} ≤ λ_{1} +d and μ_{2} ≤ μ_{1} +d, then

(3.1) ∑_{p∈L_{d}^{+}(λ,μ)} x^{des p}q^{maj p}

= ∑_{n≥0} x^{n}q^{n^{2}} ([ \begin{matrix}λ_{1} − μ_{1} \\ n \end{matrix} ] [ \begin{matrix}λ_{2} − μ_{2} \\ n \end{matrix} ]

−q^{μ_{1}−μ_{2}+d} [ \begin{matrix}λ_{2} − μ_{1} − d + 1 \\ n + 1 \end{matrix} ] [ \begin{matrix}λ_{1} − μ_{2} + d − 1 \\ n − 1 \end{matrix} ]) .

This result solves the problem put in [4, section 5, Remark (6)].

If in Theorem 1 or Corollary 2, respectively, x is set equal to 1, we obtain lattice path counting results for maj–counting. By q–Vandermonde summation [1, 3.3.10] the summation over n admits a closed form, as well in the two boundary case as in the one boundary case. For the two boundary case we get:

Corollary 3. With the assumptions of Theorem 1, we have

(3.2) ∑_{p∈L_{c,d}^{+}(λ,μ)} q^{maj p} = ∑_{k∈ℤ} q^{k^{2}(d−c+2)−k(1−c+μ_{2}−μ_{1})}

× ([ \begin{matrix}λ_{1} + λ_{2} − μ_{1} − μ_{2} \\ λ_{1} − μ_{1} − k(d − c + 2) \end{matrix} ] − [ \begin{matrix}λ_{1} + λ_{2} − μ_{1} − μ_{2} \\ λ_{1} − μ_{2} + k(d − c + 2) + c − 1 \end{matrix} ]) .

The corresponding result for the one boundary case reads:

Corollary 4. With the assumptions of Corollary 2, we have

(3.3) ∑_{p∈L_{d}^{+}(λ,μ)} q^{maj p}

= [ \begin{matrix}λ_{1} + λ_{2} − μ_{1} − μ_{2} \\ λ_{1} − μ_{1} \end{matrix} ] − q^{μ_{1}−μ_{2}+d+1} [ \begin{matrix}λ_{1} + λ_{2} − μ_{1} − μ_{2} \\ λ_{1} − μ_{2} + d + 1 \end{matrix} ] .

The last result was previously shown in [4, (5.36)]. The other generating function identities in section 5 of [4] are also special cases of Theorem 1.

Next we want to reformulate Theorem 1 into a theorem about counting lattice paths with respect to major and their number of turns. A turn in a lattice path is any vertex of the lattice path where the direction of the path changes. In the example given in Figure 1 there are turns at (0, 1), (2, 1) and (2, 2). Let t(p) denote the number of turns of a lattice path p.

In order to obtain an expression for the generating function ∑ x^{t(p)}q^{maj p}, where the sum is over all paths p being an element of L_{c,d}^{+}(λ, μ), we need some more notation. Let F (λ, μ; x) denote the generating function ∑ x^{des p}q^{maj p}, where the sum is over all paths p of L_{c,d}^{+}(λ, μ). Let F_{01}(λ, μ; x) denote the generating function ∑ x^{des p}q^{maj p}, where the sum is over all paths p of L_{c,d}^{+}(λ, μ) starting with a horizontal edge and ending with a vertical one. F_{00}(λ, μ; x), F_{10}(λ, μ; x), and F_{11}(λ, μ; x) are defined analogously. Obviously, the following equation holds,

(3.4)  F_{00}(λ, μ; x) + F_{01}(λ, μ; x) + F_{10}(λ, μ; x) + F_{11}(λ, μ; x) = F (λ, μ; x) .

Since for any multiset permutation π (consisting only of 0’s and 1’s) we have

des(0π) = des π

and maj(0π) = maj π + des π ,

we obtain

(3.5)  F_{00}(λ, μ; x) + F_{01}(λ, μ; x) = F (λ, μ + e_{1}; qx) ,

where e_{1} = (1, 0). Similarly, if e_{2} = (0, 1), we get

(3.6)  F_{01}(λ, μ; x) + F_{11}(λ, μ; x) = F (λ − e_{2}, μ; x) ,

and

(3.7)  F_{01}(λ, μ; x) = F (λ − e_{2}, μ + e_{1}; qx) .

Equations (3.4)–(3.7) yield

(3.8)  F_{00}(λ, μ; x) = F (λ, μ + e_{1}; qx) − F (λ − e_{2}, μ + e_{1}; qx)
F_{01}(λ, μ; x) = F (λ − e_{2}, μ + e_{1}; qx)
F_{10}(λ, μ; x) = F (λ, μ; x) + F (λ − e_{2}, μ + e_{1}; qx)
− F (λ, μ + e_{1}; qx) − F (λ − e_{2}, μ; x)
F_{11}(λ, μ; x) = F (λ − e_{2}, μ; x) − F (λ − e_{2}, μ + e_{1}; qx) .

Simple considerations show that

(3.9) ∑_{p∈L_{c,d}^{+}(λ,μ)} x^{t(p)} = F_{00}(λ, μ; x^{2}) + xF_{01}(λ, μ; x^{2})

+ \frac{1}{x}F_{10}(λ, μ; x^{2}) + F_{11}(λ, μ; x^{2}) .

Now we are in the position to formulate our path counting formula.

Theorem 5. Let

K_{1} = λ_{1} − μ_{1} − k(d − c) − 1
K_{2} = λ_{2} − μ_{2} + k(d − c) − 1
K_{3} = λ_{2} − μ_{1} − k(d − c) − c − 1
K_{4} = λ_{1} − μ_{2} + k(d − c) + c − 1 .

With the assumptions of Theorem 1, we have

(3.10)  ∑_{p∈L_{c,d}^{+}(λ,μ)} x^{t(p)}q^{maj p} = ∑_{n≥0} x^{2n}A_{n} + ∑_{n≥0} x^{2n−1}B_{n} ,

where

(3.11) A_{n} = ∑_{k∈ℤ} q^{M(k)} (q^{K_{2}+2k+1} [ \begin{matrix}K_{1} \\ n + k \end{matrix} ] [ \begin{matrix}K_{2} \\ n − k − 1 \end{matrix} ]

+ [ \begin{matrix}K_{1} \\ n + k − 1 \end{matrix} ] [ \begin{matrix}K_{2} \\ n − k \end{matrix} ] − (1 + q^{K_{3}+1}) [ \begin{matrix}K_{3} \\ n + k − 1 \end{matrix} ] [ \begin{matrix}K_{4} \\ n − k \end{matrix} ])

and

(3.12)  B_{n} = ∑_{k∈ℤ} q^{M(k)}((q^{k−n}+q^{K_{2}−n+k+1}) [ \begin{matrix}K_{1} \\ n + k − 1 \end{matrix} ] [ \begin{matrix}K_{2} \\ n − k − 1 \end{matrix} ]

− q^{K_{3}−n−k+2} [ \begin{matrix}K_{3} \\ n + k − 2 \end{matrix} ] [ \begin{matrix}K_{4} \\ n − k \end{matrix} ]

−q^{k−n} [ \begin{matrix}K_{3} \\ n + k − 1 \end{matrix} ] [ \begin{matrix}K_{4} \\ n − k − 1 \end{matrix} ]) .

The exponent M(k) is given by the expression

n^{2} + k^{2}(d − c + 1) − k(1 − c + μ_{2} − μ_{1}) .

Proof. Combining (3.9) and (3.8), we obtain an expression for the desired generating function by using (1.2) with x replaced by x^{2}. This expression by repeated application of the q-binomial identities

[ \begin{matrix}N \\ K \end{matrix} ] = q^{K} [ \begin{matrix}N − 1 \\ K \end{matrix} ] + [ \begin{matrix}N − 1 \\ K − 1 \end{matrix} ]

and

[ \begin{matrix}N \\ K \end{matrix} ] = [ \begin{matrix}N − 1 \\ K \end{matrix} ] + q^{N−K} [ \begin{matrix}N − 1 \\ K − 1 \end{matrix} ]

is turned into the claimed expressions (3.10)–(3.12). □

Counting lattice paths restricted by linear boundaries is intimately connected with determining the distribution for the two-sample Kolmogorov–Smirnov statistics. Vellore [11] derived formulas for the joint distribution of Kolmogorov–Smirnov statistics and run statistics (cf. [9, p.101] for the definition of these statistics) in the equalsample case. Her formulas are special cases of Theorem 5. To see this, first observe that for any path p the number of runs of p exceeds the number of turns of p by one. Let D_{n,n}, D_{n,n}^{+}, and R_{n,n} denote the two-sided, the one-sided Kolmogorov–Smirnov statistics, and run statistics for two samples of size n, respectively. As is well-known, \binom{2n}{n}P (D_{n,n} ≤ t/n, R_{n,n} = r) is equal to the number of all lattice paths from (0, 0) to (n, n) not crossing the lines y = x+t and y = x−t and containing r runs. Hence, this number is equal to the coefficient of x^{r−1} in (3.10), after setting q = 1, λ_{1} = λ_{2} = n, μ_{1} = μ_{2} = 0, and d = −c = t. This provides another proof of [11, Theorems 8 and 9]. Similarly, the result [11, Theorem 5] for \binom{2n}{n}P (D_{n,n}^{+} ≤ t/n, R_{n,n} = r) is the special case q = 1, λ_{1} = λ_{2} = n, μ_{1} = μ_{2} = 0, d = t, c = n of Theorem 5.

Note. Recently, Burge [2] independently considered generating functions for partition pairs with restrictions. To relate his paper to ours, observe that the proof of our Theorem 1 uses double-rowed arrays which actually are pairs of strict partitions. So it is clear that, in disguise, Theorem 1 is a theorem about the generating function for pairs of partitions subject to certain restrictions. In fact, our Theorem 1 could be derived from Burge’s expression for his generating function R(N_{1}, M_{1}, N_{2}, M_{2}, a, b, α, β) by setting N_{1} = N_{2}, a = 1, and b = 0. In turn, our proof of Theorem 1 could be modified to prove his result, too. Though the argumentation in Burge’s proof is different from our’s, the basic correspondence (2.11/2.12) essentially also occurs in Burge’s paper. However, Burge’s emphasis does not lie on lattice path enumeration but on the combinatorial interpretation of certain q-identities. Most interestingly, (among other results) he 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 combines Rogers’ proof and Schur’s proof of the Rogers–Ramanujan identities.

References

1. G. E. Andrews, Encyclopedia of Mathematics and its Applications, Vol. 2, The Theory of Partitions, Addison–Wesley, Reading, 1976.

2. W. H. Burge, Resitricted partition pairs, to appear in J. Combin. Theory A.

3. C. Krattenthaler, Counting lattice paths with a linear boundary I, Sitz.ber. d. ÖAW, Math./Naturwiss. Kl. 198 (1989), 87–107.

4. , Counting lattice paths with a linear boundary II: q-ballot and q-Catalan numbers, Sitz.ber. d. ÖAW, Math./Naturwiss. Kl. (to appear).

5. , Enumeration of lattice paths and generating functions for skew plane partitions, Manuscripta Math. 63 (1989), 129–156.

6. , Generating functions for plane partitions of a given shape, preprint.

7. P. A. McMahon, Combinatory Analysis, Vol. 2, Cambridge University Press, 1916, reprinted by Chelsea, New York, 1960.

8. , Collected Papers: Combinatorics, Vol. I, MIT Press, Cambridge, Massachusetts, 1978.

9. S. G. Mohanty, Lattice path counting and applications, Academic Press, New York, 1979.

10. R. P. Stanley, Ordered structures and partitions, Mem. Amer. Math. Soc. No. 119, American Mathematical Society, Providence, R.I., 1972.

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

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

McMaster University, Hamilton, Ontario, Canada L8S 4K1.