Equi-distribution over Descent Classes of the Hyperoctahedral Group

Ron M. Adin^{∗}^{§}  Francesco Brenti^{†}^{§}  Yuval Roichman^{‡}^{§}

submitted: June 9, 2004; revised: August 24, 2005

Abstract

A classical result of MacMahon shows that the length function and the major index are equi-distributed over the symmetric group. Foata and Schützenberger gave a remarkable refinement and proved that these parameters are equi-distributed over inverse descent classes, implying bivariate equi-distribution identities. Type B analogues of these results, refinements and consequences are given in this paper.

1 Introduction

Many combinatorial identities on groups are motivated by the fundamental works of MacMahon [27]. Let S_{n} be the symmetric group acting on 1, …, n. We are interested in a refined enumeration of permutations according to (non-negative, integer valued) combinatorial parameters. Two parameters that have the same generating function are said to be equidistributed. MacMahon [27] has shown, about a hundred years ago, that the inversion number and the major index statistics are equi-distributed on S_{n} (Theorem 2.2 below). In the last three decades MacMahon’s theorem has received far-reaching refinements and generalizations. Bivariate distributions were first studied by Carlitz [13]. Foata [18] gave a bijective proof of MacMahon’s theorem; then Foata and Schützenberger [22] applied this bijection to refine MacMahon’s identity, proving that the inversion number and the major index are equi-distributed over subsets of S_{n} with prescribed descent set of the inverse permutation (Theorem 2.3 below). Garsia and Gessel [23] extended the analysis to multivariate distributions. In particular, they gave an independent proof of the Foata-Schützenberger theorem, relying on an explicit and simple generating function (see Theorem 2.6 below). Further refinements and analogues of the Foata-Schützenberger theorem were later found, involving left-to-right minima and maxima [11] and pattern-avoiding permutations [28, 6]. For a representation theoretic application of Theorem 2.3 see [33].

∗Department of Mathematics and Statistics, Bar-Ilan University, Ramat-Gan 52900, Israel. Email: radin@math.biu.ac.il

†Dipartimento di Matematica, Universitá di Roma “Tor Vergata”, Via della Ricerca Scientifica, 00133 Roma, Italy. Email: brenti@mat.uniroma2.it

‡Department of Mathematics and Statistics, Bar-Ilan University, Ramat-Gan 52900, Israel. Email: yuvalr@math.biu.ac.il

§The research of all authors was partially supported by the EC’s IHRP Programme, within the Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272

Since the length and descent parameters may be defined via the Coxeter structure of the symmetric group, it is very natural to look for analogues of the above theorems in other Coxeter groups. This is a challenging open problem. In this paper we focus on the hyperoctahedral group B_{n}, namely the classical Weyl group of type B. Our goal is to find a type B analogue of the Foata-Schützenberger theorem (Theorem 2.3). To solve this we have to choose an appropriate type B extension of the major index among the many candidates, which were introduced and studied in [14, 15, 16, 29, 30, 39, 21]. It turns out that the flag-major index, which was introduced in [5] and further studied in [1, 3, 24, 4], has the desired property: the flag major index and the length function are equi-distributed on inverse descent classes of B_{n}. In fact, we obtain a slight refinement of this result, involving the “last digit” parameter. This parameter is involved in several closely related identities on S_{n}, see e.g. [6, 4, 28]. Our refinement also implies a MacMahon type theorem for the classical Weyl group of type D, which has recently been proved in [9]. A summary of the results of this paper appeared in [2].

The rest of the paper is organized as follows. Definitions, notation and necessary background are given in Section 2. The main results are listed in Section 3. Proofs of the main theorems are given in Section 4. Section 5 contains open problems, an application to Weyl groups of type D and remarks regarding different versions of the flag major index. Finally, in the appendix (Section 6), we give an alternative proof of our type B analogue of the Foata-Schützenberger theorem.

2 Background and Notation

2.1 Notation

Let P := {1, 2, 3, …}, N := P ∪ {0}, and Z the ring of integers. For n ∈ P let [n] := {1, 2, …, n}, and also [0] := ∅. Given m, n ∈ Z, m ≤ n, let [m, n] := {m, m + 1, …, n}. For n ∈ P denote [±n] := [−n, n] \ {0}. For S ⊂ N write S = {a_{1}, …, a_{r}}_{<} to mean that S = {a_{1}, …, a_{r}} and a_{1} < … < a_{r}. The cardinality of a set A will be denoted by |A|.

For n ∈ N denote

[n]_{q} := \frac{1 − q^{n}}{1 − q};
[n]_{q}! := ∏_{i=1}^{n} [i]_{q}  (n ≥ 1),  [0]_{q}! := 1.

For n_{1}, …, n_{t} ∈ N such that n_{1} + … + n_{t} = n define the q-multinomial coefficient

\left[{n \atop n_{1}, …, n_{t}}\right]_{q} := \frac{[n]_{q}!}{[n_{1}]_{q}! … [n_{t}]_{q}!}

and use a shorter notation for the q-binomial coefficient

\left[{n \atop k}\right]_{q} := \left[{n \atop k, n − k}\right]_{q} (0 ≤ k ≤ n).

Given a statement P we will sometimes find it convenient to let

χ(P) := \{ \begin{matrix}1, & if P is true, \\ 0, & if P is false. \end{matrix}

Given a sequence σ = (a_{1}, …, a_{n}) ∈ Z^{n} we say that a pair (i, j) ∈ [n]×[n] is an inversion of σ if i < j and a_{i} > a_{j}. We say that i ∈ [n − 1] is a descent of σ if a_{i} > a_{i+1}. We denote by inv(σ) (respectively, des(σ)) the number of inversions (respectively, descents) of σ. We also let

maj(σ) := ∑_{{i: a_{i}>a_{i+1}}} i

and call it the major index of σ.

For M = {m_{1}, …, m_{t}}_{<} ⊆ [0, n − 1] denote m_{0} := 0, m_{t+1} := n, and let

\left[{n \atop ΔM}\right]_{q} := \left[{n \atop m_{1} − m_{0}, m_{2} − m_{1}, …, m_{t+1} − m_{t}}\right]_{q}.

Let S_{1}, …, S_{k} be sequences of distinct integers which are pairwise disjoint as sets. A sequence S is a shuffle of S_{1}, …, S_{k} if S is a disjoint union of S_{1}, …, S_{k} (as sets) and the elements of each S_{i} appear in S in the same order as in S_{i}.

2.2 The Symmetric Group

Let S_{n} be the symmetric group on [n]. Recall that S_{n} is a Coxeter group with respect to the set of Coxeter generators S := {s_{i} | 1 ≤ i ≤ n−1}, where s_{i} may be interpreted as the adjacent transposition (i, i + 1).

If π ∈ S_{n} then the classical combinatorial statistics (defined in the previous subsection) of the sequence (π(1), …, π(n)) may also be defined via the Coxeter generators: the inversion number inv(π) is equal to the length ℓ(π) of π with respect to the set of generators S; the descent set of π is

Des(π) := {1 ≤ i < n | π(i) > π(i + 1)} = {1 ≤ i < n | ℓ(π) > ℓ(πs_{i})};

the descent number of π is des(π) := |Des(π)|; and the major index of π is the sum (possibly zero)

maj (π) := ∑_{i∈Des(π)} i.

The inverse descent class in S_{n} corresponding to M ⊆ [n − 1] is the set {π ∈ S_{n} | Des(π^{−1}) = M}. Note the following relation between inverse descent classes and shuffles.

Observation 2.1 Let π ∈ S_{n} and M = {m_{1}, …, m_{t}}_{<} ⊆ [n − 1]. Then: Des(π^{−1}) ⊆ M if and only if (π(1), …, π(n)) is a shuffle of the following increasing sequences:

(1, …, m_{1}),
(m_{1} + 1, …, m_{2}),
⋮
(m_{t} + 1, …, n).

MacMahon’s classical theorem asserts that the length function and the major index are equi-distributed on S_{n}.

Theorem 2.2 (MacMahon’s Theorem [27])

∑_{π∈S_{n}} q^{ℓ(π)} = ∑_{π∈S_{n}} q^{maj (π)} = [n]_{q}!.

Foata [18] gave a bijective proof of this theorem. Foata and Schützenberger [22] applied this bijection to prove the following refinement.

Theorem 2.3 (The Foata-Schützenberger Theorem [22, Theorem 1]) For every subset M ⊆ [n − 1],

∑_{{π∈S_{n} | Des(π^{−1})=M}} q^{ℓ(π)} = ∑_{{π∈S_{n} | Des(π^{−1})=M}} q^{maj (π)}.

This theorem implies

Corollary 2.4

(1)  ∑_{π∈S_{n}} q^{ℓ(π)}t^{des(π^{−1})} = ∑_{π∈S_{n}} q^{maj (π)}t^{des(π^{−1})}.

(2)  ∑_{π∈S_{n}} q^{ℓ(π)}t^{maj (π^{−1})} = ∑_{π∈S_{n}} q^{maj (π)}t^{maj (π^{−1})}.

An alternative proof of Theorem 2.3 may be obtained using the following classical fact [37, Prop. 1.3.17].

Fact 2.5 For any M ⊆ [n − 1],

∑_{\{π∈S_{n} | Des(π^{−1})⊆M\}} q^{inv(π)} = \left[{n \atop ΔM}\right]_{q}.

Garsia and Gessel proved that a similar identity holds for the major index.

Theorem 2.6 [23, Theorem 3.1] For any M ⊆ [n − 1],

∑_{\{π∈S_{n} | Des(π^{−1})⊆M\}} q^{maj(π)} = \left[{n \atop ΔM}\right]_{q}.

Combining this theorem with Fact 2.5 implies Theorem 2.3.

2.3 The Hyperoctahedral Group

We denote by B_{n} the group of all bijections σ of the set [±n] onto itself such that

σ(−a) = −σ(a) (∀a ∈ [±n]),

with composition as the group operation. This group is usually known as the group of “signed permutations” on [n], or as the hyperoctahedral group of rank n. We identify S_{n} as a subgroup of B_{n}, and B_{n} as a subgroup of S_{2n}, in the natural ways.

If σ ∈ B_{n} then write σ = [a_{1}, …, a_{n}] to mean that σ(i) = a_{i} for 1 ≤ i ≤ n, and let

inv(σ) := inv(a_{1}, …, a_{n}),
Des_{A}(σ) := Des(a_{1}, …, a_{n}),
des_{A}(σ) := des(a_{1}, …, a_{n}),
maj_{A}(σ) := maj(a_{1}, …, a_{n}),
Neg(σ) := {i ∈ [n] : a_{i} < 0},
neg(σ) := |Neg(σ)|.

It is well known (see, e.g., [10, Proposition 8.1.3]) that B_{n} is a Coxeter group with respect to the generating set {s_{0}, s_{1}, s_{2}, …, s_{n−1}}, where

s_{0} := [−1, 2, …, n]

and

s_{i} := [1, 2, …, i − 1, i + 1, i, i + 2, …, n] (1 ≤ i < n).

This gives rise to two other natural statistics on B_{n} (similarly definable for any Coxeter group), namely

ℓ_{B}(σ) := min{r ∈ N : σ = s_{i_{1}} … s_{i_{r}} for some i_{1}, …, i_{r} ∈ [0, n − 1]}

(known as the length of σ) and

des_{B}(σ) := |Des_{B}(σ)|,

where the B-descent set Des_{B}(σ) is defined as

Des_{B}(σ) := {i ∈ [0, n − 1] | ℓ_{B}(σs_{i}) < ℓ_{B}(σ)}.

Remark 2.7 Note that for every σ ∈ B_{n}

Des_{A}(σ) = Des_{B}(σ) \ {0}.

There are well known direct combinatorial ways to compute these statistics for σ ∈ B_{n} (see, e.g., [10, Propositions 8.1.1 and 8.1.2] or [12, Proposition 3.1 and Corollary 3.2]), namely

ℓ_{B}(σ) = inv(σ) + ∑_{i∈Neg(σ)} |σ(i)|  (1)

and

des_{B}(σ) = |{i ∈ [0, n − 1] : σ(i) > σ(i + 1)}|,  (2)

where σ(0) := 0. For example, if σ = [−3, 1, −6, 2, −4, −5] ∈ B_{6} then inv(σ) = 9, des_{A}(σ) = 3, maj_{A}(σ) = 11, neg(σ) = 4, ℓ_{B}(σ) = 27, and des_{B}(σ) = 4.

3 Main Results

Definition 3.1 The flag major index of a signed permutation σ ∈ B_{n} is defined by

fmaj(σ) := 2 · maj_{A}(σ) + neg(σ),

where maj_{A}(σ) is the major index of the sequence (σ(1), …, σ(n)) with respect to the order −n < ⋯ < −1 < 1 < ⋯ < n.

The main theorem is

Theorem 3.2 For every subset M ⊆ [0, n − 1] and i ∈ [±n]

∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M, σ(n)=i}} q^{ℓ_{B}(σ)} = ∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M, σ(n)=i}} q^{fmaj (σ)}.

See more details in Theorems 4.2 and 4.3 below. Forgetting σ(n), we have

Theorem 3.3 For every subset M = {m_{1}, …, m_{t}}_{<} ⊆ [0, n − 1],

∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M}} q^{ℓ_{B}(σ)} = ∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M}} q^{fmaj(σ)} =

= \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}).

We deduce a Foata-Schützenberger type theorem for B_{n}.

Theorem 3.4 For every subset M ⊆ [0, n − 1],

∑_{{σ∈B_{n} | Des_{B}(σ^{−1})=M}} q^{ℓ_{B}(σ)} = ∑_{{σ∈B_{n} | Des_{B}(σ^{−1})=M}} q^{fmaj (σ)}.

4 Proofs

Lemma 4.1 Let σ ∈ B_{n} and M = {m_{1}, …, m_{t}}_{<} ⊆ [0, n − 1]. Denote m_{t+1} := n. Then: Des_{B}(σ^{−1}) ⊆ M if and only if there exist (unique) integers r_{1}, …, r_{t} satisfying m_{i} ≤ r_{i} ≤ m_{i+1} (∀i) such that (σ(1), …, σ(n)) is a shuffle of the following increasing sequences:

(1, 2, …, m_{1}),
(−r_{1}, −r_{1} + 1, …, −(m_{1} + 1)),
(r_{1} + 1, r_{1} + 2, …, m_{2}),
⋮
(−r_{t}, −r_{t} + 1, …, −(m_{t} + 1)),
(r_{t} + 1, r_{t} + 2, …, n ( = m_{t+1} )).

Some of these sequences may be empty (if r_{i} = m_{i} or r_{i} = m_{i+1} for some i, or if m_{1} = 0).

Proof. Assume first that 0 ∈ M (i.e., m_{1} = 0). Then

Des_{B}(σ^{−1}) ⊆ M ⟺ Des_{A}(σ^{−1}) ⊆ {m_{2}, …, m_{t}}.

This is equivalent to

σ^{−1}(j) < σ^{−1}(j + 1) (∀j ∈ [n] \ M),

namely,

σ^{−1}(m_{i} + 1) < σ^{−1}(m_{i} + 2) < … < σ^{−1}(m_{i+1}) (1 ≤ i ≤ t).

Defining m_{i} ≤ r_{i} ≤ m_{i+1} such that σ^{−1}(r_{i}) is the last negative value in this sequence, we get the desired conclusion (with an empty sequence (1, …, m_{1})).

If 0 ∉ M (i.e., m_{1} > 0) then we get the same conclusion for the intervals [m_{i} + 1, m_{i+1}] with 1 ≤ i ≤ t, and in addition σ^{−1}(1) > 0 so that

0 < σ^{−1}(1) < σ^{−1}(2) < … < σ^{−1}(m_{1}).

This gives us the desired conclusion (with a nonempty sequence (1, …, m_{1})). □ Theorem 4.2 Let M = {m_{1}, m_{2}, …, m_{t}}_{<} ⊆ [0, n − 1] and i ∈ [±n]. Denote m_{0} := 0 and m_{t+1} := n. Then

∑_{\{σ∈B_{n} | Des_{B}(σ^{−1})⊆M, σ(n)=i\}} q^{fmaj(σ)} = \frac{α_{i}(M)}{q^{n} − q^{−n}} · \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}),

where

α_{i}(M) = \{ \begin{matrix}q^{m_{1}} − q^{−m_{1}}, & if i = m_{1} > 0; \\ q^{−m_{s}} − q^{−m_{s+1}}, & if i = m_{s+1} for s ∈ [t]; \\ q^{m_{s+1}} − q^{m_{s}}, & if i = −(m_{s} + 1) for s ∈ [t]; \\ 0, & otherwise. \end{matrix}

Note that the first case (i = m_{1} > 0) occurs only if 0 ∉ M.

Proof. By induction on n. It is easy to verify the result for n ≤ 2. Assume that n ≥ 3, and that the result holds for n − 1.

We shall use the induction hypothesis by “deleting” the value σ(n) = i from σ ∈ B_{n}. Formally, for i ∈ [±n], define a function ϕ_{i} : [−n, n] → [−(n − 1), n − 1] by

a′ = ϕ_{i}(a) := \{ \begin{matrix}a, & if |a| < |i|; \\ \frac{a}{|a|}(|a| − 1), & if |a| ≥ |i| \end{matrix} (∀a ∈ [−n, n]).

When restricted to [−n, n] \ {0, i, −i} = [±n] \ {i, −i}, ϕ_{i} is a bijection onto [±(n − 1)]. For σ ∈ B_{n} with σ(n) = i, let

τ := [σ(1)′, …, σ(n − 1)′] ∈ B_{n−1}.

Lemma 4.1 (for σ and τ) implies that, for any M = {m_{1}, …, m_{t}}_{<} ⊆ [0, n − 1], the map σ ↦ τ is a bijection from {σ ∈ B_{n} | Des_{B}(σ^{−1}) ⊆ M} onto {τ ∈ B_{n−1} | Des_{B}(τ^{−1}) ⊆ M′}, where M′ := {m′_{1}, …, m′_{t}}_{≤}. Note that we may have m′_{s} = m′_{s+1} (if m_{s} + 1 = i = m_{s+1}), but this will make no difference in the sequel.

Assume that σ(n − 1) = j, so that τ(n − 1) = j′. Then:

fmaj (σ) = fmaj (τ) + 2(n − 1)χ(j > i) + χ(i < 0).

Denote

B_{n}(M, i) := {σ ∈ B_{n} | Des_{B}(σ^{−1}) ⊆ M, σ(n) = i},

and similarly B_{n−1}(M′, j′). Denote also

M_{±} := {m_{1}, …, m_{t+1}} ∪ {−(m_{1} + 1), …, −(m_{t} + 1)}.

By Lemma 4.1, if Des_{B}(σ^{−1}) ⊆ M then σ(n) ∈ M_{±}. Thus the sum in the statement of our theorem is zero whenever i ∉ M_{±}. We shall check the values i ∈ M_{±} case-by-case.

First note that the coefficients α_{i}(M) defined in the statement of the theorem satisfy

∑_{j=−n}^{n} α_{j}(M) = q^{n} − q^{−n}  (3)

and

∑_{j>i} α_{j}(M) = \{ \begin{matrix}q^{−m_{s}} − q^{−n}, & if i = m_{s} for s ∈ [t + 1]; \\ q^{m_{s}} − q^{−n}, & if i = −(m_{s} + 1) for s ∈ [t]. \end{matrix}  (4)

Case 1: i = m_{s+1} for s ∈ [t]. Here

fmaj (σ) = fmaj (τ) + 2(n − 1)χ(j > i),

so that

∑_{σ∈B_{n}(M,i)} q^{fmaj (σ)} = ∑_{j∈[±n]\\{i,−i\}} ∑_{{σ∈Bn(M,i) \atop σ(n−1)=j}} q^{fmaj (σ)} =

= ∑_{j<i} ∑_{τ∈B_{n−1}(M′,j′)} q^{fmaj (τ)} + ∑_{j>i} ∑_{τ∈B_{n−1}(M′,j′)} q^{fmaj (τ)+2(n−1)} =

= \frac{\left[{n−1 \atop ΔM′}\right]q}{q^{n−1} − q^{−(n−1)}} · ∏_{j=m′_{1}+1}^{n−1}(1 + q^{j}) · [ ∑_{j′≤i′} α_{j′}(M′) + q^{2(n−1)} ∑_{j′>i′} α_{j′}(M′)] .

We used here the fact that j < i ⟺ j′ ≤ i′. Now, by equalities (3) and (4) (for M′ instead of M, with i′ = m′_{s+1} = m_{s+1} − 1),

∑_{j′≤i′} α_{j′}(M′) + q^{2(n−1)} ∑_{j′>i′} α_{j′}(M′) =

= (q^{n−1} − q^{−m′_{s+1}}) + q^{2(n−1)} (q^{−m′_{s+1}} − q^{−(n−1)}) =

= (q^{2(n−1)} − 1) q^{−(m_{s+1}−1)}.

Thus (using m′_{1} = m_{1})

∑_{σ∈B_{n}(M,i)} q^{fmaj (σ)} = \frac{q^{2(n−1)} − 1}{q^{n−1} − q^{−(n−1)}} · q^{−(m_{s+1}−1)} · \left[{n − 1 \atop ΔM′}\right]_{q} · ∏_{j=m_{1}+1}^{n−1}(1 + q^{j}) =

= q^{(n−1)−(m_{s+1}−1)} · \left[{n \atop ΔM}\right]_{q} · \frac{[m_{s+1} − m_{s}]_{q}}{[n]_{q}} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}) · \frac{1}{1 + q^{n}} =

= q^{n−m_{s+1}} · \frac{1 − q^{m_{s+1}−m_{s}}}{1 − q^{2n}} · \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}) =

= \frac{q^{−m_{s}} − q^{−m_{s+1}}}{q^{n} − q^{−n}} · \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}),

as claimed. Case 2: i = m_{1} > 0. The computations are as in the previous case, except that m′_{1} = m_{1} − 1:

∑_{σ∈B_{n}(M,i)} q^{fmaj (σ)} = \frac{q^{2(n−1)} − 1}{q^{n−1} − q^{−(n−1)}} · q^{−(m_{1}−1)} · \left[{n − 1 \atop ΔM′}\right]_{q} · ∏_{j=m_{1}}^{n−1}(1 + q^{j}) =

= q^{(n−1)−(m_{1}−1)} · \left[{n \atop ΔM}\right]_{q} · \frac{[m_{1}]_{q}}{[n]_{q}} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}) · \frac{1 + q^{m_{1}}}{1 + q^{n}} =

= q^{n−m_{1}} · \frac{1 − q^{2m_{1}}}{1 − q^{2n}} · \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}) =

= \frac{q^{m_{1}} − q^{−m_{1}}}{q^{n} − q^{−n}} · \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}),

as claimed. Case 3: i = −(m_{s} + 1) for s ∈ [t]. Here χ(i < 0) = 1, so that

∑_{σ∈B_{n}(M,i)} q^{fmaj (σ)} =

= ∑_{j<i} ∑_{τ∈B_{n−1}(M′,j′)} q^{fmaj (τ)+1} + ∑_{j>i} ∑_{τ∈B_{n−1}(M′,j′)} q^{fmaj (τ)+2(n−1)+1} =

= \frac{q · \left[{n−1 \atop ΔM′}\right]_{q}}{q^{n−1} − q^{−(n−1)}} · ∏_{j=m′_{1}+1}^{n−1}(1 + q^{j}) · [ ∑_{j′≤i′} α_{j′}(M′) + q^{2(n−1)} ∑_{j′>i′} α_{j′}(M′)] .

By equalities (3) and (4) (for M′ instead of M, with i′ = −(m_{s}+1)′ = −m_{s}),

∑_{j′≤i′} α_{j′}(M′) + q^{2(n−1)} ∑_{j′>i′} α_{j′}(M′) =

= (q^{n−1} − q^{m′_{s}}) + q^{2(n−1)} (q^{m′_{s}} − q^{−(n−1)}) =
= (q^{2(n−1)} − 1) q^{m_{s}}.

Thus (using m′_{1} = m_{1})

∑_{σ∈B_{n}(M,i)} q^{fmaj (σ)} = \frac{q (q^{2(n−1)} − 1)}{q^{n−1} − q^{−(n−1)}} · q^{m_{s}} · \left[{n − 1 \atop ΔM′}\right]_{q} · ∏_{j=m_{1}+1}^{n−1}(1 + q^{j}) =

= q^{n+m_{s}} · \left[{n \atop ΔM}\right]_{q} · \frac{[m_{s+1} − m_{s}]_{q}}{[n]_{q}} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}) · \frac{1}{1 + q^{n}} =

= q^{n+m_{s}} · \frac{1 − q^{m_{s+1}−m_{s}}}{1 − q^{2n}} · \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}) =

= \frac{q^{m_{s+1}} − q^{m_{s}}}{q^{n} − q^{−n}} · \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}),

as claimed.

□

To prove the corresponding result for ℓ_{B} we will find it useful to use the fact that

ℓ_{B}(σ) = \frac{inv(\overline{σ}) + neg(σ)}{2}  (5)

for all σ ∈ B_{n}, where \overline{σ} := (σ(−n), …, σ(−1), σ(1), …, σ(n)). This formula, first observed by Incitti in [26], is easily seen to be equivalent to (1). So, for example, if σ = [−3, 1, −6, 2, −4, −5] then inv(\overline{σ}) = 50 and ℓ_{B}(σ) = \frac{50+4}{2} = 27.

Theorem 4.3 Let M = {m_{1}, m_{2}, …, m_{t}}_{<} ⊆ [0, n − 1] and i ∈ [±n]. Then q^{ℓ_{B}(σ)} satisfies exactly the same formula as does q^{fmaj(σ)} in Theorem 4.2.

Proof. By induction on n. As in the previous proof, the result is easy to verify for n ≤ 2. We assume that n ≥ 3, and that the result holds for n − 1. Again, we may assume that

i ∈ M_{±} := {m_{1}, …, m_{t+1}} ∪ {−(m_{1} + 1), …, −(m_{t} + 1)}.

These values will be checked case-by-case.

Case 1: i = m_{s+1} for s ∈ [t]. By (5)

ℓ_{B}(σ) = ℓ_{B}(τ) + \frac{2(n − i) + 0}{2},

so that

∑_{σ∈B_{n}(M,i)} q^{ℓ_{B}(σ)} = ∑_{j∈[±n]\\{i,−i\}} ∑_{{σ∈Bn(M,i) \atop σ(n−1)=j}} q^{ℓ_{B}(σ)} =

= ∑_{j≠±i} ∑_{τ∈B_{n−1}(M′,j′)} q^{ℓ_{B}(τ)+(n−i)} =

= \frac{q^{n−i} · \left[{n−1 \atop ΔM′}\right]_{q}}{q^{n−1} − q^{−(n−1)}} · ∏_{j=m′_{1}+1}^{n−1}(1 + q^{j}) · ∑_{j′=−(n−1)}^{n−1} α_{j′}(M′) =

= q^{n−m_{s+1}} · \left[{n − 1 \atop ΔM′}\right]_{q} · ∏_{j=m_{1}+1}^{n−1}(1 + q^{j}) =

= q^{n−m_{s+1}} · \left[{n \atop ΔM}\right]_{q} · \frac{[m_{s+1} − m_{s}]_{q}}{[n]_{q}} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}) · \frac{1}{1 + q^{n}} =

= \frac{q^{−m_{s}} − q^{−m_{s+1}}}{q^{n} − q^{−n}} · \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}),

as claimed.

Case 2: i = m_{1} > 0. The computations are as in the previous case, except that m′_{1} = m_{1} − 1:

∑_{σ∈B_{n}(M,i)} q^{ℓ_{B}(σ)} = q^{n−m_{1}} · \left[{n − 1 \atop ΔM′}\right]_{q} · ∏_{j=m_{1}}^{n−1}(1 + q^{j}) =

= q^{n−m_{1}} · \left[{n \atop ΔM}\right]_{q} · \frac{[m_{1}]_{q}}{[n]_{q}} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}) · \frac{1 + q^{m_{1}}}{1 + q^{n}} =

= \frac{q^{m_{1}} − q^{−m_{1}}}{q^{n} − q^{−n}} · \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}),

as claimed.

Case 3: i = −(m_{s} + 1) for s ∈ [t]. Here

ℓ_{B}(σ) = ℓ_{B}(τ) + \frac{(4(|i| − 1) + 2(n − |i|) + 1) + 1}{2}.

Thus, using m′_{1} = m_{1}:

∑_{σ∈B_{n}(M,i)} q^{ℓ_{B}(σ)} = ∑_{j≠±i} ∑_{τ∈B_{n−1}(M′,j′)} q^{ℓ_{B}(τ)+(n+|i|−1)} =

= \frac{q^{n+|i|−1} · \left[{n−1 \atop ΔM′}\right]_{q}}{q^{n−1} − q^{−(n−1)}} · ∏_{j=m′_{1}+1}^{n−1}(1 + q^{j}) · ∑_{j′=−(n−1)}^{n−1} α_{j′}(M′) =

= q^{n+m_{s}} · \left[{n − 1 \atop ΔM′}\right]_{q} · ∏_{j=m_{1}+1}^{n−1}(1 + q^{j}) =

= q^{n+m_{s}} · \left[{n \atop ΔM}\right]_{q} · \frac{[m_{s+1} − m_{s}]_{q}}{[n]_{q}} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}) · \frac{1}{1 + q^{n}} =

= \frac{q^{m_{s+1}} − q^{m_{s}}}{q^{n} − q^{−n}} · \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}),

as claimed.

□

From Theorems 4.2 and 4.3 we immediately deduce Therem 3.2.

By summing Theorems 4.2 and 4.3 over i ∈ [±n] we obtain Theorem 3.3, which was the original motivation for this work, and which is the analogue, for the hyperoctahedral group, of Theorem 2.6.

It would be interesting to have combinatorial (bijective) proofs of these results.

Added in Proof: A bijective proof of Theorem 3.4 has been found by Foata and Han [20].

5 Final Remarks

5.1 Open Problems

Numerical evidence suggests that the following holds. Conjecture 5.1 For every subset M ⊆ [0, n − 1] and i ∈ [±n] the polynomial

∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M, σ(n)=i}} q^{ℓ_{B}(σ)} = ∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M, σ(n)=i}} q^{fmaj (σ)}.

is (symmetric and) unimodal. Conjecture 5.2 For every subset M ⊆ [0, n − 1] the polynomial

∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M}} q^{ℓ_{B}(σ)} = ∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M}} q^{fmaj (σ)}.

is (symmetric and) unimodal.

Using well known results (see, e.g., [36, Proposition 1 and Theorem 11]) and Theorems 3.3, 4.2 and 4.3, it is easy to see that the above conjectures are equivalent to the following. Conjecture 5.3 For 0 ≤ k < n the polynomial

\left[{n \atop k}\right]_{q} · ∏_{j=k+1}^{n}(1 + q^{j})

is (symmetric and) unimodal.

We have verified these conjectures for n ≤ 15. Conjecture 5.3 clearly holds for k = n−1 and is known to be true for k = 0 (see, e.g., [36, p. 510]). We have checked that the polynomials

∑_{{σ∈B_{n} | Des_{B}(σ^{−1})=M, σ(n)=i}} q^{ℓ_{B}(σ)} = ∑_{{σ∈B_{n} | Des_{B}(σ^{−1})=M, σ(n)=i}} q^{fmaj (σ)}.

and

∑_{{σ∈B_{n} | Des_{B}(σ^{−1})=M}} q^{ℓ_{B}(σ)} = ∑_{{σ∈B_{n} | Des_{B}(σ^{−1})=M}} q^{fmaj (σ)}.

are unimodal for all M ⊆ [0, n − 1] and i ∈ [±n] if n ≤ 5. In general, these polynomials are not symmetric.

5.2 Classical Weyl Groups of Type D

Let D_{n} be the classical Weyl group of type D and rank n. For an element σ ∈ D_{n}, let ℓ_{D}(σ) be the length of σ with respect to the Coxeter generators of D_{n}. It is well known that we may take

D_{n} = {σ ∈ B_{n} | neg(σ) ≡ 0 mod 2}.

Let σ = [σ(1), …, σ(n)] ∈ D_{n}. Biagioli and Caselli [9] introduced a flag major index for D_{n}

fmaj_{D}(σ) := fmaj (σ(1), …, σ(n − 1), |σ(n)|).

By definition,

∑_{σ∈D_{n}} q^{fmaj_{D}(σ)} = ∑_{{σ∈B_{n} | σ(n)>0}} q^{fmaj(σ)}.  (6)

Proposition 5.4

∑_{σ∈D_{n}} q^{ℓ_{D}(σ)} = ∑_{{σ∈B_{n} | σ(n)>0}} q^{ℓ_{B}(σ)}.

Proof. It is well known (see, e.g. [25, §3.15]) that

∑_{σ∈D_{n}} q^{ℓ_{D}(σ)} = [n]_{q} · ∏_{i=1}^{n−1}[2i]_{q}.

On the other hand,

∑_{{σ∈B_{n} | σ(n)>0}} q^{ℓ_{B}(σ)} = ∑_{i=1}^{n} ∑_{{σ∈B_{n} | σ(n)=i}} q^{ℓ_{B}(σ)} =

= ∑_{i=1}^{n} ∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆[0,n−1], σ(n)=i}} q^{ℓ_{B}(σ)}.

By Theorem 4.3, this is equal to

\frac{q^{0} − q^{−n}}{q^{n} − q^{−n}} · \left[{n \atop 1, …, 1}\right]_{q} · ∏_{j=1}^{n}(1 + q^{j}) = [n]_{q}! · ∏_{j=1}^{n−1}(1 + q^{j}) = [n]_{q} · ∏_{j=1}^{n−1}[2j]_{q},

completing the proof.

□

We deduce the following type D analogue (first proved in [9]) of MacMahon’s theorem.

Corollary 5.5

∑_{σ∈D_{n}} q^{fmaj_{D}(σ)} = ∑_{σ∈D_{n}} q^{ℓ_{D}(σ)}.

Proof. Combine (6) and Proposition 5.4 with Theorem 3.2.

□

Problem 5.6 Find an analogue of the Foata-Schützenberger theorem for D_{n}.

The obvious candidate for such an analogue does not work.

5.3 Two Versions of the Flag Major Index

The flag major index of σ ∈ B_{n}, flag-major(σ), was originally defined as the length of a distinguished canonical expression for σ. In [5] this length was shown to be equal to 2 · maj_{A}(σ) + neg(σ), where the major index of the sequence (σ(1), …, σ(n)) was taken with respect to the order −1 < ⋯ < −n < 1 < ⋯ < n. In [1] we considered a different order: −n < ⋯ < −1 < 1 < ⋯ < n (i.e., we defined fmaj as in Section 3 above).

While both versions give type B analogues of the MacMahon and Carlitz identities, only the second one gives an analogue of the Foata-Schützenberger theorem. On the other hand, the first one has the alternative natural interpretation as length, as mentioned above, and also produces a natural analogue of the signed Mahonian formula of Gessel and Simion, see [4]. The relation between these two versions and their (possibly different) algebraic roles requires further study.

6 Appendix

In this appendix we give an alternative proof of Theorems 3.3 and 3.4 (but not Theorem 3.2), using q-binomial identities.

6.1 Binomial Identities

In this subsection we recall several q-binomial identities.

Lemma 6.1 For every positive integer n

∑_{k=0}^{n} \left[{n \atop k}\right]_{q^{2}}q^{k} = ∏_{i=1}^{n}(1 + q^{i}).

This identity may be easily proved by induction on n. The following lemma is a multinomial extension of it.

Lemma 6.2 For every subset M = {m_{1}, …, m_{t}}_{<} ⊆ [0, n − 1]

∑_{r_{1},...,r_{t}} \left[{n \atop ΔM_{r}}\right]_{q^{2}}q^{∑_{i=1}^{t}(r_{i}−m_{i})} = \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}),

where m_{t+1} := n, the sum on the left hand side is over all r_{1}, …, r_{t} such that m_{i} ≤ r_{i} ≤ m_{i+1} (∀i), and

\left[{n \atop ΔM_{r}}\right]_{q^{2}} := \left[{n \atop m_{1}, r_{1} − m_{1}, m_{2} − r_{1}, …, r_{t} − m_{t}, m_{t+1} − r_{t}}\right]_{q^{2}}.

Proof. Decomposing the multinomial coefficient,

∑_{r_{1},...,r_{t}} \left[{n \atop ΔM_{r}}\right]_{q^{2}}q^{∑_{i=1}^{t}(r_{i}−m_{i})} = \left[{n \atop ΔM}\right]_{q^{2}} · ∏_{i=1}^{t} ∑_{r_{i}=m_{i}}^{m_{i+1}} \left[{m_{t+1} − m_{t} \atop r_{t} − m_{t}}\right]_{q^{2}}q^{r_{i}−m_{i}}.

By Lemma 6.1 this is equal to

\left[{n \atop ΔM}\right]_{q^{2}} · ∏_{i=1}^{t} ∏_{j=1}^{m_{i+1}−m_{i}}(1 + q^{j})

and, since

\left[{n \atop ΔM}\right]_{q^{2}} = \left[{n \atop ΔM}\right]_{q} · ∏_{j=1}^{n}(1 + q^{j}) · [∏_{i=0}^{t} ∏_{j=1}^{m_{i+1}−m_{i}}(1 + q^{j})]^{−1} =

= \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}) · [∏_{i=1}^{t} ∏_{j=1}^{m_{i+1}−m_{i}}(1 + q^{j})]^{−1} ,

we get the desired conclusion.

□

The following “q-binomial Theorem” is well known.

Theorem 6.3

∏_{i=1}^{n}(1 + q^{i}x) = ∑_{k=0}^{n} \left[{n \atop k}\right]_{q}q^{\binom{k+1}{2}}x^{k}.

6.2 An Alternative Proof of Theorems 3.3 and 3.4

Proof of Theorem 3.3. Let m_{0} := 0 and m_{t+1} := n. By Lemma 4.1, for each σ ∈ B_{n} with Des_{B}(σ^{−1}) ⊆ M there exist r_{1}, …, r_{t} such that m_{i} ≤ r_{i} ≤ m_{i+1} (∀i) and (σ(1), …, σ(n)) is a shuffle of the following increasing sequences:

(1, …, m_{1}),
(−r_{1}, …, −(m_{1} + 1)),
(r_{1} + 1, …, m_{2}),
⋮
(−r_{t}, …, −(m_{t} + 1)),
(r_{t} + 1, …, n).

By (1),

∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M}} q^{ℓ_{B}(σ)} = ∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M}} q^{inv(σ)+∑_{σ(i)<0} |σ(i)|}.

Note that

σ(i) < 0 ⟺ (∃j) m_{j} + 1 ≤ |σ(i)| ≤ r_{j}.

Therefore

∑_{σ(i)<0} |σ(i)| = ∑_{i=1}^{t}[(m_{i} + 1) + … + r_{i}] = ∑_{i=1}^{t} \frac{1}{2}(r_{i} − m_{i})(r_{i} + m_{i} + 1).

This is a constant, once we fix r_{1}, …, r_{t} (and M). The inversion number of a shuffle does not depend on the actual values of the elements in the shuffled sequences, but only on their order. Therefore, by Observation 2.1 and Fact 2.5,

∑_{σ} q^{inv(σ)} = \left[{n \atop m_{1}, r_{1} − m_{1}, m_{2} − r_{1}, …, r_{t} − m_{t}, m_{t+1} − r_{t}}\right]_{q},

where the sum on the left hand side is over all σ ∈ B_{n} with Des_{B}(σ^{−1}) ⊆ M = {m_{1}, … m_{t}}_{<} and prescribed r_{1}, …, r_{t}.

Combining these two formulas, we get

∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M}} q^{ℓ_{B}(σ)} =

= ∑_{r_{1},...,r_{t}} \left[{n \atop m_{1}, r_{1} − m_{1}, m_{2} − r_{1}, …, m_{t+1} − r_{t}}\right]_{q}q^{∑_{i=1}^{t} \frac{1}{2} (r_{i}−m_{i})(r_{i}+m_{i}+1)} =

= \left[{n \atop ΔM}\right]_{q} · ∏_{i=1}^{t} ∑_{r_{i}=m_{i}}^{m_{i+1}} \left[{m_{i+1} − m_{i} \atop r_{i} − m_{i}}\right]_{q}q^{\frac{1}{2} (r_{i}−m_{i})(r_{i}+m_{i}+1)}.

By the q-binomial Theorem (Theorem 6.3), with x = q^{m_{i}} and n = m_{i+1}−m_{i},

∏_{j=m_{i}+1}^{m_{i+1}}(1 + q^{j}) = ∑_{r_{i}=m_{i}}^{m_{i+1}} \left[{m_{i+1} − m_{i} \atop r_{i} − m_{i}}\right]_{q}q^{\binom{r_{i}−m_{i}+1}{2}+m_{i}(r_{i}−m_{i})} =

= ∑_{r_{i}=m_{i}}^{m_{i+1}} \left[{m_{i+1} − m_{i} \atop r_{i} − m_{i}}\right]_{q}q^{\frac{1}{2} (r_{i}−m_{i})(r_{i}+m_{i}+1)}.

Thus

∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M}} q^{ℓ_{B}(σ)} =

= \left[{n \atop ΔM}\right]_{q} · ∏_{i=1}^{t} ∏_{j=m_{i}+1}^{m_{i+1}}(1 + q^{j}) = \left[{n \atop ΔM}\right]_{q} · ∏_{j=m_{1}+1}^{n}(1 + q^{j}).

This completes the proof of the second equality in the theorem, computing a generating function for ℓ_{B}.

An analogous computation holds for fmaj : by Definition 3.1, Lemma 4.1 and Theorem 2.6,

∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M}} q^{fmaj (σ)} = ∑_{{σ∈B_{n} | Des_{B}(σ^{−1})⊆M}} q^{2·maj (σ)+neg(σ)} =

= ∑_{r_{1},...,r_{t}} \left[{n \atop m_{1}, r_{1} − m_{1}, m_{2} − r_{1}, …, r_{t} − m_{t}, m_{t+1} − r_{t}}\right]_{q^{2}}q^{∑_{i=1}^{t}(r_{i}−m_{i})}.

By Lemma 6.2 this is equal to

\left[{n \atop ΔM}\right]_{q} · ∏_{i=m_{1}+1}^{n}(1 + q^{i}),

as claimed.

□

Proof of Theorem 3.4. Apply the Inclusion-Exclusion Principle to Theorem 3.3.

□

References

[1] R. M. Adin, F. Brenti and Y. Roichman, Descent numbers and major indices for the hyperoctahedral group, Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia, PA 2000), Adv. Appl. Math. 27 (2001), 210–224.

[2] R. M. Adin, F. Brenti and Y. Roichman, Equi-distribution over descent classes of the hyperoctahedral group (Extended Abstract), Proc. FPSAC-04 (Univ. British Columbia, Vancouver, BC), 9 pp., 2004.

[3] R. M. Adin, F. Brenti and Y. Roichman, Descent representations and multivariate statistics, Trans. Amer. Math. Soc. 357 (2005), 3051–3082.

[4] R. M. Adin, I. M. Gessel and Y. Roichman, Signed Mahonians, J. Combin. Theory (Ser. A) 109 (2005), 25–43.

[5] R. M. Adin and Y. Roichman, The flag major index and group actions on polynomial rings. Europ. J. Combin. 22 (2001), 431–446.

[6] R. M. Adin and Y. Roichman, Equidistribution and sign-balance on 321avoiding permutations, Sém. Lothar. Combin. 51 (2004), B51d, 14pp.

[7] G. E. Andrews, The Theory of Partitions, Cambridge Univ. Press, Cambridge, 1984.

[8] E. Bagno, Combinatorial parameters of classical groups, Ph.D. Thesis, Bar-Ilan Univ., Ramat-Gan, 2004.

[9] R. Biagioli and F. Caselli, Invariant algebras and major indices for classical Weyl groups, Proc. London Math. Soc. 88 (2004), 603–631.

[10] A. Björner and F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, Vol. 231, Springer-Verlag, 2005.

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

[12] F. Brenti, q-Eulerian polynomials arising from Coxeter groups, Europ. J. Combin. 15 (1994), 417–441.

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

[14] R. J. Clarke and D. Foata, Eulerian calculus. I. Univariable statistics, Europ. J. Combin. 15 (1994), 345–362.

[15] R. J. Clarke and D. Foata, Eulerian calculus. II. An extension of Han’s fundamental transformation, Europ. J. Combin. 16 (1995), 221–252.

[16] R. J. Clarke and D. Foata, Eulerian calculus. III. The ubiquitous Cauchy formula, Europ. J. Combin. 16 (1995), 329–355.

[17] C. O. Chow and I. M. Gessel, On the descent numbers and major indices for the hyperoctahedral group, preprint, 2003.

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

[19] D. Foata and G.-N. Han, Calcul basique des permutations signées. I. Longueur et nombre d’inversions, Adv. Appl. Math. 18 (1997), 489– 509.

[20] D. Foata and G.-N. Han, Signed words and permutations I; a fundamental transformation, Proc. Amer. Math. Soc., to appear.

[21] D. Foata and C. Krattenthaler, Graphical major indices, II, Sém. Lothar. Combin. 34 (1995), B34k, 16 pp.

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

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

[24] J. Haglund, N. Loehr and J. B. Remmel, Statistics on wreath products, perfect matchings, and signed words, Europ. J. Combin. 26 (2005), 835– 868.

[25] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Math., No. 29, Cambridge Univ. Press, Cambridge, 1990.

[26] F. Incitti, The Bruhat order on the involutions of the hyperoctahedral group, Europ. J. Combin. 24 (2003), 825–848.

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

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

[29] V. Reiner, Signed permutation statistics, Europ. J. Combin. 14 (1993), 553–567.

[30] V. Reiner, Signed permutation statistics and cycle type, Europ. J. Combin. 14 (1993), 569–579.

[31] V. Reiner, Upper binomial posets and signed permutation statistics, Europ. J. Combin. 14 (1993), 581–588.

[32] V. Reiner, The distribution of descent and length in a Coxeter group, Electron. J. Combin. 2 (1995), R25, 20 pp.

[33] Y. Roichman, Schubert polynomials, Kazhdan-Lusztig basis and characters, Discrete Math. 217 (2000), 353–365.

[34] D. P. Roselle, Coefficients associated with the expansion of certain products, Proc. Amer. Math. Soc. 45 (1974), 144–150.

[35] R. P. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combin. Theory (Ser. A) 20 (1976), 336–356.

[36] R. P. Stanley, Log-concave and unimodal sequences in Algebra, Combinatorics, and Geometry, Annals of the New York Academy of Sciences 576 (1989), 500-534.

[37] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

[38] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, New York/Cambridge, 1999.

[39] E. Steingrimsson, Permutation statistics of indexed permutations, Europ. J. Combin. 15 (1994), 187–205.