2007/08/30

Fix-Mahonian Calculus, II: further statistics

Dominique Foata and Guo-Niu Han

ABSTRACT. Using classical transformations on the symmetric group and two transformations constructed in Fix-Mahonian Calculus I, we show that several multivariable statistics are equidistributed either with the triplet (fix,des,maj), or the pair (fix,maj), where “fix,” “des” and “maj” denote the number of fixed points, the number of descents and the major index, respectively.

1. Introduction

First, recall the traditional notations for the q-ascending factorials

(a; q)_{n} := \{ \begin{matrix}1, & if n = 0; \\ (1 − a)(1 − aq) ⋯ (1 − aq^{n−1}), & if n ≥ 1; \end{matrix}

(a; q)_{∞} := ∏_{n≥1}(1 − aq^{n−1});

and the q-exponential (see [GaRa90, chap. 1])

e_{q}(u) = ∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} = \frac{1}{(u; q)_{∞}} .

Furthermore, let (A_{n}(Y, t, q)) and (A_{n}(Y, q)) (n ≥ 0) be the sequences of polynomials respectively defined by the factorial generating functions

(1.1) ∑_{n≥0} A_{n}(Y, t, q)\frac{u^{n}}{(t; q)_{n+1}} := ∑_{s≥0} t^{s}(1 − u ∑_{i=0}^{s} q^{i})^{−1} \frac{(u; q)_{s+1}}{(uY; q)_{s+1}} ;

(1.2)  ∑_{n≥0} A_{n}(Y, q)\frac{u^{n}}{(q; q)_{n}} := (1 − \frac{u}{1 − q} )^{−1} \frac{(u; q)_{∞}}{(uY; q)_{∞}} .

DOMINIQUE FOATA AND GUO-NIU HAN

Of course, (1.2) can be derived from (1.1) by letting the variable t tend to 1, so that A_{n}(Y, q) = A_{n}(Y, 1, q). The classical combinatorial interpretation for those classes of polynomials has been found by Gessel and Reutenauer [GeRe93] (see Theorem 1.1 below). For each permutation σ = σ(1)σ(2) ⋯ σ(n) from the symmetric group 𝔖_{n} let i σ := σ^{−1} denote the inverse of σ; then let its set of fixed points, FIX σ, descent set, DES σ, idescent set, IDES σ, be defined as the subsets:

FIX σ := {i : 1 ≤ i ≤ n, σ(i) = i};
DES σ := {i : 1 ≤ i ≤ n − 1, σ(i) > σ(i + 1)};
IDES σ := DES σ^{−1}.

Note that IDES σ is also the set of all i such that i + 1 is on the left of i in the linear representation σ(1)σ(2) ⋯ σ(n) of σ. Also let fix σ := # FIX σ (the number of fixed points), des σ := # DES σ (the number of descents), maj σ := ∑_{i} i (i ∈ DES σ) (the major index), imaj σ := ∑_{i} i (i ∈ IDES σ) (the inverse major index).

Theorem 1.1 (Gessel, Reutenauer). For each n ≥ 0 the generating polynomial for 𝔖_{n} by (fix, des, maj) (resp. by (fix, maj)) is equal to A_{n}(Y, t, q) (resp. to A_{n}(Y, q)). Accordingly,

(1.3)  A_{n}(Y, t, q) = ∑_{σ∈𝔖_{n}} Y^{fix σ}t^{des σ}q^{maj σ};

(1.4)  A_{n}(Y, q) = ∑_{σ∈𝔖_{n}} Y^{fix σ}q^{maj σ}.

The purpose of this paper is to show that there are several other threevariable (resp. two-variable) statistics on 𝔖_{n}, whose distribution is given by the generating polynomial A_{n}(Y, t, q) (resp. A_{n}(Y, q)). For proving that those statistics are equidistributed with (fix, des, maj) (resp. (fix, maj)) we make use the properties of the classical bijections F_{2}^{loc}, F′_{2}, CHZ, DW^{glo}, DW^{loc}, plus two transformations F_{3}, Φ, constructed in our previous paper [FoHa07], finally a new transformation F′_{3} described in Section 3.

All those bijections appear as arrows in the diagram of Fig. 1. The nodes of the diagram are pairs or triplets of statistics, whose definitions have been, or will be, given in the paper. The integral-valued statistics are written in lower case, such as “fix” or “maj”, while the set-valued ones appear in capital letters, such as “FIX” or “DES”. We also introduce two mappings “Der” and “Desar” of 𝔖_{n} into 𝔖_{m} with m ≤ n.

Each arrow goes from one node to another node with the following meaning that we shall explain by means of an example: the vertical arrow (fix, maz, Der) ⟶^{F_{3}} (fix, maf, Der) (here rewritten horizontally for typographical reasons!) indicates that the bijection F_{3} maps 𝔖_{n} onto itself and has the property: (fix, maz, Der) σ = (fix, maf, Der) F_{3}(σ) for all σ. The remaining statistics are now introduced together with the main two decompositions of permutations: the fixed and pixed decompositions.

FURTHER STATISTICS

[figure: (FIX, maf); (PIX, mag); (fix, maj, Der); (fix, DES); (PIX, inv); (pix, inv); (fix, maz, Der); (fix, maf, Der); (fix, DEZ); (FIX, DEZ); (pix, imaj); (pix, imaj, Desar); (pix, mag, Desar); (pix, IDES); (PIX, IDES); ⟶^{DW^{loc}}; ^{^{CHZ}↓}; ^{↓^{F_{2}^{loc}}}; ^{↓^{(F′_{2})^{−1}}}; ^{^{Φ}↑}; ^{F^{3}}↑; ^{F{′ \atop 3}}↑; ⟶^{DW^{loc}}; DW^{glo}]

Fig. 1

1.1. The fixed decomposition. Let σ = σ(1)σ(2) ⋯ σ(n) be a permutation and let (i_{1}, i_{2}, …, i_{n−m}) (resp. (j_{1}, j_{2}, …, j_{m})) be the increasing sequence of the integers k (resp. k′) such that 1 ≤ k ≤ n and σ(k) = k (resp. 1 ≤ k′ ≤ n and σ(k′) ≠ k′). Also let “red” denote the increasing bijection of {j_{1}, j_{2}, …, j_{m}} onto [ m]. Let ZDer(σ) = x_{1}x_{2} ⋯ x_{n} be the word derived from σ = σ(1)σ(2) ⋯ σ(n) by replacing each fixed point σ(i_{k}) by 0 and each other letter σ(j_{k′}) by red σ(j_{k′}). As “DES,” “des” and “maj” can also be defined for arbitrary words with nonnegative letters, we further introduce:

(1.5)  DEZ σ := DES ZDer(σ);
(1.6)  dez σ := des ZDer(σ), maz σ := maj ZDer(σ);
(1.7)  Der σ := red σ(j_{1}) red σ(j_{2}) ⋯ red σ(j_{m});
(1.8)  maf σ := ∑_{k=1}^{n−m}(i_{k} − k) + maj ∘ Der σ.

The subword Der σ of ZDer(σ) can be regarded as a permutation from 𝔖_{m} (with the above notations). It is important to note that FIX Der σ = ∅, so that Der σ is a derangement of order m. Also note that σ is fully characterized by the pair (FIX σ, Der σ), which is called the fixed decomposition of σ. Finally, we can rewrite maf σ as

(1.9)  maf σ := ∑_{i∈FIX σ} i − ∑_{i=1}^{fix σ} i + maj ∘ Der σ.

Example. With σ = (\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 8 & 2 & 1 & 3 & 5 & 6 & 4 & 9 & 7 \end{matrix}) we have red = (\begin{matrix}1 & 3 & 4 & 7 & 8 & 9 \\ 1 & 2 & 3 & 4 & 5 & 6 \end{matrix}),

ZDer(σ) = 5 0 1 2 0 0 3 6 4, DEZ σ = {1, 4, 8}, dez σ = 3, maz σ = 13, Der σ = 5 1 2 3 6 4, FIX σ = {2, 5, 6} and maf σ = (2 − 1) + (5 − 2) + (6 − 3) + maj(5 1 2 3 6 4) = 7 + 6 = 13.

1.2. The pixed decomposition. Let w = y_{1}y_{2} ⋯ y_{n} be a word having no repetitions, without necessarily being a permutation of 12 ⋯ n. Say that w is a desarrangement if y_{1} > y_{2} > ⋯ > y_{2k} and y_{2k} < y_{2k+1} for some k ≥ 1. By convention, y_{n+1} = ∞. We could also say that the leftmost trough of w occurs at an even position. This notion was introduced by Désarménien [De84] and elegantly used in a subsequent paper [DW88]. A further refinement is due to Gessel [Ge91].

Let σ = σ(1)σ(2) ⋯ σ(n) be a permutation. Unless σ is increasing, there is always a nonempty right factor of σ which is a desarrangement. It then makes sense to define σ^{d} as the longest such a right factor. Hence, σ admits a unique factorization σ = σ^{p}σ^{d}, called the pixed factorization, where σ^{p} is increasing and σ^{d} is the longest right factor of σ which is a desarrangement. The set (resp. number) of the letters in σ^{p} is denoted by PIX σ (resp. pix σ).

If σ^{d} = σ(n − m + 1)σ(n − m + 2) ⋯ σ(n) and if “red” is the increasing bijection mapping the set {σ(n − m + 1), σ(n − m + 2), …, σ(n)} onto {1, 2, …, m}, define

(1.10) Desar σ := red σ(n − m + 1) red σ(n − m + 2) … red σ(n);
(1.11) mag σ := ∑_{i∈PIX σ}i − ∑_{i=1}^{pix σ} i + imaj ∘ Desar σ.

Note that Desar σ is a desarrangement and belongs to 𝔖_{m}, for short, a desarrangement of order m. Also note that σ is fully characterized by the pair (PIX σ, Desar σ), which will called the pixed decomposition of σ. Form the inverse (Desar σ)^{−1} = y_{1}y_{2} ⋯ y_{m} of Desar σ and define ZDesar(σ) to be the unique shuffle x_{1}x_{2} ⋯ x_{n} of 0^{n−m} and y_{1}y_{2} ⋯ y_{m}, where x_{i} = 0 if and only if i ∈ PIX σ.

Example. With σ = 3 5 7 4 2 8 1 9 6, then σ^{p} = 3 5 7, σ^{d} = 4 2 8 1 9 6, PIX σ = {3, 5, 7}, pix σ = 3. Also, Desar σ = 3 2 5 1 6 4, imaj ∘ Desar σ = 1 + 2 + 4 = 7, (Desar σ)^{−1} = 4 2 1 6 3 5, ZDesar σ = 4 2 0 1 0 6 0 3 5 and mag σ = (3 + 5 + 7) − (1 + 2 + 3) + 7 = 16.

Referring to the diagram in Fig. 1 the purpose of this paper is to prove the next two theorems.

Theorem 1.2. In each of the following four groups the pairs of statistics are equidistributed on 𝔖_{n}:

(1) (fix, maj), (fix, maf), (fix, maz), (pix, mag), (pix, inv), (pix, imaj);

(2) (FIX, maf), (PIX, mag), (PIX, inv);

(3) (fix, DEZ), (fix, DES), (pix, IDES);

(4) (FIX, DEZ), (PIX, IDES).

Theorem 1.3. In each of the following two groups the triplets of statistics are equidistributed on 𝔖_{n}:

(1) (fix, maf, Der) and (fix, maz, Der);

(2) (pix, mag, Desar) and (pix, imaj, Desar). Furthermore, the following diagram, involving the bijections DW^{loc}, F_{3} and F′_{3} is commutative.

[figure: _{𝔖_{n}}; _{𝔖_{n}}; _{𝔖_{n}}; _{𝔖_{n}}; ⟶^{DW^{loc}}; _{_{DW}_{loc}}; _{_{F}′_{3}}; _{_{F}_{3}}; ZDesar; ^{𝔖n^{Der}}; ^{𝔖n^{Der}}; ^{𝔖n^{Desar}}; ^{𝔖n^{Desar}}; ZDer; ZDer; ZDesar; ^{^{F}^{3}}; ^{^{F}^{3}}; dw; dw]

Fig. 2

2. The bijections

2.1. The transformations Φ and “ CHZ”. In our preceding paper [FoHa07] we have given the constructions of two bijections Φ, F_{3} of 𝔖_{n} onto itself. The latter one will be re-studied and used in Section 3. As was shown in our previous paper [FoHa07], the first one has the following property:

(2.1)  (fix, DEZ, Der) σ = (fix, DES, Der) Φ(σ) (σ ∈ 𝔖_{n}).

This shows that over 𝔖_{n} the pairs (fix, maz) and (fix, maj) are equidistributed over 𝔖_{n}, their generating polynomial being given by the polynomial A_{n}(Y, q) introduced in (1.2). Also the triplets (fix, dez, maz) and (fix, des, maj) are equidistributed, with generating polynomial A_{n}(Y, t, q) introduced in (1.1).

In [CHZ97] the authors have constructed a bijection, here called “CHZ”, satisfying

(2.2)  (fix, maf, Der) σ = (fix, maj, Der) CHZ(σ) (σ ∈ 𝔖_{n}).

2.2. The Désarménien-Wachs bijection. For each n ≥ 0 let D_{n} denote the set of permutations σ from 𝔖_{n} such that FIX σ = ∅. The elements of D_{n} are referred to as the derangements of order n. Let K_{n} be the set of permutations σ from 𝔖_{n} such that PIX σ = ∅. The class K_{n} was introduced by Désarménien [De84], who called its elements desarrangements of order n. He also set up a one-to-one correspondence between D_{n} and K_{n}. Later, by means of a symmetric function argument Désarménien and Wachs [DW88] proved that for every subset J ⊂ [n − 1] the equality

(2.3)  #{σ ∈ D_{n} : DES σ = J} = #{σ ∈ K_{n} : IDES σ = J}

holds. In a subsequent paper [DW93] they constructed a bijection DW : D_{n} → K_{n} having the expected property, that is,

(2.4)  IDES ∘DW(σ) = DES σ.

Although their bijection is based on an inclusion-exclusion argument, leaving the door open to the discovery of an explicit correspondence, we use it as such in the sequel. For the very definition of “DW” we refer the reader to their original paper [DW93].

We now make a full use of the fixed and pixed decompositions introduced in §§ 1.1 and 1.2. Let τ ∈ 𝔖_{n} and consider the chain

(2.5)  τ ↦ (FIX τ, Der τ) ↦ (FIX τ, DW ∘ Der τ) ↦ σ,

where σ is the permutation defined by

(2.6)  (PIX σ, Desar σ) := (FIX τ, DW ∘ Der τ).

Then, the mapping DW^{loc} defined by

(2.7)  DW^{loc}(τ) := σ,

is a bijection of 𝔖_{n} onto itself satisfying FIX τ = PIX σ and DES ∘ Der τ = IDES ∘ Desar σ. In particular, fix τ = pix σ. Taking the definitions of “maf” and “mag” given in (1.9) and (1.11) into account we have:

maf τ = ∑_{i∈FIXτ} i − ∑_{i=1}^{fix τ} i + maj ∘ Der τ

= ∑_{i∈PIXσ} i − ∑_{i=1}^{pix σ} i + imaj ∘ Desar σ = mag σ.

We have then proved the following proposition.

Proposition 2.1. Let σ := DW^{loc}(τ). Then

(2.8) FIX τ = PIX σ, DES ∘ Der τ = IDES ∘ Desar σ, maf τ = mag σ.

Corollary 2.2. The pairs (FIX, maf) and (PIX, mag) are equidistributed over 𝔖_{n}.

Example. Assume that the bijection “DW” maps the derangement 512364 onto the desarrangement 623145. On the other hand, the fixed decomposition of τ = 182453697 is equal to ({1, 4, 5}, 512364) and ({1, 4, 5}, 623145) is the pixed decomposition of the permutation σ = 145936278. Hence DW^{loc}(182453697) = 145936278.

We verify that DES ∘ Der τ = DES(512364) = {1, 5} = IDES(623145) = IDES ∘ Desar σ. Also maf τ = (1+4+5)−(1+2+3)+(1+5) = 10 = mag σ.

Proposition 2.3. Let σ := DW^{loc}(τ). Then

(2.9)  (FIX, DEZ) τ = (PIX, IDES) σ;
(2.10)  (fix, maz) τ = (pix, imaj) σ.

Proof. It suffices to prove (2.9) and in fact only DEZ τ = IDES σ. Let σ^{p}σ^{d} be the pixed factorization of σ. Then σ^{p} is the increasing sequence of the elements of PIX σ = FIX τ. We have i ∈ DEZ τ if and only if τ(i) ≠ i and one of the following conditions holds:

(1) τ(i) > τ(i + 1) and τ(i + 1) ≠ i + 1;

(2) τ(i + 1) = i + 1. In case (1) the letters red τ(i) and red τ(i+1) are adjacent letters in Der τ and red τ(i) > red τ(i + 1). As DES ∘ Der τ = IDES ∘ Desar σ, the letter red(i + 1) is to the left of the letter red(i) in Desar σ and then (i + 1) is to the left of i is σ, so that i ∈ IDES σ.

In case (2) we have (i+1) ∈ FIX τ = PIX σ and red i is a letter of Desar σ. Again i ∈ IDES σ.

Corollary 2.4. The pairs (FIX, DEZ) and (PIX, IDES) are equidistributed over 𝔖_{n}.

Using the same example as above we have: τ = 182453697, FIX τ = {1, 4, 5}, ZDer τ = 082003697, so that DEZ τ = {2, 3, 8}. Moreover, σ = DW^{loc}(182453697) = 145 | 936278. Hence 2, 8 ∈ IDES σ (case (1)) and 3 ∈ IDES σ (case (2)).

2.3. The second fundamental transformation. As described in [Lo83, p. 201, Algorithm 10.6.1] by means of an algorithm, the second fundamental transformation, further denoted by F_{2}, can be defined on permutations as well as on words. Here we need only consider the case of permutations. As usual, the number of inversions of a permutation σ = σ(1)σ(2) ⋯ σ(n) is defined by inv σ := #{(i, j) | 1 ≤ i < j ≤ n, σ(i) > σ(j)}. Its construction was given in [Fo68]. Further properties have been proved in [FS78], [BjW88]. Here we need the following result.

Theorem 2.5 [FS78]. The transformation F_{2} defined on the symmetric group 𝔖_{n} is bijective and the following identities hold for every permutation σ ∈ 𝔖_{n}: inv F_{2}(σ) = maj σ; IDES F_{2}(σ) = IDES σ.

Using the composition product F′_{2} := i ∘ F_{2} ∘ i we therefore have:

(2.11)  inv F′_{2}(σ) = imaj σ; DES F′_{2}(σ) = DES σ

for every σ ∈ 𝔖_{n}.

As the descent set “DES” is preserved under the transformation F′_{2}, each desarrangement is mapped onto another desarrangement. It then makes sense to consider the chain:

σ ↦ (PIX σ, Desar σ) ↦ (PIX σ, F′_{2} ∘ Desar σ) ↦ ρ,

where (PIX ρ, Desar ρ) := (PIX σ, F′_{2} ∘ Desar σ). The mapping F_{2}^{loc} : σ ↦ ρ is a bijection of 𝔖_{n} onto itself. Moreover, PIX σ = PIX ρ, imaj ∘ Desar σ = inv ∘ Desar ρ and DES ∘ Desar σ = DES ∘ Desar ρ. Hence,

mag σ = ∑_{i∈PIX σ} i − ∑_{i=1}^{pix σ} i + imaj ∘ Desar σ

= ∑_{i∈PIX ρ} i − ∑_{i=1}^{pix ρ} i + inv ∘ Desar ρ
= #{(i, j) : 1 ≤ i ≤ pix ρ < j ≤ n, ρ(i) > ρ(j)}
+ #{(i, j) : pix ρ < i < j ≤ n, ρ(i) > ρ(j)}
= inv ρ.

We have then proved the following proposition.

Proposition 2.6. Let ρ := F_{2}^{loc}(σ). Then

(2.12)  (PIX, mag) σ = (PIX, inv) ρ.

Corollary 2.7. The pairs (PIX, mag) and (PIX, inv) are equidistributed over 𝔖_{n}.

Finally, go back to Properties (2.11) and let ξ := F′_{2}(ρ). Also let ξ^{p}ξ^{d} and ρ^{p}ρ^{d} be the pixed factorizations of ξ and ρ, respectively. We do not have ξ^{p} = ρ^{p} necessarily, but as ρ and ξ have the same descent set, the factors ξ^{p} and ρ^{p} have the same length, i.e., pix ξ = pix ρ. Let us state this result in the next proposition.

Proposition 2.8. Let ξ := F′_{2}(ρ). Then

(2.13)  (pix, inv) ξ = (pix, imaj) ρ.

Corollary 2.9. The pairs (pix, inv) and (pix, imaj) are equidistributed over 𝔖_{n}.

Finally, DW^{glo} attached to the unique oblique arrow in Fig. 1 refers to the global bijection constructed by Désarménien and Wachs ([DW93], § 5). It has the property: (fix, DES) DW^{glo}(σ) = (pix, IDES) σ for all σ in 𝔖_{n}. The big challenge is to find two explicit bijections f and g, replacing DW^{glo} and DW^{loc}, such that (fix, DES) g(σ) = (pix, IDES) σ and (PIX, IDES) f(σ) = (FIX, DEZ) σ, which would make the bottom triangle commutative, that is, Φ = g ∘ f.

3. The bijections F_{3} and F′_{3}

Let 0 ≤ m ≤ n and let v be a nonempty word of length m, whose letters are positive integers (with possible repetitions). Designate by Sh(0^{n−m}v) the set of all shuffles of the words 0^{n−m} and v, that is, the set of all rearrangements of the juxtaposition product 0^{n−m}v, whose longest subword of positive letters is v. Let w = x_{1}x_{2} ⋯ x_{n} be a word from Sh(0^{n−m}v). It is convenient to write: Pos w := v, Zero w := {i : 1 ≤ i ≤ n, x_{i} = 0}, zero w := # Zero w (= n − m), so that w is completely characterized by the pair (Zero w, Pos w). Besides the statistic “maj” we will need the statistic “mafz” that associates the number

(3.1)  mafz w := ∑_{i∈Zero w} i − ∑_{i=1}^{zero w} i + maj Pos w.

with each word from Sh(0^{n−m}v). In ([FoHa07], §4) we gave the construction of a bijection F_{3} of Sh(0^{n−m}v) onto itself having the following property:

(3.2)  maj w = mafz F_{3}(w) (w ∈ Sh(0^{n−m}v)).

The bijection F_{3} is now applied to each shuffle class Sh(0^{n−m}v), when v is a derangement, or the inverse of a desarrangement. Let

𝔖_{n}^{Der} := ⋃_{m,v} Sh(0^{n−m}v) (0 ≤ m ≤ n, v ∈ D_{m});
𝔖_{n}^{Desar} := ⋃_{m,v} Sh(0^{n−m}v) (0 ≤ m ≤ n, v^{−1} ∈ K_{m}).

As already seen in § 1.1, the mapping ZDer is a bijection of 𝔖_{n} onto 𝔖_{n}^{Der} satisfying

(3.3)

FIX σ = Zero ZDer(σ); Der σ = Pos ZDer(σ);
maf σ = mafz ZDer(σ); DEZ σ = DES ZDer(σ).

Example 3.2. Let σ = 1 7 3 5 2 6 4. Then w := ZDer(σ) = 0 4 0 3 1 0 2. We have FIX σ = Zero w = {1, 3, 6}; Der σ = Pos w = 4 3 1 2; maf σ = mafz w = (1+3+6)−(1+2+3)+(1+2+3) = 10, DEZ σ = DES w = {2, 4, 5}.

Now define the bijection F_{3} of 𝔖_{n} onto itself by the chain

(3.4)  F_{3} : σ ↦^{ZDer} w ↦^{F_{3}} w′ ↦^{ZDer^{−1}} σ′.

Then, by (3.2),

(fix, maz, Der) σ = (zero, maj, Pos) w

= (zero, mafz, Pos) w′ = (fix, maf, Der) σ′,

(3.5)  (fix, maz, Der) σ = (fix, maf, Der) F_{3}(σ).

The map “Desar” has been defined in (1.10) and it was noticed that each permutation σ was fully characterized by the pair (PIX σ, Desar σ). Another way of deriving ZDesar(σ) introduced in §1.2 is to form the inverse σ^{−1} = σ^{−1}(1)σ^{−1}(2) ⋯ σ^{−1}(n) of σ. As σ^{−1}(i) ≥ pix σ + 1 if and only if i ∈ [ n] \ PIX σ, we see that ZDesar(σ) is also the word w = x_{1}x_{2} ⋯ x_{n}, where

x_{i} := \{ \begin{matrix}0, & if i ∈ PIX σ; \\ σ^{−1}(i) − pix σ, & if i ∈ [ n] \ PIX σ. \end{matrix}

The word σ^{−1} contains the subword 1 2 ⋯ pix σ. We then have: i ∈ IDES σ ⇔ i ∈ DES σ^{−1} ⇔ σ^{−1}(i) ≥ pix σ + 1 and σ^{−1}(i) > σ^{−1}(i + 1) ⇔ x_{i} ≥ 1 and x_{i} > x_{i+1} ⇔ i ∈ DES w, so that IDES σ = DES w.

On the other hand, as PIX σ = Zero w and (Desar σ)^{−1} = Pos w, we also have, by (1.11)

mag σ = ∑_{i∈PIX σ} i − ∑_{i=1}^{pix σ} i + imaj ∘ Desar σ

= ∑_{i∈Zero w} i − ∑_{i=1}^{zero w} i + maj ∘ Pos w = mafz w.

As a summary,

(3.6)

PIX σ = Zero ZDesar(σ); Desar σ = Pos ZDesar(σ);
mag σ = mafz ZDesar(σ); IDES σ = DES ZDesar(σ).

Example 3.3. Let σ = 1 3 6 5 4 7 2. Then σ^{−1} = 1 7 2 5 4 3 6; w := ZDesar(σ) = 0 4 0 2 1 0 3, PIX σ = Zero w = {1, 3, 6}; Desar σ = 3 2 4 1, (Desar σ)^{−1} = Pos w = 4 2 1 3; mag σ = mafz w = (1 + 3 + 6) − (1 + 2 + 3) + (1 + 2) = 7, IDES σ = DES w = {2, 4, 5}.

Next define the bijection F′_{3} of 𝔖_{n} onto itself by the chain

(3.7)  F′_{3} : σ ↦^{ZDesar} w ↦^{F_{3}} w′ ↦^{ZDesar^{−1}} σ′.

Then, by (3.2),

(pix, imaj, Desar) σ = (zero, maj, Pos) w

= (zero, mafz, Pos) w′ = (pix, mag, Desar) σ′,

(3.8)  (pix, imaj, Desar) σ = (pix, mag, Desar) F′_{3}(σ).

With (3.5) and (3.8) the first part of Theorem 1.3 is proved.

The second part of Theorem 1.3 is proved as follows. Remember that, if zero w = n − m, the pair (Zero w, Pos w) uniquely determines the shuffle of (n − m) letters equal to 0 into the letters of Pos w. The bijection “dw” defined by dw := ZDesar ∘ DW^{loc} ∘ ZDer^{−1} can also be derived by the chain

(3.9) dw : w ↦ (Zero w, Pos w)

↦ (Zero w, (DW ∘ Pos w)^{−1}) = (Zero w′, Pos w′) ↦ w′,

where DW denotes the Désarménien-Wachs bijection. It maps 𝔖_{n}^{Der} onto 𝔖_{n}^{Desar}. In particular,

Pos ∘ dw w = (DW ∘ Pos w)^{−1}; Zero ∘ dw(w) = Zero w.

Because of (2.4) we also have DES ∘ Pos w = DES ∘ Pos w′. As shown in our previous paper ([FoHa07], Proposition 4.1), the latter property implies that

Zero ∘F_{3}(w) = Zero ∘F_{3}(w′).

Furthermore,

Pos ∘F_{3}(w) = Pos w, Pos ∘F_{3}(w′) = Pos w′,

since F_{3} maps each shuffle class onto itself. Hence,

Zero ∘ dw ∘F_{3}(w) = Zero ∘F_{3}(w);
Pos ∘ dw ∘F_{3}(w) = (DW ∘ Pos F_{3}(w))^{−1} = (DW ∘ Pos w)^{−1};
Zero ∘F_{3} ∘ dw(w) = Zero ∘F_{3}(w);
Pos ∘F_{3} ∘ dw(w) = Pos ∘ dw(w) = (DW ∘ Pos w)^{−1}.

The word dw ∘F_{3}(w) is characterized by the pair

(Zero ∘ dw ∘F_{3}(w), Pos ∘ dw ∘F_{3}(w)),

which is equal to the pair (Zero ∘F_{3} ∘ dw(w), Pos ∘F_{3} ∘ dw(w)),

which corresponds itself to the word F_{3}(w) ∘ dw(w). Hence,

(3.10)  dw ∘F_{3} = F_{3} ∘ dw .

This shows that the top square in Fig. 2 is a commutative diagram, so is the bottom one.

Example 3.4. Noting that DW(4 3 1 2) = 3 2 4 1 we have the commutative diagram

3 5 6 4 2 7 1 1 3 6 5 4 7 2 7 4 3 1 5 6 2 1 7 3 5 2 6 4 ⟶^{DW^{loc}} ⟶^{DW^{loc}}  _{_{F{′ \atop 3}}↑}_{_{F_{3}}↑}

References

[BjW88] Anders Björner, Michelle L. Wachs. Permutation Statistics and Linear Extensions of Posets, J. Combin. Theory, Ser. A, 58 (1991), pp. 85–114.

[CHZ97] Robert J. Clarke, Guo-Niu Han, Jiang Zeng. A combinatorial interpretation of the Seidel generation of q-derangement numbers, Annals of Combinatorics, 4 (1997), pp. 313–327.

[De84] Jacques Désarménien. Une autre interprétation du nombre de dérangements, Séminaire Lotharingien de Combinatoire, [B08b], 1984, 6 pages.

[DW88] Jacques Désarménien, Michelle L. Wachs. Descentes des dérangements et mots circulaires, Séminaire Lotharingien de Combinatoire, [B19a], 1988, 9 pages.

[DW93] Jacques Désarménien, Michelle L. Wachs. Descent Classes of Permutations with a Given Number of Fixed Points, J. Combin. Theory, Ser. A, 64 (1993), pp. 311– 328.

[Fo68] Dominique Foata. On the Netto inversion number of a sequence, Proc. Amer.

Math. Soc., 19 (1968), pp. 236–240.

[FoHa07] Dominique Foata, Guo-Niu Han. Fix-Mahonian Calculus, I: two transforma-

tions, preprint, 2007, 14 pages.

[FS78] Dominique Foata, M.-P. Schützenberger. Major Index and Inversion number of

Permutations, Math. Nachr., 83 (1978), pp. 143–159.

[GaRa90] George Gasper, Mizan Rahman. Basic Hypergeometric Series, London, Cam-

bridge Univ. Press, 1990 (Encyclopedia of Math. and Its Appl., 35).

[Ge91] Ira Gessel. A coloring problem, Amer. Math. Monthly, 98 (1991), pp. 530–533.

[GeRe93] Ira Gessel, Christophe Reutenauer. Counting Permutations with Given Cycle

Structure and Descent Set, J. Combin. Theory Ser. A, 64 (1993), pp. 189–215.

[Lo83] M. Lothaire. Combinatorics on Words, Addison-Wesley, London 1983 (Encyclopedia of Math. and its Appl., 17).

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

foata@math.u-strasbg.fr

Guo-Niu Han

I.R.M.A. UMR 7501

Université Louis Pasteur et CNRS 7, rue René-Descartes F-67084 Strasbourg, France

                       guoniu@math.u-strasbg.fr