manuscripta
math.
63,
129 -
155
manuscripta mathematica
(1989)
9 Springer-Verlag1989
ENUMERATION
O F LATTICE P A T H S A N D G E N E R A T I N G F U N C T I O N S F O R S K E W P L A N E PARTITIONS
Christian Krattenthaler
n-dimensional lattice paths not touching the hyperplanes x t - x t + , f f i - 1 , /=1,2,...,n, a r e c o u n t e d b y f o u r d i f f e r e n t s t a t i s t i c s , o n e o f w h i c h i s MacMahon's m a j o r i n d e x . By a r e f l e c t i o n - l i k e p r o o f , h e a v i l y r e l y i n g o n Z e i l b e r g e r ' s {Discrete Math. 44(1983), 325-326) solution of the n-candidate ballot problem, determinantal e x p r e s s i o n s a r e o b t a i n e d . As c o r o l l a r i e s t h e generating functions for skew plane partitions, column-strict skew plane partitions, reverse skew plane plane partitions and column-strict reverse skew plane partitions, respectively, are e v a l u a t e d , t h u s e s t a b l i s h i n g p a r t l y n e w r e s u l t s , p a r t l y new p r o o f s f o r k n o w n t h e o r e m s in t h e t h e o r y of p l a n e p a r t i t i o n s .
1. INTRODUCTION. C o n s i d e r n - d i m e n s i o n a l l a t t i c e p a t h s , c o n s / s t i n g o f positive unit
(xl,x2,...,x,) counting
of
the
n-candidate for
problem
those
of
In
this
counting
that
x , ~ x a ~ " .~,x,.
satisfy
lattice paths
all t h e p o i n t s
The
is
problem
equivalent
of
to t h e
paper,
all lattice
of
which
more
generally,
paths
from
satisfying
we
encounter
Pf(Px,~2,...,~n)
x~a..-axn,
by
the
to A, e a c h
four
different
m a j , m a j ' , ~-'~, &-fi~', d e f i n e d in s e c t i o n 2. What i s o b t a i n e d
determinantal
method
paths
of all t h o s e
such
b a l l o t p r o b l e m a n d h a s a t t a i n e d s e v e r a l s o l u t i o n s ( s e e [12]
(x,,x2,...,xn)
statistics,
from 0 to A=(~l,~2,..,~,)
number
references).
point are
steps,
of
proof
Zeilberger's
[ 13]
pseudo-reflection
expressions we
give
reflection
(Theorems is
1 to
combinatorial
proof
for
4 in
section
and
is
the
case
6).
The
inspired
by
q=1
and
a
p r o o f f o r t h e c a s e nffi2 b y F i i r l i n g e r a n d H o f b a u e r [3,
Lemma o n p . 2 5 5 ] . There
is
permutations
a
bijection
between
of the multiset
lattice
paths
from
0
to
A and
~1X~,2 ~2 .... ,n ~'"] ( t h i s s y m b o l d e n o t e s
129
the
ERATTENTHALER m u l t i s e t with o b j e c t s each
k
in
a
m u l t i p l i c i t i e s (,~,,k2,...,X.)).
[1,2,...,nJ a n d
multiset
permutation
x k - d i r e c t i o n . MacMahon calls t h e
is
consider
function
lattice
for
plane
sec.X]. What h a s
permutations partitions
as
step
in
permutations corresponding
p a t h s , whose p o i n t s s a t i s f y x ~ ' - ' ~ x , , to
interpreted
Namely, the
to t h o s e
" l a t t i c e p e r m u t a t i o n s " . He is lead when
of a
evaluating
given
shape
the
A [8,
generating
sec.IX, c h . I I I ;
to b e d o n e is to c o u n t l a t t i c e p e r m u t a t i o n s b y t h e
m a j o r - s t a t i s t i c s ; i.e., to e v a l u a t e t h e w e i g h t e d s u m ~qmaj I , w h e r e t h e sum is o v e r all l a t t i c e p e r m u t a t i o n s t of t h e m u l t i s e t [ l ~ l , 2 x 2 , . . . , r ~ " 3 . Later,
MacMahon's
method
was
Stanley [10, Corollaries 5.3 and
formalized
7.2]. Thus,
and
generalized
wanting
by
to find a certain
partition generating function, one has to count a specific collection of permutations by the major index. In
section
generating partitions,
3 we
shall see
functions
for
reverse
partitions
of
a
plane
given
that in this
plane
partitions,
partitions
shape
sense
and
x is
evaluation
of the
column-strict
plane
column-strict
done
by
solving
reverse the
plane
problem
of
c o u n t i n g l a t t i c e p e r m u t a t i o n s b y maj, m a j ' , ~'Ej' a n d maj, i n t h a t o r d e r , respectively.
Thus,
as
corollaries
of
our
lattice
r e s u l t s , we o b t a i n d e t e r m i n a n t a l e x p r e s s i o n s e v e n functions for expressions
path
enumeration
for the
generating
skew p l a n e p a r t i t i o n s , e t c . , of a g i v e n s h a p e for
column-strict and
column-strict
reverse
~]F. T h e
skew
plane
p a r t i t i o n s ( C o r o l l a r y 9) a r e w e l l - k n o w n a n d may he f o u n d i n [10, p.82 for
ur-~].
The
expressions
for
ordinary
and
reverse
skew
plane
p a r t i t i o n s (Corollaries 7 a n d 8) seem to be new. T h e s p e c i a l c a s e ~ ordinary
plane
partitions
was
solved
by
MacMahon [8]
by
of
inductive
a r g u m e n t s which are not v e r y rigorous. In the r e m a i n i n g t h r e e cases for p=0 t h e d e t a r m i n a n t a l e x p r e s s i o n s c a n be s i m p l i f i e d , w h i c h l e a d s to the
well-known
hook-formulae
for
the
generating
column-strict, reverse and column-strict reverse g i v e n s h a p e ~ [11, T h e o r e m 15.3 for m ~ , For
these
results
combinatorial proof
there
are
proofs
explaining the
by
functions
of
p l a n e p a r t i t i o n s of a
P r o p o s i t i o n s 18.3 a n d Schur
functions
determinantal expressions
v a r i o u s b i j e c t i v e p r o o f s e x p l a i n i n g t h e o c c u r e n c e of t h e
18.4].
[11], [5]
a
and
hook-lengths
[2,4,6,9]. Our method of p r o o f o f f e r s a new c o m b i n a t o r i a l e x p l a n a t i o n for t h e determinantal expressions
for
all of t h e
above
g e n e r a t i n g f u n c t i o n s , e v e n in t h e case of t h e
130
stated
four
k i n d s of
v a r i o u s k i n d s of s k e w
KRATTENTHALER
plane
partitions.
MacMahon's d e t e r m i n a n t
is g e n e r a l i z e d
and
given
a
c o m b i n a t o r i a l view. I n s e c t i o n 2 we g i v e all r e l e v a n t d e f i n i t i o n s . The c o n n e c t i o n b e t w e e n lattice
path
enumeration
and
generating
functions
for
skew
plane
p a r t i t i o n s is e x p l a i n e d i n s e c t i o n 3. S e c t i o n 4 c o n t a i n s a r e c a p i t u l a t i o n of Z e i l b e r g e r ' s [13] r e f l e c t i o n proof. I n s e c t i o n 5 we g i v e t h e b i j e c t i o n s which r e p l a c e t h e r e f l e c t i o n i n Z e i l b e r g e r ' s p r o o f . T h e s e b i j e c t i o n s , i n s e c t i o n 6, a r e Finally,
in
used
to o b t a i n t h e
section
corresponding
7,
these
generating
promised d e t e r m i n a n t a l expressions.
results
functions
are
transferred
for
the
various
to
obtain
kinds
of
the skew
plane partitions.
2.
DEFINITIONS. We u s e
Jkf(hzw~2P.',Kn),
usual
P=(Pz,P2,..~
. . . . . Xn+pn )
iffil,2,...,n
the
and
multidimensional notation.
then
I~effi~l+~2+--.+k.
{'~'}=,X,!/,,!,,.~.--~.!.
If
If
,
~+~ =
X,',,
for
we w r i t e X~'p,
Let q b e a n i n d e t e r m i n a t e . The q - n o t a t i o n s we n e e d a r e
[ml!=[m]-[~-l]---[l],
[01:=1 and
[a]=(l-qa),
=[Ixll:/[~l.)[~z).~...[~.],
Let S, d e n o t e t h e s y m m e t r i c g r o u p of o r d e r n. G i v e n os n we w r i t e for
{ ~ ( z ) , ~ ( = ) , .... ~ ( , ) ) .
Dn s t a n d s
integers A with ~ . ~ 2 ~ . . . ; X , .
For
for
the
the
s e t o f all n - t u p e l a of
s e t of all p e r m u t a t i o n s of t h e
m u l t i s e t w i t h o b j e c t s [1,2,...,n~ a n d m u l t i p l i c i t i e s ~=(P~,P2,..-,Pn) we w r i t e S(~).
Given
a
multiset
permutation
~ffi~112...~p,
It~[1,2,...,n~,
we
i n t r o d u c e d i f f e r e n c e f u n c t i o n s dj(~,/) f o r j = l , 2 , . . . , n - l :
dj{~,i)
is t h e d i f f e r e n c e b e t w e e n t h e n u m b e r of j~s a n d t h e n u m b e r of
( j + l ) ' s i n ~1--.~t. O b v i o u s l y dj(~20)=O. In
this
paper,
a
latt/ce
path
~=(p(O),p(q),...,p(p))
will
be
s
finite
~ e q u e n e e of p o i n t s i n t h e i n t e g e r l a t t i c e Zn with p o s i t i v e u n i t steps~ i.e. for ~%0, p(i+l)-p(~)=Ej, f o r some j, l ~ j ~ n . Ej s t a n d s f o r t h e v e c t o r with t h e j - t h [P(0]k
A lattice path
p=p(O)
c o o r d i n a t e b e i n g e q u a l to ~, all o t h e r b e i n g e q u a l to 0.
will d e n o t e t h e k - t h c o o r d i n a t e of t h e / - t h p o i n t o n t h e p a t h ~.
and
p from p to X c a n be s y m b o l i z e d b y a p a i r (p,~), w h e r e
~S(X-p).
~ is
obtained
by
proceeding
along
the
path,
~ t a r t i n g at i t s f i r s t p o i n t p, a n d s u c c e s s i v e l y w r i t i n g a k for each s t e p
131
gRATTENTHALER in t h e X k - d i r e c t i o n . To be precise~ ll-'~i~a...~p, w h e r e p=I~.-FI if a n d
only
p(i)-p(i-1)=g k. G i v e n a
if
path
p in
the
form
and ~t=k (~,I),
the
p o i n t s of p a r e d e t e r m i n e d b y
k=| TO
give
8.n
examp}e9
(2,3,3),(3,3,3)).
take
n==3 and
po=(('l,2) 1),(1,2,2))(1,2,3),(2,2,3) )
T h e n Po is s y m b o l i z e d b y t h e p a i r ((1,2,1), 33121).
Th e s e t o f all l a t t i c e p a t h s
b y M(p---~X.). We
f r o m p to X is d e n o t e d
w r i t e M(p--~) § f o r t h e s e t of all l a t t i c e p a t h s f r o m 9 to ~ w h o s e p o i n t s all lie in
D,.
For
p,~D n the
set
M(F-~X) + is e q u a l
to t h e
set
of all
l a t t i c e p a t h s f r o m p t o ~ n o t t o u c h i n g a n y o n e of t h e h y p e r p l a n e s xl - xl+l
(2.2)
= -I
L e t Hi d e n o t e t h e h y p e r p l a n e
,
.9221,2,...,n--1.
xl-xi+z~-I
a n d R i t h e r e f l e c t i o n a t H s.
M(p-~X)- s t a n d s f o r t h e s e t o f all l a t t i c e p a t h s f r o m p t o X w h i c h t o u c h at least one of the h y p e r p l a n e s
in (2.2). O b v i o u s l y M ( 0 - ~ ) +, o r b e t t e r
[~:p=(O,t)EM(O--)~,)+~, is t h e s e t of all l a t t i c e p e r m u t a t i o n s . Next~ f o r
a
given
multiset
permutation
~=~=~=...~,
we
define
the
" d o w n - s e t " D(~) b y =
,
a n d t h e f o u r s t a t i s t i c s maj, m a j' , maj, ~ - ~ , I = P~'~'x("P"I+,)
,
~.a,j"= = PZIi x ( ~ i z ~ + l )
,
maj . -
(x(A)=I
if
A is
true,
~. ( p - . / + l ) . x ( t t - , " I s )
,
!=:i
and
x(A)==0 o t h e r w i s e . )
maj
is
the
familiar
m a j o r - a t a t i s t l c s j c o u n t i n g t h e sum o f d e s c e n t s , m e a n i n g (2.3)
m~i ~ =
maj' c o u n t s
the
the back", ~
~: i 1to(,,)
sum of a s c e n t s .
~
these
can
be i n t e r p r e t e d
as
maj " f r o m
c a n be v i e w e d a s m a j ' " f r o m t h e b a c k " .
H a v i n g in mind t h e r e p r e s e n t a t i o n we e x t e n d
,
statistics
to l a t t i c e
132
of a lattice path paths
by
p b y a p a i r (p,~),
d e f i n i n g maj p = maj ~,
KRATTENTHALER e t c . , if e = ( ~ , l ) . Finally we introduce
the
generating
functions
f ( i . - , x ; q) = s gm~ p , p
f'(p-'-)A; q) ---- s Qmaj'p , P
~'(~-~;
q) = s ~ - ~ '
p ,
P
where
the sums are
a l l p~M(p--~,). A n a l o g o u s l y ,
over
F(p-~X; q)+ = s ~maj p , e t c . , P
where
the sum is over
a l l pEM(p-'+k) +, a n d
f(Ir'*X; q)-= where
the sum is over
s ~
P , etc.,
P
a l l pZM(p--~k)-.
3. GENERATING F U N C T I O N S FOR PLANE PARTITIONS AND ENUMERATIO N OP LATTICE P A T H S . A plane partition of shape k, w h e r e is an array
of positive
(3.4)
all
8x2
...................
a2j
a2=
.............
arts . . . with entries shape
k/p,
decreasing
A~0,
81~
I
. a2,~=
an,k n" in rows
k,~D n and
where
AEDn a n d
integers
and
k~p,
columns. is an
A s k e w plane parLi~on o f
array
of positive
integers
of
the form
(3.2) az,p=+s
an,pn+l with
entries
entries
in each
elt~l+2
--.*
82,~s+l
a2,Fs+2
........
.........................
decreasing
plane partition
.-.
81~pl+l
is
a
column.
in (skew)
rows
.........
8)~
1
sz,~2
8n,k n and
plane
columns.
partition
A column-stricL with
strictly
(skew)
decreasing
A r e v e r s e (skew) plane partition i s a n a r r a y
133
of
KRATTENTHALER p o s i t i v e i n t e g e r s of t h e form (3.1) (or (3.2), r e s p e c t i v e l y ) with e n t r i e s i n c r e a s i n g i n rows a n d c o l u m n s , a column-strict r e v e r s e
partition is a r e v e r s e
(skew)
p l a n e p a r t i t i o n with
(skew) plane
strictly increasing
e n t r i e s in each column. The
w e i g h t w(lD of a
(skew)
plane
p a r t i t i o n is t h e
s u m of all i t s
e n t r i e s . The generating f u n c t i o n f o r p l a n e p a r t i t i o n s of a g i v e n s h a p e A is ~qW(II), w h e r e t h e sum is o v e r all p l a n e p a r t i t i o n s 11 of s h a p e G e n e r a t i n g f u n c t i o n s f o r c o l u m n - s t r i c t (skew) p l a n e p a r t i t i o n s , etc., of a g i v e n s h a p e ~ (or ~/p, r e s p e c t i v e l y ) a r e d e f i n e d a n a l o g o u s l y . In
[t0]
endowed
Stanley
with
theorem [t0,
a
considers labeling
Corollaries
e,
(5.3)
partitions called and
on a
partial
ordered
(P,e)-partitlons.
(7.2)]
says
that
His the
set
P
important generating
f u n c t i o n U(P,w;q) of ( P , w ) - p a r t i t i o n s c a n b e w r i t t e n i n t h e form
~ P,=; q)
~P,w;q) = ( l _ q ) ( 1 _ q 2 ) . . . ( l _ q p )
(3.3) with
~p,=;q)
=~ ~aj
o ,
w h e r e t h e s u m is o v e r all p e r m u t a t i o n s ~ of t h e ~-separator [ t 0 , p.17] of P. Here, p d e n o t e s t h e cardinalJty of P. To obtain the case of plane partitions in this general theorem, for P we h a v e to t a k e t h e s e t
=
0
for a g i v e n A~D,, A~O a n d I A l f p . P(~) b e c o m e s a p o s e r b y (3.4)
(i,,j~) 9 (i2,j2)
i f and o n l y i f
i1 9
and j ' l 9
.
Take t h e l a b e l i n g t--1
,.,(i,j~
= ~ x~: + J ,
t h e n t h e r e is a b i j e c t i o n b e t w e e n t h e s e t of ( P ( ~ ) , w ) - p a r t i t i o n s a n d t h e s e t of p l a n e p a r t i t i o n s of s h a p e ~
n a m e l y , b y a d d i n g I to each of t h e
p a r t s of a ( P ( ~ ) , e ) - p a r t i t i o n . T h u s , b y (3.3), t h e g e n e r a t i n g f u n c t i o n f o r p l a n e p a r t i t i o n s of s h a p e k i s e q u a l to (3.5)
qP
~ x ) , ~ ; q)
('~-q) ('~-q~) 99 9(l-qp)
134
KRATTENTHALER with
s(p(~),=; q) = ~ ~ " J " , where
the
Given
~---~lcT=...ap,
sum
is over
define a multiset
all permutations
being
an
element
permutation
a of
of
the
the
~=~(a)=~1=...~p
a~-separa~or
~-separator
~
By definition
~$S(A). I t i s n o t d i f f i c u l t
of
the
if
~-separator
permutation, give
= Jr
an
or
in
terms
of r~-3,
of the partial
order
The
corresponding
(3.6)
we get
9 (2,1) ~
to see that
a is an element
since and
Consider
For
the
is
~
a
lattice
illustration following
we
linear
(3.4) o n P ( h ) :
e (1,2)
z (1,3)
z (3,1)
z (2,2)
.
w(1,1)=(2,1)=(1,2)r162
is
we
~ At .
(0,~)~M(O-~x) +.
X=(3,2,1).
P(A).
k
~ Xt z a I ~
maj ~ = maj a
paths
Let
(1,1)
a lattice
P(X),
of
example.
extension
and only if
of P(~}j
by
k--I
(3.6)
of
w=121132. O b v i o u s l y
we have
142365.
m a j ~ = m a j a = 7, a n d
By ~ is
permutation.
Summarizing,
these
considerations
furnish
an
alternatlve
expression
W(P(~),c~;q):
for
w(p(~) ,=; q) = ~ qmaj p , where
the sum is over
More generally,
A,FcEDn, Jk~p, a n d
with order
all paths
to obtain
psM(O--e~)+.
skew plane
partitions
of given
shape
J~/p~
IA-p|=p, we d e f i n e
relation
defined
i n (3.4), a n d
with labeling
|--1
=o( i ' . D = The
(P(A/p),wo)-partitions
ordinary generating
plane
are
partitions
function
for
~ (~t--~'~) + (.P-~i)
#.=I
skew
comes skew
out plane
plane for
partitions.
p=O.)
partitions
written
(3.8)
qp
, ~ P ( X / i ~ ) ,~o ; q)
(l-q) (1-,f)..
135
9
9(1-qp)
Then, of
(The
case
analogously,
shape
k/~
can
of the be
I~RATTENTHALER
with
(3.9)
Y(P(X/p) ,=o; q) = ~ cPaJ P ,
w h e r e t h e sum is o v e r all pEM(p--*X) +. For the labeling
=c(i,j~
=
~:
(xt-),~) § (J-),i)
t=t+l
the
(P(~,/p),Wc)-partitions
are
column-strict
Similarly, one obtains the generating
skew
plane
partitions.
function for column-strict
plane
partitions of shape k/p to be
(3.10)
qP (l-q) (1-q~).. 9 ( 1 - ~ )
with
Y(P(x/p) ,=c; q) = ~
(3.11)
~'P
,
w h e r e t h e sum is o v e r all p~M(p--~) +. L et P ( ~ / p ) d e n o t e t h e t h e p o s e t w i t h same b a s i c s e t as P ( ~ / p ) , the right-hand
(i,,j,)
s i d e o f (3.7), b u t w i t h r e v e r s e d i f and o n l y i f
,~ ( i = , j = )
i.e.,
partial order, meaning
isai=
and ds~dz
.
For the labeling tl
(xt-~t) + (xi-.hq)
Z
= H i , J~ =
t----i'l't
we g e t t h a t t h e g e n e r a t i n g
function for reverse
skew plane partitions
of s h a p e k / p is e q u a l t o
~.e(x/p), =.,,4 q) (3.12)
qP
( 1 - q ) ( 1 - q ~ ) . 99( 1 - ~ )
with
(3.13) For the labeling I--|
mcr(i,J) we o b t a i n t h a t t h e g e n e r a t i n g
=
Z (Xt-Ft)
.Ir.~ l
+ (XI-J~I)
function for column-strict
136
reverse
skew
KRATTENTHALER
p l a n e p a r t i t i o n s of s h a p e A/p is
q)
~ . , ~ x / m , ) , ~0cr;
(3.14) (t-q) (l-q,)
9 9 (1-~)
where
w(.~x/p),~,cr; q) ~ ~ ~
(3.r
p
9
I n b o t h c a s e s t h e s u m is o v e r all pEM(p--~A)+.
4. Z E I L B E H G E R ' S
section,
in
order
recapitulate
REFLECTION
to
make
PROOF.
the
Z e i l b e r g e r ' s [13]
Let A,pED,
following
method
of
more
counting
and
A~F. In this
transparent,
we
the
of
number
e l e m e n t s of M(0-~k) +. A l i t t l e b i t more g e n e r a l l y , we e x t e n d h i s m e t h o d to e v a l u a t e
the
n u m b e r of e l e m e n t s of M(p--*A)+, w h i c h , r e c a l l i n g t h e
d e f i n i t i o n of F(p-~k;q) +, is s e e n to be e q u a l to F(F-~A;1)+. F o r t h e n u m b e r of all l a t t i c e p a t h s from F to ~, F ( F - ~ I ) ,
(4.1)
~r-+x;4)
holds
= [)x-N)] LA-pJ
F o l l o w i n g Z e i l b e r g e r we d e f i n e e~ :
(1-,:,(1),...,/-r
.... ,~-,(n))
.
The c r u c i a l p o i n t i n t h e p r o o f is to c o n s t r u c t a b i j e c t i o n b e t w e e n
u
O" e v e n
~o+~---+x)-
and
0
~aa~p~+~--+x)- ,
which p r o v e s
(4.2) This
o" ~verm 'j~p'O'+'eO'''~'~; I ) - - :" ~ ~,odd~#kC+e~'--'#'A; 1)--
is
done
by
a p p l i c a t i o n of
the
reflection
.
principle.
Consider
a
l a t t i c e p a t h of M(pa+e#-~A)-. Let Hj b e t h e l a s t h y p e r p l a n e of {2.2) t h e p a t h meets. S i n c e r e f l e c t i o n with r e s p e c t to Hj h a s t h e e f f e c t (4.3)
IRj(x, .....
xj,xj+,
.....
.,v) = ( x l . . . . .
xj+~-l,xj+l
.....
= ~(j,j+~)
+ e,,(j,j+,)
.
we have (4.4)
~j(~a+~)
137
x.)
)
KRATTENTHALER
((j,j;+l)
is
the
transposition
which
exchanges
j
./+1.) T h e r e f o r e ,
and
r e p l a c i n g t h e p o r t i o n of t h e p a t h u n t i l t h e l a s t m e e t i n g w i t h Hj b y i t s r e f l e c t i o n w i t h r e s p e c t to Hj, t u r n s t h i s p a t h i n t o a p a t h f r o m P~,C.1,J+,) + e ~ C j , j + ~ )
=
. . . . Fo(n)+n-o(n) )
.... ,paCj+l)+.f-r162
= (pa(,)+1-r
to ~, t o u c h i n g Hj. T h i s d e f i n e s t h e d e s i r e d b i j e c t i o n , h e n c e (4.2) h o l d s . S i n c e , b e c a u s e of IAtD,, f o r cfZid we h a v e
( p ~ t e a ) ~ D , , we g e t
(4.5)
T h e r e f o r e , b y c o n s e c u t i v e u s e o f (4.2), (4.5), a n d (4.1),
(4.6)
~'{0---),~; 1) + : F(O--~X; 1) - F(O--~x; 1 ) -
: .~O.--.fx;t) + J i d (-1)sgn o F(l~+eo.--)x;1)=
Z
(-1)sgn
r /'(~+~--*x;1)
~s
Z
=
(-I).r ~ f ,x-,l I
ffi l~-pl! d e t ( 1 / ( x s - s - p t + ~ ! ) RRMARK. Z e i l b e r g e r w a s w r o n g lattice path meeting,
touches
because
and
reflecting
this
counter-example.
Let
when
defines
n=~,
ecffi(0,-1,1). T h e l a t t i c e p a t h
~=0
no and
.
taking the first
the
part
of
bijection. ~=(1,1,1).
((0,-1,1), 221)
the
path
We
give
For
first
hyperplane until a
0=(2,3)
a
that simple
we
have
meets the hyperplane
x2-x~ffi-1 ( n a m e l y a f t e r i t s f i r s t s t e p ) , t h e r e f l e c t i o n w i t h r e s p e c t t o x2-xsffi--1 of t h e p o r t i o n o f t h e p a t h u n t i l t h e m e e t i n g p o i n t (0,0,1) g i v e s the path into
(0, 321). S i m i l a r l y , t h i s p r o c e d u r e
(0, 321),
the
same
path.
reason is that the property (2.2)" is n o t p r e s e r v e d (In our
example
((-1,1,0),
by
taking
hyperplanes
of
meeting point.
this cannot
be a bijection.
reflection until the first
311)
last is
Therefore
The
first
meets
//1, b u t
meeting, preserved
this
for
"meeting
its
under
Hj
reflection
of
meeting point. image
m e e t s Hz). T h i s m i s t a k e is c o r r e c t e d
the
(2.2)"
(e(l,a)ffi((-1,1,0), 311)
" m e e t i n g Hj a s f i r s t o f a l l h y p e r p l a n e s
under
r e f l e c t i o n , (0, 321), f i r s t above)
Hence,
turns
as
(as d o n e
last
until
mapping is an involution and,
under of
the
all last
hence, a
bijection. The
same
mistake
refine Zeilberger's
was
made
by
Watanabe
and
r e f l e c t i o n p r o o f . But e v e r y t h i n g
138
Mohanty [12], remains true
who after
KRATTENTHALER replacing lines 21-23 on page 282 of [12] by "for the ]asr time, only
a n y one of t h e h y p e r p l a n e s (Such a path m a y
[ [ K ( k ) ] : k E S ] o u t of [[K(k)]:kE{'1,2,...,n-1}~.
[g(k)], kfS, b u t only
meet
before meeting at least
[g(k)], kts)."
one
In
our
context
the
above
reflection
because, when reflecting a part about
the
m a j o r of i t s image.
in o r d e r
to t h e
transferred
modified
to generalize
the
same point as the reflection
would do, b u t , w h a t is more, a r e The
be
n e x t s e c t i o n we g i v e m a p s w h i c h s e n d
t h e i n i t i a l p o i n t of a l a t t i c e p a t h ~-~'-)preserving.
must
o f a l a t t i c e p a t h , n o t h i n g c a n be s a i d Therefore,
r e f l e c t i o n p r o o f to q=l, in t h e procedure
procedure
remaining
steps
(almost) m a j - ( m a j ' - , ~---~-,
in
the
above
proof
can
be
a l m o s t v e r b a t i m . T h i s will b e d o n e in s e c t i o n 6.
5. THE BIJECTIONS. As m e n t i o n e d a b o v e , in Z e i l b e r g e r ' s p r o o f g i v e n in t h e p r e c e d i n g
s e c t i o n , we do n o t r e a l l y n e e d t h e r e f l e c t i o n . What we
n e e d is a b i j e c t i o n w h i c h s e n d s a l a t t i c e p a t h p f r o m p to A t o a l a t t i c e p a t h ~ f r o m IRj(9) to A, w h e r e lattice path (pj-~j+l§ in
the
meets. Regarding
Hj i s t h e l a s t h y p e r p l a n e
o f (2.2) t h e
(4.3), if PimP j + l , we s e e t h a t ,
changing
o f t h e s t e p s in t h e x j + ~ - d i r e c t i o n in t h e p a t h p i n t o s t e p s xj-direction,
Analogously, xj-direction
we
obtain
I~jZpj§
if
a
lattice
path
(llj§
changing
from
of t h e
i n t o s t e p s in t h e x j + ~ - d i r e c t i o n , t u r n s
i~j(IL) steps
to in
~. the
p i n t o a p a t h from
Next, f o r a f i x e d j, we i n t r o d u c e t w o a u x i l i a r y m a p s , L , ( " l o w e r " ) a n d Rj
("raise").
xj§
Lj
(Fj-i~j§ respectively,
has
the
into a step
effect
of
changing
in xj-direction,
a
single
Rj h a s
step
the reverse
in
the
effect.
a p p l i c a t i o n o f L j o r ( p j + ~ - ~ j - 1 ) - t i m e a p p l i c a t i o n of Rj9 depending
on
whether
pj~lij+l
or
not,
leads
to
the
desired bijection. DEFINITION 1. L e t j b e a f i x e d i n t e g e r , I ~ n - 1 , multiset permutation minimal v a l u e at
where the
i=O o r i f p .
function
Let k
be
a n d let lffi~l...~p be a
i--~dj(l,19 does the
smallest
not reach itB
integer
1~k~p-l~
w h e r e the f u n c t i o n ~-->dj(l,i) r e a c h e s i t s minimal v a l u e , in o t h e r w o r d s gk
implies
dj(.,i)
l~k
implies
dj(.,i) ~ dj(,,k) .
x dj(.,k)
,
Then ~k=j+l. T h i s g i v e n , we d e f i n e t h e "lower" f u n c t i o n Lj by:
139
KRATTENTHALER
(A) I f ~ satisfies (5.1)
le~e+Z~...~tf~f+z~...X~k_l~rl~k+|~...~g&~g+l
where O ~ e + l z / ~ l z ~ p ,
,
and
either
(a)
_~lzkzg
or
(b)
~=~P~1=2 and
or
(c)
h=~
If=~f+=
and ~9-s'~g+=
,
then Kj(I)
= ! 1 ...lele.i. ]...~r_=
where r i s = i n / ~ ] j~1 r
and
J ltr---~flf+l
'''Ik-llk+l.--lgltg§
,
~/th
etli~/"
,
if t h e r e is ~oz~e, ~=/~I o (B) I f 9 s a t i s f i e s
(5.2)
le~e+|~...&Ik--lJj~lZlk+t6...~lf~lf+l~...~g~lg+l
where l ~ e + l z f z ~ p ,
9
and
either
(a)
e+lzkzf
or
(b)
~=e+l
or
(c)
k=f
and and
%~%+=
!+-,~1++,
,
then
5(11) = I z . . . ~ e 1 ~ e + Z . . . W k - Z l k . f Z . . . l f l f + z . . . l r - -
z j~r...~.gltg+Z.oo~p
9
where r is minimal with
,f~r
and
]~ l"=_r';g ,
i f t h e r e is none, (By convention,
I==g'rl.
i f J~j,
REMARKS, (1)
Given
condition required
the symbol I t ...lj means
j
and
a
multiset
i n D e f i n i t i o n 1, t h e r e
permutation
are
(5.3)
It k--| ~",)+I~'1t k-l-i ,
2~kLp
(5.4)
lk-- i '+,,,j~IZ11k+ I ,
l~kzp
(5.5)
II k-- i "~, ~ 1/'It k-l-i ,
2~kLp
(5.6)
IK k - - I = : ~ F t X I ~ k + ] t
,
2~kzp
and
]~=I
(5.7)
J~1~12
(j+ 1==! k+ =
is
contradiction Case
(5.3)
impossible,
because
the empty word.)
~ satisfying
the
exactly five cases:
.
then
dj(~,k+1)=dj(1,k)-1,
in
to the minima]ity of dj(I,k).) belongs
to
case
(A)(a)
140
in
D e f i n i t i o n 1,
(5.4)
to
(B)(a).
If
KRATTENTHALER 9 k-1~Ik+,,
(5.5) belongs
S i m i l a r l y , if ~ k _ l ~ k + l ,
to case (A)(c), otherwise it belongs
to (B)(b).
(5.6) b e l o n g s t o (A)(b), o t h e r w i s e i t b e l o n g s to
(B)(c). F i n a l l y , (5.7) b e l o n g s to (B)(c). T h e r e f o r e D e f i n i t i o n 1 c o v e r s all possible
cases;
moreover,
given
a multiset
permutation,
this multiset
permutation uniquely belongs to only one of the cases (A) or (B). T h u s Lj is well-defined. (2) To be
precise, the inequality chains
(5.1) and
(5.2) should
be
understood as short-hand writings in the following cases:
k=-f+l
(5.1)
in
means
~e':le+S~...slflj+lXlk+S~'*..x~g';Ig+S. (5.2) s h o u l d b e u n d e r s t o o d e==O
(5.1)
in
the
k=-g i n
inequality
(5.1),
chain
b-~-e+l o r
and
k=-s in
analogously. ~ l~...x~ f*;! f+zx...x~ k_ i ~ f l ~ . ~ k+x~...~1 gd;~g+z~
means
a n a l o g o u s m e a n i n g s h a v e e=O in (5.2) a n d g = p in (5.1) o r (5.2). in (5.1)
11~...Slk_l~.Prl~k+l~...~19~l(9+ 1. I n t h i s c a s e L j ( I )
means
should be understood
as
Lj(,) = j ,, ...,k_,~k+,...~g~g+, ...,p . t=-p in (5.2), meaning l~e~.le+l~;...~Ik_l~j~l,~Ik+l~.,.~;l~p, because
then
dj ( , , k ) = d j ( I , p ) ,
which
contradicts
iS impossible,
non-minimality
of
dj (.,p). (3) The f o l l o w i n g p r o p e r t i e s
of dj hold:
(5.8)
dj(Zj(,),i) ----dj(,,i) ,
for 0, izmin (r, ]f)
(5.9)
dj(Lj(~),i)
ffi d j ( , , i )
+ I ,
for min(r, J0~izmax(r,k)
(5.10)
dj(Zj(,),/)
= dj(,,i)
+ 2 ,
for max(r,k),i,p
.
S i n c e l t s f [ j , j ~ l ] f o r m i n ( r , k + l ) ~ i z m a x ( r , k ) , we h a v e
(s.11)
d~(~(,),r-1)
= d~(,,,k) + I .
Together with (5.8)-(5.10) and the definition of k this leads to
In
other
i-~I
implies
dl(ij(,),i) ~ dj(Ll(s),~-d)
,
~-1
implies
d j ( I j ( , ) , i ) "~ d j ( t j ( , ) , r - 1 )
.
words,
i-~dj(Lj(w),i) 2 larger than and
(5.11),
(r-l)
is
the
largest
integer
r e a c h e s i t s minimal v a l u e . M o r e o v e r , t h e minimal v a l u e o f and
the
property
~-~dj(Lj(~),~. dj ( ~ , p ) ~ d j
Definition 1. As c o r o l l a r y of (5.11) we g e t
141
where
the
dj(Lj(~),p)
function is at least
T h i s b a s e s o n (5.q0)
(~,lv)+l,
required
in
KRATTENTHALER (5.12)
=in d~(l,,(,),i) (
t,)
~
-
-
= rain d ) ( . , i ) |
-
tl
-
+
o
(4) Lj h a s t h e i m p o r t a n t p r o p e r t y (5.13)
maj($3(~))
= maj t -
1 .
(This is t h e r e a s o n w h y we c a l l e d L j " l o w e r " f u n c t i o n . )
F o r c a s e (B)
in
Lj(~),
Definition 1
this
is
D(,)=[...,e,f,~,...] and
clear
from
the
definition
of
D(Lj(~))=[...o,f-I,~,...]. This
means,
since
to obtain
D(Lj(~)), in D(,) the element f has to be replaced by f-l, which, by (2.3), proves (5.13). In case (A) we claim that ~r_1=i Indeed, supposing tr_l=j,
because
dj(~,r--2)=dj(,,k), smallest integer minimal
with
~t ~ [ j , ~ + l J
of in
contradiction
where
J~"r
for
b-+dj(~,]~
and
"r-tX"r,
to
rai, k-1, the
reaches we
condition its
would that
k
minimal v a l u e .
conclude
D(~ )=[...,e+1,...,f-l,f+l~f+2,...,g,...]
we
~r-~XJ'
is As
the r
is
Consequently,
D(Lj (~))=
and
=[...,e+l,...,f-l,f,f+2,...,E,...]. This mean.,
have
to o b t a i n D ( L j ( , ) ) , in D ( , ) t h e
e l e m e n t f + l h a s to b e r e p l a c e d b y f, w h i c h a g a i n i m p l i e s (5.13). The
next
definition introduces
the
"raise"
function
Rj,
which
will
t u r n o u t to b e t h e i n v e r s e o f L j .
DEFINITION 2. Let j be a fixed integer, I ~ n - 1 , a n d let ~=Iz...~P be a multiset permutation where dj(~,p) exceeds the minimai value of the function J--)dj(~,/) b y
at least 2. Let
(r-l) be the largest integer,
0&r-l~p-1, where J--)dj(~,z~ reaches its minima] vaJue~ meaning i~r-1
implies
dj(.,i) 9 d j ( , , r - - ' l )
l~r-1
i~olies
dj(.,i)
x dj(,,r-'l)
Then I r = j. This given, we define the "raiBe" f u n c t i o n
, . Rj by:.
(A) I s 9 s a t i s f i e s
where O.=e~ l z 2"L&~p, and
or
(a) (b)
e+lzr~f z=e+l and ~ . + =
or
(c)
~=f
either
~-~f+!
and
,
then Rj(~)
= ~l...~e~e+l...~r--~wr+l
.... ~f~f+='''~k--~
where k i s mini~a] with
j+lxl k
and
~l~]~g ,
142
J~l Ik...Igtg+1...t
p ,
KRATTENTHALER if
there is none,
k=~l.
(B) I f ~ s a t i s f i e s
where l~:e+lz.l~lz~p,
and
either
(a)
.f~lzrLg
or
(b)
.-,=/~1
or
(c)
~=g
and
and
~'*~+= ~9-~x~g+~
then ~ ( I I ) = "~l.--leIIe+|---1~k--] ~f~i ~k'-'~If11T+1"''~Ir--lltr+1 "~
"''~p
where k is minimal with .fl-lz'R k
and
e+l~]~.f" ,
if there is none, l~=.t~-I.
REMARKS. (1) As a b o v e , it c a n b e s e e n t h a t D e f i n i t i o n 2 c o v e r s all possible
cases.
In
particular,
the
case
r=l
belongs
to
case
(A)
in
D e f i n i t i o n 2. I f J ~ = , t h e n i t is t h e c a s e e=0 i n (A)(b), if . / ~ 2 , t h e n i t is t h e c a s e z~-I i n (A)(c). I n t h e l a t t e r c a s e Rj(~) s h o u l d be u n d e r s t o o d a s Rj(~)
= "=--.'k-,
o#1 - k . . . ~ g ~ g + z . . . ~ p
-
~-Wr-i is i m p o s s i b l e , b e c a u s e t h e n dj ( I , r - 2 } f f i d j ( ~ , r - 1 ) - l , i n c o n t r a d i c t i o n to d j ( 1 , r - 1 ) b e i n g minimal. (2) The i n e q u a l i t y c h a i n s (5.14) a n d (5.15) s h o u l d b e u n d e r s t o o d a s short-hand ~-p
in
w r i t i n g s i n a s i m i l a r m a n n e r like (5.1) a n d (5.2). T h e c a s e
(5.q4),
leglte+l~oo.~l~r--lxJ%Ir+lx0,oX~p, iS
meaning
because then dj(~,p)=dj(~,r-1)+l,
impossible,
i n c o n t r a d i c t i o n to t h e c o n d i t i o n t h a t
d j ( ~ , p ) e x c e e d s t h e minimal v a l u e of / - ~ d j ( ~ , D b y a t l e a s t 2. (3) I n a
similar m a n n e r as
smallest i n t e g e r
where
the
above, it can
be
function /-~dj(Rj(~),D
seen
that
reaches
k is t h e its
minimal
v a l u e . B e s i d e s , /-~dj(Rj(~),13 does n o t r e a c h i t s minimal v a l u e a t /=0 o r Jffip. (4) Rj h a s t h e p r o p e r t y
(5.16) which is p r o v e d
=aj(Rj(.))
= maj .
quite similarly as
+ I
,
(5.13) a b o v e .
((5.16) is t h e r e a s o n
for c a l l i n g Rj " r a i s e " f u n c t i o n " . )
R e g a r d i n g t h e r e m a r k s (3) a f t e r D e f i n i t i o n s I a n d 2, r e s p e c t i v e l y , we see
143
KRATTENTHALER
ej
(s.~7)
which m e a n s t h a t Rj a n d
o Lj
=
o ~j
r.j
id,
=
Lj a r e i n v e r s e s of each o t h e r . I n t h i s s e n s e
we may w r i t e Rj--Lj - l . Now we a r e
in
the
position
to c o n s t r u c t
the
desired
bijection
between
Uve ~lJ~p~+ed"~,X)- and
r oUdd~G@~--~A)--
DEFINITION 3. L e t A,F~D., A~p, a n d
.
l e t pffi(p,~) be a l a t t i c e p a t h o f (2.2) p meets.
M(p--)x)-. L e t Hj be t h e l a s t h y p e r p l a n e
of
Then ~ is
defined b y
* ( p ) = (~j (I,), zjl'.l-~'J+*+l(-))
(5.18)
9
REMARKS. (I) If t h e e x p o n e n t ( p j - p j + z + l ) i n (5.18) is n e g a t i v e , b y Lj p j - p j § (2)
we , e a l l R j - ( P J - P J + I + I ) .
To p r o v e
that
# is
well-defined,
we
must
show
that
Lj
is
a p p l i c a b l e o n = f o r ( [ J j - p j + l + 1 ) times. F i r s t we c o n s i d e r t h e
case
p j ~ p j + | . Let k
be the
smallest integer
w h e r e /-+dj(=)1~ r e a c h e s i t s minimal v a l u e . C o n s i d e r a p a t h p o i n t p(m), l~mzp, w h e r e p m e e t s Hj, t h e h y p e r p l a n e x j - x j + l = - 1 . S i n c e p s t a r t s i n F, r e m e m b e r i n g (2.1)) we c l e a r l y h a v e d j ( = ) m ) = p j + l - p j - l ) a n d t h e r e f o r e
(5.19)
rain d j ( , , i )
t; p j + z - p j - 1
.
t
I f Lj is a p p l i c a b l e o n I f o r t t i m e s we g e t (5.20)
.in
dj(Lj%(.))i)
b y (5.12)
K pj+,-pj+~--1 .
I
S i n c e ASDn, w h i c h i n p a r t i c u l a r s a y s Aj~Aj§
we g e t
dj(11,p) = ( A j - p j ) -- ( X j + l - p j + z ) •ffi MJ+I-PJ + (~J-AJ§ MJ§
)
a n d a f t e r t - t i m e s a p p l i c a t i o n of L j , if t h i s is p o s s i b l e , u s i n g (5.10) dj(J~jt(~),p) ~ pj+~-pj+2t 9 C o m p a r i s o n w i t h (5.20) g i v e s (5.21)
dj(LjtC-),p)
~ .in t
144
dj(Ljt(.),~)
~ R A T T E N T H A LER
f o r all t~0 w h e r e
L j t ( ~ ) is d e f i n e d . B e s i d e s , d j ( L j e ( , ) , 0 ) = O f o r all t~0.
T o g e t h e r w i t h (5.20) t h i s l e a d s t o
(5.22)
"- =in dj(Lj~:(,,),i)
d,,(Lj~:(,,),O)
valid for all t with O~b~pj-pj+=, I f Ljt(~) (5.22), t o g e t h e r , not reached t=0,
is well-defined,
(5.21) and
s i m p l y s a y t h a t t h e minimum v a l u e o f / - - ~ d j ( L j t ( 1 ) , ]") i s
a t ~=0 o r ~=p. Hence, Lj is a p p l i c a b l e o n L j t ( ~ )
is w e l l - d e f i n e d a n d for
,
0$t~pj-pj+l).
inductively
we
B e c a u s e of L j t ( ~ )
deduce
that
Lj
is
(ff L j t ( ~ )
being well-defined
applicable
on
~
for
{Fj-pj+~+l) times. This shows that ~ is well-defined for PjlPj+l. Similar a r g u m e n t s s e t t l e t h a t ~ is w e l l - d e f i n e d a l s o in t h e c a s e p j L p j + s . (3) We claim t h a t t h e f i n a l p o i n t o f ~(p) is ~ p to ~, 9 i s a m u l t i s e t p e r m u t a t i o n
S i n c e p is a p a t h f r o m
b e i n g a n e l e m e n t o f S(A-p). E a c h
a p p l i c a t i o n o f Lj t u r n s
a s i n g l e j + l i n t o a j, a n d e a c h a p p l i c a t i o n o f
R j f L j -s t u r n s
j i n t o a ./+1. T h e r e f o r e
a single
Lj~J-PJ+s+q(~) i s e q u a l
to
the
number
(Xj-pj)+(pj-pj+l+q)=~kj-pj+a+t,
/.jPJ-PJ+s+l(~)
of fs
t h e number
(~j+a-pj+l)-(pj-pj+l+q)
is equal to
in
Of ( J ~ l ) ' s
in
=~j+l-pj-1.
By (4.3) t h e j - t h c o o r d i n a t e o f ~j (p) i s p j + l - q , t h e ( j + q ) - t h
=
c o o r d i n a t e o f ~j{F) i s F j + I . L e t v b e t h e f i n a l p o i n t o f *(p). T h e n v t is equal
to t h e
/-th
coordinate
LjPJ-FJ+*+I(I).
of ~j(p)
added
to t h e
Together with the considerations
number
above,
o f z~s in
this estab-
l i s h e s ~=~ (4) L e t Hj b e t h e l a s t h y p e r p l a n e
o f (2.2) t h e p a t h pffi(p,~) m e e t s . L e t
p{m), l~m~p, b e t h e l a s t p o i n t w h e r e
p m e e t s Hj. T h e n ~m§
dj(~,i)~pj+=-pj-I
Besides,
dj(~,m)f~j+~-pj-I
and
i n t e g e r k, w h e r e
d j ( ~ , k ) i s a minimum f o r t h e f u n c t i o n i--'~dj(~,i), m u s t
f o r a l l i'~m, T h e r e f o r e
for an
hold k~m, I f p j ~ ' p j + l - 1 we h a v e dj(ll,O)
therefore
in
this
case
= 0 L ilj+l-pj--1
= dj(~,B)
even
view
kzm.
In
of
,
this
and
looking
at
D e f i n i t i o n s 1 a n d 2, i t i s n o t d i f f i c u l t to s e e t h a t f o r l~m [s From
this
fact
a f t e r it, t h a t
we
t --- I t deduce,
and
[Rj(~)] t = I l .
remembering
Definition 3 and
application of # leaves the path-part
145
between
R e m a r k (3) p(m) a n d
KRATTENTHALER p(p) u n c h a n g e d . the
property
preserved
In particular,
"meeting
under
Hj
p(m) a l s o is a p o i n t of #(p). T h e r e f o r e
as
last
of
all
hyperplanes
of
(2.2)"
is
a p p l i c a t i o n of #. C o n s e q u e n t l y ,
(5.23) (* o #)(p) = (# o #)((~,I)} = #{Rj(p),Lj~-PJ+'+I(1))
= ((Ej o Rj)(p),(Lj[RJ(F))J-[EJ(P)]J+z +1 o LjFJ-PJ+z+I)(1)). Rj o Rj = id,
But
and,
by
[ ~ j ( p ) ] j + , = pj+1. T h i s t u r n s
[Rj(F)]j
(4.3),
,ffi p j + , - 1
and
(5.23) i n t o
(# o #)(p) = p .
(5.24)
I n o t h e r w o r d s , # is a n i n v o l u t i o n . (5) To s e e t h a t ~ i s a b i j e c t i o n b e t w e e n ~w, ,'~ pc+ e~--)X)-
and
~s sN[ IAo+e~--*A)-
take a path p=(po+e#,1), being an element of M(Fo+e~--)A)-. Let Hj be the last hyperplane of those hyperplanes in (2.2) the path meets. Then, by
(4.4), #(p) is a path from
hence
l~#(j,j+,)+e#(j,j+1)
to A touching
#(s) is an element of M(Fc(j,j+x)+eo(j,j+,)--#A)-.
Hj,
Since ,1, is an
involution, ~ must be a bljection. (6) Using
(5.13) and
weight property
(5.16), respectively, we
obtain the following
o f #:
(5.25)
maj
e(~)
= m~
p -
pj+pj+,-I
,
w h e r e ~ is t h e i n i t i a l p o i n t o f p. F i n a l l y , t o i l l u s t r a t e a c t i o n of L j , Rj a n d }, we g i v e a n e x a m p l e . L e t
pz=((1,-1,-1), !z=31232223212131),
which
A1=(5,5,3). T h e f u n c t i o n i--)dL(Iz,z') i=11,
therefore
by
/.(!1)=31232221312131, kffi-14),
reaches
D e f i n i t i o n 1(A)(a)
Rz (!1)=31232223212321.
K--4, r=3),
I~z=(1,-1,-1) to
i t s minimal v a l u e a t /=9 a n d
(e=6,
The
f=7,
function
L2(~z)ffi12232223212131,
k=9,
gffil0,
maj Lz(=z) = m a j L , ( = , ) = 45 maj R 2 ( = z ) =
in
}-~dz(11,i) by
rffiS),
with
its
(e=0, k = l ,
D e f i n i t i o n 2(B)(b)
(effil,
maj I ,
= 46,
We
accordance
47 in a c c o r d a n c e
146
reaches
by Definition l(B)(c) and
f=4, rffiS, g--8, b---5), R2(Iz)--31233223212131. maj R ~ ( l i ) =
from
a n d b y D e f i n i t i o n 2(A)(c) (e=10, ~ffi12, f=-12, E=14,
minimal v a l u e a t iffil a n d ~-4, t h e r e f o r e f=l,
is a p a t h
have with
(5.13),
and
(5.16). Nz i s t h e l a s t
KRATTENTHALER
t h e r e f o r e we o b ~ i n
h y p e r p l a n e of [H~,Ha] pi t o u c h e s , ~ - ~ + t = 3 , ,i,(pt)
=
(IR~(1,-1,-1),/as(.~,))
Indeed this is a path = maj ~
-
3
from ( - 2 , 2 , - 1 ) 03 x~=(5,5,3) w i t h maj
in a c c o r d a n c e
~ w i t h t h e h e l p o f which
evaluated.
We s h a l l
only
give
With
4.
the
~(p--*X; q)+ and F ' ( F - ~ X ; q)+
the
construct ~, but without coment, DEFINITION
#(p~)
analogous
definitions
in
assumptions
of
Definition
I
we
and
either
(a)
e+4/k~'~
or
(b)
]Fel'l
or
(c)
/~s
'~ez'~+:i
and
and
~f_tzl~+~
,
then
= ~...~e~e+t...~k-z~k+~...Ir-
~ j~r...~tlf+l..o~,
,
where r is minimal with Jh~ r
and
el-l":x~f
,
i f there is none, ~=i~l.
(B) I f ~ satisfie~
~eile+lZoo.Z~k--lz,~lzlk+lz.-.zlfi~f+t where l ~ e f l z / t ; p ,
and
eider
(a)
el- 1zkz f
or
(b)
ie=e+l
or
(c)
k=f
and
and
le~e+2
~_z~+~
,
then -gj(~) = 1 ~ - - - ~ , 1 ~ + l - - . ~ r - ~
j~r...~k-~k+~.~.~l~+l...~
where r is minimal with
~r
and
e+1~ ~ f
i F there is n o n e ,
=
can be order
define
(A) If ~ satisfie~
Lj(~)
43
to
and leave the details to the reader.
alternative "lower" function Lj b y
where l ~ e ~ - l z t ~ p ,
=
(5.25).
with
~lr--)A; q)+ and F'(p--~X; q)+, b u t we need a n o t h e r
serves to evaluate bijection
3123211131213"1) .
((-2,2,-1),
=
.r=lerl.
147
P ,
an
KRATTENTHALER DEFINITION 5. With the a s s u m p t i o n s alternative "rnise" function Rj by
(A) I f ,
o f D e f i n i t i o n 2 we d e f i n e a n
satisfies "ez~e+lk---b-r-I~J~r+13...;~fz-f+l
9
where l l e + l Z / ~ p , and either
(a)
e+lzF f
or
(h)
r=e+l
or
(c)
~=f
zez.e+=
and
and
~ _ z z , f+l
,
then i
~ ' j ( - ) = Zl . . - ' e ' e + l "
..'k--I
~1
,k.
,.l~r-l,r+l
*.-'p
9
1 ...11p
,
..-'f'f+l
~ e r e k i s miniJal w i t h
j~lx, k
and
etl~I~f,
if there is ~one, ~ = ~ I.
(B) I f , s a t i s f i e s leb--e+lZ.--Z--r--lzJ2--r+lZ---z--fb--f+l
9
where l ~ e + l z i ~ p , a n d (a)
e+Izrz f
or
(b)
~=e+l
or
(c)
zffif a n d
either
and ~ei~l.+= .~-,~.f+,
.
tl~es
.Jl~j(.)
--.~ ~1 " " " l e l ~ e + l - - - l r - - l l [ r + l - - . ' k - - I
where k i s i i n i m a ] .~lzl k if
and
,fl-1 l g k o . . ~ f , f +
with e+l~k~f ,
t h e r e i s none, k = ~ 1 .
DEFINITION 6. With t h e assumptions o f Definition 3, # is defined by
(5.26) where, i f
~(p) = (Rj(I=),-~j p j - p j + , + l ( , ) )
~j-pj+,+lzO, Tj pj-~j+,+l Jeans ~ -(~J-~J+'+r
What we need i n t h e s e q u e l i s ,
U ~po+~---*x)oven
that ~ is a bijection
and
Uaa,~p~+~,--~x)-
0
a n d t h e v a l i d i t y of t h e w e i g h t p r o p e r t y
(5.27)
,
meg ~(p)
=
maJ
148
p
.
between
,
KRATTENTHALER
6. LATTICE PATH ENUMERATION. THEOREM 1. Let p.AED, a n d A~p. Then (6.1)
FCp--~A;q)+ = [ I A - p l ] , d e t (
PROOF.
/ /[As-s-i~t+t]!)
q
We i n t r o d u c e a w e i g h t f u n c t i o n
o~s,Jl~po+e~--~A)-. Let p f ( l i c + e ~ , , )
wz,
acting
be an e l e m e n t o f
on
.
e l e m e n t s of
~l~e+e~-~A)-
for
some o r S , . T h e n w, i s d e f i n e d b y
(6.~)
,,,, ( p ) ffi ~ = ,
. qm~
p
Let Hj be t h e l a s t h y p e r p ] a n e of (2.2) p meets. By (5.18) a n d (5.25)
,,,,(,(p))
(6.3)
= qX.q~,~ p -
I:l,o+~].~+[i,o+e,=,].l+,-'1
,
where
Since~
regarding
(4.4),
[Rj(pc~tee)]j = P a ( j + l ) + j - e ( j + l )
and
ffi ~e(j)+j+l-e(j% we o b t a i n
[l~j(pc§
{[IRj(l~e~)]j}
+ {[IR:l(pr
=
{'~('+')+~21-"(~1)} +
-(~(j+,)+j-(,(s
+
+
T h e r e f o r e (6.31 b e c o m e s w,(~(p))
:
qt-'lt
= wl ( p )
which s a y s t h a t having
in
mind
2
J . q- a j
p
,
# is w e i g h t - p r e s e r v l n g w i t h r e s p e c t to w~~ T h e r e f o r e , Remark (5)
after
r e p l a c e s (4.2) r e a d s
149
D e f i n i t i o n 3,
the
equation
which
KRATTENTHALER
(6.4)
~
O
eve~
q t =l
~po+e~-ax; q)- =
= o ~dd qt=' The
identity
which
replaces
~.o+~--~X; is MacMahon's
(4.1)
T h e o r e m 3.7, p . 4 2 ] , w h i c h i n o u r
notation
q)-
well-known
result
[1,
is
[IX-i,l 1
(6.5)
~p--~Jk; q) = t X--p J
Successive
u s e o f (6.4). (4.5), a n d
qtffi, 9
(6.5) g i v e s
~(~-+x; q)+ ffi F(ff--)X; q ) -
= qtffz
~ l r - ) X ; q) -- qtffi,
= (f='
..~r>x; q) + ~ d ( - 1 ) s g n
ffi ~
~ ,f='
f(~a+e~-+x;
(-1)sgn r eft'
~p.+ea-+x;
(-1)sgn
LX-~-~J
q)-
q)
OESn
=
Z
',,-,,'
o ~ffil
]
0s
ffi [ I , k - p l ] !
which after
det(
division
q
of
[Xs-s-pt+L]!)
$(~t)
turns
into
,
(6.1).
o
THEOR]~I 2. L e t F,AED. a n d Aul~. T h e n /
(6.6)
F'(F-+X;q)+
.ffi [ I X - F I ] !
det(
q
SKETCH OF PROOF. D e f i n e a b i j e c t i o n (x~ ..... x ~ , . . . , X n )
Extending
t to lattice paths
#
/[Xs-m-pt+t]!) t on Zn by
) (-xn .... , - x , - i + , , .... -x~)
p by
t ( p ) ffi ( t C p ( 1 ) ) . . . . .
t(p(p)))
i t i s n o t d i f f i c u l t to v e r i f y
maj'
p = maj t ( p )
and
150
.
.
KRATTENTHALER
,(~p-~x)+)
(6.7)
= ~t(~)-~(~))
+
This f u r n i s h e s
~ ' ( ~ - ~ ; q)+ = F ( t C A ) - ~ t ( ~ ) ; q)+ . T h e n s h o r t e v a l u a t i o n t u r n s f o r m u l a (6.1)~ for p r e p l a c e d b y ~(A) a n d A r e p l a c e d b y ~(F), i n t o (6.5).
0
T H E O R E M 3. L e t p~ED. and A~p. Then (6.8)
~r-~X;q) + = [IX-~l]! d e t ( 1 ~ s - s - ~ t + t ] ! )
SKETCH OF
.
PROOF. The proof runs through quite analogously like
that of Theorem 1 by utilizing ~. ving with respect to ~fi~, w e
Since by (5.27) ~ is weight-preser-
do not have to introduce an auxiliary
weight (which in the proof of Theorem 1 was wl). All other steps may be transferred almost verbatim. THEOREM 4. Let F,AEDa a n d A~p. T h e n (6.9)
F'(Ir--~A;9)+ = [ I A - p l ] ! d e t ( I / [ [ A s - s - ~ t + t ] ! )
.
SKETCH OF PE~OOF. T h e map 9 i n t r o d u c e d i n t h e p r o o f of T h e o r e m 2 s a t i s f i e s (6.7) a n d ..j'p
= m-~ t ( p )
f o r all l a t t i c e p a t h s p. T h i s implies
F'(Ir--~A; q)+ = ~(~)-'+t(F);
q)+ ,
which a f t e r s h o r t e v a l u a t i o n may be t u r n e d i n t o (6.9).
REMARK. Of c o u r s e p r o o f s for
there
is
no
Theorems 2 and 4 in the
d i f f i c u l t y to
for
~-~
and
give
reflection-like
s e n s e of T h e o r e m s I a n d
introducing two further involutions, ~' and #', properties
o
maj', respectively.
3
by
with suitable weightWe
have
avoided
this
because there do not arise new aspects, but application of the map makes t h e p r o o f s of T h e o r e m s 2 a n d 4 s h o r t e r . The r e a d e r m i g h t t r y to f i n d such i n v o l u t i o n s ~ ' and 4 ' .
In the
special case
~=0 t h e
d e t e r m i n a n t s i n T h e o r e m s 2-4 may be
151
KRATTENTHALER simplified.
To t h i s
Vandermonde's
end
we u s e
the
following
which
generalizes
determinant.
LEMMA 5. L e t xz,xa,...,xn,a2,...,a"
be indeterminates.
det((xs+~)(xs+a.-z)'''(x~+~+,))
(6.10)
lemma,
=
Then
!] (xs-x~)
,
SLt~
if,
by
convention,
for
the entries
tffin
in
the
nxn
determinant
are
set
equal to 1. PROOF. T h e is
a
determinantal
polynomial in
l~szLs2~n
expression
xz,x2,...,x
the s,-th
where
p ( x , , . . . , x n)
l] ( x s - x t )
is
is
(n),
(~).
and s 2 - t h
the determinant
(6.11) d e t ( ( x a + ~ ) ( x s + a n - , ) " "
left-hand
with degree
n
we h a v e x s l f f i X s 2 ,
are identical. Therefore
on the
If for
some
polynomial
sz,sa
with
row i n t h e d e t e r m i n a n t
may be factorized
( x s + a t + z ) ) ffi ~ t ( x s - x t )
therefore
s i d e o f (6.10)
in
Xz,...,x,.
p { x , , . . . . xn) i s
9 /X~xz. . . . . xn) , But
identical
the
degree
of
to a constant.
eL{
Considering coefficient
the
product
of
the
main-diagonal,
it
develops
of the monomial xz,-zx2 "-2.. -xn_zix, ~ on the
o f (6.11) m u s t b e e q u a l t o 1, h e n c e
p(xl,...,xn)ml.
COROLLARY 6. L e t ~.[D,, X~,O a n d
IXl:p.
[~]:
left-hand
the side
O
Then
F'(0--~X; q)+ ffi [ d , ] . . . . [dp]
(6.12)
that
'
and
[p].,
~ o - - ) x ; q)+ = r'(o--~x; q)+ : ~ ' [d. ] .... [ ~ ]
(6.13)
where Kz= ~: ( i - 1 ) X !
,
'
dp denote the hook-]en~l:h o f A (see
a n d dl . . . . .
!=1
[11,
Definition
15.1]).
PROOF. Setting ~
in (6.6) g i v e s
F ' ( O - - ~ x ; q ) + ffi [ I x I ] , . d e t ( ffi
[Ixt],.
= [sxl).,
f-;~s + s - t l - f - ~ ' s l . ~ ~ 9 a ~/[Xs_s+t],
q~
n [xri+n],)-' ( [[
det(
( | :fi! [ ~ , - i + n ] '. ) - '
~'
|=!
9
)
f-,x,+s- ~ f-x,i 2 ~ , - i 2 ~[~ _ s + n ] . . . [ X s _ s . ~ t + l ] )
qI
det((q-Xs+s[xs-s]+[n])...
152
(q-Xs+S[Xs-s]+[ ~ 1 ] ) )
,
KRATTENTHALER
where
K~ = ~ {~k~(~-i)+i2-rH)
Application
.
|=I
of
Lem~a 5
with
=q-~'s+s[XB-s] and a t = [ / ) y i e l d s
~"
( I~ [~,-i+.]:)-'
= (t~,t];
~'(0--*~; q)+
l] (e-x'+s[x.-s] - e-x~+t[x~-t])
all.
|~1
gL~
where
$s =
~
(Xi(tri)+i2-ni) +
(-Ai+i)(~-i) = 0
~
.
The proof of (6.12) is completed by the observation
..... .,-,+.])\
= [., .... , . , ] ,
when being r e g a r d e d as a multiset identity. (See for example [7, po9, identity (4) in Example 1].) In o r d e r getting
to p r o v e
~0---*~; q)+
(6.q3) set
F'(0-~;
=
q)+
F--0 in
(6.8) and
(6.9), r e s p e c t i v e l y ,
=
= [l;kl]!
n ( | =III
= [)~)]'
( II [x~-i+n],
[x1-i+n]!
R
)--I )--a
det([Xs-s+n]..-[x,-s+L+i] )
q~' 9
9 det{([As-s]+q-n[n])...([;ks-s]+q-*.-l[~4]))
,
where
~c 2 ) - c"~2) = 2("~ 1) .
=
I=1
Application of Lemma 5 with xs=[As-s] and ai=q - i [i] leads to F ( 0 - ~ ; q)+ = F'(0--~x; q)+ =
= [JAI]:
~"
( ~ [x,-i+n]:)-' I=1
I] [ x , - s - x t + t] ,
sz.~
where Ks = 2CZ~ 11 +
~ (Ai-i)(i-1) |~1
=
~ (i-1)A
t
.
D
'J'~--I
It is an old open problem to simplify the determinant in (6.1) for ~=~. Unfortunately, Lemma 5, used above to establish Corollary 6, seemingly
153
KRATTENTHALER does not apply
to t h i s c a s e .
7. G E N E R A T I N G FUNCTIONS FOR SKEW PLANE P A R T I T I O N S OF A GIVEN SHAPE. As c o r o l l a r i e s generating
functions
of Theorems
1 t o 4 we o b t a i n
of the various
kinds
expressions
for the
of skew plane partitions.
The g e n e r a t i n g f u n c t i o n f o r s k e w plane p a r t i t i o n s o f
COROLLARY 7.
the g i v e n s h a p e k i p is
(7.1)
qlA-FI det( q~ =
J
t= ,// [ks_S_p~+ t] !
J
PROOF. We o n l y have to combine (3.8), (3.9), and (6.1). COROLLARY
8.
The
Kenerating
function
for
o
reverse
skew
plane
p a r t i t i o n s o f s h a p e k/l= is
qI k-p
(7.2)
I
det ( q ~
i/ [ k . - s - ~ +
=
t] ! )
.
The g e n e r a t i n g f u n c t i o n for r e v e r s e plane p a r t i t i o n s o f s h a p e k is
(7.3)
qP/[dl]-'-[dp] ,
where IAl=p.
PROOF. For (7.2) combine (3.12), (3.13), and (6.6). (7.3) arises when combining (3.12), (3.13) for ~--0, and (6.12). [] Considering (3.10), (3.1t), (6.9); and (3.14), (3.15), (6.8); and (6.13); respectively, we obtain COROLLARY 9. The KeneratinK f u n c t i o n f o r c o l u m n - s t r i c t s k e w plane p a r t i t i o n s or c o l u m n - s t r i c t r e v e r s e s k e w plane p a r t i t i o n s , r e s p e c t i v e l y j o f s h a p e X/l= i s (7.4)
The
q
generating
I k-pl
function
deE( 1 / [ X s - s - p ~ +
for
column-strict
t] ! ) .
plane
partitions
c o l u m n - s t r i c t r e v e r s e plane p a r t i t i o n s , r e s p e c t i v e l y , o f s h a p e k is ,
~ e r e I k l = p and/~ ~. iX!. 13 I=1
154
or
KRATTENTHALER References
1. ANDREWS,G.E.: The t h e o r y A d d i s o n - W e s l e y 1976
of
partitions,
Reading,
Massachusetts:
2. FRANZBLAU,D.S., ZEILBERGER,D.: A bijective proof hook-lenKth formula, J. A l g o r i t h m u s 3, 317-343(1982)
of
the
3. FORLINGER,J., HOFBAUER,J.: q - C a t a l a n n u m b e r s , J. Combin. T h e o r y A 40, 248-264(1985) 4. GANSNER,E.: The Hillman-Grasal c o r r e s p o n d e n c e and the e n u m e r a t i o n of r e v e r s e plane parLitions, J. Combin. T h e o r y A 30~ 7t-89(1981) 5. GESSEL,I.~ VIENNOT,G.: Binomial determinants, book-lenKth formulae, Adv. in Math. 58, 300-321(1985)
paths,
6. HILLMAN,A.P., GRASSL,R.M.: R e v e r s e plane p a r t i t i o n s and book n u m b e r s , J. Combin. T h e o r y A 21, 216-221(1976)
and
tableaux
7. MACDONALD~I.G.: Symmetric functions and Hall polynomials, Oxford: Clarendon Press 1979 8. MACMAHON,P.A,: Combinal~ry analysis, Vol.2, London: Cambridge University Press 1915-1916; reprint Chelsea-New York 1960 9. REMMEL,J.B., WHITNEY,IL: A bijective proof of the f u n c t i o n f o r the n u m b e r o f r e v e r s e plane p a r t i t i o n s p a t h s , L i n e a r a n d Multilinear A l g e b r a 16, 75-91(1984)
KeneratinK v/a l a t t i c e
10. STANLEY,R.P.: Ordered structures and partitions, Mere. Amer. Math, Soc. 119(1972) 11. STANLEY,R.P.: Theory and applications of plane partitions, Part 1: Studies Appl. Math. 50, 167-188(1971); Part 2: Studies APDL Math. 50, 259-279(1971) 12. WATANABE,T., MOHANTY,S.G.: On an inclusion-exc]usion formula based on the reflection principle, Discrete Math. 64, 281-288(1987) 13. ZEILBERGER,D.: Andre's reflection proof Keneralized to ~he manycandidate ballot problem, Discrete Math. ~ , 325-326(1983)
I n s t i t u t ffir Mathematik U n i v e r s i t ~ t Wien Strudlhofgasse 4 A-1090 Vienna AUSTRIA
(Received September 12, 1988)
155
