Séminaire Lotharingien de Combinatoire 53 (2005), Article B53b

A FOATA BIJECTION FOR THE ALTERNATING GROUP AND FOR q-ANALOGUES

DAN BERNSTEIN AND AMITAI REGEV

Abstract. The Foata bijection Φ : S_{n} → S_{n} is extended to the bijections Ψ : A_{n+1} → A_{n+1} and Ψ_{q} : S_{n+q−1} → S_{n+q−1}, where S_{m}, A_{m} are the symmetric and the alternating groups. These bijections imply bijective proofs for recent equidistribution theorems, by Regev and Roichman, for A_{n+1} and for S_{n+q−1}.

1. Introduction

In [MM16] MacMahon proved his remarkable theorem about the equidistribution in the symmetric group S_{n} of the length (or the inversion-number) and the major index statistics. This raised the natural question of constructing a canonical bijection on S_{n}, for each n, that would correspond these length and major index statistics, and would thus yield a bijective proof of that theorem of MacMahon. That problem was solved by Foata [Foa68], who constructed such a canonical bijection, see Section 3 for a discussion of the Foata bijection Φ. Throughout the years, MacMahon’s equidistribution theorem has received far reaching refinements and generalizations, see for example [BW91], [Car54], [Car75], [FS78], [GG79],

[Kra95] and [Sta02].

We remark that MacMahon’s equidistribution theorem fails when the S_{n} statistics are restricted to the alternating subgroups A_{n}. However, by introducing new A_{n} statistics which are natural analogues of the S_{n} statistics, in [RR04], analogous equidistribution theorems were proved for A_{n}. This was done by first formulating the above S_{n} statistics in terms of the Coxeter ganerators s_{i} = (i, i + 1), 1 ≤ i ≤ n − 1. By choosing the “Mitsuhashi” generators a_{i} = s_{1}s_{i+1} for A_{n+1} [Mit01], analogous statistics on A_{n+1} were obtained, via canonical presentations by these generators. These canonical presentations allow the introduction of the map f : A_{n+1} → S_{n}, which is one of the main tools in [RR04], see Section 2 for a discussion of these presentations and of f.

MacMahon-type theorems were obtained in [RR04] by introducing the delent statistics for these groups (for S_{n}, this statistic already appeared in [BW91]). Via the above map f : A_{n+1} → S_{n}, equidistribution theorems were then lifted from S_{n} to A_{n+1}, thus yielding (new) equidistribution theorems for A_{n+1}. In particular, equidistribution theorems for the A_{n+1}-analogues of the length and (reverse) major-index statistics were obtained in this way, see for example Theorem 4.9 below.

These theorems naturally raise the question of constructing an A_{n+1}-analogue of the Foata bijection — with analogous properties. This problem is solved in Section 5, where indeed we construct such a map Ψ. That map Ψ is composed of a reflection of Foata’s original bijection Φ, together with the map f : A_{n+1} → S_{n} and of certain “local” inversions of f. This of course gives a new — bijective — proof of Theorem 4.9.

Statistics on symmetric groups which are q-analogues of the classical S_{n} statistics were introduced in [RR05], via S_{n} canonical presentations and the maps f_{q} : S_{n+q−1} → S_{n}, see Section 7 below. This map f_{q} sends the q statistics on S_{n+q−1} to the corresponding classical statistics on S_{n}. As in the case of A_{n+1}, this allows the lifting of equidistribution theorems from S_{n} to S_{n+q−1}. This was done in [RR05], where in that process an interesting connection with dashed patterns in permutations has appeared, see Theorems 7.7 and 7.8 below.

Again, these equidistribution theorems naturally raise the question of finding the (q-)ana-logue of the Foata bijection. In Section 7 we indeed construct such a bijection Ψ_{q}. As in the case of Ψ, the bijection Ψ_{q} is composed of f_{q}, of a reflection of the original Foata bijection Φ, and of certain “local” inversions of f_{q}. As an application, Ψ_{q} yields new — bijective — proofs of Theorems 7.7 and 7.8.

The paper is organized as follows. Sections 2, 3 and 4 contain preliminary material, mostly from [Foa68], [RR04] and [RR05], which is necessary for defining and studying the bijections Ψ and Ψ_{q}. A reader who is familiar with these three papers can skip these preliminary sections. In Section 5 we introduce and study Ψ, and Section 6 is an example, showing the properties of Ψ. Finally, the bijections Ψ_{q} are introduced and studied in Section 7.

2. Canonical presentations and the covering map

2.1. The S- and A-canonical presentations. In this subsection we review the presentations of elements in S_{n} and A_{n} by the corresponding generators and procedures for calculating them.

The Coxeter generators of S_{n} are s_{i} = (i, i + 1), 1 ≤ i ≤ n − 1. Recall the definition of the set R_{j}^{S},

R_{j}^{S} = {1, s_{j}, s_{j}s_{j−1}, …, s_{j}s_{j−1} ⋯ s_{1}} ⊆ S_{j+1},

and the following theorem.

Theorem 2.1 (see [Gol93, pp. 61–62]). Let w ∈ S_{n}. Then there exist unique elements w_{j} ∈ R_{j}^{S}, 1 ≤ j ≤ n − 1, such that w = w_{1} ⋯ w_{n−1}. Thus, the presentation w = w_{1} ⋯ w_{n−1} is unique. Call that presentation the S-canonical presentation of w.

The number of s_{i} in the S-canonical presentation of σ ∈ S_{n} is its S-length, ℓ_{S}(σ). The descent set of σ ∈ S_{n} is Des_{S}(σ) = { i | σ(i) > σ(i + 1) }; the S major-index is maj_{S}(σ) = ∑_{i∈Des_{S}(σ)} i, and the reverse S_{n} major-index is rmaj_{S_{n}}(σ) = ∑_{i∈Des_{S}(σ)}(n − i). Note that i ∈ Des_{S}(σ) iff ℓ_{S}(σ) > ℓ_{S}(σs_{i}).

The S-procedure is a simple way to calculate the S-canonical presentation of a given element in S_{n}. Let σ ∈ S_{n}, σ(r) = n, σ = […, n, …]. Then by definition of the s_{i}s, n can be ‘pulled to its place on the right’: σs_{r}s_{r+1} ⋯ s_{n−1} = […, n]. This gives w_{n−1} = s_{n−1} ⋯ s_{r+1}s_{r} ∈ R_{n−1}^{S}. Looking at σw_{n−1}^{−1} = σs_{r}s_{r+1} ⋯ s_{n−1} = […, n − 1, …, n] now, pull n − 1 to its right place (second from the right) by a similar product s_{t}s_{t+1} ⋯ s_{n−2}, yielding w_{n−2} = s_{n−2} ⋯ s_{t} ∈ R_{n−2}^{S}. Continue this way until finally σ = w_{1} ⋯ w_{n−1}.

Example 2.2. Let σ = [5, 6, 3, 2, 1, 4], then w_{5} = s_{5}s_{4}s_{3}s_{2}; σw_{5}^{−1} = [5, 3, 2, 1, 4, 6], so in order to ‘pull 5 to its place’ we need w_{4} = s_{4}s_{3}s_{2}s_{1}; now σw_{5}^{−1}w_{4}^{−1} = [3, 2, 1, 4, 5, 6], so no need to move 4, hence w_{3} = 1; continuing the same way, check that w_{2} = s_{2}s_{1} and w_{1} = s_{1}, so σ = w_{1}w_{2}w_{3}w_{4}w_{5} = (s_{5}s_{4}s_{3}s_{2})(s_{4}s_{3}s_{2}s_{1})(1)(s_{2}s_{1})(s_{1}). Thus ℓ_{S}(σ) = 11. Here Des_{S} σ = {2, 3, 4}, so maj_{S}(σ) = rmaj_{S_{6}}(σ) = 9.

For A_{n}, the “Mitsuhash” generators are a_{i} = s_{1}s_{i+1}, 1 ≤ i ≤ n − 2. Recall the definition

R_{j}^{A} = {1, a_{j}, a_{j}a_{j−1}, …, a_{j} ⋯ a_{2}, a_{j} ⋯ a_{2}a_{1}, a_{j} ⋯ a_{2}a_{1}^{−1}} ⊆ A_{j+2}

(for example, R_{3}^{A} = {1, a_{3}, a_{3}a_{2}, a_{3}a_{2}a_{1}, a_{3}a_{2}a_{1}^{−1}}), and the following theorem.

Theorem 2.3 (see [RR04, Theorem 3.4]). Let v ∈ A_{n+1}. Then there exist unique elements v_{j} ∈ R_{j}^{A}, 1 ≤ j ≤ n − 1, such that v = v_{1} ⋯ v_{n−1}, and this presentation is unique. Call that presentation the A-canonical presentation of v.

The number of a_{i} in the A-canonical presentation of σ ∈ A_{n+1} is defined to be its Alength, ℓ_{A}(σ). In analogy with S_{n}, the A-descent set of σ ∈ A_{n+1} is defined as Des_{A}(σ) = { i | ℓ_{A}(σ) ≥ ℓ_{A}(σa_{i}) }. Now define maj_{A}(σ) = ∑_{i∈Des_{A}(σ)} i, and rmaj_{A_{n+1}}(σ) = ∑_{i∈Des_{A}(σ)}(n−i), see [RR05].

The A-procedure is a simple procedure for obtaining the A-canonical presentation of σ ∈ A_{n}. A-procedure: Step 1: follow the S-procedure and obtain the S-canonical presentation of σ ∈ A_{n}. Step 2: pair the factors. Step 3: insert s_{1}s_{1} in the middle of each pair and obtain the A-canonical presentation.

Example 2.4. . Let σ = [6, 4, 3, 7, 5, 2, 1]. Step 1: σ = s_{1}s_{2}s_{1}s_{3}s_{2}s_{1}s_{4}s_{3}s_{5}s_{4}s_{3}s_{2}s_{1}s_{6}s_{5}s_{4}. Step 2: σ = (s_{1}s_{2})(s_{1}s_{3})(s_{2}s_{1})(s_{4}s_{3})(s_{5}s_{4})(s_{3}s_{2})(s_{1}s_{6})(s_{5}s_{4}). Step 3: σ = (s_{1}s_{1}s_{1}s_{2})(s_{1}s_{1}s_{1}s_{3})(s_{2}s_{1}s_{1}s_{1})(s_{4}s_{1}s_{1}s_{3})(s_{5}s_{1}s_{1}s_{4})(s_{3}s_{1}s_{1}s_{2})(s_{1}s_{1}s_{1}s_{6})(s_{5}s_{1}s_{1}s_{4}) = = (s_{1}s_{2})(s_{1}s_{3})(s_{2}s_{1})(s_{1}s_{4}s_{1}s_{3})(s_{1}s_{5}s_{1}s_{4})(s_{1}s_{3}s_{1}s_{2})(s_{1}s_{6})(s_{1}s_{5}s_{1}s_{4}) = = a_{1}a_{2}a_{1}^{−1}a_{3}a_{2}a_{4}a_{3}a_{2}a_{1}a_{5}a_{4}a_{3} = (a_{1})(a_{2}a_{1}^{−1})(a_{3}a_{2})(a_{4}a_{3}a_{2}a_{1})(a_{5}a_{4}a_{3}). Thus ℓ_{A}(σ) = 12 (while ℓ_{S}(σ) = 16). It can be shown here that Des_{A}(σ) = {1, 3, 4, 5}, hence rmaj_{A_{7}}(σ) = 10.

2.2. The covering map f. We can now introduce the covering map f, which plays an important role in later sections in the constructions of the bijections Ψ and Ψ_{q}.

Definition 2.5 (see [RR04, Definition 5.1]). Define f : R_{j}^{A} → R_{j}^{S} by (1) f(a_{j}a_{j−1} ⋯ a_{ℓ}) = s_{j}s_{j−1} ⋯ s_{ℓ} if ℓ ≥ 2, and

(2) f(a_{j} ⋯ a_{1}) = f(a_{j} ⋯ a_{1}^{−1}) = s_{j} ⋯ s_{1}. Now extend f : A_{n+1} → S_{n} as follows: let v ∈ A_{n+1}, v = v_{1} ⋯ v_{n−1} its A-canonical presentation, then

f(v) := f(v_{1}) ⋯ f(v_{n−1}),

which is clearly the S-canonical presentation of f(v).

3. The Foata bijection

The second fundamental transformation on words Φ was introduced in [Foa68] (for a full description, see [Lot83, §10.6]). It is defined on any finite word r = x_{1}x_{2} … x_{m} whose letters x_{1}, …, x_{m} belong to a totally ordered alphabet.

Definition 3.1. Let X be a totally ordered alphabet, let r = x_{1}x_{2} … x_{m} be a word whose letters belong to X, and let x ∈ X such that x_{m} ≤ x (respectively x_{m} > x). Let

r = r^{1}r^{2} … r^{p}

be the unique decomposition of r into subwords r^{i} = r_{1}^{i}r_{2}^{i} … r_{m_{i}}^{i}, 1 ≤ i ≤ p, such that r_{m_{i}}^{i} ≤ x (respectively r_{m_{i}}^{i} > x) and r_{j}^{i} > x (respectively r_{j}^{i} ≤ x) for all 1 ≤ j < m_{i}. Define γ_{x}(r) by

γ_{x}(r) = r_{m_{1}}^{1}r_{1}^{1}r_{2}^{1} … r_{m_{1}−1}^{1}r_{m_{2}}^{2}r_{1}^{2} … r_{m_{2}−1}^{2} … r_{m_{p}}^{p}r_{1}^{p} … r_{m_{p}−1}^{p}.

For example, with the usual order on the integers, r = 1 2 6 7 8 3 4 and x = 5, r decomposes into r^{1} = 1, r^{2} = 2, r^{3} = 6 7 8 3 and r^{4} = 4, so

γ_{5}(1 2 6 7 8 3 4) = 1 2 3 6 7 8 4.

Definition 3.2. Define Φ recursively as follows. First, Φ(r) := r if r is of length 1. If x is a letter and r is a nonempty word, define Φ(rx) = γ_{x}(Φ(r)) x.

For example,

Φ(6 5 3 1 4 2) = γ_{2}(γ_{4}(γ_{1}(γ_{3}(γ_{5}(6) 5) 3) 1) 4) 2
= γ_{2}(γ_{4}(γ_{1}(γ_{3}(6 5) 3) 1) 4) 2
= γ_{2}(γ_{4}(γ_{1}(6 5 3) 1) 4) 2
= γ_{2}(γ_{4}(6 5 3 1) 4) 2
= γ_{2}(3 6 5 1 4) 2
= 3 6 5 4 1 2.

The following algorithmic description of Φ from [FS78] is more useful in calculations.

Algorithm 3.3 (Φ). Let r = x_{1}x_{2} … x_{m} ; 1. Let i := 1, r′_{i} := x_{1} ;

2. If i = m, let Φ(r) := r′_{i} and stop; else continue;

3. If the last letter of r′_{i} is less than or equal to (respectively greater than) x_{i+1}, cut r′_{i} after every letter less than or equal to (respectively greater than) x_{i+1} ;

4. In each compartment of r′_{i} determined by the previous cuts, move the last letter in the compartment to the beginning of it; let t′_{i} be the word obtained after all those moves; put r′_{i+1} := t′_{i} x_{i+1} ; replace i by i + 1 and go to step 2.

Example 3.4. Calculating Φ(r), where r = 6 5 3 1 4 2, using the algorithm:

\begin{aligned}r′_{1} & = 6 | \\ r′_{2} & = 6 | 5 | \\ r′_{3} & = 6 | 5 | 3 | \\ r′_{4} & = 6 5 3 | 1 | \\ r′_{5} & = 3 | 6 | 5 | 1 4 | \\ Φ(r) = r′_{6} & = 3 6 5 4 1 2 . \end{aligned}

The main property of Φ is the following theorem.

Theorem 3.5 (see [Foa68]). (1) Φ is a bijection of S_{n} onto itself.

(2) For every σ ∈ S_{n}, maj_{S}(σ) = ℓ_{S}(Φ(σ)).

Some further properties of Φ are given in Theorem 5.1

Let σ = [σ_{1}, σ_{2}, …, σ_{n}] ∈ S_{n}. Denote the reverse and the complement of σ by

r(σ) := [σ_{n}, σ_{n−1}, …, σ_{1}] ∈ S_{n}

and

c(σ) := [n + 1 − σ_{1}, n + 1 − σ_{2}, …, n + 1 − σ_{n}] ∈ S_{n}

respectively.

Remark 3.6. Let ρ = [n, n − 1, …, 1] ∈ S_{n}. Then for σ ∈ S_{n}, r(σ) = σρ and c(σ) = ρσ. Thus it is obvious that r and c are involutions and that rc = cr. Moreover, (r(σ))^{−1} = c(σ^{−1}).

Definition 3.7. Let \overleftarrow{Φ} := rΦr, the right-to-left Foata transformation.

While \overleftarrow{Φ}(w) is easy enough to calculate by reversing w, applying Algorithm 3.3 and reversing the result, it is easy to see that it can be calculated “directly” by applying a “right-to-left” version of the Algorithm, namely:

Algorithm 3.8 (\overleftarrow{Φ}). Let r = x_{1}x_{2} … x_{m} ; 1. Let i := m, r′_{i} := x_{m} ;

2. If i = 1, let Φ(r) := r′_{i} and stop; else continue;

3. If the first letter of r′_{i} is less than or equal to (respectively greater than) x_{m−i}, cut r′_{i} before every letter less than or equal to (respectively greater than) x_{m−i} ;

4. In each compartment of r′_{i} determined by the previous cuts, move the first letter in the compartment to the end of it; let t′_{i} be the word obtained after all those moves; put r′_{i−1} := x_{m−i} t′_{i} ; replace i by i − 1 and go to step 2.

For an example of applying Algorithm 3.8, see the calculation of \overleftarrow{Φ}(w) in Section 6.

The key property of \overleftarrow{Φ} used in this paper is the following.

Theorem 3.9. For every σ ∈ S_{n}, rmaj_{S_{n}}(σ) = ℓ_{S}(\overleftarrow{Φ}(σ)).

The proof requires the following lemmas.

Lemma 3.10. The bijections Φ : S_{n} → S_{n} and c : S_{n} → S_{n} commute with each other.

Proof. We prove a slightly stronger claim, namely that Φ and c_{k} commute as maps on ℤ^{n}, where c_{k}(a_{1}, a_{2}, …, a_{n}) := (k+1−a_{1}, k+1−a_{2}, …, k+1−a_{n}). Let σ = [σ_{1}σ_{2} … σ_{n}] ∈ ℤ^{n}. We need to show that Φc_{k}(σ) = c_{k}Φ(σ). The proof is by induction on n. For n = 1, everything is trivial. For n ≥ 2, write Φ(σ_{1} … σ_{n−1}) = b_{1} … b_{n−1} and γ_{σ_{n}}(b_{1} … b_{n−1}) = c_{1} … c_{n−1}. Using the notation \overline{a} = k + 1 − a, we have

\begin{aligned}Φc_{k}(σ) & = γ\overline{σ_{n}}(Φ(\overline{σ_{1}} \overline{σ_{2}} … \overline{σ_{n−1}})) \overline{σ_{n}} \\ & = γ\overline{σ_{n}}(\overline{b_{1}} \overline{b_{2}} … \overline{b_{n−1}}) \overline{σ_{n}} \end{aligned}

by the induction hypothesis, and

c_{k}Φ(σ) = c_{k}(c_{1} … c_{n−1} σ_{n}) = \overline{c_{1}} … \overline{c_{n−1}} \overline{σ_{n}},

so it remains to show that γ\overline{σ_{n}}(\overline{b_{1}} \overline{b_{2}} … \overline{b_{n−1}}) = \overline{c_{1}} … \overline{c_{n−1}}.

Assume for now that b_{n−1} < σ_{n} (the case b_{n−1} > σ_{n} is entirely symmetric and will be left to the reader). Let M = { 1 ≤ m ≤ n − 1 | b_{m} < σ_{n} } = {m_{1}, …, m_{p}}, m_{1} < ⋯ < m_{p}. Note that \overline{b_{n−1}} > \overline{σ_{n}} and M = \{ 1 ≤ m ≤ n − 1 | \overline{σ_{m}} > \overline{b_{n}}\}. Therefore, using the notation from Definition 3.1, we have the decompositions

b_{1} … b_{n−1} = r_{1}^{1} … r_{m_{1}}^{1} r_{1}^{2} … r_{m_{2}}^{2} … r_{1}^{p} … r_{m_{p}}^{p}

6 DAN BERNSTEIN AND AMITAI REGEV

and

\overline{b_{1}} … \overline{b_{n−1}} = \overline{r_{1}^{1}} … \overline{r_{m_{1}}^{1}} \overline{r_{1}^{2}} … \overline{r_{m_{2}}^{2}} … \overline{r_{1}^{p}} … \overline{r_{m_{p}}^{p}},

so

c_{1} … c_{n−1} = γ_{σ_{n}}(b_{1} … b_{n−1}) = r_{m_{1}}^{1} r_{1}^{1} … r_{m_{1}−1}^{1} r_{m_{2}}^{2} r_{1}^{2} … r_{m_{2}−1}^{2} … r_{m_{p}}^{p} r_{1}^{p} … r_{m_{p}−1}^{p}

and

γ\overline{σ_{n}}(\overline{b_{1}} … \overline{b_{n−1}}) = \overline{r_{m_{1}}^{1}} \overline{r_{1}^{1}} … \overline{r_{m_{1}−1}^{1}} \overline{r_{m_{2}}^{2}} \overline{r_{1}^{2}} … \overline{r_{m_{2}−1}^{2}} … \overline{r_{m_{p}}^{p}} \overline{r_{1}^{p}} … \overline{r_{m_{p}−1}^{p}}.

Thus γ\overline{σ_{n}}(\overline{b_{1}} \overline{b_{2}} … \overline{b_{n−1}}) = \overline{c_{1}} … \overline{c_{n−1}} as desired. □ Lemma 3.11. For every w ∈ S_{n}, ℓ_{S}(rc(w)) = ℓ_{S}(w). Proof. The lemma follows from the definitions of r and c and from the fact that for all σ ∈ S_{n}, ℓ_{S}(σ) = inv(σ) = #{ (i, j) | 1 ≤ i < j ≤ n, σ(i) > σ(j) }:

ℓ_{S}(w) = #{ (i, j) | 1 ≤ i < j ≤ n, w(i) > w(j) }

= #{ (i, j) | 1 ≤ i < j ≤ n, c(w)(i) < c(w)(j) }

= #{ (i, j) | 1 ≤ i < j ≤ n, rc(w)(n + 1 − i) < rc(w)(n + 1 − j) } = #{ (n + 1 − s, n + 1 − r) | 1 ≤ r < s ≤ n, rc(w)(s) < rc(w)(r) } = #{ (r, s) | 1 ≤ r < s ≤ n, rc(w)(r) > rc(w)(s) }

= ℓ_{S}(rc(w)) □

Lemma 3.12. For every w ∈ S_{n}, maj_{S}(rc(w)) = rmaj_{S_{n}}(w). Proof. By the definitions of r, c and Des_{S},

i ∈ Des_{S}(rc(w)) ⟺ rc(w)(i) > rc(w)(i + 1)
⟺ c(w)(n − i + 1) > c(w)(n − i)
⟺ n + 1 − w(n − i + 1) > n + 1 − (w)(n − i)
⟺ w(n − i + 1) < (w)(n − i)
⟺ n − i ∈ Des_{S}(w).

Therefore

maj_{S}(rc(w)) = ∑_{i∈Des_{S}(rc(w))} i = ∑_{i∈Des_{S}(w)} n − i = rmaj_{S_{n}}(w).  □

Proof of Theorem 3.9.

rmaj_{S_{n}}(σ) = maj_{S}(rc(σ))  (by Lemma 3.12)
= ℓ_{S}(Φrc(σ))  (by Theorem 3.5)
= ℓ_{S}(rcΦrc(σ))  (by Lemma 3.11)
= ℓ_{S}(\overleftarrow{Φ}(σ))  (by Lemma 3.10 and Remark 3.6)  □

4. The delent statistics

Definition 4.1 (see [RR04, Definition 7.1]). Let σ ∈ S_{n}. Define Del_{S}(σ) as

Del_{S}(σ) = { 1 < j ≤ n | ∀i < j σ(i) > σ(j) }.

These are the positions of the l.t.r.min, excluding the first position.

Definition 4.2. Let σ ∈ S_{n}. Define the left-to-right minima set of σ as

\overrightarrow{min}(σ) = σ (Del_{S}(σ) ∪ \{1\}) = \{ σ(j) | 1 ≤ j ≤ n, ∀i < j σ(i) > σ(j) \}.

These are the actual (letters) l.t.r.min, including the first letter.

Example 4.3. Let σ = [5, 2, 3, 1, 4]. Then Del_{S}(σ) = \{2, 4\} and \overrightarrow{min}(σ) = \{5, 2, 1\}.

Proposition 4.4. For every σ ∈ S_{n}, \overrightarrow{min}(σ) = Del_{S}(σ^{−1}) ∪ \{1\}.

Proof. Let k ∈ \overrightarrow{min}(σ). Then j = σ^{−1}(k) ∈ Del_{S}(σ) ∪ \{1\}. Therefore, by negation, for all 1 ≤ i ≤ n, if σ(i) < σ(j) = k then i > j = σ^{−1}(k). By the change of variables i′ = σ(i), we get that for all 1 ≤ i′ ≤ n, i′ < k implies σ^{−1}(i′) > σ^{−1}(k), so by definition, k ∈ Del_{S}(σ^{−1}) ∪ \{1\}. This proves that \overrightarrow{min}(σ) ⊆ Del_{S}(σ^{−1}) ∪ \{1\}.

The reverse containment is obtained by substituting σ^{−1} for σ and applying σ to both sides. □

Definition 4.5 (see [RR04, Definition 7.4]). Let π ∈ A_{n+1}. Define Del_{A}(π) as

Del_{A}(π) = { 2 < j ≤ n + 1 | there is at most one i < j such that π(i) < π(j) }.

Definition 4.6. Let π ∈ A_{n+1}. Define the left-to-right almost-minima set of π as

\overrightarrow{amin}(π) = π (Del_{A}(π) ∪ \{1, 2\})

= { π(j) | 1 ≤ j ≤ n + 1 and there is at most one i < j such that π(i) < π(j) }.

Example 4.7. Let π = [4, 2, 6, 3, 1, 5]. Then Del_{A}(π) = \{4, 5\} and \overrightarrow{amin}(π) = \{4, 2, 3, 1\}.

Proposition 4.8. For every π ∈ A_{n+1}, \overrightarrow{amin}(π) = Del_{A}(π^{−1}) ∪ \{1, 2\}.

Proof. Let k ∈ \overrightarrow{amin}(π). Then j = π^{−1}(k) ∈ Del_{A}(π) ∪ \{1, 2\}. Therefore for all 1 ≤ i ≤ n + 1 except at most one, if π(i) < π(j) = k then i > j = π^{−1}(k). By the change of variables i′ = π(i), we get that for all 1 ≤ i′ ≤ n+1 except at most one, i′ < k implies π^{−1}(i′) > π^{−1}(k), so by definition, k ∈ Del_{A}(π^{−1}) ∪ \{1, 2\}. This proves that \overrightarrow{min}(π) ⊆ Del_{A}(π^{−1}) ∪ \{1, 2\}.

The reverse containment is obtained by substituting π^{−1} for π and applying π to both sides. □

We now quote the following theorem. The bijection Ψ of Theorem 5.8 bellow provides a (short) bijective proof of that theorem.

Theorem 4.9 (see [RR04, Theroem 9.1(2)]). For every subsets D_{1} ⊆ {1, …, n − 1} and D_{2} ⊆ {3, …, n + 1},

∑_{{σ∈A_{n+1}|Des_{A}(σ^{−1})⊆D_{1}, Del_{A}(σ^{−1})⊆D_{2}}} q^{rmaj_{A_{n+1}}(σ)} = ∑_{{σ∈A_{n+1}|Des_{A}(σ^{−1})⊆D_{1}, Del_{A}(σ^{−1})⊆D_{2}}} q^{ℓ_{A}(σ)}.

5. The bijection Ψ

Recall the notations for the reverse and the complement of σ = [σ_{1}σ_{2} … σ_{n}] ∈ S_{n}, which are r(σ) = [σ_{n}σ_{n−1} … σ_{1}] and c(σ) = [n + 1 − σ_{1}, n + 1 − σ_{2}, …, n + 1 − σ_{n}], respectively, and the notations Φ and \overleftarrow{Φ} = rΦr for Foata’s second fundamental transformation and the right-to-left Foata transformation (both described in detail in Section 3), respectively.

We shall need the following properties of Φ and \overleftarrow{Φ}, see also Theorem 3.5.

Theorem 5.1. (1) Φ is a bijection of S_{n} onto itself.

(2) For every σ ∈ S_{n}, maj_{S}(σ) = ℓ_{S}(Φ(σ)).

(3) (see [BW91, Example 5.3]) For every σ ∈ S_{n}, \overleftarrow{min}(σ) = \overleftarrow{min}(Φ(σ)), where \overleftarrow{min}(σ) = { σ(j) | 1 ≤ j ≤ n, ∀i > j σ(i) > σ(j) } is the set of right-to-left minima of σ.

(4) (see [FS78, Theorem 1]) For every σ ∈ S_{n}, Des_{S}(σ^{−1}) = Des_{S}([Φ(σ)]^{−1}).

(5) By Theorem 3.9, for every σ ∈ S_{n}, rmaj_{S_{n}}(σ) = ℓ_{S}(\overleftarrow{Φ}(σ)).

The S- and the A-canonical presentations and the map f were discussed in Section 2. A key property of f is the way it relates between certain pairs of statistics on A_{n+1} and on S_{n}.

Definition 5.2 (see [RR04, Definition 5.2]). Let m_{S} be a statistic on the symmetric groups and m_{A} a statistic on the alternating groups. We say that (m_{S}, m_{A}) is an f-pair (of statistics) if for any n and v ∈ A_{n+1}, m_{A}(v) = m_{S}(f(v)).

Proposition 5.3 (see [RR04, Propositions 5.3 and 5.4]). The following pairs are f-pairs: (ℓ_{S}, ℓ_{A}), (rmaj_{S_{n}}, rmaj_{A_{n+1}}), (del_{S}, del_{A}) and (Des_{A}, Des_{S}).

We also have

Proposition 5.4 (see [RR05, Propositions 8.4 and 8.5]). For every v ∈ A_{n+1}, f(v)^{−1} = f(v^{−1}).

The covering map f is obviously not injective. The family of maps g_{u} defined next serve as local inverses of f (see Remark 5.6).

Definition 5.5. For u ∈ A_{n+1} with A-canonical presentation u = u_{1}u_{2} ⋯ u_{n−1}, define g_{u} : R_{j}^{S} → R_{j}^{A} by

g_{u}(s_{j}s_{j−1} ⋯ s_{ℓ}) = a_{j}a_{j−1} ⋯ a_{ℓ} if ℓ ≥ 2, and g_{u}(s_{j}s_{j−1} ⋯ s_{1}) = u_{j}.

Now extend g_{u} : S_{n} → A_{n+1} as follows: let w ∈ S_{n}, w = w_{1} ⋯ w_{n−1} its S-canonical presentation, then

g_{u}(w) := g_{u}(w_{1}) ⋯ g_{u}(w_{n−1}),

which is clearly the A-canonical presentation of g_{u}(w).

Remark 5.6. Let w ∈ S_{n} and u ∈ A_{n+1}. Then f(g_{u}(w)) = w if for all 1 ≤ j ≤ n − 1,

u_{j} = a_{j} ⋯ a_{2}a_{1}^{±1} ⟺ w_{j} = s_{j} ⋯ s_{1},

where w = w_{1} ⋯ w_{n−1} and u = u_{1} ⋯ u_{n−1} are the S- and A-canonical presentations of w and u respectively.

We are now ready to define the bijection Ψ.

Definition 5.7. Define Ψ : A_{n+1} → A_{n+1} by Ψ(v) = g_{v}(\overleftarrow{Φ}(f(v))) .

That is, the image of v under Ψ is obtained by applying \overleftarrow{Φ} to f(v) in S_{n}, then using g_{v} as an “inverse” of f in order to “lift” the result back to A_{n+1}.

The following is our main theorem, which can be seen as an A_{n+1}-analogue of Theorem 5.1.

Theorem 5.8. (1) The mapping Ψ is a bijection of A_{n+1} onto itself.

(2) For every v ∈ A_{n+1}, rmaj_{A_{n+1}}(v) = ℓ_{A}(Ψ(v)).

(3) For every v ∈ A_{n+1}, del_{A}(v) = del_{A}(Ψ(v)).

(4) For every v ∈ A_{n+1}, Del_{A}(v^{−1}) = Del_{A}([Ψ(v)]^{−1}).

(5) For every v ∈ A_{n+1}, Des_{A}(v^{−1}) = Des_{A}([Ψ(v)]^{−1}).

In order to prove the theorem we need the following lemmas.

Lemma 5.9. (1) Let w ∈ S_{n}, w = w_{1} ⋯ w_{n−1} its S-canonical presentation. Then for

every 1 < j ≤ n, j ∈ \overrightarrow{min}(w) if and only if w_{j−1} = s_{j−1}s_{j−2} ⋯ s_{1}.

(2) Let v ∈ A_{n+1}, v = v_{1} ⋯ v_{n−1} its A-canonical presentation. Then for every 2 < j ≤ n + 1, j ∈ \overrightarrow{amin}(v) if and only if v_{j−2} = a_{j−2}a_{j−3} ⋯ a_{1}^{±1}.

Proof. (1) By induction on n. Let σ = w_{1} ⋯ w_{n−2} ∈ S_{n−1} ⊆ S_{n} and assume that the assertion is true for σ. If w_{n−1} = 1, then the claim is correct by the induction hypothesis. Otherwise, w_{n−1} = s_{n−1}s_{n−2} ⋯ s_{ℓ} for some 1 ≤ ℓ ≤ n − 1. Writing σ = [b_{1}, …, b_{n−1}], we have that w = σw_{n−1} = [b_{1}, …, b_{ℓ−1}, n, b_{ℓ}, …, b_{n−1}]. For every 1 < j ≤ n − 1, j = b_{k} for some k, so j is a left-to-right minimum of w if and only if it is a left-to-right minimum of σ, which, by the induction hypothesis, is true if and only if w_{j−1} = s_{j−1} ⋯ s_{1}. Finally, n is an additional left-to-right minimum of w if and only if ℓ = 1, that is if and only if w_{n−1} = s_{n−1}s_{n−2} ⋯ s_{1}.

(2) By induction on n. Let π = v_{1} ⋯ v_{n−2} ∈ A_{n} ⊆ A_{n+1} and assume that the assertion is true for π. If v_{n−1} = 1, then the claim is correct by the induction hypothesis. Otherwise, v_{n−1} = a_{n−1}a_{n−2} ⋯ a_{ℓ}^{ϵ} for some 1 ≤ ℓ ≤ n − 1 and ϵ = ±1. Writing π = [c_{1}, c_{2}, …, c_{n}], we have that

v = πv_{n−1} = \begin{cases}[c_{1}c_{2}, …, c_{ℓ}, n + 1, c_{ℓ+1}, …, c_{n}], & if ℓ > 1 and n − ℓ is even; \\ [c_{2}c_{1}, …, c_{ℓ}, n + 1, c_{ℓ+1}, …, c_{n}], & if ℓ > 1 and n − ℓ is odd; \\ [c_{1}, n + 1, c_{2}, …, c_{n}], & if ℓ = 1, n is odd and ϵ = 1; \\ [c_{2}, n + 1, c_{1}, …, c_{n}], & if ℓ = 1, n is even and ϵ = 1; \\ [n + 1, c_{1}, c_{2}, …, c_{n}], & if ℓ = 1, n is even and ϵ = −1; \\ [n + 1, c_{2}, c_{1}, c_{3}, …, c_{n}], & if ℓ = 1, n is odd and ϵ = −1. \end{cases}

For every 2 < j ≤ n, j = c_{k} for some k, so j is a left-to-right almost-minimum of v if and only if it is a left-to-right almost-minimum of π, which, by the induction hypothesis, is true if and only if v_{j−2} = a_{j−2} ⋯ a_{1}^{±1}. Finally, n + 1 is an additional left-to-right almost-minimum of v if and only if ℓ = 1, that is if and only if v_{n−1} = a_{n−1}a_{n−2} ⋯ a_{1}^{±1}. □

Corollary 5.10. For every v ∈ A_{n+1}, \overrightarrow{amin}(v) = \overrightarrow{min}(f(v)) − 1, where X − 1 = \{x − 1 | x ∈ X}.

Lemma 5.11. For every w ∈ S_{n}, \overrightarrow{min}(w) = \overrightarrow{min}(\overleftarrow{Φ}(w)), hence del_{S}(w) = del_{S}(\overleftarrow{Φ}(w)).

Proof. This follows immediately from the definitions and from Theorem 5.1(3):

j ∈ \overrightarrow{min}(w) ⟺ j ∈ \overleftarrow{min}(r(w))
⟺ j ∈ \overleftarrow{min}(Φ(r(w))
⟺ j ∈ \overrightarrow{min}(r(Φ(r(w))) = \overrightarrow{min}(\overleftarrow{Φ}(w)).

□

The following is an easy corollary of Lemmas 5.9 and 5.11.

Corollary 5.12. Let w ∈ S_{n}, w = w_{1} ⋯ w_{n−1} its S-canonical presentation, and let σ = \overleftarrow{Φ}(w), σ = σ_{1} ⋯ σ_{n−1} its S-canonical presentation. Then σ_{j} = s_{j} ⋯ s_{1} if and only if w_{j} = s_{j} ⋯ s_{1}.

Lemma 5.13. Let v ∈ A_{n+1}. Then f(Ψ(v)) = \overleftarrow{Φ}(f(v)).

Proof. Let v = v_{1} ⋯ v_{n−1} and w = \overleftarrow{Φ}(f(v)) = w_{1} ⋯ w_{n−1} be the A- and S-canonical presentations of v and \overleftarrow{Φ}(f(v)) respectively. By definition of f and Corollary 5.12, for every 1 ≤ j ≤ n − 1, w_{j} = s_{j}s_{j−1} ⋯ s_{1} if and only if v_{j} = a_{j} ⋯ a_{2}a_{1}^{±1}. Therefore, by Remark 5.6,

f(Ψ(v)) = f(g_{v}(\overleftarrow{Φ}(f(v)))) = f(g_{v}(w)) = w = \overleftarrow{Φ}(f(v)).  □

Proof of Theorem 5.8. (1) To prove that Ψ is a bijection, it suffices to find its inverse. Let v ∈ A_{n+1}, and let v = v_{1} ⋯ v_{n−1}, w = \overleftarrow{Φ}(f(v)) = w_{1} ⋯ w_{n−1} and u = Ψ(v) = g_{v}(w) = u_{1} ⋯ u_{n−1} be the A-, S- and A-canonical presentations of v, \overleftarrow{Φ}(f(v)) and Ψ(v) respectively. By Lemma 5.13,

\overleftarrow{Φ}^{−1}(f(Ψ(v))) = \overleftarrow{Φ}^{−1}(\overleftarrow{Φ}(f(v))) = f(v),

so

(∗)  g_{Ψ(v)}(\overleftarrow{Φ}^{−1}(f(Ψ(v)))) = g_{Ψ(v)}(f(v)) = g_{u}(f(v)) = g_{u}(f(v_{1})) ⋯ g_{u}(f(v_{n−1})).

We claim that π ↦ g_{π}(\overleftarrow{Φ}^{−1}(f(π))) is the inverse of Ψ, or in other words, that the right hand side of (∗) equals v_{1}v_{2} ⋯ v_{n−1}. Let 1 ≤ j ≤ n − 1. If v_{j} = a_{j}a_{j−1} ⋯ a_{ℓ}, ℓ > 1, then g_{u}(f(v_{j})) = g_{u}(s_{j}s_{j−1} ⋯ s_{ℓ}) = a_{j}a_{j−1} ⋯ a_{ℓ} = v_{j}. If v_{j} = a_{j} ⋯ a_{2}a_{1}^{±1}, then f(v_{j}) = s_{j}s_{j−1} ⋯ s_{1}, so by Corollary 5.12, w_{j} = s_{j}s_{j−1} ⋯ s_{1}, and therefore u_{j} = g_{v}(w_{j}) = v_{j}, so again g_{u}(f(v_{j})) = v_{j}, and the claim is proved.

(2) By Proposition 5.3 and Lemma 5.13, ℓ_{A}(Ψ(v)) = ℓ_{S}(f(Ψ(v))) = ℓ_{S}(\overleftarrow{Φ}(f(v))). By Theorem 3.9 and Proposition 5.3, ℓ_{S}(\overleftarrow{Φ}(f(v))) = rmaj_{S_{n}}(f(v)) = rmaj_{A_{n+1}}(v). Thus ℓ_{A}(Ψ(v)) = rmaj_{A_{n+1}}(v) as desired.

(3) By Proposition 5.3 and Lemma 5.13, del_{A}(Ψ(v)) = del_{S}(f(Ψ(v))) = del_{S}(\overleftarrow{Φ}(f(v))), and by Lemma 5.11, the definition of del_{S} and Proposition 5.3, del_{S}(\overleftarrow{Φ}(f(v))) = del_{S}(f(v)) = del_{A}(v). Thus del_{A}(Ψ(v)) = del_{A}(v) as desired.

(4) By Corollary 5.10, \overrightarrow{amin}(Ψ(v)) = \overrightarrow{min}(f(Ψ(v))) − 1, with the notation X − 1 = \{ x−1 | x ∈ X \}. Therefore by Lemmas 5.13 and 5.11, \overrightarrow{amin}(Ψ(v)) = \overrightarrow{min}(\overleftarrow{Φ}(f(v)))− 1 = \overrightarrow{min}(f(v)) − 1. Again by Lemma 5.9, we get that \overrightarrow{amin}(Ψ(v)) = \overrightarrow{amin}(v). By Proposition 4.8, this implies that Del_{A}([Ψ(v)]^{−1}) ∪ {1, 2} = Del_{A}(v^{−1}) ∪ {1, 2}, hence Del_{A}([Ψ(v)]^{−1}) = Del_{A}(v^{−1}) as desired.

(5) By Propositions 5.3 and 5.4 and Lemma 5.13,

Des_{A}([Ψ(v)]^{−1}) = Des_{S}(f([Ψ(v)]^{−1})) = Des_{S}([f(Ψ(v))]^{−1}) Des_{S}([\overleftarrow{Φ}(f(v))]^{−1}).

By Remark 3.6, \overleftarrow{Φ}(f(v))^{−1} = (rΦrf(v))^{−1} = c((Φrf(v))^{−1}), so Des_{S}([\overleftarrow{Φ}(f(v))]^{−1}) = {1, …, n − 1} \ Des_{S}([Φrf(v)]^{−1}). By Theorem 5.1,

Des_{S}([Φrf(v)]^{−1}) = Des_{S}([rf(v)]^{−1}).

Hence, Des_{S}([\overleftarrow{Φ}(f(v))]^{−1}) = \{1, …, n − 1\} \ Des_{S}([rf(v)]^{−1}) = Des_{S}(c([rf(v)]^{−1})). Since c([rf(v)]^{−1}) = c(c([f(v)]^{−1})) = f(v)^{−1}, we get that

Des_{S}([\overleftarrow{Φ}(f(v))]^{−1}) = Des_{S}([f(v)]^{−1}).

Finally, by Propositions 5.4 and 5.3, Des_{S}([f(v)]^{−1}) = Des_{S}(f(v^{−1})) = Des_{A}(v^{−1}).

□

6. Example

As an example, let v = [6, 4, 3, 7, 5, 2, 1] ∈ A_{7}. We now calculate v, v^{−1}, Ψ(v) and [Ψ(v)]^{−1}, and using the A-procedure — their A-canonical presentations. This yields the corresponding sets Del_{A} and Des_{A}, hence also the ℓ_{A} and the rmaj_{A_{7}} indices, thus demonstrating Theorem 5.8 in this example. Throughout the example, when writing a canonical presentation, we will underline all factors of the form \underline{a_{j} ⋯ a_{2}a_{1}^{±1}} and \underline{s_{j} ⋯ s_{1}}.

The A-canonical presentations of v and of v^{−1} are

v = \underline{v_{1}}\underline{v_{2}}v_{3}\underline{v_{4}}v_{5} = (\underline{a_{1}})(\underline{a_{2}a_{1}^{−1}})(a_{3}a_{2})(\underline{a_{4}a_{3}a_{2}a_{1}})(a_{5}a_{4}a_{3}) (so del_{A}(v) = 3),

v^{−1} = [7, 6, 3, 2, 5, 1, 4] = (\underline{a_{1}})(a_{3}a_{2})(\underline{a_{4}a_{3}a_{2}a_{1}^{−1}})(\underline{a_{5}a_{4}a_{3}a_{2}a_{1}^{−1}}) (so del_{A}(v^{−1}) = 3). Thus Des_{A}(v) = {1, 3, 4, 5}, so rmaj_{A_{7}}(v) = (6 − 1) + (6 − 3) + (6 − 4) + (6 − 5) = 11. Similarly Des_{A}(v^{−1}) = {1, 2, 4}. Also, Del_{A}(v) = {3, 6, 7} and Del_{A}(v^{−1}) = {3, 4, 6}.

We have

w = f(v) = \underline{w_{1}}\underline{w_{2}}w_{3}\underline{w_{4}}w_{5} = (\underline{s_{1}})(\underline{s_{2}s_{1}})(s_{3}s_{2})(\underline{s_{4}s_{3}s_{2}s_{1}})(s_{5}s_{4}s_{3}) = [5, 3, 6, 4, 2, 1].

Note that Des_{S}(w) = Des_{S}(f(v)) = {1, 3, 4, 5} = Des_{A}(v), and also, rmaj_{S_{6}}(w) = 11 = rmaj_{A_{7}}(v) and del_{S}(w) = 3 = del_{A}(v), in accordance with Proposition 5.3.

Let us calculate Ψ(v) and [Ψ(v)]^{−1}. Using Algorithm 3.8 we obtain \overleftarrow{Φ}(w):

w′_{1} =  | 1
w′_{2} =  | 2 | 1
w′_{3} =  | 4 | 2 | 1
w′_{4} =  | 6 | 4 2 1
w′_{5} = | 3 6 | 2 | 1 | 4
\overleftarrow{Φ}(w) = w′_{6} = 5, 6, 3, 2, 1, 4.

Note that ℓ_{S}(\overleftarrow{Φ}(w)) = 11 = rmaj_{S_{6}}(w), as asserted by Theorem 3.9.

The S-canonical presentation of \overleftarrow{Φ}(w), obtained by the S-procedure (see Example 2.2), is

u = \overleftarrow{Φ}(w) = \underline{u_{1}}\underline{u_{2}}u_{3}\underline{u_{4}}u_{5} = (\underline{s_{1}})(\underline{s_{2}s_{1}})(1)(\underline{s_{4}s_{3}s_{2}s_{1}})(s_{5}s_{4}s_{3}s_{2}).

The underlined factors in the S-canonical presentation of w are the same as the underlined factors in the S-canonical presentation of \overleftarrow{Φ}(w), as asserted by Corollary 5.12. This is a result of the fact that \overrightarrow{min}(w) = \{1, 2, 3, 5\} = \overrightarrow{min}(\overleftarrow{Φ}(w)), which is a result of Lemma 5.11.

Now

Ψ(v) = g_{v}(u) = \underline{v_{1}}\underline{v_{2}}(1)\underline{v_{4}}(a_{5}a_{4}a_{3}a_{2}) =

(\underline{a_{1}})(\underline{a_{2}a_{1}^{−1}})(1)(\underline{a_{4}a_{3}a_{2}a_{1}})(a_{5}a_{4}a_{3}a_{2}) = [4, 6, 7, 3, 2, 1, 5],

so [Ψ(v)]^{−1} = [6, 5, 4, 1, 7, 2, 3] = (1)(\underline{a_{2}a_{1}})(\underline{a_{3}a_{2}a_{1}})(\underline{a_{4}a_{3}a_{2}a_{1}^{−1}})(a_{5}a_{4}). It follows that

Des_{A}(v^{−1}) = {1, 2, 4} = Des_{A}([Ψ(v)]^{−1}) and Del_{A}(v^{−1}) = {3, 4, 6} = Del_{A}([Ψ(v)]^{−1}).

Also

del_{A}(Ψ(v)) = 3 = del_{A}(v)

and

ℓ_{A}(Ψ(v)) = 11 = rmaj_{A_{7}}(v).

7. q-analogues

7.1. The q statistics.

Definition 7.1 (see [RR05, Definition 4.1]). Let π ∈ S_{n}, and let q < n. Define the q-length of π, ℓ_{q}(π), as the number of Coxeter generators in the S-canonical presentation of π, where s_{1}, …, s_{q−1} are not counted. For example, let π = s_{1}s_{2}s_{1}s_{4}s_{3}s_{6}s_{5}s_{4}s_{3}s_{2}, then ℓ_{3}(π) = 6 while ℓ_{4}(π) = 4. Clearly, ℓ_{1} = ℓ_{S}.

Definition 7.2 (see [RR05, Definition 5.1]). Let π ∈ S_{n}. Define Del_{k+1}(π) as

Del_{k+1}(π) = { k + 1 < j ≤ n | #{i < j | π(i) < π(j)} ≤ k }.

Definition 7.3. Let π ∈ S_{n}. Define the left-to-right k-almost-minima set of π as

\overrightarrow{min}_{k+1}(π) = π (Del_{k+1}(π) ∪ \{1, 2, …, k + 1\})

= { π(j) | 1 ≤ j ≤ n, #{i < j | π(i) < π(j)} ≤ k }.

Proposition 7.4. For every π ∈ S_{n+q−1}, \overrightarrow{min}_{k+1}(π) = Del_{k+1}(π^{−1}) ∪ \{1, 2, …, k + 1\}.

Proof. Let r ∈ \overrightarrow{min}_{k+1}(π). Then j = π^{−1}(r) ∈ Del_{k+1}(π) ∪ \{1, …, k + 1\}. Therefore

#{1 ≤ i ≤ n + q − 1 | π(i) < π(j) = r and i < j = π^{−1}(r)} ≤ k.

By the change of variables i′ = π(i), we get

#{1 ≤ i′ ≤ n + q − 1 | i′ < r and π^{−1}(i′) < π^{−1}(r)} ≤ k,

so by definition, r ∈ Del_{k+1}(π^{−1})∪\{1, …, k+1\}. This proves that \overrightarrow{min}_{k+1}(π) ⊆ Del_{k+1}(π^{−1})∪ {1, …, k + 1}.

The reverse containment is obtained by substituting π^{−1} for π and applying π to both sides. □

Definition 7.5 (see [RR05, Definition 5.8]). Let π ∈ S_{n+q−1}. Then i is a q-descent in π if i ≥ q and at least one of the following holds: a) i ∈ Des(π); b) i + 1 ∈ Del_{q}(π).

Definition 7.6 (see [RR05, Definition 5.9]). (1) The q-descent set of π ∈ S_{n+q−1} is de-

fined as

Des_{q}(π) = { i | i is a q-descent in π }.

(2) For π ∈ S_{n+q−1} define the q, m-reverse major index of π by

rmaj_{q,m}(π) = ∑_{i∈Des_{q}(π)}(m − i),

where m = n + q − 1.

We need the notion of dashed patterns [RR05], and we introduce it via examples: σ ∈ S_{n} has the dashed pattern (1 − 2 − 4, 3) if σ = [⋯, a, ⋯, b, ⋯, d, c, ⋯], and it has the dashed pattern (2 − 1 − 4, 3) if σ = [⋯, b, ⋯, a, ⋯, d, c, ⋯] for some a < b < c < d. Given q, denote by Pat(q) the following q! dashed patterns:

Pat(q) = { (π_{1} − π_{2} − ⋯ − π_{q} − (q + 2), (q + 1)) | π ∈ S_{q} }.

For example, Pat(2) = {(1 − 2 − 4, 3), (2 − 1 − 4, 3)}. If σ ∈ S_{m} does not have any of the dashed pattern in Pat(q), then σ avoids Pat(q). We denote by Avoid_{q}(n + q − 1) the set of permutations σ ∈ S_{n+q−1} avoiding all the q! dashed patterns in Pat(q).

The main equidistribution theorems here are the following two theorems. The bijection Ψ_{q} below implies bijective proofs for these theorems.

Theorem 7.7 (see [RR05, Theorem 11.5]). For every positive integers n and q and every subsets B_{1}, B_{2} ⊆ {q, …, n + q − 1},

∑_{{ π∈S_{n+q−1}|Des_{q}(π^{−1})=B_{1}, Del_{q}(π^{−1})=B_{2} }} t^{ℓ_{q}(π)} = ∑_{{ π∈S_{n+q−1}|Des_{q}(π^{−1})=B_{1}, Del_{q}(π^{−1})=B_{2} }} t^{rmaj_{q,n+q−1}(π)}.

Theorem 7.8 (see [RR05, Theorem 11.7]). For every positive integers n and q and every subsets B ⊆ {q, …, n + q − 2},

∑_{{ π^{−1}∈Avoid_{q}(n+q−1)|Des_{q}(π^{−1})=B }} t^{ℓ_{q}(π)} = ∑_{{ π^{−1}∈Avoid_{q}(n+q−1)|Des_{q}(π^{−1})=B }} t^{rmaj_{q,n+q−1}(π)}.

7.2. The covering map f_{q}.

Definition 7.9 (see [RR05, Definition 8.1]). Let w ∈ S_{n+q−1} and let w = s_{i_{1}} ⋯ s_{i_{r}} be its S-canonical presentation. Define f_{q} : S_{n+q−1} → S_{n} as follows:

f_{q}(w) = f_{q}(s_{i_{1}}) ⋯ f_{q}(s_{i_{r}}),

where f_{q}(s_{1}) = ⋯ = f_{q}(s_{q−1}) = 1, and f_{q}(s_{j}) = s_{j−q+1} if j ≥ q.

Remark 7.10. If w = w_{1} ⋯ w_{n+q−2} is the S-canonical presentation of w ∈ S_{n+q−1}, w_{j} ∈ R_{j}^{S}, then f_{q}(w) = f_{q}(w_{q}) ⋯ f_{q}(w_{n+q−2}) is the S-canonical presentation of f_{q}(w), f_{q}(w_{j}) ∈ R_{j−q+1}^{S}.

Proposition 7.11 (see [RR05, Proposition 8.6 and Remark 11.1]). For every π ∈ S_{n+q−1}, Del_{q}(π) − q + 1 = Del_{S}(f_{q}(π)), Des_{q}(π) − q + 1 = Des_{S}(f_{q}(π)), ℓ_{q}(π) = ℓ_{S}(f_{q}(π)), and rmaj_{q,n+q−1}(π) = rmaj_{S_{n}}(f_{q}(π)). Here, X − r = { x − r | x ∈ X }.

Proposition 7.12 (see [RR05, Proposition 8.4]). For any permutation w, f_{q}(w)^{−1} = f_{q}(w^{−1}).

The map f_{q} is obviously not injective for q > 1. The family of maps g_{q,u} defined next serve as local inverses of f_{q} (see Remark 7.14).

Definition 7.13. For u ∈ S_{n+q−1} with S-canonical presentation u = u_{1} ⋯ u_{n+q−2}, define g_{q,u} : R_{j}^{S} → R_{j+q−1}^{S} by

g_{q,u}(s_{j}s_{j−1} ⋯ s_{ℓ}) = s_{j+q−1}s_{j+q−2} ⋯ s_{ℓ+q−1}, g_{u}(s_{j}s_{j−1} ⋯ s_{1}) = u_{j+q−1}.

Now extend g_{q,u} : S_{n} → S_{n+q−1} as follows: let w ∈ S_{n}, w = w_{1} ⋯ w_{n−1} its S-canonical presentation, then

g_{q,u}(w) := u_{1} ⋯ u_{q−1} · g_{q,u}(w_{1}) ⋯ g_{q,u}(w_{n−1}),

which is clearly the S-canonical presentation of g_{q,u}(w).

Remark 7.14. Let w ∈ S_{n} and u ∈ S_{n+q−1}. Then f_{q}(g_{q,u}(w)) = w if for all 1 ≤ j ≤ n − 1,

w_{j} = s_{j} ⋯ s_{1} ⟹ u_{j+q−1} = s_{j+q−1} ⋯ s_{ℓ}, ℓ ≤ q,

where w = w_{1} ⋯ w_{n−1} and u = u_{1} ⋯ u_{n+q−2} are the S-canonical presentations of w and u respectively.

7.3. The map Ψ_{q}.

Definition 7.15. Define Ψ_{q} : S_{n+q−1} → S_{n+q−1} by Ψ_{q}(v) = g_{q,v}(\overleftarrow{Φ}(f_{q}(v))) .

That is, the image of v under Ψ_{q} is obtained by applying \overleftarrow{Φ} to f_{q}(v) in S_{n}, then using g_{q,v} as an “inverse” of f_{q} in order to “lift” the result back to S_{n+q−1}.

Theorem 7.16. (1) The mapping Ψ_{q} is a bijection of S_{n+q−1} onto itself.

(2) For every v ∈ S_{n+q−1}, rmaj_{q,n+q−1}(v) = ℓ_{q}(Ψ_{q}(v)).

(3) For every v ∈ S_{n+q−1}, Del_{q}(v^{−1}) = Del_{q}(Ψ_{q}(v)^{−1}).

(4) For every v ∈ S_{n+q−1}, Des_{q}(v^{−1}) = Des_{q}(Ψ_{q}(v)^{−1}).

The proof is given below.

Lemma 7.17. Let v ∈ S_{n+q−1}, v = v_{1} ⋯ v_{n+q−2} its S-canonical presentation. Then for every q < j ≤ n + q − 1, j ∈ \overrightarrow{min}_{q}(v) if and only if v_{j−1} = s_{j−1}s_{j−2} ⋯ s_{ℓ} for some ℓ ≤ q.

Proof. By induction on n. Let π = v_{1} ⋯ v_{n−1+q−2} ∈ S_{n+q−2} ⊆ S_{n+q−1} and assume that the assertion is true for π. If v_{n+q−2} = 1, then the claim is correct by the induction hypothesis. Otherwise, v_{n+q−2} = s_{n+q−2}s_{n+q−3} ⋯ s_{ℓ} for some 1 ≤ ℓ ≤ n + q − 2. Writing π = [b_{1}, …, b_{n+q−2}], we have that v = πv_{n+q−2} = [b_{1}, …, b_{ℓ−1}, n + q − 1, b_{ℓ}, …, b_{n+q−2}], so clearly for every 1 ≤ k ≤ n + q − 2, the set of numbers smaller than b_{k} and to its left in π is equal to the set of numbers smaller than b_{k} and to its left in v. Thus b_{k} ∈ \overrightarrow{min}_{q}(v) if and only if b_{k} ∈ \overrightarrow{min}_{q}(π), which, by the induction hypothesis, is true if and only if v_{b_{k}−1} = s_{b_{k}−1} ⋯ s_{r} for some r ≤ q. Finally, n + q − 1 ∈ \overrightarrow{min}_{q}(v) if and only if n + q − 1 occupies one of the q leftmost places in v, that is, if and only if ℓ ≤ q. □

Lemma 7.18. Let v ∈ S_{n+q−1}. Then f_{q}(Ψ_{q}(v)) = \overleftarrow{Φ}(f_{q}(v)).

Proof. Let v = v_{1} ⋯ v_{n+q−2} and w = \overleftarrow{Φ}(f_{q}(v)) = w_{1} ⋯ w_{n−1} be the S-canonical presentations of v and \overleftarrow{Φ}(f_{q}(v)) respectively. By definition of f_{q} and Corollary 5.12, for every 1 ≤ j ≤ n − 1, w_{j} = s_{j}s_{j−1} ⋯ s_{1} if and only if v_{j+q−1} = s_{j+q−1} ⋯ s_{ℓ}, ℓ ≤ q. Therefore, by Remark 7.14,

f_{q}(Ψ_{q}(v)) = f_{q}(g_{q,v}(\overleftarrow{Φ}(f_{q}(v)))) = f_{q}(g_{q,v}(w)) = w = \overleftarrow{Φ}(f_{q}(v)).  □

Proof of Theorem 7.16. (1) To prove that Ψ_{q} is a bijection, it suffices to find its inverse. Let v ∈ S_{n+q−1}, and let v = v_{1} ⋯ v_{n+q−2}, w = \overleftarrow{Φ}(f_{q}(v)) = w_{1} ⋯ w_{n−1} and u = Ψ_{q}(v) = g_{q,v}(w) = v_{1} ⋯ v_{q−1}u_{q} ⋯ u_{n+q−2} be the S-canonical presentations of v, \overleftarrow{Φ}(f_{q}(v)) and Ψ_{q}(v) respectively. By Lemma 7.18,

\overleftarrow{Φ}^{−1}(f_{q}(Ψ_{q}(v))) = \overleftarrow{Φ}^{−1}(\overleftarrow{Φ}(f_{q}(v))) = f_{q}(v),

so

(∗) g_{q,Ψ_{q}(v)}(\overleftarrow{Φ}^{−1}(f_{q}(Ψ_{q}(v)))) = g_{q,Ψ_{q}(v)}(f_{q}(v))

= g_{q,u}(f_{q}(v)) = v_{1} ⋯ v_{q−1} · g_{q,u}(f_{q}(v_{1})) ⋯ g_{q,u}(f_{q}(v_{n−1})).

We claim that π ↦ g_{q,π}(\overleftarrow{Φ}^{−1}(f_{q}(π))) is the inverse of Ψ_{q}, or in other words, that the right hand side of (∗) equals v_{1}v_{2} ⋯ v_{n+q−2}. Let q ≤ j ≤ n + q − 2, and write v_{j} = s_{j}s_{j−1} ⋯ s_{ℓ}. If ℓ > q, then g_{q,u}(f_{q}(v_{j})) = g_{q,u}(s_{j−q+1} ⋯ s_{ℓ−q+1}) = s_{j} ⋯ s_{ℓ} = v_{j}. If ℓ ≤ q, then f_{q}(v_{j}) = s_{j} ⋯ s_{1}, so by Corollary 5.12, w_{j} = s_{j} ⋯ s_{1}, and therefore u_{j} = g_{q,v}(w_{j}) = v_{j}, so again g_{q,u}(f_{q}(v_{j})) = v_{j}, and the claim is proved.

(2) By Proposition 7.11 and Lemma 7.18, ℓ_{q}(Ψ_{q}(v)) = ℓ_{S}(f_{q}(Ψ_{q}(v))) = ℓ_{S}(\overleftarrow{Φ}(f_{q}(v))). By Theorem 3.9 and Proposition 7.11, ℓ_{S}(\overleftarrow{Φ}(f_{q}(v))) = rmaj_{S_{n}}(f_{q}(v)) = rmaj_{q,n+q−1}(v). Thus ℓ_{q}(Ψ_{q}(v)) = rmaj_{q,n+q−1}(v) as desired.

(3) By Lemma 7.17 and the definition of f_{q}, \overrightarrow{min}_{q}(Ψ_{q}(v)) = \overrightarrow{min}(f_{q}(Ψ_{q}(v))) − q + 1 (with the notation X − r = { x − r | x ∈ X }). Therefore by Lemmas 7.18 and 5.11, \overrightarrow{min}_{q}(Ψ_{q}(v)) = \overrightarrow{min}(\overleftarrow{Φ}(f_{q}(v))) − q + 1 = \overrightarrow{min}(f_{q}(v)) − q + 1. Again by Lemma 7.17, we get that \overrightarrow{min}_{q}(Ψ_{q}(v)) = \overrightarrow{min}_{q}(v). By Proposition 7.4, this implies that Del_{q}([Ψ_{q}(v)]^{−1}) ∪ {1, …, q} = Del_{q}(v^{−1}) ∪ {1, …, q}, hence Del_{q}([Ψ_{q}(v)]^{−1}) = Del_{q}(v^{−1}) as desired.

(4) By Propositions 7.11 and 7.12 and Lemma 7.18,

Des_{q}([Ψ_{q}(v)]^{−1}) − q + 1 = Des_{S}(f_{q}([Ψ_{q}(v)]^{−1}))
= Des_{S}([f_{q}(Ψ_{q}(v))]^{−1})
= Des_{S}([\overleftarrow{Φ}(f_{q}(v))]^{−1}).

By Remark 3.6, [\overleftarrow{Φ}(f_{q}(v))]^{−1} = [rΦrf_{q}(v)]^{−1} = c([Φrf_{q}(v)]^{−1}), so

Des_{S}([\overleftarrow{Φ}(f_{q}(v))]^{−1}) = \{1, …, n − 1\} \ Des_{S}([Φrf_{q}(v)]^{−1}).

By Theorem 5.1,

Des_{S}([Φrf_{q}(v)]^{−1}) = Des_{S}([rf_{q}(v)]^{−1}).

Hence, Des_{S}([\overleftarrow{Φ}(f_{q}(v))]^{−1}) = \{1, …, n − 1\} \ Des_{S}([rf_{q}(v)]^{−1}) = Des_{S}(c([rf_{q}(v)]^{−1})). Since c([rf_{q}(v)]^{−1}) = c(c([f_{q}(v)]^{−1})) = [f_{q}(v)]^{−1}, we get that

Des_{S}([\overleftarrow{Φ}(f_{q}(v))]^{−1}) = Des_{S}([f_{q}(v)]^{−1}).

Finally, by Propositions 7.12 and 7.11,

Des_{S}([f_{q}(v)]^{−1}) = Des_{S}(f_{q}(v^{−1})) = Des_{q}(v^{−1}) − q + 1.
□

16 DAN BERNSTEIN AND AMITAI REGEV

References

[BW91] A. Björner and Michelle L. Wachs, Permutation statistics and linear extensions of posets. J. Combin. Theory Ser. A, 58(1):85–114, 1991.

[Car54] L. Carlitz, q-Bernoulli and Eulerian numbers, Trans. Amer. Math Soc., 76 (1954) 332-350.

[Car75] L. Carlitz, A combinatorial property of q-Eulerian numbers, Amer. Math. Monthly 82 (1975) 51-54.

[Foa68] D. Foata, On the Netto inversion number of a sequence. Proc. Amer. Math. Soc., 19:236–240, 1968.

[FS78] D. Foata and M. P. Schützenberger, Major index and inversion number of permutations. Math. Nachr. 83 (1978) 143-159.

[GG79] A. Garsia and I. Gessel, Permutation statistics and partitions, Adv. Math. 31 (1979) 288-305.

[Gol93] David M. Goldschmidt, Group characters, symmetric functions, and the Hecke algebra, volume 4 of University Lecture Series. American Mathematical Society, Providence, RI, 1993.

[Kra95] C. Krattenthaler, The major counting of non intersecting lattice paths and generating functions for tableaux, Mem. Amer. Math.Soc. 115 (1995), no. 552 .

[Lot83] M. Lothaire, Combinatorics on words, volume 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley Publishing Co., Reading, Mass., 1983.

[MM16] P.A. MacMahon, Combinatory Analysis I-II, Cambridge Univ. Press. London/New York, 1916. Reprinted by Chelsea, New York, 1960.

[Mit01] Hideo Mitsuhashi, The q-analogue of the alternating group and its representations. J. Algebra, 240(2):535–558, 2001.

[RR04] A. Regev and Y. Roichman, Permutation statistics on the alternating group. Adv. in Appl. Math., 33(4):676–709, 2004.

[RR05] A. Regev and Y. Roichman, Generalized statistics on S_{n} and pattern avoidance. European J. Combin., 26(1):29–57, 2005.

[Sta02] R. P. Stanley, Some remarks on sign-balanced and maj-balanced posets, preprint,

       arXiv:math.CO/0211113, 2002.

Department of Mathematics, The Weizmann Institute of Science, Rehovot 76100, Israel

  E-mail address: dan.bernstein@weizmann.ac.il

Department of Mathematics, The Weizmann Institute of Science, Rehovot 76100, Israel

  E-mail address: am.regev@weizmann.ac.il