%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Input-Datei zum Erzeugen von Gitterpunktwegen.%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%LaTeX-Version%
%%%%%%%%%%%%%%%
%entering a path: 
%  \Pfad(x-coordinate of starting point,y-coordinate of final %point),path
%  as 1-2-word\endPfad
%(1=step in x-direction, 2=step in y-direction)
%
%coordinate-axes:
%  \Koordinatenachsen(length of positive x-axes, length of positive %y-axes)(length of negative x-axes, length of negative y-axes)
%
%lattice:
%  \Gitter(number of points in positive x-direction, number of points %in positive y-direction)(number of points in negative x-direction, %number of points in negative y-direction)
%
%labelling of points:
%  \Label[wo?]{[label]}(x-coordinate,y-coordinate)
%where:
%  [location?]=\l,\lo,\lu,\r,\ro,\ru,\o,\u
%and l=left, r=right, u=bottom, o=top.
%In addition, if by \Einheit?cm the basic unit is changed, there exist
%\llo,\loo,\llu,\luu,\rro,\roo,\rru,\ruu.
%
%The basic unit can be changed by entering
%  \Einheit=?cm
%
%The thickness of the paths can be changed by entering
%     \PfadDicke{?cm}
%
%The following point sizes are available:
%\DuennPunkt, \NormalPunkt, \DickPunkt. Syntax:
%  \DickPunkt(x-coordinate,y-coordinate), etc.
%
%Besides, a circle is available by \Kreis. Syntax:
%  \Kreis(x-coordinate,y-coordinate)
%
%\pagestyle{empty}
\catcode`\@=11
\newskip\Einheit \Einheit=0.6cm
\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\scriptsize$\bullet$\hss}}}
\def\DuennPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-2.5pt\hbox to0pt{\hss\normalsize$\bullet$\hss}\hss}}
\def\NormalPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-3pt\hbox to0pt{\hss\large$\bullet$\hss}\hss}}
\def\DickPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\Large$\bullet$\hss}\hss}}
\def\Kreis(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\Large$\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\llo{\advance\xdim by-.25cm \advance\ydim by.5 \Einheit}%
  \def\loo{\advance\xdim by-.5 \Einheit \advance\ydim by.25cm}%
  \def\o{\advance\ydim by.25cm}%
  \def\ro{\advance\xdim by.5 \Einheit \advance\ydim by.5 \Einheit}%
  \def\rro{\advance\xdim by.25cm \advance\ydim by.5 \Einheit}%
  \def\roo{\advance\xdim by.5 \Einheit \advance\ydim by.25cm}%
  \def\l{\advance\xdim by-.30cm}%
  \def\r{\advance\xdim by.30cm}%
  \def\lu{\advance\xdim by-.5 \Einheit \advance\ydim by-.6 \Einheit}%
  \def\llu{\advance\xdim by-.25cm \advance\ydim by-.6 \Einheit}%
  \def\luu{\advance\xdim by-.5 \Einheit \advance\ydim by-.30cm}%
  \def\u{\advance\ydim by-.30cm}%
  \def\ru{\advance\xdim by.5 \Einheit \advance\ydim by-.6 \Einheit}%
  \def\rru{\advance\xdim by.25cm \advance\ydim by-.6 \Einheit}%
  \def\ruu{\advance\xdim by.5 \Einheit \advance\ydim by-.30cm}%
  #1\raise\ydim\hbox to0pt{\hskip\xdim
     \vbox to0pt{\vss\hbox to0pt{\hss$#2$\hss}\vss}\hss}%
}
\catcode`\@=12


\documentstyle[fullpages,12pt]{amsart}

%\pagestyle{empty}

\renewcommand{\baselinestretch}{1.4}

\def\qbinomial#1#2{\left[\begin{array}{c}#1\\#2\end{array}\right]}
\newtheorem{ItoQ}{Lemma}
\newtheorem{QtoI}[ItoQ]{Lemma}
\newtheorem{inverses}[ItoQ]{Lemma}
\newtheorem{GA}[ItoQ]{Lemma}
\newtheorem{GC}[ItoQ]{Lemma}


\title[]{Counting Pairs of Nonintersecting Lattice Paths with 
Respect to
Weighted Turns}   

\author[]{  {  Christian Krattenthaler}}
 \address{{   Institut f\"{u}r Mathematik,}  
{     Universit\"{a}t Wien,}           
   {   Strudlhofgasse 4, }              
{   A-1090 Wien, Austria }     }      
\email{{    KRATT@@pap.univie.ac.at } }
\author[]{{  Robert A. Sulanke}}             
\address{{    Department of Mathematics,} 
 {    Boise State University,}       
   {    Boise, Idaho 83725 USA} }   
\email{{    sulanke@@math.idbsu.edu}     }

 

\begin{document}

\maketitle

\begin{abstract}
A  formula involving a difference of the products of four {\em q}-binomial coefficients is shown to count  pairs of nonintersecting lattice paths having a 
prescribed number of weighted turns.   The weights are assigned to account for the 
location of the turns according to the 
major and lesser indices.  
The result, which is a $q$-analogue of a variant of the formula of Kreweras and 
Poupard, is proved bijectively; however, when $q \neq 1$ 
the bijection is defined inductively.
\end{abstract}

\section{Introduction} 

In the coordinate plane consider lattice paths  with 
positively directed vertical and horizontal unit steps. If $0$ denotes a 
vertical step and  $1$ denotes a horizontal step, a 0-1-sequence will determine 
a path since it will always be clear where a given path starts. In any path a 
consecutive $10$ is a {\em left-hand turn}, and a consecutive $01$ is a {\em 
right-hand turn}. Define the {\em major} (or {\em greater}) {\em index} and the 
{\em lesser index} of any path $\pi$, where $\pi = \pi_1\pi_2 \cdots \pi_n$ with 
$\pi_k  \in \{ 0,1\}$, 
%%%{\bf $k \geq 2,$ } 
by
\begin{eqnarray*}
maj(\pi)   &  =   & \sum_k k \cdot \chi[ \pi_k > \pi_{k+1}], \\
less(\pi)   &  =   & \sum_k k \cdot \chi[ \pi_k < \pi_{k+1}],   
\end{eqnarray*}
 where $\chi[A] = 1$ if $A$ is true and $\chi[A] = 0$, otherwise.
%{\bf When $ \pi $ has no or one step, these indices are zero. }

For nonnegative integers $a, b, c, d, i$, and $j$ satisfying 
$a \leq c$
and $d \leq b$, let ${\cal N}(a,b,c,d,i,j)$ denote 
the set of pairs of {\em nonintersecting}
lattice paths, $( P,Q )$, where each left 
path ${P}$ runs from $(0,1)$ to $(a,b\!+\!1)$ and
has $i$ {\em left-hand turns}, and where each right 
path ${Q}$ runs from $(1,0)$ to $(c\!+\!1,d)$
and has $j$ {\em right-hand turns}.   (As usual, two paths are  {\em nonintersecting}
if they have no point in common. 
Figure~1  shows a pair
$(P,Q)$ of nonintersecting lattice paths in ${\cal
N}(4,5,6,5,2,3)$. The left-hand turns of $P$ and the
right-hand turns of $Q$ are circled. There,
$maj(P)=3+6=9$ and $less(Q)=3+5+9=17$.)
     
We will consider a bijective  proof of the following result, first   
when  
$q=1$ and then in general,
  \begin{eqnarray}
\lefteqn{\sum_{(P,Q)\in{\cal N}(a,b,c,d,i,j) } q^{maj(P) + less(Q)} = } 
\nonumber \\
& & q^{i^2 + j^2} \left\{  \qbinomial a i\!
\qbinomial b i \!    \qbinomial c j   \!   
\qbinomial d j   -\qbinomial {a\!+\!1} {i\!+\!1}  \!
\qbinomial {b\!-\!1} {i\!-\!1}   \!  \qbinomial {c\!-\!1} {j\!-\!1} \!
\qbinomial {d\!+\!1} {j\!+\!1}     \right\},  \label{Kratt}
\end{eqnarray} 
where $ \qbinomial a i  $  is the $q$-binomial coefficient (see \cite{Andrews}).

In 1955,  Narayana \cite{Narayana} recorded such a result  when the numbers of 
turns is ignored and $q=1.$  
 Formula (\ref{Kratt}) is a $q$-analogue of a symmetric form of a distribution in 
four parameters formulated by  Kreweras and Poupard  \cite{KP,Kre}  (see also 
\cite{Z}) for counting Catalan paths with a fixed number of valleys, certain 
long jumps and long landings.  Sulanke \cite{Sul1,Sul2} related their distribution to 
counting ${\cal N}(a,b,c,d,i,j)$ as given in formula (\ref{main}) below.

\vskip10pt
\vbox{
\Einheit.5cm
 
$$\begin{array}{c}
\Gitter(8,7)(0,0)
\Koordinatenachsen(8,7)(0,0)
\Pfad(1,0),12212112211\endPfad
\Pfad(0,1),221211221\endPfad
\DickPunkt(1,0)
\DickPunkt(0,1)
\DickPunkt(7,5)
\DickPunkt(4,6)
\Kreis(2,2)
\Kreis(3,3)
\Kreis(5,5)
\Kreis(1,3)
\Kreis(3,4)
\Label\lo{P }(2,4)
\Label\ru{Q }(4,3)
\Label\o{(c+1,d)}(8,5)
\Label\lo{(a,b+1)}(5,6)

\hskip5cm
\\[15pt]
\mbox{A nonintersecting pair}
\end{array}$$
\centerline{\footnotesize Figure 1}
}
\vskip10pt

Here we will be counting a set of pairs of nonintersecting paths as the difference of a set of pairs of unrestricted paths less  a set of pairs of {\em intersecting} paths. Hence, 
our proofs  of (\ref{Kratt}) and (\ref{main})   will rely on encoding the  pairs  of intersecting  paths as   quadruples  of sequences that we are able to count.   This encoding will use  insertions, deletions,  shifts  and  
 a bijection  between ${\cal N}(a,b,a,b,i,j)$ and ${\cal N}(a,b,a,b,j,i).$  For 
ordinary counting (i.e. $q=1$) we use the ``rotational'' bijection  
\begin{equation}
 R_{a,b,i,j}:{\cal N}(a,b,a,b,i,j) \leftrightarrow  {\cal N}(a,b,a,b,j,i) 
\label{rotational}
\end{equation}
where each pair of paths in  ${\cal N}(a,b,a,b,i,j)$ is rotated into a pair of paths 
in ${\cal N}(a,b,a,b,j,i)$ by an 180 degree rotation centered at $((a+1)/2,(b+1)/2)$. When $q \neq1 $, however, this 
simple rotation does not  preserve weight.  We have yet to find an explicit 
weight-preserving bijection;  as in Section 5, we can only define the bijection 
inductively. 


%
%
%     section 2 
%

\section{  Narayana's Result  and the  ``Rotation Method''} 

Ignoring the number of turns on each path in this section, let ${\cal A} \equiv {\cal A} 
(a,b,c,d)$   be the set of { \em all} pairs of lattice paths, $(P,Q)$, where 
$P$ runs from $(0,1)$ to  $(a,b+1)$
and $Q$ runs from $(1,0)$ to  $(c+1,d)$.
Let ${\cal N} (a,b,c,d)$ be the set of pairs of {  \em nonintersecting} paths 
in ${\cal A}$.  
To motivate our proof of  Formula~(\ref{Kratt}), we  introduce the 
 ``rotation method''   while proving a result  due  essentially to Narayana\cite{Narayana}, which he recorded  in an equivalent  form  for $a=c$ and $b=d$:
 \begin{equation}
|{\cal N}(a,b,c,d)| = {a\!+\!b\choose a}{c\!+\!d\choose c} - {a\!+\!b\choose 
a\!-\!1} {c\!+\!d\choose c\!+\!1}. \label{Narayana}
\end{equation}
\begin{pf*}{Proof of (\ref{Narayana})}
Let ${\cal I}$ denote the set of all {  \em intersecting}
pairs in ${\cal A}$.  We will use 
\begin{equation}
|{\cal N}|=  |{\cal A}|-  |{\cal I}| =  |{\cal A}| -
  |{\cal J}|, \label{difference}
\end{equation}
where  ${\cal J}$ is a bijective image of  \ ${\cal I}$ that we can count.  Specifically, ${\cal J}$ will be  the set of { \em all} \ pairs of lattice paths, $(P',Q')$, where 
$P'$ runs from $(1,0)$ to  $(a,b+1)$
and $Q'$ runs from $(0,1)$ to  $(c+1,d)$. 

 For each $(P,Q) \in {\cal I}$, let $(\alpha,\beta)$  denote the   {\em first point of intersection} of $P$ and $Q$.
\begin{enumerate}
\item{Let $P_1 $ be the  initial subpath of $P$ running from $(0,1)$ to $(\alpha-1,\beta).$ } 
\item{Let $P_2 $ be the  final subpath of $P$ running from $(\alpha,\beta) $ to $(a,b+1).$ } 
\item{Let $Q_1 $ be the initial subpath of $Q$ running from $(1,0)$ to $(\alpha,\beta-1).$ } 
\item{Let $Q_2 $ be the  final subpath of $Q$ running from $(\alpha,\beta) $ to $( c+1,d).$ \\
(We have yet to mention the steps immediately preceding $(\alpha,\beta)$.) } 
\end{enumerate}
\noindent Let $(\widehat{Q_1},\widehat{P_1})$ be the   image  of $(P_1,Q_1)$ under the   180-degree rotation  centered at $(\alpha/2,\beta/2)$.   $\widehat{P_1}0P_2$ runs from $(1,0)$ to $(a,b+1)$, and $\widehat{Q_1}1Q_2$ runs from $(0,1)$ to $(c+1,d)$.
 Thus, we have a bijection $\Gamma: {\cal I} \leftrightarrow {\cal J}$ where 
$$\Gamma((P,Q)) = (\widehat{P_1}0P_2,\widehat{Q_1}1Q_2) ,$$
and this shows (\ref{difference}).
Since there are ${a+b \choose a}{c+d \choose c}$ ways to choose a $(P,Q)$  in ${\cal A}$ and 
there are ${a+b \choose a-1}{c+d \choose c+1}$  ways to choose a $(P',Q')$  in 
${\cal J}$,  result (\ref{Narayana})
follows.   
\end{pf*}

We   remark that this proof is a modification of the
well-known ``interchanging''  method of 
 Gessel and Viennot \cite{GVunpub} (see \cite[section~1]{Stem} or 
\cite[section~2.2]{Krat1}) for counting  disjoint paths.  
However, in contrast to their method, here 
 $P$ and $Q$ are required to start within one unit of $(0,0)$, and
the   pair $(\widehat{P_1}0P_2,\widehat{Q_1}1Q_2) $ preserves, in essence, the   ``turn information'' of $(P,Q)$.  

Figure~2 illustrates the bijection $\Gamma:{\cal I}  \leftrightarrow   {\cal J}$.
  
 
 
 
\vskip10pt
\vbox{
\Einheit.5cm
$$\begin{array}{ccc}
\Gitter(11,9)(0,0)
\Koordinatenachsen(11,9)(0,0)
\Pfad(1,0),111222112221111\endPfad
\Pfad(0,1),2121212111112212\endPfad
\DickPunkt(1,0)
\DickPunkt(0,1)
\DickPunkt(9,8)
\DickPunkt(10,6)
%\Kreis(6,5)
%\Kreis(5,5)
%\Kreis(6,4)
\Kreis( 1, 2)
\Kreis( 2, 3)
\Kreis( 3, 4)
\Kreis(8, 5)
\Kreis( 9 , 7)
\Kreis( 4, 3)
\Kreis( 6, 6)
\Label\lo{P_{1}}(3,5)
\Label\lo{P_{2}}(8,7)
\Label\ru{Q_{1}}(4,3)
\Label\ru{Q_{2}}(9,6)
\Label\l{(0,1)\hskip15pt}(0,1)
\Label\u{(1,0)}(1,0)
\Label\ru{\hskip20pt(\alpha,\beta)}(6,5)
%\Label\o{(c+1,d)}(10,6)
%\Label\lo{(a,b+1)}(9,8)
\hskip5.3cm
&\hskip5pt\raise2cm\vbox{\hsize1cm\noindent$\longleftrightarrow$\par}&
\Gitter(11,9)(0,0)
\Koordinatenachsen(11,9)(0,0)
\Pfad(1,0),112121212221111\endPfad
\Pfad(0,1),2112221111112212\endPfad
\DickPunkt(1,0)
\DickPunkt(0,1)
\DickPunkt(9,8)
\DickPunkt(10,6)
%\Kreis(6,5)
%\Kreis(5,5)
%\Kreis(6,4)
\Label\lo{\widehat Q_{1}}(2,4)
\Label\lo{P_{2}}(8,7)
\Label\ru{\widehat P_{1}}(5,2)
\Label\ru{Q_{2}}(9,6)
\Label\l{(0,1)\hskip15pt}(0,1)
\Label\u{(1,0)}(1,0)
\Label\ru{\hskip20pt(\alpha,\beta)}(6,5)
%\Label\o{(c+1,d)}(10,6)
%\Label\lo{(a,b+1)}(9,8)
\hskip5.3cm
\\[15pt]
(P_11P_2,Q_10Q_2)\in \cal I&&
(\widehat P_10P_2,\widehat Q_11Q_2)\in \cal J
\end{array}$$
\centerline{\footnotesize Figure 2}
}
\vskip10pt




%
%                                section 3
%
\section{ Notation} 
In 
the remainder of the paper, except when noted,  $a, b, c, d, i,$ and $j$ are 
fixed integers satisfying 
$0 < i \leq a \leq c$
and $0 < j \leq  d \leq b$.   The cases for $i = 0$ or $j = 0$ are handled 
separately.  

Let ${\cal A}$ ($\equiv {\cal A}(a,b,c,d,i,j)$) denote 
the set of {\em all} \ pairs of paths, $( P,Q )$, where ${P}$ runs from $(0,1)$ 
to $(a,b\!+\!1)$ and
has $i$ {\em left-hand} turns, and where ${Q}$ runs from $(1,0)$ to $(c\!+\!1,d)$ and 
has $j$ {\em right-hand} turns.  For any $(P,Q) \in {\cal A} $, let the sequence $(x_1,y_1), 
\ldots, (x_i,y_i)$ denote the left-hand turns of $P,$ and let the sequence 
$(u_1,v_1), \ldots, (u_j,v_j)$ denote the right-hand turns of $Q$.   
These sequences of  turns completely specify $(P,Q)$, and conversely. 
Henceforth, $(P,Q)$ and $(X, Y, U, V)$ will both denote the same pair of paths in 
${\cal A}$,     where 
\begin{equation} X   =   (x_1, x_2, \ldots , x_i), \ \   Y  =   (y_1, y_2, 
\ldots , y_i),    \label{firstvector1}
\end{equation}
\begin{equation}
U   =   (u_1, u_2, \ldots , u_j), \ \  V  =   (v_1, v_2, \ldots , v_j),     
\label{firstvector2}
\end{equation}
\begin{equation}
1   \leq   x_1   <   x_2 <  \cdots   < x_i   \leq   a,   \ \ 
1   \leq   y_1   <   y_2 <  \cdots   < y_i   \leq   b, \label{condfirstvector1}
\end{equation}
\begin{equation}
1   \leq   u_1   <   u_2 <  \cdots   < u_j   \leq   c,  \ \ 
1   \leq   v_1   <   v_2 <  \cdots   < v_j   \leq d. \label{condfirstvector2}
 \end{equation}
In the example in Figure~1 we have $X =(1,3)$,
$Y =(3,4)$, $U =(2,3,5)$, $V =(2,3,5)$.

 If ${\cal I} $ denotes
the set of pairs of {\em intersecting} lattice paths in ${\cal A} $, then  
\begin{equation}
{\cal I} = \{ (X,Y,U,V) \in {\cal A}:  x_h \geq v_k \mbox{ and } y_h \leq 
v_k \mbox{ for some } h\mbox{ and } k \}.  \label{Icondition} 
\end{equation}

Let ${\cal C}$ denote the set  of all quadruples, $(X', Y', U', V')$,  of 
finite 
sequences of the form (empty sequences are allowed)
$$ X'  =   (x'_1, x'_2, \ldots, x'_i, x'_{i+1}), \ \ \ \  Y'=   (y'_1, y'_2, 
\ldots , y'_{i-1}),  $$
$$ U'   =   (u'_1, u'_2, \ldots , u'_{j-1}), \ \ \ \ V'  =   (v'_1, v'_2, 
\ldots ,v'_j,  v'_{j+1}),      $$
which satisfy 
 \begin{equation}
1   \leq        x'_1   <   x'_2  < \cdots   < x'_{i+1}    \leq   a+1, \ \ \
1   \leq         y'_1   <   y'_2  < \cdots   < y'_{i-1} \leq b-1,   
\label{condprime1}
\end{equation}
\begin{equation}
1   \leq        u'_1   <   u'_2 <  \cdots   < u'_{j-1} \leq c-1,  \ \ \
1   \leq        v'_1   <   v'_2  < \cdots   < v'_{j+1}         \leq   d+1.
\label{condprime2}
 \end{equation}

%
%                                section 4
%
\section{An Encoding}

Here we give a bijective proof for  
\begin{equation}
|{\cal N}(a,b,c,d,i,j)|={a\choose i}
{b\choose i}{c\choose j}{d\choose j}-{a\!+\!1\choose i\!+\!1}
{b\!-\!1\choose i\!-\!1}{c\!-\!1\choose j\!-\!1}{d\!+\!1\choose j\!+\!1}.  
\label{main}
\end{equation}

Since ${\cal N}(a,b,c,d,i,j) = {\cal A} - {\cal I} $,   and since, by 
elementary counting,
 $|{\cal A}|$ 
and $|{\cal C}| $ are, respectively,  the first term  and second term of 
formula~(\ref{main}),  we  now complete the proof of (\ref{main}) by 
exhibiting a bijection $\Gamma:{\cal I} \leftrightarrow   {\cal C}$.  

First, we consider the cases corresponding to $i=0$ or $j=0$.  
Formula~(\ref{main}) is clearly valid when $i = j = 0$.  If $ j=0$, 
$0< i \leq a$, and $0 < i \leq b$ (and similarly, for $i=0$, $0 < j \leq c$, 
and $ 0 < j \leq d$),   the notation of     (\ref{firstvector1}) and 
(\ref{condfirstvector1})    is meaningful and  $|{\cal A}(a,b,c,d,i,0)|= 
{\small {a\choose i}
{b\choose i} } $.  Since 
${\cal N}(a,b,c,d,i,0) = {\cal A}(a,b,c,d,i,0)$, formula~(\ref{main}) 
follows in this case.   

Assume $0<i$ and $0<j$.
For an arbitrary $(X,Y,U,V) \in {\cal I}$, define  $I$  to be the least $h$ and  
$J$ to be the least $k$,   such that $x_h \geq u_k$ and $y_h \leq v_k$.  Put 
$(\alpha,\beta) = (u_J,y_I)$; thus,  $(\alpha,\beta) $ is the first point of 
intersection of the pair of paths $(X,Y,U,V)$.  (See Figure~2 where
$I=4$, $J=2$;    there we circled the left-hand turns of $P$ and  the right-hand
turns of $Q$).  Let
${\Bbb{N}}$ denote the set of natural numbers with  ${\Bbb{N}}^{\ 0} $ being 
the singleton set 
containing the empty sequence. 

To complete the proof of (\ref{main}), we will show that the following map, adjusted so that $\cal C$ is its image, yields the desired bijection by 
exhibiting its inverse.
Define  $\Gamma:{\cal I} \rightarrow   {\Bbb{N}}^{\ i+1}\times
{\Bbb{N}}^{\ i-1}\times {\Bbb{N}}^{\ j-1}\times{\Bbb{N}}^{\ j+1}$  so that  
$$\Gamma((X,Y,U,V))   =  (X',Y',U',V')$$ 
satisfies
$$\begin{array}{lllllcccr}
X' &   =   &(\hat{x}_1,   &\ldots,   &\hat{x}_{I-1},  & \alpha, &                
x_I\!+\!1, &  \ldots,  &x_i\!+\!1), \\ 
Y' &   =   &(\hat{y}_1,   &\ldots,  &\hat{y}_{I-1},  &  y_{I+1}\!-\!1, &\ldots,    
&y_i\!-\!1), &  \\ 
U' &   =   &(\hat{u}_1,    &\ldots,  &\hat{u}_{J-1}, &  u_{J+1}\!-\!1, &\ldots,   
&   u_j\!-\!1), &  \\ 
V' &   =   &(\hat{v}_1,  &\ldots,   &\hat{v}_{J-1},   &   \beta , &  v_J\!  
+\!1, &\ldots,     &   v_j\!+\!1),  
\end{array}$$
where
$$\begin{array}{ll}
\hat{x}_k = \alpha-x_{I-k}   & \mbox{if $1 \leq k < I$}, \\ 
\hat{y}_k = \beta - y_{I-k}   & \mbox{if $1 \leq k < I$},\\ 
 \hat{u}_k = \alpha - u_{J-k}   & \mbox{if $1 \leq k < J$},\\ 
 \hat{v}_k =\beta- v_{J-k}   & \mbox{if $1 \leq k < J$}. 
\end{array}$$
Notice that these last four formulas correspond precisely to the rotation
$R_{\alpha-1,\beta-1,  I-1,J-1}$ referred to in (\ref{rotational}). 

\begin{ItoQ}  $\Gamma  $ maps $  {\cal I}$ into $ {\cal C}. $  
\end{ItoQ}

\begin{pf}  The inequalities of (\ref{condprime1}) and (\ref{condprime2}) 
can  be  routinely checked for $\Gamma(X,Y,U,V) $, particularly in light 
of the role of $R_{\alpha-1,\beta-1, I-1,J-1}$ within   
$\Gamma$. 
\end{pf}  


 We now    propose a candidate for the inverse of\/ $\Gamma:{\cal I} 
\rightarrow {\cal C}$.  
For an arbitrary   $(X',Y',U',V')$ $\in {\cal C}$,  put $y'_i = b$ and 
$u'_j = c$; and define $I'$ to be the least $h$ and  $J'$ to be the  least    
$k$ such that 
 $x'_h \leq u'_k \mbox{ and } y'_h \geq v'_k.$    
Since $x'_i  \leq a  \leq c = u'_j$ and $ y'_i = b \geq d \geq v'_j$, such 
integers $I'$ and $J'$ exist.   Put $(\alpha',\beta') = (x'_{I'},v'_{J'})$.  

Define  $\Delta:{\cal C} \rightarrow   
{\Bbb{N}}^{\ i }\times{\Bbb{N}}^{\ i}\times {\Bbb{N}}^{\ j}\times{\Bbb{N}}^{\ j }$   
so that  $\Delta((X',Y',U',V'))  =  (X,Y,U,V)$, where 
$$\begin{array}{lllllccrr}
X  &    =   &   (\widehat{x'}_1,&    \ldots,     &  \widehat{x'}_{I'-1},     
&  x'_{I'+1}\!-\!1,    & \ldots,      & \ldots,     &   x'_{i+1}\!-\!1),      \\ 
Y    &   =  &(\widehat{y'}_1, &     \ldots,   &  \widehat{y'}_{I'-1 },  
&  \beta', & y'_{I'  }\!+\!1, &\ldots,    &  y'_{i -1}\!+\!1 ),  \\ 
U     &  =  &(\widehat{u'}_1,  &    \ldots,   &  \widehat{u'}_{J'-1 }, 
& \alpha' ,  &  u'_{J' }\!+\!1, & \ldots, & u'_{j-1}\!+\!1),   \\ 
V  &   =  &   (\widehat{v'}_1,&      \ldots,  &  \widehat{v'}_{J'-1},  
& v'_{J'+1}\!-\!1,     &\ldots,    & \ldots,    &       v'_{j  + 1}\!-\!1),  
\end{array}$$
with
$$\begin{array}{ll}
\widehat{x'}_k = \alpha'-x'_{I'-k}   & \mbox{if $1 \leq k < I'$}, \\ 
\widehat{y'}_k = \beta' - y'_{I'-k}   & \mbox{if $1 \leq k < I'$},\\ 
 \widehat{u'}_k = \alpha'- u'_{J'-k}   & \mbox{if $1 \leq k < J'$},\\ 
 \widehat{v'}_k =\beta'- v'_{J'-k}   & \mbox{if $1 \leq k < J'$}. 
\end{array}$$

\begin{QtoI} $\Delta $ maps $  {\cal C}$ into $ {\cal I}.$ 
\end{QtoI}

\begin{pf}  The inequalities of ( \ref{condfirstvector1}) and 
( \ref{condfirstvector2}) 
 can easily be checked to show that $\Delta({\cal C})  \subseteq  {\cal A}$.   
To see that  $\Delta({\cal C}) \subseteq {\cal I}$, observe that 
$x_{I'} = x'_{I'+1} - 1  \geq x'_{I'}    = \alpha' = u_{J'}$ and 
$y_{I'} = \beta' = v'_{J'} \leq v'_{J'+1} - 1 = v_{J'}$; and then 
recall (\ref{Icondition}).   
\end{pf} 

\begin{inverses}   $\Delta : {\cal C} \rightarrow  {\cal I} $ 
is the inverse of $ \Gamma : {\cal I} \rightarrow  {\cal C} $ . 
\end{inverses}
\begin{pf}
First examine $\Delta \circ  \Gamma : {\cal I} \rightarrow  {\cal I}.$  
For  any $(X,Y,U,V) \in {\cal I},$    let $(X',Y',U',V') = \Gamma((X,Y,U,V))$.
Using their  previous definitions, we claim that $(I,J) = (I',J')$  and  
$(\alpha, \beta) = (\alpha', \beta')$.  Any  $(h,k)$ satisfying  $0 < h < I$ 
and $0 < k < J$  must satisfy   $x_{I-h} < u_{J-k}$  or  $y_{I-h} > v_{J-k}$.  
Thus, $x'_h = \alpha - x_{I-h} > \alpha - u_{J-k} = u'_k$ or $ y'_h = 
\beta - y_{I-h} < \beta - v_{J-k} = v'_k$.
This implies that $(I',J')$ must satisfy   $I \leq I'$ and $J \leq J'$.   
On the other hand, $x'_I = \alpha = u_J  \leq u_{J+1} - 1 = u'_J$ and 
$y'_I =  y_{I+1} - 1 \geq y_I = \beta = v'_J,$ which implies $I' \leq I$ 
and $J' \leq J$.   $\alpha = x'_I = x'_{I'} = \alpha'$, and $\beta = v'_J 
= v'_{J'} = \beta'$.
Now, since $(I,J) = (I',J')$  and $(\alpha, \beta) = (\alpha', \beta')$, 
a routine computation using  the definitions of $\Gamma$ and $\Delta$ shows 
that $\Delta(\Gamma(X,Y,U,V)) = (X,Y,U,V) $.


Next we  examine $\Gamma \circ  \Delta : {\cal C} \rightarrow  {\cal C}$. 
Put   $(X,Y,U,V) = \Delta((X',Y',U',V'))$, for  $(X',Y',U',V')$  $\in   
{\cal C} $.  
By Lemma 2, $(X,Y,U,V) \in  {\cal I}$. Thus  defining $I, J, I',$ and 
$J'$ has before, we claim that $(I',J') = (I,J)$  and  $(\alpha', \beta') 
= (\alpha, \beta)$.    Any $(h,k)$ satisfying $h < I'$ and $k < J'$ must 
satisfy   $x'_{I'-h} > u'_{J'-k}$   or    $y'_{I'-h} < v'_{J'-k}$; and 
thus, $x_h = \alpha' - x'_{I'-h} < \alpha' - u'_{J'-k} = u_k$ or $y_h = 
\beta' - y'_{I'-h} > \beta' - v'_{J'-k} = v_k.$  This yields  $I' \leq I$ 
and $J' \leq I$.   
On the other hand, $x_{I'} = x'_{I'+1}-1 \geq  x'_{I' } = \alpha' =  u_{J'}  
$ and $y_{I'} = \beta' = v'_{J'} \leq v'_{J'+1} - 1 = v_{J'}$; this condition 
implies $I \leq I'$ and $J \leq J'$.   $\alpha = u_{J} = u_{J'} = \alpha'$, 
and $\beta = y_{J} = v_{J'} = \beta'$.
 A routine check of the definitions of $\Gamma$ and $\Delta$ shows that 
$\Gamma(\Delta(X',Y',U',V')) = (X',Y',U',V') $. 
\end{pf}

%
%                                section 5
%

\section{ Counting with respect to weighted turns} 

For any $(P,Q) = (X,Y,U,V) \in {\cal A}(a,b,c,d,i,j)$, $maj(P)$   sums   the 
number of steps to each left-hand turn on $P$ and $less(Q)$  sums   
the number of steps to each right-hand turn on $Q$. Alternatively, 
\begin{eqnarray}
maj(P) + i  & = & (x_1+y_1) + \cdots + (x_i+y_i), \label{maj}\\ 
less(Q) + j  & = & (u_1+v_1) + \cdots + (u_j+v_j),\label{les}
\end {eqnarray}
where the terms $i$ and $j$ appear since $P$  starts at $(0,1)$ and $Q$  
starts at $(1,0)$.

For any subset $S$ of integers, define the {\em weight of} $S$  to be
$$w(S) = q^{\|S\|},\ \ \mbox{    where  }  \|S\| = \sum_{s_k \in S} s_k.$$
For any pair $(X,Y)$   and any quadruple $(X,Y,U,V)$ of integer sequences, put 
$$ 
w(X,Y)   =   w(X)w(Y),  \ \ \mbox{and} \ \ w(X,Y,U,V)  = w(X)w(Y)w(U)w( V). $$
Define the generating function of a set ${\cal S}$, on which this weight is 
defined, by 
$$G({\cal S}) = \sum_{S\in {\cal S} } w(S). $$
 Equations (\ref{maj}) and (\ref{les}) show that, for any  
${\cal B} \subseteq {\cal A},$
$$G({\cal B}) = \sum_{(P,Q)\in{\cal B}} q^{maj(P) +i+ less(Q)+j}.$$

On the other hand, we have
\begin{GA}
  $$G({\cal A} ) = q^{i^2+i+j^2+j}  
\qbinomial{a}{ i}
\qbinomial{b}{ i}\qbinomial{c}{ j}\qbinomial{d}{ j}   .$$
\end{GA}
\begin{GC}
  $$G({\cal C} ) = q^{i^2+i+j^2+j + 2} 
  \qbinomial{a\!+\!1}{ i\!+\!1}
\qbinomial{b\!-\!1}{ i\!-\!1}\qbinomial{c\!-\!1}{ j\!-\!1}
\qbinomial{d\!+\!1}{ j\!+\!1} .$$ 
\end{GC}
\begin{pf*}{Proof of Lemmas 4 and 5}  Let $P_k(n)$ denote the collection of 
$k$-element subsets of $\{ 1,2, \ldots, n \}$.
\begin{eqnarray*} 
G({\cal C})  & = & \sum_{(X',V',U',V') \in {\cal C} } 
q^{\|X'\|}q^{\|Y'\|}q^{\|U'\|}q^{\|V'\|} \\
    &= &  G(P_{i+1}(a+1))G(P_{i-1}(b-1))G(P_{j-1}(c-1))G(P_{j+1}(d+1)).
\end{eqnarray*} 
It is not difficult to show (See Andrews \cite{Andrews}, Ch. 3) that 
$$G(P_k(n)) = q^{{k+1}\choose2} \qbinomial{n}{ k},$$
whence Lemma 5 follows. Lemma 4 is proved in the same fashion.
\end{pf*}


\begin{pf*}{Proof of formula (\ref{Kratt})}
In this proof we will give a procedure similar to the   encoding $\Gamma$ 
of section~4.  Unfortunately, now we do not know an explicit formula for a 
weight preserving bijection
${\cal N}(a,b,a,b,i,j)\leftrightarrow {\cal N}(a,b,a,b,j,i);$ 
hence, we will establish its definition  recursively.   

We can establish the case  for $i=0$ or $j=0$ in a manner analogous 
to that used in the previous section.  Our proof of 
(\ref{Kratt}) for $0 < i \leq a$ and $0 < j \leq d$ is by induction on $a+d$.   It is easily checked 
that (\ref{Kratt}) holds for $a+d = 2$.


Our induction  hypothesis is that formula 
(\ref{Kratt}) is valid for all values of $a+d$ when $0 \leq a$, $0\leq d$, and 
$a+d <   n$ for some integer $n, n>2$.     Before proving the case for 
$a+d=n>2$, we will establish a specific weight preserving bijection, for 
$a+b <n ,$  
  \begin{equation}
{R}_{q,a,b,i,j}:{\cal N}(a,b,a,b,i,j)\leftrightarrow 
{\cal N}(a,b,a,b,j,i),\label{newrot}
\end{equation}    

  Since, by simple arithmetic,  
\begin{eqnarray*}
\lefteqn{
  \qbinomial{a\!+\!1}{ i\!+\!1}
\qbinomial{b\!-\!1}{ i\!-\!1}\qbinomial{a\!-\!1}{ j\!-\!1}
\qbinomial{b\!+\!1}{ j\!+\!1}   } \\
& \! = \! & \! \frac{  (1-q^{a+1}) (1-q^a) (1-q^{b+1}) (1-q^b) }
{ (1-q^{i+1})(1-q^i)(1-q^{j+1})(1-q^j)}   \qbinomial{a\!-\!1}{ i\!-\!1}
\qbinomial{b\!-\!1}{ i\!-\!1}\qbinomial{a\!-\!1}{ j\!-\!1}
\qbinomial{b\!-\!1}{ j\!-\!1}  \\
& \! = \! &\!   \qbinomial{a\!+\!1}{ j\!+\!1}
\qbinomial{b\!-\!1}{ j\!-\!1}\qbinomial{a\!-\!1}{ i\!-\!1}
\qbinomial{b\!+\!1}{i\!+\!1} , 
\end{eqnarray*} 
the induction hypothesis, with $a=c$ and $b=d$, implies 
\begin{equation}
G({\cal N}(a,b,a,b,i,j) ) = G( {\cal N}(a,b,a,b,j,i) ). \label{flip} 
\end{equation}
Put 
 ${\cal N}(a,b,i,j;m) = \{(X,Y,U,V) \! \in \! {\cal N}(a,b,a,b,i,j) : 
w((X,Y,U,V)) \! = \!q^m\}.$  
 Upon comparing coefficients of $q^m$ in (\ref{flip}), for any $m$,
$$ |{\cal N}(a,b,i,j;m)| = |{\cal N}(a,b,j,i;m)|.  $$
This equicardinality allows us to construct  a  specific  bijection:  
$${R}_{q,a,b,i,j,m}:{\cal N}(a,b,i,j;m)\leftrightarrow {\cal 
N}(a,b,j,i;m),$$
which, just to be specific,  preserves lexicographic order, where      ${\cal N}(a,b,i,j;m)$ and ${\cal 
N}(a,b,j,i;m)$  are ordered lexicographically according to the quadruple notation of $(X, Y, U, V).$ 
 Finally, define ${R}_{q,a,b,i,j}$ 
of (\ref{newrot})  to be the union of these 
${R}_{q,a,b,i,j,m}$'s.   

Now turn to the case $a+d = n > 2$.  Since 
\begin{eqnarray*}
\sum_{(P,Q)\in{\cal N} } q^{maj(P) +i+ less(Q)+j} &= 
&G({\cal N}(a,b,c,d,i,j))    \\
&= &   G({\cal A} )  -  G({\cal I} ), 
\end{eqnarray*}
and since Lemmas 4 and 5 hold, it suffices to establish a bijection  $${\Gamma}_q:{\cal I} 
\leftrightarrow {\cal C},$$
such that 
\begin{equation}
 q^2w((X,Y,V,U)) = w({\Gamma}_q( (X,Y,U,V) )), 
\label{weight}
\end{equation}
where the factor $q^2$    corresponds to  the same factor  in $G({\cal C})$ 
given in Lemma 5.   
Using the notation associated with the  bijection $\Gamma: {\cal I} 
\leftrightarrow {\cal C}$ of the previous section,  we define this new 
bijection so that ${\Gamma}_q((X,Y,U,V)) = (X',Y',U',V') $ where
$$\begin{array}{lllllcccr}
X' &=&(\bar{x}_1,  &   \ldots,  &  \bar{x}_{I-1}, &  \alpha , &           
x_I \!+\!1,     &    \ldots, &  x_i\!+\!1), \\ 
Y' &=&(\bar{y}_1,  &   \ldots,  &  \bar{y}_{I-1},   & y_{I+1}\!-\!1, &
\ldots,  
&  y_i\!-\!1),   &  \\ 
U' &=&(\bar{u}_1, & \ldots, & \bar{u}_{J-1}, & u_{J+1}\!-\!1, &
\ldots,  
& u_j\!-\!1), & \\ 
V' &=&(\bar{v}_1, & \ldots, & \bar{v}_{J-1},  & \beta , &  v_J \!+\!1, 
&  \ldots, &  v_j\!+\!1),  
\end{array}$$
with
\begin{eqnarray*}
\lefteqn{
( (\bar{u}_1,\ldots,\bar{u}_{J-1}),(\bar{v}_1,\ldots,\bar{v}_{J-1}),  
(\bar{x}_1,\ldots,\bar{x}_{I-1}),(\bar{y}_1,\ldots,\bar{y}_{I-1})) }\\ 
& = &{R}_{q,\alpha-1,\beta-1,I-1,J-1}
(     ({x}_1,\ldots,{x}_{I-1}), ({y}_1,\ldots,{y}_{I-1}), 
({u}_1,\ldots,{u}_{J-1}), ({v}_1,\ldots,{v}_{J-1}) ). 
\end{eqnarray*}
Here, ${R}_{q,\alpha-1,\beta-1,I-1,J-1}$ is a specific weight preserving bijection of
(\ref{newrot}) guaranteed by the induction hypothesis since   
$(\alpha-1)+(\beta-1)\leq (a-1)+(d-1)<n.$    Proofs very similar to those of section 4 show  that ${\Gamma}_q$ is 
indeed bijective.   
A 
simple check in the definition of $\Gamma_q$  shows it to 
satisfy the weight property (\ref{weight}).  
\end{pf*}

   Finally, we mention
 two  corollaries of Formula (\ref{Kratt}).  First, if we sum the right side 
of (\ref{Kratt}) with respect to $i$ and $j$, we obtain a 
$q$-analogue of Narayana's result, Equation (\ref{Narayana}), as studied by 
F\"{u}rlinger and Hofbauer \cite{FH}.

Secondly, if we put $a = c = d = j = n \leq b$ in Equation (\ref{Kratt}), 
the right paths are completely constrained to form, essentially, a diagonal 
boundary.  The resulting formula counts superdiagonal paths from $(0,1)$ to 
$(a,b+1)$ with $i$ valleys (i.e., left-hand turns).  An equivalent $q$-ballot 
number was given by MacMahon (\cite{MacMahon}, p. 368; \cite{FH}, 
section 4).   

\begin{thebibliography}{blabla} 

 \bibitem{Andrews} G.E. Andrews,   Theory of Partitions, Addison-Wesley Pub. 
Co., New York, 1976.

\bibitem{FH}   J. F\"{u}rlinger and J. Hofbauer, $q$-Catalan numbers,   J. of 
Comb. Th. (A), 40 (1985) 248-264.

 %\bibitem{Gessel} I. Gessel, A noncommutative generalization  and %q-analog of 
%the Lagrange inversion formula,  Trans. Amer. Math. Soc. 
%257 (1980) 455-481.   WHY?  He does some q-counting of "Narayana %structures"

  %\bibitem{  I. Gessel and G. Viennot, Binomial  Determinants, Paths %and 
%Hook Length   Formulae, {\it Adv. in Math}. 58 (1985) 41-55. 
   
\bibitem{GVunpub}  I. Gessel and G. Viennot, Binomial determinants, paths, and 
plane partitions, unpublished manuscript.

 

\bibitem{Krat1} C. Krattenthaler, The major counting of nonintersecting lattice 
paths and generating functions for tableaux,  preprint.

  \bibitem{Kre} G. Kreweras,  Joint distributions of three    descriptive  
parameters of   bridges,  Combinatoire \'enum\'erative    
(Proceedings, Montreal, 1985),  Lect. Notes   in Math., 
no. 1234, Springer, New York    (1986) 177-191. 

 \bibitem{KP}  G. Kreweras and Y. Poupard, Subdivision des    nombres des 
Narayana suivant   deux param\`etres suppl\'ementaire,  Europ. J.    
Combinatorics, 7 (1986) 141-149. 

 \bibitem{MacMahon} P.A. MacMahon,  Memoir on the theory of the partitions of numbers.-Part VI, Phil. Trans., A, 211 (1911) 345-373. Reprinted in Collected Papers:  Combinatorics, 
 Vol.  I. MIT Press, Cambridge Mass., 1978. 
%(This is where the result for counting Catalan paths with respect %to valleys 
%and its q-analogue appear for perhaps the first time. , %page 1429)

  \bibitem{Narayana}T.V. Narayana,  Sur les treillis form\'es par    les 
partitions d'un   entier,  Comp\-tes Rendus Acad. Sci. Paris, Ser I,  240 
(1955),    1188-89. 

 %\bibitem{   G. Polya, On the number of certain lattice    polygons,  %\it J. 
%Comb. Th. 6   (1969) 102-105     WHY?
   
\bibitem{Stem} J. Stembridge, Nonintersecting paths, Pfaffians, and plane 
partitions,  Adv. Math. 83,  (1990)
96-131

 \bibitem{Sul1}   R.A. Sulanke,  Refinements of the Narayana Numbers,  
Bull. Inst. Comb. and its App., 7 (1993) 60-66.

   
 \bibitem{Sul2}  R.A. Sulanke, A symmetric variation of a    distribution of 
Kreweras and   Poupard,  J. of Stat. Plan. and Infer.,  34 (1993) 291-303

 \bibitem{Z} D. Zeilberger, Six {\em etudes} in    generating functions, 
Intern. J.  Computer.   Math., 29 (1989) 201-215.   

\end{thebibliography}

\end{document}
