
\rightheadtext{Nonintersecting lattice paths}
\leftheadtext{C. Krattenthaler}

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

\long\def\Eat#1{}
%\loadbold
\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}}

\head I. Introduction\endhead
Gessel and Viennot's \cite{16, 17} beautiful idea of interpreting
tableaux as families of nonintersecting lattice paths is a very useful
tool for obtaining determinantal expressions for generating functions
for various families of tableaux with a given shape. (Subsequently,
Stembridge \cite{41} widened this theory. He showed that generating
functions for tableaux where the shape now is allowed to vary can
frequently given in form of a Pfaffian.) What is done in this theory,
is counting families of nonintersecting lattice paths by weights
which depend on the position of the path's edges in the
integer lattice $\Z^2$. ($\Z$ stands for the set of integers.) 
We in turn propose the counting of families
of nonintersecting lattice paths by MacMahon's \cite{32} major
index and generalizations of it. The original motivation of doing
major counting of nonintersecting lattice paths lay in a problem of Choi
and Gouyou-Beauchamps. In \cite{7} they found a nice product formula
for the number of tableaux with $p$ odd rows, with the parts being
bounded by $n$, and where the lengths of the rows are bounded by $2r$.
It was conjectured that there is also a simple product formula for
the generating function of this family of tableaux. By a slight
modification of Choi and Gouyou-Beauchamps' idea of proof, which is
inspired by Desainte-Catherine and Viennot's \cite{10} geometric
interpretation of a variation of the celebrated Knuth correspondence
\cite{24, 6}, in this paper it is shown that the computation of
the generating function of the above family of tableaux can be solved
by counting nonintersecting lattice paths with given starting and
final points, which in addition do not cross the diagonal line
$x=y$, by a variation of the major index. So we decided to
systematically develop a theory of counting families of
nonintersecting lattice paths by major index and generalizations of
it, which we call {\it strange major indices} (cf\. (4.0.4)--(4.0.4)). 

This major counting theory is developed quite analogously to the
usual theory which encounters edge weights. The only difference is
that for the major counting we have to assume that the starting
points of the lattice paths lie on a line parallel to $x+y=0$. Once
this is done, we also obtain determinants involving $q$-binomials for
the major and strange major generating functions for families of
nonintersecting lattice paths with given starting and final points.
Also here these determinants in special cases can be evaluated to
result in simple products. However, the really significant parts of
this paper consider nonintersecting paths which are bounded by $x=y$.
This has no counterpart with edge weights. Only the {\it number} of
such families of nonintersecting lattice paths has been previously
considered \cite{17, 10, 7}. Again we find determinantal
expressions, though a little bit more complicated. And again,
in special cases these determinants can be evaluated to result in
nice product expressions.

Applications of this theory do not only include the solution of the
above tableaux problem. There are other tableaux problems which also
can be treated that way. An interesting application of our major counting
is to give an alternative proof for the generating function
expression for tableaux with rows of even lengths which do not
exceed $2r$ and where the parts are bounded by $n$. (Of course this
is the $p=0$ case of the Choi--Gouyou-Beauchamps problem.) The
proofs so far \cite{11, 37, 40} rely on either the theory of
symmetric functions or group representation theory.
 Our proof only uses combinatorial
constructions and a simple determinant evaluation. A further
by-product of our major counting results is the computation of the
generating function for tableaux with $p$ odd rows, with at most $c$
columns, with only odd parts which lie
between $1$ and $2n-1$. Equivalently, we thus compute the generating
function for symmetric plane partitions with at most $n$ rows, with parts
between $1$ and $c$, and with exactly $p$ odd entries on the main
diagonal. The $p=0$ result was also
previously given by D\'esarm\'enien \cite{11, Th\'eor\'eme~1.2,
second identity}, 
Proctor \cite{37, Theorem~1 case (CYH)},
 and Stembridge
\cite{40, Corollary~4.3~(b)}. 
Moreover, having solved the Choi--Gouyou-Beauchamps
problem, by summing with respect to $p$ and using the
$q$-analog of Kummer's
summation we are able to present a new proof of the
Bender--Knuth (ex-)Conjecture \cite{4, p.~50} about the generating function for
tableaux with parts between $1$ and $n$, and with
at most $c$ columns. Likewise, by summing the generating
functions for the above described symmetric plane partitions with
respect to $p$, we provide a new proof of the MacMahon
(ex-)Conjecture \cite{32, p.~270} about the generating function for symmetric plane
partitions with at most $n$ rows and with parts between $1$ and $c$. 
Proofs of these conjectures have been given by
Andrews \cite{2, 3}, Gordon \cite{18, only for the Bender--Knuth
conjecture}, Macdonald \cite{33, pp.~51--53}, and Proctor \cite{36,
Propositions~7.2, 7.3}. In addition we
prove two theorems (Theorems~9 and 20) about specific
 generating functions for
pairs of tableaux, or, equivalently, for specific sums of squares of
Schur functions.

\userunningheads
\rightheadtext{Nonintersecting lattice paths}
\leftheadtext{C. Krattenthaler}
It should be noted that the tableaux and plane partition theorems in
this paper could also be derived starting from the summation theorems
for Schur functions in Goulden's paper \cite{19} (cf\. Remark~(2) at
the end of section~4). However, it is possible neither to obtain our
theorems for the major and strange major counting of nonintersecting
lattice paths from Goulden's results nor Goulden's results 
from our theorems. However, the ideas of the present paper can be
suitably modified to even give bijective proofs of Goulden's results.
(Goulden used a linear operator for symmetric functions and some
tricky manipulations to derive his theorems.) These bijective proofs
will appear in a forthcoming paper \cite{29} together with
far-reaching generalizations and further applications
of the results of Goulden and of the present paper.

We organize the paper in the following way. In the next section 
most of the definitions are given. The definition of the strange
major indices is deferred to section~4, where they appear for the
first time. Besides, in subsection~2.1
 it is explained how to
represent paths as two-rowed arrays, which will be crucial for our
combinatorial constructions in subsections~5.1--5.3. 
In subsection~2.2, as a preparation, we
review two sign-reversing involutions which serve to compute the
{\it number} of families of nonintersecting lattice paths.
Subsequently, in sections~3 and 4 these involutions will be modified
in order to be applicable for the major and strange major counting.
 In section~3 the counting theory for the
major index is developed. Here the results about
tableaux with even rows (Theorem~10), about tableaux with odd parts
(Theorem~11), respectively symmetric plane partitions with prescribed
number of odd entries on the main diagonal (Theorem~12),
 and the MacMahon Conjecture (Theorem~13) are
included. In section~4 the counting theory for the strange major
index is developed. Here in Theorem~21 the Choi--Gouyou-Beauchamps
problem is solved. The new proof of the Bender--Knuth Conjecture
(Theorem~22) is found in this subsection.
 Since the complete details of the means which we
need for the proofs in sections~3  and 4 very often are unpleasant
and cumbersome, there is a separate section, namely section~5, which
contains all auxiliary results and correspondences. Subsection~5.1
provides the basic results about major and strange major generating
functions of single lattice paths. Subsection~5.2 contains two
correspondences for paths which cross the line $x=y$. They are 
``major analogues" for the reflection principle. In subsection~5.3 we
give a correspondence for pairs of intersecting lattice paths. It is
a ``major analogue" for the usual interchanging procedure (cf\.
\cite{17, 41}). The modified Knuth correspondence together with its
geometric interpretation, which was
mentioned above, is described in subsection~5.4. The last two
subsections are devoted to computational lemmas. A determinant lemma
(Lemma~34) of a very general kind is proved in subsection~5.5.
Previously, special cases have been successfully used in the
computation of plane partition generating functions \cite{25, 26, 28}. 
Finally, subsection~5.6 provides a multiple summation formula which
is of crucial importance in the proofs of Theorems~18 and 19.
R.~Gustafson and S.~Milne pointed out to me that it is a special case of 
Gustafson's $C_r$ $_6\ps_6$ summation (or in the old notation: 
$Sp(r)$ $_6\ps_6$ summation) \cite{21, Theorem~5.1}. The derivation of
(5.6.1) from Gustafson's $C_r$ $_6\ps_6$ sum can be found in
\cite{30}. I have included my original proof of (5.6.1) since it is
purely elementary and independent of the deep theory of multiple
basic hypergeometric summations and transformations currently under
development, mainly by Milne and Gustafson (cf\. e.g\. \cite{9, 21,
30, 31,
34, 35} and the references cited there). Besides, the ideas in
this proof could turn out to be useful for proving other multiple
summation formulas. For further comments on the connections with the
theory of $A_r$ and $C_r$ summations (formerly: $U(r)$ and $Sp(r)$
summations) see Remark~(3) at the end of
section~4. For instance, an interesting feature of Theorem~15 is that
it implicitly contains a new $A_r$-type $q$-Gau\3 summation formula
(identity (4.3.12)).


\newpage

\heading II. Definitions and Preliminaries \endheading


\subheading{2.1. Definitions and notation}
In this paper we always consider lattice
paths in the plane 
consisting of unit horizontal and vertical steps
in the positive direction. In the sequel we shall call them 
{\it paths} for short.
Any path in a natural way corresponds to a multiset permutation
consisting of $1$'s and $2$'s. Let $P$ be a path from
$\A =( A_1, A_2)$ to $\E =(E_1,E_2)
$. Later we frequently abbreviate the fact that a path $P$ goes from
$\A$ to $\E$ by $P:\A\to\E$.
$P$ may be represented by a pair $(\A ,\pi)$, where 
$\A $ is the
starting point of $P$ and
$\pi=\pi\sb 1\pi\sb 2\dots\pi\sb { E
\sb 1+ E
\sb 2- A\sb 1- A\sb 2}$, 
where $\pi\sb i=1$
if the $i$'th step in the path $P$ is a horizontal one and $\pi\sb
i=2$
if the $i$'th step in the path $P$ is a vertical one. $\pi$ is a
multiset permutation consisting of $ E
\sb 1- A\sb 1$ entries of $1$ and
$ E
\sb 2- A\sb 2$ entries of $2$. For example, the path $P_0$ in Figure 1 is
represented by $((1,-1),\, 221221112122)$. Of course, this representation of
paths is unique. Hence, we may identify each path with its
representation.

\vskip10pt 
\vbox{\noindent
$$\Koordinatenachsen(8,8)(0,0)
\Gitter(8,8)(0,0)
\Pfad(1,-1),221221112122\endPfad
\DickPunkt(1,-1)
\DickPunkt(6,6)
\Label\ro{P_0}(3,3)
\hskip4cm
$$
\nobreak
\centerline{\eightpoint Figure 1}
}
\vskip10pt

The {\it major index} (or ``greater index") of a multiset permutation
$\pi=\pi\sb 1\pi\sb 2\dots 
\pi\sb n$, $\pi\sb i\in {\Bbb
N}$ (set of positive
integers), is defined by
$$\maj \pi =\sum \sb {i=1} \sp {n-1}i\cdot \chi
 (\pi\sb i>\pi\sb {i+1})\ ,$$
where $\ch$ is the usual truth function,
$\chi
 (A)=1$ if $A$ is true, and $\chi
 (A)=0$ otherwise.


Given a path $P=(\A ,\pi)$, we extend 
the major index
 to $P$ by defining $\maj P:=\maj \pi $. For our path in Figure~1 we
have $\maj P_0=2+5+9=16$. 

By definition each pair $21$ that occurs in a multiset
permutation $\pi$, and only these, makes a contribution to the
major index of $\pi$. Given a path $P=(\A ,\pi)$,
the occurence of $21$ in $\pi$ means that a vertical step is followed
by a horizontal one. The point which is the end point of this vertical
step (and at the same time
 the starting point of this horizontal step) will be called
a {\it North-East corner} of the path $P$. 
The North-East corners of
our path in Figure~1 are $(1,1)$, $(2,3)$, and $(5,4)$.
By the above
consideration we see that only North-East corners of a path make a
contribution to the major index. Besides, the contribution of the
North-East corner $(a,b)$ is the number of steps from the starting
point of the path to $(a,b)$, or in symbols $a+b-A_1-A_2$ provided
that the starting point is $(A_1,A_2)$. Therefore
North-East corners are of great significance when dealing with the
major index of paths. In fact, given the starting and the final point
of a path, the North-East corners uniquely determine the path.
Suppose that $P$ is a path from $\A=(A_1,A_2)$ to $\E=(E_1,E_2)$ and
let the North-East corners of $P$ be $(a_1,b_1)$, $(a_2,b_2)$, \dots,
$(a_k,b_k)$, where we assume that the $(a_i,b_i)$ are ordered from
left to right, which is equivalent with $A_1\le a_1<a_2<\dots<a_k\le E_1-1$, and
$A_2+1\le b_1<b_2<\dots<b_k\le E_2$. Then $P$
can be represented by the two-rowed array
$$\matrix\format\c&\c&\c&\c\\ a_1&\ a_2&\ \dots&\ a_k\\
b_1&\ b_2&\ \dots&\ b_k\endmatrix\ ,\tag2.1.1$$
or, if we wish to make the bounds which are caused by the starting
and the final point transparent,
$$\matrix\format\r\quad &\c&\c&\c&\c&\quad \l\\
 A_1\le&a_1&\ a_2&\ \dots&\ a_k&\le E_1-1\\
A_2+1\le& b_1&\ b_2&\ \dots&\ b_k&\le E_2\endmatrix\ .\tag2.1.2$$
For a given starting point and a given final point,
by definition the empty array is the representation for the only path
that has no North-East corner.
For the path in our running example
we obtain the array representation
$$\matrix 1\ 2\ 5\\1\ 3\ 4\endmatrix\ ,$$
or with bounds included,
$$\matrix\format\r\quad &\c&\c&\c&\quad \l\\
 1\le&1&\ 2&\ 5&\le5\\0\le&1&\ 3&\ 4&\le6\endmatrix\ .$$
 The notation (2.1.2) will be used with
a three-fold meaning. First, we write down special arrays in that way
if in addition we want to point out the row bounds. Secondly, we shall
speak of two-rowed arrays {\it of the type\/} (2.1.2) by which we will mean
arrays of the form (2.1.1) which obey the row bounds in (2.1.2). Thirdly,
the notation (2.1.2) will also be used for the {\it set} of all arrays of
the type (2.1.2). It should always be clear from the context which
meaning is intended.

In section~5, also two-rowed arrays with its
rows being of unequal length will be considered. But these arrays also will
have the property that the rows are strictly increasing. So by
convention, whenever in this subsection and in subsections~5.1--5.3
 we speak of two-rowed arrays we
mean two-rowed arrays with strictly increasing rows. Also for these
arrays we will use a notation of the kind (2.1.2) together with its
three-fold meaning just explained. (We remark that
in subsection~5.4 we consider two-rowed arrays of different type.) 
We shall frequently use the short notation $(a\mid b)$ for two-rowed
arrays, where $a$
denotes the sequence $(a_i)$ of elements of the first row, 
and $b$ denotes the
sequence $(b_i)$ of elements of the second row.

Given a sequence $a=a_1,a_2,\dots,a_k$ we write $\V a$ for the sum $\sum
_{i=0} ^{k}a_i$ of all the elements of the sequence. Also for $r$-tuples
$\et=(\et_1,\dots,\et_k)$ we shall write $\V\et$ for the sum $\sum
_{i=1} ^{k}\et_i$.
In order to relate the major index of a path $P$ with starting point
$\A=(A_1,A_2)$ to its array
representation $(a\mid b)$, given by (2.1.1), it is readily verified
that 
$$\maj P=\V a+\V b-k(A_1+A_2).\tag2.1.3$$
\medpagebreak

An $r$-tuple $\la=(\la_1,\dots,\la_r)$ with 
$\la_1\ge\la_2\ge\dots\ge\la_r$ is called a
{\it partition}. The components $\la_i$ are called {\it parts} of the
partition. Let $\la$ be a partition.
A {\it tableau $\ta$ of shape $\la$} is an array 
$$\matrix\ta_{11}&\ta_{12}&\innerhdotsfor3\after\quad &\ta_{1\la_1}\\
\ta_{21}&\ta_{22}&\innerhdotsfor2\after\quad &\ta_{2\la_2}\\
\vdots&\innerhdotsfor 2\after\quad &\iddots\\
\ta_{r1}&\hdots&\ta_{r\la_r}
 \endmatrix
\tag2.1.4$$
of positive integers $\ta_{ij}$, $1\le i\le r$, $1\le j\le \la_i$,
such that the rows are weakly  and the columns are strictly
increasing.
The entries of $\ta$ are called
{\it parts} of the tableau. The sum of all the parts of a tableau $\ta$
is called the {\it norm}, in symbols $n(\ta)$, of the tableau. Given
a set $T$ of tableaux, the {\it norm generating  function for $T$} is
defined to be $\sum _{\ta\in T} ^{}q^{n(\ta)}$. In the sequel, if we
speak of the generating function for some set of tableaux we always
mean the norm generating function.

A {\it plane partition of shape $\la$} is an array $\ta$ of positive
integers $\ta_{ij}$ of the form
(2.1.4) such that the rows and the columns are weakly decreasing. It
is called {\it column-strict} if the columns are strictly decreasing.
The notions part, norm, generating function are used for plane
partitions in the same sense as with tableaux.

The {\it Schur function} $s_\la(x_1,x_2,\dots)=s_\la(\bold x)$ is a
symmetric function (cf\. \cite{33, 38, 39}) in the variables $x_1,x_2,\dots$ 
and is combinatorially defined by
$$s_\la(\bold x)=\sum _{\ta} ^{}\prod _{} ^{}x_{\ta_{ij}}\ ,$$
where the sum is over all tableaux $\ta$ of shape $\la$ and the
product is over all parts $\ta_{ij}$ of $\ta$. Equivalently, the sum
could also run over all column-strict plane partitions $\ta$ of shape
$\la$. The vector $\bold x$ of variables can be finite or infinite.

\medpagebreak
Since we deal with generating functions, a short notation for generating
functions is in
order. We write
$$GF(M;w):=\sum _{x\in M} w(x)\tag2.1.5$$
for the generating function
 of a set $M$ with respect to a weight function $w$.

\medpagebreak
The $q$-notations which will be used are
$[\al]_q=1-q^\al$, $[n]_q!=[1]_q[2]_q\dotsb [n]_q$, $[0]_q!=1$,
$$\align(a;q)_k&=\prodl _{j=0} ^{k-1}(1-aq^j)\ ,\text { and
}(a;q)_0=1,\\
(a;q)_\infty &=\prodl _{j=0} ^{\infty}(1-aq^j)\ ,
\endalign$$
so that in particular $[n]_q!=(q;q)_n$, and 
$$\bmatrix n\\k\endbmatrix_q=\cases \dfrac{[n]_q\cdot
[n-1]_q\dotsb[n-k+1]_q}
{[k]_q!}&k\ge0\\
0&k<0\endcases\ .$$
The base $q$ in $[\al]_q$, $[n]_q!$, $(a;q)_k$, $(a;q)_\infty$, and 
$\[\smallmatrix n\\k\endsmallmatrix\]_q$ will in
most cases be omitted. Only if the base is different from $q$ it
will be explicitely stated.

The basic hypergeometric series $_{p+1}\phi_p$ is defined by
$$_{p+1}\phi_p\,\[\matrix a_1,\dots,a_{p+1}\\
b_1,\dots,b_{p}\endmatrix;q,z\]=\sum _{i=0} ^{\infty}
\frac {(a_1;q)_i\,(a_2;q)_i\dotsb(a_{p+1};q)_i}
{(q;q)_i\,(b_1;q)_i\dotsb(b_p;q)_i}z^i.$$
An excellent reference book for basic hypergeometric series is
\cite{14}. We will frequently refer to it.

\subheading{2.2. Two involutions and nonintersecting lattice paths}
In order to make the arguments in sections~3 to 5
 more transparent, it is perhaps
appropriate to recapitulate the usual procedure with nonintersecting
lattice paths (cf\. \cite{16, 17, 41, section~1}), 
before going into the major counting theory.

Given two lattice points in the integer lattice $\Z^2$,
 $\A=(A_1,A_2)$ and $\E=(E_1,E_2)$, we denote the set of all paths
from $\A$ to $\E$ by $P(\A\to\E)$. For the number of those paths we
have
$$\v{P(\A\to\E)}=\binom{E_1+E_2-A_1-A_2}{E_1-A_1}\ .\tag2.2.1$$
As usual, for a set $S$ by $\vert S\vert$ we mean
the cardinality of $S$.
Let $\A_i=(A_1^{(i)},A_2^{(i)})$ and $\E_i=(E_1^{(i)},E_2^{(i)})$,
$i=1,2,\dots,r$, be
lattice points. Set $\bold A:=(\A_1,\dots,\A_r)$ and $\bold E:=(\E_1,\dots,\E_r)$.
The set of all families $(P_1,\dots,P_r)$ of lattice paths where $P_i$
goes from $\A_i$ to $\E_i$, $i=1,\dots,r$,
 is denoted by $P(\bold A\to\bold E)$. A
family of lattice paths is called {\it intersecting} if 
there are  two
paths in the family which have a point in common, if not the family
is called {\it nonintersecting}. Two {\it paths} which have a point in
common will also be called {\it intersecting}. The set of families
$(P_1,\dots,P_r)$ of
nonintersecting lattice paths where $P_i$ goes from $\A_i$ to $\E_i$
is denoted by $P(\bold A\to\bold E)^+$, while the set of families
$(P_1,\dots,P_r)$ of intersecting lattice paths is denoted by
$P(\bold A\to\bold E)^-$.

Now let $\A_i,\E_i$ as above and
$$A_1^{(1)}\le
A_1^{(2)}\le \dots\le A_1^{(r)} \text {\quad and\quad }A_2^{(1)}\ge
A_2^{(2)}\ge \dots\ge A_2^{(r)}\ ,\tag2.2.2a$$
and
$$E_1^{(1)}\le
E_1^{(2)}\le \dots\le E_1^{(r)} \text {\quad and\quad }E_2^{(1)}\ge
E_2^{(2)}\ge \dots\ge E_2^{(r)}\ .\tag2.2.2b$$
To count the number $\vert P(\bold A\to\bold E)^+\vert$ 
of all families $(P_1,\dots,P_r)$ 
of nonintersecting lattice paths, $P_i:\A_i\to\E_i$, the following
procedure is used.  Obviously the relation
$$\v{P(\bold A\to\bold E)^+}=\v{P(\bold A\to\bold E)}-\v{P(\bold A\to\bold
E)^-}\tag2.2.3$$
holds. 
 Let $\frak S_r$ be the symmetric group of order $r$.
For a permutation $\si\in\frak S_r$ define $\bold A_\si$ to be the
$r$-tuple $(\A_{\si(1)},\A_{\si(2)},\dots,\A_{\si(r)})$. In
particular, we have $\bold A_{id}=\bold A$. The trick is
to consider the sets $P(\bold A_\si\to\bold E)^-$, $\si\in\frak S_r$,
i.e\. one allows permutations of the starting points. We are going to
construct a map $\Om$ which acts on intersecting families.
Suppose that the
family $\frak P=(P_1,\dots,P_r)$ 
is an element of $P(\bold A_\si\to\bold E)^-$. Among all
meeting points between any two paths of that family consider the
right-most meeting points, and among these the highest meeting point.
To be precise, if $(X,Y)$ is this meeting point just obtained,
then for any other meeting point $(x,y)$ we have
$$x<X,\text {\quad or if }x=X\text { then }Y\ge y.\tag2.2.4$$
Among all pairs of paths which have $(X,Y)$ in common let
$(P_I,P_J)$ be that pair for which $(I,J)$ is minimal with respect to
the lexicographical order of pairs of integers. To be precise, if
$(P_i,P_j)$ is another pair of paths with common point $(X,Y)$ then
$$I<i,\text {\quad or if }I=i\text { then }J\le j.\tag2.2.5$$
It is a simple matter of fact that by (2.2.4) the point $(X,Y)$ is the last
meeting point between $P_I$ and $P_J$.
Denote this last meeting point by $\S$.
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 $\A_I$ to $\S$, and $P_I^{(2)}$ is the
portion of $P_I$ between $\S$ and $\E_I$. Analogously, $P_J$ by $\S$ is
decomposed 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
tails are preserved. Thus we obtain the new family
$\Om(\frak P)=(P_1,\dots,P'_I,\dots,P'_J,\dots,P_r)$. Obviously it is an element
of $P(\bold A_{\si(IJ)}\to\bold E)$. ($(IJ)$ denotes the
transposition which exchanges $I$ and $J$. $\si(IJ)$ is the
composition of $\si $ and $(IJ)$.) Obviously this new family is again
intersecting, therefore it is an element of $P(\bold A_{\si(IJ)}\to\bold
E)^-$. 
Moreover, since nothing was
changed {\it after} the point $\S$, $\S$ is also the right-most and
highest meeting point for the family $\Om(\frak P)$, and $I$ and $J$ are
also
the minimal indices for intersecting pairs of paths of the family
$\Om(\frak P)$. Therefore when applying the {\it interchanging
procedure} $\Om$
 to $\Om(\frak P)$, one arrives at $\frak P$ again. Consequently $\Om$ is
an involution on 
$$\bigcup _{\si\in\frak S_r} ^{}P(\bold A_\si\to\bold E)^-\ ,
\tag2.2.6$$ 
and moreover a bijection between the subsets
$$\bigcup _{\si\text { even}} ^{}P(\bold A_\si\to\bold E)^-
\quad \text {and}\quad 
\bigcup _{\si\text { odd}} ^{}P(\bold A_\si\to\bold E)^-\ .
$$
This last fact may be formulated in a different way. On the set
$$\bigcup _{\si\in\frak S_r} ^{}P(\bold A_\si\to\bold E)\ ,
\tag2.2.7$$ 
we introduce the weight function $\om$ by
$$\om(\frak P)=\sgn \si\quad \quad \text {if }\frak P\in P(\bold
A_\si\to\bold E).$$
Then $\Om$ is a {\it sign reversing} involution on the set (2.2.6)
with respect to the weight function $\om$.
As usual, $\Om$ being sign-reversing with respect to $\om$ 
means that $\om(\Om(\frak P))=-\om(\frak P)$.
From this we get
$$\sum _{\si\in \frak S_r} ^{}\sgn\si\,\vert P(\bold A_\si\to\bold
E)^-\vert=0\ .
\tag2.2.8$$
By consecutive use of (2.2.3), (2.2.8), and (2.2.1), and by
 the observation that by (2.2.2) we have
$$P(\bold A_\si\to\bold E)^-=P(\bold A_\si\to\bold E)\quad \text {if
}\si\ne id,\tag2.2.9$$
 we obtain
$$\align \v{P(\bold A\to\bold E)^+}&=\v{P(\bold A\to\bold E)}-\v{P(\bold A\to\bold
E)^-}\\
&=\v{P(\bold A\to\bold E)}+
\sum _{\si\in\frak S_r,\, \si\ne id} ^{}\sgn \si\,\vert P(\bold A_\si\to\bold
E)^-\vert\\
&=\sum _{\si\in\frak S_r} ^{}\sgn \si\,\vert P(\bold A_\si\to\bold
E)\vert\\
&=\sum _{\si\in\frak S_r} ^{}\sgn \si\,\prod _{i=1}
^{r}\v{P(\A_{\si(i)}\to \E_i)}\\
&=\sum _{\si\in\frak S_r} ^{}\sgn \si\,\prod _{i=1}
^{r}\binom{E_{1}^{(i)}+E_{2}^{(i)}-A_{1}^{(\si(i))}-A_{2}^{(\si(i))}}
{E_{1}^{(i)}-A_{1}^{(\si(i))}}\\
&=\det_{1\le s,t\le r}\(\,\binom{E_{1}^{(s)}+E_{2}^{(s)}-A_{1}^{(t)}-A_{2}^{(t)}} 
{E_{1}^{(s)}-A_{1}^{(t)}}\,\).\tag2.2.10
\endalign$$

Since the set of edges trivially does not change
under the above described 
interchanging procedure, this procedure also
preserves edge weights (by which we mean weights which depend on the
position of the path's edges in $\Z^2$) 
and therefore can also be used for the
counting of intersecting lattice paths with respect to edge weights
(see \cite{17, 41, section~1}).
But interchanging portions of paths does not at all take care of the
major index or strange major index of the paths.
So, in subsections~3.1 and 4.1, the interchanging procedure $\Om$ 
has to be modified in order to work
with the major and the strange major index.

\bigpagebreak
In subsections~3.2 and 4.2 we are going to count families of
nonintersecting lattice
paths with given starting and final points, which in addition do not
cross the line $x=y$, by major index and strange major index,
respectively. What we are going to use in these sections are
modifications of the following procedure which yields the {\it
number} of
all those families. Again we are going to construct a sign-reversing
involution, which we this time denote by $\Th$.
 The idea is to combine the above described
interchanging procedure with the {\it reflection principle} (see e.g\.
\cite{8, p.~22}). 
Recall that the reflection principle serves to count all
 paths from
$\A=(A_1,A_2)$ to $\E=(E_1,E_2)$ which do not cross the line $x=y$.
 Suppose that $A_1\ge A_2$
and $E_1\ge E_2$, i.e\. that $\A$ and $\E$ lie below or on the
line $x=y$. Suppose that we want to count all the paths from $\A$ to
$\E$ which {\it lie below $x=y$} thereby being allowed to touch $x=y$. If
in the sequel we say that ``a path lies below the line $g$" we
{\it always}
mean that it is allowed to touch $g$, the same holding for ``above".
 The reflection principle shows that the paths from $\A$
to $\E$ which {\it cross} $x=y$ are in one-to-one correspondence with
the paths from $(A_2-1,A_1+1)$ to $(E_1,E_2)$. This is seen by
reflecting a crossing path's initial portion up to the {\it last} point
which lies above $x=y$ in the line $x=y-1$. (This differs from the
presentation in \cite{8}, where the first point is considered.) 
The number of paths which lie below $x=y$ (and hence
do not cross $x=y$) then is obtained as the difference between the
number of {\it all} paths from $(A_1,A_2)$ to $(E_1,E_2)$ and the
number of {\it all} paths from $(A_2-1,A_1+1)$ to $(E_1,E_2)$. Let us
denote the reflection in the line $x=y-1$ by $\RR$. 

As before, let $\A_i=(A_1^{(i)},A_2^{(i)})$ and
$\E_i=(E_1^{(i)},E_2^{(i)})$,
$i=1,2,\dots,r$, be
lattice points which satisfy (2.2.2). 
Again, set $\bold A:=(\A_1,\dots,\A_r)$ and $\bold E:=(\E_1,\dots,\E_r)$.
The set of all families $(P_1,\dots,P_r)$ of lattice paths, where $P_i$
goes from $\A_i$ to $\E_i$, $i=1,\dots,r$,
this time for convenience
is denoted by $Q(\bold A\to\bold E)$. We want to determine
the number of all families
$(P_1,\dots,P_r)$ of
nonintersecting lattice paths which do not cross $x=y$,
$P_i$ going from $\A_i$ to $\E_i$.
The problem only makes sense if all the points
 $\A_i$ and $\E_i$ 
lie on one side of the line $x=y$. For the following we assume  
that the points $\A_i,\E_i$ lie below or on the line $x=y$,
i.e\.
$$A_1^{(i)}\ge A_2^{(i)}\text {\quad and\quad }E_1^{(i)}\ge
E_2^{(i)},\quad i=1,2,\dots,r.
\tag2.2.11$$
The set of families $(P_1,\dots,P_r)$ of
nonintersecting lattice paths which lie below $x=y$,
$P_i$ going from $\A_i$ to $\E_i$,
is denoted by $Q(\bold A\to\bold E)^+$, while the set of families
$(P_1,\dots,P_r)$ of lattice paths which are either intersecting or
contain a path which crosses $x=y$ is denoted by
$Q(\bold A\to\bold E)^-$. 

What we want to determine is the number of families of
nonintersecting paths lying below $x=y$, i.e\.
we want to determine the number $\v{Q(\bold A\to\bold E)^+}$.
Obviously the relation
$$\v{Q(\bold A\to\bold E)^+}=\v{Q(\bold A\to\bold E)}-\v{Q(\bold A\to\bold
E)^-}\tag2.2.12$$
holds. 
Just as we above allowed permutations of the starting points, here we
allow permutations {\it and reflections} of the starting points.
We extend the reflection in the line $x=y-1$, $\RR$,
to $r$-tuples of points in the following way. Let $\et$ be an
$r$-tuple consisting of 0's and 1's, $\et\in
\{0,1\}^r$. By $\RR^\et\bold A$ we mean the $r$-tuple
$(\RR^{\et_1}\A_1,\dots,\RR^{\et_r}\A_r)$, where of course $\RR^0$
means the identity. Now we consider the sets $Q(\RR^\et\bold
A_\si\to\bold E)^-$. 
Suppose that the
family $\frak P=(P_1,\dots,P_r)$ 
is an element of $Q(\RR^\et \bold A_\si\to\bold E)^-$. Among all
meeting points between any two paths of that family and all meeting
points of any path with the line $x=y-1$, consider the
right-most meeting points, and among these the highest meeting point.
Again this is understood in the sense of (2.2.4). Denote this meeting
point by $\S$. Now we distinguish
between two cases. If $\S$ is a common point of two paths of the
family $\frak P$, then, as before, 
among the pairs of paths which have $\S$ in
common, choose $(P_I,P_J)$ with $(I,J)$ being minimal in the sense of
(2.2.5) and apply the above described interchanging procedure, thus
obtaining the new family $\Th(\frak P)=(P_1,\dots,P'_I,\dots,P'_J,\dots,P_r)$.
It is an element
of $Q(\RR^{\et^{(IJ)}} \bold A_{\si(IJ)}\to\bold E)^-$, where
$\et^{(IJ)}$ is $\et$ with the $I$'th and $J$'th coordinate
exchanged. To be precise, $\et_i^{(IJ)}=\et_i$ for $i\ne I,J$, 
$\et^{(IJ)}_I=\et_J$, and $\et^{(IJ)}_J=\et_I$.
On the other hand, if $\S$ is not a common point then it must lie on
$x=y-1$. Among the paths which go through $\S$ choose $P_I$ with $I$
being minimal. Let the image of $P_I$ under application of the 
reflection principle be denoted by $P''_I$. Here, ``applying the reflection
principle to a path $P$" is understood to mean the reflection of the
initial portion of $P$ up to the last meeting point with $x=y-1$ in
the line $x=y-1$.
We then obtain the new
family $\Th(\frak P)=(P_1,\dots,P''_I,\dots,P_r)$. This family is an
element of $Q(\RR^{\et^{(I)}}\bold A_{\si}\to\bold E)^-$, where
$\et^{(I)}$ is
given by $\et^{(I)}=(\et_1,\dots,1-\et_I,\dots,\et_r)$. Just as
above, since in both cases nothing was
changed {\it after} the point $\S$, by application of $\Th$
 to $\Th(\frak P)$, one arrives at $\frak P$ again. Consequently 
$\Th$ is an involution on
$${\bigcup _{\si\in\frak S_r,\, \et\in\{0,1\}^r} ^{}}
Q(\RR^\et\bold A_{\si}\to\bold E)^-\ .\tag2.2.13$$
Next on the set
$${\bigcup _{\si\in\frak S_r,\, \et\in\{0,1\}^r} ^{}}
Q(\RR^\et\bold A_{\si}\to\bold E)\ .\tag2.2.14$$
we introduce the weight $\th$ by
$$\th(\frak P):=(-1)^{\V\et}\sgn\si \quad \quad \text {if }\frak P\in
Q(\RR^\et\bold A_{\si}\to\bold E)^-.$$
It is easily verified that $\Th$ is sign-reversing with
respect to $\th$. From this we infer
$${\sum _{\si\in\frak S_r,\,\et\in\{0,1\}^r} ^{}}
(-1)^{\V\et}\sgn\si\,\vert Q(\RR^\et\bold A_{\si}\to\bold
E)^-\vert=0.\tag2.2.15$$
By consecutive use of (2.2.12), (2.2.15), and (2.2.1), and by
 the simple observation that we have
$$Q(\RR^\et\bold A_\si\to\bold E)^-=Q(\RR^\et\bold A_\si\to\bold E)\quad 
\text {if
}(\si,\et)\ne (id,\bold 0)\ ,\tag2.2.16$$
 we obtain
$$\align \vert Q(\bold A&\to\bold E)^+\vert=\v{Q(\bold A\to\bold E)}
-\v{Q(\bold A\to\bold
E)^-}\\
&=\v{Q(\bold A\to\bold E)}+
\underset (\si,\et)\ne (id,\bold 0)\to
{\sum _{\si\in\frak S_r,\, \et\in\{0,1\}^r} ^{}}
(-1)^{\V\et}\sgn \si\,\vert Q(\RR^\et\bold A_\si\to\bold
E)^-\vert\\
&=\sum _{\si\in\frak S_r,\, \et\in\{0,1\}^r} ^{}
(-1)^{\V\et}\sgn \si\,\vert Q(\RR^\et\bold A_\si\to\bold
E)\vert\\
&=\sum _{\si\in\frak S_r} ^{}\sgn \si\,\prod _{i=1}
^{r}(\v{P(\A_{\si(i)}\to \E_i)}-\v{P(\RR\A_{\si(i)}\to \E_i)})\\
&=\sum _{\si\in\frak S_r} ^{}\sgn \si\,\prod _{i=1}
^{r}\Bigg(\binom{E_{1}^{(i)}+E_{2}^{(i)}-A_{1}^{(\si(i))}-A_{2}^{(\si(i))}}
{E_{1}^{(i)}-A_{1}^{(\si(i))}}\\
&\hskip4cm
-\binom{E_{1}^{(i)}+E_{2}^{(i)}-A_{1}^{(\si(i))}-A_{2}^{(\si(i))}}
{E_{2}^{(i)}-A_{1}^{(\si(i))}-1}\Bigg)\\
&=\det_{1\le s,t\le r}\(\,\binom{E_{1}^{(s)}+E_{2}^{(s)}-A_{1}^{(t)}-A_{2}^{(t)}} 
{E_{1}^{(s)}-A_{1}^{(t)}}-
\binom{E_{1}^{(s)}+E_{2}^{(s)}-A_{1}^{(t)}-A_{2}^{(t)}}
{E_{2}^{(s)}-A_{1}^{(t)}-1}\,\).\\
\tag2.2.17
\endalign$$

