

\TagsOnRight
\catcode`\@=11
\def\iddots{\mathinner{\mkern1mu\raise\p@\hbox{.}\mkern2mu
    \raise4\p@\hbox{.}\mkern2mu\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\catcode`\@=13
\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\RR{{\frak R}}
\def\v#1{{\vert#1\vert}}
\def\V#1{{\Vert#1\Vert}}

\subheading{5.4. Correspondences between tableaux and nonintersecting
lattice\linebreak paths}
Here we explain the connection between the major and strange major
counting of nonintersecting lattice paths and the computation of
generating functions for tableaux. The ideas which are used are the
celebrated Knuth correspondences \cite{24}, one of Burge's \cite{6,
p.~22}
modifications of it, the geometric interpretations of Knuth's
and Burge's correspondences due to Viennot \cite{42} and
Desainte-Catherine and Viennot \cite{10} and a refinement of Choi
and Gouyou--Beauchamps \cite{7}. Though our presentation sometimes
differs from the presentations in the cited papers, in fact all the
statements of this subsection are, at least implicitly, in these
papers. Therefore the proofs for the following Propositions will be
kept short and cursory. What could be called new is the observation
that the norm of tableaux carries over into the major index or strange
major index of nonintersecting lattice paths.

\medpagebreak
The main tools of the Knuth correspondences and its variants are
algorithms which insert a positive integer into a tableaux or
delete an integer from a tableaux, respectively.

We start with the algorithms ROW-INSERT and ROW-DELETE. Given a
tableau $\ta$ and a positive integer $x$ the algorithm ROW-INSERT
inserts $x$ into $\ta$ by the following procedure.

Algorithm ROW-INSERT \cite{24, p.~712}.
\roster
\item Compare $x$ with the elements of the first row of $\ta$. While
reading from left to right, replace the first element which is larger
than $x$ by $x$. If there is no larger element then add $x$ as last
element to the first row.
\item If an element was ``bumped" in the previous step, insert it
into the second row following the same rule. Repeat this with the
subsequent rows until the element to be inserted can be placed at the
end of a (possibly empty) row.
\item Denote the tableaux which results from this inserting procedure
by ROW-INSERT$(\ta,x)$.
\endroster

Given the output $\bar\ta=\text {ROW-INSERT}(\ta,x)$ of such an
inserting procedure, we are able to recover $\ta$ and $x$ if we know
the number $r$ of the row of $\bar\ta$ where ROW-INSERT stopped. This is
accomplished by the algorithm ROW-DELETE. Let $\bar\ta$ be a tableau and $r$
a positive integer.

Algorithm ROW-DELETE \cite{24, p.~713}.
\roster
\item Take the last element of the $r$-th row of $\bar\ta$. Use it to
bump and replace the right-most 
element of the $(r-1)$-th row that is smaller.
\item Take the bumped element and repeat this procedure in the
$(r-2)$-th row, etc.
\item The element which is finally bumped in the first row is denoted
by $x$, the remaining tableau by $\ta$. The output of $\text
{ROW-DELETE}(\bar\ta,r)$ is $(\ta,x)$.
\endroster

Dually, there are column insertion and column deletion. The
difference is that now we insert into the columns and that everywhere
strict order is replaced by weak order.

Algorithm COLUMN-INSERT \cite{24, p.~720}.
\roster
\item Compare $x$ with the elements of the first column of $\ta$. While
reading from top to bottom, replace the first element which is
greater or equal
to $x$ by $x$. If there is no such element then add $x$ as last
element to the first column.
\item If an element was ``bumped" in the previous step, insert it
into the second column following the same rule. Repeat this with the
subsequent columns until the element to be inserted can be placed at the
bottom of a (possibly empty) column.
\item Denote the tableaux which results from this inserting procedure
by\break COLUMN-INSERT$(\ta,x)$.
\endroster

Also with column-insertion, given the number $r$ of the column of the
tableau $\bar\ta=\text {COLUMN-INSERT}(\ta,x)$ where COLUMN-INSERT
stopped, we are able to recover $\ta$ and $x$, this time using
COLUMN-DELETE.

Algorithm COLUMN-DELETE \cite{24, p.~720}.
\roster
\item Take the last element of the $r$-th column of $\bar\ta$. Use it to
bump and replace the down-most 
element of the $(r-1)$-th column that is smaller or equal.
\item Take the bumped element and repeat this procedure in the
$(r-2)$-th column, etc.
\item The element which is finally bumped in the first column is denoted
by $x$, the remaining tableau by $\ta$. The output of $\text
{COLUMN-DELETE}(\bar\ta,r)$ is $(\ta,x)$.
\endroster


We begin with two correspondences for pairs of tableaux.
\proclaim{Proposition~28}There exists a bijection $\De_1$ between
pairs $(\ta_1,\ta_2)$ of tableaux of identical shape, with at most $r$
columns
and with parts between $1$ and $n$, and families $\frak
P=(P_1,\dots,P_r)$ of nonintersecting lattice paths,
$P_i:(i-1,-i+1)\to(n+i-1,n-i+1)$, $i=1,\dots,r$, such that
$$\ymaj_{1,0}\De_1(\ta)=n(\ta_1)+n(\ta_2).\tag5.4.1$$
(The extension of the strange major index $\ymaj$ 
to families of lattice paths is introduced in (4.0.8).) 
\endproclaim
\demo{Proof}First we give a bijection between pairs $(\ta_1,\ta_2)$
of tableaux of identical shape and two-line arrays $(u\mid
v)$, 
$$\pmatrix u_1&u_2&\dots&u_N\\v_1&v_2&\dots&v_N\endpmatrix\tag5.4.2$$
of positive integers which satisfy
$$\align i\le j\quad \Rightarrow\quad &\text {either}\quad u_i<u_j\\
&\text {or}\quad u_i=u_j\text { and }v_i\ge v_j.\tag5.4.3
\endalign$$
As an example of an array satisfying (5.4.3) consider the two-line array in
Figure~8. Given an array $(u\mid v)$ satisfying (5.4.3) we form a
sequence $(\ta_1^{(i)},\ta_2^{(i)})_{i=0,\dots,N}$ of pairs of
tableaux. We start with $\ta_1^{(0)}=\ta_2^{(0)}=\emptyset$
($\emptyset $ denotes the empty tableau). Then for $i=1,\dots,N$ we
set $\ta_1^{(i)}=\text{COLUMN-INSERT}(\ta_1^{(i-1)},v_i)$, and, if $r$
is the number of the column of $\ta_1{(i)}$ where COLUMN-INSERT
stopped while inserting $v_i$ into $\ta_1^{(i-1)}$,
 we place $u_i$ at the bottom of the $r$-th column of $\ta_2^{(i-1)}$
thus obtaining $\ta_2{(i)}$. Finally we set
$(\ta_1,\ta_2)=(\ta_1^{(N)},\ta_2^{(N)})$. In Figure~8 the reader
finds an example of a two-line array and a pair of tableaux which
correspond to each other by this procedure.

It can be seen that this mapping is a bijection between
pairs $(\ta_1,\ta_2)$ of tableaux of the same shape, with parts
between $1$  and $n$, and with exactly $r_0$ columns, and two-line
arrays $(u\mid v)$ satisfying (5.4.3) which consist of integers
between $1$ and $n$ and where the longest (weakly) decreasing
subsequence of $v$, that is a sequence
$$v_{i_1}\ge v_{i_2}\ge \dots\ge v_{i_j}\quad 
\text {with}\quad i_1\le i_2\le \dotsb\le i_j,
\text {\ \ with $j$ maximal,}
\tag5.4.4$$
has length $r_0$. The non-obvious part is the equality between the
number of columns of the tableaux and the maximal length of a
decreasing subsequence of the bottom row of the two-line array. Since
this statement is only implicit in existing papers \cite{24, 6,
sec.~3} we sketch a proof at the end of the proof of this
Proposition. For later use we denote the mapping from a two-line
array to a pair of tableaux by $K_C$.
In the tableaux in Figure~8 the length of the first row
is 3, and longest decreasing subsequences of the bottom row
of the two-line array in
Figure~8 for instance are $(4,4,2)$,
$(6,5,3)$, $(6,6,6)$, all being of length 3.


\vskip10pt

\vbox{\noindent
\centerline{\eightpoint {\smc Example} with $n=7$, $r_0=3$, $r=4$}
$$
\underset\text {\raise-10pt\hbox{1. pair of tableaux}}\to
{\(\smatrix \format\sa\c\s\c\s\c\se\\
\hlinefor7\\
&2&&4&&4&\\
\hlinefor7\\
&3&&5&&6&\\
\hlinefor7\\
&6&&6&\\
\hlinefor5\\
&7&\\
\hlinefor3\\
\endsmatrix,
\smatrix \format\sa\c\s\c\s\c\se\\
\hlinefor7\\
&1&&1&&3&\\
\hlinefor7\\
&2&&3&&4&\\
\hlinefor7\\
&5&&5&\\
\hlinefor5\\
&6&\\
\hlinefor3\\
\endsmatrix\)}
 \longleftrightarrow
\underset\text {\raise-10pt\hbox{2. two-line array}}\to
{\pmatrix 1\ 1\ 2\ 3\ 3\ 4\ 5\ 5\ 6\\
4\ 4\ 6\ 5\ 2\ 3\ 6\ 6\ 7\endpmatrix}
\longleftrightarrow\quad \hbox to0.3cm{\hss}
\Einheit0.4cm
\raise-1.6cm\hbox{$\underset\text {\raise-10pt\hbox{3. multiset of points}}\to
{\Koordinatenachsen(9,8)(0,0)
\Gitter(9,8)(0,0)
\DickPunkt(1,4)
\DickPunkt(1,4)
\DickPunkt(2,6)
\DickPunkt(3,5)
\DickPunkt(3,2)
\DickPunkt(4,3)
\DickPunkt(5,6)
\DickPunkt(5,6)
\DickPunkt(6,7)
\Kreis(1,0)
\Kreis(8,7)
\Label\o{\ssize(2)}(1,4)
\Label\o{\ssize(2)}(5,6)
\hskip3.5cm}$}
$$
$$\hskip1cm\raise1.5cm\hbox{$\longleftrightarrow$}\quad \hbox to0.5cm{\hss}
\Einheit0.4cm
{\Koordinatenachsen(9,8)(0,0)
\Gitter(9,8)(0,0)
\DickPunkt(1,4)
\DickPunkt(3,5)
\DickPunkt(5,6)
\Kreis(1,0)
\Kreis(8,7)
\hbox to-2pt{\hss}\raise2pt\hbox{
\DickPunkt(1,4)
\DickPunkt(2,6)
\DickPunkt(6,7)
\Pfad(1,0),22221221111211\endPfad}
\hbox to 2pt{\hss}
\Pfad(1,0),22221121121112\endPfad
\hbox to 2pt{\hss}
\raise-2pt\hbox{
\DickPunkt(3,2)
\DickPunkt(4,3)
\DickPunkt(5,6)
\Pfad(1,0),11221212221112\endPfad
\hskip4.5cm}}
\hskip-.3cm\raise1.5cm\hbox{$\longleftrightarrow$}\quad \quad \quad 
{\Einheit0.4cm
\Koordinatenachsen(11,8)(0,-3)
\Gitter(11,8)(0,-3)
\DickPunkt(1,3)
\DickPunkt(3,4)
\DickPunkt(5,5)
\Kreis(0,0)
\Kreis(7,7)
\Kreis(1,-1)
\Kreis(2,-2)
\Kreis(8,6)
\Kreis(9,5)
\Kreis(3,-3)
\Kreis(10,4)
\DickPunkt(0,4)
\DickPunkt(1,6)
\DickPunkt(5,7)
\Pfad(0,0),22221221111211\endPfad
\Pfad(1,-1),22221121121112\endPfad
\DickPunkt(4,0)
\DickPunkt(5,1)
\DickPunkt(6,4)
\Pfad(2,-2),11221212221112\endPfad
\Pfad(3,-3),11111112222222\endPfad
\hskip4cm}
$$
\vskip-1cm
\vbox{\eightpoint \hskip2.5cm\raise2cm\hbox{4. light and shadow}\hskip2cm 
\raise0.5cm\hbox{5. family of nonintersecting lattice
paths}}
\nobreak
\centerline{\eightpoint Figure 8}
}
\vskip10pt

Next the array $(u\mid v)$ is viewed geometrically by interpreting
$(u_i,v_i)$, $i=1,\dots,N$, as points (with multiplicity) in the
integer lattice $\Z^2$. Besides we add the points $(1,0)$ and
$(n+1,n)$ to this multiset of points. In the third picture of Figure~8 
these two points are indicated as circles. The symbol $(2)$ being
located above the points $(1,4)$ and $(5,6)$ indicates that these
points have multiplicity 2.

Now Viennot's {\it light and shadow} procedure \cite{42, 10} is
applied. We suppose that there is a light being located in the
North-West of the multiset of points. The {\it shadow} of a point
$(x,y)$ is defined to be the set of points $(x',y')\in\R^2$ with $x\le x'\le
n+1$ and $0\le y'\le y$. We consider the (North-West) {\it border} of the union of
the shadows of all the points of the multiset. This border is a
lattice path from $(1,0)$ to $(n+1,n)$. The North-East corners of
this path are elements of the given multiset. Now we remove one copy
of each of these North-East corners from the multiset. Then the
light and shadow procedure is repeated, as long as there are points
left. A moment's thought shows that if in a two-line array $(u\mid v)$
the maximal length of a (weakly) decreasing subsequence of $v$ is
$r_0$, then by the light and shadow procedure we obtain exactly $r_0$
lattice paths. By construction, these lattice paths may meet but do
not cross each other. Item~4 in Figure~8 displays the lattice paths
which in our example are obtained by this procedure.



Next we shift the $i$-th path in the direction $(i-2,-i+1)$,
$i=1,\dots,r_0$, thus obtaining a family $(P_1,\dots,P_{r_0})$ of
{\it nonintersecting} lattice paths, $P_i:(i-1,-i+1)\to(n+i-1,n-i+1)$,
$i=1,\dots,r_0$. Finally we add the paths $P_{r_0+1},\dots,P_r$, 
$P_i:(i-1,-i+1)\to(n+i-1,n-i+1)$, $i=r_0+1,\dots,r$, all of which
start with $n$ horizontal steps followed by $n$ vertical steps. In
our example the resulting family of nonintersecting lattice paths is
item~5 of Figure~8.

To verify (5.4.1), observe that in the correspondence between pairs
of tableaux and two-line arrays the elements are preserved. Therefore
the sum $n(\ta_1)+n(\ta_2)$ of the norms of the original tableaux
equals the sum of all the coordinates of the North-East corners of
the paths which are obtained by the light and shadow procedure
(item~4 in Figure~8). The contribution of a North-East corner $(x,y)$
to $\ymaj_{1,0}(P)$ of a path $P$ which starts in $(1,0)$ is just the
number of steps from $(1,0)$ to $(x,y)$ plus 1, that is
$(x+y-1)+1=x+y$. Hence $n(\ta_1)+n(\ta_2)$ also equals $\sum _{}
^{}\ymaj_{1,0}P$, where the sum is over all paths $P$ which are
obtained by the light and shadow procedure. The final shifting and
adding of paths converts this sum into $\sum _{i=1}
^{r}\ymaj_{1,-i+1}P_i$, $P_i$ being the $i$-th path of the resulting
family of nonintersecting paths. Comparison with (4.0.8) yields
(5.4.1). For the pair of tableaux $(\ta_1^{\text {ex}},\ta_2^{\text
{ex}})$, say, in Figure~8 we have $n(\ta_1^{\text {ex}})+
n(\ta_2^{\text {ex}})=43+30=73$. For the resulting family 
$\frak P^{\text {ex}}=
(P_1^{\text {ex}},P_2^{\text {ex}},P_3^{\text {ex}},P_4^{\text {ex}})$ of
nonintersecting lattice paths we have 
$$\align
\ymaj_{1,0}(\frak P^{\text {ex}})&=\ymaj_{1,0}(P_1^{\text {ex}})+
\ymaj_{1,-1}(P_2^{\text {ex}})+\ymaj_{1,-2}(P_3^{\text
{ex}})+\ymaj_{1,-3}(P_4^{\text {ex}})\\
&=26+24+23+0=73,\endalign$$
in accordance with (5.4.1).

\smallskip
As promised, at the end we sketch a proof that the mapping $K_C$ that
was defined above and maps a two-line array $(u\mid v)$ to a pair of
tableaux $(\ta_1,\ta_2)$ has the property that the longest decreasing
subsequence of $v$ (see (5.4.4)) has length $r_0$ if and only if the
number of columns in $\ta_1$ and $\ta_2$ is $r_0$. This can be seen
in several different ways. We decide to prove it by means of
Viennot's \cite{42, 38, sec.~3.8} geometric interpretation of the
Knuth correspondence since we shall also need it at another place.
Actually, in \cite{42, 38, sec.~3.8} only the Robinson--Schensted
correspondence is considered. But it is easy to see that everything
carries over to the Knuth correspondence. 

Assuming that the reader is
already familiar with either \cite{42} or \cite{38, sec.~3.8}, 
we briefly recall Viennot's construction.
Let $(u\mid v)$ be a two-line array  of the form (5.4.2) such that 
$$\align i\le j\quad \Rightarrow\quad &\text {either}\quad u_i<u_j\\
&\text {or}\quad u_i=u_j\text { and }v_i\le v_j.\tag5.4.5
\endalign$$
Note that this differs from (5.4.3) in the behaviour of $v_i$'s
beneath equal $u_i$'s.
Suppose that with this two-line array we do the same as under the
mapping $K_C$, but using ROW-INSERT instead of COLUMN-INSERT. Let us
denote this mapping by $K_R$ and the resulting pair of tableaux by
$(P_R,Q_R)$. Again $(u\mid v)$ is viewed as a multiset of points in
$\Z^2$, only that now $(1,0)$ and $(n+1,n)$ are not added. Next we
assume a light to be located in the South-West of the multiset of
points. By light and shadow we obtain a set of lattice paths, each
having exactly one infinite horizontal and one infinite vertical ray.
Viennot's theorem says that we can read off the first row of $P_R$ by
the $y$-coordinates of the horizontal rays. Likewise, we can read off
the first row of $Q_R$ by the $x$-coordinates of the vertical rays.
In order to get the second rows, we take the ``skeletons" of the
paths (see \cite{42, 38, sec.~3.8}), apply light and shadow and read
the $y$-coordinates of the horizontal rays and the $x$-coordinates of
the vertical rays, as before. This procedure is iterated to obtain
the remaining rows of $P_R$ and $Q_R$. Simplifying, we say `{\it with a
light in the South-West the rows of $P_R$ can be read off from the
right and the rows of $Q_R$ can be read off from the top}'. This
terminology clearly is motivated by the picture of the construction.

So far we considered ROW-INSERTion. What we need is the analogue of
Viennot's construction for COLUMN-INSERTion. Let $(u\mid v)$ be a
two-line array, ordered according to (5.4.3). Let $(P_C,Q_C)$ be the
pair of tableaux that results from $(u\mid v)$ by applying $K_C$.
Again interpret $(u\mid v)$ as a multiset of points in $\Z^2$. Our
claim is that {\it with a light located in the South-East the rows of $P_C$
can be read off from the left, and that with a light in the
North-West the rows of $Q_C$ can be read off from the bottom}. This is
the geometric interpretation of the COLUMN-Knuth correspondence
$K_C$. It does not seem to have been recorded before. It is
easily checked for our example in Figure~8 (items 1 and 4).

First we turn to the reading of $P_C$. It is known that if the bottom
row $v$ of the two-line array by repeated COLUMN-INSERT is mapped to
a tableau we would obtain the same as when mapping
$v^r:=v_Nv_{N-1}\dots v_1$, the reversion of $v$, to a tableau by
using repeated ROW-INSERT. This is the contents of e.g\. \cite{38,
Theorem~4.8.8; the equation should read $T(\check \pi^r)=T'(\check\pi)$,
where $T'$ denotes application of $R-S-K'$, the repeated
COLUMN-INSERTion}. Hence, if we apply $K_R$ to $(\tilde u\mid v^r)$,
where $v^r$ is as before and $\tilde u$ is defined by $\tilde
u_i=U-u_{N-i+1}$, $i=1,2,\dots,N$, with $U$ larger than all $u_i$'s,
the resulting tableau $P_R$ would be the same as the tableau $P_C$
which is obtained by applying $K_C$ to $(u\mid v)$. Note that geometrically the
multiset of points corresponding to $(\tilde u\mid v^r)$ results from
the multiset of points corresponding to $(u\mid v)$ by a reflection
in the vertical line $x=U/2$. Also, if $(u\mid v)$ is ordered
according to (5.4.3) then $(\tilde u\mid v^r)$ is ordered according
to (5.4.5). This guarantees that application of $K_R$ to $(\tilde
u\mid v^r)$ is indeed allowed. But we know how to read the rows of $P_R$:
With a light in the South-West of $(\tilde u\mid v^r)$ (viewed as
multiset of points) the rows of $P_R$ are read from the right. Since
$P_R$ (corresponding to $(\tilde u\mid v^r)$) is the same as $P_C$
(corresponding to $(u\mid v)$), and since $(u\mid v)$ results from $(\tilde
u\mid v^r)$ by a reflection in the vertical line $x=U/2$, we know how
to read $P_C$: The light in the South-West under the reflection in
the vertical line becomes a light in the South-East, instead of
reading from the right after the reflection we are reading from the
left. This proves the claim about the reading of $P_C$.

In order to prove the claim about the reading of $Q_C$, we recall
another standard property of the COLUMN-Knuth correspondence $K_C$: If
$(u\mid v)$ by $K_C$ is mapped to $(P_C,Q_C)$ then the transpose 
$(u\mid v)^t$ by $K_C$ is mapped to $(Q_C,P_C)$. The transpose
$(u\mid v)^t$ is defined by interchanging the top and bottom row of
$(u\mid v)$ and then reordering the pairs $\binom {v_i}{u_i}$
according to (5.4.3). A proof of this fact is sketched in \cite{6,
p.~21}. Note that, geometrically, the multiset of points
corresponding to $(u\mid v)^t$ results from the multiset of points
corresponding to $(u\mid v)$ by a reflection in the diagonal $x=y$.
We have already proved that the first tableau, $P_C$, that is obtained by
$K_C$ is read with a light in the South-East from the left. Hence,
$Q_C$ can be read off $(u\mid v)^t$ with a light in the South-East
from the left. After reflecting back we see that $Q_C$ can be read
off $(u\mid v)$ with a light in the North-West from the bottom.

Now we are prepared to attack our original problem. Let $(u\mid v)$
be a two-line array ordered according to (5.4.3). It is easy to see
that the longest (weakly) decreasing subsequence of $v$ has length
$r_0$ if and only if with a light in the South-East (or in the
North-West) light and shadow would produce exactly $r_0$ lattice
paths. But, by our geometric interpretation of $K_C$, this means that
in the pair of tableaux $(\ta_1,\ta_2)$ that corresponds to $(u\mid v)$
under application of $K_C$ the first rows of $\ta_1$ and $\ta_2$
have length $r_0$.
\quad \quad \qed
\enddemo
Quite analogously, we obtain a result for pairs of tableaux with odd
entries.
\proclaim{Proposition~29}There exists a bijection $\De_2$ between
pairs $(\ta_1,\ta_2)$ of tableaux of identical shape, with at most $r$
columns
and with only odd parts which lie between $1$ and $2n-1$, and families $\frak
P=(P_1,\dots,P_r)$ of nonintersecting lattice paths,
$P_i:(2i-2,-2i+2)\to(2n+2i-2,2n-2i+2)$, $i=1,\dots,r$, where the
North-East corners of the paths have odd coordinates, such that
$$\maj\De_2(\ta)=n(\ta_1)+n(\ta_2).\tag5.4.6$$
(The extension of the major index 
to families of lattice paths is introduced in (3.0.1).) 
\endproclaim
\demo{Proof} We do almost the same as in the previous proof. First,
as described above, we map a pair $(\ta_1,\ta_2)$ of tableaux 
of the type under consideration onto its corresponding two-line
array. This array is interpreted geometrically as multiset of points
in $\Z^2$ as before, but now we add the points $(0,0)$ and $(2n,2n)$
as the future starting and final points of the paths which
are subsequently constructed by the light and shadow procedure. Next
the $i$-th path is shifted in the direction $(2i-2,-2i+2)$. If $r_0$
is the number of columns in $\ta_1$ (and hence also in $\ta_2$), then
by now we obtained $r_0$ pairwise nonintersecting paths,
$P_1,\dots,P_{r_0}$. Finally we add the paths $P_{r_0+1},\dots,P_r$, 
$P_i:(2i-2,-2i+2)\to(2n+2i-2,2n-2i+2)$, $i=r_0+1,\dots,r$, all of which
start with $2n$ horizontal steps followed by $2n$ vertical steps. 

The asserted properties of this bijection are readily verified.\quad \quad
\qed

\enddemo

Now we turn to correspondences for single tableaux. They are based on
Burge's correspondence \cite{6, p.~22}.
\proclaim{Proposition~30}There exists a bijection $\De_3$ between
tableaux $\ta$ with rows of even lengths, with at most $2r$ columns,
and with parts between $1$ and $n$, and families $\frak
P=(P_1,\dots,P_r)$ of nonintersecting lattice paths which lie below
the line $x=y$, $P_i:(i-1,-i+1)\to(n+i,n+2-i)$,  $i=1,\dots,r$, such that
$$\maj\De_3(\ta)=n(\ta).\tag5.4.7$$
Moreover $\De_3$ has the property that if the first row of $\ta$ has
length $2r$ and if the
last entry in the first row of $\ta$ is $h$ then the $r$-th path of
the family $\De_3(\ta)$ starts with $h$ horizontal steps followed by
a vertical step. If the length of the first row of $\ta$ is less than
$2r$ then the $r$-th path of $\De_3(\ta)$ starts with $n+1$
horizontal steps (of course followed by $n+1$ vertical steps).
\endproclaim
\demo{Proof}We follow Desainte--Catherine and Viennot \cite{10},
but we present the tab\-leaux in English notation.

First we set up a bijection between tableaux $\ta$ with even rows and
two-line arrays $(u\mid v)$ of the form (5.4.2) which satisfy
(5.4.3),
and in addition satisfy
$$u_i\ge v_i\quad \text {for }i=1,2\dots,N.\tag5.4.8$$
Given such an array $(u\mid v)$ we form the sequence
$(\ta^{(i)})_{i=0,\dots,N}$  of tableaux, where $\ta^{(0)}$ is the
empty tableau and $\ta^{(i)}$ is obtained from $\ta^{(i-1)}$ and the
pair $(u_i,v_i)$ in the following way. Insert $v_i$ into $\ta^{(i-1)}$
using COLUMN-INSERT. Then add $u_i$ at the end of the row of
COLUMN-INSERT$(\ta^{(i-1)},v_i)$ where COLUMN-INSERT stopped. The
resulting tableau is $\ta^{(i)}$, $i=1,\dots,N$. Finally we set
$\ta=\ta^{(N)}$. The tableau and the two-line array in Figure~9
correspond to each other by this procedure.

It can be seen that this mapping is a bijection between tableaux
with even rows, with exactly $2r_0$ columns, and with parts between
$1$ and $n$, and two-line arrays (5.4.2) satisfying (5.4.3) and
(5.4.8) where the longest (weakly) decreasing subsequence of $v$,
i.e\. a subsequence satisfying (5.4.4),
equals $r_0$. Again, the non-obvious part is the correspondence between the
number of columns of the tableau and the maximal length of a
decreasing subsequence of the bottom row of the two-line array. 
Also this statement has not been proved explicitly, therefore
we sketch a proof at the end of the proof of this
Proposition. For later use we denote the mapping from a two-line
array to a tableau with even rows by $K_E$.
In the tableau in Figure~9 the length of the first row
is 6, and the longest decreasing subsequences of the two-line array in Figure~9
are $(3,3,1)$ and $(3,3,2)$, both being of
length 3.

Again the array $(u,v)$ is interpreted as multiset of points
$(u_i,v_i)$ in $\Z^2$. Because of (5.4.8) all the points are located below
or on the diagonal $x=y$. This time we add the points $(0,0)$ and $(n+1,n+1)$.
Once more the light and shadow procedure is performed, yielding a set
of paths, all of which running from $(0,0)$ to $(n+1,n+1)$, which do not
cross each other and lie below $x=y$. If the maximal length  of a
(weakly) decreasing subsequence of $v$ is $r_0$, then by the light and
shadow procedure we obtain exactly $r_0$ paths. Shifting the $i$-th
path in the direction $(i-1,-i+1)$ gives a family $(P_1,\dots,P_{r_0})$
of nonintersecting lattice paths which lie below $x=y$,
$P_i:(i-1,-i+1)\to(n+i,n-i+2)$. Finally the paths
$P_{r_0+1},\dots,P_r$, $P_i:(i-1,-i+1)\to(n+i,n-i+2)$, are added,
each of them starting with $n+1$ horizontal steps followed by $n+1$
vertical steps. This sets up the desired bijection. Relation (5.4.7) can
be readily verified using similar arguments to those in the proof of
Proposition~28. For our tableau $\ta^{\text {ex}}$, say, in Figure~9
we have $n(\ta^{\text {ex}})=33$, while for the corresponding family
$\frak P^{\text {ex}}=
(P_1^{\text {ex}},P_2^{\text {ex}},P_3^{\text {ex}})$ of
nonintersecting lattice paths in Figure~9 we have $\maj P_1^{\text
{ex}}+\maj P_2^{\text {ex}}+\maj P_3^{\text {ex}}=17+6+10=33$, in
accordance with (5.4.7).

\vskip10pt

\vbox{\noindent
\centerline{\eightpoint {\smc Example} with $n=5$, $r_0=r=3$, $h=3$}
$$
\underset\text {\raise-10pt\hbox{1. tableau with even rows}}\to
{\smatrix \format\sa\c\s\c\s\c\s\c\s\c\s\c\se\\
\hlinefor{13}\\
&1&&1&&2&&3&&3&&3&\\
\hlinefor{13}\\
&2&&3&&3&&4&\\
\hlinefor9\\
&4&&4&\\
\hlinefor5\\
\endsmatrix}
\quad \longleftrightarrow\quad 
\underset\text {\raise-10pt\hbox{2. two-line array}}\to
{\pmatrix 2\ 3\ 3\ 3\ 4\ 4\\
1\ 3\ 3\ 1\ 4\ 2\endpmatrix}
\quad \longleftrightarrow\quad \hbox to0.5cm{\hss}
\Einheit0.4cm
\raise-1cm\hbox{$\underset\text {\raise-10pt\hbox{3. multiset of points}}\to
{\Koordinatenachsen(7,7)(0,0)
\Gitter(7,7)(0,0)
\Diagonale(-1,-1){8}
\DickPunkt(2,1)
\DickPunkt(3,3)
\DickPunkt(3,3)
\DickPunkt(3,1)
\DickPunkt(4,4)
\DickPunkt(4,2)
\Kreis(0,0)
\Kreis(6,6)
\Label\o{\ssize(2)}(3,3)
\hskip3cm}$}
$$
$$\hskip1cm\raise0.5cm\hbox{$\longleftrightarrow$}\quad \hbox to1cm{\hss}
\Einheit0.4cm
{\Koordinatenachsen(7,7)(0,0)
\Gitter(7,7)(0,0)
\Diagonale(-1,-1){8}
\DickPunkt(3,3)
\Kreis(0,0)
\Kreis(6,6)
\hbox to-2pt{\hss}\raise2pt\hbox{
\DickPunkt(2,1)
\DickPunkt(3,3)
\DickPunkt(4,4)
\Pfad(0,0),112122121122\endPfad}
\hbox to 2pt{\hss}
\Pfad(0,0),111222111222\endPfad
\hbox to 2pt{\hss}
\raise-2pt\hbox{
\DickPunkt(3,1)
\DickPunkt(4,2)
\Pfad(0,0),111212112222\endPfad
\hskip3.5cm}}
\quad \raise0.5cm\hbox{$\longleftrightarrow$}\quad \quad 
{\Einheit0.4cm
\Koordinatenachsen(9,7)(0,-2)
\Gitter(9,7)(0,-2)
\Diagonale(-1,-1){8}
\DickPunkt(2,1)
\DickPunkt(3,3)
\DickPunkt(4,4)
\Kreis(0,0)
\Kreis(6,6)
\Kreis(1,-1)
\Kreis(2,-2)
\Kreis(7,5)
\Kreis(8,4)
\DickPunkt(4,2)
\DickPunkt(5,-1)
\DickPunkt(6,0)
\Pfad(0,0),112122121122\endPfad
\Pfad(1,-1),111222111222\endPfad
\Pfad(2,-2),111212112222\endPfad
\hskip3.5cm}
$$
\vskip-0.5cm
\vbox{\eightpoint \hskip1.8cm\raise1.6cm\hbox{4. light and
shadow}\hskip2.3cm 
\raise0.6cm\hbox{5. family of nonintersecting lattice
paths}}
\nobreak
\centerline{\eightpoint Figure 9}
}
\vskip10pt

Finally we have to confirm the last two assertments of the
Proposition. In case that the tableau has less than $2r$ columns, by
the light and shadow procedure less than $r$ paths would be obtained.
Hence $P_r$ would be one of the added paths starting with $n+1$
horizontal steps followed by $n+1$ vertical steps. This proves the
last assertment. To establish the next-to-last assertment, observe
that if $P_r$ starts with $h$ steps followed by a vertical step
there is a $\bar v$ such that the point $(h,\bar v)$ is the first
North-East corner of the $r$-th path of the family of paths that is
obtained by the light and shadow procedure. So the corresponding
two-line array looks like
$$\pmatrix u_1&\hdots&u_{k-1}&h&u_{k+1}&\hdots&u_N\\
v_1&\hdots&v_{k-1}&\bar v&v_{k+1}&\hdots&v_N\endpmatrix.\tag5.4.9$$
Besides, $\bar v$ is the last element in a decreasing
subsequence
$(v_{i_1},\dots,v_{i_{r-1}},\bar v)$ of $v$ of maximal length. 
Also, all the maximal decreasing subsequences of the sequence
$$(v_1,\dots,v_{k-1})\tag5.4.10$$
have length $r-1$. Now recall that in order to obtain the tableau
$\ta$ that corresponds to the array (5.4.9), we have to form the
sequence $\ta^{(0)},\ta^{(1)},\dots,\ta^{(N)}$ of tableaux by using
the array (5.4.9) and this insertion procedure. Since all the maximal
decreasing subsequences of the sequence (5.4.10) have length $r-1$, 
the length of the first row of $\ta^{(k-1)}$ is $2r-2$. Next we have to
COLUMN-INSERT $\bar v$ into $\ta^{(k-1)}$. Since $\bar v$ belongs
to a maximal decreasing subsequence of length $r$ in the bottom row
of (5.4.9),
COLUMN-INSERT$(\ta^{(k-1)},\bar v)$ will stop at the end of the first
row of $\ta^{(k-1)}$. Subsequently, $h$ is added at the end of the
first row of COLUMN-INSERT$(\ta^{(k-1)},\bar v)$ to obtain
$\ta^{(k)}$. Everything will be established if we show that $h$
cannot be bumped during the remaining insertions. 
But this is obvious, because if $h$ is bumped a new column would be
created. Thus the resulting tableau $\ta$ would consist of more than $2r$
columns, a contradiction to our assumption.

\smallskip
As promised, at the end we sketch a proof that the 
mapping $K_E$ that 
was defined above and maps a two-line array $(u\mid v)$ 
which satisfies (5.4.3) and (5.4.8) to a 
tableau $\ta$ with even rows has the property that the longest decreasing
subsequence of $v$ (see (5.4.4)) has length $r_0$ if and only if the
number of columns of $\ta$ is $2r_0$.
What we need is the following relation between the maps $K_E$ and
$K_C$ (the latter appeared in the proof of Proposition~28) which was
stated in \cite{6, sec.~3} but was not proved there: 
There holds the relation
$$K_C\big((u\mid v)\cup(v\mid u)\big)=\big(K_E((u\mid v)),K_E((u\mid
v))\big).\tag 5.4.11$$
Here, the symbol $(u\mid v)\cup(v\mid u)$ denotes the ``union" of
$(u\mid v)$ and $(v\mid u)$. This is formed by concatenating $(u\mid
v)$ and $(v\mid u)$ and reordering the concatenation according to
(5.4.3). For example, the union of $\binom{2\ 3\ 3\ 3}{1\ 3\ 3\ 1}$
and $\binom{1\ 3\ 3\ 1}{2\ 3\ 3\ 3}$ is $\binom{1\ 1\ 2\ 3\ 3\ 3\ 3\
3}{3\ 2\ 1\ 3\ 3\ 3\ 3\ 1}$. Note that, when viewing $(u\mid v)$ and
$(v\mid u)$ as multisets of points in $\Z^2$, the union $(u\mid
v)\cup(v\mid u)$, as a multiset of points, indeed equals the multiset
union of $(u\mid v)$ and $(v\mid u)$. More precisely, $(u\mid v)\cup(v\mid u)$
is the union of the multiset of points corresponding to
$(u\mid v)$ and its reflection in the
diagonal $x=y$. Thus $(u\mid v)\cup(v\mid u)$, as multiset of points,
is symmetrical and all 
pairs of the form $\binom {w}{w}$ occur in $(u\mid v)\cup(v\mid u)$
with an even multiplicity.

If we suppose that the relation (5.4.11) between
the maps $K_C$ and $K_E$ holds then the above claim is easily proved:
Obviously the maximal length of a decreasing subsequence of $v$, the
bottom row of $(u\mid v)$, is $r_0$ if 
and only if the maximal length of a decreasing subsequence of the
bottom row of the union $(u\mid v)\cup(v\mid u)$ is $2r_0$. (This is
best seen geometrically.) On the other hand, in the proof of
Proposition~28 we have shown that the maximal length of a decreasing
subsequence of $(u\mid v)\cup(v\mid u)$ has length $2r_0$ if and only
if the tableaux that result from $(u\mid v)\cup(v\mid u)$ under
application of $K_C$ have exactly $2r_0$ columns. Thus, by (5.4.11)
our claim is established.

What remains is to prove (5.4.11). Let $(u\mid v)$ be a two-line array
satisfying (5.4.3) and (5.4.8), and let $\ta$ be the tableau
that results from $(u\mid v)$ under application of $K_E$.
Since $(u\mid v)\cup(v\mid u)$
as a multiset of points is symmetric, application of $K_C$ to 
$(u\mid v)\cup(v\mid u)$ yields a pair of identical tableaux. This is
a standard property of $K_C$ (cf\. \cite{6, p.~21}). Therefore we
only have to prove that the {\it first} tableau equals $\ta=K_E((u\mid v))$.
It is also true that application of $K_C$ to $(u\mid v)\cup(v\mid u)$
yields a pair of (identical) tableaux with only {\it even} rows since 
pairs of the form $\binom {w}{w}$ always occur with an even
multiplicity in $(u\mid v)\cup(v\mid u)$. Again this is standard 
(cf\. \cite{6, p.~21}).

We perform an induction on the length
$N$ of the two-line array $(u\mid v)$. The relation (5.4.11) is
trivially true for $N=0$. Let $\bar u$ denote
the sequence $u_1u_2\dots u_{N-1}$, and similarly for $\bar v$.
Suppose that (5.4.11) has already been
proved for all two-line arrays of length $N-1$. Using the geometric
interpretation of $K_C$ that was developed in the proof of
Proposition~28, this means that the tableau $\bar \ta$ that results
from $(\bar u\mid \bar v)$ by application of
$K_E$ can be read off
$(\bar u\mid \bar v)\cup(\bar v\mid \bar u)$ with a light in the
South-East from the left. 
To obtain $\ta$ we have to insert the pair $(u_N,v_N)$ into the
tableau $\bar\ta$ in the way described above. That is, first $v_N$ is
COLUMN-INSERTed into $\bar\ta$ and then $u_N$ is placed at the end of
the row where the algorithm stopped. Geometrically,
COLUMN-INSERTion of $v_N$ into $\bar\ta$ means to add the point
$(u_N,v_N)$ to the multiset of points
$(\bar u\mid \bar v)\cup(\bar v\mid \bar u)$ and with a light in the
South-East read from the left. Now $u_N$ is placed at the end of the
row where the COLUMN-INSERTion stopped. Thus $\ta$ is obtained.
We have to show that this is
the same as reading the multiset of points corresponding to
$(u\mid v)\cup(v\mid u)$ 
with a light in the South-East from the left. The multiset 
of points corresponding to
$(u\mid v)\cup(v\mid u)$ is obtained from the multiset
of points corresponding to
$(\bar u\mid \bar v)\cup(\bar v\mid \bar u)\cup (u_N\mid v_N)$ by
adding the point $(v_N,u_N)$. It is easy to see that the effect
that is caused by the addition of $(v_N,u_N)$ 
when reading with a light in the South-East from the left
will be the placement of $u_N$ at the end of a row. 
This is due to the fact that, because of the order (5.4.3), the point
$(v_N,u_N)$ is among the highest points of $(u\mid v)\cup(v\mid u)$,
viewed as a multiset of points, and among all those it is the left-most.
Now, the tableau, say $\ta'$, that is read
off $(\bar u\mid \bar v)\cup(\bar v\mid \bar u)\cup (u_N\mid v_N)$ is
a tableau whose shape differs from the shape of $\bar\ta$, a tableau with only even rows, 
just in one cell. Hence, $\ta'$ has exactly one row of odd length. 
And $\ta'$ differs from the
reading of $(u\mid v)\cup(v\mid u)$ by the placement of $u_N$ at the
end of a row of $\ta'$. The result of the placement of $u_N$ in $\ta'$
will again be a tableau with only
even rows since, as was remarked above, 
pairs of the form $\binom ww$ occur with an even
multiplicity in $(u\mid v)\cup(v\mid u)$.
But because there is exactly one odd row in $\ta'$ this must
be the row where $u_N$ is added. Besides this is the row where the
COLUMN-INSERTion of $v_N$ into $\bar\ta$ stopped. Thus the reading of
$(u\mid v)\cup(v\mid u)$ and the tableau $\ta$ agree.
\quad \quad
\qed
\enddemo

If we apply the same arguing to tableaux with only odd entries we
obtain an analogous result.
\proclaim{Proposition~31}There exists a bijection $\De_4$ between
tableaux $\ta$ with rows of even lengths, with at most $2r$ columns,
and with only odd parts which lie
 between $1$ and $2n-1$, and families $\frak
P=(P_1,\dots,P_r)$ of nonintersecting lattice paths which lie below
the line $x=y$, $P_i:(2i-2,-2i+2)\to(2n+2i-2,2n-2i+2)$,  $i=1,\dots,r$, 
where the North-East corners of the paths have odd coordinates, such
that
$$\maj\De_4(\ta)=n(\ta).\tag5.4.12$$
Moreover $\De_4$ has the property that if the first row of $\ta$ has
the length $2r$ and if the
last entry in the first row of $\ta$ is $2h+1$ then the $r$-th path of
the family $\De_4(\ta)$ starts with $2h+1$ horizontal steps followed by
a vertical step. If the length of the first row of $\ta$ is less than
$2r$ then the $r$-th path of $\De_4(\ta)$ starts with $2n$
horizontal steps (of course followed by $2n$ vertical steps).
\quad \quad \qed
\endproclaim
Using the idea of Choi and Gouyou--Beauchamps, Proposition~30 can be
extended to tableaux with a prescribed number of odd rows.
\proclaim{Proposition~32}There exists a bijection $\De_5$ between
tableaux $\ta$ with $p$ odd rows, with at most $2r$ columns,
and with parts between $1$ and $n$, and pairs $(\frak
P,S)$, where $\frak P=(P_1,\dots,P_r)$ is a family 
 of nonintersecting lattice paths which lie below
the line $x=y$, $P_i:(i-1,-i+1)\to(n+i,n+2-i)$,  $i=1,\dots,r$, 
with the property that if $P_r$ starts with $h$ horizontal steps
followed by a vertical step then $S$ is a $p$-subset of
$\{1,2,\dots,h-1\}$. (By convention, if $h=1$ the set
$\{1,2,\dots,h-1\}$ is meant to be the empty set.) 
Moreover, $\De_5$ satisfies
$$\maj\frak P+\V S=n(\ta)\quad \quad \text {if }(\frak
P,S)=\De_5(\ta).\quad \quad \raise-10pt\hbox{$\qed$}\tag5.4.13$$
\endproclaim
\demo{Proof}Let $\ta$  be a tableau of the considered type. 

First we consider the case that $\ta$ has exactly $2r$ columns.
We apply the algorithm
ROW-DELETE to each of the odd rows of $\ta$, beginning with the
lowest and working up to the highest. We thus obtain a sequence
$n_1,n_2,\dots,n_p$ of integers, the $n_1$ being deleted by the first
application of ROW-DELETE, etc. Besides we are left with a tableaux
$\ta_e$ with only even rows. Clearly, the last element of the first
row of $\ta_e$ is
greater than $n_i$ for all $i=1,\dots,p$. Denote this last element of
$\ta_e$ by $h$. By the last consideration
 $\{n_1,n_2,\dots,n_p\}$ is a subset of
$\{1,2\dots,h-1\}$. The observation that the integers
$n_1,n_2,\dots,n_p$ are in increasing order shows that by
successively inserting $n_p,n_{p-1},\dots,n_1$ into $\ta_e$ utilizing
ROW-INSERT, the above procedure could be inverted. Hence it is a
bijection between tableaux with $p$ odd rows, with exactly $2r$ columns,
and with parts between $1$ and $n$, and pairs $(\ta_e,S)$, where
$\ta_e$ is a tableau with even rows, with exactly $2r$ columns,
and with parts between $1$ and $n$, with the property that if the
last element in the first row of $\ta_e$ is $h$, then $S$ is a $p$-subset
of $\{1,2,\dots,h-1\}$. By Proposition~30 these tableaux are in one-to-one 
correspondence with families $\frak P=(P_1,\dots,P_r)$ of
nonintersecting lattice paths which lie below $x=y$,
$P_i:(i-1,-i+1)\to(n+i,n+2-i)$, where the path $P_r$ starts with $h$
horizontal steps followed by a vertical one. Note that in the above
considerations $h$, since being an element of $\ta_e$, can at most be
$n$. What is missing is the case $h=n+1$.

Now let the length of the first row of $\ta$ be smaller than
$2r$. We apply the same method. Use ROW-DELETE repeatedly
to get rid of the odd
rows of $\ta$. We thus obtain a pair $(\ta_e,S)$ where $\ta_e$ is a
tableau with properties as before but with less than $2r$ columns,
and where $S$ is a $p$-subset of $\{1,2,\dots,n\}$. But tableaux $\ta_e$
with less than $2r$ columns by 
Proposition~30 uniquely correspond to families $\frak
P=(P_1,\dots,P_r)$ of nonintersecting lattice paths with the
properties as before, but where
$P_r$ starts with $n+1$ horizontal steps followed by
$n+1$ vertical steps. This supplies us with the case $h=n+1$.

Combining both cases we have a bijection between tableaux $\ta$ and
pairs $(\frak P,S)$ of families $\frak P$ of nonintersecting lattice
paths and $p$-subsets $S$ as desired. In addition, from (5.4.7) and
the fact that $S$ consists of some elements of $\ta$, we derive
(5.4.13).\quad \quad \qed
\enddemo
Again the same can be done for tableaux with odd parts.
\proclaim{Proposition~33}There exists a bijection $\De_6$ between
tableaux $\ta$ with $p$ odd rows, with at most $2r$ columns,
and with only odd parts which lie
 between $1$ and $2n-1$, and pairs $(\frak
P,S)$, where $\frak P=(P_1,\dots,P_r)$ is a family 
 of nonintersecting lattice paths which lie below
the line $x=y$, $P_i:(2i-2,-2i+2)\to(2n+2i-2,2n-2i+2)$,  $i=1,\dots,r$, 
where the North-East corners of the paths have odd coordinates, 
with the property
that if $P_r$ starts with $2h+1$ horizontal steps
followed by a vertical step then $S$ is a $p$-subset of
$\{1,3,\dots,2h-1\}$. (By convention, if $h=0$ the set
$\{1,3,\dots,2h-1\}$ is meant to be the empty set.)
Moreover, $\De_6$ satisfies
$$\maj\frak P+\V S=n(\ta)\quad \quad \text {if }(\frak
P,S)=\De_6(\ta).\tag5.4.14$$
\endproclaim






\subheading{5.5. A determinant lemma}
Let the {\it degree} of a {\it Laurent polynomial} $p(X)=\sum _{i=M}
^{N}a_ix^i$, $M,N\in \Z$, $a_i\in \R$ and $a_N\ne0$, be defined by
$\deg p:=N$.
\proclaim{Lemma~34}Let $X_1,X_2,\dots,X_r,A_2,A_3,\dots,A_r,C$ be
indeterminates. If $p_0,p_1,\mathbreak\dots, p_{r-1}$ are Laurent polynomials with
$\deg p_j\le j$ and $p_j(C/X)=p_j(X)$ for $j=0,1,\dots,r-1$, then
$$\multline \det_{1\le s,t\le r}\big((A_r+X_t)\dotsb(A_{s+1}+X_t)
(A_r+C/X_t)\dotsb(A_{s+1}+C/X_t)\cdot p_{s-1}(X_t)\big)\\
=\prodl _{1\le i<j\le r} ^{}(X_i-X_j)(1-C/X_iX_j)\prodl _{i=1}
^{r}A_i^{i-1}\prodl _{i=1} ^{r}p_{i-1}(-A_i)\ ,
\endmultline\tag 5.5.1
$$
with the convention that empty products (like
$(A_r+X_t)\dotsb(A_{s+1}+X_t)$ for $s=r$) are equal to 1. (The
indeterminate $A_1$, which occurs at the right-hand side of (5.5.1),
in fact is superflous since it occurs in the argument of a constant
polynomial.)
\endproclaim
\demo{Proof}First we reduce this determinant to a simpler one.
Because of $\deg p_{s-1}\le s-1$  and $p_{s-1}(C/X)=p_{s-1}(X)$ there
must exist $\la_i^{(s)}\in\R$, $i=1,\dots,s-1$, such that
$$p_{s-1}(X)+\suml _{i=1} ^{s-1}\la_i^{(s)}(A_s+X)\dotsb(A_{i+1}+X)
(A_s+C/X)\dotsb(A_{i+1}+C/X)=\text {constant.}$$
The value of this constant must be $p_{s-1}(-A_s)$. This is seen
setting $X=-A_s$.

Hence we obtain that there are $\la_i^{(s)}\in \R$ such that
$$p_{s-1}(X)+\suml _{i=1} ^{s-1}\la_i^{(s)}(A_s+X)\dotsb(A_{i+1}+X)
(A_s+C/X)\dotsb(A_{i+1}+C/X)=p_{s-1}(-A_s)\ .\tag5.5.2$$
Now for $j=2,3,\dots,r$ (in that order) we perform the following row
operations: Add $\la_i^{(j)}/p_{i-1}(-A_i)$ times the $i$-th row, 
$i=1,2,\dots,j-1$, to
the $j$-th row. Then by using (5.5.2) it is seen that the $t$-th
entry in the $j$-th row becomes
$$(A_r+X_t)\dotsb(A_{j+1}+X_t)
(A_r+C/X_t)\dotsb(A_{j+1}+C/X_t)\cdot p_{j-1}(-A_j)\ .$$
This allows us to take $p_{j-1}(-A_j)$ out of the $j$-th row.

After having completed these operations we obtain
that the determinant in (5.5.1) is equal to
$$
\prodl _{i=1}
^{r}p_{i-1}(-A_i)\det_{1\le s,t\le r}\big((A_r+X_t)\dotsb(A_{s+1}+X_t)
(A_r+C/X_t)\dotsb(A_{s+1}+C/X_t)\big)\ .
$$
Therefore it remains to prove 
$$\multline 
\det_{1\le s,t\le r}\big((A_r+X_t)\dotsb(A_{s+1}+X_t)
(A_r+C/X_t)\dotsb(A_{s+1}+C/X_t)\big)\\
=\prodl _{1\le i<j\le r} ^{}(X_i-X_j)(1-C/X_iX_j)\prodl _{i=1}
^{r}A_i^{i-1}
\endmultline\tag5.5.3$$
in order to establish (5.5.1).
The determinant on the left-hand side of (5.5.3) is a
polynomial in  $X_1,\dots,X_r$ of degree $3\binom r2$ divided by $\prod
_{i} X_i^{r-1}$. Since, for $1\le{t_1}< {t_2}\le r$, the determinant is
zero for $X_{t_1}=X_{t_2}$ or $X_{t_1}=C/X_{t_2}$, 
the left-hand
side is equal to
$$p(X_1,\dots,X_r)\prodl _{i<j}(X_i-X_j)(X_iX_j-C)\Big/\prod
_{i}X_i^{r-1}\ ,$$
where $p(X_1,\dots,X_r)$ is some polynomial in the $X_i$'s. Comparing
the degrees yields that $p$ is a constant, which is computed by
comparing coefficients of $\prod _{i}X_i^{r-i}$ on both sides of
(5.5.3). \qed

\enddemo
If in the previous lemma we let $C\to0$, we get the following
corollary.
\proclaim{Lemma~35}Let $X_1,X_2,\dots,X_r,A_2,A_3,\dots,A_r$ be
indeterminates. If $p_0,p_1,\mathbreak\dots, p_{r-1}$ are polynomials with
$\deg p_j\le j$ for $j=0,1,\dots,r-1$, then
$$\multline \det_{1\le s,t\le r}\big((A_r+X_t)\dotsb(A_{s+1}+X_t)
\cdot p_{s-1}(X_t)\big)\\
=\prodl _{1\le i<j\le r} ^{}(X_i-X_j)\prodl _{i=1} ^{r}p_{i-1}(-A_i)\ .
\endmultline\tag 5.5.4
$$
\endproclaim
\remark{Remarks} (1) Note that in Lemma~35 we definitely mean {\it
polynomials} and not {\it Laurent} polynomials.

(2) In \cite{25, 26, 28} the author has used some determinant
lemmas to obtain closed forms for generating functions for several
families of plane partitions. In fact, all of these determinant lemmas are
special cases of Lemma~34. In particular, Lemma~2.2 of \cite{26} comes out of
Lemma~35 by setting 
$$p_{j-1}(X)=\prodl _{i=1} ^{j-1}(B_{i+1}+X).$$
 Lemma~7 of \cite{28} is the special case
$p_j\equiv 1$, $j=0,1,\dots,r-1$, of Lemma~34. 
\endremark


\subheading{5.6. A multiple basic hypergeometric summation}

\proclaim{Proposition~36}For $r\ge 1$ there holds the summation formula
$$\multline \suml _{k_1,\dots,k_r\ge0} ^{}\prodl _{i=1} ^{r}\(\frac
{\sqrt q} {q^iA}\)^{k_i}\prodl _{i=1} ^{r}\frac {(m_iA)_{k_i}}
{(qm_i/A)_{k_i}}\\
\times\prodl _{1\le i<j\le r} ^{}\frac {1-\frac {m_j}
{m_i}q^{k_j-k_i}} {1-\frac {m_j} {m_i}}\prodl  _{1\le i\le j\le r}
\frac {1-m_im_jq^{k_i+k_j}}
{1-m_im_j}\\
\hskip-2cm=\prodl  _{1\le i<j\le r} \frac {1-m_im_j/q} {1-m_im_j}\prodl _{i=1}
^{r}\frac {(1-m_i/\sqrt q)(1-m_i/A)} {(1-m_i^2)(1-\sqrt q/q^iA)}\ ,
\endmultline\tag5.6.1$$
provided that there exist nonnegative integers $n_i$ with
$n_1>n_2>\dotsb >n_r$ such that $m_i A=q^{-n_i}$ for all
$i=1,2,\dots,r$.\endproclaim
\remark{Remark} I decided to formulate the Proposition in terms of
the $m_i$'s rather than the $n_i$'s in order to keep the notation as
short as possible. However, in the following the reader should never
forget that the $m_i$'s in fact disguise the $n_i$'s via
$m_i=q^{-n_i}/A$.
\endremark
\demo{Proof}
It seems to be convenient to first give a rough sketch of
what we are going to do.
We establish (5.6.1) using a double induction. The main induction is
on $r$. For $r=1$ equation (5.6.1) can be written in basic
hypergeometric notation (cf\. subsection~2.1):
$${}_6\phi_5\left[\matrix m_1^2,qm_1,-qm_1,q,\sqrt qm_1,m_1A\\
m_1,-m_1,m_1^2,\sqrt qm_1,qm_1/A\endmatrix; q,\frac {1} {\sqrt
qA}\right]=
\frac {(1-m_1/\sqrt q)(1-m_1/A)} {(1-m_1^2)(1-1/\sqrt qA)}\ .
\tag5.6.2$$
This is just a special case of the very well-poised
$_6\phi_5$-summation (3.3.9).
(Recall that $m_1A=q^{-n_1}$ by assumption.) We remark that actually
we could start our induction with $r=0$, thereby avoiding the use of
the very well-poised $_6\phi_5$-summation. However, it is useful to
know what (5.6.1) looks like for $r=1$, the simplest non-trivial
value for $r$.

Now suppose that (5.6.1) is valid for $r-1$. To do the induction
step, i.e\. to settle (5.6.1) for $r$,
provided that it is valid for $r-1$,
 we use induction on $n_1+n_2+\dotsb+n_r$.
First we establish a recurrence (identity (5.6.6)) 
for the left-hand side of (5.6.1). In
the second step we shall show that the right-hand side obeys the same
recurrence. Hence everything will be done if the validity of (5.6.1)
has been checked for the initial values $(n_1,n_2,\dots,n_{r-1},0)$,
$n_1>n_2>\dotsb>n_{r-1}>0$.
Only for this last step it will be necessary to use the induction
hypothesis with respect to $r$.

Let us introduce the following notations: Write
$S_r(A;m_1,m_2,\dots,m_r)=\mathbreak S_r(A;\bold m)$ for the 
left-hand side and $P_r(A;m_1,m_2,\dots,m_r)=P_r(A;\bold m)$ for the\linebreak
right-hand side of
(5.6.1). Moreover we denote the summand in $S_r(A;\bold m)$
by\linebreak $E_r(A;m_1,\dots,m_r,k_1,\dots,k_r)=E_r(A;\bold m,\bold k)$ so
that $S_r(A;\bold m)=\sum _{\bold k\ge\bold 0} ^{}E_r(A;\bold m,\bold k)$. The set of summation
indices, $\{k_1,k_2,\dots,k_r\}$ is denoted by $\Om$. For a subset $T$
of $\{1,2,\dots,r\}$ let $\Om_T$ be the set $\{k_i:i\in T\}$
 of corresponding
summation indices. For any subset $B$ of $\Om$ the
symbol $\sum _{B\ge 1} ^{}E_r(A;\bold m,\bold k)$ means
$\sum{}'E_r(A;\bold m,\bold k)$, where the sum $\sum{}'$ is taken
over $k_i\ge 1$ for all $i\in B$ and over $k_i\ge 0$ for the
remaining $k_i's$.

Since the sum in (5.6.1) by assumption is finite, i.e\. consists only
of a finite number of terms, the inclusion-exclusion principle can be
applied to obtain that with our notations
$$1=\suml _{T\subseteq \{1,\dots,r\}} ^{}(-1)^{\vert T\vert}\sum
_{\Om_T\ge 1} ^{}E_r(A;\bold m,\bold k)\ .\tag5.6.3$$
The 1 on the left-hand side is the term $E_r(A;\bold m,\bold 0)$.

Next for a given $T\subseteq\{1,\dots,r\}$, we express $\sum
_{\Om_T\ge 1} ^{}E_r(A;\bold m,\bold k)$ in terms of\linebreak $S_r(A;\bold
m)$. This is done using the 
 $q$-augmentation operators $\ep_1,\dots,\ep_r$ which are defined by 
$$(\ep_if)(m_1,\dots,m_i,\dots,m_r)=f(m_1,\dots,qm_i,\dots,m_r)$$
for rational functions $f(m_1,\dots,m_r)$ and $i=1,\dots,r$. If
$n_r\ge1$ and $qm_t\ne
m_{t+1}$ for all $t$, we get that 
$$\align \suml _{\Om_T\ge1} ^{}&E_r(A;\bold m,\bold k)\tag5.6.4a\\
&\hskip-10pt=\(\prodl _{l\in T} ^{}\frac {\sqrt q} {q^lA}\frac {(1-m_lA)}
{(1-qm_l/A)}\)
\frac {\Big[\Big(\prodl _{l\in T} ^{}\ep_l\Big) \Big(\prodl _{1\le
i<j\le r} ^{}(1-m_j/m_i)\prodl _{1\le i\le j\le r}
^{}(1-m_im_j)\Big)\Big]} 
{\prodl _{1\le
i<j\le r} ^{}(1-m_j/m_i)\prodl _{1\le i\le j\le r}
^{}(1-m_im_j)}\\
\tag5.6.4b\\
&\hskip2.5cm\times \Big(\prodl _{l\in T} ^{}\ep_l\Big)\sum
_{k_1,\dots,k_r\ge0} ^{}E_r(A;\bold m,\bold k)\ .\tag5.6.4c
\endalign$$

On the other hand, suppose that $n_r\ge1$ and
 $qm_t=m_{t+1}$ holds for a fixed $t$. Then
$\ep_tE_r(A;\bold m,\bold k)$ would not be defined due to the
denominator term $1-m_{t+1}/m_t$ in $E_r(A;\bold m,\bold k)$. 
Therefore, at first sight, if $t\in T$ but
$(t+1)\notin T$ the line (5.6.4c) would not make sense. But in this case
we can show that $\suml _{\Om_T\ge1} ^{}E_r(A;\bold m,\bold k)=0$.
This implies that 
$$\suml _{\Om_T\ge1} ^{}E_r(A;\bold m,\bold k)=(1-m_{t+1}/qm_t)
R(A;\bold m)\ ,$$
where $R(A;\bold m)$ is some rational function with the property that
$\lim_{m_{t+1}\to qm_t}R(A;\bold m)$ exists. In fact, the factor
$(1-m_{t+1}/qm_t)=\Big(\prodl _{l\in T} ^{}\ep_l\Big)\,(1-m_{t+1}/m_t)$
appears in the numerator of (5.6.4b). So the limit $m_{t+1}\to qm_t$
of the rest of (5.6.4b,c) exists, hence also $\lim_{m_{t+1}\to qm_t}
\Big(\prodl _{l\in T} ^{}\ep_l\Big)
\suml _{\Om_T\ge1} ^{}E_r(A;\bold m,\bold
k)$ exists. This shows that (5.6.4) also holds
for $qm_t=m_{t+1}$, $t\in T$, $(t+1)\notin T$, since
both sides of (5.6.4) equal zero in this case. To confirm that
for $qm_t=m_{t+1}$, $t\in T$, $(t+1)\notin T$ the sum (5.6.4a) indeed
vanishes, we write
$$\align \sum
_{\Om_T\ge1} ^{}&E_r(A;\bold m,\bold k)=\frac {\sqrt q} {q^tA}\frac
{(1-m_tA)} {(1-qm_t/A)}\tag5.6.5a\\
&\hskip-5pt\times\suml _{\Om_{T'}\ge1} ^{}
\frac {\Big[\ep_t\prodl _{i=1} ^{r}\(\frac {\sqrt
q} {q^jA}\)^{k_i}\frac {(m_iA)_{k_i}} {(qm_i/A)_{k_i}} 
\prodl _{1\le
i<j\le r} ^{}{\ssize(1-\frac{m_j}{m_i}q^{k_i-k_j})}\prodl _{1\le i\le j\le r}
^{}{\ssize(1-m_im_jq^{k_i+k_j})\Big]}}
{\prodl _{1\le
i<j\le r} ^{}(1-m_j/m_i)\prodl _{1\le i\le j\le r} ^{}(1-m_im_j)}\\
\tag5.6.5b
\endalign$$
where $T'=T\backslash \{t\}$.
To abbreviate the clumsy expressions, for the moment denote the
summand in (5.6.5b) by $F(k_t,k_{t+1})$. The dependence on the other
parameters does not concern us for the following considerations. If
$k_t=k_{t+1}$ the expression $F(k_t,k_{t+1})=F(k_t,k_t)$ vanishes because
of the numerator term $(1-\frac {m_{t+1}} {qm_t}q^{k_{t+1}-k_t})$. If
$k_{t+1}\ne k_t$ the identity

{\eightpoint
$${\(\frac {\sqrt q} {q^tA}\)^{k_{t}}\(\frac {\sqrt q}
{q^{t+1}A}\)^{k_{t+1}}}
\frac {\dsize 1-\frac {m_{t+1}} {qm_t}q^{k_{t+1}-k_t}} 
{\dsize 1-\frac {m_{t+1}}
{m_t}}
=-{\(\frac {\sqrt q} {q^tA}\)^{k_{t+1}}\(\frac {\sqrt q}
{q^{t+1}A}\)^{k_{t}}}
\frac {\dsize 1-\frac {m_{t+1}} {qm_t}q^{k_{t}-k_{t+1}}} 
{\dsize 1-\frac {m_{t+1}}
{m_t}}$$}

\noindent
shows that $F(k_t,k_{t+1})=-F(k_{t+1},k_t)$. (Recall that at the
moment we are assuming $qm_t=m_{t+1}$. Hence we have $m_{t+1}/qm_t=1$.) 
Therefore $\sum _{\Om_T\ge1} ^{}
E_r(A;\bold m,\bold k)$ is zero whenever there is a $t$ with
$qm_t=m_{t+1}$, $t\in T$, and $(t+1)\notin T$.

Plugging (5.6.4) into (5.6.3) yields the identity
$$1=\suml _{T\subseteq \{1,\dots,r\}} ^{}(-1)^{\vert
T\vert}L_T(A;\bold m)\cdot\Big(\prodl _{l\in T}
^{}\ep_l\Big)S_r(A;\bold m)\ ,\tag 5.6.6$$
where $L_T(A;\bold m)$ is the expression in (5.6.4b). 
The previous considerations guarantee 
that (5.6.6) holds for all $A,m_1,\dots,m_r$ such that
$n_1>n_2>\dots>n_r\ge1$. 

Next it is shown that the right-hand side $P(A;\bold m)$ of (5.6.1)
also
satisfies (5.6.6). This is done by a verification. In
(5.6.6) replace $S(A;\bold m)$ by $P(A;\bold m)$. After some
manipulation this leads to
$$\multline 1=
\(\prodl  _{1\le i<j\le r} \frac {1-m_im_j/q} {1-m_im_j}\)
\(\prodl _{i=1}
^{r}\frac {(1-m_i/\sqrt q)(1-m_i/A)} {(1-m_i^2)(1-\sqrt q/q^iA)}\)\\
\hskip-3cm\times
\suml _{T\subseteq\{1,\dots,r\}} ^{}(-1)^{\vert T\vert}\prodl _{j\in T}
^{}\(\frac {\sqrt q} {q^jA}\frac {1-m_jA} {1-m_j/A}\)\\
\hskip1cm\times\frac {\left[\big(\prodl _{l\in T} ^{}\ep_l\big)\big(\prodl _{1\le
i<j\le r} ^{}(1-m_j/m_i)(1-m_im_j/q)\prodl _{i=1} ^{r}(1-m_i/\sqrt q)\big)\right]} 
{\prodl _{1\le
i<j\le r} ^{}(1-m_j/m_i)(1-m_im_j/q)\prodl _{i=1} ^{r}(1-m_i/\sqrt
q)}.
\endmultline\tag5.6.7$$
Multiplication of both sides of (5.6.7) by the denominator of the
right-hand side gives
$$\align \prodl _{1\le i<j\le r} ^{}&\big((1-m_im_j)(m_i-m_j)\big)\prod
_{i=1} ^{r}\big((1-m_i^2)(1-\sqrt q/q^iA)\big)\\
&=\suml _{T\subseteq\{1,\dots,r\}} ^{}(-1)^{\vert T\vert}\prodl _{j\in T}
^{}\(\frac {\sqrt q} {q^jA}\frac {(1-m_jA)} {(1-m_j/A)}\)\prodl _{i=1}
^{r}\big(m_i^{r-i}(1-m_i/A)\big)\\
&\quad \quad \quad \times\left[\Big(\prodl _{l\in T} ^{}\ep_l\Big)\Big(\prodl _{1\le
i<j\le r} ^{}(1-m_j/m_i)(1-m_im_j/q)\prodl _{i=1} ^{r}(1-m_i/\sqrt
q)\Big)\right]\\
&=: \suml _{T\subseteq\{1,\dots,r\}} \Expr (T)\ .\tag5.6.8
\endalign$$
The right-hand side of (5.6.8) is a polynomial in $m_1,m_2,\dots,m_r$
of total degree $2r+3\binom r2$. We are going to show that the
right-hand side vanishes for $m_s=m_t$, for $m_s=1/m_t$, and for $m_t=\pm 1$.
Suppose that this is done. It follows that
$$\prodl _{1\le i<j\le r} ^{}\big((1-m_im_j)(m_i-m_j)\big)\prod
_{i=1} ^{r}(1-m_i^2)\tag5.6.9$$
must be a factor of the right-hand side. This factor also has total
degree $2r+3\binom r2$ in $m_1,m_2,\dots,m_r$. Therefore the
right-hand side of (5.6.8) is the expression in (5.6.9) times some
expression which is independent of $m_1,\dots,m_r$. To get this
expression, look
at the coefficient of $\prod _{i=1} ^{r}m_i^{r-i}$ in the right-hand
side of (5.6.8). It is 
$$\suml _{T\subseteq\{1,\dots,r\}} ^{}(-1)^{\vert T\vert}\prodl _{j\in T}
^{}\frac {\sqrt q} {q^jA}=\prodl _{i=1} ^{r}(1-\sqrt q/q^iA)\ ,$$
just as desired.

Let $m_t=\pm 1$ for a fixed $t$. Moreover, fix a subset $T_1$ of
$\{1,2,\dots,r\}$ with $t\notin T_1$ and write $T_2:=T_1\cup \{t\}$. Then it
is seen that 
$$\Expr (T_1)\bvert_{m_t= 1}=-\Expr(T_2)\bvert_{m_t= 1}\ ,$$
and the same holding if 1 is replaced by $-1$.
($\Expr(T)$ was defined in (5.6.8) as the summand of the sum on the
right-hand side. $\Expr(T)\bvert_{m_t=1}$ means the evaluation of
$\Expr(T)$ at $m_t=1$.) Namely for $m_t=1$,
$$\align \Expr(T_2)\bvert_{m_t=1}&=-(-1)^{\vert T_1\vert}\frac {\sqrt q}
{q^tA}\Big(\prodl _{j\in T_1} ^{}\frac {\sqrt q} {q^jA}\frac {(1-m_jA)}
{(1-m_j/A)}\Big)\cdot \frac {1-A} {1-1/A}\\
&\quad \quad\times \Big(\prodl _{i=1}
^{r}m_i^{r-i}(1-m_i/A)\Big)\Bvert_{m_t=1}
\times \Big[\big(\prodl _{l\in T_1} ^{}\ep_l\big)\big(\prod
_{i=1} ^{r}(1-m_i/\sqrt q)\big)\\
&\quad \quad \prod _{1\le i<j\le r} ^{}(1-m_i/m_j)(1-m_im_j/q)\\
&\quad\quad \quad  \quad \quad 
\frac {1-\sqrt q} {1-1/\sqrt q}\prodl _{i=1} ^{t-1}\frac
{1-q/m_i} {1-1/m_i}\prodl _{i=t+1} ^{r}\frac {1-m_i/q} {1-m_i}
\underset i\ne t\to{\prodl _{i=1} ^{r}}\frac {1-m_i}
{1-m_i/q}\Big]\Bvert_{m_t=1}\\
&=-\Expr(T_1)\bvert_{m_t=1}\ .
\endalign$$
A similar computation can be done for $m_t=-1$. Hence for $t\notin T_1$
each two terms $\Expr(T_1)\bvert _{m_t=1}$ and $\Expr(T_1\cup\{t\})
\bvert _{m_t=1}$ cancel in the sum on the right-hand side of (5.6.8)
when it is evaluated at $m_t=1$, the same being true for $m_t=-1$. 
Therefore it must be zero for $m_t=\pm 1$.

Now we turn to the case $m_s=m_t$ for fixed $s$ and $t$, $1\le s<t\le r$.
This
 obviously only makes sense for $r\ge2$.
Consider a set $S_1\subseteq\{1,\dots,r\}$ with $s,t\notin S_1$. Let
us set $S_2:=S_1\cup\{s\}$, $S_3:=S_1\cup\{t\}$, and
$S_4:=S_1\cup\{s,t\}$. We have
$$\align \Expr(&S_2)\bvert_{m_s=m_t}=(-1)^{\vert S_3\vert}q^{t-s}\prod
_{j\in S_3} ^{}\(\frac {\sqrt q} {q^jA}\frac {(1-m_jA)} {1-m_j/A)}\)\prod
_{i=1} ^{r}\big(m_i^{r-i}(1-m_i/A)\big)\bvert_{m_s=m_t}\\
\tag5.6.10a\\
&\times\Bigg[\Big(\prodl _{l\in S_1} ^{}\ep_l\Big)\prodl _{1\le i<j\le r}
^{}\big((1-m_j/m_i)(1-m_im_j/q)\big)\prodl _{i=1} ^{r}(1-m_i/\sqrt
q)\tag5.6.10b\\
&\hskip1.5cm\Big(\prodl _{i=1} ^{s-1}\frac {1-qm_s/m_i} {1-m_s/m_i}
\underset i\ne t\to{\prodl _{i=s+1}
^{r}}\frac {1-m_i/qm_s} {1-m_i/m_s}\Big)\frac {1-m_t/qm_s}
{1-m_t/m_s}\tag5.6.10c\\
&\hskip1.5cm \Big(\prodl _{i=1} ^{r}\frac {1-m_im_s} {1-m_im_s/q}\Big)\frac
{1-m_s\sqrt q} {1-m_s/\sqrt q}\Bigg]\bigg\vert_{m_s=m_t}\ .\tag
5.6.10d
\endalign$$
(The term $(1-m_t/m_s)$ in the denominator of  (5.6.10c) seems to be a
problem. But it is not since in fact it cancels out with a term of
(5.6.10b).)
The expression $\underset i\ne t\to{\prodl _{i=s+1} ^{r}}\frac
{1-m_i/qm_s} {1-m_i/m_s}$ has to be split up into
$$\prodl _{i=s+1} ^{t-1}\frac
{1-m_i/qm_s} {1-m_i/m_s}\prodl _{i=t+1} ^{r}\frac
{1-m_i/qm_s} {1-m_i/m_s}\ .$$
A little bit of manipulation of the first product turns this into
$$q^{s-t+1}\prodl _{i=s+1} ^{t-1}\frac
{1-qm_s/m_i} {1-m_s/m_i}\prodl _{i=t+1} ^{r}\frac
{1-m_i/qm_s} {1-m_i/m_s}\ .$$
Moreover, we have
$$(1-m_t/qm_s)\bvert_{m_s=m_t}=-\frac {1}
{q}(1-qm_t/m_s)\bvert_{m_s=m_t}\ .$$
Taking these manipulations into account, we finally obtain
$$\align \Expr(S_2)\bvert_{m_s=m_t}&=q^{t-s}\cdot q^{s-t+1}\cdot\(-\frac
{1} {q}\)\cdot \Expr(S_3)\\
&=-\Expr(S_3)\ .
\endalign$$
Since obviously
$\Expr(S_1)\bvert_{m_s=m_t}=\Expr(S_4)\bvert_{m_s=m_t}=0$, this means
that for $s,t\notin S_1$ each four terms $\Expr(S_1)\bvert_{m_s=m_t}$, 
$\Expr(S_1\cup\{s\})\bvert_{m_s=m_t}$, $\Expr(S_1\cup\{t\})\bvert_{m_s=m_t}$,
$\Expr(S_1\cup\{s,t\})\bvert_{m_s=m_t}$ cancel in the sum on the
right-hand side of (5.6.8) when it is evaluated at $m_s=m_t$.
Therefore it must be zero for $m_s=m_t$.

The arguments for $m_s=1/m_t$ are similar. This time one obtains
$$\Expr(S_2)\bvert_{m_s=1/m_t}=\Expr(S_3)\bvert_{m_s=1/m_t}=0$$ and
$$\Expr(S_1)\bvert_{m_s=1/m_t}=-\Expr(S_4)\bvert_{m_s=1/m_t}.$$

Summarizing, we have shown that both sides of (5.6.1) satisfy the
functional relation (5.6.6). To be precise, for all
$n_1>n_2>\dots>n_r\ge1$ we proved that
$$1=\suml _{T\subseteq \{1,\dots,r\}} ^{}(-1)^{\vert
T\vert}L_T(A;q^{-\bold n}/A)\cdot\Big(\prodl _{l\in T}
^{}E_l^{-1}\Big)S_r(A;q^{-\bold n}/A)\tag 5.6.11a$$
and
$$1=\suml _{T\subseteq \{1,\dots,r\}} ^{}(-1)^{\vert
T\vert}L_T(A;q^{-\bold n}/A)\cdot\Big(\prodl _{l\in T}
^{}E_l^{-1}\Big)P_r(A;q^{-\bold n}/A)\ ,\tag 5.6.11b$$
where $q^{-\bold n}/A$ is a short-hand notation for
$q^{-n_1}/A,q^{-n_2}/A,\dots,q^{-n_r}/A$. $E_l$ is the usual shift operator
with respect to $n_l$,
$$(E_lf)(m_1,\dots,m_l,\dots,m_r)=f(m_1,\dots,m_l+1,\dots,m_r)\ .$$
Besides, the expressions of the form $S_r(A;q^{-\hat{\bold n}}/A)$
and
$P_r(A;q^{-\hat{\bold n}}/A)$ which are involved in the non-zero
terms of (5.6.11) all satisfy $\hat n_1>\hat n_2>\dots>\hat n_r\ge0$.
Therefore induction on $n_1+n_2+\dots+n_r$ can be performed, as soon
as the validity of (5.6.1) for the initial values
$(n_1,n_2,\dots,n_{r-1},0)$, $n_1>\dots>n_{r-1}>0$ is checked.

Let $n_r=0$, which is equivalent to $m_r=1/A$. It is clear that in
this case there are nonvanishing terms in the sum at the left-hand
side of (5.6.1) only if $k_r=0$. Hence,
$$\align S_r(A;&m_1,\dots,m_{r-1},1/A)\\
&=\suml _{k_1,\dots,k_{r-1}\ge0} ^{}\prodl _{i=1} ^{r-1}\Big(\frac
{\sqrt q} {q^iA}\Big)^{k_i}\prodl _{i=1} ^{r-1}\frac {(m_iA)_{k_i}}
{(qm_i/A)_{k_i}}\\
&\quad \quad \quad \times\prodl _{1\le i<j\le r-1} ^{}\frac {1-\frac {m_j}
{m_i}q^{k_j-k_i}} {1-\frac {m_j} {m_i}}\prodl  _{1\le i\le j\le r-1}
\frac {1-m_im_jq^{k_i+k_j}}
{1-m_im_j}\\
&\quad \quad \quad \times\prodl _{i=1} ^{r-1}\frac {1-q^{-k_i}/m_iA}
{1-1/m_iA}\frac {1-m_iq^{k_i}/A} {1-m_i/A}\\
&=S_{r-1}(qA;m_1,\dots,m_{r-1})\\
&=P_{r-1}(qA;m_1,\dots,m_{r-1})\\
&=P_{r}(A;m_1,\dots,m_{r-1},1/A)\ .
\endalign$$
The next to the last step used the induction hypothesis with respect
to $r$, the last step is an easy exercise. 

The proof of the Proposition now is complete.\quad \quad \qed

\enddemo



