\input amstex.tex 
\documentstyle{amsppt} 
\NoRunningHeads
\catcode`\@=11
\def\item"#1"{\par\noindent\hang%
  \setbox0=\hbox{\rm#1\enspace}\ifdim\wd0>\the\parindent%
  \box0\else\hbox to \parindent{\rm#1\hfil}\enspace\fi\ignorespaces}
\let\plainitem@\item
\catcode`\@=13
\def\sgn{\operatorname{sgn}}
\def\pmaj{\operatorname{maj'}}
\def\maj{\operatorname{maj}}
\magnification1200
\hsize15.6truecm
\vsize22.8truecm
\topmatter 
\title $q$--Generalization of a ballot problem 
\endtitle 
\author C.~Krattenthaler\\ S.~G.~Mohanty
\endauthor 
\affil 
Institut f\"ur Mathematik der Universit\"at Wien,\\
Strudlhofgasse 4, A-1090 Wien, Austria.\\\vskip6pt
McMaster University,\\
Hamilton, Ontario, Canada L8S\,4K1
\endaffil 
\address{Institut f\"ur Mathematik der Universit\"at Wien,
Strudlhofgasse 4, A-1090 Wien, Austria.}\endaddress
\address{McMaster University,
Hamilton, Ontario, Canada L8S\,4K1.}\endaddress
\subjclass{Primary 05A15;
 Secondary 05A10, 05A17, 05A30}\endsubjclass
\keywords{Lattice paths, major index, ballot problem}\endkeywords
\abstract{$n$--dimensional lattice paths which do not touch the
hyperplanes $x\sb
i-x\sb
{i+1}=-1$, $i=1,2,\dots ,n-1$, and $x\sb
n-x\sb
1=-1-K$
are enumerated by certain statistics, one of which is
 MacMahon's major index, the others being variations of it. 
By a reflection--like proof, 
a formula involving determinants is obtained. It is a $q$--extension
of Filaseta's (J.~Combin. Theory A 39 (1985), 102--111) expression for
the number of elections in a specific ballot problem.}
\endabstract
\endtopmatter
\document

\subheading{1.~Introduction} In \cite{2} Filaseta considered the
following ballot problem. Let $a\sb
1,\mathbreak a\sb
2,\dots,a\sb
n$ and
$t\sb
1,t\sb
2,\dots,t\sb
n$ be positive integers such that
$$a\sb
i<a\sb
{i-1}+t\sb
i\quad \quad \text {for }i=1,2,\dots,n\ ,$$
where we take $a\sb
0=a\sb
n$ in the case $i=1$. Suppose $n$ candidates
$A\sb
1,A\sb
2,\dots,A\sb
n$ in an election in which candidate $A\sb
i$ received
$a\sb
i$ votes, $i=1,2,\dots,n$. Let $A\sb
i(m)$ denote the number of votes
$A\sb
i$ received after the first $m$ votes have been cast,
$i=1,2,\dots,n$. How many possible elections are there such that
$$A\sb
i(m)<A\sb
{i-1}(m)+t\sb
i\quad \quad \text {for }i=1,2,\dots,n\text {
and }m=1,2,\dots,\sum \sb
{i=1} \sp
{n}a\sb
i\ ,$$
where again we take $A\sb
0(m)=A\sb
n(m)$ in the case $i=1$. Using an
analytical argument, Filaseta obtained the following expression for
this number of elections, 
$$\underset{u\sb
1+\dots +u\sb
n=0}\to{\sum \sb
{u\sb
1\in{\Bbb Z}}\dots \sum
\sb
{u\sb
n\in{\Bbb Z}}} (a\sb
1+\dots+a\sb
s)!\det\sb
{1\le i,j\le n} (1/b\sb
{ij}!)\ ,\tag 1.1$$ where
$$b\sb
{ij}=a\sb
j+u\sb
i\sum \sb
{\nu =1} \sp
{n}t\sb
{\nu}+\sum \sb
{\nu =1} \sp
{i}t\sb
\nu -\sum
\sb
{\nu =1} \sp
{j}t\sb
{\nu}\ .$$

This ballot problem is equivalent to the problem of counting
$n$--di\-men\-sional lattice paths from $\pmb 0$ to $\pmb
a=(a\sb
1,a\sb
2,\dots,a\sb
n)$, consisting of positive unit steps, which do
not touch any one of the hyperplanes 
$$x\sb
i=x\sb
{i-1}+t\sb
i\quad \quad \text {for }i=1,2,\dots,n\ ,\tag 1.2$$
where again $x\sb
0:=x\sb
n$. This is seen by interpreting a path $p$
from $\pmb 0$ to $\pmb a$ by an election in which the $m$--th vote
is a vote for candidate $A\sb
j$ if and only if the $m$--th step in the
path $p$ is a step in the $x\sb
j$--direction.

In this paper we consider the problem of counting paths from $\pmb 0$
to $\pmb a$ which do not touch any one of the hyperplanes in (1.2)
by MacMahon's \cite{5} greater index, which nowadays frequently is
called major index. (To be precise, we consider the equivalent
problem of counting lattice paths from $\pmb{\mu}$ to $\pmb{\lambda} $
not touching any one of the hyperplanes in (2.2) and (2.3).)  The
counting formula (Theorem~{1} in section~{3})
which we obtain is a $q$--analogue of (1.1). 
Besides, this result
generalizes previous ones of one of the authors \cite{4}. 
It is easily seen that, using the terminology of Gessel and
Zeilberger
\cite{3}, Filaseta's result solves the problem of counting lattice
paths consisting of positive unit steps in a Weyl chamber
corresponding to the affine root system $S(A\sb
n)$. Hence, our results
give a solution for the problem of $q$-counting lattice paths in a
Weyl chamber of $S(A\sb
n)$. The key for
proving Theorem~{1} lies in extending the proof method of
\cite{4} to this generalized path enumeration problem. Since this
method heavily relies on Zeilberger's \cite{6}
 reflection proof for
the classical $n$--candidate ballot problem, the first thing to be
done is to give a reflection proof of Filaseta's formula (1.1). This
is the contents of section $4$. (In fact, the arguments in section~4
are just the same as those in the proof of Theorem~1 in \cite{3} but
specialized to $S(A\sb
n)$.) Section $2$ contains all relevant
definitions. Finally, in section $5$, we give the bijections which
replace the reflections of section $4$, thus establishing a
combinatorial proof of Theorem~{1}. Section~6 presents
an extension of Theorem~1 to a family of major-like statistics
(Theorem~2). This result does not only include the case of counting by
MacMahon's greater index as special case,
 which is discussed in the preceding
section,  but also the corresponding result for
counting lattice paths by MacMahon's lesser index \cite{5, p.~136}.

\subheading{2.~Definitions} We use the usual multidimensional
notation. If $\pmb \lambda=(\lambda\sb
1,\lambda\sb
2,\dots,\mathbreak\lambda\sb
n)$ and
$\pmb\mu=(\mu\sb
1,\mu\sb
2,\dots,\mu\sb
n)$, then
$\vert\pmb\lambda\vert=\lambda\sb
1+\lambda\sb
2+\dots +\lambda\sb
n$, $\pmb\lambda -\pmb\mu
=(\lambda\sb
1-\mu\sb
1,\lambda\sb
2-\mu\sb
2,\dots,\lambda\sb
n-\mu\sb
n)$, and
$\binom{\vert\pmb\lambda\vert}{\pmb \lambda
}=\vert\pmb\lambda\vert
!/\lambda
\sb
1!\,\lambda
\sb
2!\dotsb \lambda
\sb
n!$. If $\lambda\sb
i\geq\mu\sb
i$ for all
$i=1,2,\dots,n$, we write $\pmb\lambda\geq \pmb \mu$.

Let $q$ be an indeterminate. The $q$--notations we need are
$[\alpha
]=(1-q\sp
{\alpha
})$, $[m]!=[m]\cdot [m-1]\dotsb [1]$, $[0]!=1$, and
$\left [\smallmatrix\vert\pmb\lambda\vert\\\pmb\lambda
\endsmallmatrix \right
]=[\vert\pmb\lambda\vert]!/
[\lambda
\sb
1]!\,[\lambda
\sb
2]!\dotsb [\lambda
\sb
n]!$.

In the sequel we assume $K$ to be an arbitrary fixed positive
integer. Let $K\sb
n$ stand for the set of all $n$--tuples $\pmb\lambda$ of
integers with 
$$\lambda\sb
1\geq\lambda\sb
2\geq \dots\geq\lambda\sb
n\geq\lambda\sb
1-K\ .$$ Let
$S\sb
n$ denote the symmetric group of order $n$. Given $\sigma\in S\sb
n$ we
write $\pmb\lambda\sb
\sigma$ for $(\lambda\sb
{\sigma(1)},\lambda\sb
{\sigma(2)},\dots,\lambda\sb
{\sigma(n)})$.
For the set of all permutations of the multiset
$\{1\sp
{\mu\sb
1},2\sp
{\mu\sb
2},\dots,\mathbreak
n\sp
{\mu\sb
n}\}$ (the multiset consisting of
$\mu\sb
i$ copies of $i$, $i=1,2,\dots,n$) 
 we write $S(\pmb\mu)$.

Throughout this paper, a lattice path $p$ 
will be a finite sequence $(p(0),p(1),\dots,\mathbreak
p(L))$ 
of points $p(i)$ in the integer lattice ${\Bbb Z}\sp
n$, where $p(i)\in{\Bbb
Z}\sp
n$
and $p(i+1)-p(i)=E\sb
j$ for
some $j$, $1\leq j\leq n$, $i=0,1,2,\dots$. $E\sb
j$ stands for the vector with the
$j$--th coordinate being equal to $1$, all other being equal to $0$.
$[p(i)]\sb
k$ will denote the $k$--th coordinate of the $i$--th
point on the path $p$. A lattice path $p$ from $\pmb\mu$ to
$\pmb\lambda$ can be symbolized by a pair $(\pmb\mu,\pi)$, where
$\pmb\mu =p(0)$ and $\pi\in S(\pmb\lambda-\pmb\mu)$. $\pi$ is obtained by
proceeding along the path, starting at its first point $\pmb\mu$,
and successively writing a $k$ for each step in the $x\sb
k$--direction.
To be precise, $\pi=\pi\sb
1\dots\pi\sb
L$, where $L=\vert
\pmb\lambda-\pmb\mu\vert$
and $\pi\sb
i=k$ if and only if $p(i)-p(i-1)=E\sb
k$. Conversely, if a path
$p$ is given by $(\pmb\mu,\pi)$, the points of $p$ are determined by
$$p(i)=\pmb\mu +\sum \sb
{k=1} \sp
{n}E\sb
k\cdot\vert\{r:1\leq r\leq i \text {
and }\pi\sb
r=k\}\vert\ .\tag 2.1$$
To give an example, take $n=3$ and 
$p\sb
0=((1,2,1)$, $(1,2,2)$, $(1,2,3)$, $(2,2,3)$, $(2,3,3)$, $(3,3,3))$. 
Then $p\sb
0$
is symbolized by the pair $((1,2,1)$, $33121)$.

By $N(\pmb\mu \to\pmb\lambda)$ we denote the set of all lattice paths
from $\pmb\mu$ to $\pmb\lambda$. We write $N(\pmb\mu\to\pmb\lambda)\sp
+$
for the set of all lattice paths from $\pmb\mu$ to $\pmb\lambda$ whose
points all lie in $K\sb
n$. For $\pmb\lambda,\pmb\mu\in K\sb
n$ the set
$N(\pmb\mu\to\pmb\lambda)\sp
+$ is equal to the set of all lattice paths
from $\pmb \mu$ to $\pmb\lambda$ which do not touch any one of the
hyperplanes
$$x\sb
i-x\sb
{i+1}=-1,\quad \quad i=1,2,\dots,n-1\ ,\tag 2.2$$
and $$x\sb
n-x\sb
1=-1-K\ .\tag 2.3$$ Let $H\sb
i$ denote the hyperplane
$x\sb
i-x\sb
{i+1}=-1$, $i=1,2,\dots,n-1$, let $H\sb
n$ denote the hyperplane
in (2.3), and let $R\sb
i$ be the reflection with respect to $H\sb
i$,
$i=1,2,\dots,n$. $N(\pmb\mu\to\pmb\lambda)\sp
-$ stands for the set of all 
lattice paths from $\pmb\mu$ to $\pmb\lambda$ which touch at least one
of the hyperplanes in (2.2) and (2.3).

Next, for a given multiset permutation $\pi=\pi\sb
1\pi\sb
2\dots\pi\sb
L$ we
define the major statistics by 
$$\maj\pi=\sum \sb
{i=1} \sp
{L-1}i\cdot\chi\left(\pi\sb
i>\pi\sb
{i+1}\right)\ .$$
($\chi(A)=1$ if $A$ is true, and $\chi (A)=0$ otherwise.) Having in
mind the representation of a lattice path $p$ by a pair
$(\pmb\mu,\pi)$, we extend $\maj$ to lattice paths by defining $\maj
p=\maj\pi$, if $p=(\pmb\mu,\pi)$. Finally we introduce the
generating function 
$$G(\pmb\mu\to\pmb\lambda;q)=\sum \sb
{p}q\sp
{\maj p}\ ,$$ where the sum is
taken over all $p\in N(\pmb\mu\to\pmb\lambda)$. Analogously, 
$$G(\pmb\mu\to\pmb\lambda;q)\sp
+=\sum \sb
{p}q\sp
{\maj p}\ ,$$ where the sum
is over all $p\in N(\pmb\mu\to\pmb\lambda)\sp
+$, and
$$G(\pmb\mu\to\pmb\lambda;q)\sp
-=\sum \sb
{p}q\sp
{\maj p}\ ,$$ where the sum
is over all $p\in N(\pmb\mu\to\pmb\lambda)\sp
-\ .$

\subheading{3.~Formulation of the Theorem} In section 1 it was shown
that Filaseta's ballot problem is equivalent with the problem of
counting all lattice paths from $\pmb 0$ to $\pmb a$ which do not
touch any one of the hyperplanes in (1.2). Let $\pmb
y=(y\sb
1,y\sb
2,\dots,y\sb
n)$ be an element of ${\Bbb Z}\sb
n$. By performing the
transformation $\pmb y\to\pmb z$, where
$$y\sb
i=z\sb
i+\sum \sb
{\nu =1} \sp
{i}t\sb
\nu -i\quad \text {for\quad
}i=1,2,\dots,n\ ,$$ 
it is seen that the above lattice path
counting problem is equivalent with the problem of counting all
lattice  paths from $\pmb\mu$ to $\pmb\lambda$ which do not touch any
one of the hyperplanes in (2.2) and (2.3), where
$$\align \mu\sb
i&=i-\sum \sb
{\nu =1} \sp
{i}t\sb
\nu\ ,\\
\lambda\sb
i&=a\sb
i+i-\sum \sb
{\nu =1} \sp
{i}t\sb
\nu\ ,\\
\intertext {and} K&=\sum \sb
{\nu=1} \sp
{n}t\sb
\nu-n\ .
\endalign$$ 
The major counting extension of this counting problem,
which is proved in section 5, is the following.

\proclaim{Theorem~{1}} Let $\pmb\lambda,\pmb\mu\in K\sb
n$ and
$\pmb\lambda\geq\pmb\mu$. The generating function $\sum q\sp
{\maj p}$,
where the sum is over all lattice paths from $\pmb\mu$ to $\pmb\lambda$
which do not touch any one of the hyperplanes in $(2.2)$ and $(2.3)$, is
given by
$$\multline 
G(\pmb\mu\to\pmb\lambda;q)\sp
+\\=\sum \sb
{\pmb
u\in U\sb
n}[\vert\pmb\lambda-\pmb\mu\vert]!\det\sb
{1\le s,t\le n} \left(q \sp
{T(s,t,\pmb u,\pmb
\mu)}/[\lambda\sb
s-s-\mu\sb
t+t-(K+n)u\sb
s]!\right)\ ,
\endmultline$$ where $U\sb
n$ is the set
of all $n$--tuples $\pmb u=(u\sb
1,u\sb
2,\dots,u\sb
n)$ of integers with $u\sb
1+\dots +u\sb
n=0$, and
$$ 
T(s,t,\pmb
u,\pmb\mu)=(\mu\sb
t-t)(s-t)+(n-1)u\sb
s(\mu\sb
t-t)+
(K+n)((n-1)\frac {u\sb
s\sp
2} {2}+su\sb
s)\ .$$
\endproclaim
The special case $K>\vert\pmb\lambda
-\pmb\mu\vert$ (this is
the corresponding result for counting lattice paths which do not
touch any of the hyperplanes in (2.2)\,) has previously appeared in
\cite{4, Theorem~1}.

To give a concrete example, take  $n=3$, $K=2$, 
$\pmb\mu =(1,-1,-1)$ and $\pmb \lambda=(3,2,1)$. We want to count all
paths $p$ from $(1,-1,-1)$ to $(3,2,1)$ with respect to the major
index which do not touch
$x\sb
1-x\sb
2=-1$, $x\sb
2-x\sb
3=-1$, and $x\sb
3-x\sb
1=-3$. Let such a path be
represented by $p=((1,-1,-1),\pi)$ as was explained above. The
following table lists all possibilities of
$\pi$ together with the corresponding major--values. 
{\eightpoint
$$
\matrix \format\c&\quad \quad \quad \quad \c\\
\pi&\maj\pi=\maj p\\
 & \\
2312321&13\\2312312&\hphantom{1}7\\2312231&\hphantom{1}8\\2321231&11\\
2321312&10\\2321321&16\\2323112&\hphantom{1}6\\2323121&12\\
2231231&\hphantom{1}9\\
2231312&\hphantom{1}8\\2231321&14\\2233112&\hphantom{1}4\\2233121&10
\endmatrix$$}
\tenpoint Hence,
{\eightpoint$$
G((1,-1,-1)\to (3,2,1))\sp
+=
q\sp
4+q\sp
6+q\sp
7+2q\sp
8+q\sp
9+2q\sp
{10}+q\sp
{11}+q\sp
{12}+q\sp
{13}+q\sp
{14}+q\sp
{16},$$}
\tenpoint 
which agrees with the claimed expression in Theorem~1 as can be
easily checked.


\subheading{4.~The reflection proof} Let $\pmb\lambda,\pmb\mu\in K\sb
n$ and
$\pmb\lambda\geq\pmb\mu$. For the number of all lattice paths from $\pmb
\mu$ to $\pmb\lambda$, $G(\pmb\mu\to\pmb\lambda;1)$, we have
$$G(\pmb\mu\to\pmb\lambda;1)=\binom{\vert\pmb\lambda -\pmb\mu\vert}
{\pmb\lambda
-\pmb\mu}\ .\tag 4.1$$
Following Zeilberger \cite{6}, for $\sigma\in S\sb
n$ we define
$$\pmb e\sb
\sigma=(1-\sigma (1),2-\sigma(2),\dots,n-\sigma(n))\ .$$
We are going to construct a bijection between 
$$\underset \pmb u\in U\sb
n\to{\bigcup \sb
{\sigma \text {
even}}}N(\pmb\mu\sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb u\to\pmb \lambda)\sp
-\tag 4.2$$
and
$$\underset \pmb u\in U\sb
n\to{\bigcup \sb
{\sigma\text { odd}}}N(\pmb\mu\sb
\sigma
+\pmb e\sb
\sigma+(K+n)\pmb u\to\pmb\lambda)\sp
-\ ,\tag 4.3$$ which proves
$$\multline \underset \pmb u\in U\sb
n\to{\sum \sb
{\sigma\text {
even}}}G(\pmb\mu \sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb u\to\pmb\lambda;1)\sp
-\\
=\underset \pmb u\in U\sb
n\to{\sum \sb
{\sigma \text { odd}}}G(\pmb
\mu\sb
\sigma+\pmb e\sb
\sigma+(K+n)\pmb u\to\pmb\lambda;1)\sp
-\ .
\endmultline\tag 4.4$$
This is done by application of the reflection principle. Consider a
lattice path $p$ of $N(\pmb\mu\sb
\sigma +\pmb e\sb
\sigma
+(K+n)\pmb\mu\to\pmb\lambda)\sp
-$. Let $H\sb
j$ be the last hyperplane of
those in (2.2) and (2.3) which the path $p$ meets. If $j\leq n-1$
reflection with respect to $H\sb
j$ has the effect
$$R\sb
j(x\sb
1,\dots,x\sb
j,x\sb
{j+1},\dots,x\sb
n)=(x\sb
1,\dots,x\sb
{j+1}-1,x\sb
j+1,
\dots,x\sb
n)\ ,\tag 4.5$$ while reflection with respect to $H\sb
n$ yields
$$R\sb
n(x\sb
1,x\sb
2,\dots,x\sb
{n-1},x\sb
n)=(x\sb
n+K+1,x\sb
2,\dots,x\sb
{n-1},x\sb
1-K-1)\
.\tag 4.6$$
Hence, for $j\leq n-1$, we have
$$R\sb
j(\pmb \mu\sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb u)=\pmb
\mu\sb
{\sigma(j,j+1)}+\pmb e\sb
{\sigma(j,j+1)}+(K+n)\pmb u\sp
{(j)}\ ,\tag 4.7$$
where $\pmb u\sp
{(j)}=(u\sb
1,\dots,u\sb
{j+1},u\sb
j,\dots,u\sb
n)$, and if $j=n$,
$$R\sb
n(\pmb\mu\sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb
u)=\pmb\mu\sb
{\sigma(1,n)}+\pmb e\sb
{\sigma(1,n)}+(K+n)\pmb u\sp
{(n)}\ ,\tag 4.8$$ where $\pmb
u\sp
{(n)}=(u\sb
n+1,u\sb
2,\dots,u\sb
{n-1},u\sb
1-1)$. ($(g,h)$ is the
transposition which exchanges $g$ and $h$. An expression of the form
$\sigma
(g,h)$ means the composition $\sigma
\circ(g,h)$ of the permutations
$\sigma
$ and $(g,h)$.) Therefore, replacing the
portion of the path $p$ until the last meeting with $H\sb
j$ by its
reflection with respect to $H\sb
j$, turns $p$ into a path of
$N(\pmb\mu\sb
{\sigma(j,j+1)}+\pmb e\sb
{\sigma(j,j+1)}+(K+n)\pmb
u\sp
{(j)}\to\pmb\lambda)\sp
-$ if $j\leq n-1$, in the case $j=n$ by this
reflection we obtain a path of $N(\pmb\mu\sb
{\sigma(1,n)}+\pmb
e\sb
{\sigma(1,n)}+(K+n)\pmb u\sp
{(n)}\to\pmb\lambda)\sp
-$. Since the reflected
path again meets $H\sb
j$ as last hyperplane, and its last meeting point
is the same, renewed application of this reflection procedure would
give the original path. Therefore this mapping in fact is an
involution which consequently defines the desired bijection
between the sets (4.2) and (4.3). This implies that (4.4) holds.

Since, because of $\pmb\mu \in K\sb
n$, for $\sigma\neq id$ or $\pmb u\neq
\pmb 0$ we have 
$$(\pmb\mu\sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb u)\notin K\sb
n\ ,$$
we get
$$\multline N(\pmb \mu\sb
{\sigma}+\pmb e\sb
\sigma +(K+n)\pmb
u\to\pmb\lambda)\sp
-=N(\pmb\mu\sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb u\to\pmb\lambda)\\
\text {for } \sigma\neq id\text { or }\pmb u\neq\pmb 0\ .
\endmultline\tag 4.9$$
Therefore, by consecutive use of (4.4), (4.9), and (4.1), we have 
$$\aligned G(\pmb\mu\to\pmb\lambda;1)\sp
+&=G(\pmb\mu\to\pmb\lambda;1)
-G(\pmb\mu\to\pmb\lambda;1)\sp
-\\
 &=G(\pmb\mu\to\pmb\lambda;1)-G(\pmb\mu\to\pmb\lambda;1)\sp
-\\
&\quad \quad \quad +\underset\pmb u\in U\sb
n\to{\sum \sb
{\sigma\in S\sb
n}}\sgn \sigma
\,G(\pmb\mu\sb
\sigma
+\pmb e\sb
\sigma +(K+n)\pmb u\to\pmb\lambda;1)\sp
-\\
&=\underset\pmb u\in U\sb
n\to{\sum \sb
{\sigma\in S\sb
n}}\sgn\sigma\,
G(\pmb\mu\sb
\sigma+\pmb e\sb
\sigma +(K+n)\pmb u\to\pmb\lambda;1)\\
&=\underset\pmb u\in U\sb
n\to{\sum \sb
{\sigma\in S\sb
n}}\sgn \sigma\,\pmatrix \vert\pmb\lambda
-\pmb\mu\vert\\\pmb\lambda-\pmb\mu\sb
\sigma -\pmb e\sb
\sigma-(K+n)\pmb u\endpmatrix\\
&=\sum \sb
{\pmb u\in U\sb
n}\vert \pmb\lambda -\pmb\mu\vert !\det
(1/(\lambda\sb
s-s-\mu\sb
t+t-(K+n)u\sb
s)!)\ .
\endaligned \tag 4.10$$

\subheading{5.~Proof of the Theorem} To prove Theorem~{1}, the
reflection procedure of section 4 must be modified because, when
reflecting a part of a lattice path, nothing can be said about the
major of its image. Therefore, in order to extend the reflection
proof to $q\neq 1$, we construct a map $\varphi$, which sends the initial
point of a path to the same point as the reflection procedure would
do, but is (in a certain sense) also $\maj$--preserving. 
Let the weight $w(p)$ of a path $p\in N(\pmb\mu\sb
\sigma +\pmb e\sb
\sigma+(K+n)\pmb
u\to\pmb\lambda)$ be defined by
$$w(p)=q\sp
{\sum \sb
{s=1} \sp
{n}T(s,\sigma (s),\pmb u,\pmb\mu)}q\sp
{\maj p}\
,\tag 5.1$$
where $T(s,t,\pmb u,\pmb\mu)$ is the number given in Theorem~{1}.
What we are going to do, is to construct a weight--preserving
bijection $\varphi$ between the two sets (4.2) and (4.3), which sends
the initial point of a path to the same point as the reflection
procedure would do. 

Now, let $p\in N(\pmb\mu\sb
\sigma +\pmb e\sb
\sigma+(K+n)\pmb
u\to\pmb\lambda)\sp
-$. First, suppose that the path $p$ meets $H\sb
j$ as the last hyperplane of
those in (2.2) and (2.3), and $j\leq n-1$. In \cite{4} a mapping
$\Phi$ was given satisfying the following properties (cf.
\cite{4, Def.~{3}, p.~145 (3),(4), (5.25)}):
\roster
\item $\Phi$ acts on paths which meet one of the hyperplanes
$H\sb
j$, $1\leq j\leq n-1$.
\item If the path $\overline p\in N(\pmb{\overline
\mu}\to\pmb{\overline\lambda})\sp
-$ meets $H\sb
j$ as the last hyperplane, $j\leq
n-1$, then $\Phi (\overline p)\in
N(R\sb
j(\pmb{\overline\mu})\to\pmb{\overline\lambda})\sp
-$ and 
$$\maj \Phi (\overline p)=\maj \overline
p-\overline\mu\sb
j+\overline\mu\sb
{j+1}-1\ .\tag 5.2$$
\item $\Phi $ is an involution.
\endroster
For $p$ satisfying the above properties we define 
$$\varphi(p):\, =\Phi (p)\ .$$
By (2) this immediately implies $$p\in N(\pmb\mu\sb
{\sigma(j,j+1)}+\pmb
e\sb
{\sigma(j,j+1)}+(K+n)\pmb u\sp
{(j)}\to\pmb \lambda)\sp
-\ ,$$ with the $\pmb u\sp
{(j)}$
of section 4. Moreover, using the weight property (5.2), we obtain
$$\aligned w(&\varphi(p))=q\sp
{\sum \sb
{s=1} \sp
{n}T(s,(\sigma (j,j+1))(s),\pmb
u\sp
{(j)},\pmb\mu)}q\sp
{\maj(\Phi(p))}\\
 &=q\sp
{\sum \sb
{s=1} \sp
{n}T(s,\sigma (s),\pmb u,\pmb\mu)
-\mu\sb
{\sigma(j+1)}+\sigma(j+1)+\mu\sb
{\sigma(j)}-\sigma(j)+(K+n)(u\sb
j-u\sb
{j+1})}\\
& \quad \quad \cdot q\sp
{\maj
p-\mu\sb
{\sigma(j)}-j+\sigma(j)-(K+n)u\sb
j+\mu\sb
{\sigma(j+1)}+j+1-\sigma(j+1)+(K+n)
u\sb
{j+1}-1}\\
 &=w(p)\ .
\endaligned \tag 5.3$$

Now suppose that $p$ meets $H\sb
n$ as last hyperplane. To define $\varphi(p)$
in this case, we proceed in a manner analogous to \cite{4, sec.~5}. Given a
multiset permutation $\pi=\pi\sb
1\pi\sb
2\dots \pi\sb
L$, $\pi\sb
i\in
\{1,2,\dots,n\}$, we define the difference function $d\sb
n(\pi,i)$ by
$$d\sb
n(\pi,i)=\vert \{r:r\leq i\text { and }\pi\sb
r=n\}\vert - \vert
\{r:r\leq i\text { and }\pi\sb
r=1\}\vert\ .$$
$d\sb
n(\pi,i)$ is the difference between the number of $n$'s and the
number of $1$'s in $\pi\sb
1\pi\sb
2\dots\pi\sb
i$. In the following two
definitions two auxiliary maps, $\Cal L\sb
n$ and $\Cal R\sb
n$, are
introduced. $\Cal L\sb
n$ has the effect of changing a single step in
the $x\sb
1$--direction into a step in $x\sb
n$--direction, $\Cal R\sb
n$ has
the reverse effect.
\proclaim{Definition~{1}} Let $\pi=\pi\sb
1\pi\sb
2\dots\pi\sb
L$ be a
multiset permutation where the function $i\to d\sb
n(\pi,i)$ does not
reach its minimal value at $i=0$ or $i=L$. Let $k$ be the smallest
integer, $1\leq k\leq L-1$, where the function $i\to d\sb
n(\pi,i)$
reaches its minimal value, in other words
$$\align i<k&\quad \text {implies\quad }d\sb
n(\pi,i)>d\sb
n(\pi,k)\ ,\\
i\geq k&\quad \text {implies\quad }d\sb
n(\pi,i)\geq d\sb
n(\pi,k)\ .
\endalign$$
Obviously, $\pi\sb
k=1$. This given, we define $\Cal L\sb
n$ by:
\roster
\item "(A)" If $\pi$ satisfies
$$\pi\sb
e>\pi\sb
{e+1}\leq\dots\leq\pi\sb
{k-1}\leq
1<\pi\sb
{k+1}\leq\dots\leq\pi\sb
f>\pi\sb
{f+1}\ ,$$ where $1\leq e+1<f\leq
L$, and
$$\align \text {either}&\quad (a)\quad e+1<k<f\\
\text {or}&\quad (b)\quad k=e+1\text { and }\pi\sb
e>\pi\sb
{e+2}\ ,
\endalign$$ then
$$\Cal
L\sb
n(\pi)=\pi\sb
1\dots\pi\sb
e\pi\sb
{e+1}\dots\pi\sb
{k-1}\pi\sb
{k+1}\dots\pi\sb
f\,n\,\pi\sb
{f+1}
\dots\pi\sb
L\ .$$
\item "(B)" If $\pi$ satisfies
$$\pi\sb
e\leq \pi\sb
{e+1}>\dots >\pi\sb
{k-1}>1<\pi\sb
{k+1}$$ where $1\leq
e+1<k\leq L$, and $\pi\sb
{k-1}\leq\pi\sb
{k+1}$, then 
$$\Cal
L\sb
n(\pi)=\pi\sb
1\dots\pi\sb
e\,n\,\pi\sb
{e+1}\dots\pi\sb
{k-1}\pi\sb
{k+1}\dots\pi\sb
L\
.$$
\endroster
\endproclaim
(By convention, if $i>j$, the symbol $\pi\sb
i\dots\pi\sb
j$ means the
empty word. For the detailed conventions of how to read the
inequality chains, we refer the reader to \cite{4, sec.~5}.)
\proclaim{Defintion~{2}} Let $\pi\sb
1\pi\sb
2\dots\pi\sb
L$  be a
multiset permutation where $d\sb
n(\pi,L)$ exceeds the minimal value of
the function $i\to d\sb
n(\pi,i)$ by at least two. Let $(r-1)$ be the
largest integer, $0\leq r-1\leq L-1$, where $i\to d\sb
n(\pi,i)$ reaches
its minimal value, meaning
$$\align i\leq r-1&\quad \text {implies}\quad d\sb
n(\pi,i)\geq
d\sb
n(\pi,r-1)\ ,\\
i>r-1&\quad \text {implies}\quad d\sb
n(\pi,i)>d\sb
n(\pi,r-1)\ .
\endalign$$
Then $\pi\sb
r=n$. This given we define $\Cal R\sb
n$ by:
\roster
\item "(A)" If $\pi$ satisfies
$$\pi\sb
e>\pi\sb
{e+1}\leq\dots\leq\pi\sb
{r-1}<n\leq\pi\sb
{r+1}\leq\dots\leq
\pi\sb
f>\pi\sb
{f+1}\ ,$$ where $1\leq e+1<f\leq L$ and
$$\align \text {either}&\quad (a)\quad e+1<r<f\\
\text {or}&\quad (b)\quad r=f\text { and }\pi\sb
{f-1}>\pi\sb
{f+1}\ ,
\endalign$$ then
$$\Cal R\sb
n(\pi)=\pi\sb
1\dots\pi\sb
e\,1\,\pi\sb
{e+1}\dots
\pi\sb
{r-1}\pi\sb
{r+1}\dots\pi\sb
f\pi\sb
{f+1}\dots\pi\sb
L\ .$$
\item "(B)" If $\pi$ satisfies
$$\pi\sb
{r-1}<n>\pi\sb
{r+1}>\dots>\pi\sb
f\leq \pi\sb
{f+1}\ ,$$ 
where $1\leq r<f\leq L$, and $\pi\sb
{r-1}\leq \pi\sb
{r+1}$, then
$$\Cal R\sb
n(\pi)=\pi\sb
1\dots\pi\sb
{r-1}\pi\sb
{r+1}
\dots\pi\sb
f\,1\,\pi\sb
{f+1}\dots\pi\sb
L\ .$$
\endroster
\endproclaim
Following the lines of \cite{4, sec.~5}, it can be shown that $\Cal
L\sb
n$ and $\Cal R\sb
n$ are well--defined, and that
$$\Cal L\sb
n\circ \Cal R\sb
n=\Cal R\sb
n\circ \Cal L\sb
n=id\ .$$
Besides, from the definition of $\Cal L\sb
n$ and $\Cal R\sb
n$ it is
easily seen that for any multiset permutation $\pi$ there holds 
$$\maj\Cal L\sb
n(\pi)=\maj\Cal R\sb
n(\pi)=\maj\pi\ .\tag 5.4$$

Now we are able to define $\varphi(p)$ for $p$ meeting $H\sb
n$ as last
hyperplane. Let $p=(\pmb\mu\sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb u,\pi)$, then
$$\varphi(p)=(R\sb
n(\pmb\mu\sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb u),\Cal
L\sb
n\sp
{E(\sigma,K,\pmb\mu,\pmb u)}(\pi))\ ,\tag 5.5$$ where
$$\align E(\sigma,K,\pmb\mu,\pmb u)&=[\pmb\mu\sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb
u]\sb
n-[\pmb \mu\sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb u]\sb
1+K+1\\
 &=\mu\sb
{\sigma(n)}+n-\sigma(n)-\mu\sb
{\sigma(1)}-1+\sigma(1)\\
&\quad \quad +(K+n)(u\sb
n-u\sb
1)+K+1\ .
\endalign$$
If the exponent $E(\sigma,K,\pmb\mu,\pmb u)$ in (5.5) is negative, by
$\Cal L\sb
n\sp
{E(\sigma,K,\pmb\mu,\pmb u)}$ we mean $\Cal
R\sb
n\sp
{-E(\sigma,K,\pmb\mu,\pmb u)}$.


It can be shown that $\varphi$ is well-defined,
that the endpoint of $\varphi(p)$ is the same as that of $p$, that
the last meeting point with $H\sb
n$ is the same as that of $p$, and that the portion of the path after
this last meeting point remains unchanged. Hence, by
(4.8), $$\varphi(p)\in N(\pmb\mu\sb
{\sigma(1,n)}+\pmb e\sb
{\sigma(1,n)}+(K+n)\pmb
u\sp
{(n)}\to\pmb\lambda)\sp
-\ ,$$ with the $\pmb u\sp
{(n)}$ of section 4.
Moreover, by (5.4) obviously we have
$$\maj \varphi(p)=\maj p\ .\tag 5.6$$
It is easy to see that this definition again establishes an
involution.
Therefore, using (5.6) we obtain
$$\aligned w(&\varphi(p))=q\sp
{\sum \sb
{s=1} \sp
{n}T(s,(\sigma(1,n))(s),\pmb
u\sp
{(n)},\pmb\mu)}q\sp
{\maj(\varphi(p))}\\
 &=q\sp
{\sum \sb
{s=1} \sp
{n}T(s,\sigma(s),\pmb u,\pmb\mu)+
(n-1)(\mu\sb
{\sigma(1)}-\sigma(1))}\\
 &\quad \quad \cdot q\sp
{-(n-1)(\mu\sb
{\sigma(n)}-\sigma(n))+(n-1)(\mu\sb
{\sigma(n)}-\sigma(n))-(n-1)
(\mu\sb
{\sigma(1)}-\sigma(1))}\\
 &\quad \quad \cdot q\sp
{(K+n)\left((n-1)\frac {1} {2}(2u\sb
n+1-2u\sb
1+1)-(n-1)u\sb
n+1+(n-1)u\sb
1-n\right)}\\
 &\quad \quad \cdot q\sp
{\maj p} \\
 &=w(p)\ .
\endaligned \tag 5.7$$

To give an example, take $n=3$, $K=2$, $\pmb\mu
=(1,-1,-1)$, $\pmb \lambda=(3,2,1)$, $\sigma
=(123)$ (in cycle notation),
and $\pmb u=(1,0,-1)$. Then $\pmb\mu\sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb
u=(3,-2,-2)$. Consider the path $p\sb
0=\big((3,-2,-2),2233223\big)$.
This path only touches the hyperplane $H\sb
3$, which is given by
$x\sb
n-x\sb
1=-3$ (cf\. (2.3)). The meeting points are $(3,0,0)$, $(3,1,0)$, and
$(3,2,0)$, the last meeting point being $(3,2,0)$. 
To apply the mapping $\varphi
$, first we
observe that 
$$E\big((123),2,(1,-1,-1),(1,0,-1)\big)=-2\ .$$
Hence, we have
$$\varphi
(p\sb
0)=\big(R\sb
3(3,-2,-2),\Cal R\sp
2\sb
3(2233223)\big)=\big((1,-2,0),
\Cal R\sp
2\sb
3(2233223)\big)\ .$$
Using Definition~2~(A) ($e=0$, $r=3$, $f=4$), we obtain $\Cal
R\sb
3(2233223)=1223223$, and by Definition~2~(B) ($r=4$, $f=5$) $\Cal
R\sb
3(1223223)=1222123$. Hence, $\varphi
(p\sb
0)=\big((1,-2,0),1222123\big)$.
Obviously, the final point of $p\sb
0$ again is $(3,2,1)$. $\varphi
(p\sb
0)$
meets $H\sb
3$ as the last hyperplane, just as $p\sb
0$ did. Again $(3,2,0)$ is the last meeting point with $H\sb
3$ and after this point nothing was changed. 
Moreover, we
have $\maj p\sb
0=\maj \varphi
( p\sb
0)=4$. Similarly, use of Definition~1~(B)
($e=3$, $k=5$) would give $\Cal L\sb
3(1222123)=1223223$, and by
Definition~1~(A) ($e=0$, $k=1$, $f=4$) we would get $\Cal
L\sb
3(1223223)=2233223$. This establishes $\varphi
(\varphi
(p\sb
0))=p\sb
0$, which
must be satisfied, since $\varphi
$ is an involution.


Summarizing, the map $\varphi$ maps elements of the set in (4.2) onto
elements of the set in (4.3) and vice versa. Since it is an
involution it is a bijection. Moreover it is weight--preserving with
respect to $w$. Therefore the equation which generalizes (4.4) reads
$$\multline \underset \pmb u\in U\sb
n\to{\sum \sb
{\sigma \text { even}}}q\sp
{\sum \sb
{s=1}
\sp
{n}T(s,\sigma(s),\pmb u,\pmb \mu)}G(\pmb\mu\sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb
u\to\pmb\lambda;q)\sp
-\\
=\underset \pmb u\in U\sb
n\to{\sum \sb
{\sigma \text { odd}}}q\sp
{\sum \sb
{s=1}
\sp
{n}T(s,\sigma(s),\pmb u,\pmb\mu)}G(\pmb\mu\sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb
u\to\pmb\lambda;q)\sp
-\ .
\endmultline \tag 5.8$$
The $q$--analogue of (4.1) is MacMahon's well--known result \cite{1,
Theorem~{3.7}, p.~42}, which in our notation is 
$$G(\pmb \mu\to\pmb\lambda;q)=\bmatrix \vert\pmb\lambda
-\pmb\mu\vert\\\pmb\lambda-\pmb\mu\endbmatrix \ .\tag 5.9$$
Successive use of (5.8), (4.9), and (5.9) gives 
$$\aligned
G(&\pmb\mu\to\pmb\lambda;q)\sp
+=G(\pmb\mu\to\pmb\lambda;q)-
G(\pmb\mu\to\pmb\lambda;q)\sp
 -\\
 &=G(\pmb\mu\to\pmb\lambda;q)-G(\pmb\mu\to\pmb\lambda;q)\sp
-\\
 &\quad \quad +\underset \pmb u\in U\sb
n\to{\sum \sb
{\sigma\in S\sb
n}}\sgn\sigma\, q\sp
{\sum
\sb
{s=1} \sp
{n}T(s,\sigma(s),\pmb u,\pmb\mu)}G(\pmb\mu\sb
\sigma +\pmb e\sb
\sigma
+(K+n)\pmb u\to\pmb\lambda;q)\sp
-\\
 &=\underset \pmb u\in U\sb
n\to{\sum \sb
{\sigma\in S\sb
n}}\sgn\sigma\, q\sp
{\sum \sb
{s=1}
\sp
{n}T(s,\sigma(s),\pmb u,\pmb\mu)}G(\pmb\mu\sb
\sigma +\pmb e\sb
\sigma +(K+n)\pmb
u\to\pmb\lambda;q)\\
 &=\underset \pmb u\in U\sb
n\to{\sum \sb
{\sigma\in S\sb
n}}\sgn\sigma\, q\sp
{\sum \sb
{s=1}
\sp
{n}T(s,\sigma(s),\pmb u,\pmb\mu)}
\bmatrix \vert \pmb\lambda-\pmb\mu\vert\\ \pmb\lambda -\pmb\mu\sb
\sigma -\pmb e\sb
\sigma
-(K+n)\pmb u\endbmatrix \\
 &=\sum \sb
{\pmb u\in U\sb
n}[\vert\pmb\lambda -\pmb\mu\vert ]!\det (q\sp
{T(s,t,\pmb
 u,\pmb\mu)}/ [\lambda\sb
s-\mu\sb
t-s+t-(K+n)u\sb
s]!)\ ,
\endaligned \tag 5.10$$
which exactly is the expression in Theorem~{1}.


\subheading{6. An extension of Theorem 1}
In this section we extend Theorem~1, which is a theorem about major
counting, to other, major-like statistics. To motivate the following
considerations, recall that MacMahon not only dealt with the major
(i.e\. greater)
index but also with what he called the ``lesser index" \cite{5, p.~136}. 
This lesser
index, which we denote by $\pmaj$, of a multiset permutation
$\pi=\pi\sb
1\pi\sb
2\dots\pi\sb
L$ is defined by
$$\pmaj \pi = \sum \sb
{i = 1} \sp
{L - 1} i \cdot\chi
 (\pi \sb
i < \pi\sb
 {i + 1})\ .$$
While for the major index each $j$ with $\pi\sb
j>\pi\sb
{j+1}$ makes a
contribution, for the lesser index it is each $j$ with
$\pi\sb
j<\pi\sb
{j+1}$ which makes a contribution. One also could roughly
say that taking the lesser index is nothing but taking the major
index where the order $1<2<\dots<n$ of the numbers $\{1,2,\dots,n\}$ 
has been changed into
$1>2>\dots>n$. Having this idea in mind, it is also reasonable to 
consider other total orders of $\{1,2,\dots,n\}$ and to take major
index with
respect to these orders. Thus, for each $n$ one obtains a set of $n!$
different major variants, the original major index and the lesser
index being only two of them.

To be more precise, we proceed as follows. Given a
specific total order $i\sb
1<i\sb
2<\dots<i\sb
n$ of the set $\{1,2,\dots,n\}$,
let the permutation $\tau
$ be defined by $\tau
(i\sb
j):=j$,\break
$j=1,2,\dots,n$. Then taking the major index of a multiset
permutation $\pi=\mathbreak\pi\sb
1\pi\sb
2\dots\pi\sb
L$ with respect to the order
$i\sb
1<i\sb
2<\dots<i\sb
n$ is just the same as\break
$\maj(\tau
(\pi\sb
1)\tau
(\pi\sb
2)\dots\tau
(\pi\sb
L))$. This leads to the
following definition.

Let
$\tau
$ be a fixed permutation, $\tau
 \in S\sb
n$. We extend $\tau
$ to
multiset permutations $\pi = \pi \sb
1\pi\sb
2\dots \pi\sb
L$ which satisfy
$\pi\sb
i \in\{1, 2, \dots , n\}$ by 
$$\tau
 (\pi ) = \tau
 (\pi \sb
1) \tau
 (\pi\sb
2 ) \dots \tau
 (\pi\sb
L )\ .$$
The action of $\tau
$ on a path $p = (\pmb\mu , \pi )$ is defined by
$\tau
 (p ) = (\pmb\mu, \tau
 (\pi ) )$. Now we introduce the following
permutation-indexed statistics:
$$\maj \sb
\tau
 p: = \maj \tau
 (p )         \ .\tag 6.1$$

Obviously, $\maj\sb
{ {id}}$ is identical with the major index, while for $\tau
\sb
0$ given by $\tau
 \sb
0 (i ) = n + 1 - i$
the statistics $\maj\sb
{\tau
\sb
0}$ coincides with MacMahon's lesser index.

To give another example, take $n=3$, $\tau
\sb
1=\binom{1\ 2\ 3}{2\ 3\ 1}$,
$\pi\sb
1=1223213$. This choice of $\tau
\sb
1$ corresponds to the total order
$3<1<2$. We have $\maj\sb
{\tau
\sb
1}\pi\sb
1=3+5+6=14$.

The same idea as that
 which was used in the proof of Theorem~1 also serves to
establish an analogous result for counting $N (\pmb \mu \to \pmb\lambda
 )
\sp
+$ by $ \maj\sb
\tau
$. In fact, the result for the generating function $\sum \sb
{}
\sp
{}q \sp
{\maj\sb
\tau
 p}$ almost looks to be identical, except
that the powers of $q$ are
changed according to the choice of $\tau
$.

\proclaim{Theorem 2} Let $\pmb\lambda
 , \pmb \mu \in K\sb
n$ and $\pmb\lambda
 \ge
\pmb\mu$. The generating function $\sum \sb
{} \sp
{}q\sp
{\maj\sb
\tau
 p}$, where
the sum is over all lattice paths from $\pmb\mu$ to $\pmb\lambda
$ which
do not touch any one of the hyperplanes in $(2.2)$ and $(2.3)$, is
given by
$$\sum \sb
{\pmb u \in U\sb
n} \sp
{}[\vert \pmb\lambda
 - \pmb\mu\vert]!
\det\sb
{1 \le s , t \le n}\left(q\sp
{T\sb
\tau
(s, t, \pmb u, \pmb\mu) }/[\lambda
\sb
s - s
- \mu \sb
t + t - (K + n)u\sb
 s]!\right)\ .$$
The exponents $T\sb
\tau
(s,t,\pmb u,\pmb\mu)$ are given by
$$\multline T\sb
\tau
 (s,t,\pmb u,\pmb\mu)=(\mu\sb
t-t)\sum \sb
{j=t}
\sp
{s-1}c(j)+u\sb
s(\mu\sb
t-t)\sum \sb
{j=1} \sp
{n}c(j)\\
+(K+n)\left(\frac {u\sb
s\sp
2} {2}\sum \sb
{j=1} \sp
{n}c(j)+u\sb
s\sum \sb
{j=1}
\sp
{s-1}c(j)\right)\ ,
\endmultline$$
where $c(j)=\chi
(\tau
(j)<\tau
(j+1))$, and where we adopt the convention that $\sum
\sb
{j=l} \sp
{l-1}a\sb
j=0$, and $\sum \sb
{j=l} \sp
{k-1}a\sb
j=-\sum \sb
{j=k} \sp
{l-1}a\sb
j$
whenever $k<l$. By $\tau
(n+1)$ here and in the sequel we mean
 $\tau
(1)$. Analogous conventions will be assumed for $n+1$ appearing
as a subscript: $\mu\sb
{n+1}:=\mu\sb
1$, etc.
\endproclaim
\demo{Sketch of proof} In analogy with (5.1) let the weight $w\sb
\tau
(p)$
of a path $p\in N(\pmb\mu\sb
\sigma
+\pmb e\sb
\sigma
 +(K+n)\pmb u\to \pmb \lambda
)$
be defined by 
$$w\sb
\tau
(p)=q\sp
{\sum \sb
{s=1} \sp
{n}T\sb
\tau
(s,\sigma
(s),\pmb
u,\pmb\mu)}q\sp
{\maj\sb
\tau
 p}\ .\tag 6.2$$
Let $p\in N(\pmb\mu\sb
\sigma
 +\pmb e\sb
\sigma
+(K+n)\pmb u\to \pmb\lambda
)\sp
-$ be a path
which meets $H\sb
j$ as last hyperplane of those in (2.2) and (2.3).
Suppose that there are mappings $\psi
\sb
j$ which satisfy the following
properties:
\roster
\item "(1)" $\psi
\sb
j$ acts on paths which meet $H\sb
j$ as last
hyperplane.
\item "(2)" If $\overline p\in N(\overline{\pmb\mu}
\to\overline{\pmb\lambda
})\sp
-$ meets $H\sb
j$ as last hyperplane, then
$\psi
\sb
j(\overline p)\in N(R\sb
j(\overline {\pmb \mu})\to
\overline{\pmb\lambda
})\sp
-$ and $\psi
\sb
j(\overline p)$ also meets $H\sb
j$ as
last hyperplane.
\item "(3)" The action of $\psi
\sb
j$ changes $\maj\sb
\tau
$ according to 
$$\maj\sb
\tau
\psi
\sb
j(\overline p)=\cases \maj\sb
\tau
\overline
p-c(j)(\overline \mu\sb
j-\overline\mu\sb
{j+1}+1) &\quad 1\leq j\leq n-1\\
\maj\sb
\tau
\overline p-c(n)(\overline\mu\sb
n-\overline\mu\sb
{1}+1+K)&\quad
j=n\endcases\ ,\tag 6.3$$
with $c(j)=\chi
(\tau
(j)<\tau
(j+1))$.
\item "(4)" $\psi
\sb
j$ is an involution.
\endroster
Then simple calculations show that $\psi
\sb
j(p)\in
N(\pmb\mu\sb
{\sigma
(j,j+1)}+\pmb e\sb
{\sigma
(j,j+1)}+(K+n)\pmb u\sp
{(j)}\to
\pmb\lambda
)\sp
-$ with $\pmb u\sp
{(j)}$ being defined in section 4. Moreover,
$w\sb
\tau
(\psi
\sb
j(p))=w\sb
\tau
(p)$. Let the mapping $\varphi
\sb
\tau
$, which acts on
elements of the union of the sets in (4.2) and (4.3), be defined as
follows: If an element of the union of the sets in (4.2) and (4.3)
meets $H\sb
j$ as last hyperplane of those in (2.2) and (2.3), then the
image of this path under application of $\varphi
\sb
\tau
$ is given by
applying $\psi
\sb
j$ to this path. $\varphi
\sb
\tau
$ is seen to be an involution,
and hence a bijection between the sets in (4.2) and (4.3). Besides,
it is weight-preserving with respect to $w\sb
\tau
$. Computations which
proceed analogously to those in (5.8)--(5.10) would complete the
proof of Theorem 2.

It remains to construct those mappings $\psi
\sb
j$. The idea is as follows:

If $\tau
(j)<\tau
(j+1)$ modify Definitions 1,2 of \cite{4} such that
$\bold L\sb
j$ changes a single $\tau
(j+1)$ into $\tau
(j)$, $\bold R\sb
j$
changes a single $\tau
(j)$ into a $\tau
(j+1)$, and 
$$\align \bold R\sb
j\circ \bold L\sb
j&=\bold L\sb
j\circ\bold R\sb
j=id\ ,\\
\maj\bold L\sb
j(\pi)&=\maj\pi-1\ ,\\
\maj\bold R\sb
j(\pi)&=\maj\pi +1\ .
\endalign$$
Then for a path $p=(\pmb\mu,\pi)$ which meets $H\sb
j$ as last
hyperplane, $\psi
\sb
j$
is given by 
$$\psi
\sb
j(p)=(R\sb
j(\pmb\mu),\ \bold
L\sb
j\sp
{\mu\sb
j-\mu\sb
{j+1}+1+K\cdot\chi
(j=n)}(\tau
(\pi)))\ .$$ 
If $N$ is negative, by $\bold L\sb
j\sp
N$ we mean $\bold R\sb
j\sp
{-N}$.
Similarly, if $\tau
(j)>\tau
(j+1)$, modify Definitions 3,4 of \cite{4}
such that $\overline{\bold L}\sb
j$ changes a $\tau
(j+1)$ into a $\tau
(j)$,
$\overline{\bold R}\sb
j$ changes a $\tau
(j)$ into a $\tau
(j+1)$, and
$$\align \overline{\bold R}\sb
j\circ\overline{\bold L}\sb
j&=\overline{\bold
L}\sb
j\circ\overline{\bold R}\sb
j=id\ ,\\
\maj\overline{\bold L}\sb
j(\pi)&=\maj\overline{\bold R}\sb
j(\pi)=\maj\pi\ .
\endalign$$
In this case, $\psi
\sb
j$ is given by 
$$\psi
\sb
j(p)=(R\sb
j(\pmb\mu),\ \overline {\bold
L}\sb
j\sp
{\mu\sb
j-\mu\sb
{j+1}+1+K\cdot\chi
(j=n)}(\tau
(\pi)))\ , $$ with the
analogous convention concerning negative exponents of $\overline
{\bold L}\sb
j$.\quad \qed

Setting $\tau
=\tau
\sb
0$ in Theorem 2 yields the corresponding result for
counting $N(\pmb \mu\to\pmb\lambda
)\sp
+$ by the lesser index.
\enddemo
\proclaim{Corollary 1} Let $\pmb\lambda
,\pmb\mu\in K\sb
n$ and
$\pmb\lambda
\geq\pmb\mu$. The generating function $\sum q\sp
{\pmaj p}$,
where the sum is over all lattice paths from $\pmb\mu$ to $\pmb\lambda
$
which do not touch any of the hyperplanes in (2.2) and (2.3), is
given by 
$$\sum \sb
{\pmb u\in U\sb
n} [\vert \pmb\lambda
 -\pmb\mu\vert]! \underset
1\leq s,t\leq n\to{\det}(q\sp
{T'(s,t,\pmb
u,\pmb\mu)}/[\lambda
\sb
s-s-\mu\sb
t+t-(K+n)u\sb
s]!)\ ,$$ where 
$$T'(s,t,\pmb u,\pmb\mu,)=u\sb
s(\mu\sb
t-t)+(K+n)\frac {u\sb
s\sp
2} {2}\ . \qed$$
\endproclaim
The special case $K>\vert\pmb\lambda
-\pmb\mu\vert$ has been proved
previously in \cite{4, Theorem 4}.


\Refs

\ref\no 1\by G.~E.~Andrews\book The theory of partitions
\bookinfo Encyclopedia of Mathematics and its Applications,
Vol.~2\publ (Addison--Wesley\publaddr
Reading\yr 1976)\endref
\ref\no 2\by M.~Filaseta\paper A new method for solving a class of
ballot problems\jour J.~Combin\. Theory \vol A~39\yr 1985\pages
102--111\endref
\ref\no 3\by I.~M.~Gessel, D.~Zeilberger\paper Random walk in a Weyl
chamber\jour 
preprint, 1990 \endref
\ref\no 4\by C.~Krattenthaler\paper Enumeration of lattice paths and
generating functions for skew plane partitions\jour 
Manuscripta Math\.\vol 63\yr 1989\pages 129--155\endref
\ref\no 5\by P.~A.~MacMahon\book Combinatory Analysis\bookinfo Vol.~2\publ
(Cambridge University Press, Cambridge, 1916; reprinted by Chelsea\publaddr New
York\yr 1960)\endref
\ref\no 6\by D.~Zeilberger\paper Andr\'e's reflection proof
generalized to the many candidate ballot problem\jour 
Discrete Math.\vol 44\yr 1983\pages 325--326\endref
\endRefs
\enddocument
