Anisse Kasraoui

Jiang Zeng
email: zeng@math.univ-lyon1.fr

EULER-MAHONIAN STATISTICS ON ORDERED SET PARTITIONS (II)

Keywords: ordered set partitions, σ-partitions, Euler-Mahonian statistics, p, q-Stirling numbers of the second kind, path diagrams, inversion, major index, block inversion number, block major index. MR Subject Classifications: Primary 05A18; Secondary 05A15, 05A30

Euler-Mahonian statistics on ordered set partitions (II)

Anisse Kasraoui, Jiang

Introduction

The systematic study of statistics on permutations and words has its origins in the work of MacMahon [START_REF] Macmahon | Combinatorial Analysis[END_REF]. In this paper, we will consider MacMahon's three statistics for a word w: the number of descents (des w), the number of inversions (inv w), and the major index (maj w). These are defined as follows: A descent in a word π = a 1 a 2 • • • a n is an i such that a i > a i+1 , an inversion is a pair (i, j) such that i < j and a i > a j , and the major index of w is the sum of the descents in π. The rearrangement class R(w) of a word w = a 1 a 2 • • • a n is the set of all words obtained by permutating the letters of w.

Let n = (n 1 , . . . , n k ) be a sequence of non negative integers and R(n) the rearrangement class of the word 1 n 1 . . . k n k . Then MacMahon [START_REF] Andrews | The Theory of Partitions[END_REF]Chap. 3] proved that w∈R(n)

q inv w = w∈R(n) q maj w = (q; q) n 1 +•••+n k (q; q) n 1 • • • (q; q) n k , (1.1)
where (x; q) n = (1x)(1xq) • • • (1xq n-1 ). In particular, for the symmetric group S n of [n] := {1, 2, • • • , n}, we have σ∈ Sn

q inv σ = σ∈ Sn q maj σ = [n]! q , (1.2)
where [n]

q = 1 + q + • • • q n-1 and [n] q ! = [1] q [2] q • • • [n] q .
Any statistic that is equidistributed with des is said to be Eulerian, while any statistic equidistributed with inv is said to be Mahonian. A bivariate statistic (eul, mah) is said to be a Euler-Mahonian statistic if eul is Eulerian and mah is Mahonian.

An ordered partition of [n] is a sequence of disjoint and nonempty subsets, called blocks, whose union is [n]. The blocks of an ordered partition will be written as capital letters separated by slashes, while elements of the blocks will be set in lower case. Thus an ordered partition of [n] into k blocks is written as π = B 1 /B 2 / • • • /B k . Clearly we can identify an unordered partition with an ordered partition by arranging the blocks in the increasing order of their minima, called its standard form. For example, the partition π of [START_REF] Garsia | Q-counting rook configurations and a formula of Frobenius[END_REF] consisting of the five blocks {1, 4, 7}, {2}, {3, 9}, {5} and {6, 8} will be written as π = 1 4 7/2/3 9/5/6 8. The set of all partitions of [n] into k blocks will be denoted by P k n . It is well-known that the Stirling number of the second kind S(n, k) equals the cardinality of P k n . Therefore, if OP k n denotes the set of all ordered partitions of [n] into k blocks, then |OP k n | = k! S(n, k). For any ordered partition π ∈ OP k n there is a unique partition

π 0 = B 1 /B 2 / • • • /B k ∈ P k
n and a unique permutation σ ∈ S k such that π = B σ(1) /B σ(2) / • • • /B σ(k) . In parallel with notion of σ-restricted growth function in [START_REF] Wachs | σ-Restricted Growth Functions and p,q-stirling numbers[END_REF], we shall call the corresponding partition π a σ-partition. Let P k n (σ) be the set of all σ-partitions of [n] into k blocks. For instance, π = 6 8/5/1 4 7/3 9/2 ∈ P 5 9 (σ) with σ = 54132. Clearly, for any σ ∈ S k we have |P k n (σ)| = |P k n | = S(n, k) and P k n = P k n (ε) where ε is the identity permutation.

The p, q-Stirling numbers of the second kind S p,q (n, k) were introduced in [START_REF] Wachs | q-Stirling numbers and set partition statistics[END_REF] by the recursion:

S p,q (n, k) =    p k-1 S p,q (n -1, k -1) + [k] p,q S p,q (n -1, k), if 0 < k ≤ n; 1,
if n = k = 0; 0, otherwise.

(

where

[k] p,q = p k-1 + p k-2 q + • • • + pq k-1 + q k-1 .
When p or q is set to 1, we obtain two usual q-Stirling numbers of the second kind (see [START_REF] Gould | The q-Stirling numbers of the first and second kinds[END_REF]): S q (n, k) := S q,1 (n, k) and S q (n, k) := S 1,q (n, k) = q -( k 2 ) S q (n, k) (1.4) Many authors (see e.g. [START_REF] Ehrenborg | Juggling and applications to q-analogues[END_REF][START_REF] Garsia | Q-counting rook configurations and a formula of Frobenius[END_REF][START_REF] Ishikawa | Euler-Mahonian statistics on ordered set partitions[END_REF][START_REF] Ksavrelof | Nouvelles statistiques de partitions pour les q-nombres de Stirling de seconde espèce[END_REF][START_REF] Milne | Restricted growth functions, rank row matching of partition lattices, and q-Stirling numbers[END_REF][START_REF] Remmel | Rook theory, generalized Stirling numbers and (p,q)-analogues[END_REF][START_REF] Sagan | A maj statistic for set partitions[END_REF][START_REF] Steingrímsson | Statistics on ordered partitions of sets[END_REF][START_REF] Wachs | σ-Restricted Growth Functions and p,q-stirling numbers[END_REF][START_REF] Wachs | q-Stirling numbers and set partition statistics[END_REF][START_REF] White | Interpolating Set Partition Statistics[END_REF]) have explored the combinatorial aspects of these q-Stirling numbers. In particular, Wachs and White [START_REF] Wachs | q-Stirling numbers and set partition statistics[END_REF] studied the combinatorial interpretations of these p, q-Stirling numbers. In a sequel paper Wachs [START_REF] Wachs | σ-Restricted Growth Functions and p,q-stirling numbers[END_REF] extended some unordered partition interpretations of p, q-Stirling number of the second kind to σ-partition statistics, although she used the restricted growth functions instead of set partitions.

A statistic STAT on ordered set partitions is Euler-Mahonian if for any

n ≥ k ≥ 1 its distribution over OP k n equals [k] q !S q (n, k), i.e., π∈ OP k n q STAT π = [k] q ! S q (n, k).
In [START_REF] Steingrímsson | Statistics on ordered partitions of sets[END_REF] Steingrímsson conjectured several hard Euler-Mahonian statistics on OP k n . In a previous paper [START_REF] Ishikawa | Euler-Mahonian statistics on ordered set partitions[END_REF], Ishikawa and the two current authors proved half of the conjectures of Steingrímsson [START_REF] Steingrímsson | Statistics on ordered partitions of sets[END_REF] by using the Matrix-transfer method and determinant computations.

The aim of this paper is to give a complete bijective approach to Steingrímsson's problem. In particular, we will not only derive the results in [START_REF] Ishikawa | Euler-Mahonian statistics on ordered set partitions[END_REF] bijectively but also settle the remaining half of the conjectures. In fact our bijective approach yields also new results on p, q-Stirling numbers of Wachs and White [START_REF] Wachs | q-Stirling numbers and set partition statistics[END_REF] and the σ-partitions of Wachs [START_REF] Wachs | σ-Restricted Growth Functions and p,q-stirling numbers[END_REF]. As we will show, one of our results generalizes MacMahon's equidisribution result of inversion number and major index on words.

Throughout this paper, we shall denote by P (resp. N, Z) the set of positive integers (resp. non negative integers, integers) and assume that n and k are two fixed integers satisfying n ≥ k ≥ 1. Furthermore, for any integers i 1 , i 2 , . . . , i k , we denote by {i 1 , i 2 , . . . , i k } < (resp. {i 1 , i 2 , . . . , i k } > ) the increasing (resp. decreasing) arrangement of these integers.

Definitions

Let B be a finite subset of N. The opener of B is its least element while the closer of B is its greatest element. For π ∈ OP k n , we will denote by open(π) and clos(π) the sets of openers and closers of the blocks of π, respectively. The letters (integers) in π are further divided into four classes:

• singletons: elements of the singleton blocks;

• strict openers: smallest elements of the non singleton blocks;

• strict closers: largest elements of the non singleton blocks;

• transients: all other elements, i.e., non extremal elements of non singleton blocks.

The sets of strict openers, strict closers, singletons and transients of π will be denoted, respectively, by O(π), C(π), S(π) and T (π). Let OP k n (λ) be the set of ordered partitions in OP k n of type λ. Following Steingrímsson [START_REF] Steingrímsson | Statistics on ordered partitions of sets[END_REF], we now define a system of ten inversion-like statistics on ordered set partitions. Most of them have been studied in the case of set partitions. Note that the two last statistics were essentially defined by Foata and Zeilberger [START_REF] Foata | Denert's permutation statistic is indeed Euler-Mahonian[END_REF] for permutations. The reader is refered to [START_REF] Ksavrelof | Nouvelles statistiques de partitions pour les q-nombres de Stirling de seconde espèce[END_REF][START_REF] Steingrímsson | Statistics on ordered partitions of sets[END_REF][START_REF] Wachs | σ-Restricted Growth Functions and p,q-stirling numbers[END_REF] for further informations of these statistics.

Given

a partition π = B 1 /B 2 / • • • /B k ∈ OP k n
, let w i be the index of the block (counting from left to right) containing i, namely the integer j such that i ∈ B j . Then define ten coordinate statistics as follows. For 1 ≤ i ≤ n, we let:

los i π = #{j ∈ open π | j < i, w j < w i }, ros i π = #{j ∈ open π | j < i, w j > w i }, lob i π = #{j ∈ open π | j > i, w j < w i }, rob i π = #{j ∈ open π | j > i, w j > w i }, lcs i π = #{j ∈ clos π | j < i, w j < w i }, rcs i π = #{j ∈ clos π | j < i, w j > w i }, lcb i π = #{j ∈ clos π | j > i, w j < w i }, rcb i π = #{j ∈ clos π | j > i, w j > w i }.
Moreover, let rsb i π (resp. lsb i π) be the number of blocks B in π to the right (resp. left) of the block containing i such that the opener of B is smaller than i and the closer of B is greater than i. Remark that lsb i and rsb i are each equal to the difference of two of the first eight statistics. Namely, it is easy to see that lsb i = los ilcs i = lcb ilob i and rsb i = ros ircs i = rcb irob i .

(2.1)

Then define the statistics ros, rob, rcs, rcb, lob, los, lcs, lcb, lsb and rsb as the sum of their coordinate statistics, e.g.

ros = ros 1 + • • • ros n .
For any partition π we can define the restrictions of these statistics on openers and non openers ros OS , ros T C , ..., rsb OS and rsb T C , e.g.

ros OS π = i∈ O∪S(π) ros i π and ros T C π = i∈ T ∪C(π) ros i π. (2.2)
Remark 2.1. Note that ros is the abbreviation of "right, opener, smaller", while lcb is the abbreviation of "left, closer, bigger", etc.

As an example, we give here the values of the coordinate statistics computed on π = 6 8/5/1 4 7/3 9/2: π = 6 8 / 5 / 1 4 7 / 3 9 / 2 los i : 0 0 / 0 / 0 0 2 / 1 3 / 1 ros i : 4 4 / 3 / 0 2 2 / 1 1 / 0 lob i : 0 0 / 1 / 2 2 0 / 2 0 / 3 rob i : 0 0 / 0 / 2 0 0 / 0 0 / 0 lcs i : 0 0 / 0 / 0 0 1 / 0 3 / 0 rcs i :

2 3 / 1 / 0 1 1 / 1 1 / 0 lcb i : 0 0 / 1 / 2 2 1 / 3 0 / 4 rcb i : 2 1 / 2 / 2 1 1 / 0 0 / 0 lsb i : 0 0 / 0 / 0 0 1 / 1 0 / 1 rsb i : 2 1 / 2 / 0 1 1 / 0 0 / 0 It follows that ros OS π = 8 and rsb T C π = 3.
The following result is due to Wachs and White [START_REF] Wachs | q-Stirling numbers and set partition statistics[END_REF]Cor. 5.3].

π∈P k n p rcb π q lsb π = S p,q (n, k). (2.3) Let π = B 1 /B 2 / • • • /B k ∈ OP k n .
Define a partial order ≻ on blocks B i 's as follows : B i ≻ B j if all the letters of B i are greater than those of B j , i.e., if min(B i ) > max(B j ). A block inversion in π is a pair (i, j) such that i < j and B i ≻ B j . We denote by bInv π the number of block inversions in π. A block descent is an integer i such that B i ≻ B i+1 . The block major index of π, denoted by bMaj π, is the sum of the block descents in π. We also define their complementary counterparts:

cbInv = k 2 -bInv cbMaj = k 2 -bMaj, (2.4)
and two composed statistics:

cinvLSB = lsb + cbInv + k 2 , cmajLSB = lsb + cbMaj + k 2 .
(2.5)

For any σ-partition π ∈ P k n (σ) with σ ∈ S k , we can define two natural statistics : Inv π = inv σ and Maj π = maj σ.

(2.6)

The following two statistics are the (ordered) partition analogues of their counterparts in permutations [19, p.13]:

MAK = ros + lcs, MAK ′ = lob + rcb . (2.7)
In what follows we will also denote by MAG any of these two statistics, i.e., MAG ∈ {MAK, MAK ′ }.

(2.8)

Main results

We first present our main result on the equidistribution of some inversion like statistics on σ-partitions. Theorem 3.1. For any σ ∈ S k , the triple statistics (MAK+bInv, MAK ′ +bInv, cinvLSB) and (MAK ′ + bInv, MAK + bInv, cinvLSB) are equidistributed on P k n (σ). Moreover,

π∈P k n (σ)
p (MAG+bInv) π q cinvLSB π = q k(k-1) p q inv σ S p,q (n, k).

(3.1)

Note that (3.1) gives two σ-extensions of (2.3), which is the σ = ǫ case of (3.1).

As inv is a Mahonian statistic on S k , summing the two sides over all the permutations σ in S k , we derive immediately from (3.1) the main result of [START_REF] Ishikawa | Euler-Mahonian statistics on ordered set partitions[END_REF], of which the second part was conjectured by Steingrímsson [START_REF] Steingrímsson | Statistics on ordered partitions of sets[END_REF].

Theorem 3.2 (Ishikawa et al.). We have

π∈OP k n p (MAG+bInv)π q cinvLSB π = q ( k 2 ) [k] p,q ! S p,q (n, k). (3.2)
In particular the three statistics

MAK + bInv, MAK ′ + bInv, cinvLSB (3.3)
are Euler-Mahonian on OP k n . For the major like statistics we have the following equidistribution result on ordered partitions with a fixed type. Theorem 3.4. We have

π∈OP k n p (MAG+bMaj)π q cmajLSB π = q ( k 2 ) [k] p,q ! S p,q (n, k). (3.4)
In particular the three statistics

MAK + bMaj, MAK ′ + bMaj, cmajLSB (3.5) are Euler-Mahonian on OP k n . For any set partition π ∈ P k n , denote by R(π) the rearrangement class of π, i.e., if π = B 1 /B 2 / • • • /B k , then R(π) = {B σ(1) /B σ(2) / • • • /B σ(k) | σ ∈ S k }. For instance, if π = 1 4/2 3/5, then R(π) = {1 4/2 3/5 , 1 4/5/2 3 , 5/2 3/1 4 , 2 3/1 4/5 , 2 3/5/1 4 , 5/1 4/2 3}. It is clear that |R(π)| = k! for any partition π with k blocks.
Introduce first two analogues of inversion numbers and major index on OP k n :

INV = rsb OS + bInv, MAJ = rsb OS + bMaj . (3.6)
The statistic INV is just a rewording of the inversion number inv in (2.6). Indeed, it is easy to see that bInv = rcs OS and Inv = ros OS , therefore

INV = rsb OS + rcs OS = ros OS = Inv . (3.7)
Our last result is a non trivial extension of MacMahon's identity (1.1) to rearrangement class of an arbitrary partition.

q MAJ π = π∈R(π) q INV π = [k] q !. (3.8)
To show that (3.8) implies MacMahon's formula (1.1), we consider the rearrangement class of a special set partition as follows. Let

N i = n 1 + • • • + n i for i = 1, . . . , k and Π = π 11 . . . π 1n 1 π 21 . . . π 2n 2 . . . π k1 . . . π kn k be the partition of [2N k ]
consisting of the doubletons:

π ij := {2N i-1 + j, 2N i-1 + n i + j}, ( 1
≤ i ≤ k, 1 ≤ j ≤ n i , N 0 = 0).
It is readily seen that each π ∈ R(Π) can be identified with a pair (w, (π 1 , . . . , π k )) where w ∈ R(n) is the word obtained from π by substituting each π ij by i for 1 ≤ i ≤ k and π i is the word obtained from π by deleting all the π lj for l = i. For example, if k = 3,

n 1 = 3, n 2 = 2 and n 3 = 3 then Π = {1, 4} {2, 5} {3, 6} {7, 9} {8, 10} {11, 14} {12, 15} {13, 16}.
Let π ∈ R(Π) be the ordered partition:

π = {7, 9} {2, 5} {11, 14} {1, 4} {13, 16} {12, 15} {3, 6} {8, 10}.
Then π → (w, (π 1 , π 2 , π 3 )) with w = 2 1 3 1 3 3 2 1 and

π 1 = {2, 5} {1, 4} {3, 6}, π 2 = {7, 9} {8, 10}, π 3 = {11, 14} {13, 16} {12, 15}. Note that for any i, j, l, r such that 1 ≤ i, j ≤ k, 1 ≤ l ≤ n i and 1 ≤ r ≤ n j , π il ≺ π jr ⇐⇒ i < j, therefore bMaj π = maj w, bInv π = inv w and rsb OS π = rsb OS π 1 + • • • + rsb OS π k .
It then follows from (3.6) that π∈R(Π)

q MAJπ =   w∈R(n) q maj w   k i=1 π∈R(π i ) q rsb OS π , (3.9)
π∈R(Π)

q INVπ =   w∈R(n) q inv w   k i=1 π∈R(π i ) q rsb OS π . (3.10)
As rcs OS (π) = 0 for any π ∈ R(π i ) we have INV = rsb OS on R(π i ). Hence, by Theorem 3.5,

π∈R(π i ) q rsb OS π = [n i ] q !, 1 ≤ i ≤ k,
and

π∈R(Π) q INVπ = [N k ] q !.
MacMahon's formula (1.1) follows then from (3.9) and (3.10) by invoking Theorem 3.5. The rest of this paper is organized as follows. In Section 4 we shall present the first path diagrams encoding of ordered partitions Φ : ∆ k n -→ OP k n , which was introduced in [START_REF] Ishikawa | Euler-Mahonian statistics on ordered set partitions[END_REF]. We will construct an involution on path diagrams ϕ : ∆ k n -→ ∆ k n in Section 5 and a bijection Γ σ from set partitions to ordered set partitions in Section 6. We prove Theorem 3.1 in section 7. To deal with major like statistics a second path diagram encoding Ψ : ∆ k n -→ OP k n will be given in Section 8. Then, in Section 9 we prove Theorem 3.4 by using the mapping Υ :

= Ψ • Φ -1 : OP k n → OP k n .
Finally we prove Theorem 3.6 in Section 3.6 and conclude the paper with some further remarks.

The first path diagram encoding Φ of ordered partitions

As shown in [START_REF] Ishikawa | Euler-Mahonian statistics on ordered set partitions[END_REF], we can define the notion of trace or skeleton for ordered partitions. To this end, adjoin to P a symbol ∞ such that i < ∞ for any positive integer i. The restriction of a subset

B of P on [i], namely B ∩ [i], is said to be • empty if i < min B, • active if min B ≤ i < max B, • complete if max B ≤ i. Let π ∈ OP k n .
For 1 ≤ i ≤ n the i-trace or i-skeleton T i of π is obtained by restricting each block on [i] and deleting empty blocks. By convention, we add a symbol ∞ at the end of each active block. By convention, the latter is still called block.

Clearly one can characterize a partition and the statistics ros and rsb by using its traces. More precisely, for any 1 ≤ i ≤ n, ros i π (resp. rsb i π) equals the number of blocks (resp. active blocks) to the right of the block containing i in the i-trace T i of π. A useful way to describe the traces of a partition is to draw a path diagram. Definition 4.1. A path of depth k and length n is a sequence w = (w 0 , w 1 , . . . , w n ) of points in N 2 such that w 0 = (0, 0), w n = (k, 0) and the i-th (1 ≤ i ≤ n) step (w i-1 , w i ) must be one of the following four types:

• North, i.e., w iw i-1 = (0, 1),

• East, i.e., w i -

w i-1 = (1, 0), • South-East, i.e., w i -w i-1 = (1, -1),
• Null, i.e., w iw i-1 = (0, 0) and

y i > 0 if w i = (x i , y i ).
The abscissa and ordinate of w i-1 are called the abscissa and height of the i-th step of w and denoted by x i (w) and y i (w), respectively. The set of all paths of depth k and length n will be denoted by Ω k n . We can visualize a path w by drawing a segment or loop from w i-1 to w i in the xy plane. For instance, the path w = ((0, 0), (0, 1), (0, 2), (0, 3), (0, 3), (0, 3), (1, 3), (2, 2), (3, 1), (4, 1), (5, 0)), is illustrated in Figure 1. For the reason which will be clear later, the sets of indices of North, South-East, East and Null steps of a path w will be denoted by O(w), C(w), S(w) and T (w), respectively. The 4-tuple (O(w), C(w), S(w), T (w)), denoted by λ(w), is called the type of w. For instance, if w is the path represented in Figure 1, then

λ(w) = ({1, 2, 3}, {7, 8, 10}, {6, 9}, {4, 5}). Definition 4.2. A path diagram of depth k and length n is a pair (w, γ), where w is a path in Ω k n and γ = (γ i ) 1≤i≤n is a sequence of integers such that • 0 ≤ γ i ≤ y i (w) -1 if the i-th step of w is Null or South-East, • 0 ≤ γ i ≤ x i (w) + y i (w) if the i-th step of w is North or East. Let ∆ k
n be the set of path diagrams of depth k and length n. For any statement A we denote by χ(A) the character function of A, that means

χ(A) = 1 if A is true and χ(A) = 1 if A is false. Lemma 4.3. Let w ∈ Ω k n and (w, γ) ∈ ∆ k n with O ∪ S(w) = {i 1 , i 2 , . . . , i k } < . Then (i) x i + y i = x i-1 + y i-1 + χ(i ∈ O ∪ S(w)) for i = 1, . . . , n. (ii) x i j + y i j + 1 = j for j = 1, 2, . . . , k.
Proof. Since x 1 (w) + y 1 (w) = 0 and each step is one of the four kinds: (0, 1), (1, 0), (0, 0) and (1, -1), the sum x i + y i increases by one if and only if the i-th step is North or South. This yields (i), while (ii) is a direct consequence of (i).

One can encode ordered partitions by path diagrams. The following important bijection Φ : ∆ k n → OP k n was introduced in [START_REF] Ishikawa | Euler-Mahonian statistics on ordered set partitions[END_REF]. Algorithm Φ: Starting from a path diagram h = (w, γ) in ∆ k n , we obtain Φ(h) = π by constructing recursively all the i-traces T i (1 ≤ i ≤ n) of π, i.e., such that π = T n . By convention T 0 = ∅. Assume that we have constructed

T i-1 = B i 1 /B i 2 / • • • /B i ℓ such that T i-1
has y i (w) active blocks and x i (w) complete blocks. Label the slots before B i 1 , between B i j and B i j+1 , for 1 ≤ j ≤ ℓ -1, and after B i ℓ from left to right by ℓ, . . . , 1, 0, while the active blocks of T i-1 are labeled from left to right by y i (w) -1, . . . , 1, 0. Extend T i-1 to T i as follows:

• If the i-th step of w is North (resp. East), then create an active block (resp. singleton) with i at the slot with label γ i ; • If the i-th step of w is Null (resp. South-East), then insert i (resp. replace ∞ by i) in the active block with label γ i . Since x n+1 (w) = k and y n+1 (w) = 0, the n-trace T n is a partition in OP k n . Example 4.2. Consider the path diagram h = (w, γ) ∈ ∆ 5 10 , where w is the path in Figure 1 and γ = (0, 0, 2, 1, 2, 3, 2, 0, 1, 0), then Φ(h) = 6/3 5 7/1 4 10/9/2 8. The step by step construction of Φ(h) is given in Figure 2, where the i-th step is labeled with γ i for 1 ≤ i ≤ 10.

The main properties of Φ are given in the following theorem of Ishikawa et al [START_REF] Ishikawa | Euler-Mahonian statistics on ordered set partitions[END_REF].

γ i = ros i (π), if i ∈ O(π) ∪ S(π); rsb i (π), if i ∈ T (π) ∪ C(π).
It follows that

ros OS π = i∈O∪S(w) γ i and rsb T C π = i∈T ∪C(w) γ i . (4.1)

Involution ϕ on path diagrams

For any path w ∈ Ω k n , one can define a natural bijection between the North steps and South-East steps of w. More precisely, let

O(w) = {o 1 , o 2 , • • • , o r } < and C(w) = {c 1 , c 2 , • • • , c r } < .
We define the permutation σ ∈ S r , called the associated permutation of w, as follows: Suppose the height of the i-th North step of w (i.e. the o i -th step of w) is t. Since w 0 = (0, 0) and w n = (k, 0), there must exist a South-East step of height t + 1 to the right of the o i -th step. If the first such step is the j-th South-East step (i.e. the c j -th step of w), set σ(i) = j. Since there is at least one South-East step of height t + 1 between any For a subset A ⊆ [n], the complement set A is obtained by replacing each i ∈ A by i := n + 1i. The reverse path of w is the path w whose i-th step is North (resp. East, Null, South-East) if and only if the (n + 1i)-th step of w is South-East (resp. East, Null, North). Clearly, if w ∈ Ω k n with λ(w) = (O, C, S, T ), then we can also define w as the unique path satisfying λ(w) = λ(w) := (C, O, S, T ).

h = ✲ ✻ 0 0 2 1,2 3 2 0 1 0 ❄ Φ i step i γi Ti 0 ∅ 1 N orth 0 1 ∞ 2 N orth 0 1 ∞/2 ∞ 3 N orth 2 3 ∞/1 ∞/2 ∞ 4 N ull 1 3 ∞/1 4 ∞/2 ∞ 5 N ull 2 3 5, ∞/1 4, ∞/2 ∞ 6 East 3 6/3 5 ∞/1 4 ∞/2 ∞ 7 South-East 2 6/3 5 7/1 4 ∞/2 ∞ 8
Lemma 5.1. The mapping w → w is an involution on Ω k n . Moreover, (1) For i ∈ [n], we have y i (w) = y i+1 (w). In particular, we have:

y i (w) =    y i (w) -1, if i ∈ O(w); y i (w), if i ∈ T ∪ S(w); y i (w) + 1, if i ∈ C(w).
(5.1)

(2) Suppose |O(w)| = r and let σ and σ ′ be the associated permutations of w and w respectively. Then for any j ∈ [r],

σ ′ (j) = r + 1 -σ -1 (r + 1 -j).
(5.2)

Proof.

(1) By definition of w, the height of the i-step of w corresponds to the height of the ī + 1-th step of w, so y i (w) = y i+1 (w). Eq. (5.1) follows then from the fact that λ( w) = λ(w) and the equation:

y i+1 (w) =    y i (w) + 1 if i ∈ O(w); y i (w) if i ∈ T ∪ S(w); y i (w) -1 if i ∈ C(w).
(2) By definition, for any j ∈ [r], the mapping σ maps the j-th North step of w to the σ(j)-th South-East step of w. Equivalently the mapping σ ′ maps the r + 1σ(j)-th North step of w to the r + 1j-th South-East step of w. In other words, we have σ ′ (r + 1σ(j)) = r + 1j. Substituting r + 1σ(j) by i yields the desired result.

We have now all the ingredients to define our involution ϕ on ∆ k n .

Involution ϕ. Let h = (w, γ) ∈ ∆ k n such that O ∪ S(w) = {i 1 , i 2 , • • • , i k } < , T (w) = {t 1 , t 2 , • • • , t u } < and C(w) = {c 1 , c 2 , • • • , c r } < . If O ∪ S(w) = {i ′ 1 , i ′ 2 , • • • , i ′ k } < , T (w) = {t ′ 1 , t ′ 2 , • • • , t ′ u } < and C(w) = {c ′ 1 , c ′ 2 , • • • , c ′ r } < , then ϕ(h) = (w, ξ)
, where ξ = (ξ i ) 1≤i≤n is defined as follows:

ξ i =    γ im , if i = i ′ m for m ∈ [k]; γ t u+1-m , if i = t ′ m for m ∈ [u]; γ c σ(r+1-m) , if i = c ′ m for m ∈ [r]; (5.3)
where σ is the associated permutation of w.

Example 5.1. Consider the path diagram h = (w, γ) in the Figure 4. It is easy to see that the permutation associated to w is σ = 321. It follows that

ξ c ′ 1 = γ c σ(3) = γ c 1 , ξ c ′ 2 = γ c σ(2) = γ c 2 and ξ c ′ 3 = γ c σ(1) = γ c 3 .

The image ϕ(h) of h is given below.

We now present the main result of this section.

ξ i = i∈O∪S(w)
γ i and i∈T ∪C(w)

ξ i = i∈T ∪C(w) γ i . (5.4)
Proof. We first show that the mapping ϕ is well defined. It suffices to show that:

(a) 0 ≤ ξ i ′ m ≤ x i ′ m (w) + y i ′ m (w) for m ∈ [k], (b) 0 ≤ ξ t ′ m ≤ y t ′ m (w) -1 for m ∈ [u], and (c) 0 ≤ ξ c ′ m ≤ y c ′ m (w) -1 for m ∈ [r]. Since t ′ m = t u+1-m and c ′ m = o r+1-m , we have t ′ m = t u+1-m = t u+1-m and c ′ m = o r+1-m = o r+1-m . (i) For m ∈ [k], Lemma 4.3(ii) implies that x i ′ m (w) + y i ′ m (w) = x im (w) + y im (
ϕ 2 : (w, γ) ϕ -→ (w, γ) ϕ -→ (w, µ) = (w, µ)
where µ = (µ i ) 1≤i≤n is defined by

µ i =    ξ i ′ m , if i = i m for m ∈ [k]; ξ t ′ u+1-m , if i = t m for m ∈ [u]; ξ c ′ σ ′ (r+1-m) , if i = c m for m ∈ [r]. Therefore µ im = ξ i ′ m = γ im for m ∈ [k] and µ tm = ξ t ′ u+1-m = γ tm for m ∈ [u]
. By (5.2) we have σ(r + 1σ ′ (j)) = r + 1j and

µ cm = ξ c ′ σ ′ (r+1-m) = γ c σ(r+1-σ ′ (r+1-m)) = γ cm for m ∈ [r].
Hence µ = γ and ϕ is an involution. Finally (5.4) follows from (5.3).

6. Bijection Γ σ from P k n to P k n (σ) The Lehmer code of a permutation σ in S n is the sequence c(σ) = (c 1 , . . . , c n ) of non negative integers where the integer c i is defined by

c i = #{j > i, σ(j) < σ(i)}.
We can recover the permutation σ from its code c(σ) because σ(i) equals the (c i + 1)-th element in [n] -{σ(1), ..., σ(i -1)}. Therefore the mapping c which associates to each permutation of S n its Lehmer code is a bijection from

S n to [0, n -1] × [0, n -2] × ... × [0, 1] × [0]. Moreover inv σ = c 1 + . . . + c n .
For our purpose we need to define the d-code of a permutation σ ∈ S n by

d(σ) := (d 1 , . . . , d n ) = (c σ -1 (1) , . . . , c σ -1 (n) ).
That is, the coordinate d i is the number of entries σ(j) smaller than and to the right of i in the sequence σ(1) . . . σ(n). In other words, we have

d i = #{j > σ -1 (i); σ(j) < i}.
Lemma 6.1. The mapping d which associates to each permutation of S n its d-code is a bijection from S n to

P n = [0]×[0, 1]×...×[0, n-2]×[0, n-1]. Moreover inv σ = d 1 +. . .+d n .
For example, if σ = 8 6 3 4 7 5 2 1, then

c(σ) = 7 5 2 2 3 2 1 0, d(σ) = 0 1 2 2 2 5 3 7. Lemma 6.2. For any (w, γ) ∈ ∆ k n with O ∪ S(w) = {i 1 , i 2 , . . . , i k } < , the sequence (γ i 1 , . . . , γ i k ) is the d-code of some permutation σ ∈ S k .
Proof. It suffices to verify that 0 ≤ γ i j ≤ j -1 for j = 1, . . . , k, but this is obvious in view of Lemma 4.3(ii).

For any permutation σ ∈ S k , let ∆ k n (σ) be the set of path diagrams (w, γ)

∈ ∆ k n such that d(σ) = (γ i 1 , . . . , γ i k ), where O ∪ S(w) = {i 1 , i 2 , . . . , i k } < . Lemma 6.3. For any σ ∈ S k we have (i) the restriction of ϕ on ∆ k n (σ) is an involution; (ii) the restriction of Φ on ∆ k n (σ) is a bijection from ∆ k n (σ) to P k n (σ). Proof. Let (w, γ) ∈ ∆ k n (σ) with O ∪ S(w) = {i 1 , i 2 , . . . , i k } ≤ . Then (γ i 1 , . . . , γ i k ) is the d-code of σ. (i) follows directly from the definition of ϕ. Let Φ(w, γ) = π. Suppose π = B τ (1) /B τ (2) / . . . /B τ (k) is a τ -partition in OP k n and d(τ ) = (d 1 , . . . , d k ). Hence B 1 /B 2 / . . . /B k is a partition in P k n and min B j = i j for j ∈ [k]
. By definition of Φ, in the i j -th step, we create a new block B j with i j in T i j so that there are γ i j blocks to the right of the block B j , i.e., d j = γ i j . Namely τ = σ.

Conversely, given π ∈ P k n (σ), then there is a path diagram (w, γ) ∈ ∆ k n (τ ), for some τ ∈ S k , such that Φ(w, γ) = π. As Φ is a bijection, we get d(σ) = d(τ ), so σ = τ . This completes the proof of (ii).

It is convenient to introduce the following abbreviations: cls := lcs + rcs, opb := lob + rob and sb := lsb + rsb .

(6.1) Proposition 6.4. For any π ∈ OP k n ,

cls(π) = i∈ clos(π) (n -i), (6.2) opb(π) = i∈ open(π) (i -1), (6.3) sb(π) = i∈ C(π) i - i∈ O(π) i + k -n. (6.4)
Proof. First of all, equations (6.2) and ( 6.3) follow immediately from the fact that for any i ∈ [n] the number of integers greater (resp. smaller) than i in [n] equals ni (resp. i -1). Indeed, by definition (6.1), the statistic cls(π) amounts to count, for each closer i of π, the number of the integers greater than i in [n]. Similarly we get (6.3). Now,

suppose π = B 1 / • • • /B k , then sb(π) = k i=1 |{j : min(B i ) < j < max(B i ), j / ∈ B i }| = k i=1 (max(B i ) -min(B i ) + 1 -|B i |) = k i=1 max(B i ) - k i=1 min(B i ) + k -n,
which is exactly (6.4).

We are now ready to construct a bijection from (no ordered) set partitions to ordered set partitions and state the main theorem of this section. Theorem 6.5. For any σ ∈ S k there is a bijection Γ σ : P k n → P k n (σ) such that for any

π ∈ P k n , (i) λ(Γ σ (π)) = λ(π); (ii) (cls, opb, sb)Γ σ (π) = (cls, opb, sb)π; (iii) rsb T C Γ σ (π) = rsb T C π. Proof. Let σ, τ be two permutations in S k with d(σ) = (d 1 , . . . , d k ) and d(τ ) = (d ′ 1 , . . . , d ′ k ). For any path diagram (w, γ) ∈ ∆ k n (τ ) we can define a path diagram g τ,σ (w, γ) = (w, γ ′ ) ∈ ∆ k
n (σ) as follows:

γ ′ i = d j , if i = i j ∈ O ∪ S(w); γ i , if i ∈ T ∪ C(w). (6.5)
Clearly the mapping g σ,τ :

∆ k n (σ) → ∆ k n (τ ) is a bijection because g -1 σ,τ = g τ,σ .
In particular, taking τ = ǫ (the identity permutation), then

g σ := g ǫ,σ is a bijection from ∆ k n (ǫ) to ∆ k n (σ). It follows that Γ σ := Φ • g σ • Φ -1 (6.6)
is a bijection from P k n to P k n (σ). For any π ∈ P k n , let Γ σ (π) = π ′ . The composition of mappings is better understood by the following diagram:

Γ σ : π Φ -1 -→ (w, γ) gσ -→ (w, γ ′ ) Φ -→ π ′ .
By definition of Φ and g σ , we have λ(π ′ ) = λ(w) = λ(π), namely (i). (ii) follows from Proposition 6.4. Combining (4.1) and (6.5) yields (iii):

rsb T C π ′ = i∈T ∪C(w) γ ′ i = i∈T ∪C(w) γ i = rsb T C π.
This completes the proof of Theorem 6.5.

Example 6.1. Let π = 1 5 7/2 4 10/3 8/6/9 ∈ P 5 10 and σ = 4 3 1 5 2. Hence opener(π) = {1, 2, 3, 6, 9} < and d(σ) = 0 0 2 3 1. The corresponding path diagrams (w, γ) and (w, γ ′ ) are given by w = (0, 0), (0, 1), (0, 2), (0, 3), (0, 3), (0, 3), (1, 3), (2, 2), (3, 1), (4, 1), (5, 0), γ = (0, 0, 0, 1, 2, 0, 2, 0, 0, 0),

γ ′ = (0, 0, 2, 1, 2, 3, 2, 0, 1, 0).

The mapping g

σ : h → h ′ is illustrated in Figure 5. h = ✲ ✻ 0 0 0 1, 2 0 2 0 0 0 gσ --→ h ′ = ✲ ✻ 0 0 2 1, 2 3 2 0 1 0 Figure 5. Mapping g σ
Finally, we get Γ σ (π) = Φ(h ′ ) = 6/3 5 7/1 4 10/9/2 8 ∈ P 5 10 (σ). Note that π ′ is not a rearrangement of the blocks in π.

Proof of Theorem 3.1

Consider the mapping

Ξ = Φ • ϕ • Φ -1 : OP k n -→ OP k n .
For example, if π = 6/3 5 7/1 4 10/9/2 8, then Φ -1 (π) = h is given in Figure 2, while ϕ(h) is given in Figure 4. Finally we get Ξ(π) = Φ(ϕ(h)) = 4 6 8/3 7 10/1 9/5/2.

Clearly the mapping Ξ is an involution. For any fixed σ ∈ S k , Lemma 6.3 implies that the restriction of Ξ on P k n (σ) is stable.

For any π ∈ P k n (σ), let Ξ(π) = π ′ ∈ P k n (σ). Suppose that h = (w, γ) = Φ -1 (π), h ′ = ( w, ξ) = ϕ(h) and π ′ = Φ(h ′ ). Then Lemmas 4.

Furthermore, on OP k n , the following equations hold true (see [START_REF] Ishikawa | Euler-Mahonian statistics on ordered set partitions[END_REF]Lemma 4.6]):

MAK + bInv = cls + rsb T C + Inv, MAK ′ + bInv = opb + rsb T C + Inv, (7.4)
cinvLSB = k(k -1) + sb -rsb T C -Inv .
It follows from (

(MAK + bInv, MAK ′ + bInv, cinvLSB) π ′ = (MAK ′ + bInv, MAK + bInv, cinvLSB) π. 7.2), (7.3) and (7.4) that
This completes the first part of Theorem 3.1.

In view of (7.4) it is easy to see that (3.1) is equivalent to the following two identities:

π∈ P k n (σ) p cls π+rsb T C π q sb π-rsb T C π = π∈ P k n (σ)
p opb π+rsb T C π q sb π-rsb T C π , (

and

π∈ P k n (σ)
p opb π+rsb T C π q sb π-rsb T C π = S p,q (n, k).

Now, (7.5) follows immediately from (7.2) and (7.3). According to Theorem 6.5, it suffices to prove (7.6) in the case of σ = ε. But, on P k n = P k n (ε), since lob = rsb OS = 0, there hold

opb + rsb T C = rob + rsb = rcb, sb -rsb T C = lsb = lsb + lob = lcb .
Hence the left-hand side of (7.6) is equal to

π∈ P k n p opb π+rsb T C π q sb π-rsb T C π = π∈ P k n p rcb π q lcb π , (7.7)
and (7.6) follows by applying (2.3). The proof of Theorem 3.1 is thus completed.

Remark 7.1. For any mahonian permutation statistic mah we can define a statistic Mah on ordered set partitions by Mah π = mah σ if π ∈ P k n (σ) and derive from the above proof the following identities:

π∈ OP k n p cls π+rsb T C π q sb π-rsb T C π t Mah π = [k] t ! S p,q (n, k), π∈ OP k n p opb π+rsb T C π q sb π-rsb T C π t Mah π = [k] t ! S p,q (n, k). (7.8)
In particular, by taking mah = inv we recover essentially Theorem 3.2, while by taking mah = maj we derive that the statistics

cls + rsb T C + Maj, opb + rsb T C + Maj, k(k -1) + sb -rsb T C -Maj
are Euler-Mahonian.

Remark 7.2. For ordinary partitions, there is a similar bijection, simpler than Ξ, using Motzkin paths. We sketch this bijection below. A Motzkin path of length n is a lattice path in the plane of integer lattice Z 2 from (0, 0) to (n, 0), consisting of NE-steps (1, 1), E-steps (1, 0), and SE-steps (1, -1), which never passes below the x-axis. Let D n be the set of Motzin path diagrams (ω, γ), where ω is a Motzkin path of length n and γ = (γ 1 , . . . , γ n ) is a sequence of labels such that if the i-th step is NE, then γ i = 1, if the i-th step is SE, then 1 ≤ γ i ≤ h i , and if the i-th step is E, then 1 ≤ γ i ≤ h i + 1, where h i is the height of the i-th step.

For each partition π in P n we can construct its traces {T i } 0≤i≤n . Let γ i -1 be the number of incomplete blocks to the left of the block containing i in T i . As shown in [START_REF] Ksavrelof | Nouvelles statistiques de partitions pour les q-nombres de Stirling de seconde espèce[END_REF] we can construct a bijection f : π -→ (w, γ) from P n to D n as follows: For i = 1, . . . , n, if i ∈ O(π) (resp. S(π)) we draw a NE-step (resp. E-step) with label 1 (resp. γ i ) and if i ∈ C(π) (resp. T (π)) we draw a SE-step (resp. E-step) with label γ i .

An example is given in Figure 6. Define an involution g : (w, γ) → (w ′ , γ ′ ) on D n as follows: First reverse the path w by reading it from right to left, i.e., if w = ((i, y i )) 0≤i≤n , then w ′ = ((i, y n-i )) 0≤i≤n , then pair the NE-steps with SE-steps in w two by two in the following way: each NE-step at height h corresponds to the first SE-step to its right at height h + 1 (thus we establish a bijection between the SE-steps of w and those of w ′ ), attribute the label of each SE-step of w to the corresponding SE-step of w ′ , finally the labels of NE-steps of w ′ are 1 and the E-steps of w ′ keep the same label as in w.

Now, it is easy to see (cf. [START_REF] Ksavrelof | Nouvelles statistiques de partitions pour les q-nombres de Stirling de seconde espèce[END_REF]) that the mapping

Λ = f -1 • g • f : π f -→ (w, γ) g -→ (w ′ , γ ′ ) f -1 -→ π ′
is an involution on P k n such that MAK (π) = rcb Λ(π) and lcb (Λ(π)) = lcb (π).

The involution applied to the example in Figure 1 is given in Figure 2, where MAKπ = rcb Λ(π) = 37, lcb π = lcb Λ(π) = 16. Note that the mapping Λ = f -1 • g • f is a corrected version of that given in [START_REF] Ksavrelof | Nouvelles statistiques de partitions pour les q-nombres de Stirling de seconde espèce[END_REF]. Thus, the statistics bDes, bMaj and rsb i can be easily extended to traces.

Let T = B 1 / • • • /B r be the (i -1)-trace of a partition (i ≥ 1). We can insert i before B 1 , between two adjacent blocks B j and B j+1 , for 1 ≤ j ≤ r -1, or after B r . Label these insertion positions from left to right by 0, 1, . . . , r. We say that the position j is active if B j+1 is active.

Let A and D be the set of active positions and block descents in T , respectively. We then label the r + 1 positions in T as follows:

• label the right-most position by a 0 = r and the elements of A ∪ D from right to left by a 1 , a 2 , . . . , a t . So a t < a t-1 < • • • < a 2 < a 1 , • label the remaining positions from left to right by a t+1 , . . . , a r . So a t+1 < • • • < a r . Lemma 8.1. Let ℓ be an integer satisfying 0 ≤ ℓ ≤ r and define T ′ to be the i-trace obtained by inserting in T the block {i, ∞} or {i} into position a ℓ . Then, Since T is a (i -1)-trace, the openers of T are all smaller than i. This implies that rsb i T ′ is the number of active blocks in T ′ to the right of B. We distinguish four cases.

rsb i T ′ + bMaj T ′ -bMaj T = ℓ. ( 8
(1) ℓ = 0. Since a 0 = r, we have T ′ = B 1 /B 2 / . . . /B r /B and the equation (8.1) is obvious.

(2) 1 ≤ ℓ ≤ t and a ℓ ∈ D. Let a ℓ = d j for some j, 1 ≤ j ≤ p. The block descent set of T ′ is then

{d p < • • • < d j+1 < d j + 1 < d j-1 + 1 < • • • < d 1 + 1}.
Let q be the greatest number such that o q > a ℓ . Clearly, rsb i (T ′ ) = q. We thus have that rsb i T ′ + bMaj T ′ -bMaj T = q + j.

It suffices now to remark that ℓ = j + q.

(3) 1 ≤ ℓ ≤ t and a ℓ ∈ A. Then, a ℓ = o j for some j, 1 ≤ j ≤ m. Clearly, rsb i (T ′ ) = j.

Let q be the number such that d q > a ℓ . Then, the block descent set of

T ′ is {d p < • • • < d q+1 < d q + 1 < d q-1 + 1 < • • • < d 1 + 1}.
It then follows that

rsb i T ′ + bMaj T ′ -bMaj T = j + q.
It suffices now to remark that ℓ = j + q.

(4) t + 1 ≤ ℓ ≤ r. Note that a ℓ is a position before a complete block. Let q and s be the greatest numbers such that d q > a ℓ and o s > a ℓ . Clearly, rsb i (T ′ ) = s and the block descent set of T ′ is

{d p < • • • < d q+1 < a ℓ + 1 < d q + 1 < d q-1 + 1 < • • • < d 1 + 1}.
It follows that

rsb i T ′ + bMaj T ′ -bMaj T = s + q + a ℓ + 1.
It suffices now to remark that a ℓ = ℓ-(s+q)-1. Indeed, a ℓ is equal to the number of positions in T to the left of the position, i.e. (pq) + (ms) + (ℓt -1), which is also equal to = ℓ -(q + s) -1 since t = p + m.

We give an example to illustrate the above result.

❄ Ψ i step i γi Ti 0 ∅ 1 N orth 0 1 ∞ 2 N orth 0 1 ∞/2 ∞ 3 N orth 2 3 ∞/1 ∞/2 ∞ 4 N ull 1 3 ∞/1 4 ∞/2 ∞ 5 N ull 2 3 5 ∞/1 4 ∞/2 ∞ 6 East 3 6/3 5 ∞/1 4 ∞/2 ∞ 7 South-East 2 6/3 5 7/1 4 ∞/2 ∞ 8
(bMaj T i (π) -bMaj T i-1 (π)) . (8.2)
We summarize the main properties of Ψ in the following theorem.

Theorem 8.2. The mapping Consider the mapping Υ := Ψ • Φ -1 : OP k n → OP k n . For example, if π = 6/3 5 7/1 4 10/9/2 8, then it follows from Figure 2 and Figure 3 that Υ(π) = 6/3 5 7/9/1 4 10/2 8. Note that Υ(π) is generally not a rearrangement of the blocks of π.

Ψ : ∆ k n → OP k n is a bijection such that if h = (w, γ) ∈ ∆ k n and π = Ψ(h), then λ(π) = λ(w) and
γ i = rsb i (π) + bMaj(T i (π)) -bMaj(T i-1 (π)), if i ∈ O ∪ S(π); rsb i (π), if i ∈ T ∪ C(π). ( 8
The main properties of Υ is summarized in the following lemma. We construct recursively i-skeletons T i , 1 ≤ i ≤ n, such that T i has O(π) ≤i -C(π) ≤i active blocks and (C ∪ S(π)) ≤i complete blocks by the following process. Set T 0 = ∅ and suppose T i-1 = B 1 /B 2 / • • • /B l . Then T i is obtained from T i-1 as follows:

• i ∈ O(π) (resp. S(π)): label the positions before B 1 , between B j and B j+1 , for 1 ≤ j ≤ l -1, and after B l from left to right by {0, 1, • • • , l}. Let F be the set of the positions before the active blocks in T i-1 and D = bDes(T i-1 ). Then, set a 0 = l, {a 1 > a 2 > • • • > a t } = F ∪D and let a t+1 < • • • < a l be the remaining positions. We then insert the block {i, ∞} (resp. {i}) into position a γ i .

• i ∈ T (π) (resp. C(π)): insert i (resp. replace ∞ by i) in the active block whose opener is the opener of the block of π which contains i. It is not difficult to see, via Lemma 8.1, that the above procedure is well defined. Since O(P ) ≤n = C(P ) ≤n and (C(P ) ∪ S(P )) ≤n = |C(P ) ∪ S(P )| = k, T n is a n-skeleton with 0 active blocks and k complete blocks, i.e. T n ∈ OP k n . Now, by construction, T n ∈ R(π). We then set β P (c) = T n .

To show that β P is bijective, we describe its inverse. Let π ∈ R(π) and suppose

O ∪ S(π) = {i 1 < i 2 < • • • < i k }.
For 1 ≤ j ≤ k, let c j = rsb i j π + bMaj T i j (π) -bMaj T i j-1 (π). It is then readily seen that

β P (c 1 • • • c k ) = π.
Remark. A Foata style bijection which establishes directly the equidistribution of INV and MAJ willl be given by the first author in [START_REF] Kasraoui | A note on maj-inv statitics on words[END_REF].

Concluding remarks

Recall that the q-Eulerian numbers A q (n, k) (n ≥ k ≥ 0) of Carlitz [START_REF] Carlitz | A combinatorial property of q-Eulerian numbers[END_REF] are defined by A q (n, k) = q k [nk] q A q (n -1, k -1) + [k + 1] q A q (n -1, k), (11.1) and have the following combinatorial interpretation:

A q (n, k) = σ q maj σ
where the summation is over all permutations of [n] with k descents. The original motivation of Steingrímsson [START_REF] Steingrímsson | Statistics on ordered partitions of sets[END_REF] was to give a direct combinatorial proof of the following identity [START_REF] Zeng | A q-analog of Newton's series, Stirling functions and Eulerian functions[END_REF]:

[k] q ! S q (n, k) = k m=1 q k(k-m) nm nk q A q (n, m -1). (11.2)

Though we have proved all the conjectures inspired by (11.2), a direct combinatorial proof of (11.2) is still missing. As proved in [START_REF] Zeng | A q-analog of Newton's series, Stirling functions and Eulerian functions[END_REF] the identity (11.2) is equivalent to Garsia's q-analogue of Frobenius formula relating q-Eulerian numbers and q-Stirling numbers of the second kind (see [START_REF] Garsia | On the "maj" and "inv" q-analogue of Eulerian numbers[END_REF][START_REF] Garsia | Q-counting rook configurations and a formula of Frobenius[END_REF]): n k=1

[k] q !S q (n, k)x k (x; q) k+1 = ∞ k=1

[k] n q x k = σ∈Sn x 1+des σ q maj σ (x; q) n+1 . (11.3) Note that a combinatorial proof of (11.3) has been given by Garsia and Remmel [START_REF] Garsia | Q-counting rook configurations and a formula of Frobenius[END_REF].

  Obviously we have open(π) = O(π) ∪ S(π), clos(π) = C(π) ∪ S(π), S(π) = open(π) ∩ clos(π).The 4-tuple (O(π), C(π), S(π), T (π)), denoted by λ(π), is called the type of π. For example, if π = 3 5/2 4 6/1/7 8, then open(π) = {1, 2, 3, 7}, clos(π) = {1, 5, 6, 8} and λ(π) = ({2, 3, 7}, {5, 6, 8}, {1}, {4}).

Theorem 3 . 3 .

 33 The triple statistics (MAK+bMaj, MAK ′ +bMaj, cmajLSB) and (MAK+ bInv, MAK ′ + bInv, cinvLSB) are equidistributed on OP k n (λ) for any partition type λ. Combining Theorems 3.2 and 3.3 we derive immediately the following result, of which the first part was conjectured by Ishikawa et al.[START_REF] Ishikawa | Euler-Mahonian statistics on ordered set partitions[END_REF] Conjecture 6.2] while the second part was originally conjectured by Steingrímsson[START_REF] Steingrímsson | Statistics on ordered partitions of sets[END_REF].

Theorem 3 . 5 .

 35 For any π ∈ P k n , the statistics INV and MAJ are equidistributed on R(π) and π∈R(π)

Example 4 . 1 .

 41 If π = 3 5 7/1 4 10/9/6/2 8, then the 7-trace of π is T 7 = 3 5 7/1 4 ∞/6/2 ∞, with ros 7 π = 3 and rsb 7 π = 2.

Figure 1 .

 1 Figure1. A path in Ω5 10 with two successive Null steps from (0, 3) to (0, 3).

Theorem 4 . 4 .

 44 The bijection Φ : (w, γ) → π has the following properties: λ(w) = λ(π) and for 1 ≤ i ≤ n,

Figure 2 .Figure 3 .

 23 Figure 2. the step by step construction of Φ(h)

Figure 4 .Proposition 5 . 2 .

 452 Figure 4. An example of the involution ϕ Proposition 5.2. The mapping ϕ : (w, γ) → ( w, ξ) is an involution on ∆ k n such that

  w) because both sides are equal to m -1. We have (a) by invokingξ i ′ m = γ im and 0 ≤ γ im ≤ x im (w) + y im (w). (ii) For m ∈ [u], Lemma 5.1(2) implies that y t ′ m (w) = y t ′ m (w) = y t u+1-m (w). We obtain (b) by invoking ξ t ′ m = γ t u+1-m , 0 ≤ γ t u+1-m ≤ y t u+1-m (w) -1 and y t u+1-m (w) = y t ′ m (w). (iii) For m ∈ [r], Lemma 5.1(2) implies y c ′ m (w) = y c σ(r+1-m) (w) because y c ′ m (w) = y c ′ m (w) + 1 = y o r+1-m (w) + 1, which is equal to y c σ(r+1-m) (w) by definition of σ. We derive (c) by invoking that ξ c ′ m = γ c σ(r+1-m) and 0 ≤ γ c σ(r+1-m) ≤ y c σ(r+1-m) (w) -1. Let σ ′ be the associated permutation of w. Consider the chain of bijections:

  3 and 6.3 imply that Inv π = inv σ = Inv π ′ . (7.1) By Theorem 4.4 we see that λ(π ′ ) = λ(w), λ(π) = λ(w) and rsb T C π ′ = i∈T ∪C(w) ξ i and rsb T C π = i∈T ∪C(w) γ i . It follows from (5.4) that rsb T C π ′ = rsb T C π. (7.2) As λ(w) = λ(w), by Proposition 6.4, we obtain (cls, opb, sb)π ′ = (opb, cls, sb)π. (

πFigure 6 .

 6 Figure 6. A labeled Motzkin path of length 15 and the corresponding partition.

Λ

  (π) = {1, 12, 15}/{2, 4}/{3, 6, 9}/{5, 7}/{8}/{10, 11}/{13, 14}.

Figure 7 .

 7 The labeled Motzkin path and the associated partition corresponding to those of Figure6.

8 .

 8 The second path diagrams encoding Ψ of ordered set partitions Recall that a block in a trace is a subset B of [n] ∪ {∞} such that B ∩ [n] = ∅. By convention, the closer of B is the greatest element of B. Hence max(B) = ∞ if ∞ ∈ B.

Example 8 . 1 .

 81 Let T = 6 11 ∞/3 5 7/1 4 10 ∞/9/2 8. So there are 6 insertion positions and the set of active positions and descents is A = {0, 2} and D = {4}. Therefore a 0 = 5, a 1 = 4, a 2 = 2, a 3 = 0, and a 4 = 1, a 5 = 3.

Figure 8 .

 8 Figure 8. the step by step construction of Ψ(h)

. 3 ). 4 ) 9 .

 349 Therefore i∈O∪S(w) γ i = rsb OS π + bMaj π, and i∈T ∪C(w)γ i = rsb T C π.(8Proof of Theorem 3.3

Lemma 9 . 1 .

 91 The map Υ : OP k n → OP k n is a bijection such that for any π ∈ OP k n , we have:(i) λ(Υ(π)) = λ(π), (ii) rsb T C Υ(π) = rsb T C π, (iii) MAJΥ(π) = INVπ.Proof. By definition the mapping Υ is a bijection. For π ∈ OP k n , let h = (w, γ) = Φ -1 (π) and π ′ = Ψ(h). Hence π ′ = Υ(π). By the construction of Ψ and Φ, it is clear that λ(π ′ ) = λ(w) = λ(π). Combining (4.1),(8.4) and (3.7), we haveMAJπ ′ = rsb OS π + bMaj π ′ = i∈O∪S(w) γ i = ros OS π = INVπ, rsb T C π ′ = i∈T ∪C(w) γ i = rsb T C π,completing the proof. Applying Lemma 9.1 and Proposition 6.4 we obtain (cls + rsb T C , opb + rsb T C , sbrsb T C , MAJ) Υ(π) = (cls + rsb T C , opb + rsb T C , sbrsb T C , INV) π. (9.1) According to (2.5) and (2.7), the following functional identities hold on OP k n : MAK + bMaj = lcs + rcs + rsb + bMaj = cls + rsb T C + rsb OS + bMaj = cls + rsb T C + MAJ, MAK ′ + bMaj = lob + rob + rsb + bMaj = opb + rsb T C + rsb OS + bMaj = opb + rsb T C + MAJ, cmajLSB = k(k -1) + sbrsb -bMaj = k(k -1) + sbrsb T Crsb OS -bMaj = k(k -1) + sbrsb T C -MAJ.

  .1) Proof. Clearly A and D are disjoint. Suppose A = {o 1 , o 2 , . . . , o m } > and D = {d 1 , d 2 , . . . , d p } > . So t = m + p. Let B be one of the two blocks {i, ∞} or {i}.

Denote by T ′ the trace obtained by inserting in T the block {12} into position a i . Then we have: We now construct a new bijection Ψ : ∆ k n → OP k n based on the above lemma.

Algorithm Ψ. Let h = (w, γ) ∈ ∆ k n be a path diagram. Set T 0 = ∅. Construct recursively i-skeletons T i for i = 1, . . . , n such that T i has y i+1 (w) active blocks and x i+1 (w) complete blocks by the following process. Suppose T i-1 = B 1 /B 2 / • • • /B ℓ and T i-1 has y i (w) active blocks and x i (w) complete blocks. Label the positions before B 1 , between B j and B j+1 , for 1 ≤ j ≤ ℓ -1, and after B ℓ from left to right by {0, 1, • • • , ℓ}. Extend T i-1 to T i as follows:

• The i-th step of w is North (resp. East): Let A be the set of the active positions in T i-1 and D the set of block descents in T i-1 . Then, set 8.

The step by step construction of Ψ(h) is given in Figure

To show that Ψ is bijective, we give its inverse. Algorithm Ψ -1 . Let π ∈ OP k n be an ordered partition. Let w be the path defined by

n and its image under Ψ is π.

We thus derive from (9.1) and (7.4) that

This completes the proof of Theorem 3.3.

Remark 9.2. From (7.8) and (9.1) we derive immediately the following equivalent forms of (3.4):

Remark 9.3. Composing Υ and Ξ we obtain the mapping

For example, if π = 6/3 5 7/9/1 4 10/2 8, then Ψ -1 (π) = h, where h is the path diagram in Figure 8. Therefore ϕ(h) is that given in Example 5.1. The reader can verify that Θ(π) = Ψ(ϕ(h)) = 4 6 8/1 7 10/3 9/5/2.

Obviuously, the mapping Θ is an involution on OP k n satisfying, for any π

Therefore, by Proposition 6.4,

In other words, we have

10. Proof of Theorem 3.5

By (2.6) and (3.7), we have

It remains to show that π∈R(π)

Briggs and Remmel [START_REF] Briggs | A p, q-analogue of a formula of Frobenius[END_REF] proved the following p, q-analogue of Frobenius formula (11.3):

where comaj σ = n des σmaj σ and Ŝp,q (n, k) is a variante of the p, q-Stirling numbers of the second kind defined by the following recursion: Ŝp,q (n, k) = q k-1 Ŝp,q (n -1, k -1) + p -n [k] p,q Ŝp,q (n -1, k). (11.5) We would like to point out that (11.4) and (11.3) are equivalent. Obviously (11.3) corresponds to the p = 1 case of (11.4). Conversely, since [k] q/p ! = p -( k 2 ) [k] p,q ! and Ŝp,q (n, k) = p -( n-k+1

2

)-(n-k) q ( k 2 ) S 1,q/p (n, k)

)-(n-k) S q/p (n, k), we derive (11.4) from (11.3) by substituting q → q/p and x → xp n .