\def\UenKAA{38}
\def\SunaAA{37}
\def\SulaAC{36}
\def\StemAG{35}
\def\StemAE{34}
\def\SagaAK{33}
\def\SagaAF{32}
\def\RobyAA{31}
\def\ReWhAB{30}
\def\ReWhAA{29}
\def\OkadAC{28}
\def\OkadAB{27}
\def\ModaAA{26}
\def\MacdAB{25}
\def\KulkAC{24}
\def\KulkAB{23}
\def\KrMoAA{22}
\def\KratAP{21}
\def\KratAW{20}
\def\KratAQ{19}
\def\HeTrAA{18}
\def\GreCAA{17}
\def\GeViAB{16}
\def\GeViAA{15}
\def\GeKrAA{14}
\def\GessAL{13}
\def\FuKrAA{12}
\def\DoraAA{11}
\def\DeViAA{10}
\def\CoHeAA{9}
\def\ConcAB{8}
\def\ConcAA{7}
\def\ComtAA{6}
\def\ChGoAA{5}
\def\BrWeAA{4}
\def\BrenAG{3}
\def\BrenAE{2}
\def\BereAA{1}

\input format
\input path.sty
\NoRunningHeads
\TagsOnRight
\def\P{\bold P}
\def\RR{{\frak R}}
\def\v#1{{\vert#1\vert}}
\def\V#1{{\Vert#1\Vert}}

\topmatter 
\title Oscillating tableaux and nonintersecting lattice paths 
\endtitle 
\author C.~Krattenthaler
\endauthor 
\affil 
Institut f\"ur Mathematik der Universit\"at Wien,\\
Strudlhofgasse 4, A-1090 Wien, Austria.\\
e-mail: KRATT\@Pap.Univie.Ac.At
\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 05E10;
 Secondary 05A15, 20C33, 22E45
\endsubjclass
\keywords Oscillating tableaux, nonintersecting lattice paths\endkeywords
\abstract We give alternative proofs of determinantal formulas for
certain up-down tableaux and down-up
tableaux generating functions, 
which were first given in another paper by the author.
These new proofs are based on interpreting up-down and down-up tableaux as
certain families of nonintersecting lattice paths with three types of
steps.
\endabstract
\endtopmatter
\document

\subhead 1. Introduction and definitions\endsubhead
We provide proofs by nonintersecting lattice paths for two formulas
in \cite{\KratAW, \KratAQ} (see (1.1) and (1.2) below) about the
generating functions for certain oscillating tableaux. However, before
we are able to reproduce the formulas we have to recall some
definitions. A {\it partition} is a sequence
$\la=(\la_1,\la_2,\dots)$ of nonnegative integers which are in
decreasing order, i.e\. $\la_1\ge\la_2\ge\cdots$, where only finitely
many entries differ from zero. Zeros in the ``tail" of a partition
are frequently omitted. For instance,
$(6,4,4,1,0,0,\dots)=(6,4,4,1,0)=(6,4,4,1)$. Partitions can be viewed
pictorially as left-justified arrays of cells where the number of
cells in the $i$-th row of the array is given by $\la_i$. This array
of cells is called {\it Ferrers diagram} of the partition $\la$. For
example, the Ferrers diagram of $(6,4,4,1)$ is displayed in
Figure~1.
\vskip10pt
\vbox{
$$\smatrix \format
\sa\c\quad \s\c\quad \s\c\quad \s\c\quad \s\c\quad \s\c\quad \se\\
\hlinefor{13}\\
&\vphantom{f}&& && && && && &\\
\hlinefor{13}\\
&\vphantom{f}&& && && &\\
\hlinefor{9}\\
&\vphantom{f}&& && && &\\
\hlinefor{9}\\
&\vphantom{f}&\\
\hlinefor{3}\\
\endsmatrix$$
\centerline{\eightpoint Figure 1}
}
\vskip10pt
\noindent
The partition {\it conjugate} to a partition $\la$ is the partition
$\la'=(\la_1',\la_2',\dots)$ where $\la_i'$ is the number of cells in
the $i$-th {\it column} of $\la$. Equivalently, the Ferrers diagram
of $\la'$ is the Ferrers diagram of $\la$ reflected in its main
diagonal. For example, the partition conjugate to $(6,4,4,1)$ is
$(4,3,3,3,1,1)$. On the set of partitions a {\it partial order}
$\subseteq$ is defined by: $\mu\subseteq\la$ if and only if
$\mu_i\le\la_i$ for all $i$. Equivalently, $\mu\subseteq\la$ if
and only if the Ferrers diagram of $\mu$ is contained in the
Ferrers diagram of $\la$.

A {\it (generalized) up-down tableau from $\mu$ to $\la$}
\cite{\GessAL, \RobyAA, \SagaAF, \SunaAA} is a sequence
$T=(\ta_0,\ta_1,\dots,\ta_{2n-1},\ta_{2n})$ of partitions (Ferrers
diagrams), for some $n$, such that 
$$\mu=\ta_0\subseteq \ta_1\supseteq \ta_2\subseteq \dots\subseteq
\ta_{2n-1}\supseteq \ta_{2n}=\la,$$
and $\ta_{i-1}$ and $\ta_i$ differ by a {\it horizontal strip} for
each $i=1,2,\dots,2n$. A horizontal strip (cf\. \cite{\MacdAB, p.~4})
is an arrangement of cells with at most one cell in each column. The
number $2n$ is called the {\it length} of the up-down tableau $T$.

Similarly,
a {\it (generalized) down-up tableau from $\mu$ to $\la$}
is a sequence
$T=(\ta_0,\ta_1,\dots,\mathbreak \ta_{2n-1},\ta_{2n})$ of partitions, 
for some $n$, such that 
$$\mu=\ta_0\supseteq \ta_1\subseteq \ta_2\supseteq \dots\supseteq
\ta_{2n-1}\subseteq \ta_{2n}=\la,$$
and $\ta_{i-1}$ and $\ta_i$ differ by a {\it horizontal strip} for
each $i=1,2,\dots,2n$. 
Again, the number $2n$ is called the {\it length} of the down-up
tableau $T$. Examples for an up-down tableau and a down-up tableau
from $(2,1,1)$ to $(2,2,1,1)$ are given in Figure~2. Both have
length~4.

\vskip20pt
\vbox{
{\openup-3\jot
$$\matrix \format\l\,&\l\,&\l\,&\l\,&\l\quad \quad &\l\\
\left(
\smatrix \format\sa\c\s\c\se\\
\hlinefor5\\
& && &\\
\hlinefor5\\
& &\\
\hlinefor3\\
& &\\
\hlinefor3\\
\omit\vphantom{f}\endsmatrix,
\right.&
\smatrix \format\sa\c\s\c\s\c\se\\
\hlinefor7\\
& && && &\\
\hlinefor7\\
& && &\\
\hlinefor5\\
& &\\
\hlinefor3\\
\omit\vphantom{f}\endsmatrix,&
\smatrix \format\sa\c\s\c\s\c\se\\
\hlinefor7\\
& && && &\\
\hlinefor7\\
& && &\\
\hlinefor5\\
& &\\
\hlinefor3\\
\omit\vphantom{f}\endsmatrix,&
\smatrix \format\sa\c\s\c\s\c\s\c\s\c\se\\
\hlinefor{11}\\
& && && && && &\\
\hlinefor{11}\\
& && &\\
\hlinefor5\\
& && &\\
\hlinefor5\\
& &\\
\hlinefor3\\
\endsmatrix,&
\left.
\smatrix \format\sa\c\s\c\se\\
\hlinefor{5}\\
& && &\\
\hlinefor{5}\\
& && &\\
\hlinefor5\\
& &\\
\hlinefor3\\
& &\\
\hlinefor3\\
\endsmatrix\right)&
\text {up-down tableau}\\
\omit\vphantom{f}\\
\left(
\smatrix \format\sa\c\s\c\se\\
\hlinefor5\\
& && &\\
\hlinefor5\\
& &\\
\hlinefor3\\
& &\\
\hlinefor3\\
\omit\vphantom{f}\endsmatrix,
\right.&
\smatrix \format\sa\c\se\\
\hlinefor3\\
& &\\
\hlinefor3\\
& &\\
\hlinefor3\\
\omit\vphantom{f}\vphantom{g}\\
\omit\vphantom{f}\endsmatrix,&
\smatrix \format\sa\c\s\c\s\c\se\\
\hlinefor7\\
& && && &\\
\hlinefor7\\
& &\\
\hlinefor3\\
& &\\
\hlinefor3\\
\omit\vphantom{f}\endsmatrix,&
\smatrix \format\sa\c\s\c\se\\
\hlinefor{5}\\
& && &\\
\hlinefor{5}\\
& &\\
\hlinefor3\\
& &\\
\hlinefor3\\
\omit\vphantom{f}\endsmatrix,&
\left.
\smatrix \format\sa\c\s\c\se\\
\hlinefor{5}\\
& && &\\
\hlinefor{5}\\
& && &\\
\hlinefor5\\
& &\\
\hlinefor3\\
& &\\
\hlinefor3\\
\endsmatrix\right)&
\text {down-up tableau}\endmatrix$$
}%
\centerline{\eightpoint Figure 2}
}
\vskip10pt

We say that an up-down tableau (respectively down-up tableau)
$T=(\ta_0,\ta_1,\dots,\mathbreak \ta_{2n-1},\ta_{2n})$ {\it has at most $r$
columns} ({\it respectively rows}) if each $\ta_i$, $i=0,1,\dots,2n$,
has at most $r$ columns (rows). So for example, the up-down tableau
in Figure~2 has at most 5 (6, 7,\dots) columns and the down-up
tableau in Figure~2 has at most 4 (5, 6,\dots) rows.

The {\it weight} $w(T)$ of an up-down or down-up tableau $T$ is
defined by
$$w(T):=x_1^{\vert\, \vert \ta_0\vert -\vert \ta_1\vert
\,\vert }
x_1^{\vert\, \vert \ta_1\vert -\vert \ta_2\vert
\,\vert }
x_2^{\vert\, \vert \ta_2\vert -\vert \ta_3\vert
\,\vert }
x_2^{\vert\, \vert \ta_3\vert -\vert \ta_4\vert
\,\vert }\cdots.$$
Thus the weight of the up-down tableau in Figure~2 is given by
$x_1^2x_1^0x_2^4x_2^4=x_1^2x_2^8$, while the weight of the down-up
tableau in Figure~2 is given by $x_1^2x_1^3x_2^1x_2^2=x_1^5x_2^3$.
Let us write $\bold x$ for the sequence of variables $x_1,x_2,\dots$.

Now we are able to state the formulas of \cite{\KratAW, \KratAQ}. Let
$ud_{\mu\to\la}^{(r)}(\bold x)$ denote the generating function $\sum _{T}
^{}w(T)$ summed over all up-down tableaux $T$ from $\mu$ to $\la$
with at most $r$ columns. Then for any partitions
$\al=(\al_r,\al_{r-1},\dots,\al_1)$ and
$\be=(\be_r,\be_{r-1},\dots,\be_1)$ we have
$$ud_{\be'\to\al'}^{(r)}(\bold x)=
\det_{1\le s,t\le r}\Big(\sum _{k} ^{}e_{\al_s+s-\be_t-t+k}(\bold x)
e_{k}(\bold x)
-\sum _{k} ^{}e_{\al_s+s+\be_t+t+k}(\bold x)e_k(\bold x)\Big),
\tag1.1$$
where $e_m(\bold x)$ denotes the elementary symmetric function of order $m$ 
in the variables $x_1,x_2,\dots$ (cf\. \cite{\MacdAB, p.~12}). Note that we
definitely want the entries of $\al$ and $\be$ to be indexed in
reverse order.

Likewise, let
$du_{\mu\to\la}^{(r)}(\bold x)$ denote the generating function $\sum _{T}
^{}w(T)$ summed over all down-up tableaux $T$ from $\mu$ to $\la$
with at most $r$ rows. Then for partitions
$\al$ and $\be$ as above we have
$$du_{\be\to\al}^{(r)}(\bold x)=
\det_{1\le s,t\le r}\Big(\sum _{k} ^{}h_{\al_s+s-\be_t-t+k}(\bold x)
h_{k}(\bold x)
-\sum _{k} ^{}h_{\al_s+s+\be_t+t+k}(\bold x)h_k(\bold x)\Big),
\tag1.2$$
where $h_m(\bold x)$ denotes the complete homogeneous symmetric function 
of order $m$ in the variables $x_1,x_2,\dots$ (cf\. \cite{\MacdAB,
p.~14}).

The significance of the formulas (1.1) and (1.2) is elaborated in
\cite{\KratAW}. In particular, from these formulas enumeration
results for standard oscillating tableaux with a bounded number of
rows can be derived. These standard oscillating tableaux 
play an important role in Berele's decomposition formula
\cite{\BereAA} for powers of defining representations of the complex
symplectic groups. Also, if $\al$ or $\be$ are rectangular shapes 
the determinant in (1.1) basically is an irreducible symplectic character. 
This led to a
new combinatorial description of irreducible symplectic characters in
terms of oscillating tableaux \cite{\KratAW}.

The formulas (1.1) and (1.2) 
were proved in \cite{\KratAW} by interpreting the
right-hand side determinants of (1.1) and (1.2) as generating
functions for certain families of two-rowed arrays and then setting
up a bijection between these families of two-rowed arrays and up-down
and down-up tableaux. These bijections were based on 
Robinson--Schensted type algorithms. In the next section we shall
prove (1.1) and (1.2) by using nonintersecting lattice paths and
variations of the so-called reflection principle (cf\. e.g\. \cite{\ComtAA,
p.~22}). The method of nonintersecting lattice paths, due to Gessel
and Viennot \cite{\GeViAA, \GeViAB} (cf\. also \cite{\StemAE, sec.~1}), has
been successfully utilized in numerous papers \cite{\BrenAE, \BrenAG,
\BrWeAA, \ChGoAA, \ConcAA, \ConcAB, \CoHeAA, \DeViAA, \DoraAA,
\FuKrAA, \GeKrAA, \GreCAA, \HeTrAA, \KratAQ, \KratAW, \KratAP,
\KrMoAA, \KulkAB, \KulkAC, \ModaAA, \OkadAB, \OkadAC, \ReWhAA,
\ReWhAB, \SagaAK, \StemAE, \StemAG, \SulaAC, \UenKAA}. So this paper might be
considered as a further contribution to this list of papers (which
very likely is incomplete). Combinations of the nonintersecting
lattice path method and variants of the reflection principle earlier
appeared in \cite{\FuKrAA, \KratAQ, \KratAW, \KratAP}.

\subhead 2. Nonintersecting lattice paths\endsubhead
To begin with, we introduce some lattice path notation. Given a set
$S$ of steps we denote the set of all lattice paths from $A$ to $E$
with steps from the set $S$ by $\Cal P(A\to E;S)$. We frequently
shall write
$P:A\to E$ to indicate that the lattice path $P$ runs from $A$ to
$E$. A set of paths is said to be {\it nonintersecting\/} if no
two paths of this set have a point in common. Otherwise it is called
{\it intersecting\/}. 
If to each step $s\in S$ a weight
$w(s)$ is assigned, the weight $w(P)$ of a path $P$ is defined
to be the product of the weights of all its steps. The
weight $w(\P)$ of a family $\P=(P_1,\dots,P_r)$ of paths 
is defined to be the product $\prod
_{i=1} ^{r}w(P_i)$ of the weights of all the paths in the
family.
Given any weight function $w$ defined on a set $\Cal M$,
by the generating function $GF(\Cal M;w)$ we mean $\sum
_{x\in\Cal M} ^{}w(x)$. 
\medskip

{\it Proof of (1.1).\/} Here we consider lattice paths in the plane
integer lattice with steps from the set $S_1=\{(i,j)\to(i,j+1),\
(i,2j-2)\to(i+1,2j-1),\ (i,2j-1)\to(i-1,2j),$ where $i,j$ run through
the integers$\}$. In words, the set of steps consists of 
vertical steps north, forward diagonal steps 
northeast from even height to odd height, 
and backward diagonal steps northwest from odd height
to even height. In the sequel, when we say `lattice path' we always
mean a lattice path with steps from the set $S_1$.

First we set up a one-to-one correspondence between {\it up-down
tableaux from $\be'$ to $\al'$ with at most $r$ columns}  and {\it
families $\P=(P_1,P_2,\dots,P_r)$ of nonintersecting lattice paths
where $P_i$ runs from $A_i=(\be_i+i,0)$ to $E_i=(\al_i+i,\infty)$ and
never touches the $y$-axis, $i=1,2,\dots,r$\/}. 
Let $T=(\ta_0,\ta_1,\dots,\ta_{2n})$
be an up-down tableau from $\be'$ to $\al'$ with at most $r$ columns.
The bijection is defined in a way such that the $i$-th path encodes
the growth and shrink of the $(r-i+1)$-st column of $T$. To be more
precise, starting with $A_i=(\be_i+i,0)$ for $j=1,2,\dots,n$ do the
following procedure: If $\ta_{2j-1}$ has one cell more in the
$(r-i+1)$-st column than $\ta_{2j-2}$ then add a forward diagonal
step to $P_i$, otherwise a vertical step. If $\ta_{2j}$ has one cell
less in the $(r-i+1)$-st column than $\ta_{2j-1}$ then add a backward
diagonal step, otherwise a vertical step. Finally, an infinite number
of vertical steps is added to each path to connect to the end points
$(\al_i+i,\infty)$. Thus, given $r=5$, the up-down tableau in
Figure~2 corresponds to the set of nonintersecting lattice paths
displayed in Figure~3. Note that in this example we have
$\al=(4,2,0,0,0)$ and $\be=(3,1,0,0,0)$, i.e\. $\al_1=\al_2=\al_3=0$,
$\al_4=2$, $\al_5=4$, $\be_1=\be_2=\be_3=0$, $\be_4=1$, $\be_5=3$.
\vskip10pt
\vbox{
$$
\Koordinatenachsen(10,9)(0,0)
\Gitter(10,7)(0,0)
\Pfad(1,0),223\endPfad
\Pfad(1,4),4\endPfad
\Pfad(1,4),22\endPfad
\Pfad(2,0),223\endPfad
\Pfad(2,4),4\endPfad
\Pfad(2,4),22\endPfad
\Pfad(3,0),322\endPfad
\Pfad(3,4),4\endPfad
\Pfad(3,4),22\endPfad
\Pfad(5,0),323\endPfad
\Pfad(6,4),4\endPfad
\Pfad(6,4),22\endPfad
\Pfad(8,0),223222\endPfad
\DickPunkt(1,0)
\DickPunkt(2,0)
\DickPunkt(3,0)
\DickPunkt(5,0)
\DickPunkt(8,0)
\Label\u{A_1}(1,0)
\Label\u{A_2}(2,0)
\Label\u{A_3}(3,0)
\Label\u{A_4}(5,0)
\Label\u{A_5}(8,0)
\Label\o{E_1}(1,7)
\Label\o{E_2}(2,7)
\Label\o{E_3}(3,7)
\Label\o{E_4}(6,7)
\Label\o{E_5}(9,7)
\Label\o{\uparrow}(1,6)
\Label\o{\uparrow}(2,6)
\Label\o{\uparrow}(3,6)
\Label\o{\uparrow}(6,6)
\Label\o{\uparrow}(9,6)
\Label\l{P_1}(1,2)
\Label\r{P_2}(2,1)
\Label\r{P_3}(4,2)
\Label\r{\ P_4}(6,2)
\Label\r{P_5}(8,1)
\hskip5cm
$$
\centerline{\eightpoint Figure 3}
}
\vskip10pt
Clearly this operation sets up the claimed bijection. It becomes
weight-preserving if we define the weight 
$w(v)$ of a vertical step $v$ to be $1$, the weight $w(f)$ of a
forward diagonal step $f:(i,2j-2)\to(i+1,2j-1)$ as well as the weight
$w(b)$ of a backward diagonal step $b:(i,2j-1)\to (i-1,2j)$ to be
$x_j$. Recall that this weight function $w$ on the step set $S_1$
induces a weight $w$ on families of lattice paths as was explained at the
beginning of this section.

Next we give a combinatorial description of the determinant in (1.1).
Because of
$$GF(\Cal P((a,0)\to(b,\infty);S_1);w)=\sum _{k}
^{}e_{b-a+k}(\bold x)e_k(\bold x)$$
we may write the determinant in (1.1) as
$$\det\big(GF(\Cal P(A_{t}\to E_s;S_1);w)-
GF(\Cal P(\RR A_{t}\to E_s;S_1);w)\big),\tag1.3$$
where $\RR$ is the reflection in the $y$-axis. 
By expanding the determinant, (1.3) can be written in the form
$$\multline
\underset \et \in\{1,-1\}^r\to{\sum _{\si\in\frak S_r} ^{}}
\sgn\si\prod _{i=1} ^{r}\et_i\prod _{i,\et_i=1} ^{} GF(\Cal
P(A_{\si(i)}\to E_i;S_1);w) \\
\prod _{i,\et_i=-1} ^{} GF(\Cal P(\RR A_{\si(i)}\to E_i;S_1);w),
\endmultline$$
or 
$$\underset \P=(P_1,\dots,P_r),\ P_i:\RR^{\et_i}A_{\si(i)}\rightarrow E_i\to 
{\sum _{\si\in\frak S_r,\ \et\in\{0,1\}^r}
^{}}(-1)^{\V\et}\sgn\si\,w(\P),\tag1.4$$
where $\V\et=\sum _{i=1}
^{r}\et_i$. Of course, $\RR^0$
means the identity map.

By (1.4) we have written the determinant in (1.1) as a generating
function for families $\P=(P_1,P_2,\dots,P_r)$
of lattice paths, $P_i:\RR^{\et_i}A_{\si(i)}\to E_i$, for some
$\si\in\frak S_r$ and $\et\in\{0,1\}^r$. Let
us call $\si$ the {\it permutation associated to $\P$} and $\et$ the 
{\it reflection indicator associated to $\P$}.
In the sum (1.4) many terms will cancel.
We shall construct a {\it sign-reversing} (with respect to
$(-1)^{\V\et}\sgn\si$) and {\it weight-preserving} (with respect to
$w$) {\it involution} on the set of all families $\P=(P_1,P_2,\dots,P_r)$
of lattice paths that were described above, which are
{\it either intersecting or contain a path that touches the $y$-axis.}
Suppose that this had been done. Then in the sum (1.4) 
only the terms which come from {\it nonintersecting families of lattice paths
that do not touch the $y$-axis} will survive. 
In particular, none of the starting points of such a family $\P$ could be
located to the left of the $y$-axis. Hence, the reflection indicator
associated to $\P$ must equal $(1,1,\dots,1)$. Besides, because $\P$ is
nonintersecting the location of the starting and end points of the
paths of $\P$ implies that the permutation associated to $\P$ 
must be the identity permutation.
But these families $\P$ of lattice paths exactly correspond to the
up-down tableaux under consideration, as was shown above. This would
establish (1.1).

Now we define the involution, which we denote by $\Th_1$. Let
$\P=(P_1,P_2,\dots,P_r)$ be a family of lattice paths, 
$P_i:\RR^{\et_i}A_{\si(i)}\to E_i$, for some
$\si\in\frak S_r$ and $\et\in\{0,1\}^r$, which is
either intersecting or contains a path that touches the $y$-axis. 
First consider all meeting points of a path of $\P$ and the $y$-axis.
Let $M$ be the highest of these meeting points. 
Among the paths which go through $M$ choose $P_I$ with $I$
being minimal. Note that the $y$-coordinate of $M$ must be even.
Now, to $P_I$'s initial portion up to $M$ we apply 
the following modified reflection in the $y$-axis (see Figure~4). 
Beginning from the starting point of $P_I$ up to $M$ 
consider the steps of $P_I$ in groups of two.
There are four different cases. Replace two vertical steps by two
vertical steps, a vertical step and a backward diagonal step
by a forward diagonal step and a vertical step, a forward
diagonal step and a vertical step by a vertical step and a backward
diagonal step, a forward diagonal step and a backward diagonal step
by a forward diagonal step and a backward diagonal step. What is
obtained by this procedure is joined with the terminal portion of
$P_I$ beginning from $M$. In Figure~4 the circled points indicate the
grouping of the steps into groups of two that was described above.
Let the image of $P_I$ under application of this modified
reflection be denoted by $P'_I$.
We then obtain the new family $\Th_1(\P)=(P_1,\dots,P'_I,\dots,P_r)$. 
Since the new starting point of $P_I'$ is the reflection of the
starting point of $P_I$
in the $y$-axis, the permutation associated to $\Th_1(\P)$ in this case
is still $\si$ while the reflection indicator associated to $\Th_1(\P)$
is given by $(\et_1,\dots,1-\et_I,\dots,\et_r)$. 
\vskip10pt
\vbox{
$$
\Koordinatenachsen(5,11)(-3,0)
\Gitter(5,11)(-3,0)
\Pfad(1,0),323\endPfad
\Pfad(2,4),4\endPfad
\Pfad(2,4),2\endPfad
\Pfad(1,6),4\endPfad
\Pfad(1,6),2\endPfad
\Pfad(0,8),4\endPfad
\Pfad(0,8),32\endPfad
\DickPunkt(1,0)
\DickPunkt(0,8)
\DickPunkt(1,10)
\Kreis(2,2)
\Kreis(2,4)
\Kreis(1,6)
\Label\u{\RR^{\et_I}A_{\si(I)}}(2,0)
\Label\l{M}(0,8)
\Label\o{E_I}(1,10)
\Label\r{P_I}(2,5)
\hskip3cm
\raise3cm\hbox{$\longrightarrow\hskip3cm$}
\Koordinatenachsen(5,11)(-3,0)
\Gitter(5,11)(-3,0)
\Pfad(-1,0),2\endPfad
\Pfad(-2,2),4\endPfad
\Pfad(-2,2),3\endPfad
\Pfad(-2,4),4\endPfad
\Pfad(-2,4),323232\endPfad
\DickPunkt(-1,0)
\DickPunkt(0,8)
\DickPunkt(1,10)
\Kreis(-2,2)
\Kreis(-2,4)
\Kreis(-1,6)
\Label\u{\RR^{1-\et_I}A_{\si(I)}}(-1,0)
\Label\l{M}(0,8)
\Label\o{E_I}(1,10)
\Label\lu{P_I'}(-1,6)
$$
\centerline{\eightpoint Figure 4}
}
\vskip10pt

If none of the paths of $\P$ meet the $y$-axis consider all meeting
points between any two paths of $\P$. Choose the highest
meeting points, and among those the left-most. Denote this meeting
point by $M$. Now we apply the
usual Gessel--Viennot interchanging procedure. To be more precise,
among the pairs of paths which have $M$ in
common, choose $(P_I,P_J)$, with $(I,J)$ being minimal 
with respect to the lexicographic order of pairs of integers.
Next we decompose $P_I$ into $P_I^{(1)}$ and $P_I^{(2)}$, where $P_I^{(1)}$ is
the portion of $P_I$ going from $\RR^{\et_I}\A_{\si(I)}$ to $M$, and 
where $P_I^{(2)}$ is the
portion of $P_I$ between $M$ and $E_I$. Analogously, $P_J$ is
decomposed by $M$ into $P_J^{(1)}$ and $P_J^{(2)}$. Then by concatenation
form the new paths $P'_I=P_J^{(1)}P_I^{(2)}$ and
$P'_J=P_I^{(1)}P_J^{(2)}$. In other terms, the initial portions of
$P_I$ and $P_J$ up to their last meeting point are interchanged, the
terminal portions are preserved. Thus we obtain the new family
$\Th_1(\P)=(P_1,\dots,P'_I,\dots,P'_J,\dots,P_r)$. Obviously, since
the $I$-th and $J$-th starting point have been interchanged, the
permutation associated to $\Th_1(\P)$ is $\si\circ(IJ)$
($(IJ)$ is the
transposition that interchanges $I$ and $J$), and the reflection
indicator associated to $\Th_1(\P)$ is
$(\et_1,\dots,\et_J,\dots,\et_I,\dots,\et_r)$. 

It is easy to see that in both cases, by application of
$\Th_1$ to $\Th_1(\P)$, one arrives at $\P$ again. Consequently 
$\Th_1$ is an involution. Besides, by construction it is
weight-preserving with respect to $w$ and sign-reversing with respect
to $(-1)^{\V\et}\sgn\si$.\quad \quad \qed
\bigskip


{\it Proof of (1.2).\/} Here we consider lattice paths in the plane
integer lattice with steps from the set $S_2=\{(i,j)\to(i,j+1),\
(i,2j-1)\to(i-1,2j-1),\ (i,2j)\to(i+1,2j),$ where $i,j$ run through
the integers$\}$. In words, the set of steps consists of 
vertical steps north, backward horizontal steps (west) at odd height, 
and forward horizontal steps (east) at even height.
In the sequel, when we say `lattice path' we always
mean a lattice path with steps from the set $S_2$.

First we set up a one-to-one correspondence between {\it down-up
tableaux from $\be$ to $\al$ with at most $r$ rows}  and {\it
families $\P=(P_1,P_2,\dots,P_r)$ of nonintersecting lattice paths
where $P_i$ runs from $A_i=(\be_i+i,0)$ to $E_i=(\al_i+i,\infty)$ and
never touches the $y$-axis, $i=1,2,\dots,r$\/}. 
Let  $T=(\ta_0,\ta_1,\dots,\ta_{2n})$
be a down-up tableau from $\be$ to $\al$ with at most $r$ rows.
The bijection is defined in a way such that the $i$-th path encodes
the growth and shrink of the $(r-i+1)$-st row of $T$. To be more
precise, starting with $A_i=(\be_i+i,0)$ for $j=1,2,\dots,n$ do the
following procedure: If $\ta_{2j-1}$ has $n$ cells less in the
$(r-i+1)$-st row than $\ta_{2j-2}$ then add a vertical step followed
by $n$ backward horizontal steps to $P_i$.
If $\ta_{2j}$ has $n$ cells
more in the $(r-i+1)$-st row than $\ta_{2j-1}$ then add a vertical
step followed by $n$ forward horizontal steps to $P_i$. 
Finally, an infinite number
of vertical steps is added to each path to connect to the end points
$(\al_i+i,\infty)$. Thus, given $r=4$, the down-up tableau in
Figure~2 corresponds to the set of nonintersecting lattice paths
displayed in Figure~5. Note that in this example we have
$\al_1=1$, $\al_2=1$, $\al_3=2$, $\al_4=2$, $\be_1=0$, $\be_2=1$,
$\be_3=1$, $\be_4=2$.
\vskip10pt
\vbox{
$$
\Koordinatenachsen(9,9)(0,0)
\Gitter(9,7)(0,0)
\Pfad(1,0),2222122\endPfad
\Pfad(3,0),2\endPfad
\Pfad(2,1),1\endPfad
\Pfad(2,1),212222\endPfad
\Pfad(4,0),2222122\endPfad
\Pfad(6,0),2\endPfad
\Pfad(5,1),1\endPfad
\Pfad(5,1),2112\endPfad
\Pfad(6,3),1\endPfad
\Pfad(6,3),222\endPfad
\DickPunkt(1,0)
\DickPunkt(3,0)
\DickPunkt(4,0)
\DickPunkt(6,0)
\Label\u{A_1}(1,0)
\Label\u{A_2}(3,0)
\Label\u{A_3}(4,0)
\Label\u{A_4}(6,0)
\Label\o{E_1}(2,7)
\Label\o{E_2}(3,7)
\Label\o{E_3}(5,7)
\Label\o{E_4}(6,7)
\Label\o{\uparrow}(2,6)
\Label\o{\uparrow}(3,6)
\Label\o{\uparrow}(5,6)
\Label\o{\uparrow}(6,6)
\Label\l{P_1}(1,3)
\Label\l{P_2}(3,3)
\Label\r{P_3}(4,3)
\Label\r{P_4}(7,3)
\hskip4cm
$$
\centerline{\eightpoint Figure 5}
}
\vskip10pt
Clearly this operation sets up the claimed bijection. It becomes
weight-preserving if we define the weight 
$w(v)$ of a vertical step $v$ to be $1$, the weight $w(f)$ of a
backward horizontal step $f:(i,2j-1)\to(i-1,2j-1)$ as well as the weight
$w(b)$ of a forward horizontal step $b:(i,2j)\to (i+1,2j)$ to be
$x_j$. Recall that this weight function $w$ on the step set $S_2$
induces a weight $w$ on families of lattice paths as was explained at the
beginning of this section.

Next we give a combinatorial description of the determinant in (1.2).
Because of
$$GF(\Cal P((a,0)\to(b,\infty);S_2);w)=\sum _{k}
^{}h_{b-a+k}(\bold x)h_k(\bold x)$$
we may write the determinant in (1.2) as
$$\det\big(GF(\Cal P(A_{t}\to E_s;S_2);w)-
GF(\Cal P(\RR A_{t}\to E_s;S_2);w)\big),\tag1.5$$
where $\RR$ is again the reflection in the $y$-axis. 
By expanding the determinant, (1.5) can be written in the form
$$\multline
\underset \et \in\{1,-1\}^r\to{\sum _{\si\in\frak S_r} ^{}}
\sgn\si\prod _{i=1} ^{r}\et_i\prod _{i,\et_i=1} ^{} GF(\Cal
P(A_{\si(i)}\to E_i;S_2);w) \\
\prod _{i,\et_i=-1} ^{} GF(\Cal P(\RR A_{\si(i)}\to E_i;S_2);w),
\endmultline$$
or 
$$\underset \P=(P_1,\dots,P_r),\ P_i:\RR^{\et_i}A_{\si(i)}\rightarrow E_i\to 
{\sum _{\si\in\frak S_r,\ \et\in\{0,1\}^r}
^{}}(-1)^{\V\et}\sgn\si\,w(\P),\tag1.6$$
where again $\V\et=\sum _{i=1}
^{r}\et_i$.

By (1.6) we have written also the determinant in (1.2) as a generating
function for families $\P=(P_1,P_2,\dots,P_r)$
of lattice paths, $P_i:\RR^{\et_i}A_{\si(i)}\to E_i$, for some
$\si\in\frak S_r$ and $\et\in\{0,1\}^r$. The only difference to (1.4)
is that the set of steps now is $S_2$ instead of $S_1$. Again, let
us call $\si$ the {\it permutation associated to $\P$} and $\et$ the 
{\it reflection indicator associated to $\P$}.
Also here, 
we shall construct a {\it sign-reversing} (with respect to
$(-1)^{\V\et}\sgn\si$) and {\it weight-preserving} (with respect to
$w$) {\it involution} on the set of all families
$\P=(P_1,P_2,\dots,P_r)$
of lattice paths that were described above, which are
{\it either intersecting or contain a path that touches the $y$-axis.}
Once this is done, similar arguments as those in the proof of (1.1) show
that (1.2) would be established.

Now we define the involution, which we denote by $\Th_2$. Let
$\P=(P_1,P_2,\dots,P_r)$ be a family of lattice paths, 
$P_i:\RR^{\et_i}A_{\si(i)}\to E_i$, for some
$\si\in\frak S_r$ and $\et\in\{0,1\}^r$, which is
either intersecting or contains a path that touches the $y$-axis.
As before, first
consider all meeting points of any path of $\P$ with the $y$-axis. 
Let $M$ be the highest of these meeting points. 
Among the paths which go through $M$ choose $P_I$ with $I$
being minimal. Again, note that the $y$-coordinate of $M$ must be even.
Now, to $P_I$'s initial portion up to $M$ we apply 
the following modified reflection in the $y$-axis (see Figure~6). 
Beginning from the starting point of $P_I$ up to $M$ 
consider the portions of $P_I$ which lie between
the horizontal lines $y=2j-2$ and $y=2j$, portions of $P_I$ on the
line $y=2j-2$ excluded while portions on $y=2j$ included.
If in this portion there is a vertical step followed by $n$ backward 
horizontal steps 
and then a vertical step followed by $m$ forward horizontal steps 
(note that the vertical steps are obligatory)
replace it by a vertical step followed by $m$ backward horizontal steps 
and a vertical step followed by $n$ forward horizontal steps. What is
obtained by this procedure is joined with the terminal portion of
$P_I$ beginning from $M$.
In Figure~6 the circled points indicate where
the paths are cut into portions according to the above description.
\vskip10pt
\vbox{
$$
\Koordinatenachsen(5,9)(-3,0)
\Gitter(5,9)(-3,0)
\Pfad(3,0),2\endPfad
\Pfad(-1,1),1111\endPfad
\Pfad(-1,1),22\endPfad
\Pfad(-2,3),1\endPfad
\Pfad(-2,3),21112\endPfad
\Pfad(-1,5),11\endPfad
\Pfad(-1,5),211112\endPfad
\Pfad(1,7),11\endPfad
\Pfad(1,7),21\endPfad
\SPfad(-3,2),1111111\endSPfad
\SPfad(-3,4),1111111\endSPfad
\SPfad(-3,6),1111111\endSPfad
\DickPunkt(3,0)
\DickPunkt(2,8)
\DickPunkt(0,6)
\Kreis(-1,2)
\Kreis(1,4)
\Label\u{\RR^{\et_I}A_{\si(I)}}(3,0)
\Label\lo{M}(0,6)
\Label\o{E_I}(2,8)
\Label\ru{P_I}(1,5)
\hskip3cm
\raise3cm\hbox{$\longrightarrow\hskip3cm$}
\Koordinatenachsen(5,9)(-3,0)
\Gitter(5,9)(-3,0)
\Pfad(-3,0),2211112\endPfad
\Pfad(-2,3),111\endPfad
\Pfad(-2,3),212\endPfad
\Pfad(-2,5),1\endPfad
\Pfad(-2,5),2111112\endPfad
\Pfad(1,7),11\endPfad
\Pfad(1,7),21\endPfad
\SPfad(-3,2),1111111\endSPfad
\SPfad(-3,4),1111111\endSPfad
\SPfad(-3,6),1111111\endSPfad
\DickPunkt(-3,0)
\DickPunkt(2,8)
\DickPunkt(0,6)
\Kreis(1,2)
\Kreis(-1,4)
\Label\u{\RR^{1-\et_I}A_{\si(I)}}(-3,0)
\Label\lo{M}(0,6)
\Label\o{E_I}(2,8)
\Label\r{P_I'}(1,3)
$$
\centerline{\eightpoint Figure 6}
}
\vskip10pt

If none of the paths of $\P$ meet the $y$-axis consider all meeting
points between any two paths of $\P$. Choose the highest
meeting points, and among those the left-most meeting point, and 
then apply the Gessel--Viennot interchanging procedure, as was described
before in the proof of (1.1). 

Again it is easy to see that in both cases, by application of
$\Th_2$ to $\Th_2(\P)$, one arrives at $\P$ again. Consequently 
$\Th_2$ is a sign-reversing (with respect to $(-1)^{\V\et}\sgn\si$)
and weight-reversing (with respect to $w$) involution. 
\quad \quad \qed






\Refs

\ref\no \BereAA\by A.    Berele \yr 1986 
\paper A Schensted-type correspondence for the symplectic group
\jour J. Combin\. Theory Ser.~A\vol 43
\pages 320--328\endref

\ref\no \BrenAE\by F.    Brenti \yr 1993 
\paper Determinants of super-Schur functions, lattice paths, and dotted plane partitions 
\jour Adv\. in Math\. \vol 98 
\pages 27--64\endref

\ref\no \BrenAG\by F.    Brenti 
\paper Combinatorics and total positivity
\paperinfo preprint \endref

\ref\no \BrWeAA\by D. M. Bressoud and S.-Y. Wei \yr 1992 
\paper Determinental formulae for complete symmetric functions
\jour J. Combin\. Theory Ser.~A\vol 60
\pages 277--286\endref

\ref\no \ChGoAA\by S. H. Choi and D. Gouyou--Beauchamps \yr 1991 
\paper Enum\'eration de tableaux de Young semi-standard
\inbook Actes de 3eme Colloque de Series Formelles et Combinatoire Algebrique, Bordeaux 1991\eds M.~Delest, G.~Jacob, P.~Leroux
\publ LabRI
\publaddr Universit\'e Bordeaux~I
\pages 229---243\endref

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

\ref\no \ConcAA\by A.    Conca 
\paper Gr\"obner bases of ideals of minors of a symmetric matrix
\jour J. Algebra\toappear
\endref

\ref\no \ConcAB\by A.    Conca 
\paper Ladder determinantal rings
\paperinfo preprint \endref

\ref\no \CoHeAA\by A.    Conca and J. Herzog 
\paper On the Hilbert function of determinantal rings and their canonical module
\jour Proc\. Amer\. Math\. Soc\.\toappear
 \endref

\ref\no \DeViAA\by M.    Desainte--Catherine and G. Viennot \yr 1986 
\paper Enumeration of certain Young tableaux with bounded height
\inbook Combinatoire \'enum\'erative\eds G.~Labelle, P.~Leroux
\publ Springer--Verlag
\publaddr Berlin, Heidelberg, New York
\pages 58---67\endref

\ref\no \DoraAA\by W. F. Doran 
\paper A connection between alternating sign matrices and totally symmetric
self-com\-ple\-men\-tary plane partitions\jour J. Combin\. Theory
Ser.~A\vol 64\pages 265--288\endref

\ref\no \FuKrAA\by M.    Fulmek and C. Krattenthaler 
\paper Lattice path proofs for determinant formulas for symplectic and orthogonal characters
\paperinfo preprint\endref

\ref\no \GessAL\by I. M. Gessel \yr 1993 \paper Counting paths in Young's 
lattice\jour J. Statist\. Plann\. Inference\vol 34\pages 125--134\endref

\ref\no \GeKrAA\by I. M. Gessel and C. Krattenthaler 
\paper Cylindric partitions
\paperinfo preprint \endref

\ref\no \GeViAA\by I. M. Gessel and G. 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 G. Viennot \yr 1989 
\paper Determinants, paths, and plane partitions 
\paperinfo preprint\endref

\ref\no \GreCAA\by C.    Greene \yr 1992 
\paper Proof of a conjecture on immanents of the Jacobi--Trudi matrix 
\jour Linear Algebra Appl\. \vol 171 
\pages 65--79\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 \KratAQ\by C.    Krattenthaler \yr 1993 
\paper Non-crossing two-rowed arrays and summations for Schur functions\eds A.~Barlotti, M.~Delest, R.~Pinzani
\inbook Proc\. of the 5th Conference on Formal Power Series and Algebraic Combinatorics, Florence, 1993
\publ D.S.I., Universit\`a di Firenze
\pages 301--314\endref

\ref\no \KratAW\by C.    Krattenthaler 
\paper Non-crossing two-rowed arrays
\paperinfo in preparation
\jour \vol 
\pages \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 \KrMoAA\by C.    Krattenthaler and S. G. Mohanty \yr 1992 
\paper Counting tableaux with row and column bounds
\inbook Proceedings of the 4th Colloque de Series Formelles et Combinatoire Algebrique, Montreal 1992\eds P.~Leroux, C.~Reutenauer
\publ LaCIM
\publaddr Universit\'e Qu\'ebec \`a Montr\'eal
\pages 271--282\endref

\ref\no \KulkAB\by D. M. Kulkarni 
\paper Counting of path-like objects and coefficients of Hilbert polynomial of a determinantal ideal
\paperinfo preprint \endref

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

\ref\no \MacdAB\by I. G. Macdonald \yr 1979 
\book Symmetric Functions and Hall Polynomials 
\publ Oxford University Press
\publaddr New York/Lon\-don\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 \OkadAB\by S.    Okada \yr 1990 
\paper Partially strict shifted plane partitions
\jour J. Combin\. Theory Ser.~A\vol 53
\pages 143--156\endref

\ref\no \OkadAC\by S.    Okada \yr 1991 
\paper A Robinson--Schensted-type algorithm for $SO(2n,\Bbb C)$
\jour J. Algebra\vol 143
\pages 334--372\endref

\ref\no \ReWhAA\by J. B. Remmel and R. Whitney \yr 1983 
\paper A bijective proof of the hook formula for the number of column-strict tableaux with bounded entries
\jour Europ\. J. Combin\.\vol 4
\pages 45--63\endref

\ref\no \ReWhAB\by J. B. Remmel and R. Whitney \yr 1984 
\paper A bijective proof of the generating function for the number of reverse plane partitions via lattice paths
\jour Linear and Multilinear Algebra\vol 16
\pages 75--91\endref

\ref\no \RobyAA\by T. W. Roby \yr 1991 
\book Applications and extensions of Fomin's generalization of the Robinson--Schensted correspondence to differential posets
\publ Ph.D. thesis, M.I.T.
\publaddr Cambridge, Massachusetts\endref

\ref\no \SagaAF\by B. E. Sagan \yr 1989 
\paper The ubiquitous Young tableau
\inbook Invariant theory and tableaux\ed D.~Stanton
\publ The IMA Volumes in Math\. And Its Appl\., Vol.~19, Springer--Verlag
\publaddr New York, Berlin, Heidelberg
\pages 262--298\endref

\ref\no \SagaAK\by B. E. Sagan \yr 1992 
\paper Log concave sequences of symmetric functions and analogs of the Jacobi--Trudi determinants
\jour Trans\. Amer\. Math\. Soc\.\vol 329
\pages 795--811\endref

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

\ref\no \StemAG\by J. R. Stembridge 
\paper The enumeration of totally symmetric plane partitions
\paperinfo preprint \endref

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

\ref\no \SunaAA\by S.    Sundaram \yr 1986 
\book On the combinatorics of representations of $Sp(2n,\Bbb C)$
\publ Ph\. D. Thesis
\publaddr Massachusetts Institute of Technology\endref

\ref\no \UenKAA\by K.    Ueno \yr 1991 
\paper Lattice path proof of the ribbon determinant formula for Schur functions
\jour Nagoya Math\. J.\vol 124
\pages 55--59\endref

\endRefs
\enddocument
