\input amspptbk.sty
\magnification1200
\input sekr.tex
\input format
\input path.sty

\TagsOnRight

\def\VellAA{43}
\def\SulaAC{42}
\def\StemAE{41}
\def\StecAA{40}
\def\NiedAR{39}
\def\NaraAB{38}
\def\NaraAA{37}
\def\MohaAE{36}
\def\MohaAC{35}
\def\MohaAG{34}
\def\ModaAA{33}
\def\LindAA{32}
\def\KulkAC{31}
\def\KulkAD{30}
\def\KrSuAA{29}
\def\KrMoAA{28}
\def\KrMoAC{27}
\def\KrPrAA{26}
\def\KratAV{25}
\def\KratAW{24}
\def\KratBE{23}
\def\KratAP{22}
\def\KratAQ{21}
\def\KratAF{20}
\def\KaMGAB{19}
\def\KaMGAC{18}
\def\KarlAB{17}
\def\HeTrAA{16}
\def\GhKrAA{15}
\def\GhorAD{14}
\def\GeViAB{13}
\def\GeViAA{12}
\def\GeKrAA{11}
\def\FishAA{10}
\def\EsGuAA{9}
\def\DeGrAA{8}
\def\CoHeAA{7}
\def\ConcAC{6}
\def\ComtAA{5}
\def\BurgAC{4}
\def\AbKuAC{3}
\def\AbhyAB{2}
\def\AbhyAD{1}

\def\rreeff{}
\def\Sch{{\Cal M}}
\def\run{\operatorname{run}}
\def\L#1{L\big(#1\big)}
\def\th{\vartheta}
\def\bvert{\big\vert}
\def\Bvert{\Big\vert}
\def\Expr{\operatorname{Expr}}
\def\less{\operatorname{less}}
\def\xmaj{\operatorname{xmaj}}
\def\ymaj{\operatorname{ymaj}}
\def\stat{\operatorname{stat}}
\def\A{{\Cal A}}
\def\B{{\Cal B}}
\def\E{{\Cal E}}
\def\F{{\Cal F}}
\def\P{{\bold P}}
\def\S{{\Cal S}}
\def\x{{\bold x}}
\def\y{{\bold y}}
\def\RR{{\frak R}}
\def\v#1{{\vert#1\vert}}
\def\V#1{{\Vert#1\Vert}}
\def\si{\sigma}
\def\et{\eta}
\def\sgn{\operatorname{sgn}}
\def\GF{\operatorname{GF}}
\def\NE{\operatorname{NE}}
\def\EN{\operatorname{EN}}


\topmatter 
\title The enumeration of lattice paths with respect to their number
of turns
\endtitle 
\author C.~Krattenthaler
\endauthor 
\affil 
Institut f\"ur Mathematik der Universit\"at Wien,\\
Strudlhofgasse 4, A-1090 Wien, Austria.\\
e-mail: KRATT\@Pap.Univie.Ac.At\\
WWW: \tt http://radon.mat.univie.ac.at/People/kratt
\endaffil
\address Institut f\"ur Mathematik der Universit\"at Wien,
Strudlhofgasse 4, A-1090 Wien, Austria.
\endaddress
%\itail KRATT\@Pap.Univie.Ac.At\endemail
%\dedicatory \enddedicatory
%\date \enddate
%\thanks \endthanks
%\subjclass Primary 05A15;
% Secondary 05A19, 13C40, 60-02, 60C05, 62-02, 62E15.
%\endsubjclass
%\keywords turns, lattice paths, nonintersecting lattice paths, coin
%tossing, run statistics, 
%non-crossing two-rowed arrays,
%determinantal rings, pfaffian rings, Hilbert series, tableaux, plane
%partitions
%\endkeywords
\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, 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.
\endabstract
\endtopmatter
\document


\subhead 1. Introduction\endsubhead
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 {\it turns}. By a
{\it 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~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
{\it North-East turn} ({\it 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 {\it East-North turn} ({\it 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~1 are $(1,1)$, $(2,3)$, and $(5,4)$, and the
EN-turns of the
path in Figure~1 are $(2,1)$, $(5,3)$, and $(6,4)$.

\vskip10pt 
\vbox{\noindent
$$\Koordinatenachsen(8,8)(0,0)
\Gitter(8,8)(0,0)
\Pfad(1,-1),221221112122\endPfad
\DickPunkt(1,-1)
\DickPunkt(6,6)
\Label\ro{P_1}(3,3)
\hskip4cm
$$
\nobreak
\centerline{\eightpoint Figure 1}
}
\vskip10pt

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, see section~3. The examples from probability and
statistics (correlated random walk, run and Kolmogorov-Smirnov
statistics) in section~3, lead
to the enumeration of paths, with given starting and end point, 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
{\it 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 \cite{\AbhyAD, \AbhyAB}. 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, namely by encoding paths in terms of {\it
two-rowed arrays}. Actually, this is the way in which Narayana
\cite{\NaraAA, \NaraAB, sec.~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 two-rowed 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 two-rowed 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 e.g\.
\cite{\EsGuAA, \FishAA, \KarlAB, \KaMGAC, \KaMGAB}).

Thiss exposition brings together ideas from several papers of this author
and Mohanty \cite{\KratAF, \KratAQ, \KratAP, \KratAW, \KrMoAC}. The
proof of Theorem~4 is new.

The paper is organized in the following way. In the next section we
introduce some basic notation which we use throughout the
paper. Section~3 contains the announced motivating examples. In
section~4 we address the turn enumeration of (single) lattice paths.
The results of section~4 are then applied in section~5 to solve some
of the problems of the motivating examples. Finally, section~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~3. Open problems are listed at the end of
section~6. 

\subhead 2. Notation\endsubhead
Given two lattice points $A$ and $E$, we denote the set of all
lattice paths
from $A$ to $E$ by $L(A\to E)$. If $P$ is a path from $A$ to $E$ we
will symbolize this sometimes by $P:A\to E$. If $R$ is some property
of paths, we use the ``probability-like" notation $L(A\to E\mid R)$ 
for the set of all paths from $A$ to $E$ satisfying property $R$. 



\subhead 3. Motivating examples\endsubhead
\example{Example 1. A two coin tossing game; correlated random
walk} In \cite{\MohaAG}, Mohanty considers 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:
\roster
\item start with coin $i$, $i=1,2$,
\item if the last trial was a tail then make the next trial with coin
$1$, otherwise with coin $2$,
\item stop making further trials when for the first time the total
number of heads exceeds $\mu$ times the total number of tails by exactly $a$,
with a fixed $a>0$.
\endroster
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? 

\smallskip
This game has also an equivalent formulation in terms of a
``correlated" random walk, see e.g\. \cite{\MohaAE, sec.~5.2}. In
sampling plane terminology \cite{\DeGrAA} the games describe
sequential sampling plans for binomial populations with $y=\mu x+a$
as the boundary line.

\smallskip
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 $THHHTHTHHHH$ (which is a game for
$\mu=2$ and $a=2$) would be represented by
the lattice path $P_2$ in Figure~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=\mu x+a-1$ (being allowed to touch it).

\vskip10pt 
\vbox{\noindent
$$\Koordinatenachsen(5,10)(-1,0)
\Gitter(5,10)(-1,0)
\Pfad(0,0),12221212222\endPfad
\DickPunkt(0,0)
\DickPunkt(3,8)
\Label\ro{P_2}(3,3)
\thinlines
\hskip-.5\Einheit
\catcode`\@=11
\Line@(1,2)5
\catcode`\@=13
\hskip.5\Einheit
\thicklines
%\hskip2cm
$$
\nobreak
\centerline{\eightpoint Figure 2}
}
\vskip10pt
The probability of a game of
length $(\mu n+1)n+a$ ($n$ tails and $\mu n+a$ heads) is given as
follows. If the first toss was with coin $1$, then the probability of
a game, if corresponding to a path $P$ as described above, is
$$p_1^{\NE(P)+1}(1-p_1)^{n-\NE(P)}p_2^{\mu
n+a-\NE(P)-1}(1-p_2)^{\NE(P)},\tag3.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^{\mu
n+a-\NE(P)-1}(1-p_2)^{\NE(P)+1},\tag3.2$$
if the first toss resulted into tail, respectively
$$p_1^{\NE(P)}(1-p_1)^{n-\NE(P)}p_2^{\mu
n+a-\NE(P)}(1-p_2)^{\NE(P)},\tag3.3$$
if the first toss resulted into head. 
 
Therefore, to determine the probability of games
of length $(\mu+1)n+a$ we need to enumerate lattice paths from $(0,0)$ to
$(n,\mu n+a-1)$ staying below the line $y=\mu x+a-1$, being allowed
to touch it, which have a given number of NE-turns. 
\endexample

\example{Example 2. Runs and Kolmogorov-Smirnov statistics} 
Two common rank order statistics for
nonparametric testing problems in the two-sample case are the 
{\it run statistics\/} and the (one- and two-sided) {\it Kolmogorov-Smirnov
statistics\/}. We consider just the case of equal sample size.
Recall (see e.g\. \cite{\MohaAE, sec.~4.3}) 
that this means to deal with two sets of independent, identically
distributed random variables
$\Cal X=\{X_1,X_2,\dots,X_n\}$ and $\Cal 
Y=\{Y_1,Y_2,\dots,Y_n\}$ of size $n$. 
These are then put together and ordered into
$\Cal Z=(Z_1,Z_2,\dots,Z_{2n})$ according to size. The {\it run
statistics} counts the number of maximal consecutive subsequences in
$\Cal Z$ the members of which belong to just one of the sets $\Cal X$
or $\Cal Y$. Thus, if $n=5$, and if $\Cal
Z_1=(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 $\Cal Z$ is 6. The {\it one-sided Kolmogorov-Smirnov statistics\/}
$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 occurences of $X_j$'s in the initial segment 
$Z_1,Z_2,\dots,Z_i$ of $\Cal Z$,
while $b_i$ is the number of occurences of $Y_j$'s in this initial
segment. The {\it two-sided Kolmogorov-Smirnov statistics\/}
$D_{n,n}$ is defined by
$$D_{n,n}=\frac {1} {n}\max_i\big\{\vert a_i-b_i\vert\big\},$$
with the same meanings of $a_i$ and $b_i$. Thus, we have for our
combined sample $\Cal Z_1$ that $D^+_{5,5}=1/5$ and $D_{5,5}=2/5$.

Each such sequence $\Cal 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 $\Cal Z_1$ corresponds to the lattice
path $P_3$ in Figure~3. The run statistics obviously translates into
the number of maximal horizontal and vertical pieces in the
corresponding path. The one-sided Kolmogorov-Smirnov statistics is
basically the maximal deviation from the main diagonal in direction
$(1,-1)$. The two-sided Kolmogorov-Smirnov statistics is
basically the maximal deviation from the main diagonal, in either
direction. So in Figure~4, paths which stay in the region between the
indicated lines $y=x+2$ and $y=x-2$ correspond to sequences $\Cal Z$
with two-sided Kolmogorov-Smirnov statistics $D_{n,n}\le 2/5$.

\vskip10pt 
\vbox{\noindent
$$\Koordinatenachsen(7,7)(-2,-1)
\Gitter(7,7)(-2,-1)
\Pfad(0,0),2111221221\endPfad
\DickPunkt(0,0)
\DickPunkt(5,5)
\Label\ro{P_3}(1,1)
\Diagonale(-2,0)8
\Diagonale(0,-2)7
$$
\nobreak
\centerline{\eightpoint Figure 3}
}
\vskip10pt

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 statistics, 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 statistics and between lines $y=x+t$ and $y=x-t$ 
for the two-sided Kolmogorov-Smirnov statistics.
\endexample

\example{Example 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\le i\le b,\ 0\le j\le a}$ be an $(b+1)\times (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\le i\le b$, $0\le j\le a$, and let $I_{n+1}(X)$
be the ideal in $K[X]$ that is generated by all $(n+1)\times (n+1)$
minors of $X$. The ideal $I_{n+1}(X)$ is called a {\it 
determinantal ideal}. The associated {\it 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)_\ell$ of dimension $\ell$,
$\ell=0,1,\dots$, 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 $\sum _{\ell=0}
^{\infty}\dim_K\big(R_{n+1}(X)_\ell \big)\,z^\ell$. It was shown in several ways
\cite{\AbhyAB, \AbKuAC, \CoHeAA, \KulkAC} (see also \cite{\GhorAD}) that this problem relates to
counting lattice paths with respect to turns, more precisely, to
counting {\it families of nonintersecting lattice paths} with respect
to turns. A family $(P_1,P_2,\dots,P_n)$ of paths $P_i$,
$i=1,2,\dots,n$, is called {\it nonintersecting\/} if no two paths in
the family have a point in common, otherwise it is called {\it
intersecting}.
This result is the following.

\proclaim{Theorem 1}Let 
$A_i=(0,n-i)$ and $E_i=(a-n+i,b)$, $i=1,2,\dots,n$. 
Then the Hilbert series of the determinantal
ring $R_{n+1}(X)=K[X]/I_{n+1}(X)$ equals
$$\sum _{\ell=0}
^{\infty}\dim_K\big(R_{n+1}(X)_\ell \big)\,z^\ell=\frac {\sum _{\P} ^{}z^{\NE(\P)}}
{(1-z)^{(a+b+1)n-2\binom n2}},\tag3.4$$
where the sum on the right-hand side is over all families
$\P=(P_1,P_2,\dots,P_n)$ of nonintersecting lattice paths, $P_i$
running from $A_i$ to $E_i$, $i=1,2,\dots,n$. Here the number
$\NE(\P)$ is defined to be the total number $\sum _{i=1}
^{n}\NE(P_i)$ of NE-turns of the family $\P$. 

\endproclaim
Figure~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.
\vskip10pt 
\vbox{\noindent
$$\Einheit.4cm
\Koordinatenachsen(14,16)(0,0)
\Gitter(14,16)(0,0)
%\GitterPunkt(0,0)
%\GitterPunkt(1,0)
%\GitterPunkt(2,0)
%\GitterPunkt(3,0)
%\GitterPunkt(4,0)
%\GitterPunkt(5,0)
%\GitterPunkt(6,0)
%\GitterPunkt(7,0)
%\GitterPunkt(8,0)
%\GitterPunkt(9,0)
%\GitterPunkt(10,0)
%\GitterPunkt(11,0)
%\GitterPunkt(12,0)
%\GitterPunkt(13,0)
%
%\GitterPunkt(0,1)
%\GitterPunkt(1,1)
%\GitterPunkt(2,1)
%\GitterPunkt(3,1)
%\GitterPunkt(4,1)
%\GitterPunkt(5,1)
%\GitterPunkt(6,1)
%\GitterPunkt(7,1)
%\GitterPunkt(8,1)
%\GitterPunkt(9,1)
%\GitterPunkt(10,1)
%\GitterPunkt(11,1)
%\GitterPunkt(12,1)
%\GitterPunkt(13,1)
%
%\GitterPunkt(0,2)
%\GitterPunkt(1,2)
%\GitterPunkt(2,2)
%\GitterPunkt(3,2)
%\GitterPunkt(4,2)
%\GitterPunkt(5,2)
%\GitterPunkt(6,2)
%\GitterPunkt(7,2)
%\GitterPunkt(8,2)
%\GitterPunkt(9,2)
%\GitterPunkt(10,2)
%\GitterPunkt(11,2)
%\GitterPunkt(12,2)
%\GitterPunkt(13,2)
%
%\GitterPunkt(0,3)
%\GitterPunkt(1,3)
%\GitterPunkt(2,3)
%\GitterPunkt(3,3)
%\GitterPunkt(4,3)
%\GitterPunkt(5,3)
%\GitterPunkt(6,3)
%\GitterPunkt(7,3)
%\GitterPunkt(8,3)
%\GitterPunkt(9,3)
%\GitterPunkt(10,3)
%\GitterPunkt(11,3)
%\GitterPunkt(12,3)
%\GitterPunkt(13,3)
%%
%\GitterPunkt(0,4)
%\GitterPunkt(1,4)
%\GitterPunkt(2,4)
%\GitterPunkt(3,4)
%\GitterPunkt(4,4)
%\GitterPunkt(5,4)
%\GitterPunkt(6,4)
%\GitterPunkt(7,4)
%\GitterPunkt(8,4)
%\GitterPunkt(9,4)
%\GitterPunkt(10,4)
%\GitterPunkt(11,4)
%\GitterPunkt(12,4)
%\GitterPunkt(13,4)
%%
%\GitterPunkt(0,5)
%\GitterPunkt(1,5)
%\GitterPunkt(2,5)
%\GitterPunkt(3,5)
%\GitterPunkt(4,5)
%\GitterPunkt(5,5)
%\GitterPunkt(6,5)
%\GitterPunkt(7,5)
%\GitterPunkt(8,5)
%\GitterPunkt(9,5)
%\GitterPunkt(10,5)
%\GitterPunkt(11,5)
%\GitterPunkt(12,5)
%\GitterPunkt(13,5)
%%
%\GitterPunkt(0,6)
%\GitterPunkt(1,6)
%\GitterPunkt(2,6)
%\GitterPunkt(3,6)
%\GitterPunkt(4,6)
%\GitterPunkt(5,6)
%\GitterPunkt(6,6)
%\GitterPunkt(7,6)
%\GitterPunkt(8,6)
%\GitterPunkt(9,6)
%\GitterPunkt(10,6)
%\GitterPunkt(11,6)
%\GitterPunkt(12,6)
%\GitterPunkt(13,6)
%%
%\GitterPunkt(4,7)
%\GitterPunkt(5,7)
%\GitterPunkt(6,7)
%\GitterPunkt(7,7)
%\GitterPunkt(8,7)
%\GitterPunkt(9,7)
%\GitterPunkt(10,7)
%\GitterPunkt(11,7)
%\GitterPunkt(12,7)
%\GitterPunkt(13,7)
%%
%\GitterPunkt(4,8)
%\GitterPunkt(5,8)
%\GitterPunkt(6,8)
%\GitterPunkt(7,8)
%\GitterPunkt(8,8)
%\GitterPunkt(9,8)
%\GitterPunkt(10,8)
%\GitterPunkt(11,8)
%\GitterPunkt(12,8)
%\GitterPunkt(13,8)
%%
%\GitterPunkt(4,9)
%\GitterPunkt(5,9)
%\GitterPunkt(6,9)
%\GitterPunkt(7,9)
%\GitterPunkt(8,9)
%\GitterPunkt(9,9)
%\GitterPunkt(10,9)
%\GitterPunkt(11,9)
%\GitterPunkt(12,9)
%\GitterPunkt(13,9)
%%
%\GitterPunkt(5,10)
%\GitterPunkt(6,10)
%\GitterPunkt(7,10)
%\GitterPunkt(8,10)
%\GitterPunkt(9,10)
%\GitterPunkt(10,10)
%\GitterPunkt(11,10)
%\GitterPunkt(12,10)
%\GitterPunkt(13,10)
%%
%\GitterPunkt(6,11)
%\GitterPunkt(7,11)
%\GitterPunkt(8,11)
%\GitterPunkt(9,11)
%\GitterPunkt(10,11)
%\GitterPunkt(11,11)
%\GitterPunkt(12,11)
%\GitterPunkt(13,11)
%%
%\GitterPunkt(7,12)
%\GitterPunkt(8,12)
%\GitterPunkt(9,12)
%\GitterPunkt(10,12)
%\GitterPunkt(11,12)
%\GitterPunkt(12,12)
%\GitterPunkt(13,12)
%%
%\GitterPunkt(8,13)
%\GitterPunkt(9,13)
%\GitterPunkt(10,13)
%\GitterPunkt(11,13)
%\GitterPunkt(12,13)
%\GitterPunkt(13,13)
%%
%\GitterPunkt(8,14)
%\GitterPunkt(9,14)
%\GitterPunkt(10,14)
%\GitterPunkt(11,14)
%\GitterPunkt(12,14)
%\GitterPunkt(13,14)
%%
%\GitterPunkt(8,15)
%\GitterPunkt(9,15)
%\GitterPunkt(10,15)
%\GitterPunkt(11,15)
%\GitterPunkt(12,15)
%\GitterPunkt(13,15)
%%
%\Label\u{\eightpoint 0}(0,0)
%\Label\u{\eightpoint 1}(1,0)
%\Label\u{\eightpoint 2}(2,0)
%\Label\u{\eightpoint 3}(3,0)
%\Label\u{\eightpoint 4}(4,0)
%\Label\u{\eightpoint 5}(5,0)
%\Label\u{\eightpoint 6}(6,0)
%\Label\u{\eightpoint 7}(7,0)
%\Label\u{\eightpoint 8}(8,0)
%\Label\u{\eightpoint 9}(9,0)
%\Label\u{\eightpoint 10}(10,0)
%\Label\u{\eightpoint 11}(11,0)
%\Label\u{\eightpoint 12}(12,0)
%\Label\u{\eightpoint 13}(13,0)
%%\Label\l{\eightpoint 1}(0,1)
%%\Label\l{\eightpoint 2}(0,2)
%%\Label\l{\eightpoint 3}(0,3)
%\Label\l{\eightpoint 4}(0,4)
%\Label\l{\eightpoint 5}(0,5)
%\Label\l{\eightpoint 6}(0,6)
%\Label\l{\eightpoint 7}(0,7)
%\Label\l{\eightpoint 8}(0,8)
%\Label\l{\eightpoint 9}(0,9)
%\Label\l{\eightpoint 10}(0,10)
%\Label\l{\eightpoint 11}(0,11)
%\Label\l{\eightpoint 12}(0,12)
%\Label\l{\eightpoint 13}(0,13)
%\Label\l{\eightpoint 14}(0,14)
%\Label\l{\eightpoint 15}(0,15)
\Label\o{E_1}(10,15)
\Label\o{E_2}(11,15)
\Label\o{E_3}(12,15)
\Label\o{E_4}(13,15)
\Label\l{A_1}(0,3)
\Label\l{A_2}(0,2)
\Label\l{A_3}(0,1)
\Label\l{A_4}(0,0)
\Label\lo{P_1}(7,8)
\Label\r{P_2}(6,5)
\Label\ru{P_3}(11,9)
\Label\r{P_4}(12,5)
%\Label\o{\eightpoint\ssize (4)}(4,6)
%\Label\l{\eightpoint\ssize (2)}(8,13)
%\Label\r{\eightpoint\ssize (2)}(13,10)
%\Label\u{\eightpoint\ssize (2)}(12,4)
%\Label\o{\eightpoint\ssize (3)}(8,6)
%\Label\o{\eightpoint\ssize (3)}(7,2)
%\Label\o{\eightpoint\ssize (2)}(9,11)
%\Label\o{\eightpoint\ssize (2)}(5,8)
\Pfad(0,0),1111112121111221222122222222\endPfad
\Pfad(0,1),11122111111221222211222222\endPfad
\Pfad(0,2),112211112211122222122122\endPfad
\Pfad(0,3),2211211122111222222211\endPfad
\Kreis(0,0)
\Kreis(0,1)
\Kreis(0,2)
\Kreis(0,3)
\Kreis(10,15)
\Kreis(11,15)
\Kreis(12,15)
\Kreis(13,15)
\DickPunkt(0,5)
\DickPunkt(2,6)
\DickPunkt(5,8)
\DickPunkt(8,15)
\DickPunkt(2,4)
\DickPunkt(6,6)
\DickPunkt(9,11)
\DickPunkt(10,13)
\DickPunkt(3,3)
\DickPunkt(9,5)
\DickPunkt(10,9)
\DickPunkt(6,1)
\DickPunkt(7,2)
\DickPunkt(11,4)
\DickPunkt(12,7)
%\DickPunkt(0,1)
%\DickPunkt(3,0)
%\DickPunkt(4,4)
%\DickPunkt(4,6)
%\DickPunkt(8,6)
%\DickPunkt(8,10)
%\DickPunkt(8,13)
%\DickPunkt(9,2)
%\DickPunkt(9,8)
%\DickPunkt(10,2)
%\DickPunkt(10,7)
%\DickPunkt(10,15)
%\DickPunkt(12,4)
%\DickPunkt(13,10)
%\DickPunkt(13,11)
%\DickPunkt(13,15)
\hskip5.6cm
$$
\vskip8pt
\centerline{\eightpoint Figure 4}
}
\vskip10pt

Several generalizations of this concept are also considered. These
pose even more difficult turn enumeration problem. We describe just
one such generalization in more detail. Let $\bold
a=(a_1,a_2,\dots,a_n)$ and $\bold b=(b_1,b_2,\dots,b_2)$ be two
vectors of nonnegative integers which are in strictly increasing order. 
Let $I^{\bold a,\bold b}_{n+1}(X)$ denote
the ideal in $K[X]$ that is generated by all $t\times t$
minors of the restriction of $X$ to rows $0,1,\dots,a_t-1$ and
columns $0,1,\dots,b_t-1$, $t=1,2,\dots,n$, and by all $(n+1)\times
(n+1)$ minors of $X$. (What we considered before is the special case
$\bold a=(0,1,\dots,n-1)$ and $\bold b=(0,1,\dots,n-1)$.)
Again, the associated {\it determinantal
ring\/} is $R^{\bold a,\bold b}_{n+1}(X):=K[X]/I^{\bold a,\bold
b}_{n+1}(X)$.
(For more information on these rings see \cite{\HeTrAA} and the
references in this paper.)
In the aforementioned papers 
\cite{\AbhyAB, \AbKuAC, \CoHeAA, \KulkAC} 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 $\bold a$ and $\bold b$ respectively.
\proclaim{Theorem 2}Let 
$A_i=(0,a_{n-i+1})$ and $E_i=(a-b_{n-i+1},b)$, $i=1,2,\dots,n$. 
Then the Hilbert series of the determinantal
ring $R^{\bold a,\bold b}_{n+1}(X)=K[X]/I^{\bold a,\bold b}_{n+1}(X)$ equals
$$\sum _{\ell=0}
^{\infty}\dim_K\big(R^{\bold a,\bold b}_{n+1}(X)_\ell \big)\,z^\ell=\frac {\sum _{\P} ^{}z^{\NE(\P)}}
{(1-z)^{(a+b+1)n-\sum _{i=1} ^{n}(a_i+b_i)}},\tag3.5$$
where the sum on the right-hand side is over all families
$\P=(P_1,P_2,\dots,P_n)$ of nonintersecting lattice paths, $P_i$
running from $A_i$ to $E_i$, $i=1,2,\dots,n$.

\endproclaim

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 
\cite{\AbhyAB, \AbKuAC} for the ladder case, by
Conca \cite{\ConcAC} for minors of a symmetric matrix, and by Ghorpade 
and this author \cite{\GhKrAA} for minors of pfaffians, that the
computation of Hilbert series for the resulting rings again requires
to enumerate 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.
\endexample

\subhead 4. Turn enumeration of (single) lattice paths\endsubhead
Examples~1 and 2 of the previous section, and the $n=1$ case of
Example~3, lead to the problem of
turn enumeration of lattice paths, in some way, as was made specific
above. In the next section we show that if one knows the answer for
the enumeration of lattice paths with a given number of {\it
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 point,
satisfying certain restrictions, and with a given number of NE-turns.
This is exactly what we do in this section.

The first question, namely `{\it what is the number of paths from
$A=(a_1,a_2)$ to $E=(e_1,e_2)$ with exactly $\ell$ NE-turns}', is 
immediately answered by
$$\v{\L{(a_1,a_2)\to (e_1,e_2)\mid \NE(.)=\ell}}=
\binom {e_1-a_1}\ell\binom {e_2-a_2}\ell.\tag4.1$$
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 $\ell$ for each of
those. Thus (4.1) 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)$, \dots,
$(p_\ell,q_\ell)$ be the NE-turns of a path $P$. Then the {\it NE-turn
representation\/}
of $P$ is defined by the two-rowed array
$$\matrix
p_1&p_2&\dots&p_\ell\hphantom{,}\\
q_1&q_2&\dots&q_\ell,
\endmatrix\tag4.2$$
which consist of two strictly increasing sequences. Sometimes we will
also use a one-line notation, $(p_1,\dots,p_\ell\mid
q_1,\dots,q_\ell)$, or even shorter $(p\mid q)$ where
$p=(p_1,\dots,p_\ell)$ and $q=(q_1,\dots,q_\ell)$.

Clearly, if 
$P$ runs from $(a_1,a_2)$ to $(e_1,e_2)$ then there hold $a_1\le p_1<p_2<\dots<
p_\ell\le e_1-1$ and $a_2+1\le q_1<q_2<\dots<q_\ell\le e_2$. If we wish to
make this fact transparent, we write
$$
\matrix\format\r&\quad\c&\quad\c&\quad\c&\quad\c&\quad\l\\
a_1\le&\quad p_1&p_2&\dots&p_\ell&\quad \le e_1-1\\
a_2+1\le&\quad q_1&q_2&\dots&q_\ell&\quad \le e_2.
\endmatrix\tag4.3$$
For a given starting point and a given final 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~1 would be
$$\matrix 1\ 2\ 5\\1\ 3\ 4\endmatrix\ ,$$
or with bounds included,
$$\matrix\format\r\quad &\quad\c&\quad\c&\quad\c&\quad\quad \l\\
 1\le&1&\ 2&\ 5&\le5\\0\le&1&\ 3&\ 4&\le6\endmatrix\ .$$

Apparently, in order to find the distribution for the game of
Example~1 with $\mu=1$, and to find the joint distribution for runs
and one-sided Kolmogorov-Smirnov statistics, 
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 our
first theorem.
\proclaim{Theorem 3}Let $a_1\ge a_2$ and $e_1\ge e_2$. 
The number of all lattice paths from $(a_1,a_2)$ to
$(e_1,e_2)$ staying below $x=y$ (being allowed to touch it)
with exactly $\ell$ NE-turns is given by
$$\multline
\v{\L{(a_1,a_2)\to (e_1,e_2)\mid x\ge y,\,\NE(.)=\ell}}\\
=\binom {e_1-a_1}{\ell}\binom{e_2-a_2}\ell - \binom {e_1-a_2-1}{\ell-1}
\binom{e_2-a_1+1}{\ell+1} .
\endmultline\tag4.4
$$
\endproclaim

\remark{Remark} 
Before we sketch a proof of this theorem a remark is in order. The
reader should 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 {\it
reflection principle\/} (see e.g\. \cite{\ComtAA, 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
analogue of the reflection principle for two-rowed arrays.
\endremark

\demo{Proof} The paths from $(a_1,a_2)$
to $(e_1,e_2)$ staying below $x=y$ with exactly $\ell$ NE-turns
by the NE-turn representation can be
represented by
$$\matrix\format\r&\quad\c&\quad\c&\quad\c&\quad\c&\quad\l\\
a_1\le&\quad p_1&p_2&\dots&p_\ell&\quad \le e_1-1\\
a_2+1\le&\quad q_1&q_2&\dots&q_\ell&\quad \le e_2,
\endmatrix\tag4.5a$$
where
$$
p_i\ge q_i, \quad \quad i=1,2,\dots,\ell.
\tag4.5b$$
The number
of these two-rowed arrays is the number of {\it all\/} two-rowed arrays
of the type (4.5a) minus those two-rowed arrays of the type
(4.5a) which violate (4.5b), i.e\. where $p_i<q_i$ for
some $i$ between $1$ and $\ell$. We know the first number from
(4.1). 

Concerning the second number, we claim that two-rowed arrays of the
type (4.5a) which violate (4.5b) are in one-to-one
correspondence with two-rowed arrays of the type 
$$\matrix\format\r&\quad\c&\quad\c&\quad\c&\quad\c&\quad\c&\quad\l\\
a_2+1\le&\quad &&r_2&\dots&r_\ell&\quad \le e_1-1\\
a_1\le&\quad s_0&s_1&s_2&\dots&s_\ell&\quad \le
e_2.\endmatrix\tag4.6$$
The number of all these two-rowed arrays is $\binom {e_1-a_2-1}{\ell-1}
\binom {e_2-a_1+1}{\ell+1}$, as desired. So it only remains to construct
the one-to-one correspondence.

Take a two-rowed array $(p\mid q)$ of the type (4.5a) such that
$p_i<q_i$ for some $i$. Let $I$ be the largest integer such that
$p_I<q_I$. Then map $(p\mid q)$ to
$$\matrix\format\c&\quad\c&\quad\c&\quad\c&\quad\c&\quad\c&\quad\c&\quad\c&\quad\c\\
&&q_1\kern15pt&\dots\dots &q_{I-1}&p_{I+1}&\dots&p_\ell\\
p_1&p_2&\dots\dots&\kern15ptp_I&q_I&q_{I+1}&\dots&q_\ell
\endmatrix.\tag4.7$$
Observe that both rows are strictly increasing because of
$q_{I-1}<q_I<q_{I+1}\le p_{I+1}$ (recall: $I$ is largest with
$p_I<q_I$) and $p_I<q_I$. By some case by case
analysis it can be seen that (4.7) is of type (4.6).

The inverse of this map is defined in the same way. Let $(r\mid
s)$
be a two-rowed array of the type (4.6). Let $J$ be the
largest integer such that $r_{J}<s_{J}$. If there
is no, take $J=1$. Then map $(r\mid s)$ to
$$\matrix\format\c&\quad\c&\quad\c&\quad\c&\quad\c&\quad\c&\quad\c\\
s_0&\hdotsfor2&s_{J-1}&r_{\bar
I+1} &\dots&r_\ell\\
r_2&\dots&r_{J}&s_{J}&\hdotsfor2&s_\ell
\endmatrix.\tag4.8$$
It is not difficult to check that the mappings (4.7) and
(4.8) are inverses of each other. This completes the proof of
(4.4).\quad \quad \qed
\enddemo

In order to solve the generalized problem in Example~1 (where the game
is stopped when the number of heads exceeds $\mu$ times 
the total number of tails by exactly $a$), we need to count 
lattice paths, with given starting and end
point, and with a given number of NE-turns, 
which stay below a line of the form $y=\mu x$. In parallel with 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~1. 

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

\proclaim{Theorem 4}Let $\mu$ be a positive integer and
let $e_1\ge \mu e_2$. 
The number of all lattice paths from $(0,0)$ to
$(e_1,e_2)$ staying below $x=\mu y$ (being allowed to touch it)
with exactly $\ell$ NE-turns is given by
$$
\v{\L{(0,0)\to (e_1,e_2)\mid x\ge \mu y,\,\NE(.)=\ell}}
=\binom {e_1}{\ell}\binom{e_2}\ell - \mu \binom {e_1-1}{\ell-1}
\binom{e_2+1}{\ell+1} .
\tag4.9
$$
\endproclaim

\demo{Proof} Again we represent our paths from $(0,0)$
to $(e_1,e_2)$ staying below $x=\mu y$ with exactly $\ell$ NE-turns, 
by their NE-turn representation. It reads
$$\matrix\format\r&\quad\c&\quad\c&\quad\c&\quad\c&\quad\l\\
0\le&\quad p_1&p_2&\dots&p_\ell&\quad \le e_1-1\\
1\le&\quad q_1&q_2&\dots&q_\ell&\quad \le e_2,
\endmatrix\tag4.10a$$
where
$$
p_i\ge \mu q_i, \quad \quad i=1,2,\dots,\ell.
\tag4.10b$$
Again, the number
of these two-rowed arrays is the number of {\it all\/} two-rowed arrays
of the type (4.10a) minus those two-rowed arrays of the type
(4.10a) which violate (4.10b), i.e\. where $p_i<\mu q_i$ for
some $i$ between $1$ and $\ell$. We know the first number from
(4.1). 

This time, we claim that there are as many two-rowed arrays of the
type (4.10a) which violate (4.10b) as $\mu$ times
the number of two-rowed arrays of the type 
$$\matrix\format\r&\quad\c&\quad\c&\quad\c&\quad\c&\quad\c&\quad\l\\
1\le&\quad &&r_2&\dots&r_\ell&\quad \le e_1-1\\
0\le&\quad s_0&s_1&s_2&\dots&s_\ell&\quad \le
e_2.\endmatrix\tag4.11$$
The number of all these two-rowed arrays is $\binom {e_1-1}{\ell-1}
\binom {e_2+1}{\ell+1}$, as desired. What remains to do is to find a
$(1:\mu)$ correspondence between the two-rowed arrays of type (4.10a),
violating (4.10b), and those of type (4.11).

Take a two-rowed array $(p\mid q)$ of the type (4.10a) such that
$p_i<\mu q_i$ for some $i$. Let $I$ be the largest integer such that
$p_I<\mu q_I$. The two-rowed array $(p\mid q)$ then looks like
$$\smatrix \format\r&\quad \c&\quad \c&\quad \c\s\c\s\c&\quad \c&\quad\l\\
0\le&p_1&\innerhdotsfor2\after\quad &\omit&p_I&&\dots&p_\ell&\le e_1-1\\
\omit&\omit&\omit&\omit&\hlinefor3&\omit&\omit&\omit\\
1\le&q_1&\dots&q_{I-1}&&q_I&\omit&\dots&q_\ell&\le e_2
 \endsmatrix.
\tag4.12$$
Now we fix the right portion, i.e., the entries
$p_{I+1},\dots,p_{\ell}$ and $q_I,\dots,q_\ell$. With this fixed
right portion there are 
$$\binom {\mu q_I}I\cdot\binom {q_I-1}{I-1}\tag4.13$$
possible left portions.

On the other hand, let $(r\mid s)$ be a two-rowed array of the type
(4.11). Let $I$ be maximal with $r_I<\mu s_I$ (if there is no such $I$
take $I=1$), so that $(r\mid s)$ look like
$$\smatrix \format\r&\quad \c&\quad \c&\quad \c&\quad \c\s\c\s\c&\quad \c&\quad\l\\
1\le&\quad &\quad &r_2&\dots &\omit&r_I&&\dots&r_\ell&\le e_1-1\\
\omit&\omit&\omit&\omit&\omit&\hlinefor3&\omit&\omit&\omit\\
0\le&s_0&\innerhdotsfor2\after\quad &s_{I-1}&&s_I&\omit&\dots&s_\ell&\le e_2
 \endsmatrix.
\tag4.14$$
Again, fix the right portion, i.e., the entries 
$r_{I+1},\dots,r_{\ell}$ and $s_I,\dots,s_\ell$. More precisely,
let them equal the right portion in (4.12), i.e., let $r_i=p_i$,
$i=I+1,\dots,\ell$, and $s_i=q_i$, $i=I,\dots,\ell$. With this fixed
right portion there are 
$$\binom {\mu q_I-1}{I-1}\cdot\binom {q_I}{I}=\frac {1} {\mu}
\binom {\mu q_I}I\cdot\binom {q_I-1}{I-1}
\tag4.15$$
possible left portions. By comparing with (4.13), we see that, for a
fixed right portion, there are $\mu$ times as many two-rowed arrays
of the type (4.12), with $p_I<\mu q_I$, as there are two-rowed arrays
of the type (4.14), with $r_I<\mu s_I=\mu q_I$. This settles our
claim and hence finishes the proof of the theorem.\quad \quad \qed

\enddemo

\remark{Remark} The above proof could be made purely bijective if one
could find a bijection for the binomial identity (4.15), i.e., for
$$\mu\binom {\mu q_I-1}{I-1}\cdot\binom {q_I}{I}=
\binom {\mu q_I}I\cdot\binom {q_I-1}{I-1}.\tag4.16$$
Embarassingly, I was not able to find any.

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

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

\proclaim{Theorem 5}Let $\mu$ be a positive integer and
let $e_1\ge \mu e_2$. 
The number of all lattice paths from $(0,0)$ to
$(e_1,e_2)$ staying below $x=\mu y$ (being allowed to touch it)
with exactly $\ell$ EN-turns is given by

\vbox{
$$
\v{\L{(0,0)\to (e_1,e_2)\mid x\ge \mu y,\,\EN(.)=\ell}}
=\binom {e_1+1}{\ell}\binom{e_2-1}{\ell-1} - \mu \binom {e_1}{\ell-1}
\binom{e_2}{\ell} .
\tag4.17
$$
\line{\hfil\hbox{\qed}\quad \quad }
}
\endproclaim



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

\proclaim{Theorem 6}Let $a_1+t\ge a_2\ge a_1+s$ and $e_1+t\ge e_2\ge 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 $\ell$ NE-turns is given by
$$\multline 
\v{\L{(a_1,a_2)\to (e_1,e_2)\mid x+t\ge y\ge x+s,\,\NE(.)=\ell}}\\
=\sum _{k\in\Z} ^{}\bigg(\binom
{e_1-a_1-k(t-s)} {\ell+k}\binom {e_2-a_2+k(t-s)}{\ell-k}\kern3cm\\
-\binom {e_1-a_2+k(t-s)
+t-1}{\ell-k} \binom {e_2-a_1-k(t-s)-t+1}{\ell+k}\bigg). 
\endmultline\tag4.18$$
\endproclaim

\remark{Remark} 
Again, a remark is in order before we begin with the proof. The
reader should 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 {\it iterated\/}
reflection principle (see e.g\. \cite{\MohaAE, proof of
Theorem~2 on p.~6}). 
The proof below can be considered as the
analogue of iterated reflection principle for two-rowed arrays.
\endremark

\demo{Proof} 
By the NE-turn representation, the paths under consideration
are in one-to-one correspondence with two-rowed arrays of the type
$$\matrix\format \r&\quad\c&\quad\c&\quad\c&\quad\l\\
a_1\le&p_1&\dots&p_\ell&\le e_1-1\\
a_2+1\le&q_1&\dots&q_\ell&\le e_2
\endmatrix\tag4.19a$$
where
$$
p_i+t\ge q_i\ge p_{i+1}+s.
\tag4.19b$$
Similar to the proof of Theorem~3, 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
$$\matrix\format \r&\quad\c&\quad\c&\quad\c&\quad\c&\quad\c&\quad\l\\
a_1+k(t-s)\le&p_{1-k}&\dots&p_{1+k}&\dots&p_\ell&\le e_1-1\\
a_2+1-k(t-s)\le&&&q_{1+k}&\dots&q_\ell&\le e_2
  \endmatrix\quad \quad \text{for }k\ge0
$$
and 
$$\matrix\format \r&\quad\c&\quad\c&\quad\c&\quad\c&\quad\c&\quad\l\\
a_1+k(t-s)\le&&&p_{1-k}&\dots&p_\ell&\le e_1-1\\
a_2+1-k(t-s)\le&q_{1+k}&\dots&q_{1-k}&\dots&q_\ell&\le e_2
  \endmatrix\quad \quad \text{for }k<0
$$
{\it type I arrays\/}. Similarly, we call two-rowed arrays of the type
$$\matrix\format \r&\quad\c&\quad\c&\quad\c&\quad\c&\quad\c&\quad\l\\
a_2+1-t+k(t-s)\le&p_{1-k}&\dots&p_{1+k}&\dots&p_\ell&\le e_1-1\\
a_1+t-k(t-s)\le&&&q_{1+k}&\dots&q_\ell&\le e_2
  \endmatrix\quad \quad \text{for }k\ge0
$$
and 
$$\matrix\format \r&\quad\c&\quad\c&\quad\c&\quad\c&\quad\c&\quad\l\\
a_2+1-t+k(t-s)\le&&&p_{1-k}&\dots&p_\ell&\le e_1-1\\
a_1+t-k(t-s)\le&q_{1+k}&\dots&q_{1-k}&\dots&q_\ell&\le e_2
  \endmatrix\quad \quad \text{for }k<0
$$
{\it type II arrays\/}. We shall set up a
bijection between type I arrays not being of the type (4.19)
(which means that (4.19b) must be violated if both rows have
equal length) and type II arrays. Given such a bijection, we could deduce
$$
\v{\{\text{type I arrays}\}}-\v{\{\text {type II arrays}\}}
=\v{\{\text {arrays of type (4.19)}\}}.
\tag4.20$$
The arrays of type (4.19) exactly correspond to the paths we
are intending to enumerate. By definition of type I and type II arrays,
the left-hand side in (4.20) equals the sum side in
(4.18). Thus (4.18) would be established.

The definition of the bijection and its inverse can be given in a
unified form. Let $(p\mid q)$ be a type I array not of the type
(4.19) or a type II array,
$$
\matrix p_{1-k}&\hdotsfor3&p_\ell\\
&\quad &q_{1+k}&\dots&q_\ell\endmatrix.
$$
(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\le I\le \ell$  such that either
$$
q_I>p_I+t\quad \text{or}\quad I=-k,
\tag4.21$$
or
$$
q_I<p_{I+1}+s\quad \text{or}\quad I=k.
\tag4.22$$
If (4.21) is satisfied then map $(p\mid q)$ to
$$\matrix
&&(q_{1+k}-t)&\hdotsfor2&(q_{I-1}-t)&p_{I+1}&\dots&p_\ell\\
(p_{1-k}+t)&\hdotsfor3&(p_I+t)&q_I&\hdotsfor2&q_\ell\\
&\quad &\quad &\quad &\quad &\quad &\quad &\quad &\quad 
\endmatrix.$$
Note that both rows are strictly increasing because of
$q_{I-1}<q_{I+1}\le p_{I+1}+t$ and $p_I+t<q_I$. If (4.21) is not
satisfied, but hence (4.22) is, map $(p\mid q)$ to 
$$\matrix &\quad &(q_{1+k}-s)&\dots&(q_I-s)&p_{I+1}&\dots&p_\ell\\
(p_{1-k}+s)&\hdotsfor3&(p_I+s)&q_{I+1}&\dots&q_\ell
\endmatrix.$$
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\le q_{I+1}$. 

It is not difficult to verify that this mapping maps type I arrays not
being of type (4.19) to type II arrays not
being of type (4.19), and vice versa. Besides,
by applying this map to some array twice, one would obtain this array
back. Therefore this mapping is the desired bijection.\quad \quad
\qed
\enddemo
Theorem~6 and its proof are basically from \cite{\KrMoAA}. Actually, Theorem~1
of \cite{\KrMoAA} provides a $q$-analogue. A closely related paper is
Burge's paper \cite{\BurgAC}. There, ``restricted partition pairs" are
considered, which are nothing else as two-rowed arrays with
restrictions very similar to (4.19b). 
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 at the same time 
Rogers' proof and Schur's proof of the
Rogers--Ramanujan identities, which previously were considered to be
unrelated. Eventually, the notion of partition pairs was generalized
to $r$-tuples of partitions and were investigated by Gessel and this
author \cite{\GeKrAA} 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, many of them new. A
solution for two-sided ladders is proposed by Ghorpade (private
communication).

\medskip
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\times 2$
minors. ``Nice" formulas cannot be expected here in general. 
Solutions for ``one-sided" ladders 
were proposed by Kulkarni \cite{\KulkAD} and this author
and Prohaska \cite{\KrPrAA}. Niederhausen's \cite{\NiedAR} approach
using umbral calculus methods is also worth mentioning here, though
it is formulated only for EN-turns.


\subhead 5. Applications\endsubhead
In this section we apply the results from the previous section to
solve (some of) the problems of section~3. 

{\it ad Example~1}. We saw that any game of
length $(\mu+1)n+a$ corresponds to a path from $(0,0)$ to $(n,\mu n+a-1)$
staying below the line $y=\mu x+a-1$. Equivalently, by reversal of
paths, it corresponds to
a path from $(0,0)$ to $(\mu n+a-1,n)$ staying below the line $x=\mu
y$. Also, in (3.1)--(3.3), 
we expressed the probability of a game of length $(\mu
+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 $(\mu +1)n+a$, is immediately obtained from
Theorem~4 with $e_1=\mu n+a-1$ and $e_2=n$:

{\sl A game starting with a toss of coin 1 has length $(\mu+1)n+a$
with probability}
$$\multline\sum _{\ell=0} ^{n}\(\binom {\mu n+a-1}{\ell}\binom {n}{\ell}
-\mu \binom {\mu n+a -2}{\ell-1}\binom {n+1}{\ell+1}\)\\
\times p_1^{\ell+1}(1-p_1)^{n-\ell}p_2^{\mu
n+a-\ell-1}(1-p_2)^{\ell}.
\endmultline\tag5.1$$

Of course, also games starting with a toss of coin 2 can be
represented by a path from $(0,0)$ to $(\mu n+a-1,n)$ staying below the 
line $x=\mu y$. However, we have a split expression,
namely (3.2), respectively (3.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 now we consider paths $\bar P$ from $(0,0)$ to
$(\mu n+a,n)$ {\it ending with a horizontal step} and staying below the 
line $x=\mu y$. Then it is easy to see that (3.2) and (3.3), in terms
of $\bar P$, become
$$p_1^{\NE(\bar P)}(1-p_1)^{n-\NE(\bar P)}p_2^{\mu
n+a-\NE(\bar P)}(1-p_2)^{\NE(\bar P)}.\tag5.2$$
Since the number of paths in question which have $\ell$ NE-turns is just
the difference of the number of paths from $(0,0)$ to $(\mu n+a,n)$ 
staying below $x=\mu y$ and having $\ell$ NE-turns, minus the number of 
paths from $(0,0)$ to $(\mu n+a,n-1)$ (!)
staying below $x=\mu y$ and having $\ell$ NE-turns, we obtain from
Theorem~4 by simplifying the difference:

{\sl A game starting with a toss of coin 2 has length $(\mu+1)n+a$
with probability}
$$\multline\sum _{\ell=0} ^{n}\(\binom {\mu n+a}{\ell}\binom
{n-1}{\ell-1}
-\mu \binom {\mu n+a -1}{\ell-1}\binom {n}{\ell}\)\\
\times p_1^{\ell}(1-p_1)^{n-\ell}p_2^{\mu
n+a-\ell}(1-p_2)^{\ell}.
\endmultline\tag5.3$$

\medskip
{\it ad Example~2}. We have to convert our enumeration results for
NE-turns 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 formulations, 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 
$\sum _{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\to E\mid R;x)$. We define four refinements of
$F(A\to E\mid R;x)$. Let $F_{hv}(A\to E\mid R;x)$ be the generating
function $\sum _{P} ^{}x^{\NE(P)}$ where the sum is over all paths in
$L(A\to E\mid R)$ that start with a horizontal step and end with a
vertical step. Similarly define $F_{hh}(A\to E\mid R;x)$, $F_{vh}(A\to
E\mid R;x)$, and $F_{vv}(A\to E\mid R;x)$. 
The relation between
enumeration by runs and enumeration by NE-turns is given by
$$\multline 
\sum _{P\in L(A\to E\mid R)} ^{}x^{\run(P)}=
xF_{hh}(A\to E\mid R;x^2) +x^2
F_{hv}(A\to E\mid R;x^2)\\
+ F_{vh}(A\to E\mid R;x^2)+xF_{vv}(A\to E\mid R;x^2).
\endmultline\tag5.4$$


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 equation and solving them. Evidently, there holds
$$\multline
F(A\to E\mid R;x)=F_{hh}(A\to E\mid R;x) +
F_{hv}(A\to E\mid R;x)\\
+ F_{vh}(A\to E\mid R;x)+F_{vv}(A\to E\mid R;x).
\endmultline$$
Besides, if $E_1=(1,0)$ and $E_2=(0,1)$ denote the standard unit
vectors, we have
$$\align
F_{hh}(A\to E\mid R;x)+F_{hv}(A\to E\mid R;x)&=F(A+E_1\to E\mid R;x)\\
F_{hv}(A\to E\mid R;x)+F_{vv}(A\to E\mid R;x)&=F(A\to E-E_2\mid R;x)\\
F_{hv}(A\to E\mid R;x)&=F(A+E_1\to E-E_2\mid R;x).
\endalign$$
Solving for $F_{hh}$, $F_{hv}$, $F_{vh}$, $F_{vv}$ we get
$$\align
F_{hh}(A\to E\mid R;x)&=F(A+E_1\to E\mid R;x)-F(A+E_1\to E-E_2\mid
R;x)\tag5.5\\
F_{hv}(A\to E\mid R;x)&=F(A+E_1\to E-E_2\mid R;x)\tag5.6\\
F_{vh}(A\to E\mid R;x)&=F(A\to E\mid R;x)+(A+E_1\to E-E_2\mid
R;x)\tag5.7\\
&\hskip1cm -F(A+E_1\to E\mid R;x)-F(A\to E-E_2\mid R;x)\\
F_{vv}(A\to E\mid R;x)&=F(A\to E-E_2\mid R;x)-F(A+E_1\to E-E_2\mid R;x).
\tag5.8
\endalign$$

Now, turning to the joint distribution of runs and two-sided 
Kolmogorov-Smirnov
statistics, we saw 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 (5.4) with $A=(0,0)$, $E=(n,n)$, $R$
meaning the property to `stay between $y=x+t$ and $y=x-t$', then
using the equations (5.5)--(5.8) for $F_{hh},F_{hv},F_{vh},F_{vv}$,
respectively, in (5.4), and finally applying Theorem~6 to obtain explicit
expansions for the various generating functions $F(\dots)$. A
comparison of coefficients of powers of $z$ then gives, after some
manipulation of binomials: 

{\it For the joint distribution of runs, denoted by $R_{n,n}$,
 and the two-sided Kolmogorov--Smirnov statistics $D_{n,n}$ there hold
$$\multline \binom {2n}n P(D_{n,n}\le t/n,\ R_{n,n}=2r+1)\\
=\sum _{k\in\Z} ^{}\bigg(\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}\bigg),
\endmultline$$
respectively
$$\multline \binom {2n}n P(D_{n,n}\le t/n,\ R_{n,n}=2r)\\
=\sum _{k\in\Z} ^{}\bigg(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}\bigg).
\endmultline$$
}

\noindent
Thus we recover results of Vellore \cite{\VellAA, Theorems~8 and
9}. She derived these results by very different means. (The
expressions therefore look differently. But it is not difficult to
see that they are really equivalent.)
The path of
derivation we have chosen here is from \cite{\KrMoAC} where it was
also used to obtain extensions and $q$-analogues of the above result.

\medskip
{\it ad Example 3}. By Theorems~1 and 2, 
the $n=1$ case of Example~3, i.e., the case of
rings generated by (at most) $2\times 2$ minors in the way described
above, 
leads to the problem of enumerating paths with given starting and
end point which have a given number of NE-turns. Clearly, this is
done by (4.1). 

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

\subhead 6. Nonintersecting lattice paths and
turns\endsubhead
Here we complete the solutions to our Examples of section~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 in Example~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 classical now (cf\. \cite{\GeViAA;
\GeViAB, Cor.~2; \StemAE, Theorem~1.2}). In fact, it was realized
over the past ten years that nonintersecting lattice paths have
innumerable applications in combinatorics, probability, statistics,
physics, etc\. (see the references in \cite{\KratAV} for
combinatorial applications, 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 determinant" \cite{\MohaAC, \StecAA} follow easily
from nonintersecting lattice paths, see also \cite{\SulaAC}).
However, the method that
is used for the plain enumeration (the ``Gessel--Viennot
involution", which actually can be traced back to Lindstr\"om
\cite{\LindAA} and Karlin and McGregor \cite{\KaMGAC}), 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
\cite{\KratAP} and of identities for Schur functions \cite{\KratAQ}.

From Theorems~1 and 2 we know for the computation of the Hilbert series for
the determinantal rings $R_{n+1}(X)$ and $R^{\bold a,\bold b}_{n+1}(X)$
we need to enumerate families
$\P=(P_1,P_2,\dots,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,\dots,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,\dots,A_n)$ and
$\E=(E_1,E_2,\dots,E_n)$ be points in $\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
\cite{\GeViAB, \StemAE}). 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.

\proclaim{Theorem 7}
Let 
$A_i=(a_1^{(i)},a_2^{(i)})$ and $E_i=(e_1^{(i)},e_2^{(i)})$,
$i=1,2,\dots,n$, be lattice points satisfying
$$a_1^{(1)}\le a_1^{(2)}\le\dotsb\le a_1^{(n)},\quad
a_2^{(1)}>a_2^{(2)}>\dotsb>a_2^{(n)},$$
and
$$e_1^{(1)}< e_1^{(2)}<\dotsb< e_1^{(n)},\quad
e_2^{(1)}\ge e_2^{(2)}\ge \dotsb\ge e_2^{(n)}.$$
The generating function $\sum _{\P} ^{}z^{\NE(P)}$, where the sum is
over all families $\P=(P_1,P_2,\mathbreak
\dots,P_n)$ of nonintersecting lattice paths $P_i:A_i\to E_i$, equals
$$
\det_{1\le i,j\le n}
\bigg(\sum _{k\ge0} ^{}\binom{e_1^{(i)}-a_1^{(j)}+j-i}{k+j-i}
\binom{e_2^{(i)}-a_2^{(j)}-j+i}{k}z^k\bigg).
\tag6.1$$
\endproclaim

\remark{Remark} This theorem was independently proved by Kulkarni
\cite{\KulkAC}, who derived it from a theorem on determinantal rings
due to Abhyankar, by Modak \cite{\ModaAA}, who found a manipulatory
proof, and for the first time by combinatorial means by this author 
\cite{\KratBE, \KratAW}, using two-rowed arrays. See also Ghorpade's
paper \cite{\GhorAD}.
\endremark
\demo{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\to E$,
$P_2: B\to 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\le b_1,\ a_2>b_2,\ e_1< f_1,\ e_2\ge f_2.$$
 Let the array representations of $P_1$ and $P_2$ 
be
$$
P_1:\quad \matrix\format \r&\quad \c&\quad \c&\quad \c&\quad \l\\
a_1\le&p_1&\hdots&p_k&\le e_1-1\\
a_2+1\le&q_1&\hdots&q_k&\le e_2\endmatrix\hphantom{\ ,}
\tag6.2$$
and
$$
P_2:\quad \matrix\format \r&\quad \c&\quad \c&\quad \c&\quad \l\\
b_1\le&r_1&\hdots&r_l&\le f_1-1\\
b_2+1\le&s_1&\hdots&s_l&\le f_2\endmatrix\ ,
\tag6.3$$
respectively. 

Suppose that $P_1$ and $P_2$ intersect, i.e\. have a point in common.
Let $\Sch$ 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.)

\vskip10pt
\vbox{
$$
\Pfad(0,0),221111121111\endPfad
\Pfad(-2,-1),11112222221111\endPfad
\DickPunkt(0,2)
\DickPunkt(2,2)
\DickPunkt(2,-1)
\Label\ru{\Sch}(2,2)
\Label\lo{\hskip-10pt(r_J,s_J)}(0,2)
\Label\ru{(p_I,q_{I-1})}(2,-1)
\Label\r{P_1}(6,5)
\Label\r{P_2}(9,3)
\hskip4cm
$$
\centerline{\eightpoint Figure 5}
}
\vskip10pt
Considering the east-north turn $(p_I,q_{I-1})$ in $P_1$
immediately preceding $\Sch$ (and being allowed to be equal to $\Sch$)
and the north-east turn $(r_J,s_J)$ in $P_2$ immediately preceding
$\Sch$ (and being allowed to be equal to $\Sch$), we get the inequalities
(cf\. Figure~5)
$$\gather r_J\le p_I,\tag6.4a\\
 q_{I-1}\le
s_J,\tag6.4b
\endgather$$
where
$$
1\le I\le k+1,\quad 1\le J\le l.
\tag6.4c$$

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 (6.4a,b) to make sense for $I=1$ or $I=k+1$.
Note that $\Sch=(p_I,s_J)$. Vice versa, if (6.4a,b,c) is satisfied then 
there must be a meeting point between $P_1$ and $P_2$ (because of the
particular location of the starting and end points $ A, B, E, F$). 

Summarizing, the existence of $I,J$
satisfying (6.4a,b,c) characterize the array representations of
{\it intersecting\/} pairs of paths. Therefore, we call two-rowed
arrays $P_1$ and $P_2$ of the form (6.2) and (6.3), respectively,
{\it intersecting} if (6.4a,b,c) is satisfied, for some $I$ and $J$, 
otherwise {\it
nonintersecting}. The point $\Sch=(p_I,s_J)$ is called their {\it
intersection point}.

We also need to consider {\it skew\/} two-rowed arrays.
For convenience, we introduce some terminology. Let
$j>0$. We say that the two-rowed array $P$ {\it is of the type\/} $j$
if $P$ has the form
$$\matrix\format \c&\quad \c&\quad \c&\quad \c&\quad \c&\quad \c&\quad
\c&\quad \c\\
 p_{-j+1}&p_{-j+2}&\dots&p_{-1}&p_0&p_1&\dots&p_k\\
&&&&&q_1&\dots&q_k\endmatrix$$
for some $k\ge0$. We say that $P$ {\it is of the type\/} $-j$ if $P$ has
the form
$$\matrix\format \c&\quad \c&\quad \c&\quad \c&\quad \c&\quad \c&\quad
\c&\quad \c&\quad \c\\
&&&&&p_1&\dots&p_k\\
 q_{-j+1}&q_{-j+2}&\dots&q_{-1}&q_0&q_1&\dots&q_k\endmatrix$$
for some $k\ge0$. Note that the placement of indices is chosen such
that non-positive indices can occur only in {\it one\/} row of $P$,
while the positive indices occur in both rows of $P$. The meaning
of non-skew two-rowed arrays being intersecting, respectively 
nonintersecting, and of intersection points, is extended to
skew two-rowed arrays in the obvious way.


Now we are in the position to actually begin with the proof of (6.1).
First we give the combinatorial interpretation of the determinant
(6.1) 
in terms of two-rowed arrays. 
Expanding the determinant in (6.1) we obtain
$$\multline
\sum _{\si\in\frak S_n} ^{}\sgn\si \prod _{i=1} ^{n}
\binom{e_1^{(i)}-a_1^{(\si(i))}+\si(i)-i}{k_i+\si(i)-i}
\binom{e_2^{(i)}-a_2^{(\si(i))}-\si(i)+i}{k_i}z^{k_i}\\
=\sum _{(\si,\P)} ^{}\sgn\si \,z^{\NE(\P)},
\endmultline\tag6.5$$
where $\frak S_n$ denotes the symmetric group of order $n$, and where
the sum on the right-hand side 
is over all pairs $(\P, \si)$ of permutations $\si$
in $\frak S_n$, and families 
$\P=(P_1,P_2,\dots,P_n)$ of two-rowed arrays, $P_i$ being of type
$\si(i)-i$,
 and the bounds for the entries of $P_i$ being as follows,
$$
\matrix\format  \r&\quad \c&\quad \l\\
a_1^{(\si(i))}+i-\si(i)\le&\dots\ p_{\ell_i}^{(i)}&\le e_1^{(i)}-1\\
a_2^{(\si(i))}-i+\si(i)+1\le&\dots\ q_{\ell_i}^{(i)}&\le e_2^{(i)}
\endmatrix,
\tag6.6$$
$i=1,2,\dots,n$.

The outline of the proof is as follows. We show that in the
sum on the right-hand side of (6.5) 
all contributions corresponding to pairs $(\P,\si)$ where
$\P$ is an intersecting family 
of two-rowed arrays cancel. (Clearly, a pair $(\P,\si)$ where $\P$
contains neighbouring
two-rowed arrays which intersect will be called 
{\it intersecting\/}.
Otherwise it will be called {\it nonintersecting\/}.) This is done by
constructing a sign-reversing (with respect to $\sgn\si$) 
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 two-rowed array.) 
Finally it is shown that in a pair $(\P,\si)$ with $\si\ne \text
{id}$ the family $\P$ must be intersecting. This establishes that
only pairs $(\P,\text {id})$ where $\P$ is a nonintersecting
family of two-rowed arrays contribute to the sum on the right-hand
side of (6.5). But these
pairs exactly correspond to the families of nonintersecting paths under
consideration, hence Theorem~7 would be proved.


Let $(\P,\si)$ be a pair under consideration for the sum on the
right-hand side of (6.5). 
Besides, we assume that $\P$ contains two two-rowed arrays $P_i$
and $P_{i+1}$ with
consecutive indices that have an intersection point. In the sequel
two-rowed arrays with consecutive indices will be called {\it
neighbouring\/} two-rowed arrays. 
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 $\Sch$. Let $i$ be minimal such that $\Sch$ is an intersection point of
$P_i$ and $P_{i+1}$. Let $P_i=(a\mid b)=(\dots p_{\ell_i}\mid \dots
q_{\ell_i})$ and $P_{i+1}=(c\mid d)=(\dots r_{\ell_{i+1}}\mid \dots
s_{\ell_{i+1}})$. Recall that $P_i$ is of type $\si(i)-i$ and $P_{i+1}$
is of type $\si(i+1)-i-1$ and that the bounds of the entries in
$P_i$ and $P_{i+1}$ are determined by (6.6). By (6.4), $\Sch$ being an
intersection point of $P_i$ and $P_{i+1}$ means that there exist $I$ and
$J$ such that $P_i$ looks like
$$
\matrix\format \r&\quad \c&\quad \c&\quad \c&\quad \c&\quad \c&\quad
\l\\
 a_1^{(\si(i))}+i-\si(i) \le&\dots&p_{I-1}&p_I&\dots&p_{\ell_i}&\le e_1^{(i)}-1\\
 a_2^{(\si(i))}-i+\si(i)+1 \le&\dots&q_{I-1}&q_I&\dots&q_{\ell_i}&\le e_2^{(i)}
\endmatrix,
\tag6.7$$
$P_{i+1}$ looks like
$$
\matrix\format \r&\quad \c&\quad \c&\quad \c&\quad \c&\quad \c&\quad
\c&\quad \l\\
 a_1^{(\si(i+1))}+i+1-\si(i+1) \le&\hdotsfor2 
&r_{J}&r_{J+1}&\dots&r_{\ell_{i+1}}&\le e_1^{(i+1)}-1\\
 a_2^{(\si(i+1))}-i+\si(i+1) \le&\dots&s_{J-1}&s_J&\hdotsfor2
&s_{\ell_{i+1}}&\le e_2^{(i+1)}
\endmatrix,
\tag6.8$$
$\Sch=(p_I,s_J)$, 
$$\gather  r_J\le p_I\tag6.9a\\
q_{I-1}\le s_J\tag6.9b
\endgather$$
and
$$
1\le I\le \ell_i+1,\quad  0\le J\le \ell_{i+1}.
\tag6.9c$$
Because of the construction of $\Sch$ the indices $I$ {\it and\/} $J$ are
maximal with respect to (6.9a,b,c).

We map $(\P,\si)$ to the pair $(\bar{\P},\si\circ(i,i+1))$
($(i,i+1)$
denotes the transposition interchanging $i$ and $i+1$), where $\bar{
\P}=(P_1,\dots,P_{i-1},\bar P_i,\bar P_{i+1},P_{i+2},\dots,P_n)$ with
$\bar P_i$ being given by
$$
\matrix\format  \c&\quad \c&\quad \c&\quad \c&\quad \c\\
\dots&r_J-1&p_I&\dots&p_{\ell_i}\\
\dots&s_{J-1}+1&q_I&\dots&q_{\ell_i}\endmatrix,
\tag6.10a$$
$\bar P_{i+1}$ being given by
$$
\matrix\format  \c&\quad \c&\quad \c&\quad \c&\quad \c&\quad \c\\
\hdotsfor2&p_{I-1}+1&r_{J+1}&\dots&r_{\ell_{i+1}}\\
\dots&q_{I-1}-1&s_J&\hdotsfor2
&s_{\ell_{i+1}}\endmatrix.
\tag6.10b$$
First of all, this operation is well-defined, i.e., all the rows in
(6.10a) and (6.10b) 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 inequality, because of
(6.9a) and
(6.9b). As for the second inequality, let us suppose $s_{J-1}+1\ge q_I$.
Then, by (6.9a), we have $r_J\le p_{I}<p_{I+1}$ and $q_I\le
s_{J-1}+1\le 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 $\Sch=(p_I,s_J)$, contradicting
the ``maximality" of $\Sch$. Similarly, if we assume $p_{I-1}+1\ge
r_{J+1}$, we have $r_{J+1}\le p_{I-1}+1\le p_I$ and, by (6.9b),
$q_{I-1}\le 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 $\Sch=(p_I,s_J)$, again contradicting
the ``maximality" of $\Sch$.

We claim that $(\bar{\P},\si(i,i+1))$ is again a pair under
consideration for the generating function (6.5). 
That is, we claim
that $\bar P_i$ is of type $(\si\circ(i,i+1))(i)-i=\si(i+1)-i$, that $\bar
P_{i+1}$ is of type $(\si\circ(i,i+1))(i+1)-i-1=\si(i)-i-1$, and that the
bounds for the entries of $\bar P_i$ are given by
$$
\matrix\format  \r&\quad \c&\quad \c&\quad \c&\quad \c&\quad \c&\quad
\l\\
a_1^{(\si(i+1))}+i-\si(i+1)\le&\dots&r_J&p_I&\dots&p_{\ell_i}&\le e_1^{(i)}-1\\
a_2^{(\si(i+1))}-i+\si(i+1)+1\le&\dots&s_{J-1}&q_I&\dots&q_{\ell_i}&\le
e_2^{(i)}\endmatrix,
\tag6.11$$
 and that those for $\bar P_{i+1}$ are given by
$$
\matrix\format  \r&\quad \c&\quad \c&\quad \c&\quad \c&\quad \c&\quad
\c&\quad \l\\
a_1^{(\si(i))}+i+1-\si(i)\le&\hdotsfor2 
&p_{I-1}&r_{J+1}&\dots&r_{\ell_{i+1}}&\le e_1^{(i+1)}-1\\
a_2^{(\si(i))}-i+\si(i)\le&\dots&q_{I-1}&s_J&\hdotsfor2
&s_{\ell_{i+1}}&\le e_2^{(i+1)}\endmatrix.
\tag6.12$$
The claims concerning the types of $\bar P_i$ and $\bar 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 consult
\cite{\KratAW, \KratBE}. 
Obviously the map (6.10) 
reverses the sign of the associated permutation.
Besides, it can be checked that it is an involution. 
The proof that, given a pair $(\P,\si)$, 
$\P=(P_1,P_2,\dots,P_n)$, 
$\si\ne \text {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 \cite{\KratAW, \KratBE} for the details.\quad \quad
\qed
\enddemo

\remark{Remark} The map from (6.7)/(6.8) to (6.10) 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 e.g\. \cite{\GeViAB, \StemAE, \KratAP, sec.~2.2}).
\endremark

Another problem that is posed by Example~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.
\proclaim{Theorem 8}
Let $A_i=(a_1^{(i)},a_2^{(i)})$ and
$E_i=(e_1^{(i)},e_2^{(i)})$, $i=1,2,\dots,n$, be lattice points satisfying
$$a_1^{(1)}\le a_1^{(2)}\le\dotsb\le a_1^{(n)},\quad
a_2^{(1)}>a_2^{(2)}>\dotsb>a_2^{(n)},$$
$$
e_1^{(1)}< e_1^{(2)}<\dotsb< e_1^{(n)},\quad
e_2^{(1)}\ge e_2^{(2)}\ge \dotsb\ge e_2^{(n)},$$
and
$a_1^{(i)}\ge a_2^{(i)},\quad e_1^{(i)}\ge e_2^{(i)},\quad
i=1,2,\dots,n.$
The generating function $\sum _{\P} ^{}z^{\NE(P)}$, where the sum is
over all families $\P=(P_1,P_2,\dots,P_n)$ of nonintersecting
lattice paths $P_i:A_i\to E_i$, which stay below the line $x=y$
(being allowed to touch it),
equals
$$\multline
\det_{1\le i,j\le n}
\bigg(\bigg(\sum _{k\ge0} ^{}\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}\bigg)z^k\bigg).
\endmultline\tag6.13$$
\endproclaim

\demo{Sketch of proof} 
Again we work with families of two-rowed arrays. This time we
consider triples $(\P,\si,\et)$, where $\si$ is a permutation in
$\frak S_n$, $\et\in \{-1,1\}^r$, and $\P=(P_1,P_2,\dots,P_n)$ is a
family of two-rowed arrays, with $P_i$ being of type $\et_i\si(i)-i$ and
the bounds of $P_i$ being given by 
$$
\matrix\format  \r&\quad \c&\quad \l\\
a_1^{(\si(i))}+i-\si(i)\le &\dots&\le e_1^{(i)}-1\\
a_2^{(\si(i))}-i+\si(i)+1\le &\dots&\le e_2^{(i)}\\
\endmatrix, \text {\quad for $\et=1$,}
\tag6.14$$
respectively
$$
\matrix\format  \r&\quad \c&\quad \l\\
a_2^{(\si(i))}+i+\si(i)-1\le &\dots&\le e_1^{(i)}-1\\
a_1^{(\si(i))}-i-\si(i)+2\le &\dots&\le e_2^{(i)}\\
\endmatrix, \text {\quad for $\et=-1$.}
\tag6.15$$
Define $\sgn\et:=\prod _{i=1} ^{n}\et_i$.
It is easy to see that (6.13) is the generating function 
$$
\sum _{(\P,\si,\et)} ^{}\sgn\et\,\sgn\si\,z^{\NE(\P)}
\tag6.16$$
where the sum is over all triples
which were described above.

Now, the basic idea is as follows. 
We show that in the sum
(6.16) all contributions cancel which correspond 
to triples $(\P,\si,\et)$, 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 which
is smaller than its neighbour in the bottom row. Again, 
this is done by
constructing a sign-reversing involution (with respect to
$\sgn\et\,\sgn\si$) 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
(6.7)/(6.8) to (6.10) 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
(4.7), applied to $P_1$.
It can be shown that in a triple $(\P,\si,\et)$ with $\si\ne \text
{id}$ or $\et\ne(1,1,\dots,1)$ 
the family $\P$ must be intersecting or $P_1$ ``crosses $y=x$". 
This establishes that
only triples $(\P,\text {id},(1,1,\dots,1))$ where $\P$ is a 
nonintersecting
family of two-rowed arrays which do not cross $y=x$ 
contribute to the sum (6.16). But these
triples exactly correspond to the families of nonintersecting paths under
consideration, hence Theorem~8 would be proved. We refer the reader
to \cite{\KratAW, \KratBE} for the details.
\quad \quad \qed
\enddemo



As mentioned before, Theorem~8 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 
\cite{\ConcAC} can also be solved by using the method of two-rowed
arrays, see \cite{\KratAW}. For arbitrary one-sided ladders there is
a solution when the starting points, respectively end points, are
located ``successively" (such as in Figure~4) by this author and
Prohaska \cite{\KrPrAA} proving a remarkable formula conjectured by
Conca and Herzog \cite{\CoHeAA}. For ``generally" located starting
and end points there is a solution in terms of a determinant with
entries counting certain two-rowed arrays by this author
\cite{\KratAW}.
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 
\cite{\KrMoAA} is useful in this context.
Finally we want to point the reader to a refined turn counting for
pairs of paths \cite{\KrSuAA} which relates the subject also to
polyomino counting.








\Refs

\ref\no \AbhyAD\by S. S. Abhyankar \yr 1987 
\paper Determinantal loci and enumerative combinatorics of Young tableaux
\inbook Algebraic geometry and commutative algebra, in honor of M.~Nagata 
\pages 1--26\endref

\ref\no \AbhyAB\by S. S. Abhyankar \yr 1988 
\book Enumerative combinatorics of Young tableaux
\publ Marcel Dekker
\publaddr New York, Basel\endref

\ref\no \AbKuAC\by S. S. Abhyankar and D. M. Kulkarni \yr 1989 
\paper On Hilbertian ideals
\jour Linear Alg\. Appl\.\vol 116
\pages 53--76\endref

\ref\no \BurgAC\by W. H. Burge \yr 1993 \paper Restricted partition 
pairs\jour J. Combin\. Theory Ser.~A\vol 63\pages 210--222\endref

\ref\no \ComtAA\by L.    Comtet \yr 1974 
\book Advanced Combinatorics
\publ D.~Reidel
\publaddr Dordrecht, Holland\endref

\ref\no \ConcAC\by A.    Conca \yr 1994 
\paper Symmetric ladders
\jour Nagoya Math\. J.\vol 136
\pages 35--56\endref

\ref\no \CoHeAA\by A.    Conca and J. Herzog \yr 1994 
\paper On the Hilbert function of determinantal rings and their canonical module 
\jour Proc\. Amer\. Math\. Soc\. \vol 122 
\pages 677--681\endref

\ref\no \DeGrAA\by M. H. DeGroot \yr 1959 
\paper Unbiased sequential estimation for binomial populations
\jour Ann\. Math\. Statist\.\vol 30
\pages 80--101\endref

\ref\no \EsGuAA\by J. W. Essam and A. J. Guttmann \yr 1995 
\paper Vicious walkers and directed polymer networks in general dimensions 
\jour Physical Review E \vol 52 
\pages 5849--5862\endref

\ref\no \FishAA\by M. E. Fisher \yr 1984 
\paper Walks, walls, wetting, and melting
\jour J. Statist\. Phys\.\vol 34
\pages 667--729\endref

\ref\no \GeKrAA\by I. M. Gessel and C. Krattenthaler 
\paper Cylindric partitions\jour Trans\. Amer\. Math\. Soc\. 
\toappear \endref

\ref\no \GeViAA\by I. M. Gessel and X. Viennot \yr 1985 
\paper Binomial determinants, paths, and hook length formulae
\jour Adv\. in Math\. \vol 58
\pages 300---321\endref

\ref\no \GeViAB\by I. M. Gessel and X. Viennot \yr 1989 
\paper Determinants, paths, and plane partitions 
\paperinfo preprint\endref

\ref\no \GhorAD\by S. R. Ghorpade \paper Young bitableaux, 
lattice paths and Hilbert functions\jour J. Statist\. Plann\. Inference
\toappear\vol 
\pages \endref

\ref\no \GhKrAA\by S. R. Ghorpade and C. Krattenthaler\paper On
pfaffian ideals\paperinfo in preparation\endref 

\ref\no \HeTrAA\by J.    Herzog and N. V. Trung \yr 1992 \paper 
Gr\"obner bases and multiplicity of determinantal and Pfaffian 
ideals\jour Adv\. in Math\.\vol 96\pages 1--37\endref

\ref\no \KarlAB\by S.    Karlin \yr 1988 
\paper Coincident probabilities and applications in combinatorics
\jour J. Appl\. Probab\. \vol 25A
\pages 185--200\endref

\ref\no \KaMGAC\by S.    Karlin and J. L. McGregor \yr 1959 
\paper Coincidence probabilities
\jour Pacific J. Math\.\vol 9
\pages 1141--1164\endref

\ref\no \KaMGAB\by S.    Karlin and J. L. McGregor \yr 1959 
\paper Coincidence properties of birth-and-death processes
\jour Pacific J. Math\.\vol 9
\pages 1109--1140\endref

\ref\no \KratAF\by C.    Krattenthaler \yr 1989 
\paper Counting lattice paths with a linear boundary, Part 2: $q$-ballot and $q$-Catalan numbers
\jour Sitz\.ber\. d\. \"OAW, Math-na\-tur\-wiss\. Klasse\vol 198
\pages 171--199\endref

\ref\no \KratAQ\by C.    Krattenthaler \yr 1993 
\paper Non-crossing two-rowed arrays and summations for Schur functions\eds A.~Barlotti, M.~Delest, R.~Pinzani
\inbook Proc\. of the 5th Conference on Formal Power Series and Algebraic Combinatorics, Florence, 1993
\publ D.S.I., Universit\`a di Firenze
\pages 301--314\endref

\ref\no \KratAP\by C.    Krattenthaler \yr 1995 
\book The major counting of nonintersecting lattice paths and generating functions for tableaux
\publ Mem\. Amer\. Math\. Soc\. 115, no.~552
\publaddr Providence, R.~I. \endref

\ref\no \KratBE\by C.    Krattenthaler \yr 1995 
\paper Counting nonintersecting lattice paths with respect to weighted turns
\jour Seminaire Lotharingien Combin\.\vol 34
\pages paper B34i, 17~pp\endref

\ref\no \KratAW\by C.    Krattenthaler 
\paper Non-crossing two-rowed arrays
\paperinfo in preparation
\jour \vol 
\pages \endref

\ref\no \KratAV\by C.    Krattenthaler 
\paper Nonintersecting lattice paths and oscillating tableaux
\jour J. Statist\. Plann\. Inference\toappear\endref

\ref\no \KrPrAA\by C.    Krattenthaler and M. Prohaska 
\paper A remarkable formula for counting nonintersecting lattice paths in a ladder with respect to turns
\jour preprint\vol 
\pages \endref

\ref\no \KrMoAC\by C.    Krattenthaler and S. G. Mohanty \yr 1993 
\paper On lattice path counting by major and descents
\jour Europ\. J. Combin\.\vol 14
\pages 43--51\endref

\ref\no \KrMoAA\by C.    Krattenthaler and S. G. Mohanty \yr 1995 
\paper Counting tableaux with row and column bounds
\jour Discrete Math\.\vol 139
\pages 273--286\endref

\ref\no \KrSuAA\by C.    Krattenthaler and R. A. Sulanke \paper 
Counting pairs of nonintersecting lattice paths with respect to 
weighted turns\jour Discrete Math\.\toappear\endref

\ref\no \KulkAD\by D. M. Kulkarni \yr 1993 
\paper Hilbert polynomial of a certain ladder-determinantal ideal
\jour J. Algebraic Combin\.\vol 2
\pages 57--72\endref

\ref\no \KulkAC\by D. M. Kulkarni 
\paper Counting of paths and coefficients of Hilbert polynomial of a determinantal ideal
\jour \vol 
\pages \endref

\ref\no \LindAA\by B.    Lindstr\"om \yr 1973 
\paper On the vector representations of induced matroids
\jour Bull\. London Math\. Soc\.\vol 5
\pages 85--90\endref

\ref\no \ModaAA\by M. R. Modak \yr 1992 
\paper Combinatorial meaning of the coefficients of a Hilbert polynomial
\jour Proc\. Indian Acad\. Sci\. (Math\. Sci\.)\vol 102
\pages 93--123\endref

\ref\no \MohaAG\by S. G. Mohanty \yr 1966 
\paper On a generalised two-coin tossing problem
\jour Biometrische Z.\vol 8
\pages 266--272\endref

\ref\no \MohaAC\by S. G. Mohanty \yr 1971 
\paper A short proof of Steck's result on two-sample Smirnov statistics
\jour Ann\. Math\. Statist\.\vol 42
\pages 413--414\endref

\ref\no \MohaAE\by S. G. Mohanty \yr 1979 
\book Lattice path counting and applications
\publ Academic Press
\publaddr New York\endref

\ref\no \NaraAA\by T. V. Narayana \yr 1959 \paper A partial order and 
its applications to probability theory\jour Sankhya\vol 
21\pages 91--98\endref

\ref\no \NaraAB\by T. V. Narayana \yr 1979 \book Lattice path 
combinatorics with statistical applications\publ Math\. Expositions, 
no.~23, Univ\. of Toronto Press\publaddr Toronto\endref

\ref\no \NiedAR\by H.    Niederhausen 
\paper Symmetric Sheffer sequences and their applications to lattice
path counting
\jour J. Statist\. Plann\. Inference\vol 
\pages \endref

\ref\no \StecAA\by G. P. Steck \yr 1974 
\paper A new formula for $P(R_i\le b_i,\ 1\le i\le m\mid m,n,F=G^k)$
\jour Ann\. Prob\.\vol 2
\pages 155--160\endref

\ref\no \StemAE\by J. R. Stembridge \yr 1990 
\paper Nonintersecting paths, pfaffians and plane partitions
\jour Adv\. in Math\.\vol 83
\pages 96---131\endref

\ref\no \SulaAC\by R. A. Sulanke \yr 1990 
\paper A determinant for $q$-counting lattice paths
\jour Discrete Math\.\vol 81
\pages 91--96\endref

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

\endRefs
\enddocument
