%\documentclass[12pt,reqno]{amsbook}
%\input pathlate.sty
%\input priv
%\makeindex
%\makeglossary



%\begin{document}

\chapter{Lattice paths and their turns}\label{ch4}

In this chapter we consider {\em turns\/}\index{turn of a lattice 
path}\index{path, turn} of lattice paths. Literally, a {\em turn\/} of a 
lattice path is any 
vertex of a path where the direction of the path changes. The
enumeration of lattice paths with a given number of turns is motivated
by correlated random walks, distribution of runs,
coefficients of Hilbert polynomials of determinantal and Pfaffian
rings, and summations for Schur functions.

%It evolves that it is even best to concentrate only on one type of
%turns. 
Our approach for the enumeration of simple plane lattice paths
with respect to their number of turns
is by encoding lattice paths in terms of two-rowed
arrays. It will be exhibited that most(??) of the techniques
introduced in Chapter~\ref{ch1} have their analogues for two-rowed
arrays. From this point of view 
we believe that two-rowed arrays are the ``right"
tool for attacking enumeration problems involving the number of turns.


\section{Simple lattice paths in the plane and two-rowed arrays}
\label{s4.1}

For simple lattice path in the plane there are two types of turns. We
call a vertex T of a path a {\em North-East turn\/}\index{North-East turn}
\index{turn, North-East} ({\em NE-turn\/}\index{NE-Turn} for short) if
$T$ is reached by a step towards north and left by a step 
towards east. We
call a vertex T of a path a {\em east-north turn\/}\index{east-north turn}
\index{turn, east-north} ({\em EN-turn\/}\index{EN-Turn} for short) if
$T$ is reached by a step towards east and left by a step 
towards north. Thus, the NE-turns of the path $P_0$ in
Figure~\ref{F4.1} are $(1,1)$, $(2,3)$, and $(5,4)$, the EN-turns of
$P_0$ are $(2,1)$, $(5,3)$, and $(6,4)$.
\begin{Figure}\label{F4.1}
$$\Koordinatenachsen(8,8)(0,0)
\Gitter(8,8)(0,0)
\Pfad(1,-1),221221112122\endPfad
\DickPunkt(1,-1)
\DickPunkt(6,6)
\Label\ro{P_0}(3,3)
\hskip4cm
$$
\end{Figure}
We denote by \glossary{$NE(P)$}$NE(P)$ the number of NE-turns of $P$ and
by $EN(P)$\glossary{$EN(P)$} the number of EN-turns of $P$.

Now we describe the encoding of paths in terms of two-rowed arrays.
Actually, we use two encodings, one corresponding to NE-turns, one
corresponding to EN-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 {\em NE-turn
representation\/}\index{NE-turn representation} 
of $P$ is defined by the two-rowed array
\begin{equation}\label{e4.1}\begin{array} {cccc}
p_1&p_2&\dots&p_\ell\\
q_1&q_2&\dots&q_\ell,
\end{array}
\end{equation}
which consists of two strictly increasing sequences. Clearly, if 
$P$ runs from $(a,b)$ to $(c,d)$ then $a\le p_1<p_2<\dots<
p_\ell\le c-1$ and $b+1\le q_1<q_2<\dots<q_\ell\le d$ are satisfied. 
If we wish to make this fact transparent, we write
\begin{equation} \label{e4.2} 
\begin{array} {rccccl}
a\le&\quad p_1&p_2&\dots&p_\ell&\quad \le c-1\\
b+1\le&\quad q_1&q_2&\dots&q_\ell&\quad \le d.
\end{array}
\end{equation}
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 the path in our running example
we obtain the NE-turn representation
$$\begin{matrix} 1& 2& 5\\1& 3& 4\end{matrix}\ ,$$
or with bounds included,
$$\begin{array}{rcccl}\\
1\le&\quad 1&\ 2&\ 5&\quad \le5\\
0\le&\quad 1&\ 3&\ 4&\quad \le6\end{array}\ .$$

Similarly, if $(p_1,q_1)$, $(p_2,q_2)$, \dots,
$(p_\ell,q_\ell)$ denote the EN-turns 
of a path $P$, then \eqref{e4.1} is called the {\em EN-turn
representation\/}\index{EN-turn representation} 
of $P$.
If
$P$ runs from $(a,b)$ to $(c,d)$ then $a+1\le p_1<p_2<\dots<
p_\ell\le c$ and $b\le q_1<q_2<\dots<q_\ell\le d-1$ are satisfied. Again,
as earlier, we write
\begin{equation} \label{e4.3} 
\begin{array} {rccccl}
a+1\le&\quad p_1&p_2&\dots&p_\ell&\quad \le c\\
b\le&\quad q_1&q_2&\dots&q_\ell&\quad \le d-1.
\end{array}
\end{equation}
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 EN-turn.
For the path in our running example
we obtain the EN-turn representation
$$\begin{matrix} 2& 5& 6\\1& 3& 4\end{matrix}\ ,$$
or with bounds included,
$$\begin{array}{rcccl}\\
2\le&\quad 2&\ 5&\ 6&\quad \le6\\
-1\le&\quad 1&\ 3&\ 4&\quad \le5\end{array}\ .$$


%The notations \eqref{e4.2} and \eqref{e4.3} will be used with
%a three-fold meaning. First, we write down special arrays in that way
%if in addition we want to point out the row bounds. Secondly, we shall
%speak of two-rowed arrays {\em of the type\/} \eqref{e4.2} or
%\eqref{e4.3} 
%by which we will mean 
%arrays of the form \eqref{e4.1} which obey the row bounds in
%\eqref{e4.2} or \eqref{e4.3}. Thirdly, 
%the notations \eqref{e4.2} and \eqref{e4.3} 
%will also be used for the {\em set\/} of all arrays of
%the type \eqref{e4.2} or \eqref{e4.3}. 
%It should always be clear from the context which
%meaning is intended.

Also two-rowed arrays with its
rows being of unequal length will be considered. These arrays will
also have the property that the rows are strictly increasing. So by
convention, whenever we speak of two-rowed arrays we
mean two-rowed arrays with strictly increasing rows. For these
arrays we will use a notation of the kind \eqref{e4.2} or
\eqref{e4.3} as well. 
We shall frequently use the short notation $(\mathbf a\mid \mathbf b)$ 
for two-rowed arrays, where $\mathbf a$
denotes the sequence $(a_i)$ of elements of the first row, 
and $\mathbf b$ denotes the
sequence $(b_i)$ of elements of the second row.

From \eqref{e4.2} we see at once that the number of all paths from
$(a,b)$ to $(c,d)$ with exactly $\ell$ NE-turns equals the number of
$\ell$-element subsets of $\{a,a+1,\dots,c-1\}$ times the number of
$\ell$-element subsets of $\{b+1,b+2,\dots,d\}$. A similar argument
holds for EN-turns. Thus we have proved
\begin{multline}\label{e4.4}
\v{\L{(a,b)\to (c,d)\mid NE(.)=\ell}}=
\v{\L{(a,b)\to (c,d)\mid EN(.)=\ell}}\\
=\binom {c-a}{\ell}
\binom{d-b}\ell.
\end{multline}

\section{From NE-turns to runs} \label{s4.2}
A lattice path statistic that is frequently used is the number of
{\em runs\/} of a lattice path. A {\em run\/}\index{run of a
path}\index{path, run} in a path $P$ is a maximal subpath of $P$
consisting of steps of equal type. We write $\run(P)$ for the number
of runs of $P$. The runs of the path $P_0$ in Figure~\ref{F4.1} are
the subpaths from $(1,-1)$ to $(1,1)$, from $(1,1)$ to $(2,1)$, from
$(2,1)$ to $(2,3)$, from $(2,3)$ to $(5,3)$, from $(5,3)$ to $(5,4)$,
from $(5,4)$ to $(6,4)$, and from $(6,4)$ to $(6,6)$. Thus we have
$\run(P_0)=7$. Obviously, the number of runs of a path is exactly one
more than the total number of turns (both, NE-turns and EN-turns).
Besides, there is also a close relation between NE-turns and
runs, which allows us to translate any enumeration result for NE-turns
into one for runs. The objective of this
section is to explain this relation.
??What is the condition on $R$??no condition??see turnsurv.tex!!

??Mention also translation to 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 
know the generating function $GF(L(A\to E\mid R);x^{NE(.)})$. For
brevity, 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. The notations $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)$ are defined analogously. 
The relation between
enumeration by runs and enumeration by NE-turns is given by
\begin{multline} \label{e4.5}
GF(L(A\to E\mid R);x^{\run(.)})=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).
\end{multline}
??Figure


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, 
the following is true:
\begin{multline} \notag
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).
\end{multline}
Besides, if $E_1=(1,0)$ and $E_2=(0,1)$ denote the standard unit
vectors, we have
\begin{align} \notag
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)\\
\notag
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)\\
\notag
F_{hv}(A\to E\mid R;x)&=F(A+E_1\to E-E_2\mid R;x).
\end{align}
Solving for $F_{hh}$, $F_{hv}$, $F_{vh}$, $F_{vv}$ we get
{\refstepcounter{equation}\label{e4.6}}
\alphaeqn
\begin{align} \label{e4.6a}
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)\\
\label{e4.6b}
F_{hv}(A\to E\mid R;x)&=F(A+E_1\to E-E_2\mid R;x)\\
\label{e4.6c}
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)\\
\notag
&\hskip1cm -F(A+E_1\to E\mid R;x)-F(A\to E-E_2\mid R;x)\\
\label{e4.6d}
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).
\end{align}
\reseteqn
We will find that \eqref{e4.6a}--\eqref{e4.6d} give us refined
information about NE-turn enumeration which will be useful for the
correlated random walk.??

\section{Simple paths in the plane restricted by lines parallel to
$x=y$} \label{s4.3}

??Derive many things as corollaries of plane partitions and cylindric
partitions??


As we know from Chapter~\ref{ch1}, Section~\ref{s1.1}, counting paths restricted by
$x=y$, or even by two lines $x=y+t$ and $x=y+s$, is effectively solved
by the reflection principle. Of course, reflection by itself is useless
for counting paths by turns, since the reflection of portions of paths
does not take care of turns. It might introduce new turns or make
turns disappear. However, there are ``analogues" of reflection for
two-rowed arrays, which are due to \index{Krattenthaler, Christian}Krattenthaler and 
\index{Mohanty, Sri Gopal}Mohanty 
\cite{KrMoAC}. These are the main tools of the proofs in this section.
In addition, they allow us to derive $q$-analogues, see Chapter~\ref{??},
Section~\ref{??}.

\begin{Theorem} \label{T4.1}
Let $a\ge b$ and $c\ge d$. The number of all paths from $(a,b)$ to
$(c,d)$ staying below $x=y$ with exactly $\ell$ NE-turns is given by
\begin{multline} 
\v{\L{(a,b)\to (c,d)\mid x\ge y,\,NE(.)=\ell}}\\
=\binom {c-a}{\ell}\binom{d-b}\ell - \binom {c-b-1}{\ell-1}
\binom{d-a+1}{\ell+1} ,\label{e4.7} 
\end{multline}
and with exactly $\ell$ EN-turns is given by
\begin{multline} 
\v{\L{(a,b)\to (c,d)\mid x\ge y,\,EN(.)=\ell}}\\
=\binom {c-a}{\ell}\binom{d-b}\ell - \binom {c-b+1}{\ell}
\binom{d-a-1}{\ell} .\label{e4.8} 
\end{multline}
\end{Theorem}

\begin{proof}We start with proving \eqref{e4.7}. 
By the NE-turn representation \eqref{e4.2}, the paths from $(a,b)$
to $(c,d)$ staying below $x=y$ with exactly $\ell$ NE-turns
 can be
represented by (??mention that these are two-rowed plane partitions??)
{\refstepcounter{equation}\label{e4.9}}
\alphaeqn
\begin{equation} \label{e4.9a} 
\begin{array} {rccccl}
a\le&\quad p_1&p_2&\dots&p_\ell&\quad \le c-1\\
b+1\le&\quad q_1&q_2&\dots&q_\ell&\quad \le d,
\end{array}
\end{equation}
where
\begin{equation} \label{e4.9b} 
p_i\ge q_i, \quad \quad i=1,2,\dots,\ell.
\end{equation}
\reseteqn
Following the argument in the proof of Theorem~\ref{T1.1}, the number
of these two-rowed arrays is the number of {\em all\/} two-rowed arrays
of the type \eqref{e4.9a} minus those two-rowed arrays of the type
\eqref{e4.9a} which {\em violate\/} \eqref{e4.9b}, i.e\@. where $p_i<q_i$ for
some $i$ between $1$ and $\ell$. We know the first number from
\eqref{e4.4}. 

Concerning the second number, we claim that two-rowed arrays of the
type \eqref{e4.9a} which violate \eqref{e4.9b} are in one-to-one
correspondence with two-rowed arrays of the type
\begin{equation} \label{e4.10} 
\begin{array} {rcccccl}
b+1\le&\quad &&\bar p_2&\dots&\bar p_\ell&\quad \le c-1\\
a\le&\quad \bar q_0&\bar q_1&\bar q_2&\dots&\bar q_\ell&\quad \le d.
\end{array}
\end{equation}
The number of all these two-rowed arrays is $\binom {c-b-1}{\ell-1}
\binom {d-a+1}{\ell+1}$, as desired. So it remains only to construct
the one-to-one correspondence.

Take a two-rowed array $(\mathbf p\mid \mathbf q)$ of the type \eqref{e4.9a} such that
$p_i<q_i$ for some $i$. Let $I$ be the largest integer such that
$p_I<q_I$. Then map $(\mathbf p\mid \mathbf q)$ to
\begin{equation} \label{e4.11} 
\begin{array} {ccccccccc}
&&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
\end{array}.
\end{equation}
Note that both rows are strictly increasing because of
$q_{I-1}<q_I<q_{I+1}\le p_{I+1}$ and $p_I<q_I$. By some case by case
analysis it can be seen that \eqref{e4.11} is of type \eqref{e4.10}.
For example, if $I=\ell$ then we must check $q_{I-1}\le c-1$, among
others. Clearly, this follows from the inequalities $q_{I-1}<q_I\le
d\le c$.

The inverse of this map is defined in the same way. Let $(\bar {\mathbf
p}\mid
\bar{\mathbf q})$
be a two-rowed array of the type \eqref{e4.10}. Let $\bar I$ be the
largest integer such that $\bar p_{\bar I}<\bar q_{\bar I}$. If there
are none, take $\bar I=2$. Then map $(\bar {\mathbf p}\mid \bar {\mathbf q})$ to
\begin{equation} \label{e4.12} 
\begin{array} {ccccccc}
\bar q_0&\multicolumn{2}{c}{\dotfill}&\bar q_{\bar I-1}&\bar p_{\bar
I+1} &\dots&\bar p_\ell\\
\bar p_2&\dots&\bar p_{\bar I}&\bar q_{\bar I}&\dots&\bar q_\ell
\end{array}.
\end{equation}
It is not difficult to check that the mappings \eqref{e4.11} and
\eqref{e4.12} are inverses of each other. This completes the proof of
\eqref{e4.7}.

The second identity, \eqref{e4.8}, is established similarly. This time
we represent paths from $(a,b)$ to $(c,d)$ staying below $x=y$ with
exactly $\ell$ EN-turns by the EN-turn representation \eqref{e4.3}, that is
two-rowed arrays of the type
{\refstepcounter{equation}\label{e4.13}}
\alphaeqn
\begin{equation} \label{e4.13a} 
\begin{array} {rccccl}
a+1\le&\quad p_1&p_2&\dots&p_\ell&\quad \le c\\
b\le&\quad q_1&q_2&\dots&q_\ell&\quad \le d-1,
\end{array}
\end{equation}
where
\begin{equation} \label{e4.13b} 
p_i\ge q_{i+1}, \quad \quad i=1,2,\dots,\ell, 
\end{equation}
\reseteqn
with the convention $q_{\ell+1}=d$. 
All we have to do is to enumerate those two-rowed arrays of the type
\eqref{e4.13a} which violate \eqref{e4.13b}.
We claim that these
are in one-to-one
correspondence with two-rowed arrays of the type
\begin{equation} \label{e4.14} 
\begin{array} {rcccl}
b\le&\quad \bar p_1&\dots&\bar p_\ell&\quad \le c\\
a+1\le&\quad \bar q_1&\dots&\bar q_\ell&\quad \le d-1.
\end{array}
\end{equation}
In order to see this,
take a two-rowed array $(\mathbf p\mid \mathbf q)$ of the type \eqref{e4.13a} such that
$p_i<q_{i+1}$ for some $i$.
Let $I$ be the largest integer such that
$p_I<q_{I+1}$, $1\le I\le \ell$. Then map this $(\mathbf p\mid \mathbf q)$ to
\begin{equation} \label{e4.15} 
\begin{array} {ccccccc}
q_1&\dots&q_{I}&p_{I+1}&\dots&p_\ell\\
p_1&\dots&p_I&q_{I+1}&\dots&q_\ell
\end{array}.
\end{equation}
Again, note that both rows are strictly increasing because of
$q_{I}<q_{I+1}<q_{i+2}\le p_{I+1}$ and $p_I<q_{I+1}$. Also,
it can be seen that \eqref{e4.15} is of type \eqref{e4.14}.

For the inverse of this mapping, suppose that  $(\bar {\mathbf p}\mid
\bar {\mathbf q})$
is a two-rowed array of the type \eqref{e4.14}. Choose $\bar I$ 
to be largest integer such that $\bar p_{\bar I}<\bar q_{\bar I+1}$. If there
are none, take $\bar I=\ell$. Then map $(\bar {\mathbf p}\mid \bar {\mathbf q})$ to
\begin{equation} \label{e4.16} 
\begin{array} {cccccc}
\bar q_1&\dots&\bar q_{\bar I}&\bar p_{\bar
I+1} &\dots&\bar p_\ell\\
\bar p_1&\dots&\bar p_{\bar I}&\bar q_{\bar I+1}&\dots&\bar q_\ell
\end{array}.
\end{equation}
Again it is not difficult to check that the mappings \eqref{e4.15} and
\eqref{e4.16} are inverses of each other. This completes the proof of
\eqref{e4.8}.
\end{proof}
??run formulation

If we combine both mappings, \eqref{e4.11}/\eqref{e4.12} and
\eqref{e4.15}/\eqref{e4.16}, (actually slight modifications of them),
then we are able to derive a refinement of
Theorem~\ref{T1.3} taking into account turns. 
We only give the result for NE-turns since, by a
rotation by $180^\circ$, it can easily transformed into a result for
EN-turns. 
\begin{Theorem} \label{T4.2}
Let $a+t\ge b\ge a+s$ and $c+t\ge d\ge c+s$. The number of all paths
from $(a,b)$ to $(c,d)$ staying below the line $y=x+t$ and above the
line $y=x+s$ with exactly $\ell$ NE-turns is given by
\begin{multline} \label{e4.17}
\v{\L{(a,b)\to (c,d)\mid x+t\ge y\ge x+s,\,NE(.)=\ell}}\\
=\sum _{k\in\Z} ^{}\bigg(\binom
{c-a-k(t-s)} {\ell+k}\binom {d-b+k(t-s)}{\ell-k}\hskip3cm\\
-\binom {c-b-k(t-s)
+s-1}{\ell+k} \binom {d-a+k(t-s)-s+1}{\ell-k}\bigg). 
\end{multline}
\end{Theorem}
??refer to cylindric partitions!!
\begin{proof}By the NE-turn representation, the paths under consideration
are in one-to-one correspondence with two-rowed arrays of the type
{\refstepcounter{equation}\label{e4.18}}
\alphaeqn
\begin{equation} \label{e4.18a} 
\begin{array}{rcccl}
a\le&p_1&\dots&p_\ell&\le c-1\\
b+1\le&q_1&\dots&q_\ell&\le d
\end{array}
\end{equation}
where
\begin{equation} \label{e4.18b} 
p_i+t\ge q_i\ge p_{i+1}+s.
\end{equation}
\reseteqn
Similar to the proof of Theorem~\ref{T1.3}, the proof of this theorem
is by a cancelling bijection. But not on paths, but certain two-rowed
arrays, which we introduce now. In fact, there are two types of
arrays. Let us call two-rowed arrays of the type
$$\begin{array}{rcccccl}
a+k(t-s)\le&p_{1-m}&\dots&p_{1+m}&\dots&p_\ell&\le c-1\\
b+1-k(t-s)\le&&&q_{1+m}&\dots&q_\ell&\le d
  \end{array}\quad \quad \text{for }m\ge0
$$
and 
$$\begin{array}{rcccccl}
a+k(t-s)\le&&&p_{1-m}&\dots&p_\ell&\le c-1\\
b+1-k(t-s)\le&q_{1+m}&\dots&q_{1-m}&\dots&q_\ell&\le d
  \end{array}\quad \quad \text{for }m<0
$$
{\em type I arrays\/}. Similarly, we call two-rowed arrays of the type
$$\begin{array}{rcccccl}
b+1-s+k(t-s)\le&p_{1-m}&\dots&p_{1+m}&\dots&p_\ell&\le c-1\\
a+s-k(t-s)\le&&&q_{1+m}&\dots&q_\ell&\le d
  \end{array}\quad \quad \text{for }m\ge0
$$
and 
$$\begin{array}{rcccccl}
b+1-s+k(t-s)\le&&&p_{1-m}&\dots&p_\ell&\le c-1\\
a+s-k(t-s)\le&q_{1+m}&\dots&q_{1-m}&\dots&q_\ell&\le d
  \end{array}\quad \quad \text{for }m<0
$$
{\em type II arrays\/}. The set of type I arrays is the ``analogue" of
the path set in \eqref{e1.7a}, and the set of type II arrays is the
``analogue" of the path set in \eqref{e1.7b}. We shall set up a
bijection between type I arrays not being of the type \eqref{e4.18}
(which means that \eqref{e4.18b} must be violated if both rows have
equal length) and type II arrays. Given such a bijection, we could deduce
\begin{equation} \label{e4.19} 
\v{\{\text{type I arrays}\}}-\v{\{\text {type II arrays}\}}
=\v{\{\text {arrays of type \eqref{e4.18}}\}}.
\end{equation}
The arrays of type \eqref{e4.18} exactly correspond to the paths we
are intending to enumerate. By definition of type I and type II arays,
the left-hand side in \eqref{e4.19} equals the right-hand side in
\eqref{e4.17}. Thus \eqref{e4.17} would be established.

The definition of the bijection and its inverse can be given in a
unified form. Let $(\mathbf p\mid \mathbf q)$ be either a type I array 
which is not of the type
\eqref{e4.18}, or a type II array, and be represented by
$$
\begin{matrix} p_{1-m}&\hdotsfor3&p_\ell\\
&\quad &q_{1+m}&\dots&q_\ell\end{matrix}.
$$
(This representation has to be understood symbolically. $m$ 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
\begin{equation} \label{e4.20} 
q_I>p_I+t\quad \text{or}\quad I=-m,
\end{equation}
or
\begin{equation} \label{e4.21} 
q_I<p_{I+1}+s\quad \text{or}\quad I=m.
\end{equation}
If \eqref{e4.20} is satisfied then map $(\mathbf p\mid \mathbf q)$ to
$$\begin{matrix}
&&(q_{1+m}-t)&\hdotsfor2&(q_{I-1}-t)&p_{I+1}&\dots&p_\ell\\
(p_{1-m}+t)&\hdotsfor3&(p_I+t)&q_I&\hdotsfor2&q_\ell\\
&\quad &\quad &\quad &\quad &\quad &\quad &\quad &\quad 
\end{matrix}.$$
\vskip-3pt
Note that both rows are strictly increasing because of
$q_{I-1}<q_{I+1}\le p_{I+1}$ and $p_I+t<q_I$. If \eqref{e4.20} is not
satisfied, but hence \eqref{e4.21} is, map $(\mathbf p\mid \mathbf q)$ to 
$$\begin{matrix} &\quad &(q_{1+m}-s)&\dots&(q_I-s)&p_{I+1}&\dots&p_\ell\\
(p_{1-m}+s)&\hdotsfor3&(p_I+s)&q_{I+1}&\dots&q_\ell
\end{matrix}.$$
Again note that both rows are strictly increasing, this time because
of $q_I-s<p_{I+1}$ and $p_I+s<p_{I+2}+s\le q_{I+1}$. 

It is not difficult to verify that this mapping maps type I arrays not
being of type \eqref{e4.18} to type II arrays and vice versa. Besides,
by applying this map to an array twice, one would receive the array
back. Therefore this mapping is the desired bijection.
\end{proof}

??Translation to runs

\section{Simple paths in the plane restricted by lines parallel to
$x=\mu y$} \label{s4.4}
As in the first proof of Theorem~\ref{T1.4}, we use the Lagrange
inversion to enumerate paths below $x=\mu y$ with a given number of
turns for which we need the following refinements of \eqref{e1.12}.

\begin{Proposition} \label{T4.3}
Let $\mu$ be a nonnegative integer. Then 
\begin{equation} \label{e4.22} \sum _{n\ge0} ^{}
\GF{\L{(0,0)\to (\mu n+k,n)\mid x\ge\mu y};t^{NE(.)}}
\frac {z^n} {(1+z)^{n+1}(1+tz)^{\mu n+k}}=1,
\end{equation}
and
\begin{equation} \label{e4.23} \sum _{n\ge0} ^{}
\GF{\L{(0,0)\to (\mu n+k,n)\mid x\ge\mu y};t^{EN(.)}}
\frac {z^n} {(1+z)^{n}(1+tz)^{\mu n+k+1}}=1.
\end{equation}
\end{Proposition}

\begin{proof}We use the same idea as in the proof of Theorem~\ref{T1.19}.
Of course, here we do not encode paths by their coordinates of
vertical steps, but by their coordinates of turns. 

To start with \eqref{e4.22}, multiply \eqref{e4.22} by
$(1+z)^{N+1}(1+tz)^{\mu N+k}$, and obtain
\begin{multline} \label{e4.24} 
\GF{\L{(0,0)\to (\mu n+k,n)\mid x\ge\mu y};t^{NE(.)}}
z^n(1+z)^{N-n}(1+tz)^{\mu(N-n)}\\
=(1+z)^{N+1}(1+tz)^{\mu N+k}.
\end{multline}
We want to show that the coefficients of $z^Nt^\ell$ on both sides agree.
The coefficients of $z^Nt^\ell$ on the left-hand and right-hand side of
\eqref{e4.24} are
\begin{equation} \label{e4.24a}
\sum _{n\ge0} ^{}\sum _{i\ge0} ^{}
\L{(0,0)\to (\mu n+k,n)\mid x\ge\mu y,\,NE(.)=\ell-i}\binom {\mu(N-n)}i
\binom{N-n}i 
\end{equation}
and
\begin{equation} \label{e4.24b}
\binom {\mu N+k}\ell\binom {N+1}{\ell+1},
\end{equation}
respectively. We need a combinatorial interpretation of \eqref{e4.24a}
and \eqref{e4.24b}. In order to explain it, it is convenient to
introduce the following notation. Given two sets $\mathcal A$ and $\mathcal B$
of integers, we denote the set of all two-rowed arrays
$(a_1\dots a_m\mid b_1\dots b_n)$ with $a_i\in \mathcal A$ and $b_i \in
\mathcal B$ by $S_{m,n}(\mathcal A,\mathcal B)$. Then, in combinatorial terms,
establishing that the
quantities \eqref{e4.24a} and \eqref{e4.24b} agree could be shown by setting 
up a one-to-one correspondence between
\begin{multline} \label{e4.25} 
\bigcup _{n\ge0} ^{}\bigcup _{i\ge0} ^{}\L{(0,0)\to (\mu n+k,n)\mid
x\ge \mu y,\, NE(.)=\ell-i}\\
\times S_{i,i}(\{\mu n+k+1,\dots,\mu N+k\},\{n+1,\dots,N\})
\end{multline}
and
\begin{equation} \label{e4.26} 
S_{\ell,\ell+1}(\{1,2,\dots,\mu N+k\},\{0,1,\dots,N\}).
\end{equation}

Let $(P,(r_1\dots r_i\mid s_1\dots s_i))$ be in \eqref{e4.25}. Given
that $(p_1\dots p_{\ell-i}\mid q_1\dots q_{\ell-i})$ is the NE-turn
representation of $P$, we map $(P,(\mathbf r\mid \mathbf s))$ to
\begin{equation} \label{e4.27} 
\begin{matrix} \mu n+k-p_{\ell -i}&\dots&\mu n+k-p_1&r_1&\dots& r_i\\
n-q_{\ell-i}&\dots&n-q_1&n&s_1&\dots&s_i\end{matrix}.
\end{equation}
This two-rowed array is an element of \eqref{e4.26}. At this point,
let us observe that if $(\mathbf e\mid
\mathbf f)$ represents the two-rowed array in \eqref{e4.27} then we
have $e_j\le \mu f_j+k$ for $j=1,2,\dots,\ell-i$, but
$e_{\ell-i+1}>\mu f_{\ell-i+1}+k$ (since $e_{\ell-i+1}=r_1\ge \mu
n+k+1$ and
$f_{\ell-i+1}=n$, see \eqref{e4.27}).

For the
construction of the inverse mapping,  
suppose that $(u_1\dots u_\ell\mid v_1\dots v_{\ell+1})$ is in
\eqref{e4.26}. Let $I$ be the largest integer such that $u_I\le \mu
v_I+k$. If there are none, then let $I=0$. (For motivation of this
definition, recall the observation at
the end of the previous paragraph.) Then map $(\mathbf u\mid \mathbf v)$ to
$(P,(u_{I+1},\dots,u_\ell\mid v_{I+2},\dots,v_{\ell+1}))$,
where $P$ is the path from $(0,0)$ to $(\mu v_{I+1}+k,v_{I+1})$
whose NE-turns are $(\mu v_{I+1}+k-u_{I+1-j},v_{I+1}-v_{I+1-j})$,
$j=1,2,\dots,I$. If $I=0$, $P$ is the path from $(0,0)$ to $(0,0)$. 
It is not difficult to verify that this mapping and the mapping
\eqref{e4.27} are inverses of each other. 
Thus we have shown that the coefficients of $z^Nt^\ell$ in
\eqref{e4.24} agree. This establishes \eqref{e4.22}.

For the proof of \eqref{e4.23} we use the same method. Here, we want to
show that the coefficients of $z^Nt^\ell$ in
\begin{multline} \notag
\GF{\L{(0,0)\to (\mu n+k,n)\mid x\ge\mu y};t^{EN(.)}}
z^n(1+z)^{N-n}(1+tz)^{\mu(N-n)}\\
=(1+z)^{N}(1+tz)^{\mu N+k+1}
\end{multline}
agree on both sides, for all $\ell$.
These are
$$\sum _{n\ge0} ^{}\sum _{i\ge0} ^{}
\L{(0,0)\to (\mu n+k,n)\mid x\ge\mu y,\,EN(.)=\ell-i}\binom {\mu(N-n)}i
\binom{N-n}i $$
and
$$\binom {\mu N+k+1}\ell\binom {N}{\ell},$$
respectively. In combinatorial terms,
we would have to set up a one-to-one correspondence between
\begin{multline} \label{e4.28} 
\bigcup _{n\ge0} ^{}\bigcup _{i\ge0} ^{}\L{(0,0)\to (\mu n+k,n)\mid
x\ge \mu y,\, EN(.)=\ell-i}\\
\times S_{i,i}(\{\mu n+k+1,\dots,\mu N+k\},\{n+1,\dots,N\})
\end{multline}
and
\begin{equation} \label{e4.29} 
S_{\ell,\ell}(\{0,1,\dots,\mu N+k\},\{1,2,\dots,N\}).
\end{equation}

Let $(P,(r_1\dots r_i\mid s_1\dots s_i))$ be in \eqref{e4.28} and
$(p_1\dots p_{\ell-i}\mid q_1\dots q_{\ell-i})$ the NE-turn
representation of $P$. It should be noted that $q_1$ necessarily is 0.
We map $(P,(\mathbf r\mid \mathbf s))$ to
\begin{equation} \label{e4.30} 
\begin{matrix} \mu n+k-p_{\ell -i}&\dots&\mu n+k-p_1&r_1&\dots& r_i\\
n-q_{\ell-i}&\dots&n-q_1&s_1&\dots&s_i\end{matrix}.
\end{equation}

For the inverse mapping, suppose that $(u_1\dots u_\ell\mid v_1\dots
v_{\ell})$ is in
\eqref{e4.29}. Let $I$ be the largest integer such that $u_{I+1}\le \mu
v_I+k$. If there are none, then let $I=0$. Then we map $(\mathbf u\mid
\mathbf v)$ to
$(P,(u_{I+1},\dots,u_\ell\mid v_{I+1},\dots,v_{\ell}))$,
where $P$ is the path from $(0,0)$ to $(\mu v_{I}+k,v_I)$
whose NE-turns are $(\mu v_I+k-u_{I+1-j},v_I-v_{I+1-j})$,
$j=1,2,\dots,I$. If $I=0$, $P$ is the path from $(0,0)$ to $(0,0)$. 
We leave it to the reader to verify that this mapping is the inverse of
\eqref{e4.30}. 
This completes the proof of \eqref{e4.23}.
\end{proof}

Applying the Lagrange inversion \eqref{??} with $f(z)=(1+z)(1+tz)^\mu$
to \eqref{e4.22} and \eqref{e4.23} gives
the desired enumeration results for paths staying below $x=\mu y$ with
a given number of turns.

\begin{Theorem} \label{T4.4}
Let $\mu$ be a positive integer and
$c\ge \mu d$. The number of all lattice paths from the origin to
$(c,d)$ which stay below $x=\mu y$ with exactly $\ell$ NE-turns
is given by
\begin{equation} \label{e4.31} 
\v{\L{(0,0)\to (c,d)\mid x\ge \mu y,\,NE(.)=\ell}}
=\binom c\ell \binom d\ell-\mu\binom {c-1}{\ell-1} \binom
{d+1}{\ell+1},\hskip.5cm
\end{equation}
and with exactly $\ell$ EN-turns is given by
\begin{multline} \label{e4.32} 
\v{\L{(0,0)\to (c,d)\mid x\ge \mu y,\,EN(.)=\ell}}\\
=\frac {c-\mu d+1} {c+1}\binom {c+1}{\ell} \binom {d-1}{\ell-1}
=\binom {c+1}\ell \binom {d-1}{\ell-1}-\mu\binom {c}{\ell-1} \binom
{d}{\ell}.
\end{multline}
\end{Theorem}
There are also nice combinatorial proofs for \eqref{e4.31} and
\eqref{e4.32}, making use of two-rowed arrays. This is what we
describe next.
\begin{proof} [Combinatorial Proof of Theorem~\ref{T4.4}]
We start with a combinatorial proof of \eqref{e4.31}. 
We represent our paths from $(0,0)$
to $(c,d)$ staying below $x=\mu y$ with exactly $\ell$ NE-turns, 
by their NE-turn representation. It is given by
{\refstepcounter{equation}\label{e4.33}}
\alphaeqn
\begin{equation} \label{e4.33a}
\begin{array} {rccccl}
0\le&\quad p_1&p_2&\dots&p_\ell&\quad \le c-1\\
1\le&\quad q_1&q_2&\dots&q_\ell&\quad \le d,
\end{array}
\end{equation}
where
\begin{equation} \label{e4.33b}
p_i\ge \mu q_i, \quad \quad i=1,2,\dots,\ell.
\end{equation}
\reseteqn
Again, the number
of these two-rowed arrays is the number of {\it all\/} two-rowed arrays
of the type \eqref{e4.33a} minus those two-rowed arrays of the type
\eqref{e4.33a} which violate \eqref{e4.33b}, i.e\@. where $p_i<\mu q_i$ for
some $i$ between $1$ and $\ell$. The first number is clearly $\binom
c\ell\binom d\ell$.

We claim that there are as many two-rowed arrays of the
type \eqref{e4.33a} which violate \eqref{e4.33b} as $\mu$ times
the number of two-rowed arrays of the type 
\begin{equation} \label{e4.34}
\begin{array} {rcccccl}
1\le&\quad &&r_2&\dots&r_\ell&\quad \le c-1\\
0\le&\quad s_0&s_1&s_2&\dots&s_\ell&\quad \le
d.\end{array}
\end{equation}
The number of all these two-rowed arrays is $\binom {c-1}{\ell-1}
\binom {d+1}{\ell+1}$, as desired. What remains to do is to find a
$(1:\mu)$ correspondence between the two-rowed arrays of type \eqref{e4.33a}
violating \eqref{e4.33b}, and those of type \eqref{e4.34}.

Take a two-rowed array $(\mathbf p\mid \mathbf q)$ of the type \eqref{e4.33a} 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 $(\mathbf p\mid \mathbf q)$ then looks like
\begin{equation} \label{e4.35}
\begin{tabular}  {r c c c | c | c c l}
$0\le$&$p_1$&\multicolumn2{c} \dotfill &$p_I$&\dots&$p_\ell$&$\le c-1$\\
\cline{5-5}
$1\le$&$q_1$&\dots&$q_{I-1}$&\multicolumn1{c}{$q_I$}&\dots&$q_\ell$&$\le d$
 \end{tabular}.
\end{equation}
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 
\begin{equation} \label{e4.36}
\binom {\mu q_I}I\cdot\binom {q_I-1}{I-1}
\end{equation}
possible left portions.

On the other hand, let $(\mathbf r\mid \mathbf s)$ be a two-rowed array of the type
\eqref{e4.34}. Let $J$ be maximal with $r_J<\mu s_J$ (if there is no such $J$
take $J=1$), so that $(\mathbf r\mid \mathbf s)$ looks like
\begin{equation} \label{e4.37}
\begin{tabular}  {r c c c c c | c | c c l}
$1\le$&\quad &\quad &$r_2$&\multicolumn2{c}\dotfill &$r_J$&\dots&$r_\ell$&$\le
c-1$\\
\cline{7-7}
$0\le$&$s_0$&$s_1$&$s_2$&\dots
&$s_{J-1}$&\multicolumn1{c}{$s_J$}&\dots&$s_\ell$&$\le d$
 \end{tabular}.
\end{equation}
Again, fix the right portion, i.e., the entries 
$r_{J+1},\dots,r_{\ell}$ and $s_J,\dots,s_\ell$. Furthermore, 
assume that the right-hand portion in \eqref{e4.37} is
equal to the right portion in \eqref{e4.35}, i.e., assume that $J=I$, $r_i=p_i$,
$i=I+1,\dots,\ell$, and $s_i=q_i$, $i=I,\dots,\ell$. With this fixed
right portion in \eqref{e4.37} there are 
\begin{equation} \label{e4.38}
\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}
\end{equation}
possible left portions. By comparing with \eqref{e4.36}, we see that, for a
fixed right portion, there are $\mu$ times as many two-rowed arrays
of the type \eqref{e4.35} with $p_I<\mu q_I$, as there are two-rowed arrays
of the type \eqref{e4.37} with $r_I<\mu s_I=\mu q_I$. This settles our
claim and hence finishes the proof of \eqref{e4.31}.

\medskip
The second assertion, \eqref{e4.32}, can be established in
much the same way as the above proof of \eqref{e4.31}. To be precise,
this sort of argument would give the second expression in
\eqref{e4.32}. 

Interestingly, there is also a nice combinatorial
argument to explain the first expression in \eqref{e4.32},
by using the \index{cycle lemma}cycle lemma~\ref{T1.5}. The argument
given here can be considered as a refinement of the one in the 
combinatorial proof of Theorem~\ref{T1.4} (given after the proof of
the cycle lemma~\ref{T1.5}).

We want to count paths from $(0,0)$ to $(c,d)$ staying (weakly) below $x=\mu
y$ which have exactly $\ell$
EN-turns. Again, to fit with the cycle lemma we adjoin a horizontal step at the
beginning and shift everything by one unit to the right. Thus we are
now asking for the number of paths from $(0,0)$ to $(c+1,d)$ staying
{\em strictly\/} below $x=\mu y$, except for the starting point
$(0,0)$, which have exactly $\ell$ EN-turns.
To find this number, $N$ say, we count in
two different ways the set of all pairs $(P,Q)$,
where 
\begin{enumerate}
\item $P$ is any path from $(0,0)$ to $(c+1,d)$ which starts with a
horizontal step and which has exactly $\ell$ EN-turns,
\item $Q$ is a path
from $(0,0)$ to $(c+1,d)$ which stays strictly below $x=\mu y$ except for
$(0,0)$ and which has exactly $\ell$ EN-turns,
\item $P$ and $Q$ are related by a cyclic permutation of their steps.
\end{enumerate}  
Figure~\ref{F4.1A} displays an example of such a pair $(P,Q)$, with
$\mu=2$, $c=6$, $d=2$, $\ell=2$, where $Q$ is the cyclic permutation of $P$
which starts with the third step of $P$. The bold steps in the Figure
indicate the possible beginnings of a path $Q$.


\begin{Figure}\label{F4.1A}
$$
\underset {\text {a. Arbitrary path}}
{
\Gitter(9,5)(0,0)
\Koordinatenachsen(9,5)(0,0)
\Pfad(0,0),121112111\endPfad
\PfadDicke{2.5pt}
\Pfad(1,1),1\endPfad
\Pfad(4,2),11\endPfad
\Label\lo{P}(2,1)
\Label\lo{(c+1,d)}(9,2)
\Label\lo{x=\mu y}(6,3)
\PfadDicke{.5pt}
\raise-.5\Einheit\hbox to0pt{\hskip-1 \Einheit
         \unitlength\Einheit
         \line(2,1){10}\hss}
\DickPunkt(0,0)
\DickPunkt(7,2)
\hskip5cm
}
\hbox{\hskip3cm}
\underset {\text {b. Path staying strictly below $x=\mu y$}}
{
\Gitter(9,5)(0,0)
\Koordinatenachsen(9,5)(0,0)
\PfadDicke{1pt}
\Pfad(0,0),111211112\endPfad
\Label\ro{Q}(5,1)
\Label\lo{(c+1,d)}(9,2)
\Label\lo{x=\mu y}(6,3)
\PfadDicke{.5pt}
\raise-.5\Einheit\hbox to0pt{\hskip-1 \Einheit
         \unitlength\Einheit
         \line(2,1){10}\hss}
\DickPunkt(0,0)
\DickPunkt(7,2)
\hskip5cm
}
$$
\end{Figure}


It is not difficult to see that there are $\binom {c+1}\ell\binom
{d-1}{\ell-1}$
possible paths $P$, and, by the cycle lemma~\ref{T1.5}, for each $P$
there are exactly $c+1-\mu d$ cyclic permutations $Q$ staying
strictly below $x=\mu y$ except for $(0,0)$. So our set of pairs
$(P,Q)$ has cardinality $(c+1-\mu d)\binom {c+1}\ell\binom
{d-1}{\ell-1}$. On the other
hand, there are $N$ possible paths $Q$, and for each $Q$ there are $c+1$
cyclic permutations $P$, namely those which start with one of the
$c+1$ horizontal steps of $Q$. Therefore the cardinality of our set of
pairs $(P,Q)$ is also equal to $(c+1)N$. Equating the two
expressions for the cardinality
gives the desired result for the number $N$ that we are
looking for.
\end{proof}

??translate into Mohanty--Narayana results

??translate into runs

??two-boundaries, $x=\mu y+t$, $x=\mu y+s$, start in first line, end
in second, formula similar to above Theorem?

??general boundary $->$ multiple sums.

\section{Nonintersecting lattice paths and their number of turns}
\label{s4.5}
In this section we are concerned with a problem that arose from the
study of the Hilbert polynomial of certain determinantal and Pfaffian
rings \cite{??}. Let $\A=(A_1,A_2,\dots,A_n)$ and
$\E=(E_1,E_2,\dots,E_n)$ be points in $\Z^2$. How many families
$\P=(P_1,P_2,\dots,P_n)$ of nonintersecting lattice paths, where $P_i$
runs from $A_i$ to $E_i$, $i=1,2,\dots,n$, are there such that the
total number of NE-turns in $\P$ is some fixed number, $\ell$ say. 
In a sense, the results of this section refine the
results of Chapter~\ref{ch2}. Of course, as in Chapter~\ref{ch2} we
will assume that the starting and end points are located such that
they are compatible (in the sense of the paragraph before
Theorem~\ref{T2.1}). We shall even assume the stronger
condition that
...?? The case that is actually relevant for the determination of
Hilbert polynomials of determinantal rings is the one where the
starting points are on one vertical line and the end points are on one
horizontal line. The problem can however be solved for the general
case by using, not surprisingly, two-rowed arrays.

We are going to prove the following three theorems about
the counting of nonintersecting lattice paths with a given number of
turns. The first theorem concerns counting families of nonintersecting
lattice paths with given starting and end points with a given number
of NE-turns.
\begin{Theorem} \label{T4.10}
Let 
$A_i=(a_1^{(i)},a_2^{(i)})$ and $E_i=(e_1^{(i)},e_2^{(i)})$ 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 number of all families $\P=(P_1,P_2,
\dots,P_n)$ of nonintersecting lattice paths $P_i:A_i\to E_i$,
such that the paths of $\P$ altogether contain exactly $\ell$ NE-turns, is
\begin{equation}\label{e4.51}
\sum _{\ell_1+\dotsb+\ell_n=\ell} ^{}\det_{1\le i,j\le n}
\bigg(\binom{e_1^{(j)}-a_1^{(i)}+i-j}{\ell_i+i-j}
\binom{e_2^{(j)}-a_2^{(i)}-i+j}{\ell_i}\bigg).
\end{equation}
\end{Theorem}
The second theorem concerns counting families of nonintersecting
lattice paths staying below $x=y$, with given starting and end points,
by their number of NE-turns.
\begin{Theorem}\label{T4.11}
Let $A_i=(a_1^{(i)},a_2^{(i)})$ and
$E_i=(e_1^{(i)},e_2^{(i)})$ 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 number of 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$, and
where the paths of $\P$ altogether
contain exactly $\ell$ NE-turns, is
\begin{multline}\label{e4.52}
\sum _{\ell_1+\dotsb+\ell_n=\ell} ^{}\det_{1\le i,j\le n}
\bigg(\binom{e_1^{(j)}-a_1^{(i)}+i-j}{\ell_i+i-j}
\binom{e_2^{(j)}-a_2^{(i)}-i+j}{\ell_i}\\
-\binom{e_1^{(j)}-a_2^{(i)}-i-j+1}{\ell_i-j}
\binom{e_2^{(j)}-a_1^{(i)}+i+j-1}{\ell_i+s}\bigg).
\end{multline}
\end{Theorem}
In the third theorem (basically) the same families of nonintersecting
lattice paths as before are counted, but with respect to their number
of EN-turns. By a rotation by $180^\circ$ this could be translated
into a result about counting families of nonintersecting lattice paths
staying {\em above\/} $x=y$, with given starting and end points, with
respect to {\em NE-turns\/}.
\begin{Theorem}\label{T4.12}
Let $A_i=(a_1^{(i)},a_2^{(i)})$ and 
$E_i=(e_1^{(i)},e_2^{(i)})$ be lattice points satisfying 
$$a_1^{(1)}< a_1^{(2)}<\dotsb< a_1^{(n)},\quad
a_2^{(1)}\ge a_2^{(2)}\ge \dotsb\ge a_2^{(n)},$$
$$
e_1^{(1)}\le  e_1^{(2)}\le \dotsb\le  e_1^{(n)},\quad
e_2^{(1)}> e_2^{(2)}> \dotsb> 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 number of all families $\P=(P_1,P_2,\dots,P_n)$ of nonintersecting
lattice paths $P_i:A_i\to E_i$, $P_i:A_i\to E_i$, which stay below
the line $x=y$, and where the paths of
$\P$ altogether
contain exactly $\ell$ EN-turns, is
\begin{multline}\label{e4.53}
\sum _{\ell_1+\dotsb+\ell_n=\ell} ^{}\det_{1\le  i,j\le  n}
\bigg(\binom{e_1^{(j)}-a_1^{(i)}+i-j}{\ell_i+i-j}
\binom{e_2^{(j)}-a_2^{(i)}-i+j}{\ell_i}\\
-\binom{e_1^{(j)}-a_2^{(i)}-i-j+3}{\ell_i-j+1}
\binom{e_2^{(j)}-a_1^{(i)}+i+j-3}{\ell_i+i-1}\bigg).
\end{multline}
\end{Theorem}

These theorems are more conveniently proved after before having
modified the problem. This modification is described next.

Suppose, $\P=(P_1,P_2,\dots,P_n)$ is a family of nonintersecting lattice 
paths $P_i:A_i\to E_i$. Now we shift the $i$-th path $P_i$
in the direction $(-i+1,i-1)$ thus obtaining the new path $P'_i$,
$i=1,2,\dots,n$. The new family $\P'=(P'_1,P'_2,\dots,P'_n)$ might be
intersecting, however it is {\em non-crossing\/} (see Figure~\ref{F4.2}). 
\begin{Figure}\label{F4.2}
$$\Koordinatenachsen(7,7)(0,0)
\Gitter(7,7)(0,0)
\Pfad(-1,1),1222111122\endPfad
\Pfad(1,0),21122111\endPfad
\Pfad(2,0),111122\endPfad
\DickPunkt(-1,1)
\DickPunkt(1,0)
\DickPunkt(2,0)
\DickPunkt(4,6)
\DickPunkt(6,3)
\DickPunkt(6,2)
\Label\ro{P_1}(1,4)
\Label\o{P_2}(2,1)
\Label\lo{P_3}(5,0)
\hskip4cm
\longrightarrow
\hskip1cm\hbox{}
\Koordinatenachsen(7,7)(0,0)
\Gitter(7,7)(0,0)
\hskip-2pt\raise2pt\hbox{\Pfad(-1,1),1222111122\endPfad
\DickPunkt(-1,1)
\DickPunkt(4,6)}
\hskip2pt\hbox{}
\Pfad(0,1),21122111\endPfad
\DickPunkt(0,1)
\DickPunkt(5,4)
\hskip2pt\hbox{}
\raise-2pt\hbox{\Pfad(0,2),111122\endPfad
\DickPunkt(0,2)
\DickPunkt(4,4)}
\hskip-2pt\hbox{}
\Label\ro{P'_1}(1,4)
\Label\o{P'_2}(1,2)
\Label\ro{P'_3}(3,2)
\hskip4cm
$$
\vbox{\small \hskip1cm\raise0cm\hbox{nonintersecting lattice
paths}\hskip2cm 
\raise0cm\hbox{non-crossing lattice paths}}
\end{Figure}

The actual meaning of ``non-crossing'' stems from applying the
shifting process to nonintersecting paths. Hence,
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)$ with 
$$a_1\le b_1,\ a_2>b_2,\ e_1< f_1,\ e_2\ge f_2.$$
Roughly speaking, these inequalities say that $ A$ is located in the
north-West of $ B$ (strictly in direction north and weakly in
direction West), and $ E$ is located in the
north-West of $ F$ (weakly in direction north and strictly in
direction West).
 Let the array representations of $P_1$ and $P_2$ 
be
\begin{equation}\label{e4.54}
P_1:\quad \begin{array} {rcccl}
a_1\le&p_1&\hdots&p_k&\le e_1-1\\
a_2+1\le&q_1&\hdots&q_k&\le e_2\end{array}\hphantom{\ ,}
\end{equation}
and
\begin{equation}\label{e4.55}
P_2:\quad \begin{array} {rcccl}
b_1\le&r_1&\hdots&r_l&\le f_1-1\\
b_2+1\le&s_1&\hdots&s_l&\le f_2\end{array}\ ,
\end{equation}
respectively. 

Suppose that $P_1$ and $P_2$ intersect, i.e\@. have a point in common.
Let $M$ be a meeting point of $P_1$ and $P_2$.
By definition set $p_{k+1}:=e_1$ and $q_0:=a_2$.
(Note that the thereby augmented sequences $a$ and $b $
remain strictly increasing.)

\begin{Figure}\label{F4.3}
$$
\Pfad(0,0),221111121111\endPfad
\Pfad(-2,-1),11112222221111\endPfad
\DickPunkt(0,2)
\DickPunkt(2,2)
\DickPunkt(2,-1)
\Label\ru{M}(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
$$
\end{Figure}
Considering the east-north turn $(p_I,q_{I-1})$ in $P_1$
immediately preceding $M$ (and being allowed to be equal to $M$)
and the north-east turn $(r_J,s_J)$ in $P_2$ immediately preceding
$M$ (and being allowed to be equal to $M$), we get the inequalities
(cf\@. Figure~\ref{F4.3})
{\refstepcounter{equation}\label{e4.56}}
\alphaeqn
\begin{gather}\label{e4.56a} r_J\le p_I,\\
\label{e4.56b}
 q_{I-1}\le
s_J,
\end{gather}
where
\begin{equation}\label{e4.56c}
1\le I\le k+1,\quad 1\le J\le l.
\end{equation}
\reseteqn

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 (\ref{e4.56}a,b) to make sense for $I=1$ or $I=k+1$.
Note that $M=(p_I,s_J)$. Vice versa, if (\ref{e4.56}a,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 (\ref{e4.56}a,b,c) characterize the array representations of
{\em intersecting\/} pairs of paths. 

Now, if $P_2$ is shifted in direction $(-1,1)$, we obtain the path
$P_2'$ with array representation 
\begin{equation}\label{e4.57}
\begin{array}{rcccl}
b'_1\le&c'_1&\hdots&c'_l&\le f'_1-1\\
b'_2+1\le&d'_1&\hdots&d'_l&\le f'_2\end{array}\ ,
\end{equation}
where $c'_i=r_i-1$, $d'_i=s_i+1$, $b'_1=b_1-1$, $b'_2=b_2+1$,
$f'_1=f_1-1$, $f'_2=f_2+1$.
The conditions (\ref{e4.56}a,b,c) become
{\refstepcounter{equation}\label{e4.58}}
\alphaeqn
\begin{gather} c'_J< p_I,\label{e4.58a}\\
 q_{I-1}<
d'_J,\label{e4.58b}
\end{gather}
where
\begin{equation}\label{e4.58c}
1\le I\le k+1,\quad 1\le J\le l.
\end{equation}
\reseteqn
We take (\ref{e4.58}a,b,c) as definition of two paths $P_1$ and $P_2$ with
array representations 
\eqref{e4.54} and \eqref{e4.57}, respectively, being non-crossing.
We call the point $(p_I,d'_J)$ {\em crossing point\/} of $P_1$ and $P_2$.

Modulo the above described shifting process,
Theorems~\ref{T4.10}--\ref{T4.12} are equivalent to the following
three Theorems. Aside from translating ``nonintersecting" into
``non-crossing", we also transformed \eqref{e4.51}--\eqref{e4.53} into
generating functions form. Thus the results become more compact and
also more closely resemble the similarity to the determinant formulas
\eqref{e2.??}, \eqref{e2.??} for counting without turns.
\begin{Theorem}\label{T4.13}
Let $A_i=(a_1^{(i)},a_2^{(i)})$ and $E_i=(e_1^{(i)},e_2^{(i)})$ be lattice points satisfying
\begin{equation}\label{e4.60}
a_1^{(1)}+1\le a_1^{(2)}+2\le\dotsb\le a_1^{(n)}+n,\quad
a_2^{(1)}\ge a_2^{(2)}\ge \dotsb\ge a_2^{(n)},
\end{equation}
and
\begin{equation}\label{e4.61}
e_1^{(1)}\le e_1^{(2)}\le \dotsb\le e_1^{(n)},\quad
e_2^{(1)}-1\ge e_2^{(2)}-2\ge \dotsb\ge e_2^{(n)}-n.
\end{equation}
The generating function $\sum _{\P} t^{NE(\P)}$ 
where the sum is over all families $\P=(P_1,P_2,\dots, 
P_n)$ of non-crossing lattice paths $P_i:A_i\to E_i$,
is
\begin{multline}\label{e4.62}
\GF{\L{(\A\to\E\mid \text{\em non-crossing})};t^{NE(.)}}\\
=\det_{1\le i,j\le
n}\(\sum _{\ell_i} ^{}\binom {e_1^{(j)}-a_1^{(i)}}{\ell_i+i-j}
\binom {e_2^{(j)}-a_2^{(i)}}{\ell_i}\).
\end{multline}
\end{Theorem}
\begin{Theorem}\label{T4.14}
Let $A_i=(a_1^{(i)},a_2^{(i)})$ and $E_i=(e_1^{(i)},e_2^{(i)})$ 
be lattice points satisfying \eqref{e4.60} and \eqref{e4.61}
and 
\begin{equation}\label{e4.63}
a_1^{(1)}\ge a_2^{(1)}\quad \text {and}\quad e_1^{(1)}\ge
e_2^{(1)}.
\end{equation}
The generating function $\sum _{\P} t^{NE(\P)}$ 
where the sum is over all families $\P=(P_1,P_2,\dots,\break P_n)$ of non-crossing lattice paths 
$P_i:A_i\to E_i$, 
such that $P_1$ stays below the line $x=y$,
is
\begin{multline}\label{e4.64}
\GF{\L{(\A\to\E\mid x\ge y,\,\text{\em non-crossing})};t^{NE(.)}}\\
=\det_{1\le i,j\le
n}\bigg(\sum _{\ell_i} ^{}\bigg(\binom
{e_1^{(j)}-a_2^{(i)}}{\ell_i+i-j}
\binom {e_2^{(j)}-a_2^{(i)}}{\ell_i}\\-
\binom {e_1^{(j)}-a_2^{(i)}-1}{\ell_i-j}
\binom {e_2^{(j)}-a_1^{(i)}+1}{\ell_i+i}\bigg)t^{\ell_i}\bigg).
\end{multline}
\end{Theorem}
\begin{Theorem}\label{T4.15}
Let $A_i=(a_1^{(i)},a_2^{(i)})$ and $E_i=(e_1^{(i)},e_2^{(i)})$ 
be lattice points satisfying 
\begin{gather}
a_1^{(1)}\le a_1^{(2)}\le\dotsb\le a_1^{(n)},\quad
a_2^{(1)}-1\ge a_2^{(2)}-2\ge \dotsb\ge a_2^{(n)}-n,\label{e4.65}\\
e_1^{(1)}+1\le e_1^{(2)}+2\le \dotsb\le e_1^{(n)}+n,\quad
e_2^{(1)}\ge e_2^{(2)}\ge \dotsb\ge e_2^{(n)},\label{e4.66}
\end{gather}
and \eqref{e4.63}.
The generating function $\sum _{\P} t^{EN(\P)}$ 
where the sum is over all families $\P=(P_1,P_2,\dots,P_n)$ 
of non-crossing lattice paths $P_i:A_i\to E_i$,
such that $P_1$ stays below the line $x=y$,
is
\begin{multline}\label{e4.67}
\GF{\L{(\A\to\E\mid x\ge y,\,\text{\em non-crossing})};t^{EN(.)}}\\
=\det_{1\le i,j\le
n}\bigg(\sum _{\ell_i} ^{}\bigg(\binom {e_1^{(j)}-a_1^{(i)}}{\ell_i+i-j}
\binom {e_2^{(j)}-a_2^{(i)}}{\ell_i}
\\-\binom {e_1^{(j)}-a_2^{(i)}+1}{\ell_i-j+1}
\binom {e_2^{(j)}-a_1^{(i)}-1}{\ell_i+i-1}
\bigg)t^{\ell_i}\bigg).
\end{multline}
\end{Theorem}

\begin{proof}[Proof of Theorem \ref{T4.13}] 
Since 
in the proof we are also considering {\em skew\/} two-rowed arrays, we
introduce some terminology for convenience. Let
$j>0$. We say that the two-rowed array $P$ {\em is of the type\/} $j$
if $P$ has the form
$$\begin{array}{cccccccc}
 p_{-j+1}&p_{-j+2}&\dots&p_{-1}&p_0&p_1&\dots&p_k\\
&&&&&q_1&\dots&q_k\end{array}$$
for some $k\ge0$. We say that $P$ {\em is of the type\/} $-j$ if $P$ has
the form
$$\begin{array}{ccccccccc}
&&&&&p_1&\dots&p_k\\
 q_{-j+1}&q_{-j+2}&\dots&q_{-1}&q_0&q_1&\dots&q_k\end{array}$$
for some $k\ge0$. Note that the placement of indices is chosen such
that non-positive indices can occur only in {\em one\/} row of $P$,
while the positive indices occur in both rows of $P$.

First we give the combinatorial interpretation of the determinant
\eqref{e4.62} 
in terms of two-rowed arrays. It is easy to see that \eqref{e4.62} is the
generating function
\begin{equation}\label{e4.68}
\sum _{(\P,\si)} ^{}\sgn\si\, w_{\x,\y}(\P),
\end{equation}
where the sum is over all pairs $(\P, \si)$ of permutations $\si$
in $\S_n$, the symmetric group of order $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,
\begin{equation}\label{e4.69}
\begin{array} {rcl}
a_1^{(\si(i))}\le&\dots\ p_{\ell_i}^{(i)}&\le e_1^{(i)}-1\\
a_2^{(\si(i))}+1\le&\dots\ q_{\ell_i}^{(i)}&\le e_2^{(i)}
\end{array},
\end{equation}
$i=1,2,\dots,n$.

The outline of the proof is as follows. Next we extend the notion of
being non-crossing to two-rowed arrays. We then show that in the
sum \eqref{e4.68} 
all contributions corresponding to pairs $(\P,\si)$ where
$\P$ is a crossing family (to be explained below) 
of two-rowed arrays cancel. This is done by
constructing a weight-preserving, sign-reversing involution on those
pairs. Finally we show that in a pair $(\P,\si)$ with $\si\ne \text
{id}$ the family $\P$ must be crossing. This establishes that
only pairs $(\P,\text {id})$ where $\P$ is a non-crossing
family of two-rowed arrays contribute to the sum \eqref{e4.68}. But these
pairs exactly correspond to the families of non-crossing paths under
consideration, hence Theorem~\ref{T4.13} would be proved.

\medskip
Let $M_1$ and $M_2$ be two-rowed arrays, given by
$$M_1:\quad \quad 
\begin{array} {rcl}
a_1\le&\dots\ p_k&\le e_1-1\\
a_2+1\le&\dots\ q_k&\le e_2\end{array}$$
and
$$M_2:\quad \quad 
\begin{array}{rcl}
b_1\le&\dots\ r_l&\le f_1-1\\
b_2+1\le&\dots\ s_l&\le f_2\end{array},$$
respectively. 
By definition we set $p_{k+1}:=e_1$, we set $q_0:=a_2$
 in case that the sequence $\dots\ q_0$ is empty, and we set $r_0:=b_1-1$
in case that the sequence $\dots\ r_0$ is empty.
We say that $(p_I,s_J)$ is a {\em crossing point\/} of
$M_1$ and $M_2$ if 
{\refstepcounter{equation}\label{e4.70}}
\alphaeqn
\begin{gather}  r_J<p_I\label{e4.70a}\\
q_{I-1}<s_J\label{e4.70b}
\end{gather}
and
\begin{equation}\label{e4.70c}
1\le I\le k+1,\quad  0\le J\le l.
\end{equation}
\reseteqn
These inequalities should be understood to hold only if all variables
are defined. In particular, if the sequence $\dots\ s_0$ is empty the
inequality (\ref{e4.70}b) does not make sense. However, if the sequence $\dots
\ r_0$ is empty the inequality (\ref{e4.70}a) makes sense because of the
conventional assignment for $r_0$ above.
\medskip

Let $(\P,\si)$ be a pair under consideration for the sum \eqref{e4.68}. 
Besides, we assume that $\P$ contains two two-rowed arrays $P_i$
and $P_{i+1}$ with
consecutive indices that have a crossing point. In the sequel
two-rowed arrays with consecutive indices will be called {\em
neighbouring\/} two-rowed arrays. A pair $(\P,\si)$ where $\P$
contains neighbouring
two-rowed arrays with a crossing point will be called {\em crossing\/}.
Otherwise it will be called {\em non-crossing\/}.
We are going to construct a weight-preserving (with respect to the
weight function $w_{\x,\y}$) and sign-reversing (with respect to
$\sgn \si$) involution on crossing pairs $(\P,\si)$.
Consider all
crossing points of neighbouring arrays. Among these points choose
those with maximal $x$-coordinate, and among all those choose the
crossing point with maximal $y$-coordinate. Denote this crossing
point by $M$. Let $i$ be minimal such that $M$ is a crossing point of
$P_i$ and $P_{i+1}$. Let $P_i=(\mathbf a\mid \mathbf b)=(\dots p_{\ell_i}\mid \dots
q_{\ell_i})$ and $P_{i+1}=(\mathbf c\mid \mathbf 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 \eqref{e4.69}. By \eqref{e4.70}, $M$ being a
crossing point of $P_i$ and $P_{i+1}$ means that there exist $I$ and
$J$ such that $P_i$ looks like
\begin{equation}\label{e4.71}
\begin{array}{rcccccl}
 a_1^{(\si(i))} \le&\dots&p_{I-1}&p_I&\dots&p_{\ell_i}&\le e_1^{(i)}-1\\
 a_2^{(\si(i))}+1 \le&\dots&q_{I-1}&q_I&\dots&q_{\ell_i}&\le e_2^{(i)}
\end{array},
\end{equation}
$P_{i+1}$ looks like
\begin{equation}\label{e4.72}
\begin{array}{rccccccl}
 a_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))}+1 \le&\dots&s_{J-1}&s_J&\hdotsfor2
&s_{\ell_{i+1}}&\le e_2^{(i+1)}
\end{array},
\end{equation}
$M=(p_I,s_J)$, 
{\refstepcounter{equation}\label{e4.73}}
\alphaeqn
\begin{gather}  r_J<p_I\label{e4.73a}\\
q_{I-1}<s_J\label{e4.73b}
\end{gather}
and
\begin{equation}\label{e4.73c}
1\le I\le \ell_i+1,\quad  0\le J\le \ell_{i+1}.
\end{equation}
\reseteqn
Because of the construction of $M$ the indices $I$ {\em and\/} $J$ are
maximal with respect to (\ref{e4.73}a,b,c).

We map $(\P,\si)$ to the pair $(\bar{\P},\si\circ(i,i+1))$
($(i,i+1)$
denotes the transposition exchanging $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
{\refstepcounter{equation}\label{e4.74}}
\alphaeqn
\begin{equation}\label{e4.74a}
\begin{array} {ccccc}
\dots&r_J&p_I&\dots&p_{\ell_i}\\
\dots&s_{J-1}&q_I&\dots&q_{\ell_i}\end{array},
\end{equation}
$\bar P_{i+1}$ being given by
\begin{equation}\label{e4.74b}
\begin{array} {cccccc}
\hdotsfor2&p_{I-1}&r_{J+1}&\dots&r_{\ell_{i+1}}\\
\dots&q_{I-1}&s_J&\hdotsfor2
&s_{\ell_{i+1}}\end{array}.
\end{equation}
\reseteqn
First of all, this operation is well-defined, i.e., all the rows in
\eqref{e4.74a} and \eqref{e4.74b} are strictly increasing. 
To see this we have to check
$r_J<p_I$, $s_{J-1}<q_I$, $p_{I-1}<r_{J+1}$, and $q_{I-1}<s_J$. This
is obvious for the first and last inequality, because of
\eqref{e4.73a} and
\eqref{e4.73b}. As for the second inequality, let us suppose $s_{J-1}\ge q_I$.
Then, by \eqref{e4.73a}, we have $r_J<p_{I}<p_{I+1}$ and $q_I\le s_{J-1}<s_J$. 
This means
that $(p_{I+1},s_J)$ is a crossing 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}\ge
r_{J+1}$, we have $r_{J+1}\le p_{I-1}<p_I$ and, by \eqref{e4.73b},
$q_{I-1}<s_J<s_{J+1}$. This means
that $(p_{I},s_{J+1})$ is a crossing 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 \eqref{e4.68}. 
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
\begin{equation}\label{e4.76}
\begin{array} {rcccccl}
a_1^{(\si(i+1))}\le&\dots&r_J&p_I&\dots&p_{\ell_i}&\le e_1^{(i)}-1\\
a_2^{(\si(i+1))}+1\le&\dots&s_{J-1}&q_I&\dots&q_{\ell_i}&\le
e_2^{(i)}\end{array},
\end{equation}
 and that those for $\bar P_{i+1}$ are given by
\begin{equation}\label{e4.77}
\begin{array} {rccccccl}
a_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))}+1\le&\dots&q_{I-1}&s_J&\hdotsfor2
&s_{\ell_{i+1}}&\le e_2^{(i+1)}\end{array}.
\end{equation}
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
\index{Krattenthaler, Christian}Krattenthaler \cite{KratBE}. 
Obviously the map \eqref{e4.74} 
reverses the signs of the associated permutations.
Besides, it can be checked that it is an involution. 

Finally we have to show 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 a crossing point.  If $\si\ne \text {id}$ then
there must exist an $i$ with $\si(i+1)<i+1$. Without loss of
generality we may assume that $i$ is minimal with this property. Then
we have $\si(i)\ge i$. Besides, from $\si(i)\ge i\ge \si(i+1)$ it
follows that $\si(i)>\si(i+1)$. 
Let $P_i=(\mathbf a\mid \mathbf b)=(\dots p_{\ell_i}\mid \dots
q_{\ell_i})$ and $P_{i+1}=(\mathbf c\mid \mathbf d)=(\dots r_{\ell_{i+1}}\mid \dots
s_{\ell_{i+1}})$. Because of $\si(i)-i\ge0$ the sequence $\dots q_0$ is
empty, hence the assignment $q_0:=a_2^{(\si(i))}$ applies. Because of
$\si(i+1)-i-1<0$ the sequence $\dots r_0$ is empty, hence the
assignment $r_0:=a_1^{(\si(i+1))}-1$ applies. Because of
$\si(i)>\si(i+1)$ and \eqref{e4.60} the inequalities
$r_0=a_1^{(\si(i+1))}-1\le a_1^{(\si(i))}<p_1$ and
$q_0=a_2^{(\si(i))}\le a_2^{(\si(i+1))}<s_0$ hold. By \eqref{e4.70} 
this means that $(p_1,s_0)$ is a crossing point of $P_i$ and
$P_{i+1}$.
\end{proof}


\begin{proof}[Proof of Theorem \ref{T4.14}] 
Again we work with families of two-rowed arrays. This time we
consider triples $(\P,\si,\et)$, where $\si$ is a permutation in
$\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 
\begin{equation}\label{e4.78}
\begin{array} {rcl}
a_1^{(\si(i))}\le &\dots&\le e_1^{(i)}-1\\
a_2^{(\si(i))}+1\le &\dots&\le e_2^{(i)}\\
\end{array}, \text {\quad for $\et=1$,}
\end{equation}
respectively
\begin{equation}\label{e4.79}
\begin{array} {rcl}
a_2^{(\si(i))}+1\le &\dots&\le e_1^{(i)}-1\\
a_1^{(\si(i))}\le &\dots&\le e_2^{(i)}\\
\end{array}, \text {\quad for $\et=-1$.}
\end{equation}
Define $\sgn\et:=\prod _{i=1} ^{n}\et_i$.
It is easy to see that \eqref{e4.64} is the generating function 
\begin{equation}\label{e4.80}
\sum _{(\P,\si,\et)} ^{}\sgn\et\,\sgn\si\,w_{\x,\x}(\P)
\end{equation}
where the sum is over all triples
which were described above.

We adopt the notion of ``crossing of neighbouring arrays" from the
previous proof. In addition, we have to consider crossings of $P_1$
with the line $x=y$. Let $P_1=(\mathbf a\mid \mathbf b)$, or with bounds included
\begin{equation}\label{e4.81}
\begin{array} {rccccccl}
L_1\le&\hdotsfor2 &p_{I}&p_{I+1}&\dots&p_{\ell_1}&\le
e_1^{(1)}-1\\
L_2\le&\dots&q_{I-1}&q_I&\hdotsfor2&q_{\ell_1}&\le e_2^{(1)}
\end{array}.
\end{equation}
Recall that $L_1$ and $L_2$ are $a_1^{(\si(1))}+1$
and $a_2^{(\si(1))}$ or the other way round,
 depending on whether $\et_1=1$ or $\et=-1$. Let us, by convention,
set $p_0:=L_1-1$.
We say that $(q_I,q_I)$ is a
{\em crossing point of $P_1$ and $x=y$\/} if 
$I\ge0$ and $p_I<q_I$. Again it is understood that this inequality
only holds if both $p_I$ and $q_I$ are defined. In particular, this
means that in case $I=0$ the inequality only makes sense if 
the sequence $\dots p_0$ is empty (in which case the assignment
$p_0:=L_1-1$ applies). We say that
a family $\P=(P_1,P_2,\dots,P_n)$ is a {\em crossing family\/} 
if either there is a crossing
of neighbouring arrays or there is a crossing of $P_1$ and $x=y$.

Similarly to the proof of Theorem~\ref{T4.13} we shall show that in the sum
\eqref{e4.80} all contributions corresponding to triples $(\P,\si,\et)$ where
$\P$ is a crossing family of two-rowed arrays cancel by
constructing a weight-preserving (with respect to $w_{\x,\x}$), 
sign-reversing (with respect to $\sgn\et\,\sgn\si$) involution on those
triples. Finally we show that in a triple $(\P,\si,\et)$ with
$(\si,\et)\ne (\text
{id},(1,1,\dots,1))$ the family $\P$ must be crossing. This establishes that
only triples $(\P,\text {id},(1,1,\dots,1))$ where $\P$ is a non-crossing
family of two-rowed arrays contribute to the sum \eqref{e4.80}. But these
triples exactly correspond to the families of non-crossing paths under
consideration, hence Theorem~\ref{T4.14} would be proved.

Let $(\P,\si,\et)$ be a triple where $\P=(P_1,P_2,\dots,P_n)$ 
is a crossing family of two-rowed arrays. Consider all crossing points 
between neighbouring arrays and all crossing points of $P_1$ and $x=y$.
Among these points choose
those with maximal $x$-coordinate, and among all those choose the
crossing point with maximal $y$-coordinate. Denote this crossing
point by $M$. If $M$ is a crossing point between neighbouring arrays
let $i$ be minimal such that $M$ is a crossing point of $P_i$ and
$P_{i+1}$. Map $(\P,\si,\et)$ to $(\bar{\P},
\si\circ(i,i+1),\et^{(i,i+1)})$, where
$\et^{(i,i+1)}=(\et_1,\dots,\et_{i+1},\et_i,\dots,\et_n)$ and $\bar{
\P}=(\dots,\bar P_i,\bar P_{i+1},\dots)$ with $\bar P_i$ and $\bar P_{i+1}$
being constructed by \eqref{e4.76} and \eqref{e4.77}, 
respectively, as in the proof of
Theorem~\ref{T4.13}. Note that
$\sgn\et^{(i,i+1)}\,\sgn\big(\si\circ(i,i+1)\big)=-\sgn\et\,\sgn\si$ so that the map
indeed changes the sign of the corresponding terms in the generating
function \eqref{e4.80}.

 If $M$ is no crossing point between neighbouring arrays, then it has to
be a crossing point of $P_1$ and $x=y$. In this case
we map $(\P, \si,\et)$ to the triple $(\bar {\P},\si,\et^{(1)})$
where $\et^{(1)}=(-\et_1,\et_2,\dots,\et_n)$ and $\bar {\P}=(\bar
P_1,P_2,\dots,P_n)$ with $\bar P_1$ being constructed basically
according to the ``two-rowed arrays reflection'' \eqref{e4.11}. To be
precise, let $P_1$ be given by \eqref{e4.81} and 
let $I$ be the index such that $M=(q_I,q_I)$. 
Then $\bar P_1$ is defined by 
\begin{equation}\label{e4.82}
\begin{array} {rccccccl}
L_2\le&\hdotsfor2 &q_{I-1}&p_{I+1}&\dots&p_{\ell_1}&\le
e_1^{(1)}-1\\
L_1\le&\dots&p_I&q_I&\hdotsfor2&q_{\ell_1}&\le e_2^{(1)}
\end{array}.
\end{equation}
To check that this is well-defined we have to verify $q_{I-1}<p_{I+1}$.
In fact, if we assume $q_{I-1}\ge p_{I+1}$, we have
$p_{I+1}<q_{I+1}$ (because otherwise $p_{I+1}\ge
q_{I+1}>q_I>q_{I-1}$, which is a contradiction to our assumption).
But this means that $(q_{I+1},q_{I+1})$ is a crossing point of $P_1$
and $x=y$ with larger coordinates than $\Sch=(q_I,q_I)$, 
which contradicts the ``maximality" of $\Sch$. Also for being
well-defined, we have to check $L_1\le q_0$ in case that $I=0$ and
$\dots p_0$ is empty. But in this case the assignment $p_0:=L_1-1$
applies. And, since $I=0$ we have $p_0<q_0$. But this is exactly
equivalent to $L_1\le q_0$.

Next we note that 
the type of $\bar P_1$ is 
$-\et_1\si(1)+1-2=-\et_1\si(1)-1=\et_1^{(1)}\si(1)-1$.
Trivially, $\sgn\et^{(1)}=-\sgn\et$ so also this mapping changes the
sign of the corresponding terms in the generating function \eqref{e4.80}.
Therefore $(\bar {\P},\si,\et^{(1)})$ is indeed again a triple
under consideration for the generating function \eqref{e4.80}.

That $(q_I,q_I)$ is also a crossing point of $\bar P_1$ is obvious.
It is also maximal in the sense explained above since the entries to
the right of $p_{I+1}$ and $q_I$ were not changed. Therefore, applying the map
again to the triple $(\bar {\P},\si,\et^{(1)})$ gives $(\P,\si,\et)$.

Finally we have to show that if $(\si,\et)\ne (\text {id},(1,1,\dots,1))$
in the triple $(\P,\si,\et)$ the family $\P$ must be a crossing
family. Let $\et\ne (1,1,\dots,1)$. Let $i$ be minimal with
$\et_i=-1$. If $i=1$ then either there is an $I\ge 1$ with $p_I<q_I$,
i.e\@. a crossing of $P_1$ and $x=y$. Or for all $I\ge 1$ there holds
$p_I\ge q_I$. By \eqref{e4.60} and \eqref{e4.63} we have 
$q_0\ge L_2+\si(1)=a_1^{(\si(1))}+\si(1)\ge
a_1^{(1)}+1>a_2^{(1)}\ge a_2^{(\si(1))}=L_1-1=p_0$. Hence $(q_0,q_0)$ is
a crossing of $P_1$ and $x=y$. (Note that $q_{-1}$ and $q_0$ exist
since for $\et_1=-1$ the type of $P_1$ is $-\si(1)-1\le -2$.) 
Now suppose that $i\ge 2$. In addition
assume that there is no crossing point of neighbouring arrays. We
claim that again there must be a crossing point of $P_1$ and $x=y$. 
Because of $\et_i=-1$, $P_i$ is of the type $-\si(i)-i$. Let
$P_{i-1}=(\mathbf a\mid \mathbf b)$ and $P_i$ be
given by
$$\begin{array} {rcccccl}
a_2^{(\si(i))}+1\le&& &r_1&\dots&r_{\ell_i}&\le
e_1^{(i)}-1\\
a_1^{(\si(i))}\le&\dots&s_0&s_1&\dots&s_{\ell_i}&\le e_2^{(i)}
\end{array}.$$
By assumption $P_i$ and $P_{i-1}$ are non-crossing. Because $\dots
r_0$ is empty the assignment $r_0:=a_2^{(\si(i))}$ applies. By
\eqref{e4.60} there
hold the inequalities $s_0\ge a_1^{(\si(i))}+\si(i)+i-1\ge
a_1^{(1)}+1+i-1>a_2^{(1)}\ge a_2^{(\si(i))}=r_0$. Now let $j$ be
maximal with $p_j\le r_0$. Then there holds $r_0<p_{j+1}$. If 
$q_j<s_0$ then $(p_{j+1},s_0)$ would be a crossing point of $P_{i-1}$
and $P_i$ which contradicts our assumptions. Hence we have $p_j\le
r_0< s_0\le q_j$. The same argument is repeated with $P_{i-2}$ and
$P_{i-1}$, etc\@., until we arrive at $P_1$. Obviously, this gives us a
crossing point of $P_1$ and $x=y$, as was claimed.

If $\si\ne \text {id}$ and $\et=(1,1,\dots,1)$, the same arguments as
in the proof of Theorem~\ref{T4.13} apply to establish that there must be a
crossing of neighbouring arrays.
\end{proof}

\begin{proof}[Sketch of Proof of Theorem~\ref{T4.15}] 
Here we use the EN-turn representation of paths. 
For the combinatorial interpretation of the determinant \eqref{e4.67} we
consider triples 
$(\P,\si,\et)$, where $\si$ is a permutation in
$\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+1-\et_i$ and
the bounds of $P_i$ being given by 
{\refstepcounter{equation}\label{e4.83}}
\alphaeqn
\begin{equation}\label{e4.83a}
\begin{array} {rcl}
a_1^{(\si(i))}+1\le &\dots&\le e_1^{(i)}\\
a_2^{(\si(i))}\le &\dots&\le e_2^{(i)}-1\\
\end{array}, \text {\quad for $\et=1$,}
\end{equation}
respectively
\begin{equation}\label{e4.83b}
\begin{array} {rcl}
a_2^{(\si(i))}\le &\dots&\le e_1^{(i)}\\
a_1^{(\si(i))}+1\le &\dots&\le e_2^{(i)}-1\\
\end{array}, \text {\quad for $\et=-1$.}
\end{equation}
\reseteqn
It is easy to see that \eqref{e4.67} is the generating function 
\begin{equation}\label{e4.84}
\sum _{(\P,\si,\et)} ^{}\sgn\et\,\sgn\si\,w_{\x,\x}(\P)
\end{equation}
where the sum is over all triples
which were described above.

Since now we are considering EN-turns,
we have to redefine what we mean by a crossing of two-rowed
arrays and a crossing of a two-rowed array and $x=y$. 
Let $M_1$ and $M_2$ be two-rowed arrays, given by
$$M_1:\quad \quad 
\begin{array} {rcl}
a_1+1\le&\dots\ p_k&\le e_1\\
a_2\le&\dots\ q_k&\le e_2-1\end{array}$$
and
$$M_2:\quad \quad 
\begin{array} {rcl}
b_1+1\le&\dots\ r_l&\le f_1\\
b_2\le&\dots\ s_l&\le f_2-1\end{array},$$
respectively. 
By definition we set $s_{l+1}:=f_2$, we set $r_0:=b_1$
 in case that the sequence $\dots\ r_0$ is empty, and we set
$q_0:=a_2-1$ in case that the sequence $\dots\ q_0$ is empty.
We say that $(p_I,s_J)$ is a {\em crossing point\/} of
$M_1$ and $M_2$ if 
{\refstepcounter{equation}\label{e4.85}}
\alphaeqn
\begin{gather}  r_{J-1}<p_I\label{e4.85a}\\
q_{I}<s_J\label{e4.85b}
\end{gather}
and
\begin{equation}\label{e4.85c}
0\le I\le k,\quad  1\le J\le l+1.
\end{equation}
\reseteqn
To define crossings of a two-rowed array $M$ with $x=y$, let $M$ be
given by
$$\begin{array} {rccl}
L_1\le&\dots &p_{\ell_1}&\le
U_1\\
L_2\le&\dots &q_{\ell_1}&\le U_2
\end{array}.$$
By convention we set $q_{\ell_1+1}:=U_2+1$. The point $(q_{I+1},q_{I+1})$
is called a crossing point of $M$ and $x=y$ if $1\le I\le \ell_1+1$ and 
$p_I<q_{I+1}$. Note that if $M_1$, $M_2$, $M$ correspond to lattice
paths (by the EN-turn encoding) $P_1$, $P_2$, $P$, respectively,
 the first definition exactly is
equivalent to $P_1$ and $P_2$ having a crossing, 
while the second is equivalent to $P$ and
$x=y$ having a crossing.

The arguments are now completely analogous to those in the proof of Theorem~\ref{T4.14}. So
we shall not give all the details.
Again we construct a weight-preserving (with respect to $w_{\x,\x}$),
sign-reversing (with respect to $\sgn\et\,\sgn\si$) involution on
triples $(\P,\si,\et)$ where $\P$ is a crossing (in the new
sense) family. Also here we have to distinguish between two cases.
Either there is a crossing of neighbouring paths, $P_i$ and $P_{i+1}$
say. Or else their is a crossing of $P_1$ and $x=y$. In the first
case assume that $P_i$ is given by
$$\begin{array}{ccccc}
\dots&p_{I-1}&p_I&\hdotsfor2\\
\hdotsfor2&q_I&q_{I+1}&\dots
\end{array},$$
and $P_{i+1}$ be given by
$$\begin{array}{cccc}
\dots&r_{J-1}&r_J&\dots\\
\dots&s_{J-1}&s_J&\dots
\end{array}.$$
As in the proof of Theorem~\ref{T4.14} it is assumed that $M=(p_I,s_J)$ is a
``maximal" crossing point, and in particular a crossing point
of $P_i$ and $P_{i+1}$.
Then we map $(\P,\si,\et)$ to $(\bar {\P},\si\circ(i,i+1),\et^{(i,i+1)})$
where $\P=(P_1,\dots,\bar P_i,\bar P_{i+1},\dots,P_n)$ with $\bar P_i$
being given by
{\refstepcounter{equation}\label{e4.86}}
\alphaeqn
\begin{equation}\label{e4.86a}
\begin{array}{ccccc}
\dots&r_{J-1}&p_I&\hdotsfor2\\
\hdotsfor2&s_{J-1}&q_{I+1}&\dots
\end{array},
\end{equation}
and $\bar P_{i+1}$ being given by
\begin{equation}\label{e4.86b}
\begin{array}{cccc}
\dots&p_{I-1}&r_J&\dots\\
\dots&q_I&s_J&\dots
\end{array}.
\end{equation}
\reseteqn
In the second case let $P_1$ be given by
$$\begin{array}{cccc}
\dots&p_I&p_{I+1}&\dots \\
\dots&q_I&q_{I+1}&\dots
\end{array}.$$
Here we assume that $M=(q_{I+1},q_{I+1})$ is a ``maximal" crossing point of 
$P_1$ and $x=y$. Then we map 
$(\P,\si,\et)$ to $(\bar {\P},\si,\et^{(1)})$ where 
$\P=(\bar P_1,P_2,\dots,P_n)$ with $\bar P_1$ being given by
\begin{equation}\label{e4.87}
\begin{array}{cccc}
\dots&q_I&p_{I+1}&\dots \\
\dots&p_I&q_{I+1}&\dots
\end{array}.
\end{equation}

It can be shown that this mapping is a weight-preserving,
sign-reversing involution and that ``non-crossing triples" can only
occur for $(\si,\et)=(\text {id},(1,1,\dots,1))$. These exactly
correspond to the families of non-crossing paths under consideration.


\end{proof}
\begin{Remark} A special case of Theorem~\ref{T4.10}
is of relevance in the computation of Hilbert
polynomials of determinantal rings. This was shown by several
authors, \index{Conca, Aldo}Conca and \index{Herzog, J\"urgen}Herzog 
\cite{CoHeAA}, \index{Kulkarni, Devadatta M.}Kulkarni \cite{KulkAC}, and
\index{Modak, M. R.}Modak \cite{ModaAA}. In fact, \index{Kulkarni,
Devadatta M.}Kulkarni \cite[Main 
Theorem~5]{KulkAC}
derived this special case ($r=p$, $\ell=E$, $\mathcal
A\sb
i=(0,a\sb
{p-i+1})$, $E\sb
i=(m(2)-b\sb
{p-i+1},m(1))$) from \index{Abhyankar, Shreeram S.}Abhyankar's formula 
(Abhyankar \cite[(20.14.4),
p.~484]{AbhyAB}),
while \index{Conca, Aldo}Conca and \index{Herzog, J\"urgen}Herzog 
\cite{CoHeAA} used it to give an alternative
proof of \index{Abhyankar, Shreeram S.}Abhyankar's formula, see also 
\index{Krattenthaler, Christian}Krattenthaler \cite{KratAZ}. 
On the other hand, \index{Modak, M. R.}Modak \cite{ModaAA} gave an independent
(manipulative) proof of this special case. Slight variations of
Theorem~\ref{T4.10} solve the computation of Hilbert series for rings 
generated by minors of a symmetric matrix as considered by
\index{Conca, Aldo}Conca 
\cite{ConcAC}, see \index{Krattenthaler, Christian}Krattenthaler \cite{KratAZ}.
Theorem~\ref{T4.11} can be applied for the
computation of the Hilbert series for certain ladder determinantal rings
(one sided, with a diagonal upper bound) and
perhaps also for Pfaffian rings. On the other hand, \index{Modak, M. R.}Modak 
\cite{ModaAA} gave an independent
(manipulative) proof of this special case. Slight variations of
Theorem~1 solve the computation of Hilbert series for rings generated
by minors of a symmetric matrix as considered by \index{Conca, Aldo}Conca 
\cite{ConcAC}, see \index{Krattenthaler, Christian}Krattenthaler \cite{KratAZ}. 
For arbitrary one-sided ladders see \index{Krattenthaler, Christian}Krattenthaler 
\cite{KratAZ} and
\index{Krattenthaler, Christian}Krattenthaler and \index{Prohaska, Maria}Prohaska 
\cite{KrPrAA}.
Similar ideas should also give
answers for the Hilbert series of more general ladder determinantal
rings and symmetric ladders (cf\@. \index{Conca, Aldo}Conca \cite{ConcAC}). In particular,
the extension of the dummy path idea in \index{Krattenthaler, 
Christian}Krattenthaler and \index{Mohanty, Sri Gopal}Mohanty 
\cite{KrMoAA} should be
useful in this context.

\end{Remark}









%\end{document}
