%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_1B_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_Jc_{J+1}$. The inequality (26b) implies $b_0b_I$. The inequality (26a) implies $c_J\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))}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_0A_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