March 5, 2005

<ph f="cmbx">A Foata bijection for the alternating group and for </ph> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>q</mi> </math> <ph f="cmmi"> </ph><ph f="cmbx">analogues</ph>

Dan Bernstein

Amitai Regev

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

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] , analogue 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] , analogue 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 the analogue 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 [RR03] — 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 [RR03] , 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   ) analogue 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 [RR03] , 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 A   -length , ℓ 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 [RR03] .
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 = 1267834   and x = 5   , r   decomposes into r 1 = 1   , r 2 = 2   , r 3 = 6783   and r 4 = 4   , so γ 5 ( 1267834 ) = 1236784 .  
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 Φ ( r x ) = γ x ( Φ ( r ) ) x   .
For example,
Φ ( 653142 ) = γ 2 ( γ 4 ( γ 1 ( γ 3 ( γ 5 ( 6 ) 5 ) 3 ) 1 ) 4 ) 2 = γ 2 ( γ 4 ( γ 1 ( γ 3 ( 65 ) 3 ) 1 ) 4 ) 2 = γ 2 ( γ 4 ( γ 1 ( 653 ) 1 ) 4 ) 2 = γ 2 ( γ 4 ( 6531 ) 4 ) 2 = γ 2 ( 36514 ) 2 = 365412 .
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 = 653142   , using the algorithm:
r 1 ′ = 6 |
r 2 ′ = 6 | 5 |
r 3 ′ = 6 | 5 | 3 |
r 4 ′ = 653 | 1 |
r 5 ′ = 3 | 6 | 5 | 14 |
Φ ( r ) = r 6 ′ = 365412 .
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 r c = c r   .
Moreover, ( r ( σ ) ) − 1 = c ( σ − 1 )   .
Definition 3.7. Let Φ ← : = r Φ r   , the right-to-left Foata transformation.
While Φ ← ( 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 ( Φ ←   ). 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 Φ ← ( w )   in Section 6 .
The key property of Φ ←   used in this paper is the following.
Theorem 3.9. For every σ ∈ S n   , rmaj S n ( σ ) = ℓ S ( Φ ← ( σ ) )   .
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 Z 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 ] ∈ Z 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 a ¯ = k + 1 − a   , we have
    Φ c k ( σ ) = γ σ n ¯ ( Φ ( σ 1 ¯ σ 2 ¯ . . . σ n − 1 ¯ ) ) σ n ¯ = γ σ n ¯ ( b 1 ¯ b 2 ¯ . . . b n − 1 ¯ ) σ n ¯
    by the induction hypothesis, and c k Φ ( σ ) = c k ( c 1 . . . c n − 1 σ n ) = c 1 ¯ . . . c n − 1 ¯ σ n ¯ ,   so it remains to show that γ σ n ¯ ( b 1 ¯ b 2 ¯ . . . b n − 1 ¯ ) = c 1 ¯ . . . 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 b n − 1 ¯ > σ n ¯   and M = { 1 ≤ m ≤ n − 1 | σ m ¯ > 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   and 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 ¯ ,   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 γ σ 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 ¯ .
    Thus γ σ n ¯ ( b 1 ¯ b 2 ¯ . . . b n − 1 ¯ ) = c 1 ¯ . . . c n − 1 ¯   as desired. □
Lemma 3.11. For every w ∈ S n   , ℓ S ( r c ( 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 , r c ( w ) ( n + 1 − i ) < r c ( w ) ( n + 1 − j ) } = # { ( n + 1 − s , n + 1 − r ) | 1 ≤ r < s ≤ n , r c ( w ) ( s ) < r c ( w ) ( r ) } = # { ( r , s ) | 1 ≤ r < s ≤ n , r c ( w ) ( r ) > r c ( w ) ( s ) } = ℓ S ( r c ( w ) ) Λ
    □
Lemma 3.12. For every w ∈ S n   , maj S ( r c ( w ) ) = rmaj S n ( w )   .
  • Proof. By the definitions of r   , c   and Des S   ,
    i ∈ Des S ( r c ( w ) ) ⟺ r c ( w ) ( i ) > r c ( 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 ( r c ( w ) ) = ∑ i ∈ Des S ( r c ( w ) ) i = ∑ i ∈ Des S ( w ) n − i = rmaj S n ( w ) . Λ   □
  • Proof of Theorem 3.9 .
    rmaj S n ( σ ) = maj S ( r c ( σ ) ) (by Lemma 3.12 )
    = ℓ S ( Φ r c ( σ ) ) (by Theorem 3.5 )
    = ℓ S ( r c Φ r c ( σ ) ) (by Lemma 3.11 )
    = ℓ S ( Φ ← ( σ ) ) (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 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 min → ( σ ) = { 5 , 2 , 1 }   .
Proposition 4.4. For every σ ∈ S n   , min → ( σ ) = Del S ( σ − 1 ) ∪ { 1 }   .
  • Proof. Let k ∈ 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 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
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 amin → ( π ) = { 4 , 2 , 3 , 1 }   .
Proposition 4.8. For every π ∈ A n + 1   , amin → ( π ) = Del A ( π − 1 ) ∪ { 1 , 2 }   .
  • Proof. Let k ∈ 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 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 ⊆ { 1 , . . . , 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 Φ ← = 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 Φ ←   , 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   , min ← ( σ ) = min ← ( Φ ( σ ) )   , where 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 ( Φ ← ( σ ) )   .
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 [RR03,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.3and 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 [RR03,Propositions 8.4and 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 ( Φ ← ( f ( v ) ) )   .
That is, the image of v   under Ψ   is obtained by applying Φ ←   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 ∈ 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 ∈ 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 = { [ 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 .   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   , amin → ( v ) = min → ( f ( v ) ) − 1   , where X − 1 = { x − 1 | x ∈ X }   .
Lemma 5.11. For every w ∈ S n   , min → ( w ) = min → ( Φ ← ( w ) )   , hence del S ( w ) = del S ( Φ ← ( w ) )   .
  • Proof. This follows immediately from the definitions and from Theorem 5.1 (3):
    j ∈ min → ( w ) ⟺ j ∈ min ← ( r ( w ) ) ⟺ j ∈ min ← ( Φ ( r ( w ) ) ⟺ j ∈ min → ( r ( Φ ( r ( w ) ) ) = min → ( Φ ← ( 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 σ = Φ ← ( 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 ) ) = Φ ← ( f ( v ) )   .
  • Proof. Let v = v 1 ⋯ v n − 1   and w = Φ ← ( f ( v ) ) = w 1 ⋯ w n − 1   be the A   and S   -canonical presentations of v   and Φ ← ( 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 ( Φ ← ( f ( v ) ) ) ) = f ( g v ( w ) ) = w = Φ ← ( 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 = Φ ← ( 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   , Φ ← ( f ( v ) )   and Ψ ( v )   respectively. By Lemma 5.13 , Φ ← − 1 ( f ( Ψ ( v ) ) ) = Φ ← − 1 ( Φ ← ( f ( v ) ) ) = f ( v ) ,   so
      g Ψ ( v ) ( Φ ← − 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 π ( Φ ← − 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 ( Φ ← ( f ( v ) ) )   . By Theorem 3.9 and Proposition 5.3 , ℓ S ( Φ ← ( 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 ( Φ ← ( f ( v ) ) )   , and by Lemma 5.11 , the definition of del S   and Proposition 5.3 , del S ( Φ ← ( f ( v ) ) ) = del S ( f ( v ) ) = del A ( v )   . Thus del A ( Ψ ( v ) ) = del A ( v )   as desired.
    • (4) By Corollary 5.10 , amin → ( Ψ ( v ) ) = min → ( f ( Ψ ( v ) ) ) − 1   , with the notation X − 1 = { x − 1 | x ∈ X }   . Therefore by Lemmas 5.13 and 5.11 , amin → ( Ψ ( v ) ) = min → ( Φ ← ( f ( v ) ) ) − 1 = min → ( f ( v ) ) − 1   . Again by Lemma 5.9 , we get that amin → ( Ψ ( v ) ) = 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 ( [ Φ ← ( f ( v ) ) ] − 1 ) .   By Remark 3.6 , Φ ← ( f ( v ) ) − 1 = ( r Φ r f ( v ) ) − 1 = c ( ( Φ r f ( v ) ) − 1 )   , so Des S ( [ Φ ← ( f ( v ) ) ] − 1 ) = { 1 , . . . , n − 1 } \ Des S ( [ Φ r f ( v ) ] − 1 )   . By Theorem 5.1 , Des S ( [ Φ r f ( v ) ] − 1 ) = Des S ( [ r f ( v ) ] − 1 ) .   Hence, Des S ( [ Φ ← ( f ( v ) ) ] − 1 ) = { 1 , . . . , n − 1 } \ Des S ( [ r f ( v ) ] − 1 ) = Des S ( c ( [ r f ( v ) ] − 1 ) )   .
      Since c ( [ r f ( v ) ] − 1 ) = c ( c ( [ f ( v ) ] − 1 ) ) = f ( v ) − 1   , we get that Des S ( [ Φ ← ( 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 r m a j 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 a j ⋯ a 2 a 1 ± 1 ̲   and s j ⋯ s 1 ̲   .
The A   -canonical presentations of v   and of v − 1   are v = v 1 ̲ v 2 ̲ v 3 v 4 ̲ v 5 = ( 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 ) (so del A ( v ) = 3 ) ,   v − 1 = [ 7 , 6 , 3 , 2 , 5 , 1 , 4 ] = ( a 1 ̲ ) ( a 3 a 2 ) ( a 4 a 3 a 2 a 1 − 1 ̲ ) ( 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 ) = w 1 ̲ w 2 ̲ w 3 w 4 ̲ w 5 = ( s 1 ̲ ) ( s 2 s 1 ̲ ) ( s 3 s 2 ) ( 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 Φ ← ( w )   :
w 1 ′ = | 1
w 2 ′ = | 2 | 1
w 3 ′ = | 4 | 2 | 1
w 4 ′ = | 6 | 421
w 5 ′ = | 36 | 2 | 1 | 4
Φ ← ( w ) = w 6 ′ = 5 , 6 , 3 , 2 , 1 , 4 .
Note that ℓ S ( Φ ← ( w ) ) = 11 = rmaj S 6 ( w )   , as asserted by Theorem 3.9 .
The S   -canonical presentation of Φ ← ( w )   , obtained by the S   -procedure (see Example 2.2 ), is u = Φ ← ( w ) = u 1 ̲ u 2 ̲ u 3 u 4 ̲ u 5 = ( s 1 ̲ ) ( s 2 s 1 ̲ ) ( 1 ) ( 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 Φ ← ( w )   , as asserted by Corollary 5.12 . This is a result of the fact that min → ( w ) = { 1 , 2 , 3 , 5 } = min → ( Φ ← ( w ) )   , which is a result of Lemma 5.11 .
Now
Ψ ( v ) = g v ( u ) = v 1 ̲ v 2 ̲ ( 1 ) v 4 ̲ ( a 5 a 4 a 3 a 2 ) = ( a 1 ̲ ) ( a 2 a 1 − 1 ̲ ) ( 1 ) ( 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 ) ( a 2 a 1 ̲ ) ( a 3 a 2 a 1 ̲ ) ( 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 [RR03,Definition 5.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 [RR03,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
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   , min → k + 1 ( π ) = Del k + 1 ( π − 1 ) ∪ { 1 , 2 , . . . , k + 1 }   .
  • Proof. Let r ∈ 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 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 [RR03,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 [RR03,Definition 5.9] ).
  • (1) The q   -descent set of π ∈ S n + q − 1   is defined 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 [RR03] , 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 [RR03,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 [RR03,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 [RR03,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 [RR03,Proposition 8.6andRemark 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 [RR03,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 ( Φ ← ( f q ( v ) ) )   .
That is, the image of v   under Ψ q   is obtained by applying Φ ←   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 ∈ 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 ∈ min → q ( v )   if and only if b k ∈ 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 ∈ 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 ) ) = Φ ← ( f q ( v ) )   .
  • Proof. Let v = v 1 ⋯ v n + q − 2   and w = Φ ← ( f q ( v ) ) = w 1 ⋯ w n − 1   be the S   -canonical presentations of v   and Φ ← ( 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 ( Φ ← ( f q ( v ) ) ) ) = f q ( g q , v ( w ) ) = w = Φ ← ( 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 = Φ ← ( 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   , Φ ← ( f q ( v ) )   and Ψ q ( v )   respectively. By Lemma 7.18 , Φ ← − 1 ( f q ( Ψ q ( v ) ) ) = Φ ← − 1 ( Φ ← ( f q ( v ) ) ) = f q ( v ) ,   so
      (*) g q , Ψ q ( v ) ( Φ ← − 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 , π ( Φ ← − 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 ( Φ ← ( f q ( v ) ) )   .
      By Theorem 3.9 and Proposition 7.11 , ℓ S ( Φ ← ( 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   , min → q ( Ψ q ( v ) ) = min → ( f q ( Ψ q ( v ) ) ) − q + 1   (with the notation X − r = { x − r | x ∈ X }   ). Therefore by Lemmas 7.18 and 5.11 , min → q ( Ψ q ( v ) ) = min → ( Φ ← ( f q ( v ) ) ) − q + 1 = min → ( f q ( v ) ) − q + 1   . Again by Lemma 7.17 , we get that min → q ( Ψ q ( v ) ) = 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 ( [ Φ ← ( f q ( v ) ) ] − 1 ) .
      By Remark 3.6 , [ Φ ← ( f q ( v ) ) ] − 1 = [ r Φ r f q ( v ) ] − 1 = c ( [ Φ r f q ( v ) ] − 1 )   , so Des S ( [ Φ ← ( f q ( v ) ) ] − 1 ) = { 1 , . . . , n − 1 } \ Des S ( [ Φ r f q ( v ) ] − 1 )   . By Theorem 5.1 , Des S ( [ Φ r f q ( v ) ] − 1 ) = Des S ( [ r f q ( v ) ] − 1 ) .   Hence, Des S ( [ Φ ← ( f q ( v ) ) ] − 1 ) = { 1 , . . . , n − 1 } \ Des S ( [ r f q ( v ) ] − 1 ) = Des S ( c ( [ r f q ( v ) ] − 1 ) )   .
      Since c ( [ r f q ( v ) ] − 1 ) = c ( c ( [ f q ( v ) ] − 1 ) ) = [ f q ( v ) ] − 1   , we get that Des S ( [ Φ ← ( 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   . □
    □
References

  1. A. Björner and Michelle L. Wachs, Permutation statistics and linear extensions of posets. J. Combin. Theory Ser. A, 58(1):85–114, 1991.
  2. L. Carlitz, q   -Bernoulli and Eulerian numbers, Trans. Amer. Math Soc., 76 (1954) 332-350.
  3. L. Carlitz, A combinatorial property of q   -Eulerian numbers, Amer. Math. Monthly 82 (1975) 51-54.
  4. D. Foata, On the Netto inversion number of a sequence. Proc. Amer. Math. Soc., 19:236–240, 1968.
  5. D. Foata and G. N. Han, Further properties of the second fundamental transformation on words. http://www-irma.u-strasbg.fr/ foata/paper/pub92.html , 2004.
  6. D. Foata and M. P. Schutzenberger, Major index and inversion number of permutations. Math. Nachr. 83 (1978) 143-159.
  7. A. Garsia and I. Gessel, Permutation statistics and partitions, Adv. Math. 31 (1979) 288-305.
  8. David M. Goldschmidt, Group characters, symmetric functions, and the Hecke algebra, volume 4 of University Lecture Series. American Mathematical Society, Providence, RI, 1993.
  9. C. Krattenthaler, The major counting of non intersecting lattice paths and generating functions for tableaux, Mem. Amer. Math.Soc. 115 (1995), no. 552 .
  10. M. Lothaire, Combinatorics on words, volume 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley Publishing Co., Reading, Mass., 1983.
  11. P.A. MacMahon, Combinatory Analysis I-II, Cambridge Univ. Press. London/New-York, 1916. Reprinted by Chelsea, New-York, 1960.
  12. Hideo Mitsuhashi, The q   -analogue of the alternating group and its representations. J. Algebra, 240(2):535–558, 2001.
  13. A. Regev and Y. Roichman, q   statistics on S n   and pattern avoidance. arXiv: math.CO/0305393 , 2003.
  14. A. Regev and Y. Roichman, Permutation statistics on the alternating group. Adv. in Appl. Math., 33(4):676–709, 2004.
  15. 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