text:
# Permutation Statistics on the Alternating Group

## 1 Introduction

### 1.1 General outline

One of the most active branches in enumerative combinatorics is the study of permutation statistics. Let $`S_n`$ be the symmetric group on $`1,\mathrm{},n`$. One is interested in the refined count of permutations according to (non-negative, integer valued) combinatorial parameters. For example, the number of inversions in a permutation - namely its length \- is such a parameter. Another parameter is MacMahon’s major index, which is defined via the descent set of a permutation - see below.

Two parameters that have the same generating function are said to be equi-distributed. Indeed, MacMahon  proved the remarkable fact that the inversions and the major-index statistics are equi-distributed on $`S_n`$. MacMahon’s classical theorem  has received far reaching refinements and generalizations, including: multivariate refinements which imply equi-distribution on certain subsets of permutations (done by Carlitz , Foata-Schützenberger  and Garsia-Gessel ); analogues for other combinatorial objects, cf. ; generalizations to other classical Weyl groups, cf. .

Let $`A_nS_n`$ denote the alternating group on $`1,\mathrm{},n`$. Easy examples show that the above statistics fail to be equi-distributed when restricted to $`A_n`$. Our main goal is to find statistics on $`A_n`$ which are natural generalizations of the $`S_n`$ statistics and are equi-distributed on $`A_n`$, yielding analogous identities for their generating functions. This goal is achieved by proving further refinements of the above $`S_n`$-identities.

It is well known that the above statistics on $`S_n`$ may be defined via the Coxeter generators $`\{(i,i+1)1in1\}`$ of $`S_n`$. Mitsuhashi  pointed out at a certain set of generators of the alternating group $`A_n`$, which play a role similar to that of the above Coxeter generators of $`S_n`$, see Subsection 1.3 below. We use these generators to define the analogous length and descent statistics on the alternating group.

The $`S_n`$-Coxeter generators allow one to introduce the classical canonical presentation of the elements of $`S_n`$, see Subsection 3.1. Similarly, the above Mitsuhashi’s ‘Coxeter’ generators allow us to introduce the corresponding canonical presentation of the elements of $`A_{n+1}`$, see Subsection 3.3. We remark that usually, $`S_n`$ is viewed as a double cover of $`A_n`$. However, the above canonical presentations enable us to introduce a covering map $`f`$ from the alternating group $`A_{n+1}`$ onto $`S_n`$, and thus $`A_{n+1}`$ can be viewed as a covering of $`S_n`$.

A new statistic, the delent number, plays a crucial role in the paper, and allows us to ‘lift’ $`S_n`$ identities to $`A_{n+1}`$. The delent number on $`S_n`$ may be defined as follows: if the transposition $`(1,2)`$ appears $`r`$ times in the canonical presentation of $`\sigma S_n`$ then the delent number of $`\sigma `$, $`del_S(\sigma )`$, is $`r`$. An analogous statistic is defined for $`A_{n+1}`$, see Definition 4.3. We give direct combinatorial characterizations of this statistic (see Propositions 1.7 and 1.8 below) and show that this statistic is involved in new $`S_n`$ equi-distribution identities, refining some of the results of Foata-Schützenberger  and of Garsia-Gessel . Identities involving the delent number are then ‘lifted’ by the covering map $`f`$, yielding $`A_{n+1}`$ equi-distribution identities, see Theorem 6.1, Theorem 9.1 and Corollary 9.2.

In the Appendix we present different statistics on $`A_n`$, and a consequent different analogue of MacMahon’s equi-distribution theorem. These statistics are compatible with the usual point of view of $`S_n`$ as a double cover of $`A_n`$.

The above setting and results are connected with enumeration of other combinatorial objects, such as permutations avoiding patterns, leading to $`q`$-analogues of the classical $`S_n`$ statistics and of the Bell and Stirling numbers. A detailed study of these $`q`$-analogues is given in  (a few of these results appear in Subsection 5.3).

The paper is organized as follows : The rest of this section surveys briefly the classical background and lists our main results. Background and notations are given in detail in Section 2, while the $`A`$ canonical presentation is analyzed in Section 3. In Section 4 we study the length statistics, and in Section 5 we discuss the relations between various $`S`$\- and $`A`$-statistics, relations given by the map $`f:A_{n+1}S_n`$. In Section 6 we study the ordinary and the reverse major indices, together with the delent statistics. Additional properties of the delent numbers are given in Section 7. In Section 8 we prove some lemmas on shuffles - lemmas that are needed for the proof of the main theorem. The main theorem (Theorem 9.1) and its proof are given in Section 9. Finally, the Appendix constitutes Section 10.

### 1.2 Classical $`S_n`$-Statistics

Recall that the Coxeter generators $`S:=\{(i,i+1)|1in1\}`$ of $`S_n`$ give rise to various combinatorial statistics, like the length statistic, etc. As we show later, most of these $`S_n`$ statistics have $`A_n`$ analogues, therefore we add “S-” and “A-” to the titles of the corresponding statistics.
The S-length: For $`\pi S_n`$ let $`\mathrm{}_S(\pi )`$ be the standard length of $`\pi `$ with respect to these Coxeter generators.
The S-descent: Given a permutation $`\pi `$ in the symmetric group $`S_n`$, the $`S`$-descent set of $`\pi `$ is defined by

$$\mathrm{𝐷𝑒𝑠}_S(\pi ):=\{i|\mathrm{}_S(\pi )>\mathrm{}_S(\pi s_i)\}=\{i\pi (i)>\pi (i+1)\}.$$

The descent number of $`\pi `$, $`\mathrm{𝑑𝑒𝑠}_S(\pi )`$, is defined by $`\mathrm{𝑑𝑒𝑠}_S(\pi ):=|\mathrm{𝐷𝑒𝑠}_S(\pi )|.`$

The major index, $`\mathrm{𝑚𝑎𝑗}_S(\pi )`$ is

$$\mathrm{𝑚𝑎𝑗}_S(\pi ):=\underset{i\mathrm{𝐷𝑒𝑠}_S(\pi )}{}i.$$

The corresponding reverse major index does depend on $`n`$, and is denoted

$$\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi ):=\underset{i\mathrm{𝐷𝑒𝑠}_S(\pi )}{}(ni).$$

The reverse major index $`rmaj_{S_n}(\pi )`$ is implicit in .

These statistics are involved in many combinatorial identities. First, MacMahon proved the following equi-distribution of the length and the major indices :

$$\underset{\sigma S_n}{}q^{\mathrm{}_S(\sigma )}=\underset{\sigma S_n}{}q^{maj_S(\sigma )}.$$

Foata  gave a bijective proof of MacMahon’s theorem, then Foata and Schützenberger  applied this bijection to refine MacMahon’s identity by analyzing bivariate distributions. Garsia and Gessel  extended the analysis to multivariate distributions. Extensions of MacMahon’s identity to hyperoctahedral groups appear in .

Combining Theorems 1 and 2 of  one deduces the identity

###### Theorem 1.1

For any subset $`D_1\{1,\mathrm{},n1\}`$

$$\underset{\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)D_1\}}{}q^{\mathrm{𝑚𝑎𝑗}_{S_n}(\pi )}=\underset{\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)D_1\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi )}$$

$$=\underset{\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)D_1\}}{}q^{\mathrm{}_S(\pi )}.$$

A bivariate equi-distribution follows.

###### Corollary 1.2

$$\underset{\pi S_n}{}q_1^{\mathrm{𝑚𝑎𝑗}_{S_n}(\pi )}q_2^{\mathrm{𝑑𝑒𝑠}_S(\pi ^1)}=\underset{\pi S_n}{}q_1^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi )}q_2^{\mathrm{𝑑𝑒𝑠}_S(\pi ^1)}=\underset{\pi S_n}{}q_1^{\mathrm{}_S(\pi )}q_2^{\mathrm{𝑑𝑒𝑠}_S(\pi ^1)}.$$

As already mentioned, one of the main goals in this paper is to find analogous statistics and identities for the alternating group $`A_n`$. In the process we first prove some further refinements of some of the above identities for $`S_n`$, refinements involving the new delent statistic, see Theorems 6.1.1 and 9.1.1.

### 1.3 Main Results

Here is a summary of the main results of this paper.

#### 1.3.1 $`A_n`$-Statistics

Following Mitsuhashi  we let

$$a_i:=s_1s_{i+1}=(1,2)(i+1,i+2)(1in1).$$

Thus $`a_i=a_i^1`$ if $`i1`$, while $`a_1^2=a_1^1`$. The set $`A:=\{a_i|1in1\}`$ generates the alternating group on $`n+1`$ letters $`A_{n+1}`$ (see e.g. ). It is the above exceptional property of $`a_1`$ among the elements of $`A`$ \- which naturally leads to the ‘delent’ statistic (Definition 1.5 below), both for $`S_n`$ and for $`A_{n+1}`$. This new statistic enables us to deduce new refinements of the MacMahon-type identities for $`S_n`$, and for each such an identity to derive the analogous identity for $`A_{n+1}`$.

The canonical presentation in $`S_n`$ by the Coxeter generators is well known, and is discussed in Section 3, see Theorem 3.1. With the above generating set $`A`$ of $`A_{n+1}`$ we also have canonical presentations for the elements of $`A_{n+1}`$, as follows. For each $`1jn1`$ define

$`R_j^A=\{1,a_j,a_ja_{j1},\mathrm{},a_j\mathrm{}a_2,a_j\mathrm{}a_2a_1,a_j\mathrm{}a_2a_1^1\}.`$ (1)
###### Theorem 1.3

(See Theorem 3.4) Let $`vA_{n+1}`$, then there exist unique elements $`v_jR_j^A`$, $`1jn1`$, such that $`v=v_1\mathrm{}v_{n1}`$, and this presentation is unique. Call that presentation $`v=v_1\mathrm{}v_{n1}`$ the $`A`$ canonical presentation of $`v`$.

The $`A`$ canonical presentation allow us to introduce the A-length of an element in $`A_{n+1}`$:

###### Definition 1.4

Let $`vA_{n+1}`$ with $`v=a_{i_1}^{ϵ_1}\mathrm{}a_{i_r}^{ϵ_r}`$ ($`ϵ_i=\pm 1`$) its $`A`$ canonical presentation, then its A-length is $`\mathrm{}_A(v)=r`$.

A combinatorial interpretation of the $`A`$-length in terms of inversions is given below, see Proposition 4.5.

The $`A`$-descent statistic is defined using the above generating set $`A`$ :

###### Definition 1.5

1. The alternating-descent (i.e. the $`A`$-descent) set of $`\sigma A_{n+1}`$ is defined by:

$$\mathrm{𝐷𝑒𝑠}_A(\sigma ):=\{1in1\mathrm{}_A(\sigma )\mathrm{}_A(\sigma a_i)\},$$

and the A-descent number of $`\sigma A_{n+1}`$ is defined by

$$\mathrm{𝑑𝑒𝑠}_A(\sigma ):=|\mathrm{𝐷𝑒𝑠}_A(\sigma )|.$$

(note that the strict relation $`>`$, in the definition of an $`S`$-descent in Section 1.2, is replaced in the $`A`$-analogue by $``$).
2. Define the alternating reverse major index of $`\sigma A_{n+1}`$ as

$$\mathrm{𝑟𝑚𝑎𝑗}_{A_{n+1}}(\sigma ):=\underset{i\mathrm{𝐷𝑒𝑠}_A(\sigma )}{}(ni).$$

#### 1.3.2 The Delent Number

New statistics, for the alternating group, as well as for the symmetric group, are introduced.

###### Definition 1.6

(See Definition 4.3)

1. Let $`wS_n`$. The $`S`$-delent number of $`w`$ is the number of times that $`s_1=(1,2)`$ occurs in the $`S`$ canonical presentation of $`w`$, and is denoted by $`del_S(w)`$.
2. Let $`vA_{n+1}`$. The $`A`$-delent number of $`v`$ is the number of times that $`a_1^{\pm 1}`$ occur in the $`A`$ canonical presentation of $`v`$, and is denoted by $`del_A(v)`$.

A combinatorial interpretation of the delent numbers, $`del_S`$ and $`del_A`$, is given in Section 7. Let $`wS_n`$, then $`j`$ is a l.t.r.min (left-to-right minimum) of $`w`$ if $`w(i)>w(j)`$ for all $`1i<j`$.

###### Proposition 1.7

(see Proposition 7.7) For every permutation $`wS_n`$ denote

$$Del_S(w)=\{1<in|i\mathrm{is}\mathrm{a}\mathrm{l}.\mathrm{t}.\mathrm{r}.\mathrm{min}\},$$

then

$$del_S(w)=|Del_S(w)|.$$

Similar to l.t.r.min, we define an almost left to right minimum (a.l.t.r.min) of $`wA_{n+1}`$ as follows:

$`j`$ is an a.l.t.r.min of $`w`$ if $`w(i)<w(j)`$ for at most one $`j`$ less than $`i`$. Define $`Del_A(w)`$ as the set of the almost left-to-right minima of $`w`$. Then $`del_A(v)=Del_A(w)`$, i.e. is the number of a.l.t.r.min of $`w`$, see Proposition 7.7.

We also have

###### Proposition 1.8

(See Proposition 4.4) Let $`wA_{n+1}`$, then

$$del_S(w)=\mathrm{}_S(w)\mathrm{}_A(w).$$

#### 1.3.3 Equi-distribution Identities

The covering map $`f:A_{n+1}S_n`$, presented in Definition 5.1, allows us to translate $`S_n`$-identities, which involve the delent statistic, into corresponding $`A_{n+1}`$-identities. This strategy is used in the proofs of part (2) of the following theorems.

Part (1) of the following theorem is a new generalization of MacMahon’s classical identity, and part (2) is its $`A`$-analogue.

###### Theorem 1.9

(see Theorem 6.1)

$$\underset{\sigma S_n}{}q^{\mathrm{}_S(\sigma )}t^{del_S(\sigma )}=\underset{\sigma S_n}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\sigma )}t^{del_S(\sigma )}=$$
$`(1)`$
$$=(1+qt)(1+q+q^2t)\mathrm{}(1+q+\mathrm{}+q^{n1}t);$$

and

$$\underset{wA_{n+1}}{}q^{\mathrm{}_A(w)}t^{del_A(w)}=\underset{wA_{n+1}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{A_{n+1}}(w)}t^{del_A(w)}$$
$`(2)`$
$$=(1+2qt)(1+q+2q^2t)\mathrm{}(1+q+\mathrm{}+q^{n2}+2q^{n1}t).$$

Recall the standard notation $`[m]=\{1,\mathrm{},m\}`$. The main theorem in this paper strengthens Theorem 1.1, and also gives its $`A`$-analogue. This is

###### Theorem 1.10

(See Theorem 9.1) For every subsets $`D_1[n1]`$ and $`D_2[n]`$

$$\underset{\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)D_1,\mathrm{𝐷𝑒𝑙}_S(\pi ^1)D_2\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi )}=$$
$`(1)`$
$$\underset{\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)D_1,\mathrm{𝐷𝑒𝑙}_S(\pi ^1)D_2\}}{}q^{\mathrm{}_S(\pi )},$$

and

$$\underset{\{\sigma A_{n+1}|\mathrm{𝐷𝑒𝑠}_A(\sigma ^1)D_1,\mathrm{𝐷𝑒𝑙}_A(\sigma ^1)D_2\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{A_{n+1}}(\sigma )}=$$
$`(2)`$
$$\underset{\{\sigma A_{n+1}|\mathrm{𝐷𝑒𝑠}_A(\sigma ^1)D_1,\mathrm{𝐷𝑒𝑙}_A(\sigma ^1)D_2\}}{}q^{\mathrm{}_A(\sigma )}.$$

This shows that the delent set and the descent set play a similar role in these identities.

The $`A`$-analogue of Corollary 1.2 follows. It is obtained as a special case of Corollary 9.2(2) (by substituting $`q_3=1`$).

###### Corollary 1.11

(See Corollary 9.2)

$$\underset{\sigma A_{n+1}}{}q_1^{\mathrm{𝑟𝑚𝑎𝑗}_{A_{n+1}}(\sigma )}q_2^{\mathrm{𝑑𝑒𝑠}_A(\sigma ^1)}=\underset{\sigma A_{n+1}}{}q_1^{\mathrm{}_A(\sigma )}q_2^{\mathrm{𝑑𝑒𝑠}_A(\sigma ^1)}.$$

Note that, while the $`S`$-identity holds for $`\mathrm{𝑚𝑎𝑗}_{S_n}`$ as well as for $`\mathrm{𝑟𝑚𝑎𝑗}_{S_n}`$, it is not possible to replace $`\mathrm{𝑟𝑚𝑎𝑗}_{A_{n+1}}`$ by $`\mathrm{𝑚𝑎𝑗}_{A_{n+1}}`$ in the $`A`$-analogue.

## 2 Preliminaries

### 2.1 Notation

For an integer $`a`$ we let $`[a]:=\{1,2,\mathrm{},a\}`$ (where $`[0]:=\mathrm{}`$). Let $`n_1,\mathrm{},n_r`$ be non-negative integers such that $`_{i=1}^rn_i=n`$. Recall that the $`q`$-multinomial coefficient $`\left[\genfrac{}{}{0pt}{}{n}{n_1,\mathrm{},n_r}\right]_q`$ is defined by:

$$[0]!_q:=1,$$

$$[n]!_q:=[n1]!_q(1+q+\mathrm{}+q^{n1})(n1),$$

$$\left[\genfrac{}{}{0pt}{}{n}{n_1\mathrm{}n_r}\right]_q:=\frac{[n]!_q}{[n_1]!_q\mathrm{}[n_r]!_q}.$$

Represent $`\sigma S_n`$ by ‘its second row’ $`\sigma =[\sigma (1),\mathrm{},\sigma (n)]`$. We also use the cycle-notation; in particular, we denote $`s_i:=(i,i+1)`$, the transposition of $`i`$ and $`i+1`$. Thus

$`[\mathrm{},\sigma (i),\sigma (i+1),\mathrm{}]s_i=[\mathrm{},\sigma (i+1),\sigma (i),\mathrm{}]`$ (2)
(i.e. only $`\sigma (i),\sigma (i+1)`$ switch places).

### 2.2 The Coxeter System of the Symmetric Group

The symmetric group on $`n`$ letters, denoted by $`S_n`$, is generated by the set of adjacent transpositions $`S:=\{(i,i+1)|1i<n\}`$.

The defining relations of $`S`$ are the Moore-Coxeter relations :

$$(s_is_{i+1})^3=1(1i<n),$$

$$(s_is_j)^2=1(|ij|>1)$$

$$s_i^2=1(i).$$

This set of generators is called the Coxeter system of $`S_n`$.

For $`\pi S_n`$ let $`\mathrm{}_S(\pi )`$ be the standard length of $`\pi `$ with respect to $`S`$ (i.e. the length of the canonical presentation of $`\pi `$, see Section 3 ). Let $`w`$ be a word on the letters $`S`$. A commuting move on $`w`$ switches the positions of consequent letters $`s_is_j`$ where $`|ij|>1`$. A braid move replaces $`s_is_{i+1}s_i`$ by $`s_{i+1}s_is_{i+1}`$ or vice versa. The following is a well known fact, but we shall not use it in this paper.

###### Fact 2.1

All irreducible expressions of $`\pi S_n`$ are of length $`\mathrm{}_S(\pi )`$. For every pair of irreducible words of $`\pi S_n`$, it is possible to move from one to another along commuting and braid moves.

### 2.3 Permutation Statistics

There are various statistics on the symmetric groups $`S_n`$, like the descent number and the major index. We introduce and study analogous statistics on the alternating groups $`A_n`$. As was mentioned, to distinguish we add ‘sub S’ and ‘sub A’ accordingly.
Given a permutation $`\pi =[\pi (1),\mathrm{},\pi (n)]`$ in the symmetric group $`S_n`$, we say that a pair $`(i,j)`$, $`1i<jn`$ is an inversion of $`\pi `$ if $`\pi (i)>\pi (j)`$. The set of inversions of $`\pi `$ is denoted by $`Inv_S(\pi )`$ and its cardinality is denoted by $`\mathrm{𝑖𝑛𝑣}_S(\pi )`$. Also $`1i<n`$ is a descent of $`\pi `$ if $`\pi (i)>\pi (i+1)`$. For the definitions of the descent set $`\mathrm{𝐷𝑒𝑠}_S(\pi )`$, the descent number $`\mathrm{𝑑𝑒𝑠}_S(\pi )`$, the major index $`\mathrm{𝑚𝑎𝑗}_S(\pi )`$ and the reverse major index $`\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi )`$, see Subsection 1.2.

Note that $`i`$ is a descent of $`\pi `$ if and only if $`\mathrm{}_S(\pi s_i)<\mathrm{}_S(\pi )`$. Thus (as already mentioned in Subsection 1.2), the descent set, and consequently the other related statistics, have an algebraic interpretation in terms of the Coxeter system. Also, for every $`\pi S_n`$

$`\mathrm{𝑖𝑛𝑣}_S(\pi )=\mathrm{}_S(\pi ).`$ (3)
The following well known identity is due to MacMahon . See, e.g.  and \[16, Corollaries 1.3.10 and 4.5.9\].

###### Theorem 2.2

$$\underset{\pi S_n}{}q^{\mathrm{𝑖𝑛𝑣}_S(\pi )}=\underset{\pi S_n}{}q^{\mathrm{𝑚𝑎𝑗}_S(\pi )}=$$

$$=[n]!_q=(1+q)(1+q+q^2)\mathrm{}(1+q+\mathrm{}+q^{n2}+q^{n1}).$$

The following theorem is a reformulation of \[6, Theorem 1\].

###### Theorem 2.3

For every $`B[n1]`$,

$$\underset{\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)=B\}}{}q^{\mathrm{𝑖𝑛𝑣}_S(\pi )}=\underset{\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)=B\}}{}q^{\mathrm{𝑚𝑎𝑗}_S(\pi )}.$$

Note. Let $`\sigma S_n`$, $`\sigma =[\sigma (1),\mathrm{},\sigma (n)]`$. Then $`\sigma =[\mathrm{},k,\mathrm{},\mathrm{},\mathrm{}]`$ (i.e. $`k`$ is left of $`\mathrm{}`$ in $`\sigma `$ ) if and only if $`\sigma ^1(k)<\sigma ^1(\mathrm{})`$. Shuffles. Let $`1in1`$, then $`wS_n`$ is an $`\{i\}`$-shuffle if it shuffles $`\{1,\mathrm{},i\}`$ with $`\{i+1,\mathrm{},n\}`$; in other words, if $`1a<bi`$ then $`w^1(a)<w^1(b)`$, and similarly, if $`i+1k<\mathrm{}n`$, then $`w^1(k)<w^1(\mathrm{})`$.

Example. Let $`n=4`$ and $`B=\{2\}`$, then $`\{1,2\}`$ and $`\{3,4\}`$ are being shuffled, hence

$$[1,2,3,4],[1,3,2,4],[1,3,4,2],[3,1,2,4],[3,1,4,2],[3,4,1,2]$$

are all the $`\{2\}`$-shuffles.

More generally, let $`B=\{i_1,\mathrm{},i_k\}[n1]`$, where $`i_1<\mathrm{}<i_k`$. Denote $`i_0:=0`$ and $`i_{k+1}:=n`$. A $`B`$-shuffle is a permutation which shuffles $`\{1,\mathrm{},i_1\},\{i_1+1,\mathrm{},i_2\},\mathrm{}`$ Thus $`\pi S_n`$ is a $`B`$-shuffle if it satisfies: if $`i_ja<bi_{j+1}`$ for some $`0jk`$, then $`\pi =[\mathrm{},a,\mathrm{},b,\mathrm{}]`$ (i.e. $`a`$ is left of $`b`$ in $`\pi `$). Notice that in particular there can be no descent for $`\pi ^1`$ on any $`a`$, $`i_j<a<i_{j+1}`$, hence $`Des_S(\pi ^1)B`$. The opposite is also clear, hence

###### Fact 2.4

For every $`B[n1]`$

$$\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)B\}=\{\pi S_n|\pi \text{is a }B\text{-shuffle}\}.$$

For a permutation $`\pi S_n`$ let

$$\mathrm{𝑠𝑢𝑝𝑝}(\pi ):=\{1in|\pi (i)i\}$$

be the support of $`\pi `$.

Let $`k[n1]`$, and let $`\pi _1,\pi _2`$ be permutations in $`S_n`$, such that $`\mathrm{𝑠𝑢𝑝𝑝}(\pi _1)[k]`$ and $`\mathrm{𝑠𝑢𝑝𝑝}(\pi _2)[k+1,n]`$. A permutation $`\sigma S_n`$ is called a shuffle of $`\pi _1`$ and $`\pi _2`$ if $`\sigma =\pi _1\pi _2r`$ for some $`\{k\}`$-shuffle $`r`$. Equivalently, $`\sigma `$ is a shuffle of $`\pi _1`$ and $`\pi _2`$ if and only if the letters of $`[k]`$ appear in $`\sigma `$ in the same order as they appear in $`\pi _1`$ and the letters of $`[k+1,n]`$ appear in $`\sigma `$ in the same order as they appear in $`\pi _2`$. The following is a special case of \[16, Prop. 1.3.17\].

###### Fact 2.5

Let $`k[n]`$, and let $`\pi _1,\pi _2`$ be permutations in $`S_n`$, such that $`\mathrm{𝑠𝑢𝑝𝑝}(\pi _1)[k]`$ and $`\mathrm{𝑠𝑢𝑝𝑝}(\pi _2)[k+1,n]`$. Then

$$\underset{\mathrm{𝐷𝑒𝑠}(r^1)\{k\}}{}q^{\mathrm{𝑖𝑛𝑣}_S(\pi _1\pi _2r)\mathrm{𝑖𝑛𝑣}_S(\pi _1)\mathrm{𝑖𝑛𝑣}_S(\pi _2)}=\left[\genfrac{}{}{0pt}{}{n}{k}\right]_q.$$

The following analogue is a special case of a well known theorem of Garsia and Gessel. It should be noted that, while Garsia-Gessel’s Theorem is stated in terms of sequences, our reformulation is in terms of permutations.

###### Theorem 2.6

\[7, Theorem 3.1\] Let $`k[n1]`$, and let $`\pi _1,\pi _2`$ be permutations in $`S_n`$, such that $`\mathrm{𝑠𝑢𝑝𝑝}(\pi _1)[k]`$ and $`\mathrm{𝑠𝑢𝑝𝑝}(\pi _2)[k+1,n]`$. Let $`\nu _k:=(1,k+1)(2,k+2)\mathrm{}(nk,n)S_n`$. Then

$$\underset{\mathrm{𝐷𝑒𝑠}_S(r^1)\{k\}}{}q^{\mathrm{𝑚𝑎𝑗}_S(\pi _1\pi _2r)\mathrm{𝑚𝑎𝑗}_S(\pi _1)\mathrm{𝑚𝑎𝑗}_S(\nu _k^1\pi _2\nu _k)}=\left[\genfrac{}{}{0pt}{}{n}{k}\right]_q.$$

In order to translate Theorem 2.6 into Garsia-Gessel’s terminology, note that $`\pi _1\pi _2r`$ are shuffles of $`\pi _1`$ and $`\pi _2`$ (as mentioned above); thus the sum runs over all shuffles of $`\pi _1`$ and $`\pi _2`$. Also, $`\mathrm{𝑚𝑎𝑗}_S(\nu _k^1\pi _2\nu _k)`$ is the major index of $`\pi _2`$, when it is considered as a sequence on the letters $`[k+1,n]`$.

###### Remark 2.7

In general, it is possible to replace a statement involving $`\mathrm{𝑚𝑎𝑗}`$ by a corresponding statement involving $`r\mathrm{𝑚𝑎𝑗}`$, using the following automorphism $`\sigma \widehat{\sigma }`$ :
Let $`\rho _nS_n`$ denote the involution

$$\rho _n:=(1,n)(2,n1)\mathrm{}([n/2],[(n+3)/2]),$$

where for a real number $`\alpha `$, $`[\alpha ]`$ is the ‘integer part’ of $`\alpha `$. Define

$$\widehat{\sigma }:=\rho _n\sigma \rho _n.$$

Then $`\sigma \widehat{\sigma }`$ is an automorphism of $`S_n`$ with the following properties :

1. Let $`i<j`$ and $`\sigma (i)>\sigma (j)`$, then $`n+1j<n+1i`$ and $`\widehat{\sigma }(n+1j)>\widehat{\sigma }(n+1i)`$. In particular, $`iDes_S(\sigma )`$ if and only if $`niDes_S(\widehat{\sigma })`$, hence

$`rmaj_{S_n}(\sigma )=maj_S(\widehat{\sigma }).`$ (4)
2. There is a bijection between $`Inv_S(\sigma )`$ and $`Inv_S(\widehat{\sigma })`$ given by

$`(i,j)(n+1j,n+1i)`$, hence

$`inv_S(\sigma )=inv_S(\widehat{\sigma }).`$ (5)
3. Part 1 implies that $`\sigma `$ is an $`\{i\}`$-shuffle if and only if $`\widehat{\sigma }`$ is an $`\{ni\}`$-shuffle, i.e.

$`\mathrm{𝐷𝑒𝑠}_S(\sigma ^1)\{i\}\mathrm{𝐷𝑒𝑠}_S(\widehat{\sigma }^1)\{ni\}.`$ (6)
This easily generalizes to $`B`$-shuffles.

Note that by (4) and \[15, Claim 0.4\], for every $`\pi S_n`$

$$\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi )=charge(\pi ^1),$$

where the charge is defined as in \[10, p. 242\].

## 3 The $`S`$ and $`A`$ Canonical Presentations

In this section we consider canonical presentations of elements in $`S_n`$ and in $`A_n`$ by the corresponding Coxeter generators. This presentation for $`S_n`$ is well known, see for example \[8, pp. 61-62\]. The analogous presentation for $`A_n`$ follows from the properties of the Mitsuhashi’s Coxeter generators.

### 3.1 The $`S_n`$ Case

The $`S_n`$ canonical presentation is proved below, using the $`S`$-procedure, which is also applied later.

Recall that $`s_i=(i,i+1)`$, $`1i<n`$, are the Coxeter generators of $`S_n`$. For each $`1jn1`$ define

$`R_j^S=\{1,s_j,s_js_{j1},\mathrm{},s_js_{j1}\mathrm{}s_1\}`$ (7)
and note that $`R_1^S,\mathrm{},R_{n1}^SS_n`$. .

###### Theorem 3.1

(see \[8, pp. 61-62\]) Let $`wS_n`$, then there exist unique elements $`w_jR_j^S`$, $`1jn1`$, such that $`w=w_1\mathrm{}w_{n1}`$. Thus, the presentation $`w=w_1\mathrm{}w_{n1}`$ is unique.

###### Definition 3.2

Call the above $`w=w_1\mathrm{}w_{n1}`$ in Theorem 3.1 the $`S`$ canonical presentation of $`wS_n`$.

A proof of Theorem 3.1 follows from the following S-Procedure.
The S-Procedure. The following is a simple procedure for calculating the $`S`$ canonical presentation of a given $`wS_n`$. It can also be used to prove Theorem 3.1, as well as various other facts. Let $`\sigma S_n`$, $`\sigma (r)=n`$, $`\sigma =[\mathrm{},n,\mathrm{}]`$, then apply Equation (2) to ‘pull $`n`$ to its place on the right’: $`\sigma s_rs_{r+1}\mathrm{}s_{n1}=[\mathrm{}\mathrm{},n]`$. This gives $`w_{n1}=s_{n1}\mathrm{}s_{r+1}s_r`$. Next, in

$$\sigma w_{n1}^1=\sigma s_rs_{r+1}\mathrm{}s_{n1}=[\mathrm{},n1,\mathrm{},n],$$

pull $`n1`$ to its right place (second from right) by a similar product $`s_ts_{t+1}\mathrm{}s_{n2}`$. This yields $`w_{n2}=s_{n2}\mathrm{}s_t`$. Continue! Finally, $`\sigma =w_1\mathrm{}w_{n1}`$.

For example, let $`\sigma =[2,5,4,1,3]`$, then $`w_{n1}=w_4=s_4s_3s_2`$; $`\sigma w_4^1=[2,4,1,3,5]`$, therefore $`w_3^1=s_2s_3`$. Check that $`w_2=1`$ and, finally, $`w_1=s_1`$. Thus $`\sigma =w_1\mathrm{}w_4=(s_1)(1)(s_3s_2)(s_4s_3s_2)`$. The uniqueness in Theorem 3.1 follows by cardinality, since the number of canonical words in $`S_n`$ is at most

$$\underset{j=1}{\overset{n1}{}}card(R_j^S)=S_n.$$

This proves Theorem 3.1. $`\mathrm{}`$

### 3.2 A Generating Set for $`A_n`$

We turn now to $`A_n`$. As was already mentioned in 1.3.1, we let

$$a_i:=s_1s_{i+1}(1in1).$$

The set

$$A:=\{a_i|1in1\}$$

generates the alternating group on $`n`$ letters $`A_{n+1}`$. This generating set and its following properties appear in .

###### Proposition 3.3

\[12, Proposition 2.5\] The defining relations of $`A`$ are

$$(a_ia_j)^2=1(|ij|>1);$$

$$(a_ia_{i+1})^3=1(1i<n1);$$

$$a_1^3=1\text{and}a_i^2=1(1<in1).$$

The general braid-relation $`(a_ia_{i+1})^3=1`$ implies the following braid-relations.

1. $`a_2a_1a_2=a_1^1a_2a_1^1`$ and
2. $`a_2a_1^1a_2=a_1a_2a_1`$.
3. $`a_{i+1}a_ia_{i+1}=a_ia_{i+1}a_i`$ if $`i2`$ (since $`a_i^1=a_i`$).

Let

$$\overline{A}:=A\{a_1^1\},$$

where $`A`$ is defined as above. Clearly, $`\overline{A}`$ is a generating set for $`A_{n+1}`$.

### 3.3 The $`A`$ Canonical Presentation

Mitsuhashi’s Coxeter generators are now applied to obtain a unique canonical presentation for elements in the alternating group.

For each $`1jn1`$ define

$`R_j^A=\{1,a_j,a_ja_{j1},\mathrm{},a_j\mathrm{}a_2,a_j\mathrm{}a_2a_1,a_j\mathrm{}a_2a_1^1\}`$ (8)
and note that $`R_1^A,\mathrm{},R_{n1}^AA_{n+1}`$.

###### Theorem 3.4

Let $`vA_{n+1}`$, then there exist unique elements $`v_jR_j^A`$, $`1jn1`$, such that $`v=v_1\mathrm{}v_{n1}`$, and this presentation is unique.

###### Definition 3.5

Call the above $`v=v_1\mathrm{}v_{n1}`$ in Theorem 3.4 the $`A`$ canonical presentation of $`v`$.

Proof of Theorem 3.4. Let $`v=w_1\mathrm{}w_n`$, $`w_jR_j^S`$, be the $`S`$ canonical presentation of $`v`$. Rewrite that presentation explicitly as

$`v=(s_{i_1}s_{i_2})\mathrm{}(s_{i_{2r1}}s_{i_{2r}}).`$ (9)
Note that $`s_is_j=(s_is_1)(s_1s_j)=a_{i1}^1a_{j1}`$ (denote $`a_0=1`$). Thus each $`s_i`$ in (9) is replaced by a corresponding $`a_{i1}^{\pm 1}`$. It follows that for each $`2jn`$, $`w_j`$ is replaced by $`v_{j1}R_{j1}^A`$ and $`v=v_1\mathrm{}v_{n1}`$. This proves the existence of such a presentation.

A second proof of the existence follows from the following A-procedure.
The A-Procedure is similar to the S-procedure. We describe its first step, which is also its inductive step.
Let $`\sigma A_{n+1}`$, $`\sigma =[\mathrm{},n+1,\mathrm{}]`$. As in the S-procedure, pull $`n+1`$ to the right: $`\sigma s_rs_{r+1}\mathrm{}s_n=[b_1,b_2,\mathrm{},n+1]`$. The (S-) length of $`s_rs_{r+1}\mathrm{}s_n`$ is $`nr+1`$; if it is odd, use $`\sigma s_rs_{r+1}\mathrm{}s_ns_1=[b_2,b_1,\mathrm{},n+1]`$. Thus

$$v_{n1}=\{\begin{array}{cc}s_ns_{n1}\mathrm{}s_r,\hfill & \text{ if }nr+1\text{ is even;}\hfill \\ s_1s_ns_{n1}\mathrm{}s_r,\hfill & \text{ if }nr+1\text{ is odd.}\hfill \end{array}$$

The case $`r2`$. Then $`s_1s_j=s_js_1`$ for all $`jr+1`$, hence

$$v_{n1}=\{\begin{array}{cc}(s_1s_n)(s_1s_{n1})\mathrm{}(s_1s_r)=a_{n1}\mathrm{}a_{r1},\hfill & \text{ if }nr+1\text{ is even;}\hfill \\ (s_1s_1)(s_1s_n)\mathrm{}(s_1s_r)=a_{n1}\mathrm{}a_{r1},\hfill & \text{ if }nr+1\text{ is odd.}\hfill \end{array}$$

The case $`r=1`$. If $`nr+1=n`$ is even,

$$v_{n1}=s_n\mathrm{}s_2s_1=(s_1s_n)\mathrm{}(s_1s_3)(s_2s_1)=a_{n1}\mathrm{}a_2a_1^1,$$

and similarly if $`nr+1`$ is odd.
This completes the first step. In the next step, pull $`n`$ to the $`n`$-th position (i.e. second from the right), etc. This proves the existence of such a presentation $`v=v_1\mathrm{}v_{n1}`$. Example. Let $`\sigma =[3,5,4,2,1]`$, so $`n+1=5`$. Now $`\sigma s_2s_3s_4=[3,4,2,1,5]`$ and since $`s_2s_3s_4`$ is of odd length (=3), permute 3 and 4: $`\sigma s_2s_3s_4s_1=[4,3,2,1,5]`$. Thus $`v_3=s_1s_4s_3s_2=(s_1s_1)(s_1s_4)(s_1s_3)(s_1s_2)=a_3a_2a_1`$. Similarly, $`v_2=a_2a_1^1`$ and $`v_1=a_1`$, hence $`[3,5,4,2,1]=(a_1)(a_2a_1^1)(a_3a_2a_1)`$. Uniqueness follows by cardinality: note that for all $`1jn1`$, $`R_j^A=j+2`$, hence the number of such words $`v_1\mathrm{}v_{n1}`$ in $`A_{n+1}`$ is at most

$$\underset{j=1}{\overset{n1}{}}(j+2)=A_{n+1}.$$

Since each element in $`A_{n+1}`$ does have such a presentation, this implies the uniqueness - and the proof of Theorem 3.4 is complete. $`\mathrm{}`$Given $`wS_n`$, we say that $`s_i`$ occurs $`\mathrm{}`$ times in $`w`$ if it occurs $`\mathrm{}`$ times in the canonical presentation of $`w`$. Similarly for the number of occurrences of $`a_i`$, or of $`a_1^1`$, in $`vA_{n+1}`$. The number of occurrences of $`s_1`$, as well as those of $`a_1^{\pm 1}`$, are of particular importance in this paper.

###### Lemma 3.6

Let $`wS_n`$, then the number of occurrences of $`s_i`$ in $`w`$ equals the number of occurrences of $`s_i`$ in $`w^1`$. Similarly for $`A_{n+1}`$ and $`a_1^{\pm 1}`$.

This is an obvious corollary of

###### Lemma 3.7

Let $`w=s_{i_1}\mathrm{}s_{i_p}`$ be the canonical presentation of $`wS_n`$. Then the canonical presentation of $`w^1`$ is obtained from the presentation $`w^1=s_{i_p}\mathrm{}s_{i_1}`$ by commuting moves only - without any braid moves.
Similarly for $`v,v^1A_{n+1}`$.

Proof. We prove for $`S_n`$. The proof is by induction on $`n`$. Write $`w=w_1\mathrm{}w_{n1}`$, $`w_jR_j^S`$. If $`w_{n1}=1`$ then $`wS_{n1}`$ and the proof follows by induction.

Let $`w_{n1}=s_{n1}s_{n2}\mathrm{}s_k`$ where $`1kn1`$. Now either $`w_{n2}=1`$ or $`w_{n2}=s_{n2}s_{n3}\mathrm{}s_{\mathrm{}}`$ for some $`1\mathrm{}n2`$, and similarly for $`w_{n3}`$, $`w_{n4}`$ etc. The case $`w_{n2}=1`$ is similar to the case $`w_{n2}1`$ and is left to the reader, so let $`w_{n2}1`$ and

$$w^1=w_{n1}^1w_{n2}^1\mathrm{}=(s_k\mathrm{}s_{n1})(s_{\mathrm{}}\mathrm{}s_{n2})w_{n3}^1w_{n4}^1\mathrm{}$$

Notice that $`s_{n1}(s_{\mathrm{}}\mathrm{}s_{n3})=(s_{\mathrm{}}\mathrm{}s_{n3})s_{n1}`$, hence

$$w^1=(s_k\mathrm{}s_{n2})(s_{\mathrm{}}\mathrm{}s_{n3})(s_{n1}s_{n2})w_{n3}^1w_{n4}^1\mathrm{}$$

Next, move $`s_{n1}s_{n2}`$ to the right, similarly, by commuting moves. Continue by similarly pulling $`s_{n3}`$ \- in $`w_{n3}^1`$ \- to the right, etc. It follows that by such commuting moves we obtain

$$w^1=\overline{w}^1(s_{n1}s_{n2}\mathrm{}s_d)$$

for some $`d`$, where $`\overline{w}=s_{j_r}\mathrm{}s_{j_1}S_{n1}`$, and is in canonical form. By induction, transform $`\overline{w}^1`$ to its canonical form by commuting moves - and the proof is complete. $`\mathrm{}`$

## 4 The Lengths Statistics

The canonical presentations of the previous sections allow us to introduce the S and the A lengths.

###### Definition 4.1

(The length statistics).

1. Let $`wS_n`$ with $`w=s_{i_1}\mathrm{}s_{i_r}`$ its $`S`$ canonical presentation, then its S-length is $`\mathrm{}_S(w)=r`$.
2. Let $`vA_{n+1}`$ with $`v=a_{i_1}^{ϵ_1}\mathrm{}a_{i_r}^{ϵ_r}`$ ($`ϵ_i=\pm 1`$) its $`A`$ canonical presentation, then its A-length is $`\mathrm{}_A(v)=r`$.

For example, $`\mathrm{}_A(a_1)=1`$ and $`\mathrm{}_S(a_1)=\mathrm{}_S(s_1s_2)=2`$.

###### Remark 4.2

An analogue of Fact 2.1 holds : All irreducible expressions of $`vA_{n1}`$ are of length $`\mathrm{}_A(v)`$. This fact will not be used in the paper.

###### Definition 4.3

1. Let $`wS_n`$. The number of times that $`s_1`$ occurs in the $`S`$ canonical presentation of $`w`$ is denoted by $`del_S(w)`$.
2. Let $`vA_{n1}`$. The number of times that $`a_1^{\pm 1}`$ occurs in the $`A`$ canonical presentation of $`v`$ is denoted by $`del_A(v)`$.

For example, $`del_S(s_1s_2s_1s_3)=2`$ and $`del_A(a_1^1a_2a_1a_3a_2a_1^1))=3`$.
A combinatorial characterization of $`del_S`$ ($`del_A`$) is given in section 7.

Relations between $`del_S`$ and the S and the A lengths of $`vA_{n+1}`$ are given by the following proposition.

###### Proposition 4.4

Let $`wA_{n+1}`$, then

$$\mathrm{}_A(w)=\mathrm{}_S(w)del_S(w).$$

Moreover, let

$`w=s_{i_1}\mathrm{}s_{i_{2r}}=w_1\mathrm{}w_n,w_iR_i^S,`$ (10)
be its $`S`$ canonical presentation and

$`w=a_{j_1}^{ϵ_1}\mathrm{}a_{j_t}^{ϵ_t}=v_1\mathrm{}v_{n1},v_iR_i^A,`$ (11)
its $`A`$ canonical presentation. Then

$`\mathrm{}_A(v_i)=\{\begin{array}{cc}\mathrm{}_S(w_{i+1})\hfill & \text{ if }s_1\text{ does not occur in }w_{i+1}\text{;}\hfill \\ \mathrm{}_S(w_{i+1})1\hfill & \text{ if }s_1\text{ occurs in }w_{i+1}\text{.}\hfill \end{array}`$ (12)
Proof. As in the proof of Theorem 3.4, the proof easily follows from (9) by replacing $`s_is_j`$ by $`(s_is_1)(s_1s_j)`$.

$`\mathrm{}`$

The S-lengths $`\mathrm{}_S(w_{i+1})`$ and the A–lengths $`\mathrm{}_A(v_i)`$ in (12) can be calculated directly from $`w=[b_1,\mathrm{},b_{n+1}]`$ as follows.

###### Proposition 4.5

Let $`wS_{n+1}`$ as above. For each $`2jn`$ let $`T_j(w)`$ denote the set of indices $`i`$ such that $`i<j`$ and $`w=[\mathrm{},j,\mathrm{},i,\mathrm{}]`$ (i.e. $`w^1(i)>w^1(j)`$); denote $`t_j(w)=T_j(w)`$. Keeping the notations of Proposition 4.4 we have:

1. $`\mathrm{}_S(w_j)=t_{j+1}(w)`$. Moreover, $`T_{j+1}(w)`$ is the full set $`\{1,\mathrm{},j\}`$ (i.e. $`t_{j+1}(w)=j`$) if and only if $`s_1`$ occurs in $`w_j`$.
2. $`\mathrm{}_A(v_k)`$ equals $`T_k(w)`$, provided that $`T_k(w)`$ is not the full set $`\{1,\mathrm{},k1\}`$, and it equals $`T_k(w)1`$ otherwise.

Proof. By an easy induction on $`n`$, prove that

$$(\mathrm{}_S(w_1),\mathrm{},\mathrm{}_S(w_n))=(t_2(w),\mathrm{},t_{n+1}(w)).$$

This follows since
$`[b_1,\mathrm{},b_n,n+1]s_ns_{n1}\mathrm{}s_r=[b_1,\mathrm{},b_{r1},n+1,b_r,\mathrm{},b_n]`$.
Here are the details: Write $`w=w_1\mathrm{}w_n`$, let $`\sigma =w_1\mathrm{}w_{n1}`$, so $`\sigma =[d_1,\mathrm{},d_n,n+1]`$. If $`w_n=1`$, the claim follows by induction. Let $`w_n=s_ns_{n1}\mathrm{}s_r`$ for some $`r1`$. Then $`w=\sigma w_n=[d_1,\mathrm{},d_{r1},n+1,d_r,\mathrm{}d_n]`$. Thus $`t_{n+1}(w)=nr+1=\mathrm{}_S(w_n)`$. Also, for $`2jn`$, $`t_j(w)=t_j(\sigma )`$, and the proof of part 1 follows by induction. Part 2 now follows from (12). $`\mathrm{}`$

## 5 $`f`$-Pairs of Statistics

### 5.1 The Covering Map

Theorems 3.1 and 3.4 allow us to introduce the following definition.

###### Definition 5.1

Define $`f:A_{n+1}S_n`$ as follows.

$$f(a_1)=f(a_1^1)=s_1\text{and}f(a_i)=s_i,2in1.$$

Now extend $`f:R_j^AR_j^S`$ via

$$f(a_ja_{j1}\mathrm{}a_{\mathrm{}})=s_js_{j1}\mathrm{}s_{\mathrm{}},f(a_j\mathrm{}a_1)=f(a_j\mathrm{}a_1^1)=s_j\mathrm{}s_1.$$

Finally, let $`vA_{n+1},v=v_1\mathrm{}v_{n1}`$ its unique $`A`$ canonical presentation, then

$$f(v)=f(v_1)\mathrm{}f(v_{n1})$$

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

Notice that for $`vA_{n+1}`$, $`\mathrm{}_A(v)=\mathrm{}_S(f(v))`$. We therefore say that the pair of the length statistics $`(\mathrm{}_S,\mathrm{}_A)`$ is an $`f`$-pair. More generally, we have

###### 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 $`vA_{n+1}`$, $`m_A(v)=m_S(f(v))`$.

Examples of $`f`$-pairs are given in Proposition 5.4 below.

###### Proposition 5.3

Recall Definition 1.5.1. For every $`\pi A_{n+1}`$

$$\mathrm{𝐷𝑒𝑠}_A(\pi )=Des_S(f(\pi )).$$

Proof - is left to the reader. $`\mathrm{}`$

It follows that the descent statistics are $`f`$-pairs. By Definition 4.3, $`(del_S,del_A)`$ is an $`f`$-pair. We summarize:

###### Proposition 5.4

The following pairs

$$(\mathrm{}_S,\mathrm{}_A),$$

$$(\mathrm{𝑑𝑒𝑠}_S,\mathrm{𝑑𝑒𝑠}_A),$$

$$(\mathrm{𝑚𝑎𝑗}_S,\mathrm{𝑚𝑎𝑗}_A),$$

$$(\mathrm{𝑟𝑚𝑎𝑗}_{S_n},\mathrm{𝑟𝑚𝑎𝑗}_{A_{n+1}})$$

and

$$(del_S,del_A)$$

are $`f`$-pairs.

### 5.2 The ‘del’ Statistics

The following basic properties of $`del_S`$ play an important role in this paper.

###### Proposition 5.5

* For each $`wS_n`$, $`f^1(w)=2^{del_S(w)}`$.
* For each $`wS_n`$ and $`vA_{n+1}`$

$`del_S(w)=del_S(w^1)\text{and}del_A(v)=del_A(v^1).`$ (13)

Proof. Part 1 follows since each occurrence of $`s_1`$ can be replaced by an occurrence of either $`a_1`$ or $`a_1^1`$. Part 2 follows from Lemma 3.6.

$`\mathrm{}`$

We have the following general proposition.

###### Proposition 5.6

Let $`(m_S,m_A)`$ be an $`f`$-pair of statistics, then for all $`n`$

$$\underset{vA_{n+1}}{}q^{m_A(v)}t^{del_A(v)}=\underset{wS_n}{}q^{m_S(w)}(2t)^{del_S(w)}.$$

Proof. Since $`A_{n+1}=_{wS_n}f^1(w)`$, a disjoint union, we have:

$$\underset{vA_{n+1}}{}q^{m_A(v)}t^{del_A(v)}=\underset{wS_n}{}\underset{vf^1(w)}{}q^{m_A(v)}t^{del_A(v)}=$$

$$\underset{wS_n}{}\underset{vf^1(w)}{}q^{m_S(f(v))}t^{del_S(f(v))}=\underset{wS_n}{}\underset{vf^1(w)}{}q^{m_S(w)}t^{del_S(w))}=$$

$$\underset{wS_n}{}2^{del_S(w)}q^{m_S(w)}t^{del_S(w))}.$$

$`\mathrm{}`$
A refinement of Proposition 5.6 is given in Proposition 5.10

###### Proposition 5.7

With the above notations we have:

1. $$\underset{\sigma S_n}{}q^{\mathrm{}_S(\sigma )}t^{del_S(\sigma )}=(1+qt)(1+q+q^2t)\mathrm{}(1+q+\mathrm{}+q^{n1}t).$$
2. $$\underset{wA_{n+1}}{}q^{\mathrm{}_A(w)}t^{del_A(w)}=(1+2qt)(1+q+2q^2t)\mathrm{}(1+q+\mathrm{}+q^{n2}+2q^{n1}t).$$

Proof.

1. The proof of part 1 is similar to the proof of Corollary 1.3.10 in . Let $`w_jR_j^S`$, then $`del_S(w_j)=1`$ if $`w_j=s_j\mathrm{}s_1`$ and $`=0`$ otherwise. Let $`wS_n`$ and let $`w=w_1\mathrm{}w_{n1}`$ be its $`S`$ canonical presentation, then $`del_S(w)=del_S(w_1)+\mathrm{}+del_S(w_{n1})`$ and $`\mathrm{}_S(w)=\mathrm{}_S(w_1)+\mathrm{}+\mathrm{}_S(w_{n1})`$. Thus

$$\underset{wS_n}{}q^{\mathrm{}_S(w)}t^{del_S(w)}=\underset{j=1}{\overset{n1}{}}\left(\underset{w_jR_j^S}{}q^{\mathrm{}_S(w_j)}t^{del_S(w_j)}\right).$$

The proof now follows since

$$\underset{w_jR_j^S}{}q^{\mathrm{}_S(w_j)}t^{del_S(w_j)}=1+q+q^2+\mathrm{}+q^{j2}+q^{j1}t.$$
2. By Proposition 5.6, part 2 follows from part 1.

$`\mathrm{}`$

### 5.3 Connection with the Stirling Numbers

Recall that $`c(n,k)`$ is the number of permutations in $`S_n`$ with exactly $`k`$ cycles, $`1kn`$: $`c(n,k)`$ are the sign-less Stirling numbers of the first kind. Let $`w_S(n,\mathrm{})`$ denote the number of $`S`$ canonical words in $`S_n`$ with $`\mathrm{}`$ appearances of $`s_1`$. Similarly, let $`w_A(n+1,\mathrm{})`$ denote the number of $`A`$ canonical words in $`A_{n+1}`$ with $`\mathrm{}`$ appearances of $`a_1^{\pm 1}`$.

We prove

###### Proposition 5.8

Let $`0\mathrm{}n1`$, then

1. $$\underset{\mathrm{}0}{}w_S(n,\mathrm{})t^{\mathrm{}}=(t+1)(t+2)\mathrm{}(t+n1),$$

hence $`w_S(n,\mathrm{})=c(n,\mathrm{}+1)`$.
2. $$\underset{\mathrm{}0}{}w_A(n,\mathrm{})t^{\mathrm{}}=(2t+1)(2t+2)\mathrm{}(2t+n1),$$

hence $`w_A(n+1,\mathrm{})=2^{\mathrm{}}c(n,\mathrm{}+1)`$.

Proof. Substitute $`q=1`$ in Proposition 5.7 and, in part 1, apply Proposition 1.3.4 of , which states that

$$\underset{k=0}{\overset{n}{}}c(n,k)x^k=x(x+1)(x+2)(\mathrm{}(x+n1).$$

$`\mathrm{}`$further connections with the Stirling numbers are given below (Propositions 5.11, 5.12 and 7.10) and in .

### 5.4 A Multivariate Refinement

###### Definition 5.9

Let $`wS_n`$, $`w=w_1\mathrm{}w_{n1}`$ its $`S`$ canonical presentation and let $`1jn1`$. Denote $`ϵ_{_{S,j}}(w)=1`$ if $`s_1`$ occurs in $`w_j`$, and $`=0`$ otherwise; also denote

$$\overline{ϵ}_S(w)=(ϵ_{S,1}(w),\mathrm{},ϵ_{S,n1}(w))$$

and

$$t^{\overline{ϵ}_S(w)}=t_1^{ϵ_{S,1}(w)}\mathrm{}t_{n1}^{ϵ_{S,n1}(w)}.$$

Similarly for $`v=v_1\mathrm{}v_{n1}A_{n+1}`$: $`ϵ_{_{A,j}}(v)=1`$ if $`a_1^{\pm 1}`$ occurs in $`v_j`$, and $`=0`$ otherwise, and define $`\overline{ϵ}_A(w)`$ similarly. Clearly, $`del_S(w)=_jϵ_{_{S,j}}(w)`$ and $`del_A(v)=_jϵ_{_{A,j}}(v)`$.

Proposition 5.6 admits the following generalization.

###### Proposition 5.10

Let $`(m_S,m_A)`$ be an $`f`$-pair of statistics, then for all $`n`$

$$\underset{vA_{n+1}}{}q^{m_A(v)}\underset{j=1}{\overset{n1}{}}t_j^{ϵ_{_{A,j}}(v)}=\underset{wS_n}{}q^{m_S(w)}\underset{j=1}{\overset{n1}{}}(2t_j)^{ϵ_{_{S,j}}(w)}.$$

The proof is a slight generalization of the proof of Proposition 5.6 \- and is left to the reader. We end this section with another two multivariate generalizations, which will not be used in the rest of the paper. Proposition 5.7 generalizes as follows.

###### Proposition 5.11

Let $`\mathrm{}_S,\mathrm{}_A`$ be the length statistics, then

1. $$\underset{wS_n}{}q^{\mathrm{}_S(w)}\underset{j=1}{\overset{n1}{}}(t_j)^{ϵ_{_{S,j}}(w)}=(1+qt_1)(1+q+q^2t_2)\mathrm{}(1+q+\mathrm{}+q^{n1}t_{n1}).$$
2. $$\underset{vA_{n+1}}{}q^{\mathrm{}_A(v)}\underset{j=1}{\overset{n1}{}}t_j^{ϵ_{_{A,j}}(v)}=(1+2qt_1)\mathrm{}(1+q+\mathrm{}+q^{n2}+2q^{n1}t_{n1}).$$

One can generalize Proposition 5.8 as follows. Let $`w=w_1\mathrm{}w_{n1}S_n`$, a canonical presentation, with $`ϵ_{_{S,j}}(w)`$ and $`\overline{ϵ}__S(w)`$ as in Definition 5.9. Given $`\overline{ϵ}=(ϵ_1,\mathrm{},ϵ_{n1})`$ with all $`ϵ_i\{0,1\}`$, denote $`w_S(n,\overline{ϵ})=card\{wS_n\overline{ϵ}_S(w)=\overline{ϵ}\}`$. Also denote $`\overline{ϵ}=_jϵ_j`$ and $`t^{\overline{ϵ}}=_jt_j^{ϵ_j}`$. Note that

$$\underset{\overline{ϵ}=\mathrm{}}{}w_S(n,\overline{ϵ})=w_{\mathrm{}}(n,\mathrm{})=c(n,\mathrm{}+1).$$

Similarly, introduce the analogous notations for $`A_{n+1}`$.
Proposition 5.8 now generalizes as follows.

###### Proposition 5.12

With the above notations

1. $$\underset{\overline{ϵ}}{}w_S(n,\overline{ϵ})t^{\overline{ϵ}}=(t_1+1)\mathrm{}(t_{n1}+n1).$$
2. $$\underset{\overline{ϵ}}{}w_A(n,\overline{ϵ})t^{\overline{ϵ}}=(2t_1+1)\mathrm{}(2t_{n1}+n1).$$

## 6 The Major Index and the Delent Number

Recall the definitions of $`\mathrm{𝑟𝑚𝑎𝑗}_{S_n}`$ and $`\mathrm{𝑟𝑚𝑎𝑗}_{A_{n+1}}`$ from Subsections 1.2 and 1.3. In this section we prove

###### Theorem 6.1

$$\underset{\sigma S_n}{}q^{\mathrm{}_S(\sigma )}t^{del_S(\sigma )}=\underset{\sigma S_n}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\sigma )}t^{del_S(\sigma )}=$$
$`(1)`$
$$=(1+qt)(1+q+q^2t)\mathrm{}(1+q+\mathrm{}+q^{n1}t);$$

and

$$\underset{wA_{n+1}}{}q^{\mathrm{}_A(w)}t^{del_A(w)}=\underset{wA_{n+1}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{A_{n+1}}(w)}t^{del_A(w)}$$
$`(2)`$
$$=(1+2qt)(1+q+2q^2t)\mathrm{}(1+q+\mathrm{}+q^{n2}+2q^{n1}t).$$

Note that Theorem 6.1 follows from our main theorem 9.1. However, the proof of Theorem 9.1 applies the machinery required for the proof of Theorem 6.1 combined with additional, more elaborate arguments - therefore we prove it here.

Comparing the coefficients of $`t^k`$ in both parts, we obtain

###### Theorem 6.2

Let $`B_{n,k}^S:=\{\sigma S_ndel_S(\sigma )=k\}`$ and
$`B_{n+1,k}^A:=\{\sigma A_{n+1}del_A(\sigma )=k\}`$. Then for each $`0kn1`$,

$$\underset{\sigma B_{n,k}^S}{}q^{\mathrm{}_S(\sigma )}=\underset{\sigma B_{n,k}^S}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\sigma )};$$
$`(1)`$
and

$$\underset{\sigma B_{n+1,k}^A}{}q^{\mathrm{}_A(\sigma )}=\underset{\sigma B_{n,k}^A}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{A_{n+1}}(\sigma )}.$$
$`(2)`$
Note that part 1 is a refinement of MacMahon’s equi-distribution theorem.

The proof of Theorem 6.1 follows from the lemmas below. Recall that the descent set - hence also the major-indices $`maj_S`$ and $`\mathrm{𝑟𝑚𝑎𝑗}_{S_n}`$ \- are defined for any sequence of integers, not necessarily distinct. Here $`n`$ denotes the number of letters in the sequence.

###### Lemma 6.3

Let $`x_1,\mathrm{},x_n`$ and $`y`$ be integers, not necessarily distinct, such that $`x_i<y`$ for $`1in`$. Let $`u`$ be the $`n`$-tuple $`u=[x_1,\mathrm{},x_n]`$, and let

$$v_i=[x_1,\mathrm{},x_{i1},y,x_i,\mathrm{},x_n],1in+1$$

(thus $`v_1=[y,x_1,\mathrm{},x_n]`$ and $`v_{n+1}=[x_1,\mathrm{},x_n,y]`$). Then

1. $`{\displaystyle \underset{i=1}{\overset{n+1}{}}}q^{maj_S(v_i)}=q^{maj_S(u)}(1+q+\mathrm{}+q^n)`$ (14)
$`\text{and}{\displaystyle \underset{i=1}{\overset{n}{}}}q^{maj_S(v_i)}=q^{maj_S(u)}(q+q^2+\mathrm{}+q^n).`$ (15)
2. $`{\displaystyle \underset{i=1}{\overset{n+1}{}}}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(v_i)}=q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)}(1+q+\mathrm{}+q^n)`$ (16)
$`\text{and}{\displaystyle \underset{i=2}{\overset{n+1}{}}}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(v_i)}=q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)}(1+q+\mathrm{}+q^{n1}).`$ (17)

Part 1 of Lemma 6.3 is well known. The proof of part 2 is similar. For the sake of completeness the proof is included.

Proof. Denote $`u^{}=[x_1,\mathrm{},x_{n1}]`$ and $`u^{\prime \prime }=[x_2,\mathrm{},x_n]`$. Similarly, denote $`v_i^{}=[x_1,\mathrm{},x_{i1},y,x_i,\mathrm{},x_{n1}],1in,`$ and
$`v_i^{\prime \prime }=[x_2,\mathrm{},x_{i1},y,x_i,\mathrm{},x_n],2in+1`$
(thus $`v_n^{}=[x_1,\mathrm{},x_{n1},y]`$ and $`v_2^{\prime \prime }=[y,x_2,\mathrm{},x_n]`$).

1. We argue by induction on $`n`$, proving (14) and (15) first.

1. Assume $`x_{n1}x_n`$, then $`maj_S(v_{n+1})=maj_S(u)=maj_S(u^{})=maj_S(v_n^{})`$, $`maj_S(v_n)=maj_S(u)+n`$ and $`maj_S(v_i)=maj_S(v_i^{})`$ for $`1in1`$. It follows that

    $`{\displaystyle \underset{i=1}{\overset{n+1}{}}}q^{maj_S(v_i)}=q^{maj_S(v_{n+1})}+q^{maj_S(v_n)}+{\displaystyle \underset{i=1}{\overset{n1}{}}}q^{maj_S(v_i)}=`$
    $`q^{maj_S(u)}+q^nq^{maj_S(u)}+{\displaystyle \underset{i=1}{\overset{n1}{}}}q^{maj_S(v_i^{})}=`$
    $`q^nq^{maj_S(u)}+{\displaystyle \underset{i=1}{\overset{n}{}}}q^{maj_S(v_i^{})}=\text{(by induction)}`$
    $`q^{maj_S(u)}(1+q+\mathrm{}+q^{n1})+q^nq^{maj_S(u)}.`$
    2. Assume $`x_{n1}>x_n`$, then $`maj_S(v_{n+1})=maj_S(u)=maj_S(u^{})+n1`$ and $`maj_S(v_i)=maj_S(v_i^{})+n`$ for $`1in`$. Thus

    $`{\displaystyle \underset{i=1}{\overset{n+1}{}}}q^{maj_S(v_i)}=q^{maj_S(u)}+{\displaystyle \underset{i=1}{\overset{n}{}}}q^{n+maj_S(v_i^{})}=`$
    $`q^{maj_S(u)}+q^n{\displaystyle \underset{i=1}{\overset{n}{}}}q^{maj_S(v_i^{})}=\text{(by induction)}`$
    $`q^{maj_S(u)}+q^nq^{maj_S(u^{})}(1+q+\mathrm{}+q^{n1})=`$
    $`q^{maj_S(u)}+q^{maj_S(u)+1}(1+q+\mathrm{}+q^{n1})=`$
    $`q^{maj_S(u)}(1+q+\mathrm{}+q^n).`$
    Together, (a) and (b) prove Equation (14). Note that Equation (15) follows from Equation (14) since, in both cases above, $`maj_S(v_{n+1})=maj_S(u)`$.
2. We prove now (16) and (17).

1. Assume $`x_1x_2`$. First, note that $`1Des_S(v_1)`$ and it contributes $`n+11=n`$ to $`\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(v_1)`$. Let $`2kn1`$, then $`kDes_S(u)`$ if and only if $`k+1Des_S(v_1)`$; such $`k`$ contributes $`nk=(n+1)(k+1)`$ to both $`\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(v_1)`$ and to $`\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)`$. It follows that $`\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(v_1)=\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)+n`$.

    By similar arguments $`\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(v_i)=\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(v_i^{\prime \prime })`$ for $`\mathrm{\hspace{0.33em}2}in+1`$ and also $`\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)=\mathrm{𝑟𝑚𝑎𝑗}_{S_{n1}}(u^{\prime \prime })`$. Thus

    $`{\displaystyle \underset{i=1}{\overset{n+1}{}}}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}}(v_i)=q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)+n}+{\displaystyle \underset{i=2}{\overset{n+1}{}}}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(v_i^{\prime \prime })\text{(by induction)}}`$
    $`=q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)+n}+q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n1}}(u^{\prime \prime })}(1+q+\mathrm{}+q^{n1})`$
    and the proof follows.
    2. Assume $`x_1>x_2`$. Here (again) $`\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(v_1)=\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)+n`$ while $`\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(v_2)=\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(v_2^{\prime \prime })=\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)`$. By similar arguments as above, $`\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(v_i)=\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(v_i^{\prime \prime })+n`$ for $`3in+1`$. Also $`\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)=\mathrm{𝑟𝑚𝑎𝑗}_{S_{n1}}(u^{\prime \prime })+n1`$. Thus

    $`{\displaystyle \underset{i=1}{\overset{n+1}{}}}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(v_i)}=q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)+n}+q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)}+q^n{\displaystyle \underset{i=3}{\overset{n+1}{}}}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(v_i^{\prime \prime })}=`$
    $`q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)}+q^n{\displaystyle \underset{j=2}{\overset{n+1}{}}}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(v_j^{\prime \prime })}=\text{(by induction)}`$
    $`=q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)}+q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n1}}(u^{\prime \prime })+n}(1+q+\mathrm{}+q^{n1})=`$
    $`=q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)}+q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)+1}(1+q+\mathrm{}+q^{n1}),`$
    which implies the proof. Together, (a) and (b) prove Equation (16). Now Equation (17) follows from Equation (16) since, in both cases (a) and (b) above, $`\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(v_1)=\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)+n`$.

$`\mathrm{}`$

###### Lemma 6.4

Recall that $`R_n^S=\{1,s_n,\mathrm{},s_ns_{n1}\mathrm{}s_1\}S_{n+1}`$ and let $`wS_n`$ (so $`wS_{n+1}`$, where $`w(n+1)=n+1`$). Then

$$\underset{\tau R_n^S}{}q^{maj_S(w\tau )}=q^{maj_S(w)}(1+q+\mathrm{}+q^n),$$

and

$$\underset{\tau R_n^S}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(w\tau )}=q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(w)}(1+q+\mathrm{}+q^n).$$

Proof. Write $`wS_n`$ as $`w=[w(1),\mathrm{},w(n)](=u`$ in 6.3). Similarly write $`wS_nS_{n+1}`$ as $`w=[w(1),\mathrm{},w(n),n+1](=v_{n+1}`$, in 6.3, where $`y=n+1`$). Thus

$$ws_n=[w(1),\mathrm{},n+1,w(n)](=v_n),$$

$$ws_ns_{n1}=[w(1),\mathrm{},n+1,w(n1),w(n)](=v_{n1}),$$

etc, and the proof follows by the previous lemma. $`\mathrm{}`$

###### Remark 6.5

Let $`\stackrel{~}{R}_n^S=R_n^S\{s_ns_{n1}\mathrm{}s_1\}S_{n+1}`$, and let $`\sigma S_n`$. It follows from Equation (17) that

$$\underset{\tau \stackrel{~}{R}_n^S}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(\sigma \tau )}=q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\sigma )}(1+q+\mathrm{}+q^{n1}).$$

###### Lemma 6.6

For every $`\sigma S_n`$

$$\underset{\tau R_n^S}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(\sigma \tau )}t^{del_S(\sigma \tau )}=q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\sigma )}t^{del_S(\sigma )}(1+q+\mathrm{}+q^{n1}+tq^n).$$

Proof. By Lemma 6.4

$$\{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(\sigma \tau )\tau R_n^S\}=\{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\sigma )+i0in\}.$$

Let $`\eta =s_ns_{n1}\mathrm{}s_1`$ and note that $`\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\sigma )+n=\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(\sigma \eta )`$ (this is the statement “$`\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(v_1)=\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(u)+n`$” in the proof of Lemma 6.3).

Let $`\tau R_n^S`$.

If $`\tau \eta `$ then $`del_S(\sigma \tau )=del_S(\sigma )`$ since both $`\sigma `$ and $`\sigma \tau `$ have the same number of occurrences of $`s_1`$. By a similar reason $`del_S(\sigma \eta )=del_S(\sigma )+1`$. Thus

$`\{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(\sigma \tau )del_S(\sigma \tau )\tau R_n^S\}=`$
$`\{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(\sigma \tau )del_S(\sigma \tau )\tau R_n^S,\tau \eta \}\{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(\sigma \eta )del_S(\sigma \eta )\}=`$
$`\{(\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\sigma )+i)del_S(\sigma )0in1\}\{(\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\sigma )+n)(del_S(\sigma )+1)\}`$
(disjoint unions with no repetitions in the sets) which translates to

$$\underset{\tau R_n^S}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n+1}}(\sigma \tau )}t^{del_S(\sigma \tau )}=q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\sigma )}t^{del_S(\sigma )}(1+q+\mathrm{}+q^{n1}+tq^n).$$

$`\mathrm{}`$

###### Proposition 6.7

For all $`n`$

$$\underset{\sigma S_n}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\sigma )}t^{del_S(\sigma )}=(1+tq)(1+q+tq^2)\mathrm{}(1+q+\mathrm{}+q^{n2}+tq^{n1}).$$

Proof. Follows from Lemma 6.6 by induction on $`n`$, since

$$S_{n+1}=_{\tau R_n^S}S_n\tau .$$

$`\mathrm{}`$
The proof of Theorem 6.1.
Part (1) clearly follows by comparing part 1 of Proposition 5.7 with Proposition 6.7.
Part (2) follows from part (1) by Proposition 5.6. $`\mathrm{}`$

## 7 Additional Properties of the Delent Number

We show first that $`del_S(w)`$ is the number of left-to-right minima of $`w`$.

###### Definition 7.1

Let $`wS_n`$, then $`j`$ is a l.t.r.min (left-to-right minimum) of $`w`$ if $`w(i)>w(j)`$ for all $`1i<j`$. Write $`w=[b_1,\mathrm{},b_n]`$, then $`i=1`$ is a l.t.r.min and so is $`i`$ such that $`b_i=1`$. We slightly modify the definition, so that the identity $`e=[1,\mathrm{},n]`$ has no l.t.r.min. This can be done in one of the following two ways.
Either:
1. Do not count $`i=1`$ as a l.t.r.min (which is Definition 7.1.1 of l.t.r.min),
or:
2. Do not count $`i`$ such that $`b_i=1`$ as a l.t.r.min (which is Definition 7.1.2 of l.t.r.min).
3. Define $`Del_S(w)`$ as the l.t.r.min according to Definition 7.1.1:

$$Del_S(w):=\{1<in|j<iw(i)<w(j)\}.$$

For example let $`w=[3,2,7,8,4,6,1,5]`$, then $`\{2,7\}`$ are the l.t.r.min according to 7.1.1, and $`\{1,2\}`$ according to 7.1.2.
With either definition we have

###### Proposition 7.2

Let $`wS_n`$, then $`del_S(w)`$ equals the number of l.t.r.min of $`w^1`$ according to either Definition 7.1.1 or 7.1.2. Since by Lemma 3.6 $`del_S(w)=del_S(w^1)`$, this also equals the number of l.t.r.min of $`w`$. In particular,

$$Del_S(w)=del_S(w)=del_S(w^1).$$

Proof. By induction on $`n2`$. First, $`S_2=\{1,s_1\}`$ and $`s_1=[2,1]`$ has one l.t.r.min - according to either 7.1.1 or 7.1.2. Proceed now with the inductive step, which is essentially the same for both definitions. Let $`w=w_1\mathrm{}w_{n1}`$ be the canonical presentation of $`w`$, let $`\sigma =w_1\mathrm{}w_{n2}`$ (so $`\sigma S_{n1}`$) and assume true for $`\sigma `$. Write $`\sigma ^1=[b_1,\mathrm{},b_{n1},n]`$. If $`w_{n1}=1`$, the proof is given by the induction hypothesis. Otherwise $`w_{n1}^1=s_ks_{k+1}\mathrm{}s_{n1}`$ for some $`1kn1`$. Denoting $`s_{[k,n1]}=s_ks_{k+1}\mathrm{}s_{n1}`$ we see that $`w^1=s_{[k,n1]}\sigma ^1`$. Comparing $`\sigma ^1`$ with $`w^1=s_{[k,n1]}\sigma ^1`$, we see that

1. the (position with) $`n`$ in $`\sigma ^1`$ is replaced in $`w^1`$ by $`k`$;
2. each $`j`$ in $`\sigma ^1`$, $`kjn1`$, is replaced by $`j+1`$ in $`w^1`$;
3. each $`j`$, $`1jk1`$ is unchanged.

Thus $`\sigma ^1=[b_1,\mathrm{},b_{n1},n]`$, $`w^1=[c_1,\mathrm{},c_{n1},k]`$, and the two tuples $`(b_1,\mathrm{},b_{n1})`$ and $`(c_1,\mathrm{},c_{n1})`$ are order-isomorphic. This implies that if $`k>1`$ then $`\sigma ^1`$ and $`w^1`$ have the same left-to-right minima. Let $`k=1`$ and adopt Definition 7.1.1 first, then $`w^1`$ has $`i=n`$ as an additional left-to-right minimum, which completes the proof in that case. In the case of Definition 7.1.2, compare $`k=2`$ with $`k=1`$ to deduce that $`i`$ such that $`c_i=2`$ is an additional l.t.r.min, and the proof follows. $`\mathrm{}`$

###### Remark 7.3

The above proof implies a bit more: Note that the above case $`k=1`$ is equivalent to both $`nDel_S(w^1)`$ and to $`ϵ_{S,n1}(w)=1`$, where $`ϵ_{S,i}(w)`$ are given by Definition 5.9. By induction on $`n`$, the above proof implies that $`Del_S(w^1)=\{i+1ϵ_{S,i}(w)=1\}`$. Let now $`D[n1]`$ and let $`\pi S_n`$. The condition $`D=Del_S(\pi ^1)`$ implies that $`D=\{i+1ϵ_{S,i}(\pi )=1\}`$; this uniquely determines $`\overline{ϵ}_S(\pi )`$, and hence determines a unique value $`t^{ϵ_D}:=t^{\overline{ϵ}_S(\pi )}`$: if $`DH`$ then $`t^{ϵ_D}t^{ϵ_H}`$. We shall apply this observation in the proof of Theorem 9.1.

Each of the two definitions of l.t.r.min can be extended as follows.

###### Definition 7.4

Let $`w=[b_1,\mathrm{},b_n]S_n`$. Then $`1in`$ is an a.l.t.r.min (almost-left-to-right minimum) if, first of all, there is at most one $`b_j`$ smaller than $`b_i`$ and left of $`b_i`$: card$`\{1jib_j<b_i\}1`$.
The second condition is one of the following:
Either
1. Do not count $`i=1`$ and $`i=2`$ as a.l.t.r.min (which is Definition 7.4.1 of a.l.t.r.min),
or:
2. Do not count $`i`$ such that $`b_i=1,2`$ as an a.l.t.r.min (which is Definition 7.4.2 of a.l.t.r.min).
3. For $`wA_{n+1}`$ define $`Del_A(w)`$ to be the set of a.l.t.r.min of $`w`$ according to Definition 7.4.1.

###### Remark 7.5

1. Without the above restrictions 1 and 2 in Definition 7.4, $`i`$ such that $`b_i\{1,2\}`$ is an a.l.t.r.min; similarly, if $`i\{1,2\}`$ then $`i`$ is an a.l.t.r.min.
2. If $`b_i=1`$ and $`b_j=2`$ are interchanged in $`w=[b_1,\mathrm{},b_n]`$, this does not change the set of a.l.t.r.min indices. Also, if $`b_1`$ and $`b_2`$ are interchanged this would not change the set of a.l.t.r.min indices. Thus with either definition 7.4.1 or 7.4.2, $`s_1w`$ and $`ws_1`$ have the same a.l.t.r.min as $`w`$ itself.

###### Proposition 7.6

Let $`wS_n`$, then the number of occurrences of $`s_2`$ in (the canonical presentation of) $`w`$ equals the number of a.l.t.r.min of $`w^1`$ according to either Definition 7.4.1 or 7.4.2. Lemma 3.6 implies that this is also the number of a.l.t.r.min of $`w`$.

Proof. By induction on $`n`$. This is easily verified for $`n=2`$, and we proceed with the inductive step.
Let $`w=w_1\mathrm{}w_{n1}`$ be the canonical presentation of $`w`$, and denote $`\sigma =w_1\mathrm{}w_{n2}`$, so that $`w^1=w_{n1}^1\sigma ^1`$. If $`w_{n1}=1`$ we are done by induction. Otherwise, by the S-procedure, $`w_{n1}=s_{n1}\mathrm{}s_kx`$ where $`k2`$ and $`x\{1,s_1\}`$.
Write $`w^1=xs_k\mathrm{}s_{n1}\sigma ^1=xs_{[k,n1]}\sigma ^1`$. By Remark 7.5, $`s_{[k,n1]}\sigma ^1`$ and $`xs_{[k,n1]}\sigma ^1`$ have the same number of a.l.t.r.min. Therefore it suffices to show:

1. If $`k3`$ then $`\sigma ^1`$ has equal number of a.l.t.r.min as $`s_{[k,n1]}\sigma ^1`$.
2. If $`k=2`$, $`s_{[2,n1]}\sigma ^1`$ has one more a.l.t.r.min than $`\sigma ^1`$.

Let $`\sigma ^1=[b_1,\mathrm{},b_{n1},n]`$, then $`s_{[k,n1]}\sigma ^1=[c_1,\mathrm{},c_{n1},k]`$, and as in the proof of 7.2, $`(b_1,\mathrm{},b_{n1})`$ and $`(c_1,\mathrm{},c_{n1})`$ are order isomorphic . If $`k3`$, the last position (with $`k`$) is not an a.l.t.r.min, while if $`k=2`$, it is an additional a.l.t.r.min, and this implies the proof in the case of 7.4.1. In case of 7.4.2, compare $`k=3`$ with $`k=2`$: a $`2`$ is changed into a $`3`$, which is an additional a.l.t.r.min. $`\mathrm{}`$

By essentially the same argument we have

###### Proposition 7.7

Let $`vA_{n+1}`$ then, with either Definition 7.4.1 or 7.4.2 of a.l.t.r.min, $`del_A(v)`$ equals the number of a.l.t.r.min of $`v^1`$. In particular $`Del_A(v)=del_A(v)=del_A(v^1)`$.

Proof. Again, by induction on $`n`$. This is easily verified for $`n+1=3`$, so proceed with the inductive step.
Let $`v=v_1\mathrm{}v_{n1}`$ be the A- canonical presentation of $`v`$, and denote $`\sigma =v_1\mathrm{}v_{n2}`$, so that $`v^1=v_{n1}^1\sigma ^1`$. If $`v_{n1}=1`$ we are done by induction. Otherwise, by the A-procedure, $`v_{n1}=xs_n\mathrm{}s_ky`$ where $`k2`$ and $`x,y\{1,s_1\}`$; moreover, $`k=2`$ if and only if either $`a_1`$ or $`a_1^1`$ occurs in $`v_{n1}`$.
Write $`v^1=ys_k\mathrm{}s_nx\sigma ^1=ys_{[k,n]}x\sigma ^1`$, and proceed as in the proof of 7.6, applying 7.5.2. $`\mathrm{}`$

###### Remark 7.8

Given $`wS_n`$, one can define a.a.l.t.r.min, a.a.a.l.t.r.min, etc, then prove the corresponding propositions, analogue of Proposition 7.6. For example, we have

###### Definition 7.9

Let $`w=[b_1,\mathrm{},b_n]S_n`$. Then $`1in`$ is an a.a.l.t.r.min (almost-almost-left-to-right minimum) if card$`\{1jib_j<b_i\}2`$ and
1. $`i1,\mathrm{\hspace{0.17em}2},\mathrm{\hspace{0.17em}3}`$ (which is Definition 7.9.1 of a.a.l.t.r.min),
or
2. $`b_i1,\mathrm{\hspace{0.17em}2},\mathrm{\hspace{0.17em}3}`$. (which is Definition 7.9.2 of a.a.l.t.r.min).

One can then prove that, with either definition of a.a.l.t.r.min, the number of a.a.l.t.r.min of $`wS_n`$ equals the number of occurrences of $`s_3`$ in $`w`$. Similarly for the occurrences of the other $`s_i`$’s.

Similar to Proposition 5.8, we define $`w_S(n,\mathrm{},k)`$ to be the number of $`S`$ canonical words in $`S_n`$ with $`\mathrm{}`$ occurrences of $`s_k`$ (define $`w_A(n+1,\mathrm{},k)`$ similarly), and we have

###### Proposition 7.10

Let $`kn1`$, then

$$\underset{\mathrm{}=0}{\overset{nk}{}}w_S(n,\mathrm{},k)t^{\mathrm{}}=k!(kt+1)(kt+2)\mathrm{}(kt+nk),$$

hence $`w_S(n,\mathrm{},k)=k!k^{\mathrm{}}c(nk+1,\mathrm{}+1)`$, and similarly for $`w_A(n+1,\mathrm{},k)`$.

Proof \- is omitted.

## 8 Lemmas on Shuffles

In this section we prove lemmas, which will be used in the next section to prove the main theorem.

### 8.1 Equi-distribution on Shuffles

The following result follows from Theorem 2.6.

###### Proposition 8.1

Let $`i[n1]`$, and let $`\pi S_n`$ with $`\mathrm{𝑠𝑢𝑝𝑝}(\pi )[i]`$. Then

$$\underset{\mathrm{𝐷𝑒𝑠}_S(r^1)\{i\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi r)\mathrm{𝑟𝑚𝑎𝑗}_{S_i}(\pi )}=\underset{\mathrm{𝐷𝑒𝑠}(r^1)\{i\}}{}q^{\mathrm{}_S(\pi r)\mathrm{}_S(\pi )}=\left[\genfrac{}{}{0pt}{}{n}{i}\right]_q.$$

Proof. Let $`\rho _n:=(1,n)(2,n1)\mathrm{}S_n`$ and $`\rho _i:=(1,i)(2,i1)\mathrm{}S_i`$. By (4)

$$\underset{\mathrm{𝐷𝑒𝑠}_S(r^1)\{i\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi r)\mathrm{𝑟𝑚𝑎𝑗}_{S_i}(\pi )}=\underset{\mathrm{𝐷𝑒𝑠}_S(r^1)\{i\}}{}q^{maj_S(\rho _n\pi r\rho _n)maj_S(\rho _i\pi \rho _i)}=$$

$$\underset{\mathrm{𝐷𝑒𝑠}_S(r^1)\{i\}}{}q^{maj_S(\rho _n\pi \rho _n\rho _nr\rho _n)maj_S(\rho _i\pi \rho _i)}=\underset{\mathrm{𝐷𝑒𝑠}_S(\widehat{r}^1)\{ni\}}{}q^{maj_S(\rho _n\pi \rho _n\widehat{r})maj_S(\rho _i\pi \rho _i)}.$$

The last equality follows from (6).

Note that $`\mathrm{𝑠𝑢𝑝𝑝}(\rho _n\pi \rho _n)[ni+1,n]`$ and verify that $`\nu _{ni}^1\rho _n\pi \rho _n\nu _{ni}=\rho _i\pi \rho _i`$, where $`\nu _{ni}:=(1,ni+1)(2,ni+2)\mathrm{}`$. Indeed, let $`ji`$, then $`\nu _{ni}(j)=j+ni`$, hence $`\rho _n\nu _{ni}(j)=\rho _n(j+ni)=n(j+ni)+1=ij+1=\rho _i(j)`$. Similarly, if $`ki`$, also $`\nu _{ni}^1\rho _n(k)=\rho _i(k)`$. This implies the above equality. Now, obviously $`\mathrm{𝑠𝑢𝑝𝑝}(1)[ni]`$ and $`maj_S(1)=0`$. Thus by Garsia-Gessel’s Theorem (Theorem 2.6) (taking $`\pi _1=1`$ and $`\pi _2=\rho _n\pi \rho _n`$) the right-hand-side is equal to

$$\underset{\mathrm{𝐷𝑒𝑠}_S(\widehat{r}^1)\{ni\}}{}q^{maj_S(1\rho _n\pi \rho _n\widehat{r})maj_S(1)maj_S(\nu _{ni}^1\rho _n\pi \rho _n\nu _{ni})}=\left[\genfrac{}{}{0pt}{}{n}{i}\right]_q.$$

The equality

$$\underset{\mathrm{𝐷𝑒𝑠}(r^1)\{i\}}{}q^{\mathrm{}_S(\pi r)\mathrm{}_S(\pi )}=\underset{\mathrm{𝐷𝑒𝑠}(r^1)\{i\}}{}q^{\mathrm{}_S(\pi 1r)\mathrm{}_S(\pi )\mathrm{}_S(1)}=\left[\genfrac{}{}{0pt}{}{n}{i}\right]_q$$

is an immediate consequence of Fact 2.5, combined with (3).

$`\mathrm{}`$

###### Note 8.2

Let $`r`$ be an $`\{i\}`$-shuffle and let $`supp(\pi )[i]`$ as above. If $`r(1)1`$, necessarily $`r(1)=i+1`$, hence also $`\pi r(1)=i+1`$. It follows that

$$\pi r(1)\{\pi (1),i+1\}.$$

The next lemma requires some preparations.

Fix $`1in1`$ and define $`g_i:S_nS_{n1}`$ as follows: Let
$`\sigma =[a_1,\mathrm{},a_n]S_n`$, then $`g_i(\sigma )=[a_1^{},\mathrm{},a_{n1}^{}]`$ is defined as follows: delete $`a_j=i+1`$, leave $`a_k^{}=a_k`$ unchanged if $`a_ki`$, and change $`a_t^{}=a_t1`$ if $`a_ti+2`$. Denote $`g_i(\sigma )=\sigma ^{}`$. For example, let $`\sigma =[5,2,3,6,1,4]`$ and $`i=2`$, then $`g_2(\sigma )=\sigma ^{}=[4,2,5,1,3]`$. Let $`supp(\pi )[i]`$, then $`g_i(\pi )=\pi `$: $`\pi ^{}=\pi `$. Moreover, since $`\pi `$ only permutes $`1,\mathrm{},i`$, the following basic property of $`g_i`$ is rather obvious, since $`supp(\pi )[i]`$:

###### Fact 8.3

1. Let $`\sigma S_n`$, then $`\pi (g_i\sigma )=g_i(\pi \sigma )`$, namely, $`(\pi \sigma )^{}=\pi ^{}\sigma ^{}=\pi \sigma ^{}`$.

2. $`g_i`$ is a bijection between the $`\{i\}`$-shuffles $`rS_n`$ satisfying $`r(1)=i+1`$, and all the $`\{i\}`$-shuffles $`r^{}S_{n1}`$:

$$g_i:\{rS_nDes_S(r^1)\{i\},r(1)=i+1\}\{r^{}S_{n1}Des_S(r^1)\{i\}\}$$

is a bijection.

We need

###### Lemma 8.4

Let $`1in2`$, $`supp(\pi )[i]`$ and $`r(1)=i+1`$. Also let $`g_i(\pi )=\pi ^{}`$ and $`g_i(r)=r^{}`$.

1. If $`r(2)=i+2`$ then $`\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi r)=\mathrm{𝑟𝑚𝑎𝑗}_{S_{n1}}(\pi ^{}r^{})`$.
2. If $`r(2)=1`$ then $`\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi r)=n1+\mathrm{𝑟𝑚𝑎𝑗}_{S_{n1}}(\pi ^{}r^{})`$.

Proof. By Note 8.2, $`\pi r=[i+1,a_2,\mathrm{},a_n]`$ then, applying $`g_i`$, we have $`\pi ^{}r^{}=[a_2^{},\mathrm{},a_n^{}]`$, and it is easy to check that for all $`2kn1`$, $`a_k>a_{k+1}`$ if and only if $`a_k^{}>a_{k+1}^{}`$. Thus, for $`2kn1`$, $`kDes(\pi r)`$ if and only if $`k1Des(\pi ^{}r^{})`$; note also that such $`k`$ contributes $`nk=(n1)(k1)`$ to both $`\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi r)`$ and to $`\mathrm{𝑟𝑚𝑎𝑗}_{S_{n1}}(\pi ^{}r^{})`$.

1. If $`r(2)=i+2`$ then $`a_2=\pi r(2)=i+2`$, hence $`1Des(\pi r)`$, and the descents of $`\pi r`$ occur only for (some) $`2kn1`$, and the above argument implies the proof.
2. If $`r(2)=1`$ then $`a_2=\pi r(2)=\pi (1)<i+1`$, hence $`1`$ is a descent of $`\pi r`$, contributing $`n1`$ to $`\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi r)`$, and again, the above argument completes the proof. $`\mathrm{}`$

###### Lemma 8.5

With the notations of Proposition 8.1

$$\underset{\mathrm{𝐷𝑒𝑠}_S(r^1)\{i\}\text{ and }\pi r(1)=i+1}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi r)\mathrm{𝑟𝑚𝑎𝑗}_{S_i}(\pi )}=q^i\left[\genfrac{}{}{0pt}{}{n1}{i}\right]_q.$$
$`(1)`$
and

$$\underset{\mathrm{𝐷𝑒𝑠}_S(r^1)\{i\}\text{ and }\pi r(1)=\pi (1)}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi r)\mathrm{𝑟𝑚𝑎𝑗}_{S_i}(\pi )}=\left[\genfrac{}{}{0pt}{}{n1}{i1}\right]_q.$$
$`(2)`$
Proof. By induction on $`ni`$. For $`ni=1`$, the $`\{n1\}`$-shuffles are $`[1,\mathrm{},j1,n,j,\mathrm{},n1]=[1,\mathrm{},n]s_{n1}s_{n2}\mathrm{}s_j`$, $`\mathrm{\hspace{0.33em}1}jn1`$. Thus the summation in (2) is over $`rR_{n1}^S\{s_{n1}s_{n2}\mathrm{}s_1\}`$ and Equation (2) follows from Remark 6.5 (with $`n1`$ replacing $`n`$). Now,

$$sum(1)+sum(2)=\underset{\mathrm{𝐷𝑒𝑠}_S(r^1)\{n1\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi r)\mathrm{𝑟𝑚𝑎𝑗}_{S_{n1}}(\pi )},$$

Hence, by Proposition 8.1

$$sum(1)+sum(2)=\left[\genfrac{}{}{0pt}{}{n}{n1}\right]_q,$$

so

$$sum(1)=\left[\genfrac{}{}{0pt}{}{n}{n1}\right]_q\left[\genfrac{}{}{0pt}{}{n1}{n2}\right]_q=q^{n1},$$

which verifies (1) in that case.

Let now $`ni2`$ and assume the lemma holds for $`n1i`$.

Since $`Des(r^1)\{i\}`$ and $`r(1)=i+1`$, either $`r(2)=i+2`$ (then $`\pi r(2)=i+2`$), or $`r(2)=1`$ (then $`\pi r(2)=\pi (1)`$). Thus, the sum in (1) equals $`sum[r(2)=i+2]+sum[r(2)=1]`$. Apply $`g_i`$ to the permutations in these sums, and apply Lemma 8.4.1 and Fact 8.3; then, by induction on $`n`$,

$$sum[r(2)=i+2]=\underset{\mathrm{𝐷𝑒𝑠}_S(r^1)\{i\}\text{ and }\pi ^{}r^{}(1)=i+1}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n1}}(\pi ^{}r^{})\mathrm{𝑟𝑚𝑎𝑗}_{S_i}(\pi ^{})}$$

$$=q^i\left[\genfrac{}{}{0pt}{}{n2}{i}\right]_q.$$

Similarly, by Lemma 8.4.2 and Fact 8.3,

$$sum[r(2)=1]=\underset{\mathrm{𝐷𝑒𝑠}_S(r^1)\{i\}\text{ and }\pi ^{}r^{}(1)=\pi ^{}(1)}{}q^{n1+\mathrm{𝑟𝑚𝑎𝑗}_{S_{n1}}(\pi ^{}r^{})\mathrm{𝑟𝑚𝑎𝑗}_{S_i}(\pi ^{})}$$

$$=q^{n1}\left[\genfrac{}{}{0pt}{}{n2}{i1}\right]_q.$$

Adding the last two sums, we conclude:

$$\underset{\mathrm{𝐷𝑒𝑠}_S(r^1)\{i\}\text{ and }\pi r(1)=i+1}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_{n1}}(\pi r)\mathrm{𝑟𝑚𝑎𝑗}_{S_i}(\pi )}=q^i\left[\genfrac{}{}{0pt}{}{n2}{i}\right]_q+q^{n1}\left[\genfrac{}{}{0pt}{}{n2}{i1}\right]_q=$$

$$=q^i(\left[\genfrac{}{}{0pt}{}{n2}{i}\right]_q+q^{n1i}\left[\genfrac{}{}{0pt}{}{n2}{i1}\right]_q)=q^i\left[\genfrac{}{}{0pt}{}{n1}{i}\right]_q.$$

is an immediate consequence of Proposition 8.1 and part (1), since

$$\left[\genfrac{}{}{0pt}{}{n}{i}\right]_q\left[\genfrac{}{}{0pt}{}{n1}{i1}\right]_q=q^i\left[\genfrac{}{}{0pt}{}{n1}{i}\right]_q.$$

$`\mathrm{}`$

We have an analogous lemma for length.

###### Lemma 8.6

With the notation of Proposition 8.1

$$\underset{\mathrm{𝐷𝑒𝑠}_S(r^1)\{i\}\text{ and }\pi r(1)=i+1}{}q^{\mathrm{}_S(\pi r)\mathrm{}_S(\pi )}=q^i\left[\genfrac{}{}{0pt}{}{n1}{i}\right]_q.$$
$`(1)`$
and

$$\underset{\mathrm{𝐷𝑒𝑠}_S(r^1)\{i\}\text{ and }\pi r(1)=\pi (1)}{}q^{\mathrm{}_S(\pi r)\mathrm{}_S(\pi )}=\left[\genfrac{}{}{0pt}{}{n1}{i1}\right]_q.$$
$`(2)`$
Proof. The case $`ni=0`$ is obvious (the sum in (1) is empty while in (2), $`r=1`$), so assume $`in1`$. Recall that in general, $`\mathrm{}_S(\sigma )`$ equals the number $`inv_S(\sigma )`$ of inversions of $`\sigma `$.

We prove (1) first, so let $`\pi r(1)=i+1`$. As in Lemma 8.4, write

$$\pi r=[i+1,a_2,\mathrm{},a_n]\text{and}g_i(\pi r)=\pi ^{}r^{}=[a_2^{},\mathrm{},a_n^{}],$$

and compare their inversions. Clearly, $`i+1`$ contributes $`i`$ inversions to $`inv_S(\pi r)`$. Also, as in the proof of Lemma 8.4, there is a bijection between the inversions among $`\{a_2,\mathrm{},a_n\}`$ and those among $`\{a_2^{},\mathrm{},a_n^{}\}`$. Thus $`inv_S(\pi r)=i+inv_S(\pi ^{}r^{})`$. Also, since $`supp(\pi )[i]`$ , $`inv_S(\pi )=inv_S(\pi ^{})`$. Induction, Fact 8.3 and Proposition 8.1 imply the proof of (1). Now, by Proposition 8.1, (1) implies the proof of (2). $`\mathrm{}`$

### 8.2 Canonical Presentation of Shuffles

###### Observation 8.7

Let $`1i<n`$. Every $`\{i\}`$-shuffle has a unique canonical presentation of the form $`w_iw_{i+1}\mathrm{}w_{n1}`$, where $`\mathrm{}(w_j)\mathrm{}(w_{j+1})`$ for all $`ji`$.

Proof. Apply the ‘S-Procedure’ that follows Theorem 3.1. Note that after pulling $`n,n1,\mathrm{},i+1`$ to the right, an $`\{i\}`$-shuffle is transformed into the identity permutation. $`\mathrm{}`$
Let $`\overline{ϵ}=(ϵ_1,\mathrm{},ϵ_{n1})`$, then denote $`t^{\overline{ϵ}}=t_1^{ϵ_1}\mathrm{}t_{n1}^{ϵ_{n1}}`$.

###### Corollary 8.8

Recall Definition 5.9. For an $`\{i\}`$-shuffle $`w`$,

$$\mathrm{𝑑𝑒𝑙}_S(w)=\{\begin{array}{cc}1,\hfill & \text{ if }w(1)=i+1\text{;}\hfill \\ 0,\hfill & \text{ otherwise, }\hfill \end{array}$$

and therefore

$$t^{\overline{ϵ}_S(w)}=t_i^{del_S(w)}=\{\begin{array}{cc}t_i,\hfill & \text{ if }w(1)=i+1\text{;}\hfill \\ 1,\hfill & \text{ otherwise }\hfill \end{array}$$

Proof. Write $`w=w_iw_{i+1}\mathrm{}w_{n1}`$ (canonical presentation) with $`\mathrm{}_S(w_i)\mathrm{}\mathrm{}_S(w_{n1})`$, then $`ϵ_{S,j}(w)=0`$ for $`j>i`$. Thus $`del_S(w)`$ is either 1 or 0, and is 1 exactly when $`w_i=s_i\mathrm{}s_1`$, in which case $`w(1)=i+1`$. $`\mathrm{}`$

###### Remark 8.9

Let $`r,\pi S_n`$, $`r`$ an $`\{i\}`$-shuffle and $`supp(\pi )[i]`$. Then the corresponding canonical presentations are: $`\pi =w_1\mathrm{}w_i,`$ $`r=w_{i+1}\mathrm{}w_{n1}`$, hence also $`\pi r=w_1\mathrm{}w_{n1}`$ is canonical presentation. In particular, $`\overline{ϵ}_S(\pi r)=\overline{ϵ}_S(\pi )+\overline{ϵ}_S(r)`$.

We generalize: Let $`B=\{i_1,i_2\}`$ and let $`wS_n`$ be a $`B`$-shuffle. Then $`w`$ shuffles the three subsets $`\{1,\mathrm{},i_1\}`$, $`\{i_1+1,\mathrm{},i_2\}`$ and $`\{i_2+1,\mathrm{},n\}`$. Clearly $`w`$ has a unique presentation as a product $`w=\tau _1\tau _2`$ where $`\tau _2S_n`$ shuffles $`\{1,\mathrm{},i_2\}`$ with $`\{i_2+1,\mathrm{},n\}`$, and $`\tau _1S_{i_2}`$ shuffles $`\{1,\mathrm{},i_1\}`$ with $`\{i_1+1,\mathrm{},i_2\}`$. By Observation 8.7, $`\tau _1=w_{i_1}w_{i_1+1}\mathrm{}w_{i_21}`$ and $`\tau _2=w_{i_2}w_{i_2+1}\mathrm{}w_{n1}`$, where each $`w_jR_j^S`$. Thus

$$w=w_{i_1}\mathrm{}w_{i_21}w_{i_2}\mathrm{}w_{n1}$$

is the $`S`$ canonical presentation of $`w`$,

$$del_S(w)=del_S(\tau _1)+del_S(\tau _2)\text{and}t^{\overline{ϵ}_S(w)}=t_{i_1}^{del_S(\tau _1)}t_{i_2}^{del_S(\tau _2)}.$$

This easily generalizes to an arbitrary $`B=\{i_1,\mathrm{},i_k\}\{1,\mathrm{},n1\}`$, which proves the following proposition.

###### Proposition 8.10

Let $`B=\{i_1,\mathrm{},i_k\}\{1,\mathrm{},n1\}`$ and let $`i_{k+1}:=n`$. Every $`B`$-shuffle $`\pi S_n`$ has a unique presentation

$$\pi =\tau _1\mathrm{}\tau _k$$

where $`\tau _j`$ is an $`\{i_j\}`$-shuffle in $`S_{i_{j+1}}`$ (for $`1jk`$). Moreover,

$$\mathrm{𝑑𝑒𝑙}_S(\pi )=\underset{j=1}{\overset{k}{}}\mathrm{𝑑𝑒𝑙}_S(\tau _j)\text{and}t^{\overline{ϵ}_S(\pi )}=t_{i_1}^{del_S(\tau _1)}\mathrm{}t_{i_k}^{del_S(\tau _k)}.$$

## 9 The Main Theorem

Recall the definitions of the $`A`$-descent set $`\mathrm{𝐷𝑒𝑠}_A`$ and the $`A`$-descent number $`\mathrm{𝑑𝑒𝑠}_A`$ (Definition 1.5). Let $`B[n1]`$ and $`\pi S_n`$. Recall from Fact 2.4 that $`Des_S(\pi ^1)B`$ if and only if $`\pi `$ is a $`B`$-shuffle.

The following is our main theorem, which we now prove.

###### Theorem 9.1

For every subsets $`D_1[n1]`$ and $`D_2[n1]`$

$$\underset{\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)D_1,\mathrm{𝐷𝑒𝑙}_S(\pi ^1)D_2\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi )}=$$
$`(1)`$
$$\underset{\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)D_1,\mathrm{𝐷𝑒𝑙}_S(\pi ^1)D_2\}}{}q^{\mathrm{}_S(\pi )},$$

and

$$\underset{\{\sigma A_{n+1}|\mathrm{𝐷𝑒𝑠}_A(\sigma ^1)D_1,\mathrm{𝐷𝑒𝑙}_A(\sigma ^1)D_2\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{A_{n+1}}(\sigma )}=$$
$`(2)`$
$$\underset{\{\sigma A_{n+1}|\mathrm{𝐷𝑒𝑠}_A(\sigma ^1)D_1,\mathrm{𝐷𝑒𝑙}_A(\sigma ^1)D_2\}}{}q^{\mathrm{}_A(\sigma )}.$$

An immediate consequence of Theorem 9.1 is

###### Corollary 9.2

$$\underset{\pi S_n}{}q_1^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi )}q_2^{\mathrm{𝑑𝑒𝑠}_S(\pi ^1)}q_3^{\mathrm{𝑑𝑒𝑙}_S(\pi ^1)}=\underset{\pi S_n}{}q_1^{\mathrm{}_S(\pi )}q_2^{\mathrm{𝑑𝑒𝑠}_S(\pi ^1)}q_3^{\mathrm{𝑑𝑒𝑙}_S(\pi ^1)}.$$
$`(1)`$
$$\underset{\sigma A_n}{}q_1^{\mathrm{𝑟𝑚𝑎𝑗}_{A_{n+1}}(\sigma )}q_2^{\mathrm{𝑑𝑒𝑠}_A(\sigma ^1)}q_3^{\mathrm{𝑑𝑒𝑙}_A(\sigma ^1)}=\underset{\sigma A_n}{}q_1^{\mathrm{}_A(\sigma )}q_2^{\mathrm{𝑑𝑒𝑠}_A(\sigma ^1)}q_3^{\mathrm{𝑑𝑒𝑙}_A(\sigma ^1)}.$$
$`(2)`$
Note that in Corollary 9.2(1) both definitions 7.1.1 and 7.1.2 for calculating $`\mathrm{𝑑𝑒𝑙}_S`$ could be used. This follows from Proposition 7.2. Similarly, in Corollary 9.2(2) both definitions 7.4.1 and 7.4.2 for calculating $`\mathrm{𝑑𝑒𝑙}_A`$ could be used (by Proposition 7.7).

### 9.1 A Lemma

###### Lemma 9.3

Let $`i[n]`$, and let $`\sigma `$ be a permutation in $`S_n`$, such that $`\mathrm{𝑠𝑢𝑝𝑝}(\sigma )[i]`$. Then

$$\underset{\mathrm{𝐷𝑒𝑠}(r^1)\{i\}}{}q^{\mathrm{}_S(\sigma r)}t^{\overline{ϵ}_S(\sigma r)}=q^{\mathrm{}_S(\sigma )}t^{\overline{ϵ}_S(\sigma )}\left(\left[\genfrac{}{}{0pt}{}{n1}{i1}\right]_q+t_iq^i\left[\genfrac{}{}{0pt}{}{n1}{i}\right]_q\right)$$
$`(1)`$
and

$$\underset{\mathrm{𝐷𝑒𝑠}(r^1)\{i\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\sigma r)}t^{\overline{ϵ}_S(\sigma r)}=q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_i}(\sigma )}t^{\overline{ϵ}_S(\sigma )}\left(\left[\genfrac{}{}{0pt}{}{n1}{i1}\right]_q+t_iq^i\left[\genfrac{}{}{0pt}{}{n1}{i}\right]_q\right).$$
$`(2)`$
Proof. By Definition 5.9 and Remark 8.9

$$t^{\overline{ϵ}_S(\sigma r)}=t^{\overline{ϵ}_S(\sigma )+\overline{ϵ}_S(r)},$$

and by Corollary 8.8

$$t^{\overline{ϵ}_S(r)}=\{\begin{array}{cc}t_i,\hfill & \text{ if }r(1)=i+1\text{;}\hfill \\ 1,\hfill & \text{ otherwise }\hfill \end{array}$$

Noting that $`r(1)=i+1`$ if and only if $`\sigma r(1)=i+1`$, and recalling that $`\sigma r(1)\{\sigma (1),i+1\}`$, we obtain

$$t^{\overline{ϵ}_S(\sigma r)}=\{\begin{array}{cc}t^{\overline{ϵ}_S(\sigma )}t_i,\hfill & \text{ if }\sigma r(1)=i+1\text{;}\hfill \\ t^{\overline{ϵ}_S(\sigma )},\hfill & \text{ if }\sigma r(1)=\sigma (1)\hfill \end{array}$$

Combining this with Lemmas 8.5 and 8.6 gives the desired result. For example, regarding length,

$$\underset{\mathrm{𝐷𝑒𝑠}(r^1)\{i\}}{}q^{\mathrm{}_S(\sigma r)}t^{\overline{ϵ}_S(\sigma r)}=$$

$$=\underset{\mathrm{𝐷𝑒𝑠}(r^1)\{i\}\text{ and }\sigma r(1)=\sigma (1)}{}q^{\mathrm{}_S(\sigma r)}t^{\overline{ϵ}_S(\sigma r)}+\underset{\mathrm{𝐷𝑒𝑠}(r^1)\{i\}\text{ and }\sigma r(1)=i+1}{}q^{\mathrm{}_S(\sigma r)}t^{\overline{ϵ}_S(\sigma r)}=$$

$$=q^{\mathrm{}_S(\sigma )}t^{\overline{ϵ}_S(\sigma )}\left(\left[\genfrac{}{}{0pt}{}{n1}{i1}\right]_q+t_iq^i\left[\genfrac{}{}{0pt}{}{n1}{i}\right]_q\right).$$

This proves part (1). A similar argument proves (2).

$`\mathrm{}`$

### 9.2 Proof of Main Theorem

Proof of Theorem 9.1(1).

By the principle of inclusion and exclusion, we may replace $`\mathrm{𝐷𝑒𝑙}_S(\pi ^1)D_2`$ by $`\mathrm{𝐷𝑒𝑙}_S(\pi ^1)=D_2`$ in both hand-sides of Theorem 9.1(1). By Remark 7.3, $`\{\pi S_n|\mathrm{𝐷𝑒𝑙}_S(\pi ^1)=D_2\}`$ (i.e. the set $`D_2`$) determines the unique value $`t^{ϵ_{D_2}}:=t^{\overline{ϵ}_S(\pi )}`$.

Hence, Theorem 9.1(1) is equivalent to the following statement :

For every subset $`B[n1]`$

$$\underset{\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)B\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi )}t^{\overline{ϵ}_S(\pi )}=$$

$$\underset{\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)B\}}{}q^{\mathrm{}_S(\pi )}t^{\overline{ϵ}_S(\pi )},$$

This statement is proved by induction on the cardinality of $`B`$. If $`|B|=1`$ then $`B=\{i\}`$ for some $`i[n1]`$ and Theorem 9.1(1) is given by Lemma 9.3 (with $`\sigma =1`$). Assume that the theorem holds for every $`B[n1]`$ of cardinality less than $`k`$. Let $`B=\{i_1,\mathrm{},i_k\}[n1]`$ and denote $`\overline{B}:=\{i_1,\mathrm{},i_{k1}\}`$. By Proposition 8.10, for every $`\pi S_n`$ with $`\mathrm{𝐷𝑒𝑠}_S(\pi ^1)B`$ there is a unique presentation

$$\pi =\overline{\pi }\tau _k,$$

where $`\overline{\pi }`$ is a $`\overline{B}`$-shuffle in $`S_{i_k}`$ and $`\tau _k`$ is an $`\{i_k\}`$-shuffle in $`S_n`$. Moreover, $`\mathrm{𝐷𝑒𝑠}_S(\pi ^1)B`$ if and only if $`\pi `$ has such a presentation. Hence

$$\underset{\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)B\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\pi )}t^{\overline{ϵ}_S(\pi )}=$$

$$\underset{\{\overline{\pi }S_{i_k},\tau _kS_n|\mathrm{𝐷𝑒𝑠}_S(\overline{\pi }^1)\overline{B},\mathrm{𝐷𝑒𝑠}_S(\tau _k^1)\{i_k\}\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\overline{\pi }\tau _k)}t^{\overline{ϵ}_S(\overline{\pi }\tau _k)}=$$

$$\underset{\{\overline{\pi }S_{i_k}|\mathrm{𝐷𝑒𝑠}_S(\overline{\pi })\overline{B}\}}{}\underset{\{\tau _kS_n|\mathrm{𝐷𝑒𝑠}_S(\tau _k^1)\{i_k\}\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_n}(\overline{\pi }\tau _k)}t^{\overline{ϵ}_S(\overline{\pi }\tau _k)}.$$

By Lemma 9.3(2) this equals to

$$\underset{\{\overline{\pi }S_{i_k}|\mathrm{𝐷𝑒𝑠}_S(\overline{\pi }^1)\overline{B}\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{S_{i_{k1}}}(\overline{\pi })}t^{\overline{ϵ}_S(\overline{\pi })}\left(\left[\genfrac{}{}{0pt}{}{n1}{i_k1}\right]_q+t_{i_k}q^i\left[\genfrac{}{}{0pt}{}{n1}{i_k}\right]_q\right)$$

which, by induction, equals

$$\underset{\{\overline{\pi }S_{i_k}|\mathrm{𝐷𝑒𝑠}_S(\overline{\pi }^1)\overline{B}\}}{}q^{\mathrm{}_S(\overline{\pi })}t^{\overline{ϵ}_S(\overline{\pi })}\left(\left[\genfrac{}{}{0pt}{}{n1}{i_k1}\right]_q+t_{i_k}q^i\left[\genfrac{}{}{0pt}{}{n1}{i_k}\right]_q\right).$$

Now by a similar argument, this time applying Lemma 9.3(1),

$$\underset{\{\pi S_n|\mathrm{𝐷𝑒𝑠}_S(\pi ^1)B\}}{}q^{\mathrm{}_S(\pi )}t^{\overline{ϵ}_S(\pi )}=$$

$$\underset{\{\overline{\pi }S_{i_k}|\mathrm{𝐷𝑒𝑠}_S(\overline{\pi }^1)\overline{B}\}}{}q^{\mathrm{}_S(\overline{\pi })}t^{\overline{ϵ}_S(\overline{\pi })}\left(\left[\genfrac{}{}{0pt}{}{n1}{i_k1}\right]_q+t_{i_k}q^i\left[\genfrac{}{}{0pt}{}{n1}{i_k}\right]_q\right),$$

and the proof follows. $`\mathrm{}`$

Proof of Theorem 9.1(2). By the principle of inclusion and exclusion and Remark 7.3, Theorem 9.1(2) is equivalent to the following statement :

For every subset $`B[n1]`$

$$\underset{\{\sigma A_{n+1}|\mathrm{𝐷𝑒𝑠}_A(\sigma ^1)B\}}{}q^{\mathrm{𝑟𝑚𝑎𝑗}_{A_{n+1}}(\sigma )}t^{\overline{ϵ}_A(\sigma )}=$$

$$\underset{\{\sigma A_{n+1}|\mathrm{𝐷𝑒𝑠}_A(\sigma ^1)B\}}{}q^{\mathrm{}_A(\sigma )}t^{\overline{ϵ}_A(\sigma )},$$

By Proposition 5.10 this part is reduced to Theorem 9.1(1).

$`\mathrm{}`$

## 10 Appendix

In this section we present another pair of statistics, leading to a different analogue of MacMahon’s Theorem.

For $`1i<n`$ define a map $`h_i:S_nS_n`$ as follows:

$$h_i(\pi ):=\{\begin{array}{cc}s_i\pi ,\hfill & \text{ if }i\mathrm{𝐷𝑒𝑠}_S(\pi ^1)\text{;}\hfill \\ \pi ,\hfill & \text{ if }i\mathrm{𝐷𝑒𝑠}_S(\pi ^1)\text{.}\hfill \end{array}$$

For every permutation $`\pi S_n`$ define

$$\widehat{\mathrm{}}_i(\pi ):=\mathrm{}_S(h_i(\pi )),$$

and

$$\widehat{\mathrm{𝑚𝑎𝑗}}_i(\pi ):=\mathrm{𝑚𝑎𝑗}_S(h_i(\pi )).$$

Then $`\widehat{\mathrm{}}_i`$ and $`\widehat{\mathrm{𝑚𝑎𝑗}}_i`$ are equi-distributed over the even permutations in $`S_n`$ (i.e. over the alternating group $`A_n`$).

###### Theorem 10.1

Let $`n2`$, then

$$\underset{\pi A_n}{}q^{\widehat{\mathrm{}}_i(\pi )}=\underset{\pi A_n}{}q^{\widehat{\mathrm{𝑚𝑎𝑗}}_i(\pi )}=\underset{i=3}{\overset{n}{}}(1+q+\mathrm{}+q^{i1}).$$

Proof. By definition,

$$Image(h_i)=\{\pi S_n|iDes_S(\pi ^1)\}=\{\pi S_n|\pi ^1\text{ is an }[n]\{i\}\text{-shuffle}\}.$$

Also, for each $`\sigma Image(h_i)`$, $`h_i^1(\sigma )=\{\sigma ,s_i\sigma \}`$, and exactly one element in the set $`\{\sigma ,s_i\sigma \}`$ is even.

Thus, by Garsia-Gessel’s Theorem (Theorem 2.6),

$$\underset{\pi A_n}{}q^{\widehat{\mathrm{𝑚𝑎𝑗}}_i(\pi )}=$$

$$\underset{\{\pi S_n|\pi ^1\text{ is an }[n]\{i\}\text{-shuffle}\}}{}q^{\mathrm{𝑚𝑎𝑗}(\pi )}=\left[\genfrac{}{}{0pt}{}{n}{2,1,\mathrm{},1}\right]_q=\underset{i=3}{\overset{n}{}}(1+q+\mathrm{}+q^{i1}),$$

and similarly for $`\widehat{\mathrm{}}_i`$.

$`\mathrm{}`$