%This is an AmS-TeX file
%of a 17 pages paper

\input amstex
\input amsppt.sty

\def\StemAE{17}
\def\ModaAA{16}
\def\LindAA{15}
\def\KulkAC{14}
\def\KrMoAC{13}
\def\KrPrAA{12}
\def\KratAZ{11}
\def\KratAP{10}
\def\KaMGAC{9}
\def\HeTrAA{8}
\def\GeViAB{7}
\def\GeViAA{6}
\def\KulkAB{5}
\def\KrMoAA{4}
\def\CoHeAA{5}
\def\ConcAC{4}
\def\ComtAA{3}
\def\AbKuAC{2}
\def\AbhyAB{1}

\magnification1200
\hsize15.6truecm
\vsize22.8truecm
\catcode`\@=11
\font@\twelverm=cmr10 scaled\magstep1
\font@\twelveit=cmti10 scaled\magstep1
\font@\twelvebf=cmbx10 scaled\magstep1
\font@\twelvei=cmmi10 scaled\magstep1
\font@\twelvesy=cmsy10 scaled\magstep1
\font@\twelveex=cmex10 scaled\magstep1

\newtoks\twelvepoint@
\def\twelvepoint{\normalbaselineskip15\p@
 \abovedisplayskip15\p@ plus3.6\p@ minus10.8\p@
 \belowdisplayskip\abovedisplayskip
 \abovedisplayshortskip\z@ plus3.6\p@
 \belowdisplayshortskip8.4\p@ plus3.6\p@ minus4.8\p@
 \textonlyfont@\rm\twelverm \textonlyfont@\it\twelveit
 \textonlyfont@\sl\twelvesl \textonlyfont@\bf\twelvebf
 \textonlyfont@\smc\twelvesmc \textonlyfont@\tt\twelvett
%Ergnzung des fetten Small-Capitals-Fonts:
%
 \ifsyntax@ \def\big##1{{\hbox{$\left##1\right.$}}}%
  \let\Big\big \let\bigg\big \let\Bigg\big
 \else
  \textfont\z@=\twelverm  \scriptfont\z@=\tenrm  \scriptscriptfont\z@=\sevenrm
  \textfont\@ne=\twelvei  \scriptfont\@ne=\teni  \scriptscriptfont\@ne=\seveni
  \textfont\tw@=\twelvesy \scriptfont\tw@=\tensy \scriptscriptfont\tw@=\sevensy
  \textfont\thr@@=\twelveex \scriptfont\thr@@=\tenex
        \scriptscriptfont\thr@@=\tenex
  \textfont\itfam=\twelveit \scriptfont\itfam=\tenit
        \scriptscriptfont\itfam=\tenit
  \textfont\bffam=\twelvebf \scriptfont\bffam=\tenbf
        \scriptscriptfont\bffam=\sevenbf
  \setbox\strutbox\hbox{\vrule height10.2\p@ depth4.2\p@ width\z@}%
  \setbox\strutbox@\hbox{\lower.6\normallineskiplimit\vbox{%
        \kern-\normallineskiplimit\copy\strutbox}}%
 \setbox\z@\vbox{\hbox{$($}\kern\z@}\bigsize@=1.4\ht\z@
 \fi
 \normalbaselines\rm\ex@.2326ex\jot3.6\ex@\the\twelvepoint@}

\font@\fourteenrm=cmr10 scaled\magstep2
\font@\fourteenit=cmti10 scaled\magstep2
\font@\fourteensl=cmsl10 scaled\magstep2
\font@\fourteensmc=cmcsc10 scaled\magstep2
\font@\fourteentt=cmtt10 scaled\magstep2
\font@\fourteenbf=cmbx10 scaled\magstep2
\font@\fourteeni=cmmi10 scaled\magstep2
\font@\fourteensy=cmsy10 scaled\magstep2
\font@\fourteenex=cmex10 scaled\magstep2
\font@\fourteenmsa=msam10 scaled\magstep2
\font@\fourteeneufm=eufm10 scaled\magstep2
\font@\fourteenmsb=msbm10 scaled\magstep2
\newtoks\fourteenpoint@
\def\fourteenpoint{\normalbaselineskip15\p@
 \abovedisplayskip18\p@ plus4.3\p@ minus12.9\p@
 \belowdisplayskip\abovedisplayskip
 \abovedisplayshortskip\z@ plus4.3\p@
 \belowdisplayshortskip10.1\p@ plus4.3\p@ minus5.8\p@
 \textonlyfont@\rm\fourteenrm \textonlyfont@\it\fourteenit
 \textonlyfont@\sl\fourteensl \textonlyfont@\bf\fourteenbf
 \textonlyfont@\smc\fourteensmc \textonlyfont@\tt\fourteentt
%Ergnzung des fetten Small-Capitals-Fonts:
%
 \ifsyntax@ \def\big##1{{\hbox{$\left##1\right.$}}}%
  \let\Big\big \let\bigg\big \let\Bigg\big
 \else
  \textfont\z@=\fourteenrm  \scriptfont\z@=\twelverm  \scriptscriptfont\z@=\tenrm
  \textfont\@ne=\fourteeni  \scriptfont\@ne=\twelvei  \scriptscriptfont\@ne=\teni
  \textfont\tw@=\fourteensy \scriptfont\tw@=\twelvesy \scriptscriptfont\tw@=\tensy
  \textfont\thr@@=\fourteenex \scriptfont\thr@@=\twelveex
        \scriptscriptfont\thr@@=\twelveex
  \textfont\itfam=\fourteenit \scriptfont\itfam=\twelveit
        \scriptscriptfont\itfam=\twelveit
  \textfont\bffam=\fourteenbf \scriptfont\bffam=\twelvebf
        \scriptscriptfont\bffam=\tenbf
  \setbox\strutbox\hbox{\vrule height12.2\p@ depth5\p@ width\z@}%
  \setbox\strutbox@\hbox{\lower.72\normallineskiplimit\vbox{%
        \kern-\normallineskiplimit\copy\strutbox}}%
 \setbox\z@\vbox{\hbox{$($}\kern\z@}\bigsize@=1.7\ht\z@
 \fi
 \normalbaselines\rm\ex@.2326ex\jot4.3\ex@\the\fourteenpoint@}

\font@\seventeenrm=cmr10 scaled\magstep3
\font@\seventeenit=cmti10 scaled\magstep3
\font@\seventeensl=cmsl10 scaled\magstep3
\font@\seventeensmc=cmcsc10 scaled\magstep3
\font@\seventeentt=cmtt10 scaled\magstep3
\font@\seventeenbf=cmbx10 scaled\magstep3
\font@\seventeeni=cmmi10 scaled\magstep3
\font@\seventeensy=cmsy10 scaled\magstep3
\font@\seventeenex=cmex10 scaled\magstep3
\font@\seventeenmsa=msam10 scaled\magstep3
\font@\seventeeneufm=eufm10 scaled\magstep3
\font@\seventeenmsb=msbm10 scaled\magstep3
\newtoks\seventeenpoint@
\def\seventeenpoint{\normalbaselineskip18\p@
 \abovedisplayskip21.6\p@ plus5.2\p@ minus15.4\p@
 \belowdisplayskip\abovedisplayskip
 \abovedisplayshortskip\z@ plus5.2\p@
 \belowdisplayshortskip12.1\p@ plus5.2\p@ minus7\p@
 \textonlyfont@\rm\seventeenrm \textonlyfont@\it\seventeenit
 \textonlyfont@\sl\seventeensl \textonlyfont@\bf\seventeenbf
 \textonlyfont@\smc\seventeensmc \textonlyfont@\tt\seventeentt
%Ergnzung des fetten Small-Capitals-Fonts:
%
 \ifsyntax@ \def\big##1{{\hbox{$\left##1\right.$}}}%
  \let\Big\big \let\bigg\big \let\Bigg\big
 \else
  \textfont\z@=\seventeenrm  \scriptfont\z@=\fourteenrm  \scriptscriptfont\z@=\twelverm
  \textfont\@ne=\seventeeni  \scriptfont\@ne=\fourteeni  \scriptscriptfont\@ne=\twelvei
  \textfont\tw@=\seventeensy \scriptfont\tw@=\fourteensy \scriptscriptfont\tw@=\twelvesy
  \textfont\thr@@=\seventeenex \scriptfont\thr@@=\fourteenex
        \scriptscriptfont\thr@@=\fourteenex
  \textfont\itfam=\seventeenit \scriptfont\itfam=\fourteenit
        \scriptscriptfont\itfam=\fourteenit
  \textfont\bffam=\seventeenbf \scriptfont\bffam=\fourteenbf
        \scriptscriptfont\bffam=\twelvebf
  \setbox\strutbox\hbox{\vrule height14.6\p@ depth6\p@ width\z@}%
  \setbox\strutbox@\hbox{\lower.86\normallineskiplimit\vbox{%
        \kern-\normallineskiplimit\copy\strutbox}}%
 \setbox\z@\vbox{\hbox{$($}\kern\z@}\bigsize@=2\ht\z@
 \fi
 \normalbaselines\rm\ex@.2326ex\jot5.2\ex@\the\seventeenpoint@}

\catcode`\@=13



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Input-Datei zum Erzeugen von Gitterpunktwegen.%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Pfad-Eingabe: 
%  \Pfad(x-Koordinate des Anf.Punkts,y-Koordinate des Anf.Punkts),Pfad
%  als 1-2-Wort\endPfad
%(1=Schritt in x-Richtung, 2=Schritt in y-Richtung)
%
%Koordinatenachsen:
%  \Koordinatenachsen(L\"ange der x-Achse, L\"ange der y-Achse)
%
%Gitter:
%  \Gitter(Anzahl der Punkte in x-Richtung, Anzahl der Punkte in x-Richtung)
%
%Bezeichnung von Punkten:
%  \Label[wo?]{[Bezeichnung]}(x-Koordinate,y-Koordinate)
%wobei:
%  [wo?]=\l,\lo,\lu,\r,\ro,\ru,\o,\u
%und l=links, r=rechts, u=unten, o=oben.
%
%Die Einheit kann durch Eingabe von
%  \Einheit=?cm
%ver\"andert werden.
%
%Die Dicke der Pfade kann durch Eingabe von
%     \PfadDicke{?cm}
%ver\"andert werden.
%
%Es stehen die folgenden Punktgr\"o\3en zur Verf\"ugung:
%\DuennPunkt, \NormalPunkt, \DickPunkt. Eingabe:
%  \DickPunkt(x-Koordinate,y-Koordinate), etc.
%
%Weiters steht mit \Kreis ein Kreis zur Verf\"ugung. Eingabe:
%  \Kreis(x-Koordinate,y-Koordinate)
%
\catcode`\@=11
\newskip\Einheit \Einheit=0.5cm
\newcount\xcoord \newcount\ycoord
\newdimen\xdim \newdimen\ydim \newdimen\PfadD@cke \newdimen\Pfadd@cke
\PfadD@cke1pt \Pfadd@cke0.5pt
\def\PfadDicke#1{\PfadD@cke#1 \divide\PfadD@cke by2 \Pfadd@cke\PfadD@cke \multiply\PfadD@cke by2}
\long\def\LOOP#1\REPEAT{\def\BODY{#1}\ITERATE}
\def\ITERATE{\BODY \let\next\ITERATE \else\let\next\relax\fi \next}
\let\REPEAT=\fi
\def\Punkt{\hbox{\raise-2pt\hbox to0pt{\hss$\ssize\bullet$\hss}}}
\def\DuennPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-2.5pt\hbox to0pt{\hss$\bullet$\hss}\hss}}
\def\NormalPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-3pt\hbox to0pt{\hss\twelvepoint$\bullet$\hss}\hss}}
\def\DickPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\fourteenpoint$\bullet$\hss}\hss}}
\def\Kreis(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\fourteenpoint$\circ$\hss}\hss}}
\def\Pfad(#1,#2),#3\endPfad{\unskip\leavevmode
  \xcoord#1 \ycoord#2 \ZeichnePfad#3\endPfad}
\def\ZeichnePfad#1{\ifx#1\endPfad\let\next\relax
  \else\let\next\ZeichnePfad
    \ifnum#1=1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \vrule height\Pfadd@cke width1 \Einheit depth\Pfadd@cke\hss}%
      \advance\xcoord by 1
    \else
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-1pt\vrule height1 \Einheit width\PfadD@cke depth0pt}\hss}%
      \advance\ycoord by 1
    \fi
  \fi\next}
\def\Koordinatenachsen(#1,#2){\unskip
 \hbox to0pt{\hskip-.5pt\vrule height#2 \Einheit width.5pt depth1 \Einheit}%
 \hbox to0pt{\hskip-1 \Einheit \xcoord#1 \advance\xcoord by1
    \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}}
\def\Koordinatenachsen(#1,#2)(#3,#4){\unskip
 \hbox to0pt{\hskip-.5pt \ycoord-#4 \advance\ycoord by1
    \vrule height#2 \Einheit width.5pt depth\ycoord \Einheit}%
 \hbox to0pt{\hskip-1 \Einheit \hskip#3\Einheit 
    \xcoord#1 \advance\xcoord by1 \advance\xcoord by-#3 
    \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}}
\def\Gitter(#1,#2){\unskip \xcoord0 \ycoord0 \leavevmode
  \LOOP\ifnum\ycoord<#2
    \loop\ifnum\xcoord<#1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}%
      \advance\xcoord by1
    \repeat
    \xcoord0
    \advance\ycoord by1
  \REPEAT}
\def\Gitter(#1,#2)(#3,#4){\unskip \xcoord#3 \ycoord#4 \leavevmode
  \LOOP\ifnum\ycoord<#2
    \loop\ifnum\xcoord<#1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}%
      \advance\xcoord by1
    \repeat
    \xcoord#3
    \advance\ycoord by1
  \REPEAT}
\def\Label#1#2(#3,#4){\unskip \xdim#3 \Einheit \ydim#4 \Einheit
  \def\lo{\advance\xdim by-.5 \Einheit \advance\ydim by.5 \Einheit}%
  \def\o{\advance\ydim by.5 \Einheit}%
  \def\ro{\advance\xdim by.5 \Einheit \advance\ydim by.5 \Einheit}%
  \def\l{\advance\xdim by-.5 \Einheit}%
  \def\r{\advance\xdim by.5 \Einheit}%
  \def\lu{\advance\xdim by-.5 \Einheit \advance\ydim by-.5 \Einheit}%
  \def\u{\advance\ydim by-.5 \Einheit}%
  \def\ru{\advance\xdim by.5 \Einheit \advance\ydim by-.5 \Einheit}%
  #1\raise\ydim\hbox to0pt{\hskip\xdim
     \vbox to0pt{\vss\hbox to0pt{\hss$#2$\hss}\vss}\hss}%
}
\catcode`\@=13


\TagsOnRight

\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\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}}

\topmatter 
\title Counting nonintersecting lattice paths with turns 
\endtitle 
\author C.~Krattenthaler\footnote"$^\dagger$"{Supported in part by EC's Human
Capital and Mobility Program, grant CHRX-CT93-0400 and the\linebreak 
\hbox{Austrian Science Foundation FWF, grant P10191-PHY}}
\endauthor 
\affil 
Institut f\"ur Mathematik der Universit\"at Wien,\\
Strudlhofgasse 4, A-1090 Wien, Austria.\\
e-mail: KRATT\@Pap.Univie.Ac.At
\endaffil
\address Institut f\"ur Mathematik der Universit\"at Wien,
Strudlhofgasse 4, A-1090 Wien, Austria.
\endaddress
%\email KRATT\@Pap.Univie.Ac.At\endemail
%\dedicatory \enddedicatory
%\date \enddate
%\thanks \endthanks
\subjclass Primary 05A15;
 Secondary 05A19, 13C40.
\endsubjclass
\keywords Nonintersecting lattice paths, turns, non-crossing two-rowed arrays,
determinantal rings, pfaffian rings, Hilbert series
\endkeywords
\abstract We derive enumeration formulas for families of
nonintersecting lattice paths with given starting and end points and
a given total number of North-East turns. These formulas are important for
the computation of Hilbert series for determinantal and pfaffian
rings.
\endabstract
\endtopmatter
\document
\rightheadtext{Nonintersecting lattice paths with turns}
\leftheadtext{C. Krattenthaler}

\subhead 1. Introduction\endsubhead
Recent work of Abhyankar and Kulkarni \cite{\AbhyAB, \AbKuAC} and of
Conca, Herzog and Trung \cite{\ConcAC, \CoHeAA, \HeTrAA} showed that
the computation of Hilbert series for determinantal and pfaffian
rings boils down to counting families of $n$ nonintersecting lattice
paths with given starting and end points and a given total number of turns
in certain regions. 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}). 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 new methods are needed now.

In this note we develop the basic theory of turn enumeration of
nonintersecting lattice paths. Theorem~1 solves the turn enumeration of
(unrestricted) nonintersecting lattice paths with given starting and end
points, Theorem~4 provides a generalization. 
Theorem~2 solves the turn enumeration of
nonintersecting lattice paths that stay below a diagonal line 
with given starting and end
points, Theorem~5 provides a generalization.
Finally, Theorem~3 solves a problem that is equivalent to the turn 
enumeration of
nonintersecting lattice paths that stay above a diagonal line 
with given starting and end
points, Theorem~6 provides a generalization.
We also briefly
indicate how these theorems are related to the computation of Hilbert
series for determinantal and pfaffian rings.

What concerns the proofs of these results,
it turns out that lattice paths are not the right objects to play
with. The objects that are natural in the context of turn enumeration
are {\it two-rowed arrays\/}. To prove the determinant formulas we
construct operations on two-rowed arrays (the operations (24)/(25)
$\to$ (28)/(29), (37a)/(37b) $\to$ (38a)/(38b), (32) $\to$ (33), 
(39) $\to$ (40)) that are in some sense analogous to the
Gessel--Viennot involution for paths and the reflection principle for
paths. These operations are inspired by operations from
\cite{\KratAP, \KrMoAC}.

A full account of this theory will be the subject of forthcoming
papers \cite{\KratAZ, \KrPrAA}. In particular, these papers contain
more enumeration results concerning nonintersecting lattice paths
with a given total number of turns. Besides, the impact of our
results to the theory of determinantal and pfaffian rings is
explained in detail there. Also, more general enumeration results for
non-crossing two-rowed arrays are presented there that lead to
summation theorems for Schur functions. An interesting feature is
that it is the Robinson--Schensted--Knuth correspondence and its
properties that constitute the link between ``turn enumeration" of
nonintersecting lattice paths and the above mentioned applications.

The paper is organized as follows. In the next section we explain our
terminology and state our results (Theorems~1--6). Then, in section~3, we
provide the proofs of Theorems~4--6. Theorems~1--3 follow as special
cases.

\subhead 2. The results\endsubhead
We consider lattice paths in the plane 
consisting of unit horizontal and vertical steps
in the positive direction. In the sequel we shall call them shortly
{\it paths}.
Let $P$ be a path from
$\A =( A_1, A_2)$ to $\E =(E_1,E_2)
$. Later we frequently abbreviate the fact that a path $P$ goes from
$\A$ to $\E$ by $P:\A\to\E$.

\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_0}(3,3)
\hskip4cm
$$
\nobreak
\centerline{\eightpoint Figure 1}
}
\vskip10pt
A point in a path $P$ which is the end point of a vertical
step and at the same time
 the starting point of a horizontal step will be called
a {\it North-East turn} ({\it NE-turn} for short) of the path $P$. 
The NE-turns of
the path in Figure~1 are $(1,1)$, $(2,3)$, and $(5,4)$. Similarly, 
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 will be called
an {\it East-North turn} ({\it EN-turn} for short) of the path $P$. 
The EN-turns of the
path in Figure~1 are $(2,1)$, $(5,3)$, and $(6,4)$.

The aim of this note is to prove the following three theorems about
the enumeration of nonintersecting lattice paths with a given total number of
turns. Here, as usual, paths are called nonintersecting if no two of
them have a point in common.
\proclaim{Theorem 1} Let 
$\Cal A_i=(A_1^{(i)},A_2^{(i)})$ and $\Cal E_i=(E_1^{(i)},E_2^{(i)})$ be lattice points satisfying
$$A_1^{(1)}\le A_1^{(2)}\le\dotsb\le A_1^{(r)},\quad
A_2^{(1)}>A_2^{(2)}>\dotsb>A_2^{(r)},$$
and
$$E_1^{(1)}< E_1^{(2)}<\dotsb< E_1^{(r)},\quad
E_2^{(1)}\ge E_2^{(2)}\ge \dotsb\ge E_2^{(r)}.$$
The number of all families $\Cal P=(P_1,\dots,P_r)$ of nonintersecting lattice paths $P_i:\Cal A_i\to\Cal E_i$,
such that the paths of $\Cal P$ altogether contain exactly $K$ NE-turns, is
$$\sum _{k_1+\dotsb+k_r=K} ^{}\det_{1\le s,t\le r}
\bigg(\binom{E_1^{(t)}-A_1^{(s)}+s-t}{k_s+s-t}
\binom{E_2^{(t)}-A_2^{(s)}-s+t}{k_s}\bigg).\quad \quad \qed\tag1$$
\endproclaim

\remark{Remark} A special case of Theorem~1
is of relevance in the computation of Hilbert
series for determinantal rings. This was shown by several
authors \cite{\CoHeAA, \KulkAC, \ModaAA}. In fact, Kulkarni \cite{\KulkAC,
Main Theorem~5}
derived this special case ($r=p$, $K=E$, $\Cal
A\sb
i=(0,a\sb
{p-i+1})$, $\Cal E\sb
i=(m(2)-b\sb
{p-i+1},m(1))$) from Abhyankar's formula \cite{\AbhyAB,
(20.14.4), p.~484} for the Hilbert series for certain determinantal
rings,
while Conca and Herzog \cite{\CoHeAA} used it to give an alternative
proof of Abhyankar's formula, see also \cite{\KratAZ}. 
On the other hand, 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 Conca
\cite{\ConcAC}, see \cite{\KratAZ}.
\endremark
\proclaim{Theorem 2}Let $\Cal A_i=(A_1^{(i)},A_2^{(i)})$ and
$\Cal E_i=(E_1^{(i)},E_2^{(i)})$ be lattice points satisfying
$$A_1^{(1)}\le A_1^{(2)}\le\dotsb\le A_1^{(r)},\quad
A_2^{(1)}>A_2^{(2)}>\dotsb>A_2^{(r)},$$
$$
E_1^{(1)}< E_1^{(2)}<\dotsb< E_1^{(r)},\quad
E_2^{(1)}\ge E_2^{(2)}\ge \dotsb\ge E_2^{(r)},$$
and
$A_1^{(i)}\ge A_2^{(i)},\quad E_1^{(i)}\ge E_2^{(i)},\quad
i=1,\dots,r.$
The number of all families $\Cal P=(P_1,\dots,P_r)$ of nonintersecting lattice paths $P_i:\Cal A_i\to\Cal E_i$, which do not cross the line $x=y$, and where the paths of
$\Cal P$ altogether
contain exactly $K$ NE-turns, is
$$\multline
\sum _{k_1+\dotsb+k_r=K} ^{}\det_{1\le s,t\le r}
\bigg(\binom{E_1^{(t)}-A_1^{(s)}+s-t}{k_s+s-t}
\binom{E_2^{(t)}-A_2^{(s)}-s+t}{k_s}\\
-\binom{E_1^{(t)}-A_2^{(s)}-s-t+1}{k_s-t}
\binom{E_2^{(t)}-A_1^{(s)}+s+t-1}{k_s+s}\bigg).\quad \quad \qed
\endmultline\tag2$$
\endproclaim


\remark{Remark} Theorem~2 can be applied for the
computation of the Hilbert series for certain ladder determinantal
rings
(one sided, with a diagonal upper bound) and
also for pfaffian rings, see \cite{\KratAZ}. 
For arbitrary one-sided ladders see \cite{\KratAZ, \KrPrAA}.
\endremark
\proclaim{Theorem 3}Let $\Cal A_i=(A_1^{(i)},A_2^{(i)})$ and 
$\Cal E_i=(E_1^{(i)},E_2^{(i)})$ be lattice points satisfying 
$$A_1^{(1)}< A_1^{(2)}<\dotsb< A_1^{(r)},\quad
A_2^{(1)}\ge A_2^{(2)}\ge \dotsb\ge A_2^{(r)},$$
$$
E_1^{(1)}\le  E_1^{(2)}\le \dotsb\le  E_1^{(r)},\quad
E_2^{(1)}> E_2^{(2)}> \dotsb> E_2^{(r)},$$
and
$A_1^{(i)}\ge  A_2^{(i)},\quad E_1^{(i)}\ge  E_2^{(i)},\quad
i=1,\dots,r.$
The number of all families $\Cal P=(P_1,\dots,P_r)$ of nonintersecting lattice paths $P_i:\Cal A_i\to\Cal E_i$, $P_i:\Cal A_i\to\Cal E_i$, which do not cross the line $x=y$, and where the paths of
$\Cal P$ altogether
contain exactly $K$ EN-turns, is
$$\multline
\sum _{k_1+\dotsb+k_r=K} ^{}\det_{1\le  s,t\le  r}
\bigg(\binom{E_1^{(t)}-A_1^{(s)}+s-t}{k_s+s-t}
\binom{E_2^{(t)}-A_2^{(s)}-s+t}{k_s}\\
-\binom{E_1^{(t)}-A_2^{(s)}-s-t+3}{k_s-t+1}
\binom{E_2^{(t)}-A_1^{(s)}+s+t-3}{k_s+s-1}\bigg).\quad \quad \qed
\endmultline\tag3$$
\endproclaim
Actually, more general results can be shown (see Theorems~4,5,6
below). However, they are more
conveniently formulated after before having modified the problem.

Suppose, $\Cal P=(P_1,\dots,P_r)$ is a family of nonintersecting lattice 
paths $P_i:\Cal A_i\to\Cal 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,\dots,r$. The new family $\Cal P'=(P'_1,\dots,P'_r)$ might be
intersecting, however it is {\it non-crossing} (see Figure~2). 
\vskip10pt 
\vbox{\noindent
$$\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{\eightpoint \hskip1cm\raise0cm\hbox{nonintersecting lattice
paths}\hskip2cm 
\raise0cm\hbox{non-crossing lattice paths}}
\nobreak
\centerline{\eightpoint Figure 2}
}
\vskip10pt
Before we make precise what
the exact meaning of non-crossing in this context is (see 
(10) below), we introduce some notation.

Obviously, given the starting and the final point
of a path, the North-East turns uniquely determine the path.
Suppose that $P$ is a path from $\A=(A_1,A_2)$ to $\E=(E_1,E_2)$ and
let the North-East turns of $P$ be $(a_1,b_1)$, $(a_2,b_2)$, \dots,
$(a_k,b_k)$, where we assume that the $(a_i,b_i)$ are ordered from
left to right, which is equivalent with $A_1\le a_1<a_2<\dots<a_k\le E_1-1$, and
$A_2+1\le b_1<b_2<\dots<b_k\le E_2$. Then $P$
can be represented by the two-rowed array
$$\matrix\format\c&\c&\c&\c\\ a_1&\ a_2&\ \dots&\ a_k\\
b_1&\ b_2&\ \dots&\ b_k\endmatrix\ ,\tag4$$
or, if we wish to make the bounds which are caused by the starting
and the final point transparent,
$$\matrix\format\r\quad &\c&\c&\c&\c&\quad \l\\
 A_1\le&a_1&\ a_2&\ \dots&\ a_k&\le E_1-1\\
A_2+1\le& b_1&\ b_2&\ \dots&\ b_k&\le E_2\endmatrix\ .\tag5$$
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 North-East turn.
For the path in Figure~1
we obtain the array representation
$$\matrix 1\ 2\ 5\\1\ 3\ 4\endmatrix\ ,$$
or with bounds included,
$$\matrix\format\r\quad &\c&\c&\c&\quad \l\\
 1\le&1&\ 2&\ 5&\le5\\0\le&1&\ 3&\ 4&\le6\endmatrix\ .$$

Later, also two-rowed arrays with 
rows of unequal length will be considered. But these arrays also will
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. 
We shall frequently use the short notation $(a\mid b)$ for two-rowed
arrays, where $a$
denotes the sequence $(a_i)$ of elements of the first row, 
and $b$ denotes the
sequence $(b_i)$ of elements of the second row.

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 mean 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
$$P_1:\quad \matrix \format\r\quad &\c\quad &\c\quad &\c\quad &\l\\
A_1\le&a_1&\hdots&a_k&\le E_1-1\\
A_2+1\le&b_1&\hdots&b_k&\le E_2\endmatrix\hphantom{\ ,}\tag6$$
and
$$P_2:\quad \matrix \format\r\quad &\c\quad &\c\quad &\c\quad &\l\\
B_1\le&c_1&\hdots&c_l&\le F_1-1\\
B_2+1\le&d_1&\hdots&d_l&\le F_2\endmatrix\ ,\tag7$$
respectively. 

Suppose that $P_1$ and $P_2$ intersect, i.e\. have a point in common.
Let $\S$ be a meeting point of $P_1$ and $P_2$.
By definition set $a_{k+1}:=E_1$ and $b_0:=A_2$.
(Note that the thereby augmented sequences $a$ and $b $
remain strictly increasing.)

\vskip10pt 
\vbox{\noindent
$$
\Pfad(0,0),221111121111\endPfad
\Pfad(-2,-1),11112222221111\endPfad
\DickPunkt(0,2)
\DickPunkt(2,2)
\DickPunkt(2,-1)
\Label\ru{\S}(2,2)
\Label\lo{\hskip-10pt(c_J,d_J)}(0,2)
\Label\ru{(a_I,b_{I-1})}(2,-1)
\Label\r{P_1}(6,5)
\Label\r{P_2}(9,3)
\hskip4cm
$$
\nobreak
\centerline{\eightpoint Figure 3}
}
\vskip10pt
Considering the East-North turn $(a_I,b_{I-1})$ in $P_1$
immediately preceding $\S$ (and being allowed to be equal to $\S$)
and the North-East turn $(c_J,d_J)$ in $P_2$ immediately preceding
$\S$ (and being allowed to be equal to $\S$), we get the inequalities
(cf\. Figure~3)
$$\gather c_J\le a_I,\tag8a\\
 b_{I-1}\le
d_J,\tag8b
\endgather$$
where
$$1\le I\le k+1,\quad 1\le J\le l.\tag8c$$

Of course, $k,l,a_I,b_I,c_J,d_J$, etc., refer to the array representations
of $P_1$ and $P_2$. It now becomes apparent that 
the above assignments for $a_{k+1}$ and $b_0$ are needed
for the inequalities (8a,b) to make sense for $I=1$ or $I=k+1$.
Note that $S=(a_I,d_J)$. Vice versa, if (8a,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 (8a,b,c) characterize the array representations of
{\it intersecting} pairs of paths. 

Now, if $P_2$ is shifted in direction $(-1,1)$, we obtain the path
$P_2'$ with array representation 
$$\matrix \format\r\quad &\c\quad &\c\quad &\c\quad &\l\\
B'_1\le&c'_1&\hdots&c'_l&\le F'_1-1\\
B'_2+1\le&d'_1&\hdots&d'_l&\le F'_2\endmatrix\ ,\tag9$$
where $c'_i=c_i-1$, $d'_i=d_i+1$, $B'_1=B_1-1$, $B'_2=B_2+1$,
$F'_1=F_1-1$, $F'_2=F_2+1$.
The conditions (8a,b,c) become
$$\gather c'_J< a_I,\tag10a\\
 b_{I-1}<
d'_J,\tag10b
\endgather$$
where
$$1\le I\le k+1,\quad 1\le J\le l.\tag10c$$
We take (10a,b,c) as definition of two paths $P_1$ and $P_2$ with
array representations (6) and (9), respectively, being non-crossing.
We call the point $(a_I,d'_J)$ {\it crossing point} of $P_1$ and $P_2$.

Let $\bold x=(x_1,x_2,\dots)$ and $\bold y=(y_1,y_2,\dots)$ be
sequences of indeterminates.
Given a path $P_1$ with array representation (6) we define a {\it
weight} for $P_1$ by 
$$w_{\bold x,\bold y}(P_1)=\prod _{i=1} ^{k}x_{a_i} y_{b_i}.\tag11$$
This weight is extended to families $\Cal P=(P_1,\dots,P_r)$ of lattice paths
by 
$$w_{\bold x,\bold y}(\Cal P)=\prod _{j=1}^{r}w_{\bold x,\bold y}( P_j).\tag12$$


Now we are prepared to formulate the promised generalizations of
Theorems~1,2,3.
\proclaim{Theorem 4}Let $\Cal A_i=(A_1^{(i)},A_2^{(i)})$ and $\Cal E_i=(E_1^{(i)},E_2^{(i)})$ be lattice points satisfying
$$
A_1^{(1)}+1\le A_1^{(2)}+2\le\dotsb\le A_1^{(r)}+r,\quad
A_2^{(1)}\ge A_2^{(2)}\ge \dotsb\ge A_2^{(r)},\tag13$$
and
$$E_1^{(1)}\le E_1^{(2)}\le \dotsb\le E_1^{(r)},\quad
E_2^{(1)}-1\ge E_2^{(2)}-2\ge \dotsb\ge E_2^{(r)}-r.\tag14$$
The generating function $\sum _{\Cal P} w_{\bold x,\bold y}(\Cal P)$ 
where the sum is over all families $\Cal P=(P_1,\dots,\mathbreak P_r)$ of non-crossing lattice paths $P_i:\Cal A_i\to\Cal E_i$,
is
$$\det_{1\le s,t\le
r}(f_{s-t}(\x,A_1^{(s)},E_1^{(t)}-1,\y,A_2^{(s)}+1,E_2^{(t)})),\tag15$$
where $f_m(\x,a,b,\y,c,d)=\sum _{k} ^{}
e_{k+m}(x_a,\dots,x_b)e_k(y_c,\dots,y_d)$ with $e_n(z_1,\dots,z_h)$
denoting the elementary symmetric function in the variables
$z_1,\dots,z_h$.
\endproclaim
\proclaim{Theorem 5}Let $\Cal A_i=(A_1^{(i)},A_2^{(i)})$ and $\Cal E_i=(E_1^{(i)},E_2^{(i)})$ 
be lattice points satisfying (13) and (14)
and 
$$A_1^{(1)}\ge A_2^{(1)}\quad \text {and}\quad E_1^{(1)}\ge
E_2^{(1)}.\tag16$$
The generating function $\sum _{\Cal P} w_{\bold x,\bold x}(\Cal P)$ 
where the sum is over all families $\Cal P=(P_1,\dots,\mathbreak P_r)$ of non-crossing lattice paths 
$P_i:\Cal A_i\to\Cal E_i$, 
such that $P_1$ does not cross the line $x=y$,
is
$$\multline
\det_{1\le s,t\le
r}(f_{s-t}(\x,A_1^{(s)},E_1^{(t)}-1,\x,A_2^{(s)}+1,E_2^{(t)})\\-
f_{-s-t}(\x,A_2^{(s)}+1,E_1^{(t)}-1,\x,A_1^{(s)},E_2^{(t)})).
\endmultline\tag17$$
\endproclaim
\proclaim{Theorem 6}Let $\Cal A_i=(A_1^{(i)},A_2^{(i)})$ and $\Cal E_i=(E_1^{(i)},E_2^{(i)})$ 
be lattice points satisfying 
$$\gather
A_1^{(1)}\le A_1^{(2)}\le\dotsb\le A_1^{(r)},\quad
A_2^{(1)}-1\ge A_2^{(2)}-2\ge \dotsb\ge A_2^{(r)}-r,\tag18\\
E_1^{(1)}+1\le E_1^{(2)}+2\le \dotsb\le E_1^{(r)}+r,\quad
E_2^{(1)}\ge E_2^{(2)}\ge \dotsb\ge E_2^{(r)},\tag19
\endgather$$
and (16).
The generating function $\sum _{\Cal P} w_{\bold x,\bold x}(\Cal P)$ 
where the sum is over all families $\Cal P=(P_1,\dots,P_r)$ of non-crossing lattice paths $P_i:\Cal A_i\to\Cal E_i$,
such that $P_1$ does not cross the line $x=y$,
is
$$\multline
\det_{1\le s,t\le
r}(f_{s-t}(\x,A_1^{(s)}+1,E_1^{(t)},\x,A_2^{(s)},E_2^{(t)}-1)
\\-f_{-s-t+2}(\x,A_2^{(s)},E_1^{(t)},\x,A_1^{(s)}+1,E_2^{(t)}-1)).
\endmultline\tag20$$
\endproclaim
Clearly, Theorems~1,2,3 result from Theorems~4,5,6, respectively, 
by ``unshifting",
i.e\. by replacing $A_1^{(i)}$ by $A_1^{(i)}-i+1$, $A_2^{(i)}$ by
$A_2^{(i)}+i-1$, etc\., setting $x_i=y_i=z$ and extracting the
coefficient of $z^{2K}$ in (15), (17), and (20), respectively.

\subhead 3. The proofs\endsubhead
\demo{Proof of Theorem 4} 
In the proof we are also considering {\it skew} two-rowed arrays. 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\ &&\c\ \\
 a_{-j+1}&a_{-j+2}&\dots&a_{-1}&a_0&a_1&\dots&a_k\\
&&&&&b_1&\dots&b_k\endmatrix$$
for some $k\ge0$. We say that $P$ {\it is of the type} $-j$ if $P$ has
the form
$$\matrix\format\c\ &&\c\ \\
&&&&&a_1&\dots&a_k\\
 b_{-j+1}&b_{-j+2}&\dots&b_{-1}&b_0&b_1&\dots&b_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$.
 We extend the weight function $w_{\x,\y}$ to skew
arrays in the obvious way,
$$w_{\x,\y}(P)=\prod _{i} ^{}x_{a_i}\prod _{j} ^{}y_{b_j}.$$

First we give the combinatorial interpretation of the determinant (15)
in terms of two-rowed arrays. It is easy to see that (15) is the
generating function
$$\sum _{(\Cal P,\si)} ^{}\sgn\si\, w_{\x,\y}(\Cal P),\tag21$$
where the sum is over all pairs $(\Cal P, \si)$ of permutations $\si$
in $\frak S_r$, the symmetric group of order $r$, and families $\Cal
P=(P_1,\dots,P_r)$ 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))}\le&\dots\ a_{k_i}^{(i)}&\le E_1^{(i)}-1\\
A_2^{(\si(i))}+1\le&\dots\ b_{k_i}^{(i)}&\le E_2^{(i)}
\endmatrix,\tag22$$
$i=1,\dots,r$.

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
(21) all contributions corresponding to pairs $(\Cal P,\si)$, where
$\Cal 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 $(\Cal P,\si)$ with $\si\ne \text
{id}$ the family $\Cal P$ must be crossing. This establishes that
only pairs $(\Cal P,\text {id})$ where $\Cal P$ is a non-crossing
family of two-rowed arrays contribute to the sum (21). But these
pairs exactly correspond to the families of non-crossing paths under
consideration, hence Theorem~4 would be proved.

\medskip
Let $M_1$ and $M_2$ be two-rowed arrays, given by
$$M_1:\quad \quad 
\matrix \format\r&\quad \c\quad &\l\\
A_1\le&\dots\ a_k&\le E_1-1\\
A_2+1\le&\dots\ b_k&\le E_2\endmatrix$$
and
$$M_2:\quad \quad 
\matrix \format\r&\quad \c\quad &\l\\
B_1\le&\dots\ c_l&\le F_1-1\\
B_2+1\le&\dots\ d_l&\le F_2\endmatrix,$$
respectively. 
By definition we set $a_{k+1}:=E_1$, we set $b_0:=A_2$
 in case that the sequence $\dots\ b_0$ is empty, and we set $c_0:=B_1-1$
in case that the sequence $\dots\ c_0$ is empty.
We say that $(a_I,d_J)$ is a {\it crossing point} of
$M_1$ and $M_2$ if 
$$\gather  c_J<a_I\tag23a\\
b_{I-1}<d_J\tag23b
\endgather$$
and
$$1\le I\le k+1,\quad  0\le J\le l.\tag23c$$
These inequalities should be understood to hold only if all variables
are defined. In particular, if the sequence $\dots\ d_0$ is empty the
inequality (23b) does not make sense for $J=0$. However, if the sequence $\dots
\ c_0$ is empty the inequality (23a) makes sense because of the
conventional assignment for $c_0$ above.
\medskip

Let $(\Cal P,\si)$ be a pair under consideration for the sum (21). 
Besides, we assume that $\Cal 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 {\it
neighbouring} two-rowed arrays. A pair $(\Cal P,\si)$ where $\Cal P$
contains neighbouring
two-rowed arrays with a crossing point will be called {\it crossing}.
Otherwise it will be called {\it 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 $(\Cal 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 $S$. Let $i$ be minimal such that $S$ is a crossing point of
$P_i$ and $P_{i+1}$. Let $P_i=(a\mid b)=(\dots a_{k_i}\mid \dots
b_{k_i})$ and $P_{i+1}=(c\mid d)=(\dots c_{k_{i+1}}\mid \dots
d_{k_{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 (22). By (23), $S$ being a
crossing 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\ &\c\ &\c\ &\c\ &\c\quad &\l\\
 A_1^{(\si(i))} \le&\dots&a_{I-1}&a_I&\dots&a_{k_i}&\le E_1^{(i)}-1\\
 A_2^{(\si(i))}+1 \le&\dots&b_{I-1}&b_I&\dots&b_{k_i}&\le E_2^{(i)}
\endmatrix,\tag24$$
$P_{i+1}$ looks like
$$\matrix\format\r&\quad \c&\ \c&\ \c&\ \c&\ \c&\ \c\quad &\l\\
 A_1^{(\si(i+1))} \le&\innerhdotsfor2\after\quad 
&c_{J}&c_{J+1}&\dots&c_{k_{i+1}}&\le E_1^{(i+1)}-1\\
 A_2^{(\si(i+1))}+1 \le&\dots&d_{J-1}&d_J&\innerhdotsfor2\after\
&d_{k_{i+1}}&\le E_2^{(i+1)}
\endmatrix,\tag25$$
$S=(a_I,d_J)$, 
$$\gather  c_J<a_I\tag26a\\
b_{I-1}<d_J\tag26b
\endgather$$
and
$$1\le I\le k_i+1,\quad  0\le J\le k_{i+1}.\tag26c$$
Because of the construction of $S$ the indices $I$ {\it and} $J$ are
maximal with respect to (26a,b,c).

We map $(\Cal P,\si)$ to the pair $(\bar{\Cal P},\si\circ(i,i+1))$
($(i,i+1)$
denotes the transposition exchanging $i$ and $i+1$), where $\bar{\Cal
P}=(P_1,\dots,P_{i-1},\bar P_i,\bar P_{i+1},P_{i+2},\dots,P_r)$ with
$\bar P_i$ being given by
$$\matrix \format\c\ &&\c\ \\
\dots&c_J&a_I&\dots&a_{k_i}\\
\dots&d_{J-1}&b_I&\dots&b_{k_i}\endmatrix,\tag27a$$
$\bar P_{i+1}$ being given by
$$\matrix \format\c &&\ \c\\
\innerhdotsfor2\after\ &a_{I-1}&c_{J+1}&\dots&c_{k_{i+1}}\\
\dots&b_{I-1}&d_J&\innerhdotsfor2\after\
&d_{k_{i+1}}\endmatrix.\tag27b$$
First of all, this operation is well-defined, i.e., all the rows in
(27a) and (27b) are strictly increasing. To see this we have to check
$c_J<a_I$, $d_{J-1}<b_I$, $a_{I-1}<c_{J+1}$, and $b_{I-1}<d_J$. This
is obvious for the first and last inequality, because of (26a) and
(26b). As for the second inequality, let us suppose $d_{J-1}\ge b_I$.
Then, by (26a), we have $c_J<a_{I}<a_{I+1}$ and $b_I\le d_{J-1}<d_J$. 
This means
that $(a_{I+1},d_J)$ is a crossing point of $P_i$ and $P_{i+1}$, with
an $x$-coordinate larger than that of $\S=(a_I,d_J)$, contradicting
the ``maximality" of $\S$. Similarly, if we assume $a_{I-1}\ge
c_{J+1}$, we have $c_{J+1}\le a_{I-1}<a_I$ and, by (26b),
$b_{I-1}<d_J<d_{J+1}$. This means
that $(a_{I},d_{J+1})$ is a crossing point of $P_i$ and $P_{i+1}$, with
a $y$-coordinate larger than that of $\S=(a_I,d_J)$, again contradicting
the ``maximality" of $\S$.

We claim that $(\bar{\Cal P},\si\circ(i,i+1))$ is again a pair under
consideration for the generating function (21). 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\ &\c\ &\c\ &\c\ &\c\quad &\l\\
A_1^{(\si(i+1))}\le&\dots&c_J&a_I&\dots&a_{k_i}&\le E_1^{(i)}-1\\
A_2^{(\si(i+1))}+1\le&\dots&d_{J-1}&b_I&\dots&b_{k_i}&\le E_2^{(i)}\endmatrix,\tag28$$
 and that those for $\bar P_{i+1}$ are given by
$$\matrix \format\r&\quad \c&\ \c&\ \c&\ \c&\ \c&\ \c\quad &\l\\
A_1^{(\si(i))}\le&\innerhdotsfor2\after\quad 
&a_{I-1}&c_{J+1}&\dots&c_{k_{i+1}}&\le E_1^{(i+1)}-1\\
A_2^{(\si(i))}+1\le&\dots&b_{I-1}&d_J&\innerhdotsfor2\after\
&d_{k_{i+1}}&\le E_2^{(i+1)}\endmatrix.\tag29$$
The claims concerning the types of $\bar P_i$ and $\bar P_{i+1}$ are
trivial. Therefore let us consider the bounds. We distinguish between
several cases.
\roster
\item"(a)" If $2\le I\le k_i$ and $2\le J\le k_{i+1}-1$ there is no
problem, since then the sequences $\dots a_{I-1}$, $a_I\dots a_{k_i}$,
$\dots b_{I-1}$, $b_I\dots b_{k_i}$, $\dots c_{J}$, $c_{J+1}\dots
c_{k_{i+1}}$,
$\dots d_{J-1}$, $d_J\dots d_{k_{i+1}}$ are all nonempty and therefore
the constraints in (28) and (29) obviously hold.
\item"(b)" If $I=1$ and the sequence $\dots a_{0}$ is empty we have to
prove $c_{J+1}\ge A_1^{(\si(i))}$. Suppose $a_1>c_{J+1}$. The
inequality (26b) implies
$b_0<d_J<d_{J+1}$ therefore the point $(a_1,d_{J+1})$ would also be a crossing
point of $P_i$ and $P_{i+1}$ which violates the maximality of $J$ with
respect to (26a,b,c). Hence, by (24) we have $c_{J+1}\ge a_1\ge
A_1^{(\si(i))}$.
\item"(c)" If $I=1$ and the sequence $\dots b_{0}$ is empty we have to
prove $d_{J}\ge A_2^{(\si(i))}+1$. In this case the assignment
$b_0:=A_2^{(\si(i))}$ applies. Because of (26b) we have
$A_2^{(\si(i))}=b_0<d_J$.
\item"(d)" If $J=0$ and the sequence $\dots c_{0}$ is empty we have to
prove $a_{I}\ge A_1^{(\si(i+1))}$. In this case the assignment
$c_0:=A_1^{(\si(i+1))}-1$ applies. Because of (26a) we have
$A_1^{(\si(i+1))}-1=c_0<a_I$.
\item"(e)" If $J=1$ and the sequence $\dots d_{0}$ is nonempty nothing has
to be proved.
\item"(f)" If $J=1$ and the sequence $\dots d_{0}$ is empty we have to
prove $b_{I}\ge A_2^{(\si(i+1))}+1$. Suppose $d_1>b_I$. The
inequality (26a) implies $c_J<a_I<a_{I+1}$ therefore the point
$(a_{I+1},d_J)$ would also be a crossing point of $P_i$ and $P_{i+1}$
which violates the maximality of $I$ with respect to (26a,b,c).
Hence, by (25) we have $b_I\ge d_1\ge A_2^{(\si(i+1))}+1$.
\item"(g)" If $I=k_{i}+1$ we have to
prove $c_{J}\le E_1^{(i)}-1$ and $d_{J-1}\le E_2^{(i)}$. In this case
the assignment $a_{k_i+1}:=E_1^{(i)}$ applies. By (26a) we have
$c_J<a_{k_i+1}=E_1^{(i)}$. By (25) and 
(14), we have $d_{J-1}<d_J\le
E_2^{(i+1)}\le E_2^{(i)}+1$. 
\item"(h)" If $J=k_{i+1}$ we have to
prove $a_{I-1}\le E_1^{(i+1)}-1$. By (24) and 
(14) we have $a_{I-1}\le
E_1^{(i)}-1\le E_1^{(i+1)}-1$.
\endroster
Obviously the map (27) is weight-preserving with respect to
$w_{\x,\y}$ and reverses the signs of the associated permutations.

Next we claim that the map (27) is an involution. To establish this claim
it suffices to show that $S$ is also a crossing point of $\bar P_i$
and $\bar P_{i+1}$, and also maximal in the sense explained
above. 
Once this is shown it easily seen that an application of our
mapping (27) to $(\bar{\Cal P},\si\circ(i,i+1))$ gives $(\Cal P,\si)$ again.
Suppose that $\bar P_i=(\bar a\mid \bar b)=(\dots \bar a_{\bar k_i}\mid \dots
\bar b_{\bar k_i})$ and $\bar P_{i+1}=(\bar c\mid \bar d)=
(\dots \bar c_{\bar k_{i+1}}\mid \dots
\bar d_{\bar k_{i+1}})$.
Let $\bar I$ and $\bar J$ be chosen such that $\bar a_{\bar I}=a_I$
and $\bar d_{\bar J}=d_J$ (compare with (27)). Then we have $\bar
b_{\bar I-1}=d_{J-1}$ and $\bar c_{\bar J}=a_{I-1}$. Because of
$a_{I-1}<a_I$ and $d_{J-1}<d_J$ we conclude $\bar c_{\bar J}<\bar
a_{\bar I}$ and $\bar b_{\bar I-1}<\bar d_{\bar J}$. By (23) this is
equivalent to saying that $(\bar a_{\bar I},\bar d_{\bar
J})=(a_I,d_J)=S$ is a crossing point of $\bar P_i$ and $\bar
P_{i+1}$. (These arguments also hold in the ``degenerate" cases
$I=1$, $J=0,1$, etc\.) That $S$ is also maximal for $\bar {\Cal P}$
follows from the fact that when applying the map (27) to $P_i$ and
$P_{i+1}$ nothing was changed to the right of $a_I$, $b_I$, $d_J$,
and $c_{J+1}$.

Finally we have to show that, given a pair $(\Cal P,\si)$, $\Cal
P=(P_1,\dots,P_r)$, 
$\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=(a\mid b)=(\dots a_{k_i}\mid \dots
b_{k_i})$ and $P_{i+1}=(c\mid d)=(\dots c_{k_{i+1}}\mid \dots
d_{k_{i+1}})$. Because of $\si(i)-i\ge0$ the sequence $\dots b_0$ is
empty, hence the assignment $b_0:=A_2^{(\si(i))}$ applies. Because of
$\si(i+1)-i-1<0$ the sequence $\dots c_0$ is empty, hence the
assignment $c_0:=A_1^{(\si(i+1))}-1$ applies. Because of
$\si(i)>\si(i+1)$ and (13) the inequalities
$c_0=A_1^{(\si(i+1))}-1\le A_1^{(\si(i))}<a_1$ and
$b_0=A_2^{(\si(i))}\le A_2^{(\si(i+1))}<d_0$ hold. By (23) 
this means that $(a_1,d_0)$ is a crossing point of $P_i$ and
$P_{i+1}$.\quad \quad \qed

\enddemo

\remark{Remark} The operation (24)/(25) $\to$ (28)/(29) that is the
backbone of the preceding proof and is an analogue of the
Gessel--Viennot involution in the context of two-rowed arrays 
is inspired by \cite{\KratAP, operation (5.3.6)/(5.3.10)}.
\endremark

\demo{Proof of Theorem 5} 
Again we work with families of two-rowed arrays. This time we
consider triples $(\Cal P,\si,\et)$, where $\si$ is a permutation in
$\frak S_r$, $\et\in \{-1,1\}^r$, and $\Cal P=(P_1,\dots,P_r)$ 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))}\le &\dots&\le E_1^{(i)}-1\\
A_2^{(\si(i))}+1\le &\dots&\le E_2^{(i)}\\
\endmatrix, \text {\quad for $\et=1$,}\tag30a$$
respectively
$$\matrix \format\r&\quad \c\quad &\l\\
A_2^{(\si(i))}+1\le &\dots&\le E_1^{(i)}-1\\
A_1^{(\si(i))}\le &\dots&\le E_2^{(i)}\\
\endmatrix, \text {\quad for $\et=-1$.}\tag30b$$
Define $\sgn\et:=\prod _{i=1} ^{r}\et_i$.
It is easy to see that (17) is the generating function 
$$\sum _{(\Cal
P,\si,\et)} ^{}\sgn\et\,\sgn\si\,w_{\x,\x}(\Cal P)\tag31$$ 
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=(a\mid b)$, or with bounds included
$$\matrix \format\r&\quad \c&\ \c&\ \c&\ \c&\ \c&\ \c\quad &\l\\
L_1\le&\innerhdotsfor2\after\quad &a_{I}&a_{I+1}&\dots&a_{k_1}&\le
E_1^{(1)}-1\\
L_2\le&\dots&b_{I-1}&b_I&\innerhdotsfor2\after\ &b_{k_1}&\le E_2^{(1)}
\endmatrix.\tag32$$
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 $a_0:=L_1-1$.
We say that $(b_I,b_I)$ is a
{\it crossing point of $P_1$ and $x=y$} if 
$I\ge0$ and $a_I<b_I$. Again it is understood that this inequality
only holds if both $a_I$ and $b_I$ are defined. In particular, this
means that in case $I=0$ the inequality only makes sense if 
the sequence $\dots a_0$ is empty (in which case the assignment
$a_0:=L_1-1$ applies).
We say that
a family $\Cal P=(P_1,\dots,P_r)$ is a {\it crossing family\/} if either their is a crossing
of neighbouring arrays or their is a crossing of $P_1$ and $x=y$.

Similarly to the proof of Theorem~4 we shall show that in the sum
(31) all contributions corresponding to triples $(\Cal P,\si,\et)$ where
$\Cal 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 $(\Cal P,\si,\et)$ with
$(\si,\et)\ne (\text
{id},(1,1,\dots,1))$ the family $\Cal P$ must be crossing. This establishes that
only triples $(\Cal P,\text {id},(1,1,\dots,1))$ where $\Cal P$ is a non-crossing
family of two-rowed arrays contribute to the sum (31). But these
triples exactly correspond to the families of non-crossing paths under
consideration, hence Theorem~5 would be proved.

Let $(\Cal P,\si,\et)$ be a triple where $\Cal P=(P_1,\dots,P_r)$ 
is a crossing family of two-rowed arrays. Consider all crossing points 
of 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 $S$. If $S$ is a crossing point of neighbouring arrays
let $i$ be minimal such that $S$ is a crossing point of $P_i$ and
$P_{i+1}$. Map $(\Cal P,\si,\et)$ to $(\bar{\Cal 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_r)$ and $\bar{\Cal
P}=(\dots,\bar P_i,\bar P_{i+1},\dots)$ with $\bar P_i$ and $\bar P_{i+1}$
being constructed by (28) and (29), respectively, as in the proof of
Theorem~4. 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 (31).

 If $S$ is no crossing point of neighbouring arrays, then it has to
be a crossing point of $P_1$ and $x=y$. In this case
we map $(\Cal P, \si,\et)$ to the triple $(\bar {\Cal P},\si,\et^{(1)})$
where $\et^{(1)}=(-\et_1,\et_2,\dots,\et_r)$ and $\bar {\Cal P}=(\bar
P_1,P_2,\dots,P_r)$ with $\bar P_1$ being constructed as follows.
Let $P_1$ be given by
(32) and let $I$ be the index such that $S=(b_I,b_I)$. 
Then $\bar P_1$ is defined by
$$\matrix \format\r&\quad \c&\ \c&\ \c&\ \c&\ \c&\ \c\quad &\l\\
L_2\le&\innerhdotsfor2\after\quad &b_{I-1}&a_{I+1}&\dots&a_{k_1}&\le
E_1^{(1)}-1\\
L_1\le&\dots&a_I&b_I&\innerhdotsfor2\after\ &b_{k_1}&\le E_2^{(1)}
\endmatrix.\tag33$$
To check that this is well-defined we have to verify $b_{I-1}<a_{I+1}$.
In fact, if we assume $b_{I-1}\ge a_{I+1}$, we have
$a_{I+1}<b_{I+1}$ (because otherwise $a_{I+1}\ge
b_{I+1}>b_I>b_{I-1}$, which is a contradiction to our assumption).
But this means that $(b_{I+1},b_{I+1})$ is a crossing point of $P_1$
and $x=y$ with larger coordinates than $\S=(b_I,b_I)$, 
which contradicts the ``maximality" of $\S$. Also for being
well-defined, we have to check $L_1\le b_0$ in case that $I=0$ and
$\dots a_0$ is empty. But in this case the assignment $a_0:=L_1-1$
applies. And, since $I=0$ we have $a_0<b_0$. But this is exactly
equivalent to $L_1\le b_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 (31).
Therefore $(\bar {\Cal P},\si,\et^{(1)})$ is indeed again a triple
under consideration for the generating function (31).

That $(b_I,b_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 $a_{I+1}$ and $b_I$ were not changed. Therefore, applying the map
again to the triple $(\bar {\Cal P},\si,\et^{(1)})$ gives $(\Cal
P,\si,\et)$.

Finally we have to show that if $(\si,\et)\ne (\text {id},(1,1,\dots,1))$
in the triple $(\Cal P,\si,\et)$ the family $\Cal 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 $a_I<b_I$,
i.e\. a crossing of $P_1$ and $x=y$. Or for all $I\ge 1$ there holds
$a_I\ge b_I$. 
By (13) and (16) we have $b_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=a_0$. Hence $(b_0,b_0)$ is
a crossing of $P_1$ and $x=y$. (Note that $b_{-1}$ and $b_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}=(a\mid b)$ and $P_i$ be
given by
$$\matrix \format\r&\quad \c&\ \c&\ \c&\ \c&\ \c\quad &\l\\
A_2^{(\si(i))}+1\le&& &c_1&\dots&c_{k_i}&\le
E_1^{(i)}-1\\
A_1^{(\si(i))}\le&\dots&d_0&d_1&\dots&d_{k_i}&\le E_2^{(i)}
\endmatrix.$$
By assumption $P_i$ and $P_{i-1}$ are non-crossing. Because $\dots
c_0$ is empty the assignment $c_0:=A_2^{(\si(i))}$ applies. By (13) there
hold the inequalities $d_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))}=c_0$. Now let $j$ be
maximal with $a_j\le c_0$. Then there holds $c_0<a_{j+1}$. If 
$b_j<d_0$ then $(a_{j+1},d_0)$ would be a crossing point of $P_{i-1}$
and $P_i$ which contradicts our assumptions. Hence we have $a_j\le
c_0< d_0\le b_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~4 apply to establish that there must be a
crossing of neighbouring arrays.\quad \quad \qed

\enddemo

\remark{Remark} The operation (32) $\to $ (33) that is an analogue
of the reflection principle (see e.g\. \cite{\ComtAA, p.~22}) 
for two-rowed arrays is inspired by
\cite{\KrMoAC, (2.12); \KratAP, (5.2.4)}.
\endremark
\demo{Sketch of Proof of Theorem~6} 
Here we encode paths by their EN-turns. For example the two-rowed
array representation of the path in Figure~1 would be
$$\matrix 2\ 5\ 6\\1\ 3\ 4\endmatrix\ ,$$
or with bounds included,
$$\matrix\format\r\quad &\c&\c&\c&\quad \l\\
 2\le&2&\ 5&\ 6&\le6\\-1\le&1&\ 3&\ 4&\le5\endmatrix\ .$$
For the combinatorial interpretation of the determinant (20) we
consider triples 
$(\Cal P,\si,\et)$, where $\si$ is a permutation in
$\frak S_r$, $\et\in \{-1,1\}^r$, and $\Cal P=(P_1,\dots,P_r)$ 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 
$$\matrix \format\r&\quad \c\quad &\l\\
A_1^{(\si(i))}+1\le &\dots&\le E_1^{(i)}\\
A_2^{(\si(i))}\le &\dots&\le E_2^{(i)}-1\\
\endmatrix, \text {\quad for $\et=1$,}\tag34a$$
respectively
$$\matrix \format\r&\quad \c\quad &\l\\
A_2^{(\si(i))}\le &\dots&\le E_1^{(i)}\\
A_1^{(\si(i))}+1\le &\dots&\le E_2^{(i)}-1\\
\endmatrix, \text {\quad for $\et=-1$.}\tag34b$$
It is easy to see that (20) is the generating function 
$$\sum _{(\Cal
P,\si,\et)} ^{}\sgn\et\,\sgn\si\,w_{\x,\x}(\Cal P)\tag35$$ 
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 
\matrix \format\r&\quad \c\quad &\l\\
A_1+1\le&\dots\ a_k&\le E_1\\
A_2\le&\dots\ b_k&\le E_2-1\endmatrix$$
and
$$M_2:\quad \quad 
\matrix \format\r&\quad \c\quad &\l\\
B_1+1\le&\dots\ c_l&\le F_1\\
B_2\le&\dots\ d_l&\le F_2-1\endmatrix,$$
respectively. 
By definition we set $d_{l+1}:=F_2$, we set $c_0:=B_1$
 in case that the sequence $\dots\ c_0$ is empty, and we set
$b_0:=A_2-1$ in case that the sequence $\dots\ b_0$ is empty.
We say that $(a_I,d_J)$ is a {\it crossing point} of
$M_1$ and $M_2$ if 
$$\gather  c_{J-1}<a_I\tag36a\\
b_{I}<d_J\tag36b
\endgather$$
and
$$0\le I\le k,\quad  1\le J\le l+1.\tag36c$$
To define crossings of a two-rowed array $M$ with $x=y$, let $M$ be
given by
$$\matrix \format\r&\quad \c&\ \c\quad &\l\\
L_1\le&\dots &a_{k_1}&\le
U_1\\
L_2\le&\dots &b_{k_1}&\le U_2
\endmatrix.$$
By convention we set $b_{k_1+1}:=U_2+1$. The point $(b_{I+1},b_{I+1})$
is called a crossing point of $M$ and $x=y$ if $1\le I\le k_1+1$ and 
$a_I<b_{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~5. 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 $(\Cal P,\si,\et)$ where $\Cal 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
$$\matrix\format\c&&\ \c\\
\dots&a_{I-1}&a_I&\innerhdotsfor2\after\ \\
\hdotsfor2&b_I&b_{I+1}&\dots
\endmatrix,\tag37a$$
and $P_{i+1}$ be given by
$$\matrix\format\c&&\ \c\\
\dots&c_{J-1}&c_J&\dots\\
\dots&d_{J-1}&d_J&\dots
\endmatrix.\tag37b$$
As in the proof of Theorem~5 it is assumed that $S=(a_I,d_J)$ is a
``maximal" crossing point, and in particular a crossing point
of $P_i$ and $P_{i+1}$.
Then we map $(\Cal P,\si,\et)$ to $(\bar {\Cal P},\si\circ(i,i+1),\et^{(i,i+1)})$
where $\Cal P=(P_1,\dots,\bar P_i,\bar P_{i+1},\dots,P_r)$ with $\bar P_i$
being given by
$$\matrix\format\c&&\ \c\\
\dots&c_{J-1}&a_I&\innerhdotsfor2\after\ \\
\hdotsfor2&d_{J-1}&b_{I+1}&\dots
\endmatrix,\tag38a$$
and $\bar P_{i+1}$ being given by
$$\matrix\format\c&&\ \c\\
\dots&a_{I-1}&c_J&\dots\\
\dots&b_I&d_J&\dots
\endmatrix.\tag38b$$
In the second case let $P_1$ be given by
$$\matrix\format\c&&\ \c\\
\dots&a_I&a_{I+1}&\dots \\
\dots&b_I&b_{I+1}&\dots
\endmatrix.\tag39$$
Here we assume that $S=(b_{I+1},b_{I+1})$ is a ``maximal" crossing point of 
$P_1$ and $x=y$. Then we map 
$(\Cal P,\si,\et)$ to $(\bar {\Cal P},\si,\et^{(1)})$ where $\Cal
P=(\bar P_1,P_2,\dots,P_r)$ with $\bar P_1$ being given by
$$\matrix\format\c&&\ \c\\
\dots&b_I&a_{I+1}&\dots \\
\dots&a_I&b_{I+1}&\dots
\endmatrix.\tag40$$

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.
\quad \quad \qed
\enddemo

\remark{Remark} The operation (37a)/(37b) $\to$ (38a)/(38b) 
that is another analogue of the
Gessel--Viennot involution in the context of two-rowed arrays 
is again inspired by 
\cite{\KratAP, operation (5.3.6)/(5.3.10)}. (In fact, it is a simple
translation of the operation (24)/(25) $\to$ (28)/(29)). The
operation (39) $\to$ (40) that is another analogue
of the reflection principle (see e.g\. \cite{\ComtAA, p.~22}) 
for two-rowed arrays is inspired by
\cite{\KrMoAC, (2.11); \KratAP, (5.2.24)}.


\endremark



\Refs

\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 \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 \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 \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 \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 \KratAP\by C.    Krattenthaler 
\paper The major counting of nonintersecting lattice paths and generating functions for tableaux
\jour to appear in Mem\. Amer\. Math\. Soc\. \endref

\ref\no \KratAZ\by C.    Krattenthaler \paper Non-crossing two-rowed arrays
\jour in preparation\endref  

\ref\no \KrPrAA\by C.    Krattenthaler and M. Prohaska \yr 19?? 
\paper A remarkable formula for counting nonintersecting lattice paths in a ladder with respect to turns
\paperinfo in preparation\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 \KulkAC\by D. M. Kulkarni 
\paper Counting of paths and coefficients of Hilbert polynomial of a determinantal ideal
\jour preprint \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 \StemAE\by J. R. Stembridge \yr 1990 
\paper Nonintersecting paths, pfaffians and plane partitions
\jour Adv\. in Math\.\vol 83
\pages 96---131\endref

\endRefs
\enddocument
