Descent Numbers and Major Indices for the Hyperoctahedral Group

Ron M. Adin ^{1}

Department of Mathematics and Computer Science

Bar-Ilan University Ramat-Gan 52900, Israel radin@math.biu.ac.il

Francesco Brenti ^{1} Dipartimento di Matematica Universitá di Roma “Tor Vergata” Via della Ricerca Scientifica 00133 Roma, Italy brenti@mat.uniroma2.it

Yuval Roichman ^{1}

Department of Mathematics and Computer Science

Bar-Ilan University Ramat-Gan 52900, Israel yuvalr@math.biu.ac.il

December 1, 2000

Dedicated to Dominique Foata

1Research of all authors was supported in part by the Israel Science Foundation, administered by the Israel Academy of Sciences and Humanities.

Abstract We introduce and study three new statistics on the hyperoctahedral group B_{n}, and show that they give two generalizations of Carlitz’s identity for the descent number and major index over S_{n}. This answers a question posed by Foata.

1 Introduction

A well known classical result due to MacMahon (see [13]) asserts that the inversion number and major index of a permutation are equidistributed over the symmetric group S_{n}. The joint distribution of major index and descent number was studied by Carlitz [4], Gessel [11], and others. Despite the fact that an increasing number of enumerative results of this nature have been generalized to the hyperoctahedral group B_{n} (see, e.g., [3], [9], [16], [17], [18]) and that several “major index” statistics have been introduced and studied for B_{n} (see, e.g., [5], [6], [7], [14], [15], [20]), no generalization of MacMahon’s result has been found until the recent paper [1]. There a new statistic, the flag major index (denoted here fmaj ) was introduced; and it was shown to be equidistributed with length, which is the natural analogue of inversion number from a Coxeter group theoretic point of view. No corresponding “descent statistic” has been found that allows the generalization to B_{n} of the well known Carlitz identity for descent number and major index on S_{n} (see [4], and also Theorem 2.2 below), a problem first posed by Foata [8].

Problem 1.1 (Foata) : Extend the (“Euler-Mahonian”) bivariate distribution of descent number and major index to the hyperoctahedral group B_{n}.

The purpose of this paper is to introduce and study three new statistics on B_{n}: the negative descent (denoted ndes); the negative major (nmaj ); and the flag descent (fdes). When restricted to S_{n} they reduce to descent number, major index, and twice descent number, respectively, and they solve the above problem. More precisely, we show that nmaj is equidistributed with length on B_{n}, and that ndes is the “right” corresponding descent statistic needed to extend Carlitz’s result to B_{n}, thus answering Foata’s question. Finally, we prove the surprising result that the pair of statistics (fdes, fmaj ) is equidistributed with (ndes, nmaj ) over B_{n}, thus obtaining a second generalization of Carlitz’s identity to B_{n}.

The organization of the paper is as follows. In the next section we collect several definitions, notation, and results that will be used in the sequel. In section 3 we introduce a new “descent set” for elements of B_{n} and, correspondingly, a new “descent number” ndes and a new “major index” nmaj . It is shown that nmaj is equidistributed with length over B_{n} (Proposition 3.1), and, moreover, that the pair (ndes, nmaj ) gives a generalization of Carlitz’s identity (Theorem 3.2) and thus solves Foata’s problem. In section 4 we introduce a “flag analogue” of the descent number for B_{n}, fdes, and show that it gives a second solution to Foata’s problem (Corollary 4.2). We then deduce that the pairs of statistics (ndes, nmaj ) and (fdes, fmaj ) are equidistributed over B_{n} (Corollary 4.5).

2 Notation, Definitions, and Preliminaries

In this section we collect some definitions, notation and results that will be used in the rest of this paper. We let P =^{def} {1, 2, 3, …}, N =^{def} P ∪ {0}, Z be the ring of integers, and Q be the field of rational numbers; for a ∈N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅). Given n, m ∈ Z, n ≤ m, we let [n, m] =^{def} {n, n + 1, …, m}. For S ⊂ N we 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|. More generally, given a multiset M = {1^{a_{1}}, 2^{a_{2}}, …, r^{a_{r}}} we denote by |M| its cardinality, so |M| = ∑_{i=1}^{r} a_{i}. Given a statement P we will sometimes find it convenient to let

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

Given a variable q and a commutative ring R we denote by R[q] (respectively, R[[q]]) the ring of polynomials (respectively, formal power series) in q with coefficients in R. For i ∈ N we let, as customary, [i]_{q} =^{def} 1 + q + q^{2} + … + q^{i−1} (so [0]_{q} = 0).

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(σ) =^{def} ∑_{{i: a_{i}>a_{i+1}}} i

and call it the major index of σ.

Given a set T we let S(T) be the set of all bijections π : T → T, and S_{n} =^{def} S([n]). If σ ∈ S_{n} then we write σ = σ_{1} … σ_{n} to mean that σ(i) = σ_{i}, for i = 1, …, n. If σ ∈ S_{n} then we will also write σ in disjoint cycle form (see, e.g., [19], p. 17), and will usually omit to write the 1-cycles of σ. For example, if σ = 365492187 then we also write σ = (9, 7, 1, 3, 5)(2, 6). Given σ, τ ∈ S_{n} we let στ =^{def} σ ∘ τ (composition of functions) so that, for example, (1, 2)(2, 3) = (1, 2, 3).

We denote by B_{n} the group of all bijections π of the set [−n, n] \ {0} onto itself such that

π(−a) = −π(a)

for all a ∈ [−n, n] \ {0}, 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 we write π = [a_{1}, …, a_{n}] to mean that π(i) = a_{i} for i = 1, …, n, and we let

inv(π) =^{def} inv(a_{1}, …, a_{n}),

des_{A}(π) =^{def} des(a_{1}, …, a_{n}),

maj_{A}(π) =^{def} maj(a_{1}, …, a_{n}),  (1)

Neg(π) =^{def} {i ∈ [n] : a_{i} < 0},

and

neg(π) =^{def} |Neg(π)|.

It is well known (see, e.g., [2, 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} =^{def} [−1, 2, … n]

and

s_{i} =^{def} [1, 2, …, i − 1, i + 1, i, i + 2, … n]

for i = 1, …, n − 1. This gives rise to two other natural statistics on B_{n} (similarly definable for any Coxeter group), namely

l(π) =^{def} 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}(π) =^{def} |{i ∈ [0, n − 1] : l(πs_{i}) < l(π)}|.

There is a well known direct combinatorial way to compute these two statistics for π ∈ B_{n} (see, e.g., [2, Propositions 8.1.1 and 8.1.2] or [3, Proposition 3.1 and Corollary 3.2]), namely

l(π) = inv(π) − ∑_{i∈Neg(π)} π(i)  (2)

and

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

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

Let

T =^{def} {π ∈ B_{n} : des_{A}(π) = 0}.  (4)

It is then well known, and easy to see, that

B_{n} = ⨄_{u∈S_{n}}{πu : π ∈ T },  (5)

where ⨄ denotes disjoint union.

We will use this decomposition often in this paper. The reader familiar with Coxeter groups will immediately recognize that (5) is one case of the multiplicative decomposition of a Coxeter group into a parabolic subgroup and its minimal coset representatives (see, e.g., [12] or [2]).

As customary, given a variable t we define an operator δ_{t} : Q[q, t] → Q[q, t] by

δ_{t}(P (q, t)) = \frac{P (q, qt) − P (q, t)}{qt − t},

for all P ∈ Q[q, t]. Note that δ_{t}(q^{n}) = 0 and

δ_{t}(t^{n}) = [n]_{q} t^{n−1}  (6)

for all n ∈ N, and

δ_{t}(A(q, t) B(q, t)) = δ_{t}(A(q, t))B(q, t) + A(q, qt)δ_{t}(B(q, t))  (7)

for all A, B ∈ Q[q, t]. Also,

δ_{t}(P)(1, t) = \frac{d}{dt}(P (1, t))

for all P ∈ Q[q, t].

For n ∈ P we let

A_{n}(t, q) =^{def} ∑_{σ∈S_{n}} t^{des_{A}(σ)}q^{maj^{A}(σ)},

and A_{0}(t, q) =^{def} 1. For example, A_{3}(t, q) = 1 + 2tq^{2} + 2tq + t^{2}q^{3}. The following two results are due to Carlitz [4] and Gessel [11], and proofs of them can also be found in [10].

Theorem 2.1 Let n ∈ P. Then

A_{n}(t, q) = (1 + tq[n − 1]_{q}) A_{n−1}(t, q) + tq(1 − t)δ_{t}(A_{n−1}(t, q)).

Theorem 2.2 Let n ∈ P. Then

∑_{r≥0}[r + 1]_{q}^{n}t^{r} = \frac{A_{n}(t, q)}{∏_{i=0}^{n}(1 − tq^{i})}.

in Z[q][[t]].

3 The “Negative” Statistics

In this section we define and study a new “descent set” for the elements of B_{n}. This gives rise, in a very natural way, to new “major index” and “descent number” statistics for B_{n}. We then show that these two statistics give a generalization of Carlitz’s identity to B_{n}, and that one of them is equidistributed with length.

3.1 The Negative Descent Multiset

For π ∈ B_{n} we define

Des_{A}(π) =^{def} {i ∈ [n − 1] : π(i) > π(i + 1)}

and the negative descent multiset

NDes(π) =^{def} Des_{A}(π) ⨄{−π(i) : i ∈ Neg(π)},  (8)

where Neg(π) is the set of positions of negative entries in π, defined in (1).

For example, if π = [−3, 1, −6, 2, −4, −5] ∈ B_{6} then Des_{A}(π) = {2, 4, 5} and NDes(π) = {2, 3, 4^{2}, 5^{2}, 6}. Note that if π ∈ S_{n} then NDes(π) is a set and coincides with the usual descent set of π. Also note that NDes(π) can be defined rather naturally also in purely Coxeter group theoretic terms. In fact, for i ∈ [n] let η_{i} ∈ B_{n} be defined by

η_{i} =^{def} [1, 2, …, i − 1, −i, i + 1, …, n],

so η_{1} = s_{0}. Then η_{1}, …, η_{n} are reflections (in the Coxeter group sense; see, e.g., [12]) of B_{n} and it is clear from (2) that

NDes(π) = {i ∈ [n − 1] : l(πs_{i}) < l(π)} ⨄{i ∈ [n] : l(π^{−1}η_{i}) < l(π^{−1})}.

These considerations explain why it is natural to think of NDes(π) as a “descent set”. With this in mind, the following definitions are also natural. For π ∈ B_{n} we let

ndes(π) =^{def} |NDes(π)|

and

nmaj (π) =^{def} ∑_{i∈NDes(π)} i.

For example, if π = [−3, 1, −6, 2, −4, −5] ∈ B_{6} then ndes(π) = 7 and nmaj (π) = 29. Note that from (8) it follows that

nmaj (π) = maj_{A}(π) − ∑_{i∈Neg(π)} π(i) (∀π ∈ B_{n}).  (9)

This formula is also one of the motivations behind our definition of nmaj (π), because of the corresponding formula (2).

3.2 Equidistribution and Generating Function

Our first result shows that nmaj and l are equidistributed in B_{n}.

Proposition 3.1 Let n ∈ P. Then

∑_{π∈B_{n}} q^{nmaj(π)} = ∑_{π∈B_{n}} q^{l(π)}.

Proof. Let T be defined by (4). It is clear from our definitions that for all u ∈ S_{n} and σ ∈ T,

maj_{A}(σu) = maj_{A}(u), inv(σu) = inv(u),

and

∑_{i∈Neg(σu)}(σu)(i) = ∑_{i∈Neg(σ)} σ(i).

Therefore, from (2), (5), (9), and the corresponding classical result for S_{n} (see, e.g., [13]) we conclude that

∑_{π∈B_{n}} q^{nmaj (π)} = ∑_{σ∈T} ∑_{u∈S_{n}} q^{nmaj (σu)}
= ∑_{σ∈T} ∑_{u∈S_{n}} q^{maj^{A}(σu)−∑_{i∈Neg(σu)}(σu)(i)}
= ∑_{σ∈T} q^{− ∑_{i∈Neg(σ)} σ(i)} · ∑_{u∈S_{n}} q^{maj^{A}(u)}
= ∑_{σ∈T} q^{− ∑_{i∈Neg(σ)} σ(i)} · ∑_{u∈S_{n}} q^{inv(u)}
= ∑_{σ∈T} ∑_{u∈S_{n}} q^{inv(σu)−∑_{i∈Neg(σu)}(σu)(i)}
= ∑_{π∈B_{n}} q^{l(π)},

as desired. □

We now prove the main result of this section, which is also the first main result of this work, namely that the pair of statistics (ndes, nmaj ) gives a generalization of Theorem 2.2 to B_{n}.

Theorem 3.2 Let n ∈ P. Then

∑_{r≥0}[r + 1]_{q}^{n}t^{r} = \frac{∑_{π∈B_{n}}t^{ndes(π)}q^{nmaj(π)}}{(1 − t)∏_{i=1}^{n}(1 − t^{2}q^{2i})}

in Z[q][[t]].

Proof. Let T have the same meaning as in (4). Then it is clear from our definitions that des_{A}(σu) = des_{A}(u) for all σ ∈ T and u ∈ S_{n}. Therefore we have from (5) that

∑_{π∈B_{n}} t^{ndes(π)}q^{nmaj (π)} = ∑_{σ∈T} ∑_{u∈S_{n}} t^{des_{A}(σu)+neg(σu)}q^{maj^{A}(σu)−∑_{i∈Neg(σu)}(σu)(i)}
= ∑_{σ∈T} t^{neg(σ)}q^{− ∑_{i∈Neg(σ)} σ(i)} · ∑_{u∈S_{n}} t^{des_{A}(u)}q^{maj^{A}(u)}

= ∑_{S⊆[n]} t^{|S|} q^{∑_{i∈S} i} · ∑_{u∈S_{n}} t^{des_{A}(u)}q^{maj^{A}(u)}
= ∏_{i=1}^{n}(1 + tq^{i}) · ∑_{u∈S_{n}} t^{des_{A}(u)} q^{maj^{A}(u)}

and the result follows from Theorem 2.2. □

4 The Flag Statistics

In this section we introduce yet another pair of statistics on B_{n}, and show that it also gives a solution to Foata’s problem. We then derive some consequences of this result.

4.1 The Flag Major Index

For i = 0, 1, …, n − 1 let t_{i} =^{def} s_{i}s_{i−1} ⋯ s_{0}. Explicitly,

t_{i} = [−i − 1, 1, 2, …, i, i + 2, …, n]

for i = 0, …, n − 1. It is not hard to show (see also [1]) that for any π ∈ B_{n} there exist unique integers k_{0}, …, k_{n−1}, with 0 ≤ k_{i} ≤ 2i + 1 for i = 0, …, n − 1, such that

π = t_{n−1}^{k_{n−1}} … t_{2}^{k_{2}}t_{1}^{k_{1}}t_{0}^{k_{0}}.

The flag major index of π (see [1]) is then defined by

fmaj (π) =^{def} ∑_{i=0}^{n−1} k_{i}.

There is a simple way to compute the flag major index of a signed permutation π. In fact, we have the following result which was first proved in [1].

Theorem 4.1 Let π ∈ B_{n}. Then

fmaj (π) = 2 maj_{A}(π) + neg(π).

For example, if π = [−3, 1, −6, 2, −4, −5] then fmaj (π) = 2 · 11 + 4 = 26.

In [1] it was shown that fmaj appears naturally in the Hilbert series of (diagonal action) invariant algebras; note that this property is not shared by nmaj .

4.2 The Flag Descent Number

For π ∈ B_{n} let

fdes(π) =^{def} 2 des_{A}(π) + ε_{1}(π),  (10)

where des_{A} is as in Section 2 and

ε_{1}(π) =^{def} \{ \begin{matrix}1, & if π(1) < 0, \\ 0, & otherwise. \end{matrix}  (11)

This definition is motivated by Theorem 4.1, and because of this similarity we call fdes(π) the flag descent number of π. For example, if π = [−3, 1, −6, 2, −4, −5] then fdes(π) = 2 · 3 + 1 = 7. Note that from (3), (1) and (11) it follows immediately that

fdes(π) = des_{A}(π) + des_{B}(π)  (12)

and also

fdes(π) = des(π(−n), …, π(−1), π(1), …, π(n))

for all π ∈ B_{n}.

Our aim is to show that the pair of statistics (fdes, fmaj ) gives a solution to Foata’s problem and thus has the same joint distribution, over B_{n}, as the pair (ndes, nmaj ) defined in the previous section.

4.3 Main Theorems

The main result of this section is

Theorem 4.2 Let n ∈ P. Then

∑_{r≥0}[r + 1]_{q}^{n}t^{r} = \frac{∑_{π∈B_{n}}t^{fdes(π)}q^{fmaj (π)}}{(1 − t)∏_{i=1}^{n}(1 − t^{2}q^{2i})}

in Z[q][[t]].

This solves Foata’s problem and implies, together with Theorem 3.2, that the two pairs of statistics (fdes, fmaj ) and (ndes, nmaj ) are equidistributed over B_{n}.

Theorem 4.2 will be proved in several steps.

Let, for convenience,

S_{n}(t, q) =^{def} ∑_{π∈B_{n}} t^{fdes(π)}q^{fmaj (π)}  (13)

for all n ∈ P, and set S_{0}(t, q) =^{def} 1. For example, S_{1}(t, q) = 1 + tq and S_{2}(t, q) = 1 + 2tq + tq^{2} + t^{2}q^{2} + 2t^{2}q^{3} + t^{3}q^{4}.

Our first result gives a recursion satisfied by the polynomials S_{n}(t, q).

Theorem 4.3 Let n ∈ P. Then

S_{n}(t, q) = (1 + tq + t^{2}q^{2}[2n − 2]_{q})S_{n−1}(t, q) + tq(1 − t)(1 + tq)δ_{t}(S_{n−1}(t, q)).

Proof. The result is clear for n ≤ 2, so fix n ≥ 3. For σ ∈ B_{n−1} and i ∈ [n] let

σ_{i} =^{def} [σ(1), …, σ(i − 1), n, σ(i), …, σ(n − 1)]

and

σ_{−i} =^{def} [σ(1), …, σ(i − 1), −n, σ(i), …, σ(n − 1)].

Then clearly

S_{n}(t, q) = ∑_{σ∈B_{n−1}} ∑_{i=1}^{n} [t^{fdes(σ_{i})} q^{fmaj (σ_{i})} + t^{fdes(σ_{−i})} q^{fmaj (σ_{−i})}] .  (14)

Using (12) and our definitions it is not hard to check (though with some patience) that, for all σ ∈ B_{n−1},

fdes(σ_{1}) = fdes(σ) + 1 + χ[σ(1) > 0];
fdes(σ_{−1}) = fdes(σ) + χ[σ(1) > 0];
fdes(σ_{±i}) = fdes(σ) + 2χ[σ(i − 1) < σ(i)]

for i = 2, …, n − 1;

fdes(σ_{n}) = fdes(σ);

and

fdes(σ_{−n}) = fdes(σ) + 2.

Similarly, let

d_{i}(σ) =^{def} |{j ∈ Des_{A}(σ) : j ≥ i}| (i = 1, …, n − 1)

be the number of descents in σ from position i on. Then

maj_{A}(σ_{i}) = maj_{A}(σ) + d_{i}(σ) + (i − 1) χ[σ(i − 1) < σ(i)] + 1

and

maj_{A}(σ_{−i}) = maj_{A}(σ) + d_{i}(σ) + (i − 1) χ[σ(i − 1) < σ(i)]

for i = 1, …, n − 1;

maj_{A}(σ_{n}) = maj_{A}(σ),

and

maj_{A}(σ_{−n}) = maj_{A}(σ) + n − 1.

Therefore, using Theorem 4.1,

∑_{i=1}^{n} [t^{fdes(σ_{i})} q^{fmaj (σ_{i})} + t^{fdes(σ_{−i})} q^{fmaj (σ_{−i})}] =

= t^{fdes(σ)+χ[σ(1)>0]} q^{fmaj (σ)+2d_{1}(σ)+1}(tq + 1)+
+ ∑_{{i∈[2,n−1]: σ(i−1)>σ(i)}} t^{fdes(σ)} q^{fmaj (σ)+2d_{i}(σ)+1}(q + 1)+
+ ∑_{{i∈[2,n−1]: σ(i−1)<σ(i)}} t^{fdes(σ)+2} q^{fmaj (σ)+2d_{i}(σ)+2i−1}(q + 1) +
+ t^{fdes(σ)} q^{fmaj (σ)}(1 + t^{2}q^{2n−1}).  (15)

From the definition of d_{i}(σ) it is clear that

∑_{{i∈[2,n−1]: σ(i−1)>σ(i)}} q^{2d_{i}(σ)} = ∑_{k=1}^{des_{A}(σ)} q^{2(k−1)}  (16)

for all σ ∈ B_{n−1}. On the other hand, let

{i_{1}, i_{2}, …, i_{a}}_{<} =^{def} {i ∈ [2, n − 1] : σ(i − 1) < σ(i)},

so that a = n − 2 − des_{A}(σ). Then

σ(i_{a}) > σ(i_{a} + 1) > … > σ(n − 1),

and therefore

i_{a} + d_{i_{a}}(σ) = i_{a} + (n − 1 − i_{a}) = n − 1.

Similarly, for each j ∈ [a − 1] one has

σ(i_{j}) > σ(i_{j} + 1) > … > σ(i_{j+1} − 1) < σ(i_{j+1}), and therefore

i_{j} + d_{i_{j}}(σ) = i_{j} + d_{i_{j+1}}(σ) + (i_{j+1} − i_{j} − 1) = i_{j+1} + d_{i_{j+1}}(σ) − 1.

This shows that

∑_{{i∈[2,n−1]: σ(i−1)<σ(i)}} q^{2(d_{i}(σ)+i)} = ∑_{k=1}^{a} q^{2(n−k)}  (17)

for all σ ∈ B_{n−1}.

From (15), (16), and (17) we conclude that

∑_{i=1}^{n} [t^{fdes(σ_{i})} q^{fmaj (σ_{i})} + t^{fdes(σ_{−i})} q^{fmaj (σ_{−i})}] =

= t^{fdes(σ)+χ[σ(1)>0]} q^{fmaj (σ)+2des_{A}(σ)+1}(1 + tq) +
+ t^{fdes(σ)}q^{fmaj (σ)+1}(1 + q) ∑_{k=1}^{des_{A}(σ)} q^{2(k−1)} +
+ t^{fdes(σ)+2}q^{fmaj (σ)−1}(1 + q) ∑_{k=1}^{a} q^{2(n−k)} +
+ t^{fdes(σ)}q^{fmaj (σ)}(1 + t^{2}q^{2n−1}) =
= t^{fdes(σ)}q^{fmaj (σ)} {t^{χ[σ(1)>0]}q^{2des_{A}(σ)+1}(1 + tq)+
+ ∑_{j=1}^{2des_{A}(σ)} q^{j} + t^{2} ∑_{j=2n−2a−1}^{2n−2} q^{j} + (1 + t^{2}q^{2n−1})} =
= t^{fdes(σ)}q^{fmaj (σ)} {t^{χ[σ(1)>0]}q^{2des_{A}(σ)+1}(1 + tq)+
+ ∑_{j=0}^{2des_{A}(σ)} q^{j} + t^{2} ∑_{j=2n−2a−1}^{2n−1} q^{j}} .

Using the value of a, (10) and some case-by-case analysis (depending on the sign of σ(1)) we get

∑_{i=1}^{n} [t^{fdes(σ_{i})} q^{fmaj (σ_{i})} + t^{fdes(σ_{−i})} q^{fmaj (σ_{−i})}] =  (18)
= t^{fdes(σ)}q^{fmaj (σ)} {[fdes(σ) + 1]_{q} + tq^{fdes(σ)+1}+
+ t^{2}([2n]_{q} − [fdes(σ) + 2]_{q})} =
= t^{fdes(σ)}q^{fmaj (σ)} {1 + q[fdes(σ)]_{q} + tq + tq(q − 1)[fdes(σ)]_{q}+
+ t^{2}q^{2}([2n − 2]_{q} − [fdes(σ)]_{q})} .  (19)

Substituting (19) into (14) we now obtain

S_{n}(t, q) = (1 + tq + t^{2}q^{2}[2n − 2]_{q})S_{n−1}(t, q) +
+ (q + tq(q − 1) − t^{2}q^{2}) ∑_{σ∈B_{n−1}}[fdes(σ)]_{q} t^{fdes(σ)}q^{fmaj (σ)},

and the result follows from (13) and (6). □

Using the previous theorem we can now prove the following result.

Theorem 4.4 Let n ∈ P. Then

∑_{π∈B_{n}} t^{fdes(π)}q^{fmaj (π)} = ∏_{i=1}^{n}(1 + tq^{i}) · ∑_{σ∈S_{n}} t^{des_{A}(σ)}q^{maj_{A}(σ)}.

Proof. We show that both sides satisfy the same recursion; equality of initial conditions is easily checked (n ≤ 2). Let, for convenience,

S̃_{n}(t, q) =^{def} ∏_{i=1}^{n}(1 + tq^{i}) · A_{n}(t, q)

be the right-hand side of the formula in Theorem 4.4.

It is easily verified that

δ_{t} (∏_{i=1}^{n}(1 + tq^{i})) = q[n]_{q} ∏_{i=2}^{n}(1 + tq^{i}),

so that by (7)

(1 + tq)δ_{t}(S̃_{n}(t, q)) = q[n]_{q}S̃_{n}(t, q) + ∏_{i=1}^{n+1}(1 + tq^{i}) · δ_{t}(A_{n}(t, q)).

By Theorem 2.1 we therefore conclude that

S̃_{n}(t, q) = ∏_{i=1}^{n}(1 + tq^{i}) · A_{n}(t, q) =
= ∏_{i=1}^{n}(1 + tq^{i}) · {(1 + tq[n − 1]_{q})A_{n−1}(t, q) + tq(1 − t)δ_{t}(A_{n−1}(t, q))} =
= (1 + tq^{n})(1 + tq[n − 1]_{q})S̃_{n−1}(t, q) +
+ tq(1 − t){(1 + tq)δ_{t}(S̃_{n−1}(t, q)) − q[n − 1]_{q}S̃_{n−1}(t, q)} =
= (1 + tq + t^{2}q^{2}[2n − 2]_{q})S̃_{n−1}(t, q) + tq(1 − t)(1 + tq)δ_{t}(S̃_{n−1}(t, q)),

and comparison with Theorem 4.3 completes the proof. □

Theorem 4.4 has several interesting consequences. The first one is that the descent statistic fdes yields a solution to Foata’s problem (Theorem 4.2).

Proof of Theorem 4.2. This follows immediately from Theorems 4.4 and 2.2, given the definition of A_{n}(t, q). □

This in turn implies, together with Theorem 3.2, that the two pairs of statistics (fdes, fmaj ) and (ndes, nmaj ) are equidistributed in B_{n}.

Corollary 4.5 Let n ∈ P. Then

∑_{π∈B_{n}} t^{ndes(π)}q^{nmaj (π)} = ∑_{π∈B_{n}} t^{fdes(π)}q^{fmaj (π)}.

It would be interesting to have a direct combinatorial (i.e., bijective) proof of this result.

Finally, the special case t = 1 of Corollary 4.5, together with Proposition 3.1, implies the following result, which extends Theorem 2.2 of [1].

Corollary 4.6 Let n ∈ P. Then

∑_{π∈B_{n}} q^{l(π)} = ∑_{π∈B_{n}} q^{nmaj (π)} = ∑_{π∈B_{n}} q^{fmaj (π)}.

Acknowledgments. This paper grew out of stimulating discussions with Dominique Foata, Ira Gessel and Doron Zeilberger during the conference “Classical Combinatorics” in honor of Foata’s 65^{th} birthday. The work on it was carried out while the second author was visiting the other authors at Bar-Ilan University.

References

[1] R. M. Adin and Y. Roichman, The flag major index and group actions on polynomial rings, Europ. J. Combinatorics, to appear.

[2] A. Björner and F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, Springer-Verlag, 2001, to appear.

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

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

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

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

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

[8] D. Foata, personal communication, July 2000.

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

[10] A. Garsia, On the “maj” and “inv” q-analogues of Eulerian polynomials, Linear and Multilinear Algebra, 8(1979/80), 21–34.

[11] I. M. Gessel, Generating functions and enumeration of sequences, Ph.D. Thesis, M.I.T., 1977.

[12] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, no. 29, Cambridge Univ. Press, Cambridge, 1990.

[13] P. A. MacMahon, Combinatory Analysis, Chelsea, New York, 1960. (Originally published in 2 vols. by the Cambridge Univ. Press, 1915–1916.)

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

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

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

[17] V. Reiner, The distribution of descent and length in a Coxeter group, Electron. J. Combinatorics, 2 (1995), R25.

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

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

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