\input amstex.tex 
%\documentstyle{amsppt} 
\NoRunningHeads
\magnification1200
\hsize15.6truecm
\vsize22.8truecm
\catcode`\@=11
\def\item"#1"{\par\noindent\hang%
  \setbox0=\hbox{\rm#1\enspace}\ifdim\wd0>\the\parindent%
  \box0\else\hbox to \parindent{\rm#1\hfil}\enspace\fi\ignorespaces}
\let\plainitem@\item
\catcode`\@=13
\def\des{\operatorname{des}}
\def\maj{\operatorname{maj}}
\NoRunningHeads
\topmatter 
\title ON LATTICE PATH COUNTING BY MAJOR AND DESCENTS
\endtitle 
\author C.~Krattenthaler\\S.~G.~Mohanty
\endauthor 
\affil 
Institut f\"ur Mathematik der Universit\"at Wien,\\
Strudlhofgasse 4, A-1090 Wien, Austria.\\\vskip6pt
McMaster University,\\
Hamilton, Ontario, Canada L8S\,4K1
\endaffil 
\address{Institut f\"ur Mathematik der Universit\"at Wien,
Strudlhofgasse 4, A-1090 Wien, Austria.}\endaddress
\address{McMaster University,
Hamilton, Ontario, Canada L8S\,4K1.}\endaddress
\subjclass{Primary 05A15; Secondary 05A10, 05A17, 05A30,
62G30.}\endsubjclass
\keywords{Lattice paths, major index, descents, runs, turns,
Kolmo\-gorov--Smirnov\linebreak statistics}\endkeywords
\abstract{A formula for counting lattice paths in the plane from $\mu
=(\mu\sb 1,\mu\sb 2)$ to $\lambda
=(\lambda
\sb 1,\lambda
\sb 2)$ which do not cross
 the lines
$y=x+d$ and $y=x+c$, where $c,d\in {\Bbb
Z}$ 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.}\endabstract
\endtopmatter
\document

\subheading{{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 $\mu =(\mu\sb 1,\mu\sb 2)$ to $\lambda
=(\lambda
\sb 1,\lambda
\sb 2),\ \lambda
,\mu \in {\Bbb
Z}\sp 2$, which do not cross the lines
$y=x+d$ and $y=x+c$, where $c,d\in {\Bbb
Z}$ and $d>c$, is 
$$\sum\sb {k\in {\Bbb
Z}}
\left\{\binom {\lambda
\sb 1+\lambda
\sb 2-\mu\sb 1-\mu\sb 2}{\lambda
\sb 1-\mu\sb
1-k(d-c+2)}-\binom{\lambda
\sb 1+\lambda
\sb 2-\mu\sb 1-\mu\sb 2}
{\lambda
\sb 1-\mu\sb 2+k(d-c+2)+c-1}\right\}\ ,\tag 1.1 $$
provided $\lambda
\sb 1+c\leq \lambda
\sb 2\leq \lambda
\sb 1+d$ and $\mu\sb 1+c\leq 
\mu\sb 2\leq
\mu\sb 1+d$. This is easily proved by iterated reflection (cf.
\cite{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 \cite{{3,4,5}}. First we give the relevant definitions. 

The {\it major index} (or ``greater index") of a multiset permutation
$\pi=\pi\sb 1\pi\sb 2\dots 
\pi\sb n$, $\pi\sb i\in {\Bbb
N}\sb 0 $ (set of nonnegative
integers), is defined by
$$\maj \pi =\sum \sb {i=1} \sp {n-1}i\cdot \chi
 (\pi\sb i>\pi\sb {i+1})\ .$$
($\chi
 (A)=1$ if $A$ is true, and $\chi
 (A)=0$ otherwise.) McMahon
\cite{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 $\pi\sb i\pi\sb {i+1}$ with $\pi\sb i>\pi\sb {i+1}$ is called a {\it
descent} of $\pi$. The number of descents of $\pi$,
$$\des \pi =\sum \sb {i=1}\sp  {n-1}\chi
 (\pi\sb i>\pi\sb {i+1})\ ,$$ 
is another important statistics on multiset permutations. Stanley
\cite{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 $\mu$ to $\lambda
$.
$p$ may be represented by a pair $(\mu,\pi)$, where $\mu$ is the
starting point of $p$ and
$\pi=\pi\sb 1\pi\sb 2\dots\pi\sb {\lambda
\sb 1+\lambda
\sb 2-\mu\sb 1-\mu\sb 2}$, 
where $\pi\sb i=0$
if the $i$'th step in the path $p$ is a horizontal one and $\pi\sb i=1$
if the $i$'th step in the path $p$ is a vertical one. $\pi$ is a
multiset permutation consisting of $\lambda
\sb 1-\mu\sb 1$ entries of $0$ and
$\lambda
\sb 2-\mu\sb 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=(\mu,\pi)$, we extend $\maj$ and
$\des$ to $p$ by defining $\maj p:=\maj \pi $ and $\des p:=\des
\pi$.

\medskip
\centerline{\vrule height.4pt depth0pt width3cm
\vrule height2cm depth2cm width.4pt
\hbox to0pt{\hss\raise -2pt\hbox{$\bullet$}\hss}%
\hbox to 0pt{\vrule height.5cm depth0cm width.6pt
\raise.49cm \hbox to 0pt{\hskip-2.5pt\raise -2pt\hbox{$\bullet$}\hskip-2pt
\vrule height1pt depth0pt width.5cm
\hskip-2pt\raise -2pt\hbox{$\bullet$}\hskip-2pt
\vrule height1pt depth0pt width.5cm
\hskip-1pt\raise -2pt\hbox{$\bullet$}\hskip-2.5pt\vrule
height.5cm depth0cm width1pt
\raise.49cm \hbox to 0pt{\hskip-2.5pt\raise -2pt\hbox{$\bullet$}\hskip-1pt
\vrule height1pt depth0pt width.5cm
\hskip-1pt\raise -2pt\hbox{$\bullet$}\hskip-1pt
\vrule height1pt depth0pt width.5cm
\hskip-1pt\raise -2pt\hbox{$\bullet$}\hskip-1pt\hss}%
\hss}%
\hss}%
\vrule height.4pt depth0pt width3cm
}
\centerline{\eightpoint Figure 1}
\medskip

Now we are able to formulate the generalization of formula (1.1) to
counting by $\maj$ and $\des$.
\proclaim{Theorem~{1}} Given $c,d \in {\Bbb
Z},\, d>c$, let
$L\sb {c,d}\sp +(\lambda
,\mu)$ be the set of all lattice paths from
$\mu=(\mu\sb 1,\mu\sb 2)$ to $\lambda
 =(\lambda
\sb 1,\lambda
\sb 2)$ which 
do not cross the
lines $y=x+d$ and $y=x+c$. If $\lambda
\sb 1+c\leq \lambda
\sb 2\leq \lambda
\sb 1+d$ and
$\mu\sb 1+c\leq \mu\sb 2\leq \mu\sb 1+d$, then
$$\multline \sum\sb {p\in L\sb {c,d}\sp +(\lambda
,\mu)}x\sp {\des p}q\sp {\maj
p}\\ =\sum\sb {n\geq 0}x\sp n\sum\sb {k\in
{\Bbb
Z}}q\sp {n\sp 2+k\sp 2(d-c+1)-k(1-c+\mu\sb 2-\mu\sb 1)} \\
\times \left(\left[\matrix \lambda
\sb 1-\mu\sb 1-k(d-c)\\n+k\endmatrix\right ]\left
[\matrix \lambda
\sb 2-\mu\sb 2+k(d-c)\\n-k\endmatrix\right ]\right.\\
\left.-\left [\matrix
\lambda
\sb 2-\mu\sb 1-k(d-c)-c+1\\n+k\endmatrix\right ]\left[\matrix
\lambda
\sb 1-\mu\sb 2+k(d-c)+c-1\\n-k\endmatrix\right ]\right) ,
\endmultline \tag 1.2$$
where $\left [\smallmatrix a\\b\endsmallmatrix\right ]$ is the Gaussian
binomial coefficient $$\left[\matrix
a\\b\endmatrix\right]=(1-q\sp a)(1-q\sp {a-1})\dotsb(1-q\sp 
{a-b+1})/(1-q\sp b) (1-q
\sp {b-1})\dotsb (1-q).$$ 
\endproclaim
Previous results of McMahon \cite{8, p.1429} and of one of the authors
\cite{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 \cite{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 \cite{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 \cite{11}.

\subheading{{2.} Proof of Theorem ~{1}} Any path $p$
from $\mu$ to $\lambda$ may be represented by an array 
$$\matrix\format&\c\,\\ a\sb n\ &a\sb {n-1} & \dots &a\sb 1\\b\sb 
n\ &b\sb {n-1}
 &\dots & b\sb 1&\ ,
\endmatrix \tag 2.1$$
where $n$ is equal to $\des p$, the number of descents of $p$, $a\sb
i$ is equal to the $x$--coordinate of the $i$'th descent of $p$, and
$b\sb i$ is the $y$--coordinate of the $i$'th descent of $p$. More
precisely, if $p=(\mu,\pi)$ and $\pi\sb \nu  \pi\sb {\nu  +1}$ is the $i$'th
descent of $\pi$, then
$$a\sb i=\mu\sb 1+\vert\{j:\pi\sb j=0\text { and }j\leq \nu \}\vert$$ and
$$b\sb i=\mu\sb 2+\vert\{j:\pi\sb j=1\text { and }j\leq \nu \}\vert\ .$$
For example, the path in Figure 1 would be represented by
$$\matrix 2&0\\2&1\endmatrix\ .$$
We shall frequently use the short notation $(a\mid b)$, where
$a=(a\sb n,a\sb {n-1},\mathbreak \dots ,a\sb 1)$ and $b=(b\sb 
n,b\sb {n-1},\dots,b\sb 1)$, for an
array of the form (2.1). By definition, for a path $p$ which is
represented by $(a\mid b)$ we have
$$a\sb i<a\sb {i+1},\ \mu\sb 1\leq a\sb i\leq \lambda
\sb 1-1\ ,\tag 2.2$$ and 
$$b\sb i<b\sb {i+1},\ \mu\sb 2+1\leq b\sb i\leq \lambda
\sb 2\ .\tag 2.3$$
Besides, if $p\in L\sb {c,d}\sp +(\lambda
,\mu)$, then the inequalities
$$b\sb i\leq a\sb i+d\text { for }i=n,n-1,\dots ,1\tag 2.4$$ and 
$$b\sb i\geq a\sb {i+1}+c\text { for }i=n,n-1,\dots ,1,0\ , \tag 2.5$$ with
the conventions $a\sb {n+1}:=\lambda
\sb 1$ and $b\sb
0:=\mu\sb
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\in L\sb {c,d}\sp +(\lambda
,\mu)$, which corresponds to this
array. 

If we let $w(a\mid b):=\sum
\sb ia\sb i+\sum
\sb ib\sb i$, then,
obviously, for a
path $p$ with representation $(a\mid b)$ the equation
$$\maj p=w(a\mid b)-n(\mu\sb 1+\mu\sb 2)$$ is true. Therefore, in
order to prove Theorem 1, we have to show that the generating
function $\sum
 q\sp {w(a\mid b)}$, where the sum is over all $(a\mid
b)$, $a=(a\sb n,\dots,a\sb 1)$ and $b=(b\sb n,\dots,b\sb 1)$, which satisfy
(2.2)--(2.5), is equal to 
$$\multline \sum\sb {k\in
{\Bbb
Z}}q\sp {n(\mu\sb 1+\mu\sb 2)+n\sp 2+k\sp 
2(d-c+1)-k(1-c+\mu\sb 2-\mu\sb 1)} \\
\times \left(\left[\matrix
\lambda
\sb 1-\mu\sb 1-k(1-c)\\n+k\endmatrix\right]\left[\matrix
\lambda
\sb 2-\mu\sb 2+k(d-c)\\n-k\endmatrix\right]\right.\\
\left.-\left[\matrix
\lambda
\sb 2-\mu\sb 1-k(d-c)-c+1\\n+k\endmatrix\right]\left[\matrix
\lambda
\sb 1-\mu\sb 2+k(d-c)+c-1\\n-k\endmatrix\right]\right)\ .
\endmultline \tag 2.6$$

First we introduce some more sets of double--arrays. For $k\in {\Bbb
Z}$
let $L\sb {c,d}\sp {(1)}(\lambda
,\mu;k)$ denote the set of all ``skew''
arrays of the form 
$$\matrix\format&\c\,\\ a\sb {n+k}\dots &a\sb {n-k}& \dots & a\sb 1\\
 &b\sb {n-k}& \dots & b\sb 1 
\endmatrix \quad \quad \text {for $k\ge0$}\tag 2.7)(a$$
and
$$\matrix\format&\c\,\\ 
 &a\sb {n+k}& \dots & a\sb 1 \\
b\sb {n-k}\dots &b\sb {n+k}& \dots & b\sb 1
\endmatrix \quad \quad \text {for $k<0$}\tag 2.7)(b$$
 satisfying $a\sb {i+1}>a\sb i$ and $b\sb {i+1}>b\sb i$, 
and
$$\alignedat2 \mu\sb 1\leq & a\sb i& &\leq \lambda
\sb 1-k(d-c)-1\\
\mu\sb 2+1\leq& b\sb i& &\leq \lambda
\sb 2+k(d-c)\ .
\endmatrix \tag 2.8$$ Analogously, for $k\in {\Bbb
Z}$ let
$L\sb {c,d}\sp {(2)}(\lambda
,\mu;k)$ denote the set of all arrays of the
form (2.7) satisfying $a\sb {i+1}>a\sb i$ and $b\sb {i+1}>b\sb i$, and 
$$\alignedat2 \mu\sb 1&\leq a\sb i& &\leq \lambda
\sb 2-k(d-c)-c\\
\mu\sb 2+1&\leq b\sb i& &\leq \lambda
\sb 1+k(d-c)+c-1\ .
\endalignedat\tag 2.9$$
Note that $L\sb {c,d}\sp +(\lambda
,\mu) $ is a subset of
$L\sb {c,d}\sp {(1)}(\lambda
,\mu;0)$, if we identify each path with its
representing array. Let $L\sb {c,d}\sp -(\lambda
,\mu)$ be the set difference
$$L\sb {c,d}\sp {(1)}(\lambda
,\mu;0)\backslash L\sb {c,d}\sp +(\lambda
,\mu)\
.$$
$L\sb {c,d}\sp -(\lambda
,\mu)$ 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\sp {(n+k)}\mid
b\sp {(n-k)})$ of the form (2.7), with $a\sp 
{(n+k)}=(a\sb {n+k},\dots,a\sb 1)$
and $b\sp {(n-k)}=(b\sb {n-k},\dots,b\sb 1)$, by 
$$w(a\sp {(n+k)}\mid b\sp {(n-k)})=k\sp 2d-(k\sp 2-k)c+\sum\sb 
ia\sb i+\sum\sb ib\sb i\ .\tag
2.10$$ Next we construct a weight--preserving involution $\varphi
$ on the
set $$L\sb {c,d}=\bigcup \sb {k\in{\Bbb
Z}}(L\sb {c,d}\sp {(1)}(\lambda
,\mu;k)\cup
L\sb {c,d}\sp {(2)}(\lambda
,\mu;k))\backslash L\sb {c,d}\sp +(\lambda
,\mu)\ 
.$$ Given an
element $(a\sp {(n+k)}\mid b\sp {(n-k)})$ of $L\sb {c,d}$, let $J$ be the
smallest nonnegative integer such that either 
$$b\sb J<a\sb {J+1}+c\text {\quad or\quad}J=n+k+1 \tag I$$ or
$$b\sb J>a\sb J+d\text {\quad or\quad }J=n-k+1\ .\tag II$$
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\sp {(n+k)}\mid b\sp {(n-k)})\in L\sb {c,d}$ it 
is possible to find
such a $J$, because if $b\sb i\leq a\sb i+d$ 
and $b\sb i\geq a\sb {i+1}+c$ is
satisfied for all $i=1,2,\dots,n-\vert k\vert$, 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\leq n$, with either $b\sb J>a\sb J+d$ or
$b\sb J<a\sb {J+1}+c$, since any element $(a\sp {(n)}\mid 
b\sp {(n)})$ of $L\sb
{c,d}$
belongs to $L\sb {c,d}\sp -(\lambda
,\mu)$.

The map $\varphi
$ is defined as follows: If $(a\sp {(n+k)}\mid b\sp {(n-k)})$
is the array 
$$\matrix\format&\c\,\\ a\sb {n+k}\dots &a\sb {n-k}\dots 
a\sb {J+1}&a\sb J&\dots &a\sb 1\\
 &b\sb {n-k}\dots b\sb {J+1}&b\sb J&\dots &b\sb 1&\ ,
\endmatrix$$ where $J$ is the above defined uniquely determined
integer, then, if condition (I) holds, $\varphi
(a\sp {(n+k)}\mid b\sp {(n-k)})$
is defined by
$$\matrix\format&\c\,\\  &(b\sb {n-k}-c)&\dots &(b\sb 
{J+1}-c)&a\sb J&\dots &a\sb 1\\
(a\sb {n+k}+c)\dots &(a\sb {n-k}+c)&\dots &(a\sb {J+1}+c)&b\sb J&\dots
&b\sb 1&\ , 
\endmatrix \tag 2.11$$ if condition (I) does not hold (but, hence,
condition (II) does), 
$\varphi
(a\sp {(n+k)}\mid b\sp {(n-k)})$ is defined by
$$\matrix\format&\c\,\\ &(b\sb {n-k}-d)&\dots &(b\sb J-d)& a\sb J & 
a\sb {J-1}&\dots &a\sb 1\\
(a\sb {n+k}+d)\dots &(a\sb {n-k+2}+d)&\dots &
(a\sb {J+2}+d)&(a\sb {J+1}+d)&b\sb {J-1}&\dots &b\sb 1&\ . 
\endmatrix \tag 2.12$$ 
More precisely, the arrray $(A\sp {(n-k)}\mid B\sp {(n+k)})$ in (2.11) is
given by $$A\sb i=\cases a\sb i&1\leq i\leq 
J\\ b\sb i-c&J<i\leq n-k \endcases$$
and $$B\sb i=\cases b\sb i&1\leq i\leq J\\a\sb i+c&J<i\leq n+k\ ,\endcases$$
while the array $(C\sp {(n-k+1)}\mid D\sp {(n+k-1)})$ in (2.12) is given by 
$$C\sb i=\cases a\sb i&1\leq i\leq J\\b\sb {i-1}-d&J<i\leq n-k+1\endcases$$
and $$D\sb i=\cases b\sb i&1\leq i<J\\a\sb {i+1}+d&J\leq 
i\leq n+k-1\ .\endcases$$
One can readily verify the following properties of $\varphi
$:
\roster
\item If $(a\sp {(n+k)}\mid b\sp {(n-k)})\in L \sb 
{c,d} \sp {(i)}(\lambda
,\mu;k)$, $i=1,2$, and
$\varphi
 (a\sp {(n+k)}\mid b\sp {(n-k)})$ is given by (2.11), then $\varphi
(a\sp {(n+k)}\mid b\sp {(n-k)})\in L \sb {c,d} \sp {(3-i)}(\lambda
,\mu;-k)$.
\item If $(a\sp {(n+k)}\mid b\sp {(n-k)})\in L 
\sb {c,d} \sp {(i)}(\lambda
,\mu;k)$,
$i=1,2$, and $\varphi
 (a\sp {(n+k)}\mid b\sp {(n-k)})$ is given by (2.12), then
$\varphi
(a\sp {(n+k)}\mid b\sp {(n-k)})\in L \sb {c,d} 
\sp {(3-i)}(\lambda
,\mu;-k+1)$.
\item $\varphi
$ is an involution on $L\sb {c,d}$.
\item $\varphi
$ is weight--preserving with respect to the weight $w$
given in (2.10).
\endroster
Items (1)--(4) imply the generating function identity 
$$\multline \underset k\neq 0\to {\sum\sb {k\in{\Bbb
Z}}}\sum\sb {p\in
L\sb {c,d}\sp {(1)}(\lambda
,\mu;k)}q\sp {w(p)}+\sum\sb {p\in
L\sb {c,d}\sp -(\lambda
,\mu,k)}q\sp {w(p)}=\\
=\sum\sb {k\in{\Bbb
Z}}\sum\sb {p\in L \sb {c,d} 
\sp {(2)}(\lambda
,\mu;k)}q\sp {w(p)}\ .
\endmultline \tag 2.13$$
Besides, by definition we have $$\sum\sb {p\in L \sb {c,d}
\sp {-}}q\sp {w(p)}=\sum\sb {p\in L \sb {c,d} 
\sp {(1)}(\lambda
,\mu;0)}q\sp {w(p)}
-\sum\sb {p\in L \sb {c,d} \sp {+}(\lambda
,\mu)}q\sp {w(p)}\ .\tag 2.14$$
Obviously, because of (2.10) the generating function
$$\sum\sb {p\in L \sb {c,d} \sp {(1)}(\lambda
,\mu;k)}q\sp {w(p)}$$ is equal to
$q\sp {k\sp 2d-(k\sp 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 $\mu\sb 1$ and at most
$\lambda
\sb 1-1-k(d-c)$ times the generating function for all partitions
with $(n-k)$ distinct parts, each part at least $(\mu\sb 2+1)$ and at
most $\lambda
\sb 2+k(d-c)$. Therefore, by applying the classical result
\cite{1, Theorem 3.1} for the generating function for linear partitions, we
obtain $$\sum\sb {p\in L \sb {c,d} 
\sp {(1)}(\lambda
,\mu;k)}q\sp {w(p)}=q\sp {N(k)}
\left[\matrix \lambda
\sb 1-\mu\sb 1-k(d-c)\\n+k\endmatrix \right] \left[\matrix
\lambda
\sb 2-\mu\sb 2+k(d-c)\\n-k\endmatrix\right]\ ,\tag 2.15$$ where 
$$N(k)=k\sp 2d-(k\sp 2-k)c+\pmatrix n+k\\2\endpmatrix+\pmatrix 
n-k\\2\endpmatrix
+\mu\sb 1(n+k)+(\mu\sb 2+1)(n-k)\ .$$
Analogously, we get 
$$\multline \sum\sb {p\in L \sb {c,d} \sp {(2)}(\lambda
,\mu;k)}q\sp {w(p)}\\
=q\sp {N(k)}\bmatrix \lambda
\sb 2-\mu\sb 1-k(d-c)-c+1\\n+k\endbmatrix \bmatrix
\lambda
\sb 1-\mu\sb 2+k(d-c)+c-1\\n-k\endbmatrix .
\endmultline \tag 2.16$$ Finally, substitution of (2.14)--(2.16) into
(2.13) yields (2.6), which is equivalent to Theorem 1.

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

If we choose $c=\mu\sb 2-\lambda
\sb 1$ in Theorem 1, the terms with
$k\notin
\{0,1\}$ vanish. Besides, any path from $\mu=(\mu\sb 1,\mu\sb 2)$ to
$\lambda
=(\lambda
\sb 1,\lambda
\sb 2)$ cannot 
cross the line $y=x+\mu\sb 2-\lambda
\sb 1$. Thus we
obtain the result for lattice path counting by $\maj$ and $\des $ for
the one boundary case.

\proclaim{ Corollary~{2}} Given $d\in {\Bbb
Z}$, let $L\sb d\sp +(\lambda
,\mu)$
be the set of all lattice paths from $\mu=(\mu\sb 1,\mu\sb 2)$ to
$\lambda
=(\lambda
\sb 1,\lambda
\sb 2)$ not crossing the line $y=x+d$. If $\lambda
\sb 2\leq
\lambda
\sb 1+d$ and $\mu\sb 2\leq \mu\sb 1+d$, then 
$$\multline \sum\sb {p\in L\sb d\sp +(\lambda
,\mu)}x\sp {\des p}q\sp {\maj p}\\
=\sum\sb {n\geq 0}x\sp nq\sp {n\sp 2}\left(\bmatrix 
\lambda
\sb 1-\mu\sb 1\\n\endbmatrix \bmatrix
\lambda
\sb 2-\mu\sb 2\\n\endbmatrix \right. \\ 
\left. -q\sp {\mu\sb 1-\mu\sb 2+d}\bmatrix \lambda
\sb 2-\mu\sb 
1-d+1\\n+1\endbmatrix \bmatrix
\lambda
\sb 1-\mu\sb 2+d-1\\n-1\endbmatrix \right)\ .
\endmultline \tag 3.1$$ 
\endproclaim
This result solves the problem put in \cite{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 \cite{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:

\proclaim{ Corollary~{3}} With the assumptions of Theorem 1, we
have 
$$\multline \sum\sb {p\in L \sb {c,d} \sp {+}(\lambda
,\mu)}q\sp {\maj
p}=\sum\sb {k\in{\Bbb
Z}}q\sp {k\sp 2(d-c+2)-k(1-c+\mu\sb 2-\mu\sb 1)}\\
\times \left(\bmatrix \lambda
\sb 1+\lambda
\sb 2-\mu\sb 1-\mu\sb 
2\\\lambda
\sb 1-\mu\sb 1-k(d-c+2)\endbmatrix
-\bmatrix \lambda
\sb 1+\lambda
\sb 2-\mu\sb 1-\mu\sb 2\\\lambda
\sb 1-\mu\sb 
2+k(d-c+2)+c-1\endbmatrix
\right)\ .
\endmultline \tag 3.2$$
\endproclaim
The corresponding result for the one boundary case reads:
\proclaim{ Corollary~{4}} With the assumptions of Corollary 2,
we have 
$$\multline \sum\sb {p\in L \sb {d} \sp {+}(\lambda
,\mu)}q\sp {\maj p}\\
=\bmatrix \lambda
\sb 1+\lambda
\sb 2-\mu\sb 1-\mu\sb 2\\\lambda
\sb 1-\mu\sb 1\endbmatrix
-q\sp {\mu\sb 1-\mu\sb 2+d+1}\bmatrix \lambda
\sb 1+\lambda
\sb 2-\mu\sb 1-\mu\sb 2\\
\lambda
\sb 1-\mu\sb 2+d+1\endbmatrix \ .
\endmultline \tag 3.3$$
\endproclaim
The last result was previously shown in \cite{4, (5.36)}. The other
generating function identities in section 5 of \cite{4} are also
special cases of Theorem 1.

\medskip
Next we want to reformulate Theorem~1 into a theorem about counting
lattice paths with respect to major and their number of turns. A
{\it 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
 $\sum
x\sp {t(p)}q\sp {\maj p}$, 
where the sum is over all paths $p$ being an element of
$L\sb {c,d}\sp +(\lambda
,\mu)$, we need some more notation. Let $F(\lambda
,\mu ;x)$
denote the generating function $\sum x\sp {\des p}q\sp {\maj p}$, 
where the sum is
over all paths $p$ of $L\sb {c,d}\sp +(\lambda
,\mu)$. Let $F\sb {01}(\lambda
,\mu ;x)$
denote the generating function $\sum x\sp {\des p}q\sp {\maj p}$, 
where the sum is
over all paths $p$ of $L\sb {c,d}\sp +(\lambda
,\mu)$ starting with a horizontal
edge and ending with a vertical one. $F\sb {00}(\lambda
,\mu; x)$, 
$F\sb {10}(\lambda
,\mu;x)$, and $F\sb {11}(\lambda
,\mu;x)$ are defined analogously.
Obviously, the following equation holds,
$$F\sb {00}(\lambda
,\mu;x)+F\sb {01}(\lambda
,\mu;x)+F\sb 
{10}(\lambda
,\mu;x)+F\sb {11}(\lambda
,\mu;x)=
F(\lambda
,\mu;x)\ . \tag 3.4$$
Since for any multiset permutation $\pi$ (consisting only of $0$'s
and $1$'s) we have
$$\des (0\pi)=\des \pi$$
and
$$\maj(0\pi)=\maj\pi+\des\pi\ ,$$ 
we obtain
$$F\sb {00}(\lambda
,\mu;x)+F\sb {01}(\lambda
,\mu;x)=F(\lambda
,\mu+e\sb 1;qx)\ , \tag 3.5$$
where $e\sb 1=(1,0)$. Similarly, if $e\sb 2=(0,1)$, we get
$$F\sb {01}(\lambda
,\mu;x)+F\sb {11}(\lambda
,\mu;x)=F(\lambda
-e\sb 2,\mu;x)\ , \tag 3.6$$ 
and
$$F\sb {01}(\lambda
,\mu;x)=F(\lambda
-e\sb 2,\mu+e\sb 1;qx)\ . \tag 3.7$$
Equations $(3.4)$--$(3.7)$ yield 
$$\align F\sb {00}(\lambda
,\mu;x)&=F(\lambda
,\mu +e\sb 1;qx)-F(\lambda
-e\sb 2,\mu +e\sb
1;qx) \tag 3.8\\
F\sb {01}(\lambda
,\mu;x)&=F(\lambda
-e\sb 2,\mu+e\sb 1;qx)\\
F\sb {10}(\lambda
,\mu;x)&=F(\lambda
,\mu;x)+F(\lambda
-e\sb 2,\mu+e\sb 1;qx)\\
&\hskip1.5cm-F(\lambda
,\mu+e\sb
1;qx)-
F(\lambda
-e\sb 2,\mu;x)\\
F\sb {11}(\lambda
,\mu;x)&=F(\lambda
-e\sb 2,\mu;x)-F(\lambda
-e\sb 2,\mu+e\sb 1;qx)\ .
\endalign$$ 
Simple considerations show that
$$\multline\sum \sb {p\in
L\sb {c,d}\sp +(\lambda
,\mu)}x\sp {t(p)}=F\sb 
{00}(\lambda
,\mu;x\sp 2)+xF\sb {01}(\lambda
,\mu;x\sp
2)\\
+\frac{1} {x}F\sb {10}(\lambda
,\mu;x\sp 2)+F\sb {11}(\lambda
,\mu;x\sp 2)\
.\endmultline \tag
3.9$$
Now we are in the position to formulate our path counting formula.

\proclaim{Theorem~{5}} Let
$$\align K\sb 1&=\lambda
\sb 1-\mu\sb 1-k(d-c)-1\\
K\sb 2&=\lambda
\sb 2-\mu\sb 2+k(d-c)-1\\
K\sb 3&=\lambda
\sb 2-\mu\sb 1-k(d-c)-c-1\\
K\sb 4&=\lambda
\sb 1-\mu\sb 2+k(d-c)+c-1\ .
\endalign$$
With the assumptions of Theorem 1, we have 
$$\sum \sb {p\in L\sb {c,d}\sp +(\lambda
,\mu)}x\sp 
{t(p)}q\sp {\maj p}=\sum \sb {n\geq 0}x\sp {2n}A\sb n+\sum
\sb {n\geq 0}x\sp {2n-1}B\sb n\ ,\tag 3.10$$ where
$$\multline A\sb n=\sum \sb {k\in {\Bbb
Z}}q\sp
{M(k)}\left 
(q\sp {K\sb
2+2k+1}\bmatrix K\sb 1\\n+k\endbmatrix \bmatrix
K\sb 2\\n-k-1\endbmatrix \right .\\
\left .+\bmatrix K\sb 1\\n+k-1\endbmatrix \bmatrix
K\sb 2\\n-k\endbmatrix 
-\left(1+q\sp
{K\sb
3+1}\right)\bmatrix K\sb 3\\n+k-1\endbmatrix \bmatrix
K\sb 4\\n-k\endbmatrix\right )\endmultline \tag 3.11$$ and
$$\align B\sb n=\sum \sb 
{k\in {\Bbb
Z}}q\sp
{M(k)}\bigg (\big( q\sp
{k-n}+&q\sp
{K\sb
2-n+k+1}\big)
\bmatrix K\sb 1\\n+k-1\endbmatrix \bmatrix
K\sb 2\\n-k-1\endbmatrix  \tag 3.12\\
& -q\sp
{K\sb
3-n-k+2}
\bmatrix K\sb 3\\n+k-2\endbmatrix \bmatrix
K\sb 4\\n-k\endbmatrix\\
&\left .
 -q\sp
{k-n}\bmatrix K\sb 3\\n+k-1\endbmatrix \bmatrix
K\sb 4\\n-k-1\endbmatrix \right )\ . \endalign$$
The exponent $M(k) $ is given by the expression
$$n\sp
2+k\sp
2(d-c+1)-k(1-c+\mu\sb
2-\mu\sb
1)\ .$$
\endproclaim
\demo{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\sp 2$. This expression by repeated application of the
$q$-binomial identities
$$\bmatrix N\\K\endbmatrix=q\sp
{K}\bmatrix N-1\\K\endbmatrix +\bmatrix
N-1\\K-1\endbmatrix$$
and
$$\bmatrix N\\K\endbmatrix=\bmatrix N-1\\K\endbmatrix +
q\sp
{N-K}\bmatrix
N-1\\K-1\endbmatrix$$
 is turned into the claimed expressions
(3.10)--(3.12).\quad \quad \qed\enddemo

Counting lattice paths restricted by linear boundaries is intimately
connected  with determining the distribution for the two-sample
Kolmogorov--Smirnov statistics. Vellore \cite{11} derived formulas for
the joint distribution of Kolmogorov--Smirnov statistics and run
statistics (cf\. \cite{9, p.101} for the definition of these statistics) 
in the equal-sample 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\sb
{n,n}$, 
$D\sb {n,n}\sp +$, and $R\sb {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\sb {n,n}\leq t/n,R\sb {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\sp {r-1}$ in $(3.10)$, after setting $q=1$,
 $\lambda
\sb 1=\lambda
\sb 2=n$,
$\mu\sb 1=\mu\sb 2=0$, and $d=-c=t$. This provides another proof of
\cite{11, Theorems 8 and 9}. Similarly, the result \cite{11, Theorem
5} for $\binom {2n}n P(D\sb 
{n,n}\sp +\leq t/n, R\sb {n,n}=r)$ is
the special case $q=1$, $\lambda
\sb 1=\lambda
\sb 2=n$, $\mu\sb 
1=\mu\sb 2=0$, $d=t$, $c=n$ of
Theorem 5.

\remark{Note} Recently, Burge \cite{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\sb
1,M\sb
1,N\sb
2,M\sb
2,a,b,\alpha
,\beta
)$
by setting $N\sb
1=N\sb
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.
\endremark
\Refs

\ref\no 1\by G.~E.~Andrews\book The Theory of Partitions\publ
Addison--Wesley\publaddr Reading\yr 1976\paperinfo Encyclopedia of
Mathematics and its Applications, Vol.~2\endref
\ref\no 2\by W. H. Burge\paper Resitricted partition pairs\paperinfo
to appear in J. Combin\. Theory A \endref
\ref\no 3\manyby C.~Krattenthaler\paper Counting lattice paths with a
linear boundary I\jour Sitz.ber\. d\. \"OAW, Math./Na\-tur\-wiss\. Kl\.
\vol 198\yr 1989\pages 87--107\endref
\ref\no 4\bysame \paper Counting lattice paths with a linear boundary
II: $q$-ballot and $q$-Catalan numbers\jour 
Sitz.ber\. d\. \"OAW, Math./Na\-tur\-wiss\. Kl\.
\toappear\endref
\ref\no 5\bysame \paper Enumeration of lattice paths and generating
functions for skew plane partitions\jour 
Ma\-nu\-scrip\-ta Math\. \vol 63\yr 1989\pages 129--156\endref
\ref\no 6\bysame \paper Generating functions for plane partitions of
a given shape 
\paperinfo preprint\endref
\ref\no 7\manyby P.~A.~McMahon\book Combinatory Analysis\bookinfo Vol.~2,
Cambridge University Press, 1916\publ reprinted by Chelsea\publaddr
New York\yr 1960\endref
\ref\no 8\bysame \book Collected Papers: Combinatorics \bookinfo
Vol.~I\publ MIT Press\publaddr Cambridge, Massachusetts\yr 1978\endref
\ref\no 9\by S.~G.~Mohanty\book Lattice path counting and
applications\publ Academic Press\publaddr New York\yr 1979\endref
\ref\no 10\by R.~P.~Stanley\book Ordered structures and
partitions\bookinfo Mem\. Amer\. Math\. Soc\. No.~119\publ American
Mathematical Society\publaddr Providence, R.I.\yr 1972\endref

\ref\no 11\by S.~Vellore\paper Joint distributions of
Kolmogorov--Smirnov statistics and runs\jour Studia Scientiarum
Math\. Hungarica
\vol 7\yr 1972\pages 155-165\endref
\enddocument
