\input amstex
\input amsppt.sty

\def\des{\operatorname{des}}
\def\maj{\operatorname{maj}}
\magnification1200
\hsize13cm
\vsize19cm
\topmatter 
\title ON LATTICE PATH COUNTING BY MAJOR AND DESCENTS
\endtitle 
\author C.~Krattenthaler\\S.~G.~Mohanty
\endauthor 
\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, 05A30}
\endsubjclass
\keywords{Lattice paths, major index, descents}
\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 McMahon's major index and variations of the major
index. A formula involving determinants is obtained. For $n=2$ we
also present a formula for counting these lattice paths
simultaneously by major and descents.}
\endabstract
\endtopmatter
\document
Consider $n$-dimensional  lattice paths 
consisting of positive unit
steps. In the sequel they are called simply paths for short. 
Any path $p$ from $\pmb\mu$ to $\pmb\lambda
$ may be represented by
the pair $(\pmb\mu,\pi)$, where $\pmb\mu$ is the initial point of $p$
and $\pi $ is the multiset permutation of
$\{1\sp
{\lambda
\sb
1-\mu\sb
1},2\sp
{\lambda
\sb
2-\mu\sb
2},\dots, n\sp
{\lambda
\sb
n-\mu\sb
n}\}$ which
comes out of $p$ by successively writing $i$ for a step in
$x\sb
i$-direction. For example, the path $p\sb
0$: $(2,1,0)\to (3,1,0)\to
(3,1,1)\to(3,2,1)\to(3,3,1)\to(4,3,1)\to(4,4,1)\to(5,4,1)\to(5,4,2)$
in this representation reads $\big((2,1,0),13221213\big)$.

The number of {\it descents} of a multiset permutation
$\pi=\pi\sb
1\pi\sb
2\dots\pi\sb
L$, $\des\pi$, is
$$\des\pi=\vert\{i:\pi\sb
i>\pi\sb
{i+1},1\le i\le L-1\}\vert\ .$$
The {\it major} of a multiset permutation $\pi$, $\maj\pi$, is the
sum of the positions where a descent occurs,
$$\maj\pi=\sum \sb
{i=1} \sp
{L-1}i\chi(\pi\sb
i>\pi\sb
{i+1})\ .$$
($\chi
$ is the usual truth function.)
For example, for $\pi\sb
0=13221213$ we have $\des\pi\sb
0=3$ and
$\maj\pi\sb
0=2+4+6=12$. 
These definitions are extended to paths $p=(\pmb\mu,\pi)$ by
$\maj p=\maj\pi$ and $\des p=\des\pi$.

It was McMahon who introduced these two notions in his treatise on
generating functions for plane partitions \cite{7}. His idea of
computing plane partition generating functions with the help of
counting ``lattice permutations" by major and descents, was
formalized and generalized by Stanley in his thesis (cf\. \cite{9}).
In particular, Stanley's theorem \cite{9, Corollaries~5.3 and 5.7}
implies that the generating function for plane partitions of the skew
shape $\pmb\lambda
/\pmb\mu$, $\lambda
\sb
1\ge\lambda
\sb
2\ge\dotsb\ge\lambda
\sb
n$ 
and $\mu\sb
1\ge\mu\sb
2\ge\dotsb\ge\mu\sb
n$, can be computed by solving the
problem of counting $n$-dimensional lattice paths from $\pmb\mu$ to
$\pmb\lambda
$ which do not touch any of the hyperplanes
$$x\sb
i-x\sb
{i+1}=-1,\quad \quad i=1,2,\dots,n-1\ .\tag1$$
Besides, another theorem of Stanley \cite{9, Proposition~8.2} implies that the
generating function for plane partitions of shape $\pmb\lambda
/\pmb\mu$
{\it with parts bounded by $m$} can be computed by counting the same
family of paths with respect to $\maj$ {\it and} $\des$. While the
case of major counting has been solved completely \cite{4}, for the case
of counting simultaneously by major and descents we have only a
solution for $n=2$. In fact, a more general theorem is given below
(Theorem C). Yet, the existence of a simple formula for the
generating function for plane partitions with bounded parts (see
e.g\. \cite{2, Theorem~16}) strongly suggests that there should be
also a simple formula for counting $n$-dimensional paths which do not
touch any of the hyperplanes in (1) by major and descents.

In this paper we encounter the more general problem of counting
paths from $\pmb\mu$ to $\pmb\lambda
$ which do not touch any of the
hyperplanes in (1) and do not touch the additional hyperplane
$$x\sb
n-x\sb
1=-1-K\ ,\tag2$$
where $K$ is some positive integer, by major and descents. 
While the case of counting by only major is solved completely
(Theorem A), and this result is even generalized to statistics which
are variations of the major statistics (Theorem~B), 
for counting by both major
and descents we are only able to give a formula for $n=2$ (Theorem~C), 
as mentioned
above.  

The cardinality
of the family of
 paths under consideration has been previously computed  by
Filaseta \cite{1}. His theorem comes out of Theorem~A by setting
$q=1$.


For sake of brevity we do not give proofs of our results. Detailed
proofs of Theorems~A and B can be found in \cite{5}, the proof of
Theorem~C is given in \cite{6}.

\medpagebreak
We use the usual multidimensional notation. If 
$\pmb \lambda
=(\lambda
\sb
1,\lambda
\sb
2,\dots,\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$, and $\pmb\lambda
 -\pmb\mu
=(\lambda
\sb
1-\mu\sb
1,\lambda
\sb
2-\mu\sb
2,\dots,\lambda
\sb
n-\mu\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 use 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]!$.

\medpagebreak
Let $K$ be an arbitrary fixed positive integer and let $K\sb
n$ denote
the set of all $n$-tuples $\pmb\lambda
$ of integers with 
$$\lambda
\sb
1\ge \lambda
\sb
2\ge\dotsb\ge\lambda
\sb
n\ge\lambda
\sb
1-K\ .$$
\proclaim{Theorem~{A}} 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 $(1)$ and $(2)$, is
given by
$$\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)\ ,$$
 where $U\sb
n$ is the set
of all $n$--tuples $\pmb u$ 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
This result generalizes Theorem~1 of \cite{4}.

Let 
$\tau
$ be a fixed permutation of $[1,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 )$ then is defined by
$\tau
 (p ) = (\pmb\mu, \tau
 (\pi ) )$. Now we introduce the following
permutation-indexed statistics:
$$\maj \sb
\tau
 p: = \maj \tau
 (p )         \ .$$
Obviously, $\maj\sb
{\text {id}}$ is identically with the major (=
greater) index, while for $\tau
\sb
0$ given by $\tau
 \sb
0 (i ) = n + 1 - i$
the statistics $\maj\sb
{\tau
\sb
0}$ coincides with McMahon's lesser index
\cite{7, p.~136}. 
The next theorem is the $\maj\sb
\tau
$-analogue of Theorem~A.
\proclaim{Theorem B} 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 $(1)$ and $(2)$, 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)\frac {u\sb
s\sp
2} {2}\sum \sb
{j=1} \sp
{n}c(j)+(K+n)u\sb
s\sum \sb
{j=1}
\sp
{s-1}c(j)\ ,
\endmultline$$
where $c(j)=\chi
(\tau
(j)<\tau
(j+1))$, $c(n)=\chi
(\tau
(n)<\tau
(1))$ and 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$.
\endproclaim
Our last theorem gives the promised result for counting 2-dimensional
paths not touching the lines $x\sb
1-x\sb
2=-1$ and $x\sb
2-x\sb
1=-1-K$ by major and
descents. The formulation of the theorem even is slightly more general.
\proclaim{Theorem~{C}} Given $c,d \in {\Bbb
Z},\, d>c$, let
 $\lambda
\sb 1+c\leq \lambda
\sb 2\leq \lambda
\sb 1+d$ and
$\mu\sb 1+c\leq \mu\sb 2\leq \mu\sb 1+d$. The generating function
$\sum x\sp
{\des p}q\sp
{\maj p}$, where the sum is over all lattice paths
from $\pmb\mu=(\mu\sb
1,\mu\sb
2)$ to $\pmb\lambda
=(\lambda
\sb
1,\lambda
\sb
2)$ which do not
cross the lines $x\sb
2=x\sb
1+d$ and $x\sb
2=x\sb
1+c$, is given by
$$\multline \sum\sb {n\geq 0}x\sp n\sum\sb {k\in
{\Bbb
Z}}q\sp {n\sp 2+k\sp 2(d-c+1)-k(1-c+\mu\sb 2-\mu\sb 1)} \\
\times \left(\left[\matrix \lambda
\sb 1-\mu\sb 1-k(d-c)\\n+k\endmatrix\right ]\left
[\matrix \lambda
\sb 2-\mu\sb 2+k(d-c)\\n-k\endmatrix\right ]\right.\\
\left.-\left [\matrix
\lambda
\sb 2-\mu\sb 1-k(d-c)-c+1\\n+k\endmatrix\right ]\left[\matrix
\lambda
\sb 1-\mu\sb 2+k(d-c)+c-1\\n-k\endmatrix\right ]\right) ,
\endmultline $$
where $\left [\smallmatrix a\\b\endsmallmatrix\right ]$ is the Gaussian
binomial coefficient, $\left[\smallmatrix
a\\b\endsmallmatrix\right]=\frac{[a]!}{[b]!\,[a-b]!}$.
\endproclaim
Previous results of McMahon \cite{8, p.1429} and of one of the authors
\cite{3, Theorems 5-7} are special cases of this theorem.

\Refs
\ref\no 1\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 \no2\by I. Gessel and G. Viennot\paper Determinants, paths, and 
plane partitions\paperinfo preprint \endref
\ref\no 3\by C.    Krattenthaler \yr 1989 \paper Counting lattice paths 
with a linear boundary, Part 2: $q$-ballot and $q$-Catalan numbers\jour 
Sitz\.ber\. d\. \"OAW, Math-na\-tur\-wiss\. Klasse\vol 
198\pages 171--199\endref

\ref\no 4\bysame\paper Enumeration of lattice paths and
generating functions for skew plane partitions\jour 
Ma\-nu\-scrip\-ta Math\.\vol 63\yr 1989\pages 129--155\endref

\ref\no 5\by C.    Krattenthaler and S. G. Mohanty \yr 1994 \paper 
$q$-Generalization of a ballot problem\jour 
Discrete Math\.\vol 126\pages 195--208\endref
\ref\no 6\by C.    Krattenthaler and S. G. Mohanty \yr 1993 \paper 
On lattice path counting by major and descents\jour 
Europ\. J. Combin\.\vol 14\pages 43--51\endref
\ref\no 7\by P.~A.~McMahon\book Combinatory Analysis\bookinfo Vol.~2,
Cambridge University Press, 1916\publ reprinted by Chelsea\publaddr
New York\yr 1960\endref
\ref\no 8\bysame \book Collected Papers: Combinatorics \bookinfo
Vol.~I\publ MIT Press\publaddr Cambridge, Massachusetts\yr 1978\endref

\ref\no 9\by R.~P.~Stanley\book Ordered structures and
partitions\bookinfo Mem\. Amer\. Math\. Soc\. No.~119\publ American
Mathematical Society\publaddr Providence, R.I.\yr 1972\endref

\endRefs

\enddocument


