Two Oiseau Decompositions of Permutations and their Application to Eulerian Calculus

Dominique Foata and Arthur Randrianarivony

Abstract: Two transformations are constructed that map the permutation group onto a well-defined subset of a partially commutative monoid generated by the so-called oiseaux. Those transformations are then used to show that some bivariable statistics introduced by Babson and Steingrímsson are Euler-Mahonian.

1. Introduction

Everybody knows that each permutation of a finite set can be uniquely expressed as a product of disjoint cycles, except for changes in the order of the factors, so that the rule of commutation is the property of being disjoint. In what follows the cycles will be replaced by the so-called oiseaux, and those oiseaux, although they may also be regarded as disjoint, are restricted to commute according to another rule.

By oiseau it is meant a word, whose letters are distinct nonnegative integers, of the form pdth, where p and t are single letters, d is a (strictly) decreasing (possibly empty) word and h a (strictly) increasing (possibly empty) word; it is further assumed that p (resp. t) is the greatest (resp. the smallest) letter in pdth. By convention, the letter p could also be equal to ∞. The letter “p” stands for peak, the letter “d” for double-descent, the letter “t” for trough and “h” for double-rise, or hill.

Remark. As shown in Fig. 1 an oiseau looks like a bird seen from some distance, whose left wing is higher than the right one. The terminology was suggested by Gérard Duchamp [Du04], who has used those oiseaux as particular classes of descents occurring in the Dynkin Lie projector. In this example p = 16 is the peak of the oiseau, d = 4 is the double-descent factor, t = 2 is the trough, h = 6, 10, 14 is the double-rise factor.

Take the set of all the oiseaux as an alphabet A, supposed to be totally ordered by the lexicographic order, denoted by “≤,” induced by the usual order on the integers. As an element of alphabet A, each

DOMINIQUE FOATA AND ARTHUR RANDRIANARIVONY

[figure: 16; •; 4; •; 2; •; 6; •; 10; •; 14; •] Fig. 1

oiseau will be written (pdth) with parentheses. Let (pdth), (p′d′t′h′) be two distinct oiseaux; we say that (pdth) is below (p′d′t′h′) and write (pdth) ≪ (p′d′t′h′), if and only if every letter in the word pdth is less than every letter in p′d′t′h′. We also say that (p′d′t′h′) is above (pdth) and write (p′d′t′h′) ≫ (pdth). Two oiseaux are said to commute if and only if one is below the other. One of the goals of this paper is to show that each permutation can be written as a juxtaposition product of oiseaux submitted to the previous commutation rule. As a matter of fact, two transformations d and D will be given that map permutations onto such juxtaposition products.

For instance, consider the following permutation

σ = 18 ∧ , 3 , 1 ∨, 16 ∧ , 4 , 2 ∨, 6, 9 ∧, 5 ∨, 7, 10, 11 ∧ , 8 ∨, 13 ∧ , 12 ∨, 14, 17 ∧ , 15 ∨, 19,

where the peaks (resp. the troughs) are materialized by “∧” (resp. “∨”) and the double-rises (resp. the double-descents) are written in boldface (resp. in italic). Under the first transformation d the permutation is mapped onto an oiseau-word v, i.e., a word whose letters are oiseaux of the form (p_{0}d_{0}t_{0}h_{0}) … (p_{r}d_{r}t_{r}h_{r}):

v = (∞, 0, 19)(18 ∧ , 3 , 1 ∨)(16 ∧ , 4 , 2 ∨, 6, 10, 14)(9 ∧, 5 ∨, 7)(11 ∧ , 8 ∨)(13 ∧ , 12 ∨)(17 ∧ , 15 ∨).

Using the commutation rule on oiseaux, this juxtaposition product can be rewritten as

v′ = (∞, 0, 19)(18 ∧ , 3 , 1 ∨)(16 ∧ , 4 , 2 ∨, 6, 10, 14)(17 ∧ , 15 ∨)(13 ∧ , 12 ∨)(9 ∧, 5 ∨, 7)(11 ∧ , 8 ∨).

Finally, the permutation σ′ that is sent over v′ under the second transformation D reads:

σ′ = 19 ∧ , 1 ∨, 18 ∧ , 3 , 2 ∨, 6, 10, 14, 16 ∧ , 15 ∨, 17 ∧ , 12 ∨, 13 ∧ , 5 ∨, 7, 9 ∧ , 8 ∨, 11 ∧ , 4 .

OISEAU DECOMPOSITIONS OF PERMUTATIONS

Notice that the nonzero troughs in the permutations σ, σ′ and the words v, v′ are the same: 1, 2, 5, 8, 12, 15; as well as the double-descents (written in italic): 3, 4. As seen in the following theorem, the transformations d, D and also the commutation rule on oiseaux preserve the set of all the nonzero troughs and double-descents.

Let σ = x_{1}x_{2} … x_{n} be a permutation of 1, 2, …, n. Following Babson-Steingrímsson [BaSt01], (b ca)σ designates the number of triples (i, j, k) such that 1 ≤ i < j < k = j + 1 ≤ n and x_{j} > x_{i} > x_{k}. When the parentheses are removed from an oiseau-word, we get another word, say \overline{v}, whose letters are nonnegative integers. It then makes sense to define (b ca)v := (b ca)\overline{v}. The main result of the paper can be stated as follows.

Theorem 1.1. For each positive integer n there exist two sets B_{n}^{min} and B_{n}^{max} of oiseau-words having the following properties:

(i) the transformation d is a bijection of the permutation group S_{n} onto B_{n}^{min} with the property

(b ca)σ = (b ca)d σ;

(ii) there is a bijection θ of B_{n}^{min} onto B_{n}^{max} such that

(b ca)v = (b ca)θ(v);

(iii) the transformation D is a bijection of S_{n} onto B_{n}^{max} with the property

(b ca)σ = (b ca)D σ + n − L σ − des σ,

where L σ is the rightmost letter of σ and des σ the usual number of descents of the permutation;

(iv) the bijections d, θ, D preserve the set of the nonzero troughs and double-descents.

Going back to the previous numerical example we can verify that in σ the letter 3 is to the left of 16, 4, 2; 6 is to the left of 9, 5; the letters 9, 10 are on the left of 11, 8; 16 is on the left of 17, 15; so that (b ca)σ = 5. Also (b ca)v = (b ca)v′ = 5. However (b ca)σ′ = 12, L σ′ = 4, des σ′ = 8 and n = 19. As v′ = D σ′, we verify that

12 = (b ca)σ′ = (b ca)D σ′ + n − L σ′ − des σ′ = 5 + 19 − 4 − 8,

so that (iii) holds.

The composition product Φ := D^{−1}θd is then a bijection of S_{n} onto itself with the property

(1.1)  (b ca)Φ(σ) = (b ca)σ + n − L Φ(σ) − des Φ(σ)

and this latter result will be the basic ingredient for proving that two bivariable statistics are Euler-Mahonian.

(1)  (2)  (3)  (4)  (5)  (6) (7)
σ  d σ  θd σ=D σ′ D^{−1}θd σ (b ca)σ′ (b ca)σ f(σ′)
S_{4}  B_{4}^{min}  B_{4}^{max}  =Φ(σ)=:σ′
1234 (∞01234)  id  1234  0  0  0
1243 (∞012)(43)  id  1243  0  0  0
1324 (∞014)(32)  id  1423  0  0  0
1342 (∞013)(42)  id  1324  0  1  −1
1423 (∞01)(423)  id  1342  1  0  1
1432 (∞01)(432)  id  1432  0  0  0
2134 (∞034)(21)  id  3412  1  0  1
2143 (∞0)(21)(43) (∞0)(43)(21) 4312  0  0  0
2314 (∞024)(31)  id  2413  1  1  0
2341 (∞023)(41)  id  2314  1  2  −1
2413 (∞02)(413)  id  2134  0  1  −1
2431 (∞02)(431)  id  2143  0  1  −1
3124 (∞04)(312)  id  4123  0  0  0
3142 (∞0)(31)(42)  id  3241  2  1  1
3214 (∞04)(321)  id  4132  0  0  0
3241 (∞0)(32)(41)  id  3214  0  2  −2
3412 (∞03)(412)  id  3124  0  1  −1
3421 (∞03)(421)  id  3142  1  1  0
4123 (∞0)(4123)  id  2341  2  0  2
4132 (∞0)(41)(32)  id  4231  1  0  1
4213 (∞0)(4213)  id  3421  1  0  1
4231 (∞0)(42)(31)  id  4213  0  1  −1
4312 (∞0)(4312)  id  2431  1  0  1
4321 (∞0)(4321)  id  4321  0  0  0

Fig. 2

In Fig. 2 the permutations in S_{4} are listed in column (1). The second column contains the images of each permutation σ under the bijection d. We can then read all the oiseau-words belonging to B_{4}^{min}. In column (3) the elements θd σ that are listed are the oiseau-words belonging to B_{4}^{max}. The entry “id” means that d σ = θd σ. This is the case for all the oiseau-words, except for σ = 2143. Notice that the oiseaux (21) and (43) commute. The images σ′ := Φ(σ) are listed in column (4). In columns (5) and (6) the statistics (b ca) are calculated for σ′ and for σ, respectively. The function f in column (7) is defined to be f(σ′) := n − L σ′ − des σ′, so that (1.1) reads (b ca)σ′ = (b ca)σ+f(σ′). To verify that (1.1) holds for n = 4 we just have to notice that column (5) = column (6) + column (7). The nonzero troughs and the double-descents are reproduced in boldface, so that statement (iv) of Theorem 1.1 is illustrated by the fact that in each row the set of letters in boldface is the same in columns (1), (2), (3) and (4). For instance, 2 is a trough in σ = 3241 and d σ = (∞0)(32)(41), but a double-descent in Φ(σ) = 3214.

For constructing the transformations d, D and θ, and accordingly defining the two sets B_{n}^{min} and B_{n}^{max}, we have recourse to the theory of partially commutative monoids, as was developed by Cartier and Foata [CaFo69]. The salient features are recalled in Section 2. The partially commutative monoid generated by the set of the oiseaux is then described in Section 3. The next two sections are devoted to the constructions of the transformations d and D. Surprisingly, part (iii) of Theorem 1.1 requires a delicate analysis that is made in Section 6. The final sections deal with Eulerian Calculus. In particular, we prove that four conjectures made by Babson and Steingrímsson [BaSt01] are correct.

The following notations will be used throughout. Let A be a nonempty set; we let A^{∗} denote the free monoid generated by A, that is, the set of all the finite words w = a_{1}a_{2} … a_{m}, whose letters a_{i} belong to A. The number m of the letters in the word w is the length of w, denoted by |w|. If E is a subset of A, then |w|_{E} is the number of letters of w that belong to E. When the underlying alphabet A is the set of the integers, then tot w designates the sum of its letters: tot w = a_{1} + a_{2} + ⋯ + a_{m} (“tot” stands for “total”). As noted before, L w designates the rightmost letter a_{m} of w. Furthermore, F w refers to its leftmost letter a_{1} (the first one).

When the alphabet A is totally ordered, the number of descents of w is defined to be the number of integers j such that 1 ≤ j ≤ m − 1 and a_{j} > a_{j+1}. It is expressed as (ba)w or des w. Further statistics, that are introduced in the final sections, refer to Eulerian Calculus proper.

2. Partially commutative monoids

Let A^{∗} be the free monoid generated by a nonempty set A and let C be a subset of A × A containing no element of the form (a, a) and such that (a′, a) belongs to C if (a, a′) does. Two words w and w′ are said to be C-adjacent, if there exist two words u and v and an ordered pair (a, a′) in C such that w = uaa′v and w′ = ua′av. Two words w and w′ are said to be C-equivalent, if they are equal, or if there exists a sequence of words w_{0}, w_{1}, …, w_{p}, such that w_{0} = w, w_{p} = w′ and w_{i−1} and w_{i} are C-adjacent for 1 ≤ i ≤ p. This defines an equivalence relation R_{C} on A^{∗}, compatible with the multiplication in A^{∗}. The quotient monoid A^{∗}/R_{C} is denoted by L(A; C) and is called the C-partially commutative monoid generated by A. The C-equivalence class of a letter a ∈ A is denoted by [a]. Two letters a, a′ are said to commute, if [a][a′] = [a′][a] in L(A; C).

A subset F of A is said to be commutative, if it is finite, non-empty and if any two of its elements commute. For such a subset let [F] := ∏_{a∈A}[a]. A letter a is said to be linked to a subset F of A, if a ∈ F or if there exists a letter in F that does not commute with a. Let F, F′ be two subsets of A; then, F is said to be contiguous to F′ if every letter of F′ is linked to F. Each sequence (F_{1}, …, F_{r}) of commutative subsets of A is called a V -sequence, if for each i = 1, …, r − 1 the subset F_{i} is contiguous to F_{i+1}.

Theorem 2.1. For every element u in L(A; C) there is a unique V - sequence (F_{1}, …, F_{r}) such that u = [F_{1}] ⋯ [F_{r}].

[See [CaFo69, p. 11] for a proof.]

We mention a further property that is needed in the present context. Suppose that the alphabet A is totally ordered and let “≤” denote the total ordering. A word w = a_{1}a_{2} … a_{m} is said to be C-minimal (resp. C-maximal), if for each i = 1, 2, …, m − 1 the following property holds

(2.1) if a_{i} and a_{i+1} commute, then a_{i} < a_{i+1} (resp. a_{i} > a_{i+1}).

Proposition 2.2. Each C-equivalence class in L(A; C) contains one and only one C-minimal (resp. C-maximal) word.

Proof. Let u = [b_{1}][b_{2}] … [b_{m}] be a C-equivalence class and let (F_{1}, F_{2}, …, F_{r}) be its V -sequence. Denote the minimum of F_{1} (with respect to the total ordering on A) by a_{1}. The product [F_{1} \{a_{1}}][F_{2}] ⋯ [F_{r}] in L(A; C) admits a V -sequence (G_{1}, G_{2}, …, G_{s}). More essentially, the inclusion F_{1} \ {a_{1}} ⊂ G_{1} holds, as can be verified directly, or by using Corollary 1.4 on page 15 in [CaFo69]. Extract a_{2} := min G_{1} from B_{1}. If a_{2} belongs to F_{1}, both a_{1} and a_{2} commute and a_{1} < a_{2}; if a_{2} ∉ F_{1}, then a_{2} necessarily belongs to F_{2} and commutes with all the letters in F_{1} \ {a_{1}}. Consequently, a_{1} and a_{2} do not commute. Again form the new class [G_{1} \ {a_{2}}][G_{2}] ⋯ [G_{s}], and so on. At the end we get a word a_{1}a_{2} … a_{m} such that either a_{i} < a_{i+1}, or a_{i} and a_{i+1} do not commute.

To prove the uniqueness take two distinct C-minimal words v and v′ supposed to be C-equivalent. There suffices to consider the case where v = a_{1}a_{2} … a_{m}, v′ = a_{i_{1}}a_{i_{2}} … a_{i_{m}} with a_{1} ≠ a_{i_{1}}. Those words may also be expressed as v =a_{1}a_{2} … a_{j}a_{i_{1}}a_{j+2} … a_{m} and v′ =a_{i_{1}}a_{i_{2}}…a_{i_{k}}a_{1}a_{i_{k+2}} … a_{i_{m}}, with a_{i_{1}} ≠ a_{1}, a_{2}, …, a_{j} and a_{1} ≠ a_{i_{1}}, a_{i_{2}}, …, a_{i_{k}}. As v and v′ are supposed to be C-equivalent, the letter a_{i_{1}} (resp. a_{1}) commutes with a_{1}, a_{1}, …, a_{j} (resp. with a_{i_{1}}, a_{i_{2}}, …, a_{i_{k}}). But as v and v′ are both Cminimal, the two relations a_{1} < a_{i_{1}}, a_{i_{1}} < a_{1} hold, a contradiction. To prove the “resp.” part, simply replace “min” vy “max” and “<” by “>” in the above derivation.

In the sequel the map that sends each C-minimal word in A^{∗} onto the C-maximal word that belongs to the same C-equivalence class will be denoted by θ. If v = a_{1}a_{2} … a_{m} is C-minimal, we form the Cclass u = [a_{1}][a_{2}] ⋯ [a_{m}], then its V -sequence (F_{1}, F_{2}, …, F_{r}). Following the proof of the previous proposition, define b_{1} := max F_{1} and form the V -sequence (G_{1}, G_{2}, …, F_{s}) of [F_{1} \ {b_{1}}][F_{2}] … [F_{r}]. Further, define b_{2} := max G_{1}, and so on. Finally, θ(v) = b_{1}b_{2} … b_{m}.

3. The oiseau partially commutative monoid

Now A will designate the set of all the oiseaux (pdth), as defined in the introduction and C will be the set of all pairs ((pdth), (p′d′t′h′)) of oiseaux such that either (pdth) ≪ (p′d′t′h′), or (pdth) ≫ (p′d′t′h′). We form the free monoid A^{∗} generated by A. Its elements are the oiseauwords v = (p_{0}d_{0}t_{0}h_{0})(p_{1}d_{1}t_{1}h_{1}) … (p_{r}d_{r}t_{r}h_{r}). We also consider the Cpartially commutative monoid L(A; C). The C-equivalence class of each oiseau (pdth) will be denoted by [pdth].

For each n ≥ 1 the two classes of oiseau-words B_{n}^{min} and B_{n}^{max}, mentioned in the statement of Theorem 1.1, are defined as follows. An oiseau-word v = (p_{0}d_{0}t_{0}h_{0})(p_{1}d_{1}t_{1}h_{1}) … (p_{r}d_{r}t_{r}h_{r}) belongs to B_{n}^{min} (resp. to B_{n}^{max}) if and only if the following three conditions hold:

(i) the oiseau-word v is C-minimal (resp. C-maximal); (ii) p_{0} = ∞, d_{0} = e (the empty word) and t_{0} = 0; (iii) the factor h_{0}p_{1}d_{1}t_{1}h_{1} … p_{r}d_{r}t_{r}h_{r} is a permutation of 1, 2, … n.

Let [v] = [p_{0}d_{0}t_{0}h_{0}] … [p_{r}d_{r}t_{r}h_{r}] be the C-equivalence class of an element v = (p_{0}d_{0}t_{0}h_{0}) … (p_{r}d_{r}t_{r}h_{r}) of B_{n}^{min} (resp. of B_{n}^{max}). As p_{0}d_{0}t_{0} = ∞0, no oiseau (p_{i}d_{i}t_{i}h_{i}) (i = 1, …, r) can commute with (p_{0}d_{0}t_{0}h_{0}) = (∞0h_{0}). Hence, all the words in the C-equivalence class [v] start with (∞0h_{0}) and the first factor in the V -sequence of [v] is reduced to the single term [(∞0h_{0})]. The set of all the C-equivalence classes that contain one element of B_{n}^{min} (and only one by Proposition 2.2) will be designated by B_{n}. The three sets B_{n}, B_{n}^{min}, B_{n}^{max} can be put into a one-to-one correspondence. In particular, B_{n}^{max} = θ(B_{n}^{min}), where θ is the bijection introduced at the end of Section 2.

Example. The following word

v = (∞, 0, 19)(18, 3, 1)(16, 4, 2, 6, 10, 14)(9, 5, 7)(11, 8)(13, 12)(17, 15)

is an element of B_{19}^{min}. To derive θ(v), calculate the V -sequence of [v] that reads (F_{1}, F_{2}, F_{3}, F_{4}, F_{5}) with

F_{1} = {(∞, 0, 19)}, F_{2} = {(18, 3, 1)}, F_{3} = {(16, 4, 2, 6, 10, 14)},
F_{4} = {(9, 5, 7), (13, 12), (17, 15)}, F_{5} = {(11, 8)}).

Then a_{1} = max F_{1} = (∞, 0, 19). The V -sequence of [F_{2}][F_{3}][F_{4}][F_{5}] is simply (F_{2}, F_{3}, F_{4}, F_{5}), so that a_{2} = (18, 3, 1). The V -sequence of [F_{3}][F_{4}][F_{5}] is (F_{3}, F_{4}, F_{5}) and a_{3} = (16, 4, 2, 6, 10, 14). The V -sequence of [F_{4}][F_{5}] is (F_{4}, F_{5}) and a_{4} = max F_{4} = (17, 15). The V -sequence of [F_{4} \ {a_{4}}][F_{5}] is ({(9, 5, 7), (13, 12)}, {(11, 8)}) and a_{5} = (13, 12). Finally, a_{6} = (9, 5, 7), a_{7} = (11, 8), so that

θ(v) = (∞, 0, 19)(18, 3, 1)(16, 4, 2, 6, 10, 14)(17, 15)(13, 12)(9, 5, 7)(11, 8).

The next two sections will be devoted to constructing two bijections d and D of the permutation group S_{n} onto B_{n}^{min} and B_{n}^{max}, respectively.

4. The first transformation

To construct the first bijection d of S_{n} onto B_{n}^{min} we proceed as follows. Let σ = x_{1}x_{2} ⋯ x_{n} be a permutation of the word 12 … n, written as a linear word. Let x_{0} := 0, x_{−1} = x_{n+1} := +∞ and consider the word 0σ = x_{0}x_{1} … x_{n}. By peak of 0σ it is meant a letter x_{j} such that 1 ≤ j ≤ n and x_{j−1} < x_{j}, x_{j} > x_{j+1}. By trough we mean a letter x_{j} such that 0 ≤ j ≤ n and x_{j−1} > x_{j}, x_{j} < x_{j+1}. Accordingly, each permutation 0σ has (r+1) troughs and r peaks for some r ≥ 0. By double-descent we mean a letter x_{j} such that 1 ≤ j ≤ n − 1 and x_{j−1} > x_{j} > x_{j+1}. By double-rise we mean a letter x_{j} such that 1 ≤ j ≤ n and x_{j−1} < x_{j} < x_{j+1}. As above, 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. There is a unique factorization

(4.1)  t_{0}h_{0} | p_{1}d_{1}t_{1}h_{1} | p_{2}d_{2}t_{2}h_{2} | … | p_{r}d_{r}t_{r}h_{r}

of 0σ, called its peak factorization, having the following properties: (1) r ≥ 0; t_{0} = 0;

(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-descents, respectively. It will be convenient to let p_{0} = p_{r+1} := +∞.

In each component p_{j}d_{j}t_{j}h_{j} the peak p_{j} is not necessarily the greatest letter of the factor, so that (p_{j}d_{j}t_{j}h_{j}) may not be an oiseau. The transformation d will consist of moving to the left the different double-rises in such a way that the new factors, say, (p_{j}d_{j}t_{j}h′_{j}) will be oiseaux; in particular, p_{j} ≫ h′_{j}.

Let y be a double-rise of 0σ, so that y is a letter of the factor h_{j} for some j (0 ≤ j ≤ r). Define φ(y) to be the greatest integer i such that 0 ≤ i ≤ j and p_{i} > y > t_{i}. Thus, the following inequalities hold:

(4.2)  p_{i} > y > t_{i}, y > p_{i+1}, …, y > p_{j}, t_{j} < y < p_{j+1}.

Next, define h′_{i} to be the increasing word of all double-rises y in σ such that φ(y) = i. If φ(y) ≠ i for every double-descent y of 0σ, let h′_{i} be the empty word. Clearly, (∞0h′_{0}) is an oiseau, as well as each letter (p_{i}d_{i}t_{i}h′_{i}) for i = 1, 2, …, r. Define d σ to be the following element in A^{∗} [remember that t_{0} = 0]

(4.3)  d σ := (∞t_{0}h′_{0})(p_{1}d_{1}t_{1}h′_{1})(p_{2}d_{2}t_{2}h′_{2}) … (p_{r}d_{r}t_{r}h′_{r})

For example, start with the peak-factorized permutation

0σ = {0 \atop 0} | 18 ∧ , {3 \atop 1}, 1 ∨ | 16 ∧ , 4{, \atop 2}2 ∨, 6 | 9 ∧, 5 ∨{, \atop 3}7, 10 | 11 ∧ {, \atop 4}8 ∨ | 13 ∧ , {12 ∨ \atop 5}, 14 | 17 ∧ , {15 ∨ \atop 6}, 19,

that has seven factors, numbered from 0 to 6. The peaks (resp. the troughs) are materialized by “∧” (resp. “∨”) and the double-rises are written in boldface. We have p_{0} = ∞, p_{1} = 18, p_{2} = 16, p_{3} = 9, p_{4} = 11, p_{5} = 13, p_{6} = 17. Also, t_{0} = 0, t_{1} = 1, t_{2} = 2, t_{3} = 5, t_{4} = 8, t_{5} = 12, t_{6} = 15. Next, the double-descent factors read d_{1} = 3; d_{2} = 4, d_{3} = d_{4} = d_{5} = d_{6} = e (the empty word) and the double-rise factors h_{0} = h_{1} = e; h_{2} = 6; h_{3} = 7, 10; h_{4} = e; h_{5} = 14; h_{6} = 19.

Thus φ(6) = 2, φ(7) = 3, φ(10) = 2, φ(14) = 2, φ(19) = 0 (remember that p_{0} = ∞) and h′_{0} = 19; h′_{2} = 6, 10, 14; h′_{3} = 7; h′_{4} = h′_{5} = h′_{6} = e. Hence

d σ =(∞, 0, 19)(18, 3, 1)(16, 4, 2, 6, 10, 14)(9, 5, 7)(11, 8)(13, 12)(17, 15).

Go back to the general case. For each i = 0, 1, …, r−1 the trough t_{i} is less than both p_{i} and p_{i+1}. Hence, if p_{i} > p_{i+1}, the two oiseaux (p_{i}d_{i}t_{i}h′_{i}) and (p_{i+1}d_{i+1}t_{i+1}h′_{i+1}) cannot commute. In an equivalent manner, if (p_{i}d_{i}t_{i}h′_{i}) and (p_{i+1}d_{i+1}t_{i+1}h′_{i+1}) commute, then p_{i} < p_{i+1} and also (p_{i}d_{i}t_{i}h′_{i}) < (p_{i+1}d_{i+1}t_{i+1}h′_{i+1}) (for the lexicographic order). But as the oiseaux commute, the <-sign can be replaced by the ≪-sign, so that d σ is minimal.

The map d is bijective. The construction of d given above is perfectly reversible. Let v = (∞t_{0}h′_{0})(p_{1}d_{1}t_{1}h′_{1})(p_{2}d_{2}t_{2}h′_{2}) … (p_{r}d_{r}t_{r}h′_{r}) be an element of B_{n}^{min} and let y be a double-rise in the word p_{i}d_{i}t_{i}h′_{i} (0 ≤ i ≤ r) (with p_{0} = ∞, d_{0} = e and t_{0} = 0).

If p_{i} < p_{i+1} (remember that p_{r+1} = ∞ by convention), let φ^{−}(y) := i. If p_{i} > p_{i+1}, define φ^{−}(y) to be the smallest integer j such that i + 1 ≤ j ≤ r and y < p_{j+1}. Then, define h_{j} to be the increasing word of all double-rises y from each of the words p_{0}d_{0}t_{0}h′_{0}, …, p_{r}d_{r}t_{r}h′_{r} such that φ^{−}(y) = j and form the permutation σ^{−} := t_{0}h_{0}p_{1}d_{1}t_{1}h_{1}p_{r}d_{r}t_{r}h_{r}.

As the inequalities in (4.2) hold, we have the equivalence

[y is a letter of h_{j} and φ(y) = i] ⇔ [y is a letter of h′_{i} and φ^{−}(y) = j].

To show that d is reversible we only have to verify that the factorization

t_{0}h_{0} | p_{1}d_{1}t_{1}h_{1} | … | p_{r}d_{r}t_{r}h_{r},

is the peak factorization of σ^{−}, essentially verify that the p_{j}’s are the peaks of σ^{−}. When p_{j} > p_{j+1}, we don’t have p_{j}d_{j}t_{j}h′_{j} ≫ p_{j+1}d_{j+1}t_{j+1}h′_{j+1}, because v is supposed to be minimal; hence t_{j} < p_{j+1}. The double-rises in h′_{j} less than p_{j+1} occur in h_{j}, while the double-rises greater than p_{j+1} occur in a factor h_{i} with i ≥ j + 1. It follows that p_{j+1} is greater than all the letters of h_{j}. It is then is a peak of σ^{−}, so that σ^{−} = σ. Thus d is a bijection.

Example. Start with the C-minimal word

v = (∞, {0 \atop 0}, 19)(18, {3 \atop 1}, 1)(16, 4, 2, {6 \atop 2}, 10, 14)(9, {5 \atop 3}, 7)(11{, \atop 4}8)(13{, \atop 5}12)(17{, \atop 6}15)

We have φ^{−}(19) = 6; φ^{−}(6) = 2; φ^{−}(10) = 3; φ^{−}(14) = 5; φ^{−}(7) = 3; so that h_{0} = h_{1} = e; h_{2} = 6; h_{3} = 7, 10; h_{4} = e; h_{5} = 14; h_{6} = 19 and

d^{−1}v =σ =| 18, 3, 1 | 16, 4, 2, 6 | 9, 5, 7, 10 | 11, 8 | 13, 12, 14 | 17, 15, 19.

5. The second transformation

In the second transformation the key role will be played by the doubledescents instead of the double-rises. The peak factorization is replaced by the trough factorization that consists of cutting the permutation just before each trough. More formally, each permutation σ = x_{1}x_{2} … x_{n} has a unique factorization

h_{0}p_{0}d_{0} | t_{1}h_{1}p_{1}d_{1} | t_{2}h_{2}p_{2}d_{2} | … | t_{r}h_{r}p_{r}d_{r},

where all the previous notations about the letters h, p, d, t have been kept. By convention this time, t_{0} = t_{r+1} = −∞.

Construction of the transformation D. There are four steps in the construction:

(1) The first step consists of transposing the factors t_{i}h_{i} and p_{i}d_{i} in each compartment, for i = 1, 2, …, r, the first compartment remaining alike, to obtain:

h_{0}p_{0}d_{0} | p_{1}d_{1}t_{1}h_{1} | p_{2}d_{2}t_{2}h_{2} | … | p_{r}d_{r}t_{r}h_{r}.

(2) Let x be a letter of the factor d_{i} (1 ≤ i ≤ r). Either there exists an integer j such that 1 ≤ j ≤ i and p_{j} > x > t_{j} and ψ^{−}(x) will denote the greatest integer with those properties, or such an integer does not exist and we define ψ^{−}(x) := 0. Also let ψ^{−}(x) := 0 for each letter x in the factor d_{0}.

(3) For each i = 0, 1, …, r form the decreasing factor \overline{d}_{i} with all the letters x such that ψ^{−}(x) = i.

(4′) If the word \overline{d}_{0} is empty, define D σ to be the word in A^{∗} [later it will be shown that each letter ( …) is an oiseau]

D σ := (∞0h_{0}p_{0})(p_{1}\overline{d}_{1}t_{1}h_{1})(p_{2}\overline{d}_{2}t_{2}h_{2}) … (p_{r}\overline{d}_{r}t_{r}h_{r}).

(4′′) If \overline{d}_{0} is nonempty, denote its rightmost letter by t_{0}, so that \overline{d}_{0} may be written as \overline{d}_{0} = \overline{d}_{0}′ t_{0} for some (decreasing) factor \overline{d}_{0}′. If h_{0} = e, let h′_{0} = h′′_{0} := e; if t_{0} ≪ h_{0}, let h′_{0} := e, h′′_{0} := h_{0}; if h_{0} ≪ t_{0}, let h′_{0} := h_{0}, h′′_{0} := e. Otherwise, the word h_{0} may be expressed (in a unique manner) as h_{0} = h′_{0}h′′_{0}, in such a way that h′_{0} ≪ t_{0} ≪ h′′_{0}. Then define

D σ := (∞0h′_{0})(p_{0}\overline{d}_{0}′ t_{0}h′′_{0})(p_{1}\overline{d}_{1}t_{1}h_{1})(p_{2}\overline{d}_{2}t_{2}h_{2}) … (p_{r}\overline{d}_{r}t_{r}h_{r}).

Example 1. Consider the following permutation already troughfactorized:

σ = 18{, \atop 0}20 ∧ | 3 ∨, 7{, \atop 1}17 ∧ | 16 ∨, 19 ∧ {, \atop 2}15, 6 | 2 ∨, 12{, \atop 3}14 ∧ , 10 | 9 ∨, 13 ∧ {, \atop 4}11, 8 | 1 ∨, 5 ∧{, \atop 5}4.

Step (1) yields

18{, \atop 0}20 ∧ | 17 ∧ {, \atop 1}3 ∨, 7 | 19 ∧ , 15{, \atop 2}6, 16 ∨ | 14 ∧ , 10{, \atop 3}2 ∨, 12 | 13 ∧ , 11{, \atop 4}8, 9 ∨ | 5 ∧, 4{, \atop 5}1 ∨.

In step (2) we have to define: ψ^{−}(15) = 1, ψ^{−}(6) = 1, ψ^{−}(10) = 3, ψ^{−}(11) = 4, ψ^{−}(8) = 3; ψ^{−}(4) = 5, so that we may form, as prescribed in step (3), \overline{d}_{0} = e; \overline{d}_{1} = 15, 6; \overline{d}_{2} = e; \overline{d}_{3} = 10, 8; \overline{d}_{4} = 11; \overline{d}_{5} = 4.

As \overline{d}_{0} = e, step (4′) applies, so that

D σ:=(∞, 0, 18, 20)(17, 15, 6, 3, 7)(19, 16)(14, 10, 8, 2, 12)(13, 11, 9)(5, 4, 1).

Example 2. With the permutation

σ = 1, 6, 11{, \atop 0}18 ∧ , 17 | 16 ∨, 20 ∧ {, \atop 1}15 | 8 ∨, 12{, \atop 2}14 ∧ | 10 ∨, 13 ∧ {, \atop 3}9, 7 | 2 ∨, 4, 19 ∧ {, \atop 4}5, 3,

already trough-factorized, step (1) yields:

1, 6, 11{, \atop 0}18 ∧ , 17 | 20 ∧ , 15{, \atop 1}16 ∨ | 14 ∧ , 8 ∨{, \atop 2}12 | 13 ∧ , 9{, \atop 3}7, 10 ∨ | 19 ∧ , 5{, \atop 4}3, 2 ∨, 4.

In step (2) we define: ψ^{−}(17) = 0, ψ^{−}(15) = 0, ψ^{−}(9) = 2, ψ^{−}(7) = 0, ψ^{−}(5) = 4, ψ^{−}(3) = 4. In step (3) we get: \overline{d}_{0} = 17, 15, 7; \overline{d}_{1} = e; \overline{d}_{2} = 9; \overline{d}_{3} = e; \overline{d}_{4} = 5, 3. As \overline{d}_{0} = 17, 15, 7 is nonempty, we apply (4′′) with h_{0} = 1, 6, 11 and \overline{d}_{0}′ = 7. We get h′_{0} = 1, 6 < 7 < 11 = h′′_{0}. Hence

D σ =(∞, 0, 1, 6)(18, 17, 15, 7, 11)(20, 16)(14, 9, 8, 12)(13, 10)(19, 5, 3, 2, 4).

Several properties are to be verified.

(a) Each letter in D σ is an oiseau. First, 0 ≪ h_{0} ≪ p_{0}, so that (∞0h_{0}p_{0}) is an oiseau. Next, for each i = 1, 2, …, r we have p_{i} ≫ \overline{d}_{i} ≫ t_{i} by (2)–(3). Also t_{i} ≪ h_{i} ≪ p_{i}, since t_{i} is a trough and p_{i} a peak in the permutation σ. Consequently, for each i = 1, 2, …, r, each letter (p_{i}\overline{d}_{i}t_{i}h_{i}) is an oiseau.

Now, if x is a letter in d_{0}, it is also a letter in \overline{d}_{0} by (2), so that p_{0} ≫ x ≫ t_{1}. Furthermore, if x is a letter of some d_{i} with 1 ≤ i ≤ r and ψ^{−}(x) = 0, then x < t_{1}, x < t_{2}, …, x < t_{i}. As p_{0} ≫ t_{1}, we conclude that p_{0} ≫ x. Hence, p_{0} ≫ \overline{d}_{0} and (p_{0}\overline{d}_{0}h′′_{0}) = (p_{0}\overline{d}_{0}′ t_{0}h′′_{0}) is also an oiseau.

(b) The word D σ is C-maximal. First (∞0h_{0}p_{0}) (resp. (∞0h′_{0})) does not commute with any one of the other letters in D σ. As t_{i+1} is the closest trough to the right of the peak p_{i} in σ, we have p_{i} > t_{i+1} (i ≥ 1). Hence p_{i}\overline{d}_{i}t_{i}h_{i} ≪ p_{i+1}\overline{d}_{i+1}t_{i+1}h_{i+1} cannot hold. It then follows that if (p_{i}\overline{d}_{i}t_{i}h_{i}) and (p_{i+1}\overline{d}_{i+1}t_{i+1}h_{i+1}) commute, we necessarily have p_{i}\overline{d}_{i}t_{i}h_{i} ≫ p_{i+1}\overline{d}_{i+1}t_{i+1}h_{i+1}. Finally, as p_{0} > t_{1}, we show, using the same argument, that if (p_{0}\overline{d}_{0}′ t_{0}h′′_{0}) and (p_{1}\overline{d}_{1}t_{1}h_{1}) commute, we have (p_{0}\overline{d}_{0}′ t_{0}h′′_{0}) ≫ (p_{1}\overline{d}_{1}t_{1}h_{1}). Thus D σ is C-maximal.

(c) Construction of the inverse D^{−1}. Compare steps (4′) and (4′′). In (4′) the rightmost letter p_{0} in the first oiseau is greater than the trough t_{1} in the second oiseau. In (4′′) the rightmost letter of 0h′_{0} in the first oiseau is less than the trough t_{0} in the second oiseau. This makes up the first step in the definition of the reverse of D. Let v = ω_{0}ω_{1} … ω_{s} belong to B_{n}^{max} with ω_{0} = (∞0k_{0}). If s = 0, then D^{−1} v = k_{0} = 1, 2, …, n. Assume now that s ≥ 1.

(i) If the rightmost letter of 0k_{0} is not less than the trough in the oiseau ω_{1}, it cannot be 0; denote it by p_{0}. We may express v as

(5.1)  v = (∞0h_{0}p_{0})(p_{1}\overline{d}_{1}t_{1}h_{1})(p_{2}\overline{d}_{2}t_{2}h_{2}) … (p_{r}\overline{d}_{r}t_{r}h_{r}),

with r = s, 0h_{0}p_{0} = 0k_{0} and (p_{i}\overline{d}_{i}t_{i}h_{i}) = ω_{i} for i = 1, 2, …, r.

(ii) If the rightmost letter of 0k_{0} is less than the trough is the oiseau ω_{1}, we may express v as

(5.2) v = (∞0h′_{0})(p_{0}\overline{d}_{0}′ t_{0}h′′_{0})(p_{1}\overline{d}_{1}t_{1}h_{1})(p_{2}\overline{d}_{2}t_{2}h_{2}) … (p_{r}\overline{d}_{r}t_{r}h_{r}),

with r = s − 1, ω_{0} = (∞0k_{0}) = (∞0h′_{0}), ω_{1} = (p_{0}\overline{d}_{0}′ t_{0}h′′_{0}) and ω_{i+1} = (p_{i}\overline{d}_{i}t_{i}h_{i}) for i = 0, 1, …, r and 0h′_{0} ≪ t_{0}. Then define h_{0} := h′_{0}h′′_{0}, \overline{d}_{0} := \overline{d}_{0}′ t_{0}.

In both cases the words \overline{d}_{i}, h_{i} and the letter p_{i} have been defined for each i = 0, 1, …, r and the letter t_{i} for i = 1, 2 …, r. We form the factorization

(5.3)  h_{0}p_{0}\overline{d}_{0} | t_{1}h_{1}p_{1}\overline{d}_{1} | t_{2}h_{2}p_{2}\overline{d}_{2} | ⋯ | t_{r}h_{r}p_{r}\overline{d}_{r}.

With the convention t_{r+1} = −∞ and for i = 0, 1, …, r we move each letter x of \overline{d}_{i} to the right until it falls between a peak p_{j} and the next trough t_{j+1}. More formally, we define ψ(x) to be the least integer j such that i ≤ j ≤ r and p_{j} > x > t_{j+1} and let d_{j} be the decreasing word with all the letters x such that ψ(x) = j. As t_{i} ≪ h_{i} ≪ p_{i}, because the letters of v are oiseaux, the factorization

(5.4)  h_{0}p_{0}d_{0} | t_{1}h_{1}p_{1}d_{1} | t_{2}h_{2}p_{2}d_{2} | ⋯ | t_{r}h_{r}p_{r}d_{r}

is a trough factorization of a permutation. This defines D^{−1} v. We also convince ourselves that D^{−1}D and DD^{−1} are identity maps.

Example 1. Let

v = (∞, 0, 18, 20)(17, 15, 6, 3, 7)(19, 16)(14, 10, 8, 2, 12)(13, 11, 9)(5, 4, 1)

belong to B_{20}^{max}. As the rightmost letter 20 of the factor 0, 18, 20 is not less than the trough 3 of the second oiseau, step (i) applies. We define h_{0} = 18, 20, p_{0} = 20, \overline{d}_{1} = 15, 6, \overline{d}_{2} = e, \overline{d}_{3} = 10, 8, \overline{d}_{4} = 11, \overline{d}_{5} = 4. Next, form the factorization introduced in (5.3)

18, 20 | 3, 7, 17, 15, 6 | 16, 19 | 2, 12, 14, 10, 8 | 9, 13, 11 | 1, 5, 4

and move the letters of the \overline{d}_{i}’s (the letters in boldface) to the right until they are inserted correctly between a peak and the next trough. We get

18, 20 | 3, 7, 17 | 16, 19, 15, 6 | 2, 12, 14, 10 | 9, 13, 11, 8 | 1, 5, 4.

This is the trough factorization of the permutation D^{−1}v.

Example 2. The following word

v = (∞, 0, 1, 6)(18, 17, 15, 7, 11)(20, 16)(14, 9, 8, 12)(13, 10)(19, 5, 3, 2, 4)

belongs to B_{20}^{max}. The rightmost letter 6 of the factor 0, 1, 6 is less than the trough 7 of the second oiseau, so that step (ii) applies. We have h′_{0} = 1, 6, p_{0} = 18, \overline{d}_{0}′ = 17, 15, t_{0} = 7, h′′_{0} = 11, then h_{0} = h′_{0}h′′_{0} = 1, 6, 11, \overline{d}_{0} = \overline{d}_{0}′ t_{0} = 17, 15, 7, \overline{d}_{1} = e, \overline{d}_{2} = 9, \overline{d}_{3} = e, \overline{d}_{4} = 5, 3. Thus, the (5.1)-factorization reads

1, 6, 11, 18, 17, 15, 7 | 16, 20 | 8, 12, 14, 9 | 10, 13 | 2, 4, 19, 5, 3.

Next, we move the letters in bold-face to the right, following the rule described before. We get:

1, 6, 11, 18, 17 | 16, 20, 15 | 8, 12, 14 | 10, 13, 9, 7 | 2, 4, 19, 5, 3,

which is the trough factorization of a permutation σ = D^{−1}v.

6. Order statistics

Let 0σ = 0x_{1}x_{2} … x_{n} be a permutation, starting with 0, whose peak factorization reads

t_{0}h_{0} | p_{1}d_{1}t_{1}h_{1} | p_{2}d_{2}t_{2}h_{2} | … | p_{r}d_{r}t_{r}h_{r}.

Let p_{0} := ∞, d_{0} := e, t_{0} = 0 and for 0 ≤ i < j ≤ r let |p_{i}d_{i}t_{i}h_{i}|_{]t_{j},p_{j}[} denote the number of letters in the word p_{i}d_{i}t_{i}h_{i} that belong to the open interval ]t_{j}, p_{j}[. As only the factors p_{i}d_{i}t_{i} contain subfactors of the form ca, we can express (b ca)σ as

(6.1)  (b ca)σ = ∑_{1≤j≤r} ∑_{i<j} |p_{i}d_{i}t_{i}h_{i}|_{]t_{j},p_{j}[}.

Now, let v = (∞0h_{0})(p_{1}d_{1}t_{1}h′_{1}) … (p_{r}d_{r}t_{r}h′_{r}) belong to the C-equiv-alence class B_{n} and define

(6.2)  (b ca)v := ∑_{1≤j≤r} ∑_{i<j} |p_{i}d_{i}t_{i}h′_{i}|_{]t_{j},p_{j}[},

keeping the convention p_{0} := ∞, d_{0} := e, t_{0} = 0. When two oiseaux (p_{i}d_{i}t_{i}h′_{i}), (p_{j}d_{j}t_{j}h′_{j}) commute, then |p_{i}d_{i}t_{i}h′_{i}|_{]t_{j},p_{j}[} = 0. It then follows that if two elements v, v′ in A^{∗}, of valuation 1^{n}, are C-equivalent, then

(6.3)  (b ca)v = (b ca)v′.

When we go from σ to d σ, only the positions of some double-rises y change, and if they do, those double-rises move to the left, but not to the left of factors p_{i}d_{i}t_{i}h_{i} such that p_{i} > y, as shown in (4.2). Hence, we also have

|p_{i}d_{i}t_{i}h′_{i}|_{]t_{j},p_{j}[} = |p_{i}d_{i}t_{i}h_{i}|_{]t_{j},p_{j}[}

for 0 ≤ i < j ≤ r. Hence,

(6.4)  (b ca)σ = (b ca)d σ.

But as the statistic (b ca) depends only on the C-equivalence class and not on its representative by (6.3), we also have

(6.5)  (b ca)θ(d σ) = (b ca)d σ.

The next proposition is the analog for D of property (6.4). It requires a longer proof.

Proposition 6.1. Let σ be a permutation of order n. Then

(6.6)  (b ca)σ − (b ca)D σ = n − L σ − des σ.

Proof. Let v := D σ. As seen in Section 5 (c), the element v is in B_{n}^{max} and appears in the form (5.1) or in the form (5.2). When r = 0, we have v = (∞0h_{0}p_{0}) or v = (∞0h′_{0})(p_{0}\overline{d}_{0}′ t_{0}h′′_{0}). In the first case, σ = h_{0}p_{0} is the increasing word 12 … n and identity (6.6) holds. In the second case, σ = h′_{0}h′′_{0}p_{0}\overline{d}_{0}′ t_{0} and des σ = |p_{0}\overline{d}_{0}′ |, (b ca)σ = |h′_{0}h′′_{0}|]t_{0}, p_{0}[ = |h′′_{0}|]t_{0}, p_{0}[ = |h′′_{0}|. On the other hand, (b ca) D σ = |h′_{0}|]t_{0}, p_{0}[ = 0, since h′_{0} ≪ t_{0}, whenever h′_{0} is nonempty. Thus, the left-hand side of (6.6) is equal to |h′′_{0}|.

To evaluate the right-hand side of (6.6) consider the two cases:

(i) h′_{0} = h′′_{0} = e; (ii) h′_{0}, h′′_{0} not both empty. In case (i) n − L σ − des σ = p_{0} − 1 − (p_{0} − 1) = 0 = |h′′_{0}|, since p_{0}\overline{d}_{0}′ t_{0} = n(n − 1) … 1. In case (ii) we have n − L σ − des σ = p_{0} − 1 − |p_{0}\overline{d}_{0}′ | = p_{0} − |p_{0}\overline{d}_{0}′ t_{0}|, which is equal to the number of letters in σ less than t_{0}. This number is precisely |h′′_{0}|. Thus (6.6) holds for r = 0

We then proceed by induction on r and assume that r ≥ 1. The construction of D, given in Section 5, depends only on the total ordering on the set {1, 2, …, n}. The latter set can then be replaced by any set E of integers of the same cardinality. Let S_{E} be the set of the permutations of E. Then the set D(S_{E}) will again be denoted by B_{n}^{max}, the context indicating the underlying set E that is on use.

Having this convention in mind we can write v, using the notations (5.1) and (5.2), as v = v_{1}(p_{r}\overline{d}_{r}t_{r}h_{r}), where v_{1} is an element of B_{n_{1}}^{max} for some n_{1} ≤ n − 2. Let σ_{1} := D^{−1}v_{1}. Again notice that σ_{1} is a permutation of a set of cardinality n_{1}. We shall evaluate the left-hand side of (6.6) as the sum U_{1} + U_{2} − U_{3}, where

U_{1} := (b ca)σ − (b ca)σ_{1}; U_{2} := (b ca)σ_{1} − (b ca)v_{1};
U_{3} := (b ca)v − (b ca)v_{1}.

A first evaluation of U_{3}. Using (5.1) and (5.2) let

w := h_{0}p_{0}p_{1}\overline{d}_{1}t_{1}h_{1} … p_{r−1}\overline{d}_{r−1}t_{r−1}h_{r−1}

(resp. h′_{0}p_{0}\overline{d}_{0}′ t_{0}h′′_{0}p_{1}\overline{d}_{1}t_{1}h_{1} … p_{r−1}\overline{d}_{r−1}t_{r−1}h_{r−1}). Then (6.7) (b ca)v − (b ca)v_{1} = |w|]t_{r}, p_{r}[.

Evaluation of U_{1}. By (5.4) σ = h_{0}p_{0}d_{0}t_{1}h_{1}p_{1}d_{1} … t_{r}h_{r}p_{r}d_{r}. In the construction of D^{−1}σ the decreasing factor d_{r} is made of the doubledescents x in w such that ψ(x) = r [let d′_{r−1} be the decreasing word made of those letters x], plus all the double-descents in the factor \overline{d}_{r}. Also, by construction,

(6.8)  d′_{r−1} ≪ t_{r}

and also,

(6.9)  t_{r} ≪ \overline{d}_{r},

since (p_{r}d_{r}t_{r}\overline{h}_{r}) is an oiseau. Hence

(6.10)  d_{r} = \overline{d}_{r}d′_{r−1}.

Accordingly,

σ = h_{0}p_{0}d_{0}t_{1}h_{1}p_{1}d_{1} … t_{r−1}h_{r−1}p_{r−1}d_{r−1}t_{r}h_{r}p_{r}\overline{d}_{r}d′_{r−1};
σ_{1} = h_{0}p_{0}d_{0}t_{1}h_{1}p_{1}d_{1} … t_{r−1}h_{r−1}p_{r−1}d_{r−1}d′_{r−1}.

We can evaluate U_{1}, the open intervals to be considered being ]t_{r}, p_{r−1}[ and ] L σ, p_{r}[ for σ and ] L σ_{1}, p_{r−1}[ for σ_{1}. We get

(6.11) U_{1} = |σ_{1}|]t_{r}, p_{r−1}[ − |p_{r−1}d_{r−1}d′_{r−1}|]t_{r}, p_{r−1}[
+ |σ_{1}|] L σ, p_{r}[ − |d′_{r−1}|] L σ, p_{r}[ + |t_{r}h_{r}|] L σ, p_{r}[
− |σ_{1}|] L σ_{1}, p_{r−1}[ + |p_{r−1}d_{r−1}d′_{r−1}|] L σ_{1}, p_{r−1}[.

Evaluation of U_{2}. As the bottoms of the descents are the t_{i}’s and the double-descents, we have: des σ−des σ_{1} = |d_{r−1}t_{r}|+|\overline{d}_{r}d′_{r−1}|−|d_{r−1}d′_{r−1}| = |t_{r}\overline{d}_{r}|. On the other hand, n − L σ = |σ|] L σ, +∞[, so that by induction

(6.12)  U_{2} = |σ_{1}|] L σ_{1}, +∞[ − des σ_{1}
= |σ_{1}|] L σ_{1}, +∞[ − des σ + |t_{r}\overline{d}_{r}|.

Evaluation of U_{3}. Again take the expression derived in (6.7). The word w is a rearrangement of h_{0}p_{0}\overline{d}_{0}t_{1}h_{1}p_{1}\overline{d}_{1} … t_{r−1}h_{r−1}p_{r−1}\overline{d}_{r−1} [see (5.3)] and also of h_{0}p_{0}d_{0}t_{1}h_{1}p_{1} … t_{r−1}h_{r−1}p_{r−1}d_{r−1}d′_{r−1} = σ_{1} [see (5.4)] by definition of d′_{r−1}. Hence

(6.13)  U_{3} = |σ_{1}|]t_{r}, p_{r}[.

To calculate U_{1} + U_{2} − U_{3} two cases are to be considered: (i) L σ = L σ_{1}; (ii) L σ ≠ L σ_{1}.

Case (i): The factor d′_{r−1} is nonempty. By (6.8) we have L σ = L d′_{r−1} < t_{r} and

−|p_{r−1}d_{r−1}d′_{r−1}|]t_{r}, p_{r−1}[−|d′_{r−1}|] L σ, p_{r}[+|p_{r−1}d_{r−1}d′_{r−1}|] L σ, p_{r−1}[ = 0.

There are three terms of the form |σ|_{]...[} in (6.11) and one in (6.13) and their contribution to U_{1} − U_{3} is

|σ_{1}|]t_{r}, p_{r−1}[ + |σ_{1}|] L σ, p_{r}[ − |σ_{1}|] L σ_{1}, p_{r−1}[ − |σ_{1}|]t_{r}, p_{r}[ = 0,

since L σ =L σ_{1}. Hence

U_{1} + U_{2} − U_{3} = |t_{r}h_{r}|] L σ, p_{r}[ + |σ_{1}|] L σ, +∞[ − des σ + |t_{r}\overline{d}_{r}|
= |σ_{1}|] L σ, +∞[ + |p_{r}\overline{d}_{r}t_{r}h_{r}| − des σ
= |σ|] L σ, +∞[ − des σ.

Case (ii): The factor d′_{r−1} is then empty and L σ_{1} = L p_{r−1}d_{r−1} > t_{r}, L σ > t_{r}, \overline{d}_{r} = d_{r}. Then

|σ_{1}|] L σ_{1}, +∞[ + |σ_{1}|]t_{r}, p_{r−1}[ + |σ_{1}|] L σ, p_{r}[ − |σ_{1}|] L σ_{1}, p_{r−1}[ − |σ_{1}|]t_{r}, p_{r}[

= |σ_{1}|] L σ_{1}, +∞[ + |σ_{1}|]t_{r}, L σ_{1}] − |σ_{1}|]t_{r}, L σ]

= \{ \begin{matrix}|σ_{1}|] L σ_{1}, +∞[ + |σ_{1}|] L σ, L σ_{1}], & if L σ < L σ_{1}; \\ |σ_{1}|] L σ_{1}, +∞[ − |σ_{1}|] L σ_{1}, L σ], & if L σ_{1} < L σ. \end{matrix}

= |σ_{1}|] L σ, +∞[.

Also −|p_{r−1}d_{r−1}d′_{r−1}|]t_{r}, p_{r−1}[−|d′_{r−1}|]L σ, p_{r}[+|p_{r−1}d_{r−1}d′_{r−1}|]L σ_{1}, p_{r−1}[=−1.

Hence

U_{1} + U_{2} − U_{3} = |σ_{1}|] L σ, +∞[ − des σ + |t_{r}h_{r}|] L σ, p_{r}[ + |t_{r}\overline{d}_{r}| − 1
= |σ_{1}|] L σ, +∞[ − des σ + |p_{r}d_{r}t_{r}h_{r}|] L σ, +∞[
= |σ|] L σ, +∞[ − des σ.

With the completion of Proposition 6.1 all the statements of Theorem 1.1 have been proved, except statement (iv). In fact, only the steps (4′) and (4′′) in the definition of D (see Section 5) modify the nature of some peaks, troughs, double-descents or double-rises. In (4′) the peak p_{0} becomes a double-rise, but troughs and double-descents remain alike. In (4′′) the rightmost letter of \overline{d}_{0}, a descent, becomes a trough. In both cases, the set of troughs and double-descents is not modified. This proves statement (iv).

7. Euler-Mahonian Statistics

Let us go back to the notation introduced by Babson and Steingrímsson [BaSt00] for “atomic” permutation statistics. For each permutation α, β, γ of a, b, c the expression (α βγ)(w) is meant to be 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. Of course, (ba)σ denotes the number of descents, des σ (i.e. the number of places 1 ≤ i < n such that x_{i} > x_{i+1}). Finally, [b a)σ is the number of of x_{j} such that x_{1} > x_{j}, that is, x_{1} − 1.

Using these atomic objects, Babson and Steingrímsson noticed that the two classical Mahonian statistics, the inversion number “inv” and the major index “maj” could be written in terms of those patterns. For instance, inv = (bc a)+(ca b)+(cb a)+(ba) and maj = (a cb)+(b ca)+ (c ba) + (ba). It is worth mentioning that an analogous notation has been introduced by Han ([Ha94], theorem 2.1) that enabled him to make a link between the major index and the Denert statistic. The former authors were then motivated to perform a computer search for all statistics that could be thus written and be “conjecturally Mahonian.” Several of the statistics they have introduced have been shown to be Mahonian since. However their Conjecture 11 has remained open (it will be stated later on). Our purpose will be to prove its correctness by using the previous algebraic set-up. Before doing so let us recall some basic notations and facts about Euler-Mahonian statistics.

As usual,

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

Also,

(7.3)  [n]_{q} := \frac{1 − q^{n}}{1 − q} = (1 + q + ⋯ + q^{n−1});
(7.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,

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

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

(7.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:

(7.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:

(7.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}.

The bistatistic that is Euler-Mahonian, par excellence, is the pair (des, maj). The proof of this statement goes back to Carlitz [Ca54], [Ca59], although some q-calculations for the major index already appeared in [Ma15]. Further bistatistics have since been introduced and proved to be Euler-Mahonian, in particular the pair (des, mak) (see [FoZe90]), where

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

Actually, the original “mak”, as introduced by Foata and Zeilberger [FoZe90], reads

(a cb) + (ca b) + (cb a) + (ba),

but Babson and Steingrímsson changed the notation. However, we shall stick with Definition (7.9) in the sequel. Notice that to prove that (des, mak) is Euler-Mahonian requires only a slight modification in the argument used in [FoZe90], § 8. Babson-Steingrímsson’s Conjecture 11 is the following.

Conjecture 11. Let

S_{1} := (a cb) + (b ac) + (cb a) + [b a),
S_{2} := (a cb) + (b ac) + (c ba) + [b a),
S_{3} := (a cb) + (b ca) + (cb a) + [b a),
S_{4} := (a cb) + (b ca) + (c ba) + [b a).

Then the bistatistics (des, S_{i}) for i = 1, 2, 3, 4 are Euler-Mahonian.

In the next section we prove that (des, S_{1}) and (des, S_{3}) are equidistributed with (des, mak) (this requires the machinery developed in the previous sections). The last section is devoted to proving that (des, S_{2}) and (des, S_{4}) are equidistrubuted with (des, maj). This is far easier.

8. The transformation Φ

The transformation

(8.1)  Φ := D^{−1}θ d,

already introduced in the introduction, maps the permutation group S_{n} onto itself. Let Φ^{−1} be the inverse bijection. As is often the case, such combinatorial bijections are now combined with the classical dihedral transformations, namely the reverse image r and the complement c that map each permutation σ = x_{1}x_{2} … x_{n} onto r σ = x_{n} … x_{2}x_{1} and c σ = (n + 1 − x_{1})(n + 1 − x_{2}) … (n + 1 − x_{n}), respectively.

Denote by Dbv σ the sum of the descent bottom values of the permutation σ, that is, the sum of the troughs and double-descents of σ. The following formula can be obtained by means of a simple counting:

(8.1)  Dbv = (a cb) + (cb a) + (ba).

It follows from (7.9) that “mak” can also be expressed as

(8.2)  mak = Dbv +(b ca).

Another statistic S will be used for technical reasons. It is defined by

(8.3)  S := Dbv +(b ca) + (ba) + L − n = mak +(ba) + L − n.

Statement (iv) of Theorem 1.1, that was proved at the end of Section 6, has two consequences, essential for the subsequent derivation:

(8.4) des Φ(σ) = des σ (or (ba)Φ(σ) = (ba)σ); (8.5) Dbv Φ(σ) = Dbv σ.

Theorem 8.1. The transformation r Φ^{−1} r Φ is a bijection of S_{n} onto itself having the property that

(8.6)  (des, S_{1})(r Φ^{−1} r Φ)(σ) = (des, mak) σ

holds for each permutation σ.

Theorem 8.2. The transformation r c Φ r c is a bijection of S_{n} onto itself having the property that

(8.7)  (des, S_{3})(r c Φ r c)(σ) = (des, mak) σ

holds for each permutation σ.

The first step in the proof of Theorem 8.1 is to establish the following identity

(8.8)  mak r Φ(σ) − mak r σ = L σ + F σ − F Φ(σ) + des Φ(σ) − n,

for each σ ∈ S_{n}.

By definition of “mak” we get

mak r = (bc a) + (ac b) + (a bc) + (ab).

Let T_{1} := (a bc) + (bc a) + (ab) and T_{2} := (b ac) + (ac b), so that mak r = T_{1} + T_{2} − (b ac). Let us evaluate T_{1} σ, T_{2} σ in terms of the factors of the peak factorization

0h_{0} | p_{1}d_{1}t_{1}h_{1} | p_{2}d_{2}t_{2}h_{2} | … | p_{r}d_{r}t_{r}h_{r}

of 0σ introduced in (4.1). When σ′′ = Φ(σ), let us also calculate T_{1} σ′′, T_{2} σ′′, in terms of the trough factorization

h′′_{0}p′′_{0}d′′_{0} | t′′_{1}h′′_{1}p′′_{1}d′′_{1} | t′′_{2}h′′_{2}p′′_{2}d′′_{2} | … | t′′_{s}h′′_{s}p′′_{s}d′′_{s},

of σ′′ introduced in § 5. We have added a double prime to all the factors to avoid any confusion with the factorization of σ. As θ(σ) is a rearrangement of the oiseau-word d σ and σ′′ = D^{−1}θ d σ, we have

(8.9)  θ(d σ) = D σ′′ = (∞0h′_{0})(p_{i_{1}}d_{i_{1}}t_{i_{1}}h′_{i_{1}}) … (p_{i_{r}}d_{i_{r}}t_{i_{r}}h′_{i_{r}}),

where, as seen in (4.3), the word h′_{0}h′_{1}h′_{2} … h′_{r} (and also h′_{0}h′_{i_{1}}h′_{i_{2}} … h′_{i_{r}}) is a rearrangement of h_{0}h_{1}h_{2} … h_{r}.

If x_{i} < x_{i+1} holds in the permutation σ = x_{1}x_{2} … x_{n}, then x_{i} is either a trough or a double-rise. The contribution of x_{i} to T_{1} σ is equal to x_{i} if i ≤ n − 1 and 0 if i = n. As, by convention, x_{n} is either a trough or a double-rise, we get:

T_{1} σ = ∑_{i=0}^{r} tot h_{i} + ∑_{i=1}^{r} t_{i} − L σ.

The same investigation of the contribution of each factor h_{i}p_{i+1} to T_{2} σ leads to the evaluation

\begin{aligned}T_{2} σ & = (p_{1} − F σ − |h_{0}|) + ∑_{i=2}^{r}(p_{i} − t_{i−1} − |h_{i−1}| − 1) + (L σ − t_{r} − |h_{r}|) \\ & = ∑_{i=1}^{r} p_{i} − ∑_{i=1}^{r} t_{i} − ∑_{i=0}^{r} |h_{i}| + L σ − F σ − (r − 1), \end{aligned}

so that

(8.10)  (T_{1} + T_{2})σ = ∑_{i=1}^{r} p_{i} + ∑_{i=0}^{r} tot h_{i} − ∑_{i=0}^{r} |h_{i}| − F σ − r + 1.

In the same manner,

T_{1} σ′′ = ∑_{i=0}^{s} tot h′′_{i} + ∑_{i=1}^{s} t′′_{i};

T_{2} σ′′ = (p′′_{0} − F σ′′ − |h′′_{0}|) + ∑_{i=1}^{s}(p′′_{i} − t′′_{i} − |h′′_{i}| − 1)

= ∑_{i=0}^{s} p′′_{i} − ∑_{i=1}^{s} t′′_{i} − ∑_{i=0}^{s} |h′′_{i}| − F σ′′ − s.

Hence

(8.11) (T_{1} + T_{2})σ′′ = ∑_{i=0}^{s} p′′_{i} + ∑_{i=0}^{s} tot h′′_{i} − ∑_{i=0}^{s} |h′′_{i}| − F σ′′ − s.

To pursue the calculation of (T_{1} + T_{2})σ′′ we have to take the steps (4′) and (4′′) in the construction of D, described in Section 5, into account. In case (4′)

D σ′ = (∞0h′′_{0}p′′_{0})(p′′_{1}\overline{d′′_{1}}t′′_{1}h′′_{1}) … (p′′_{s}\overline{d′′_{s}}t′′_{s}h′′_{s}),

so that, by comparison with (8.9),

(T_{1} + T_{2})σ′′ = ∑_{i=1}^{r} p_{i} + ∑_{i=0}^{r} tot h′_{i} − (∑_{i=0}^{r} |h′_{i}| − 1) − F σ′′ − r

= ∑_{i=1}^{r} p_{i} + ∑_{i=0}^{r} tot h_{i} − ∑_{i=0}^{r} |h_{i}| − F σ′′ − r + 1. (8.12)

In case (4′′)

D σ′′ = (∞0(h′_{0})′′)(p′′_{0}((\overline{d′_{0}})′′t′′_{0}(h′′_{0})′′)(p′′_{1}\overline{d′′_{1}}t′′_{1}h′′_{1}) ⋯ (p′′_{s}\overline{d′′_{s}}t′′_{s}h′′_{s}).

By comparison with (8.9)

(T_{1} + T_{2})σ′′ = ∑_{i=1}^{r} p_{i} + ∑_{i=0}^{r} tot h′_{i} − ∑_{i=0}^{r} |h′_{i}| − F σ′ − (r − 1)

= ∑_{i=1}^{r} p_{i} + ∑_{i=0}^{r} tot h_{i} − ∑_{i=0}^{r} |h_{i}| − F σ′ − r + 1. (8.13)

Thus, the two expressions for (T_{1} + T_{2})σ′′ in (8.12) and (8.13) coincide and

(8.14)  (T_{1} + T_{2})σ′′ − (T_{1} + T_{2})σ = F σ − F σ′′.

As mak r = T_{1} + T_{2} − (b ac), identity (8.3) will be proved if we show that

− (b ac)σ′′ + (b ac)σ = L σ + des σ′′ − n.

To do so we make use of the identity

(8.15)  (b ac) = (b ca) + (ba) + L − n,

that is straightforward to prove by induction, and of (1.1) that rewrites

(b ca)σ′′ = (b ca)σ + n − L σ′′ − des σ′′.

Because (ba)σ′′ = (ba)σ by (8.4), we get:

− (b ac)σ′′ + (b ac)σ = −(b ca)σ′′ + (b ca)σ − L σ′′ + L σ
= −(b ca)σ − n + L σ′′ + des σ′′
+ (b ca)σ − L σ′′ + L σ
= L σ + des σ′′ − n.

Lemma 8.3. The two identities hold: S Φ = mak and S_{1} r = S r Φ.

Proof. We have:

S Φ = Dbv Φ + (b ca)Φ + (ba)Φ − n + L Φ  [by (8.3)]
= Dbv +(b ca)Φ + (ba)Φ − n + L Φ  [by (8.5)]
= Dbv +((b ca) + n − L Φ − (ba)Φ) + (ba)Φ − n + L Φ [by (1.1)]
= Dbv +(b ca) = mak .  [by (8.2)]

On the other hand, the statistic S_{1} can be rewritten as:

(8.16)  S_{1} = mak + F + L −n − 1.

Hence, as des r = n − 1 − des and L r = F, we have:

S r Φ = mak r Φ + des r Φ + L r Φ − n  [by (8.3)]

= (mak r + L + F − F Φ + des Φ − n)

+ (n − 1 − des Φ) + F Φ − n [by (8.8)]

= mak r + F r + L r − n − 1 = S_{1} r.

It follows from Lemma 8.3 that S_{1} r Φ^{−1} r = S, so that S_{1} r Φ^{−1} r Φ = S Φ = mak. Also des r Φ^{−1} r Φ = des, by (8.4) and the fact that r occurs twice in the expression of the transformation r Φ^{−1} r Φ. This achieves the proof of Theorem 8.1.

The proof of Theorem 8.2 is much simpler. It is based upon the straightforward identities:

(8.17)  des r c = des and mak r c = n des − mak .

First,

des r c Φ r c = des r c Φ  [by (8.17)]
= des r c  [by (8.4)]
= des .  [by (8.17)]

Then, notice that the statistic S_{3} is also equal to

(8.18)  S_{3} = mak − des + F − 1.

Hence

S_{3} r c Φ = mak r c Φ − des r c Φ + F r c Φ − 1  [by (8.18)]
= (n des Φ − mak Φ) − des Φ + (n + 1 − L Φ) − 1 [by (8.17)]

= n des −(mak Φ + des Φ + L Φ − n)

= n des −S Φ  [by (8.3)]
= n des − mak  [by Lemma 8.3]
= mak r c.  [by (8.17)]

Thus S_{3} r c Φ r c = mak. This achieves the proof of Theorem 8.2.

9. The other statistics S_{2} and S_{4}

Those statistics will be compared with the major index “maj” that reads maj = (a cb) + (b ca) + (c ba) + (ba). First,

S_{2} − maj = (b ac) − (b ca) + [b a) − (ba).

As (b ac) + (b a] = (b ca) + (ba), we have S_{2} − maj = [b a) − (b a]. Also S_{4} − maj = (b a) − (ba).

With each permutation σ = x_{1}x_{2} … x_{n} associate σ′ = x′_{1}x′_{2} … x′_{n}, where x′_{i} − x_{i} ≡ n + 1 − x_{n} − x_{1} (mod n). Then, σ ↦ σ′ is an involution, for (x′_{i})′ ≡ x′_{i} + n + 1 − x′_{n} − x′_{1} ≡ (x_{i} + n + 1 − x_{n} − x_{1}) + n + 1 − (x_{n} + n + 1 − x_{n} − x_{1}) − (x_{n} + n + 1 − x_{n} − x_{1}) ≡ x_{i}. Moreover, des σ′ = des σ and

maj σ′ = maj σ + x_{1} + x_{n} − n − 1
= maj σ + [b a)σ − (b a]σ = S_{2} σ.

This shows that (des, S_{2}) is equidistributed with (des, maj).

What about S_{4}? We have S_{4} σ = maj σ + (b a)σ − (ba)σ = maj σ + x_{1} − 1 − des σ. Consider the transformation that maps the permutation σ = x_{1}x_{2} … x_{n} onto \overline{σ} = \overline{x}_{1}\overline{x}_{2} … \overline{x}_{n}, where \overline{x}_{n} := n + 1 − x_{1} and

\overline{x}_{i} ≡ x_{i+1} − x_{1} (mod (n + 1)) (i = 1, 2, …, n − 1).

The map σ ↦ σ′ not involutive, but is a bijection of S_{n} onto itself and

des \overline{σ} = des σ;
maj \overline{σ} = maj σ + x_{1} − 1 − des σ = S_{4} σ.

Again (des, S_{4}) is another bistatistic equidistributed with (des, maj). Thus, Conjecture 11 is correct.

Acknowledgements. The authors thank Einar Steingrímsson for his careful and knowledgeable reading of the paper.

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.

[CaFo69] Pierre Cartier and Dominique Foata, Problèmes combinatoires de permutations et réarrangements. Berlin, Springer-Verlag, 1969 (Lecture Notes in Math., 85).

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

[Du04] Gérard Duchamp, Oral communication, 2004.

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

[Ha94] Guo-Niu Han, Une transformation fondamentale sur les réarrangements de mots, Advances in Math., 105, 1994, 26–41.

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

Dominique Foata Institut Lothaire 1, rue Murner F-67000 Strasbourg, France

foata@math.u-strasbg.fr

Arthur Randrianarivony Faculté des Sciences Université d’Antananarivo Antananarivo, Madagascar

                           arthur@univ-antananarivo.mg