Eulerian Calculus: a Technology for Computer Algebra and Combinatorics
Dominique Foata
Département de mathématique, Université Louis Pasteur (France)
Algorithms Seminar
May 21, 2001
[summary by Dominique GouyouBeauchamps]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
Babson and Steingrímsson have introduced pairs of permutation
statistics that they conjectured were all EulerMahonian, i.e.,
equidistributed with the pair (des,maj) where des is the
number of descents and maj is the major index. How to prove their
conjecture? We use the socalled ``Umbral Transfer Matrix Method''
implemented by Zeilberger and specific combinatorial constructions
leading to new transformations on the symmetric group. Details may be
found in the recent work of D. Foata and D. Zeilberger [2].
1 Introduction
We use the BabsonSteingrímsson notation [1] for
``atomic'' permutation statistics. Given a permutation w=x_{1}x_{2}...
x_{n} of 1, 2, ..., n they denote (abc)(w) the number of
occurences of the pattern abc, i.e., the number of pairs of places
1£ i<j<n such that x_{i}<x_{j}<x_{j+1}. Similary, the pattern
(bca)(w) is the number of ocurrences of x_{j+1}<x_{i}<x_{j}, and in
general, for any permutation a, b, g of a, b,
c, the expression (abg)(w) is the number of pairs
(i,j), 1£ i<j<n, such that the orderings of the two triples
(x_{i},x_{j},x_{j+1}) and a,b,g are identical. The
statistic (abc) is defined in the same way by looking at the
occurences (x_{i},x_{i+1},x_{j}) such that i+1<j and
x_{i}<x_{i+1}<x_{j}. Of course, (ba)(w) denotes the number des w
of descents of w (i.e., the number of places 1£ i<n
such that x_{i}>x_{i+1}) and (ab)(w) denotes the number rise w of
rises of w (i.e., the number of places 1£ i<n such that
x_{i}<x_{i+1}).
The classical permutation statistics inv and maj may be
written as (bca)+(cab)+(cba)+(ba) and
(acb)+(bca)+(cba)+(ba), respectively. This inspired Babson and
Steingrímsson to perform a computer search for all statistics
that could be thus written, and look for those that appear to be
Mahonian. They came up with a list of 18. Some of them turned out to
be wellknown, and some were new. Yet eight new conjecturally Mahonian
statistics were left open. Here we prove four of them.
2 Notations
Recall the usual notations

(a;q)_{n} = 
ì
í
î 
1 
if n=0, 
(1a )(1aq)... (1aq^{n1}) 
if n³ 1, 





(a;q)_{¥}= 

(a;q)_{n}= 

(1aq^{n}), 



[n]_{q} = 

= 

q^{i},
[n]_{q}! = 

= 

[i]_{q}. 


A statistic stat on the symmetric group S_{n} is said to be
Mahonian, if for every n³ 0 we have
A sequence (A_{n}(t,q))_{n³ 0} of polynomials in two
variables t and q, is said to be EulerMahonian, if one of
the following equivalent conditions holds:

For every n³ 0,

A_{n}(t,q) = 

t^{s}([s+1]_{q})^{n}. 
 The exponential generating function for the fractions A_{n}(t,q)/(t;q)_{n+1} is given by
 The sequence (A_{n}(t,q)) satisfies the recurrence
relation:
(1
q)
A_{n}(
t,
q)=(1
tq^{n})
A_{n1}(
t,
q)
q(1
t)
A_{n1}(
tq,
q).
(1)
 Let A_{n}(t,q)=å_{s³ 0}t^{s}A_{n,s}(q). Then the coefficients
A_{n,s}(q) satisfy the recurrence:
A_{n,s}(q) = [s+1]_{q}A_{n1,s}(q)+q^{s}[ns]_{q}A_{n1,s1}(q).
Now a pair of statistics (stat_{1},stat_{2}) defined on each
symmetric group S_{n} (n³ 0) is said to be EulerMahonian, if for every n³ 0 we have

t^{stat1w}q^{stat2w} = A_{n}(t,q). 
3 Results
Our results are the following:
Theorem 1
The permutation statistic S11=(acb)+2(bca)+(ba) is Mahonian.
Theorem 2
The permutation statistic S13=(acb)+2(bac)+(ab) is Mahonian.
Theorem 3
Let S5=(bca)+(cba)+(abc)+(ab). Then, the pair (rise,S5)
is EulerMahonian.
Theorem 4
Let S6=(bac)+(cba)+(acb)+(ba). Then, the pair (des,S6)
is EulerMahonian.
Our Theorems 1, 2, and 4 are the three parts of Conjecture 8 of
[1], while Theorem 3 is Conjecture 10 of [1]. It
turns out that, thanks to Zeilberger's recent theory of the Umbral Transfer Matrix Method [4], the proofs of
the first three theorems are completely automatic, using the general
Maple package ROTA, together with a new interfacing
package PERCY that computes the appropriate Rota operators
for what we will call Markovian Permutation Statistics.
Figure 1: rs(10,11,2,4,5,9,6,12,14,15,7,3,1,8,13) =
(8,13,1,4,5,12,14,15,7,6,9,3,2,10,11).
However, ROTA is useless in the case of S6. So proving Theorem
4 still requires the traditional combinatorial method:
construct a bijection w® w' of S_{n} onto itself which has the
property that
(des,S6) w' = (des,maj) w
holds for every wÎS_{n}.
4 Proof of Theorem 4
Instead of the pair (des,maj) we will take another
EulerMahonian pair (des,mak), where mak is a Mahonian
statistic that was introduced by Foata and Zeilberger in
[3]. In the BabsonSteingrímsson notation mak
reads
mak := (acb)+(cba)+(ba)+(cab).
First, the descent bottom of a permutation x_{1}x_{2}... x_{n}
is defined to be the set desbot w of all the x_{i}'s such that
2£ i£ n and x_{i1}>x_{i}. Its cardinality is the number
des w of descents of w.
Next, the word statistics U and V are introduced as follows. Let
y=x_{i} be a letter of the permutation w=x_{1}x_{2}... x_{n}. Define
U_{y}(w) = 
(cab) 
 
_{b=y}w;
V_{y}(w) = 
(bac) 
 
_{b=y}w. 
Thus, U_{y}(w) is the number of adjacent letters x_{j}x_{j+1} to the left
of y=x_{i} such that x_{j}>x_{i}>x_{j+1}. The word statitics U and V
are then:
U(w)=U_{1}(w)U_{2}(w)... U_{n}(w);
V(w)=V_{1}(w)V_{2}(w)... V_{n}(w).
Now, recall the traditional reverse image r, which is an
involution that maps each permutation w=x_{1}x_{2}... x_{n} onto r
w=x_{n}x_{n1}... x_{1}. We shall introduce another involution s
of S_{n}, called the risedesexchange, which exchanges the
rises and the descents of a permutation and keeps peaks and troughs in
their original ordering. The involution s is not explained here,
but can be immediately visualized in Fig. 1.
Proposition 1
The involution rs of S_{n} has the following properties:

desbotrs w = desbot w,
 (U,V) rs w = (V,U) w.
Let Sdesbot w be the sum of all the letters x_{i} of the
permutation w=x_{1}x_{2}... x_{n} which belong to the descent bottom
set desbot w.
Proposition 2
For each permutation w we have:
Sdesbot w = 
( 
(acb)+(cba)+(ba) 
) 
w. 
Next, we introduce the complement to (n+1), denoted by c,
that maps each permutation w=x_{1}x_{2}... x_{n} onto
c w = (n+1x_{1})(n+1x_{2})... (n+1x_{n}). Thus the
statistic S6 rc reads
S6 rc = (acb)+(cba)+(ba)+(bca) .
Taking Proposition 2 into account, we get the expressions:
mak w = Sdesbot w+U_{1}(w)+... +U_{n}(w),
S6 rc = Sdesbot w+V_{1}(w)+... +V_{n}(w).
Therefore, Proposition 1 implies the following corollary.
Corollary 1
The involution rs is an involution of S_{n} having the property:
(des,mak) w = (des,S6 rc) rs w.
But (des,mak) is EulerMahonian, as proved in
[3]. Therefore, the pair (des, S6 rc) is
EulerMahonian, as well as (des,S6), since we always have
desrc w = des w. Hence Theorem
4 is proved.
5 Markovian Permutation Statistics
The reduction of a sequence w of n distinct integers,
denoted by red(w), is the permutation obtained by replacing the
smallest member by 1, the secondsmallest by 2, ..., and the
largest by n. For example red(5 8 3 7 4) = 3 5 1 4 2.
A permutation statistic F:S_{n}®Z is said to be
Markovian, if there exists a function h(j,i,n) such that
F(x_{1}... x_{n}) = F 
( 
red(x_{1}... x_{n1}) 
) 
+h(x_{n1},x_{n},n). 
A Markovian permutation statistic F:S_{n}®Z is said to be
nice Markovian if the above h(j,i,n) can be written as
h(j,i,n) = 
ì
í
î 
f(j,i,n) 
if j<i, 
g(j,i,n) 
if j>i, 

where f and g are affine linear functions of their arguments,
i.e., can be written as ai+bj+cn+d, for some integers a, b, c, d.
We, and the Maple package PERCY, will only consider
nice Markovian statistics. We will denote them by [f,g,j,i,n]. For
exemple, inv = [ni,ni,j,i,n], maj = [0,n1,j,i,n],
des = [0,1,j,i,n], rise = [1,0,j,i,n].
Given a permutation statistic F we are interested in the sequence of polynomials
gf 
(F)_{n}(q) = 

q^{F(w)} (n³ 0). 
However, in order to take advantage of Markovity, we need to consider the
more refined
GF 
(F)_{n}(q,z) = 

q^{F(w)}
z^{xn} (n³ 0) 
that also keeps track of the last letter x_{n}. Now, by using Rota operators
[4], it is easy to express GF(F)_{n} in terms of GF(F)_{n1}.
Let w'=x'_{1}... x'_{n1}=red(x_{1}... x_{n1}); then
GF(F)_{n}(q,z) 
= 


= 



æ
ç
ç
è 

q^{g(j+1,i,n)}z^{i}+ 

q^{f(j,i,n)}z^{i} 
ö
÷
÷
ø 
q^{F(w')}. 

Now for i£ j£ n1 we introduce the umbra P,
P(z^{j}) = 
æ
ç
ç
è 

q^{g(j+1,i,n)}z^{i}+ 

q^{f(j,i,n)}z^{i} 
ö
÷
÷
ø 
, 
and we extend by linearity, so that P is
defined on all polynomials of degree less than or equal to n1. In
terms of P, we have the very simple recurrence:
GF(F)_{n}(q,z) = P 
( 
GF(F)_{n1}(q,z) 
) 
. 
Maple can compute the umbra automatically. All the users have
to enter is f and g, and PERCY would convert it to the
Markovian notation.
6 Proof of Theorem 1
Using PERCY and ROTA we get that the umbra P linking
GF(S11)_{n1}(q,z) to GF(S11)_{n}(q,z) maps the polynomial
a(z) onto
Hence b_{n}(z)=GF(S11)_{n}(q,z) satisfies the functional recurrence
b_{n}(z) = 
z^{n+1}b_{n1}(1)zb_{n1}(z) 

z1 

+ 
z 
( 
b_{n1}(qz)
b_{n1}(q^{2}) 
) 


zq 

, 
with the initial condition b_{1}(z)=z. But if we guess (and if we
check) that the sequence
satisfies the same recurrence,
we obtain that b_{n}(z)=c_{n}(z), and finally that b_{n}(1)=c_{n}(1)=[n]_{q}!
7 Proof of Theorem 2
Using PERCY and ROTA we get that the umbra P linking
GF(S13)_{n1}(q,z) to GF(S13)_{n}(q,z) maps the polynomial
a(z) onto

+ 
zqa(z)q^{2n+1}z^{n+1}a(q^{2}) 

1zq^{2} 

. 
Hence d_{n}(z)=GF(S13)_{n}(q,z) satisfies the functional recurrence
d_{n}(z) = 
z 
( 
d_{n1}(zq)d_{n1}(1) 
) 


qz1 

+ 
zqd_{n1}(z)
q^{2n+1}z^{n+1}d_{n1}(q^{2}) 

1zq^{2} 

, 
with the initial condition d_{1}(z)=z. But if we guess (and if we
check) that the sequence
satisfies the same recurrence,
we obtain that d_{n}(z)=e_{n}(z), and finally that d_{n}(1)=e_{n}(1)=[n]_{q}!.
8 Proof of Theorem 3
PERCY can compute the Umbra multistatistics, when the generating
function is the weightenumerator of S_{n} according to the weight
weight 
(w) = z^{xn} 

q_{j}^{Fj(w)}, 
where w=x_{1}... x_{n} and F_{1}(w), ..., F_{r}(w) are several nice
Markovian permutation statistics. Define
A_{n}(t,q;z)= 

t^{des w}q^{maj w}z^{xn},
B_{n}(t,q;z)= 

t^{rise w}q^{S5w}z^{xn}. 
PERCY and ROTA compute the following functional recurrences

A_{n}(t,q;z) 
= 

z(1tq^{n1})A_{n1}(t,q;z)z(z^{n}tq^{n1})A_{n1}
(t,q;1) 

1z 

;


(2) 

B_{n}(t,q;z)= 
z(1tq^{n})B_{n1}(t,q;z)z(1tz^{n})B_{n1}(t,q;q) 

zq 

. 
By comparing the two functional recurrences, we guess and we verify that
B_{n}(t,q;z)=q^{n}z^{n+1}A_{n}(tq,q;q/z).
Hence
B_{n}(t,q;1)=q^{n}A_{n}(tq,q;q). By plugging t=tq, z=q into
Eq. (2), we get that
A_{n}(tq,q;q) = q^{n} 
(1tq^{n})A_{n1}(t,q;1)q(1t)A_{n1}(tq,q;1) 

1q 

. 
But, this equals q^{n}A_{n}(t,q) by Eq. (1).
And we have proved that B_{n}(t,q;1)=A_{n}(t,q;1)=A_{n}(t,q).
The input and output files of PERCY can be downloaded from
http://www.math.temple.edu/~zeilberg/programs.html
.
References
 [1]

Babson (Eric) and Steingrímsson (Einar). 
Generalized permutation patterns and a classification of the
Mahonian statistics. Séminaire Lotharingien de Combinatoire,
vol. 44, n°B44b, 2000. 
18 pages. Available from
http://www.mat.univie.ac.at/~slc/
.
 [2]

Foata (D.) and Zeilberger (D.). 
BabsonSteingrímsson statistics are indeed Mahonian (and
sometimes even EulerMahonian). 
To appear in Advances in Applied Mathematics.
 [3]

Foata (Dominique) and Zeilberger (Doron). 
Denert's permutation statistic is indeed EulerMahonian. Studies in Applied Mathematics, vol. 83, n°1, 1990,
pp. 3159.
 [4]

Zeilberger (Doron). 
The umbral transfermatrix method. I. Foundations. Journal
of Combinatorial Theory. Series A, vol. 91, n°12, 2000,
pp. 451463. 
In memory of GianCarlo Rota.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.