Babson-Steingrímsson Statistics Are Indeed Mahonian (and Sometimes Even Euler-Mahonian)

Dominique FOATA^{1} and Doron ZEILBERGER^{2}

Abstract: Babson and Steingrímsson have recently introduced eight new permutation statistics, that they conjectured were all Mahonian (i.e. equi-distributed with the number of inversions). We prove their conjecture for the first four, and also prove that the first and the fourth are even Euler-Mahonian. We use two different, in fact, opposite, techniques. For three of them we give a computer-generated proof, using the Maple package ROTA, that implements the second author’s “Umbral Transfer Matrix Method.” For the fourth one a geometric permutation transformation is used that leads to a further refinement of this Euler-Mahonian distribution study.

1. Babson and Steingrímsson’s Notation

DOMINIQUE FOATA AND DORON ZEILBERGER

In [BaSt00] Babson and Steingrímsson introduced a convenient notation for “atomic” permutation statistics. Given a permutation w = x_{1}x_{2} … x_{n} of 1, 2, …, n they define, for example, (a bc)(w) to be the number of occurrences of the “pattern” a bc, i.e. the number of pairs of places 1 ≤ i < j < n such that x_{i} < x_{j} < x_{j+1}. Similarly, the pattern (b ca)(w) is that number of occurrences of x_{j+1} < x_{i} < x_{j}, and in general, for any permutation α, β, γ of a, b, c, the expression (α βγ)(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 (α, β, γ) are identical. The statistic (ab c)(w) is defined in the same way by looking at the occurrences (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 of descents, des w (i.e. the number of places 1 ≤ i < n such that x_{i} > x_{i+1}), and (ab)(w) denotes the number of rises, rise w (i.e. the number of places 1 ≤ i < n such that x_{i} < x_{i+1}).

1 Département de mathématique, Université Louis Pasteur, F-67084 Strasbourg, foata@math.u-stasbg.fr; http://cartan.u-stasbg.fr/~foata/.

Supported by the NSF, as a consultant on Zeilberger’s grant.

2 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA.

zeilberg@math.temple.edu; http://www.math.temple.edu/~zeilberg/.

Supported in part by the NSF.

Using these atomic objects, Babson and Steingrímsson noticed that the classical permutation statistics “inv” and “maj” may be written as (bc a) + (ca b) + (cb a) + (ba) and (a cb) + (b ca) + (c ba) + (ba), respectively. This inspired them 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 well-known (e.g. “inv” and “maj”), and some were new, but they could do themselves. Yet eight new “conjecturally Mahonian” statistics were left open. Here we do four of them. The other four should also be amenable to our methods.

2. Notations and Results

Recall the usual notations

(2.1) (a; q)_{n} := \{ \begin{matrix}1, & if n = 0; \\ (1 − a)(1 − aq) … (1 − aq^{n−1}), & if n ≥ 1; \end{matrix}
(2.2) (a; q)_{∞} := lim_{n}(a; q)_{n} = ∏_{n≥0}(1 − aq^{n}).

Also, let

(2.3)  [n]_{q} := \frac{1 − q^{n}}{1 − q} = (1 + q + ⋯ + q^{n−1});
(2.4)  [n]_{q}! := \frac{(q; q)_{n}}{(1 − q)^{n}} = [n]_{q} [n − 1]_{q} ⋯ [1]_{q}
= (1 + q + ⋯ + q^{n−1})(1 + q + ⋯ + q^{n−2}) ⋯ (1).

The sequence of polynomials ([n]_{q}!) (n ≥ 0) is said to be Mahonian. On the other hand, a statistic “stat” (actually, we should say a sequence (stat_{n}) (n ≥ 0) of statistics, where stat_{n} is defined on the symmetric group S_{n}) is said to be Mahonian, if for every n ≥ 0 we have

∑_{w∈S_{n}} q^{stat w} = [n]_{q}!

A sequence (A_{n}(t, q)) (n ≥ 0) of polynomials in two variables t and q, is said to be Euler-Mahonian, if one of the following equivalent conditions holds:

(1) For every n ≥ 0,

(2.5)  \frac{1}{(t; q)_{n+1}} A_{n}(t, q) = ∑_{s≥0} t^{s} ([s + 1]_{q})^{n}.

BABSON-STEINGRÍMSSON STATISTICS

(2) The exponential generating function for the fractions \frac{A_{n}(t, q)}{(t; q)_{n+1}} is given by:

(2.6)  ∑_{n≥0} \frac{u^{n}}{n!} \frac{A_{n}(t, q)}{(t; q)_{n+1}} = ∑_{s≥0} t^{s} exp(u [s + 1]_{q}).

(3) The sequence (A_{n}(t, q)) satisfies the recurrence relation:

(2.7) (1 − q) A_{n}(t, q) = (1 − tq^{n}) A_{n−1}(t, q) − q(1 − t) A_{n−1}(tq, q).

(4) Let A_{n}(t, q) = ∑_{s≥0} t^{s} A_{n,s}(q). Then the coefficients A_{n,s}(q) satisfy the recurrence:

(2.8)  A_{n,s}(q) = [s + 1]_{q} A_{n−1,s}(q) + q^{s}[n − s]_{q} A_{n−1,s−1}(q).

It is routine to prove that those four conditions are equivalent (see, e.g. [ClFo95, §§ 6,7] for a proof in a more general setting). Now a pair of statistics (stat_{1}, stat_{2}) defined on each symmetric group S_{n} (n ≥ 0) is said to be Euler-Mahonian, if for every n ≥ 0 we have

∑_{w∈S_{n}} t^{stat_{1} w}q^{stat_{2} w} = A_{n}(t, q).

The first values of the Euler-Mahonian polynomials are the following: A_{0}(t, q) = A_{1}(t, q) = 1; A_{2}(t, q) = 1 + tq; A_{3}(t, q) = 1 + t(2q + 2q^{2}) + t^{2}q^{3}; A_{4}(t, q) = 1 + t(3q + 5q^{2} + 3q^{3}) + t^{2}(3q^{3} + 5q^{4} + 3q^{5}) + t^{3}q^{6}; A_{5}(t, q) = 1 + t(4q + 9q^{2} + 9q^{3} + 4q^{4}) + t^{2}(6q^{3} + 16q^{4} + 22q^{5} + 16q^{6} + 6q^{7})

+ t^{3}(4q^{6} + 9q^{7} + 9q^{8} + 4q^{9}) + t^{4}q^{10}.

Our results are the following.

Theorem 1. The permutation statistic

S11 := (a cb) + 2(b ca) + (ba)

is Mahonian.

Theorem 2. The permutation statistic

S13 := (a cb) + 2(b ac) + (ab)

is Mahonian .

Theorem 3. Let S5 := (b ca) + (c ab) + (a bc) + (ab). Then, the pair (rise, S5) is Euler-Mahonian.

Theorem 4. Let S6 := (ba c) + (c ba) + (ba) + (ac b). Then, the pair (des, S6) is Euler-Mahonian.

Our Theorems 1, 2, and 4 are the three parts of Conjecture 8 of [BaSt00], while Theorem 3 is Conjecture 10 of [BaSt00]. In fact, our Theorem 4 is stronger, since in [BaSt00] S6 is only conjectured to be Mahonian, but we will prove that it is in fact Euler-Mahonian when associated with “des”.

Several pairs of statistics are known to be Euler-Mahonian, the pair (des, maj) being the Euler-Mahonian pair, par excellence, a result that goes back to Carlitz [Ca54], [Ca59], or even in an implicit form to MacMahon [Ma15, vol. 2, p. 211]. For proving that a given pair (stat_{1}, stat_{2}) is Euler-Mahonian, we can form the generating polynomial for S_{n} by the pair (stat_{1}, stat_{2}), say, B_{n}(t, q) and show that one of the conditions (1), (2),

(3) or (4) holds when A_{n}(t, q) is replaced by B_{n}(t, q). This is the approach we have adopted for proving the first three results, but we have done it in such a way that the calculation can be computer-implemented, as we now explain.

It turns out that, thanks to the second author’s recent theory of the “Umbral Transfer Matrix Method” [Ze00], 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.

Since Markovian Permutation Statistics are easily amenable to automatic treatment by ROTA, and S5, S11, and S13 happen to belong to that class (thanks to the consistent location of the ‘dash’), all we did, after writing PERCY, was to ‘plug them in’. PERCY can, actually, handle arbitrary Markovian Permutation Statistics. In particular, it can be used to prove, in a few nano-seconds, MacMahon’s classical result that “maj” is Mahonian. We believe that it can also discover and prove many new results in addition to those proved here.

However, ROTA is useless in the case of S6, since the location of the dash in S6 := (ac b) + (ba c) + (c ba) + (ba) is not consistent. 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}. Instead of the pair (des, maj) we will take another Euler-Mahonian pair (des, mak), where “mak” is a Mahonian statistic that was introduced in our previous paper [FoZe90]. In the Babson-Steingrímsson notation “mak” reads

(2.9)  mak := (a cb) + (cb a) + (ba) + (ca b),

wrongly designated by “makl” in [BaSt00]. We will make use of the Euler-Mahonian pair (des, mak), but prove the stronger Theorem 4′, where an involution of S_{n} is constructed that preverses the descent set and permutes two word statistics U and V we now define.

First, the descent bottom set of a permutation w = 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_{i−1} > x_{i}. Its cardinality is the number of descents of w, des w, so that

(2.11)  des w = # DESBOT 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

(2.12)  U_{y}(w) := (ca − b) |b = y w;
(2.13)  V_{y}(w) := (b − ac) |b = y w.

Thus, U_{y}(w) is the number of pairs 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 statistics U and V are then:

(2.14)  U(w) := U_{1}(w)U_{2}(w) … U_{n}(w);
(2.15)  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_{2}x_{1}. We shall introduce another involution s of S_{n}, called the rise-des-exchange, which exchanges the rises and the descents of a permutation (in a sense that will be explained in Section 6, but can be immediately visualized in Fig. 1) and keeps peaks and troughs in their original ordering. We can then consider the involution r s.

Theorem 4′. The involution r s of S_{n} has the following properties:

(a) DESBOT r s w = DESBOT w;

(b) (U, V) r s w = (V, U) w.

In Section 6 we will show how Theorem 4′ implies Theorem 4.

3. Markovian Permutation Statistics

The reduction of a sequence of n distinct integers w, denoted by red(w), is the permutation obtained by replacing the smallest member by 1, the second-smallest by 2, …, and the largest by n. For example, red(8 3 5 9 2) = 4 2 3 5 1.

Definition. 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_{n−1})) + h(x_{n−1}, x_{n}, n).

Definition: 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) = \{ \begin{matrix}f(j, i, n), & if j < i; \\ g(j, i, n), & if j > i; \end{matrix}

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.

¿From now on we, and the Maple package PERCY, will only consider Nice Markovian Permutation Statistics. We will denote them by [f, g, j, i, n]. For example, inv = [n − i, n − i, j, i, n], maj = [0, n − 1, j, i, n], des = [0, 1, j, i, n], rise = [1, 0, j, i, n], etc.

Given a permutation statistic F we are interested in the sequence of polynomials

gf(F)_{n}(q) := ∑_{w∈S_{n}} 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) := ∑_{w=x_{1}...x_{n}∈S_{n}} q^{F (w)}z^{x_{n}} (n ≥ 0)

that also keeps track of the last letter x_{n}. Now, using Rota operators (see [Ze00]), it is easy to express GF(F)_{n} in terms of GF(F)_{n−1}. Let w′ := x′_{1} ⋯ x′_{n−1} = red(x_{1} ⋯ x_{n−1}); then

GF(F)_{n}(q, z) := ∑_{i=1}^{n} z^{i} ∑_{{w∈S_{n} \atop x_{n}=i}} q^{F (w)}

= ∑_{i=1}^{n} z^{i}(∑_{j=1}^{i−1} ∑_{{w∈S_{n} \atop x_{n−1}=j, x_{n}=i}} q^{F (w)} + ∑_{j=i+1}^{n} ∑_{{w∈S_{n} \atop x_{n−1}=j, x_{n}=i}} q^{F (w)})

= ∑_{i=1}^{n} z^{i}(∑_{j=1}^{i−1} ∑_{{w∈S_{n} \atop x_{n−1}=j}}q^{F (w′)+f(j,i,n)} + ∑_{j=i+1}^{n} ∑_{{w∈S_{n} \atop x_{n−1}=j}}q^{F (w′)+g(j,i,n)})

= ∑_{j<i≤n}z^{i} ∑_{{w′∈S_{n−1} \atop x′_{n−1}=j}} q^{F (w′)+f(j,i,n)} + ∑_{i≤j≤n−1} z^{i} ∑_{{w′∈S_{n−1} \atop x′_{n−1}=j}} q^{F (w′)+g(j+1,i,n)}

= ∑_{j=1}^{n−1} ∑_{{w′∈S_{n−1} \atop x′_{n−1}=j}} (∑_{i=1}^{j} q^{g(j+1,i,n)}z^{i} + ∑_{i=j+1}^{n} q^{f(j,i,n)}z^{i})q^{F (w′)}.

Now for 1 ≤ j ≤ n − 1 introduce the umbra P,

(3.1)  P(z^{j}) := (∑_{i=1}^{j} q^{g(j+1,i,n)}z^{i} + ∑_{i=j+1}^{n} q^{f(j,i,n)}z^{i}),

and extend by linearity, so that P is defined on all polynomials of degree ≤ n − 1. In terms of P, we have the very simple recurrence:

GF(F)_{n}(q, z) = P(GF(F)_{n−1}(q, z)).

Of course, P itself may (and usually is) complicated, but we don’t care, we don’t even have to see it, since Maple can compute the umbra automatically, (all it has to do is to be able to sum geometric series symbolically, that it does very well), and store it for later. All the users have to enter is f and g, or if they prefer, they may use the notation of [BaSt00], and PERCY would convert it to the Markovian notation, and take it from there.

4. Proofs of Theorems 1, 2, 3

Proof of Theorem 1. Using PERCY (and ROTA) (or even by hand!) we get that the umbra P linking GF(S11)_{n−1}(q, z) to GF(S11)_{n}(q, z), as defined in (3.1), maps the polynomial a(z) onto

\frac{z^{n+1}a(1) − za(z)}{z − 1} + \frac{z(a(qz) − a(q^{2}))}{z − q}.

Hence b_{n}(z) := GF(S11)_{n}(q, z) satisfies the functional recurrence

b_{n}(z) = \frac{z^{n+1}b_{n−1}(1) − zb_{n−1}(z)}{z − 1} + \frac{z(b_{n−1}(qz) − b_{n−1}(q^{2}))}{z − q},

with the initial condition b_{1}(z) = z. But, the same is true of

c_{n}(z) := z \frac{(z^{n} − q^{n})}{(z − q)}[n − 1]_{q}! (check!).

Hence b_{n}(z) = c_{n}(z), and finally b_{n}(1) = c_{n}(1) = [n]_{q}!

Proof of Theorem 2. Using PERCY (and ROTA) (or even by hand!) we get that the umbra linking GF(S13)_{n−1}(q, z) to GF(S13)_{n}(q, z) is

a(z) ↦ \frac{z(a(zq) − a(1))}{qz − 1} + \frac{zqa(z) − q^{2n+1}z^{n+1}a(q^{−2})}{1 − zq^{2}}.

Hence d_{n}(z) := GF(S13)_{n}(q, z) satisfies the functional recurrence

d_{n}(z) = \frac{z(d_{n−1}(zq) − d_{n−1}(1))}{qz − 1} + \frac{zqd_{n−1}(z) − q^{2n+1}z^{n+1}d_{n−1}(q^{−2})}{1 − zq^{2}}.

with the initial condition d_{1}(z) = z. But, the same is true of

e_{n}(z) := z \frac{(1 − q^{n}z^{n})}{(1 − qz)}[n − 1]_{q}! (check!).

Hence d_{n}(z) = e_{n}(z), and finally d_{n}(1) = e_{n}(1) = [n]_{q}!

Proof of Theorem 3. PERCY can just as easily compute the Umbra for multi-statistics, when the generating function is the weight-enumerator of S_{n} according to the weight

weight(w) := z^{x_{n}} ∏_{j=1}^{r} q_{j}^{F_{j}(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) := ∑_{w∈S_{n}}t^{des w}q^{maj w}z^{x_{n}}, B_{n}(t, q; z) := ∑_{w∈S_{n}}t^{rise w}q^{S5 w}z^{x_{n}}.

PERCY, using ROTA, computes the following functional equations (that in fact, are simple enough to be derivable by humans):

(4.1) A_{n}(t, q; z) = \frac{z(1 − tq^{n−1})A_{n−1}(t, q; z) − z(z^{n} − tq^{n−1})A_{n−1}(t, q; 1)}{1 − z};

(4.2) B_{n}(t, q; z) = \frac{z(1 − tq^{n})B_{n−1}(t, q; z) − z(1 − tz^{n})B_{n−1}(t, q; q)}{z − q}.

We have to prove that B_{n}(t, q; 1) = A_{n}(t, q; 1) = A_{n}(t, q), the Euler-Mahonian polynomial, as defined in (2.5)-(2.8), as we already know that (des, maj) is Euler-Mahonian. By comparing the two functional recurrences, we get that B_{n}(t, q; z) = q^{−n}z^{n+1}A_{n}(tq, q; q/z), hence we have to prove that A_{n}(tq, q; q) = q^{n}A_{n}(t, q; 1) = A_{n}(t, q). By plugging t = tq, z = q into (4.1), and using the induction hypothesis, we get that

A_{n}(tq, q; q)

= \frac{q(1 − (tq)q^{n−1})A_{n−1}(tq, q; q) − q(q^{n} − (tq)q^{n−1})A_{n−1}(tq, q; 1)}{1 − q}

= \frac{q(1 − tq^{n})q^{n−1}A_{n−1}(t, q; 1) − q^{n+1}(1 − t)A_{n−1}(tq, q; 1)}{1 − q}

= q^{n} \frac{(1 − tq^{n})A_{n−1}(t, q) − q(1 − t)A_{n−1}(tq, q)}{1 − q}.

But, this equals q^{n}A_{n}(t, q) by (2.7).

The input and output files of PERCY, for all the above claimed statements, can be downloaded from

     http://www.math.temple.edu/~zeilberg/programs.html.

5. A Brief Description of PERCY

You must have MAPLE^{T M}. First go to Zeilberger’s homepage

            http://www.math.temple.edu/~zeilberg/,

click on programs, and download PERCY and ROTA. Make sure that they reside in the same directory in your computer. Then go into Maple (by typing: maple , followed by ENTER ), and type read PERCY; . Then follow the on-line instructions. In particular, to get a list of all procedures, type: Ezra(); (not to be confused with ezra(); and ezra1();, that refer to ROTA; for information about ROTA, see [Ze00]).

BSE(bitui,j,i,n) inputs an expression, bitui in the notation of [BaSt00], and three variables j,i,n and returns the Nice Markovian Statistic in the [f, g, j, i, n] notation. Given a Markovian permuta-

tion statistic MPS=[f,g,j,i,n], PermPreUmbra(MPS,q,z); and PermUm-

bra(MPS,q,z); find the pre-umbra and umbra respectively connecting the weight-enumerator of S_{n−1} to that of S_{n}. For example PermUmbra([0,n-

1,j,i,n],q,z) does it for maj.

Given a Markovian permutation statistic, MPS, a variable q, and a positive integer L, GF(MPS,q,L); finds the first L terms in the weightenumeration sequence, fast, using the umbra (by calling ROTA). The skeptic can check the answer (for small L!), by also doing GFdirect(MPS,q,L);, which computes by direct (super-exponentially slow) enumeration. Per-

mUmbraMS(MPSs,qs,z) and GFMS(MPSs,qs,L) are the analogous functions

for multi-statistics, where MPSs is a list of Markovian permutation statistics and qs is a list of corresponding variables. For example, to get the first 10 terms in the sequence of the Euler-Mahonian polynomials,

type GFMS([[0,n-1,j,i,n],[0,1,j,i,n]],[q,t],10); . For more de-

tails, download PERCY and use the on-line help.

6. Proof of Theorem 4′

The reverse image r was redefined at the end of Section 2. The definition of the involution s, which is now given, is based on the peaktrough factorization of a permutation. By peak of the permutation w = x_{1}x_{2} ⋯ x_{n} we mean a letter x_{j} such that 1 ≤ j ≤ n and x_{j−1} < x_{j}, x_{j} > x_{j+1}. [By convention, x_{0} = x_{n+1} := 0.] By trough we mean a letter x_{j} such that 2 ≤ j ≤ n − 1 and x_{j−1} > x_{j}, x_{j} < x_{j+1}. Accordingly, each permutation has k troughs and (k + 1) peaks for some k ≥ 0. By double descent we mean a letter x_{j} such that 2 ≤ j ≤ n and x_{j−1} > x_{j} > x_{j+1}. By double rise we mean a letter x_{j} such that 1 ≤ j ≤ n − 1 and x_{j−1} < x_{j} < x_{j+1}.

In the following p and t will designate letters which are peaks and troughs, respectively, while d, h, will designate words all letters of which are double descents, double rises, respectively.

Each permutation w has a unique factorization, called its peak-trough factorization w = h_{1}p_{1}d_{1}t_{1} … h_{k−1}p_{k−1}d_{k−1}t_{k−1} h_{k}p_{k}d_{k}, having the following properties:

(1) k ≥ 1;

(2) the p_{i}’s are the peaks and the t_{i}’s the troughs of the permutation;

(3) for each i the symbols h_{i}, d_{i} are words, possibly empty, all letters of which are double rises, double rises, respectively.

It will be convenient to put t_{0} = t_{k} := 0. The set of all the letters in the juxtaposition product d_{1}t_{1} … d_{k−1}t_{k−1}d_{k}, i.e. the set of all the double descents and troughs of the permutation w, is the descent bottom set, DESBOT w, of w introduced in Section 2 (see (2.11)).

Definition of the involution s. Let y be a double rise of w, so that y is a letter of a factor h_{j} for some j (1 ≤ j ≤ k). Define φ_{w}(y) to be the least integer i such that j ≤ i ≤ k and p_{i} > y > t_{i}.

Define d′_{i} to be the decreasing word of all double rises y in w such that φ_{w}(y) = i. If φ_{w}(y) ≠ i for every double rise y of w, let d′_{i} be the empty word.

Let y be a double descent of w, so that y is a letter of a factor d_{j} for some j (1 ≤ j ≤ k) and p_{j} > y > t_{j}. Define φ_{w}(y) to be the greatest integer i such that 1 ≤ i ≤ j and t_{i−1} < y < p_{i}.

Define h′_{i} to be the increasing word of all double descents y in w such that φ_{w}(y) = i. If φ_{w}(y) ≠ i for every double descent y of w, let h′_{i} be the empty word.

Then, let

(6.1)  s w := h′_{1}p_{1}d′_{1}t_{1} … h′_{k−1}p_{k−1}d′_{k−1}t_{k−1} h′_{k}p_{k}d′_{k}.

The construction is illustrated in Fig. 1. To obtain the graph of s w we have to move the double rises to the right until they hit the first decreasing segment p_{i} > t_{i}. There is necessarily one since, by assumption, t_{k} = 0. Likewise, we move the double descents to the left until they reach the first increasing segment t_{i−1} < p_{i}, which exists since t_{0} = 0 by convention.

In the example we start with the permutation

w = 10, 11 ∧ , 2 ∨, 4, 5, 9 ∧, 6 ∨, 12, 14, 15 ∧ , 7, 3, 1 ∨, 8, 13 ∧

and we obtain the permutation

s w = 11 ∧ , 10, 2 ∨, 3, 9 ∧, 6 ∨, 7, 15 ∧ , 14, 12, 5, 4, 1 ∨, 13 ∧ , 8,

where the peaks (resp. the troughs) are materialized by “∧” (resp. “∨”)

Let RISE w (resp. DES w, resp. TROUGH w) be the set of of all the double rises (resp. the double descents, resp. the troughs) of w, so that DESBOT w = DES w ∪ TROUGH w.

[figure: w; 10; 11; 2; 4; 5; 9; 6; 12; 14; 15; 7; 3; 1; 8; 13]

[figure: s w; 10; 11; 2; 4; 5; 9; 6; 12; 14; 15; 7; 3; 1; 8; 13]

[figure: r s w; 10; 11; 2; 4; 5; 9; 6; 12; 14; 15; 7; 3; 1; 8; 13]

Fig. 1 Lemma 6.1. The operation s is an involution. Moreover,

(a) DES s w = RISE w, RISE s w = DES w and TROUGH s w = TROUGH w;

(b) (U, V) s w = (U, V) w.

Proof. When passing from w to s w the subword p_{1}t_{1} … p_{k−1}t_{k−1} p_{k} made of the successive peaks and troughs remains alike. The double rises (resp. double descents) of w are transformed into double descents (resp. double rises) of s w.

By considering the graphs of the permutations w and s w it is clear that we recover w by applying s to s w itself.

Finally, if y is a double rise of w between t_{j−1} and p_{j}, we have defined φ_{w}(y) as the least integer i such that j ≤ i ≤ k and p_{i} > y > t_{i}. Accordingly, the number of pairs p_{l} > t_{l} to the left of y in both w and s w is the same and the number of pairs t_{l−1} < p_{l} to the right of y is also the same in both w and s w. Accordingly,

U_{y}(w) := (ca b) |b = y w

= ∑_{1≤l≤j−1} χ(p_{l} > y > t_{l})

= ∑_{1≤l≤i−1} χ(p_{l} > y > t_{l})

= (ca b) |b = y s w = U_{y}(s w).

In the same manner,

V_{y}(w) := (b ac) |b = y w

= ∑_{j+1≤l≤k−1} χ(t_{l} < y < p_{l+1})

= ∑_{i≤l≤k−1} χ(t_{l} < y < p_{l+1})

= (b ac) |b = y s w = V_{y}(s w).

There is an analogous proof when y is a double descent of w.

Lemma 6.2. The reverse image r has the following properties:

(a) DES r w = RISE w, RISE r w = DES w and TROUGH r w = TROUGH w;

(b) (U, V) r w = (V, U) w.

Proof. Property (a) is obvious. On the other hand, when going from w to r w each decrease ca to the left of y in w will become an increase ac to the right of y in r w, so that (b) holds.

It follows from Lemmas 6.1 and 6.2 that DES r s w = RISE s w = DES w and TROUGH r s w = TROUGH s w = TROUGH w, so that DESBOT r s w = DESBOT w. Finally, (U, V) s r w = (U, V) r w = (V, U) w. This completes the proof of Theorem 4′.

In the example of Fig. 1 we have

w = 10, 11 ∧ , 2 ∨, 4, 5, 9 ∧, 6 ∨, 12, 14, 15 ∧ , 7, 3, 1 ∨, 8, 13 ∧ ,
s w = 11 ∧ , 10, 2 ∨, 3, 9 ∧, 6 ∨, 7, 15 ∧ , 14, 12, 5, 4, 1 ∨, 13 ∧ , 8,
r s w = 8, 13 ∧ , 1 ∨, 4, 5, 12, 14, 15 ∧ , 7, 6 ∨, 9 ∧, 3, 2 ∨, 10, 11 ∧ ,

and we can verify that:

( \begin{matrix}y \\ U_{y}(r s w) \\ V_{y}(r s w) \end{matrix} )=( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 2 & 2 & 2 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 2 & 3 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \end{matrix} )=( \begin{matrix}y \\ V_{y}(w) \\ U_{y}(w) \end{matrix} ).

7. Proof of Theorem 4 and Consequences

Let Σ DESBOT 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.

Lemma 7.1. For each permutation w we have:

(7.1)  Σ DESBOT w = ((a cb) + (cb a) + (ba)) w.

Proof. Let x_{i} ∈ DESBOT w, so that x_{i−1} > x_{i} and (ba) |b = x_{i} w = 1. Then (a cb) |b = x_{i} w counts the letters x_{j}, less than x_{i}, which are to the left of x_{i}, while (cb a) |b = x_{i} w counts the letters x_{j}, less than x_{i}, to the right of x_{i}. Hence, ((a cb) + (cb a) + (ba)) |b = x_{i} w is equal to x_{i}.

Next, introduce the other classical operation of the dihedral group, the complement to (n + 1), denoted by c, that maps each permutation w = x_{1}x_{2} … x_{n} onto c w := (n + 1 − x_{1})(n + 1 − x_{2}) ⋯ (n + 1 − x_{n}). It is straightforward to verify the relations: (ba c) r c = (a cb), (c ba) r c = (cb a), (ac b) r c = (b ac), (ba) r c = (ba).

As stated in Theorem 4, the statistic S6 is defined by

S6 := (ba c) + (c ba) + (ba) + (ac b),

so that the statistic S6 r c reads

S6 r c := (a cb) + (cb a) + (ba) + (b ac),

while the “mak” statistic defined in (2.9) is

mak = (a cb) + (cb a) + (ba) + (ca b).

Taking Lemma 7.1 into account, as well as the definitions of the word statistics U, V given in (2.12)–(2.15), we get the expressions:

mak, w = Σ DESBOT w + U_{1}(w) + ⋯ + U_{n}(w);
S6 r c w = Σ DESBOT w + V_{1}(w) + ⋯ + V_{n}(w).

Now, remember that des w is the number of elements in DESBOT w. Therefore, Theorem 4′ implies the following corollary.

Corollary 7.2. The involution r s is an involution of S_{n} having the property:

(des, mak) w = (des, S6 r c) rs w.

But (des, mak) is Euler-Mahonian, as proved in [FoZe90]. Therefore, the pair (des, S6 r c) is Euler-Mahonian, as well as (des, S6), since we always have des r c w = des w. Hence Theorem 4 is proved.

References

[BaSt00] Eric Babson and Einar Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Loth.

Comb. [http://mat.univie.ac.at/∼slc/] 44 , 2000, B44b, 18 pp.

[Ca54] Leo Carlitz, q-Bernoulli and Eulerian numbers,Trans. Amer. Math. Soc., 76, 1954, 332–350.

[Ca59] Leo Carlitz, Eulerian numbers and polynomials, Math. Magazine, 33, 1959, 247–260.

[ClFo95] Robert J. Clarke and Dominique Foata, Eulerian Calculus, II: An Extension of Han’s Fundamental Transformation, Europ. J. Combinatorics, 16, 1995, 221–252.

[FoZe90] Dominique Foata and Doron Zeilberger, Denert’s Permutation Statistic Is Indeed Euler-Mahonian, Studies in Appl. Math., 83, 1990, 31–59.

[Ma15] Percy Alexander MacMahon, Combinatory Analysis, vol. 1 and 2. Cambridge, Cambridge Univ. Press, 1915 (Reprinted by Chelsea, New York, 1955).

[Ze00] Doron Zeilberger, The Umbral Transfer Matrix Method: I. Foundations, J. Comb. Theory, ser. A [Rota Memorial Issue], 91, 2000, 451–463.