Séminaire Lotharingien de Combinatoire 61A (2010), Article B61Ak

ON SOME ANALOGUES OF DESCENT NUMBERS AND MAJOR INDEX FOR THE HYPEROCTAHEDRAL GROUP

RICCARDO BIAGIOLI AND JIANG ZENG

À la mémoire de Pierre Leroux

Abstract. We give a new description of the flag major index, introduced by Adin and Roichman, by using a major index defined by Reiner. This allows us to establish a connection between an identity of Reiner and some more recent results due to Chow and Gessel. Furthermore we generalize the main identity of Chow and Gessel by computing the four-variate generating series of descents, major index, length, and number of negative entries over Coxeter groups of type B and D.

1. Introduction

It is well known that enumerating permutations by number of descents “des” and major index “maj” yields a remarkable q-analogue for Eulerian polynomials, which satisfies the equation

\frac{∑_{σ∈S_{n}} t^{des(σ)}q^{maj(σ)}}{∏_{i=0}^{n}(1 − tq^{i})} = ∑_{k≥0}(1 + q + ⋯ + q^{k})^{n} t^{k},  (1.1)

where S_{n} denotes the group of permutations of {1, …, n}. Although this identity is usually attributed to Carlitz [8], it is actually a special case of a result of MacMahon [12, Volume 2, Chapter 4]. It is clear that (1.1) is equivalent to

∑_{n≥0} \frac{∑_{σ∈S_{n}} t^{des(σ)}q^{maj(σ)}}{∏_{i=0}^{n}(1 − tq^{i})} \frac{u^{n}}{n!} = ∑_{k≥0} t^{k} exp (1 + q + ⋯ + q^{k})u.  (1.2)

At the end of 1970’s, Gessel [11], and Garsia and Gessel [10] gave substantial extensions of (1.2). In a different direction, Reiner [14, 15] generalized Garsia and Gessel’s work to the group of signed permutations of {1, …, n}, denoted by B_{n}. By using Coxeter group theory, he defined some B_{n}-analogues of descent number, major index, and inversions number, denoted by “d_{R}”, “maj_{R}”, “ℓ_{R}”, respectively, and obtained the identity

∑_{n≥0} \frac{∑_{β∈B_{n}} t^{d_{R}(β)}q^{maj_{R}(β)}p^{ℓ_{R}(β)}a^{neg(β)}}{∏_{i=0}^{n}(1 − tq^{i})} \frac{u^{n}}{[n̂]_{a,p}!} = ∑_{k≥0} t^{k}ê[u]_{a,p}e[qu]_{p} ⋯ e[q^{k}u]_{p},  (1.3)

where neg(β) denotes the number of negative entries in the window notation of β ∈ B_{n}. The precise definitions of the above statistics as well as all undefined notation will be given in Section 2.

The two authors are supported by the grant ANR-08-BLAN-0243-03 and by the Program P2R Franco-Israélien en Mathématiques.

Motivated by their work on invariant algebras, Adin and Roichman introduced the flag major index “fmaj” in [1]. This statistic turned out to be the key ingredient of new B_{n}-analogues of Carlitz identity (see [2, Problem 1.1] on Foata’s problem). Two such analogues were given by Adin, Brenti and Roichman [2, Theorem 4.2, Corollary 4.5]. More recently, a third one was proposed by Chow and Gessel [9, Theorem 3.7]. In its equivalent form, their result reads as follows [9, Theorem 3.8]:

∑_{n≥0} \frac{∑_{β∈B_{n}} t^{des_{B}(β)}q^{fmaj(β)}}{∏_{i=0}^{n}(1 − tq^{2i})} \frac{u^{n}}{n!} = ∑_{k≥0} t^{k} exp(1 + q + ⋯ + q^{2k})u.  (1.4)

Here “des_{B}” denotes a B_{n}-analogue of the descent number, computed with respect to a generating set different from the aforementioned one of Reiner.

Our starting point is the observation that the substitution q ← q^{2}, a ← q^{−1}, p ← 1, and u ← (1 + q^{−1})u in Reiner’s identity (1.3) yields

∑_{n≥0} \frac{∑_{β∈B_{n}} t^{d_{R}(β)}q^{2 maj_{R}(β)−neg(β)}}{∏_{i=0}^{n}(1 − tq^{2i})} \frac{u^{n}}{n!} = ∑_{k≥0} t^{k} exp(1 + q + ⋯ + q^{2k})u.  (1.5)

This implies immediately that the two pairs (des_{B}, fmaj) and (d_{R}, 2 maj_{R} − neg) are equidistributed over B_{n}. Actually our first result (cf. Proposition 3.1) shows that these two pairs of statistics are equal over B_{n}. Therefore Equations (1.4) and (1.5) are the same. This prompted us to look for refinements of Chow and Gessel’s identity by computing the generating function of the four statistics (des_{B}, maj, ℓ_{B}, neg) over B_{n}. It turns out (cf. Theorem 5.1) that this distribution is different from that of Reiner’s four statistics in (1.3). In contrast to the method of Chow and Gessel [9], that uses q-difference calculus and recurrence relations, we adopt a more combinatorial approach inspired by that of Garsia and Gessel [10], and of Reiner [14]. The basic idea is to encode signed sequences by pairs made of a signed permutation and a partition.

Finally we consider the group of even-signed permutations of {1, …, n}, denoted D_{n}. For the Eulerian polynomials of type D, Brenti [7, Theorem 4.10] proved the identity

\frac{∑_{γ∈D_{n}} t^{des_{D}(γ)}}{(1 − t)^{n+1}} = ∑_{k≥0}\{(2k + 1)^{n} − n2^{n−1}[B_{n}(k + 1) − B_{n}]\}t^{k},  (1.6)

where B_{n}(x) denotes the nth Bernoulli polynomial, and B_{n} the nth Bernoulli number. Motivated by this identity and our results in type B, we compute the generating function of some D_{n}-analogues of descents, major index, length, and number of negative entries (cf. Theorem 6.3), by using the same encoding technique for the hyperoctahedral group.

2. Preliminaries and notation

In this section we give some definitions, notation and results that will be used in the rest of this work. Let P be a statement: the characteristic function χ of P is defined as χ(P) = 1 if P is true, and χ(P) = 0 otherwise. For n ∈ ℕ we let [n] := {1, 2, …, n} (where [0] := ∅). Given n, m ∈ ℤ, n ≤ m, we let [n, m] := {n, n + 1, …, m}. The cardinality of a set A will be denoted either by |A| or by #A. For n ∈ ℕ, we let

ON SOME ANALOGUES OF DESCENT NUMBERS AND MAJOR INDEX FOR B_{n} 3

(a; p)_{n} := \{ \begin{matrix}1, & if n = 0; \\ (1 − a)(1 − ap) ⋯ (1 − ap^{n−1}), & if n ≥ 1. \end{matrix}

For our study we need notation for p-analogues of integers and factorials. These are defined by the expressions

[n]_{p} : = 1 + p + p^{2} + ⋯ + p^{n−1},
[n]_{p}! : = [n]_{p}[n − 1]_{p} ⋯ [2]_{p}[1]_{p},
[n̂]_{a,p}! : = (−ap; p)_{n}[n]_{p}!,

where [0]_{p}! = 1. For n = n_{0} +n_{1} +⋯+n_{k} with n_{0}, …, n_{k} ≥ 0 we define the p-multinomial coefficient by

[\begin{matrix}n \\ n_{0}, n_{1}, …, n_{k} \end{matrix}]_{p} := \frac{[n]_{p}!}{[n_{0}]_{p}! [n_{1}]_{p}! ⋯ [n_{k}]_{p}!}.

Finally,

e[u]_{p} := ∑_{n≥0} \frac{u^{n}}{[n]_{p}!}, and ê[u]_{a,p} := ∑_{n≥0} \frac{u^{n}}{[n̂]_{a,p}!}

are the two classical p-analogues of the exponential function.

Recall that the group of signed permutations on [n], or the hyperoctahedral group of rank n, is denoted by B_{n}. This is the group of all bijections β of the set [−n, n] \ {0} onto itself such that

β(−i) = −β(i)

for all i ∈ [−n, n]\{0}, with composition as the group operation. If β ∈ B_{n} then we write β = [β(1), …, β(n)] and we call this the window notation of β. We denote by |β(i)| the absolute value of β(i), and by sgn(β(i)) its sign. For β ∈ B_{n} we let

inv(β) := |{(i, j) ∈ [n] × [n] | i < j, β(i) > β(j)}|, and
neg(β) := |{i ∈ [n] | β(i) < 0}|.

As set of generators for B_{n} we take S_{B} := {s_{1}^{B}, …, s_{n−1}^{B}, s_{0}^{B}} where for i ∈ [n − 1]

s_{i}^{B} := [1, …, i − 1, i + 1, i, i + 2, …, n] and s_{0}^{B} := [−1, 2, …, n].

It is well-known that (B_{n}, S_{B}) is a Coxeter system of type B (see e.g., [6, §8.1]). The following characterization of the length function ℓ_{B}(β) := min{r | β = s_{i_{1}}^{B} ⋯ s_{i_{r}}^{B}, s_{i_{i}}^{B} ∈ S_{B}} of B_{n} with respect to S_{B} is well-known [6, Proposition 8.1.1]:

ℓ_{B}(β) = inv(β) − ∑_{β(i)<0} β(i).

The B-descent set of β ∈ B_{n} is defined by

Des_{B}(β) := {i ∈ [0, n − 1] | β(i) > β(i + 1)},

where β(0) := 0, and its cardinality is denoted by des_{B}(β). The inversion number inv and the B-descent set Des_{B} are computed by using the natural order

−n < ⋯ < −1 < 0 < 1 < ⋯ < n  (2.1)

on the set [−n, n]. As usual the major index is defined to be the sum of descents

maj(β) = ∑_{i∈Des_{B}(β)} i,

and the flag-major index [2, Theorem 4.1] by

fmaj(β) := 2 maj(β) + neg(β).

We should point out that in their first paper [1] Adin and Roichman defined the flag-major index by using a different order. Here we use their second definition which appears in the subsequent paper with Brenti [2], and that uses the natural order (2.1).

Reiner defined descents and length for B_{n} in the usual geometric way by using root systems [14, §2]. Given an element β ∈ B_{n}, let ℓ_{R}(β) denote this length of β and Des_{R}(β) the set of descents of β. Reiner also gave a combinatorial description of these statistics in another paper [17, §2]. Fix the following order on the set [−n, n] \ {0}, denoted by <_{R}:

1 <_{R} ⋯ <_{R} n <_{R} −n <_{R} ⋯ <_{R} −1.  (2.2)

Write < instead of <_{R} when they coincide. Denote by inv_{R}(β) the cardinality of the set of inversions of β ∈ B_{n} computed with respect to the order (2.2), i.e.,

Inv_{R}(β) := {(i, j) ∈ [n] × [n] | i < j, β(j) <_{R} β(i)}.

Then the following result holds [17, §2].

Proposition 2.1. For any β ∈ B_{n} we have

ℓ_{R}(β) = inv_{R}(β) + ∑_{β(i)<0}(n + 1 + β(i)),  (2.3)
Des_{R}(β) = {i ∈ [1, n] | β(i + 1) <_{R} β(i)},  (2.4)

where β(n + 1) := n.

The cardinality of Des_{R}(β) is denoted by d_{R}(β). Note that Reiner used the notation d and inv instead of d_{R} and ℓ_{R}. To avoid confusion we denote the major index associated to Reiner’s descent set by maj_{R}, i.e.,

maj_{R}(β) = ∑_{i∈Des_{R}(β)} i.

Remark 2.2. The main difference between the two descent sets is that 0 can be in Des_{B} but not in Des_{R}, while n can be in Des_{R} but not in Des_{B}. More precisely, 0 ∈ Des_{B}(β) if and only if β(1) < 0, while n ∈ Des_{R}(β) if and only if β(n) < 0. Clearly, this difference reflects on the corresponding major indices. Besides, the two length statistics ℓ_{B} and ℓ_{R} are different since they are computed with respect to different sets of generators. However they are equidistributed over B_{n}, as will be explained in Remark 5.3.

Example 2.3. If β = [−3, 1, 5, 2, −4, −6] ∈ B_{5} then

Des_{B}(β) = {0, 3, 4, 5}, and Des_{R}(β) = {1, 3, 5, 6}.

Hence maj(β) = 12, while maj_{R}(β) = 15. For the length functions we have that ℓ_{B}(β) = 10 + 13 = 23, while ℓ_{R}(β) = 7 + 8 = 15.

We denote by D_{n} the subgroup of B_{n} consisting of all the signed permutations having an even number of negative entries in their window notation, more precisely

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

It is usually called the even-signed permutation group. As a set of generators for D_{n} we take S_{D} := {s_{0}^{D}, s_{1}^{D}, …, s_{n−1}^{D}} where for i ∈ [n − 1]

s_{i}^{D} := s_{i}^{B} and s_{0}^{D} := [−2, −1, 3, …, n].

The following is a well-known combinatorial way to compute the length, and the descent set of γ ∈ D_{n} (see, e.g., [6, §8.2]):

ℓ_{D}(γ) = ℓ_{B}(γ) − neg(γ), and
Des_{D}(γ) = {i ∈ [0, n − 1] | γ(i) > γ(i + 1)},

where γ(0) := −γ(2). The cardinality of Des_{D}(γ) will be denoted by des_{D}(γ).

3. Connection between Reiner’s and Chow and Gessel’s identities

In the introduction, from Reiner’s and Chow and Gessel’s identities (1.5) and (1.4), we observed the equidistribution of the two pairs of statistics (des_{B}, fmaj) and (d_{R}, 2 maj − neg) over B_{n}. In this section we show that these two pairs are in fact identical. Therefore, the two identities are the same.

Proposition 3.1. For any β ∈ B_{n} we have

d_{R}(β) = des_{B}(β),  (3.1)
maj_{R}(β) = maj(β) + neg(β).  (3.2)

Proof. We first prove that d_{R}(β) = des_{B}(β) for every β ∈ B_{n}. Clearly it suffices to restrict our attention to the case of one descent.

a) If i ∈ Des_{R}(β) is such that β(i) > β(i + 1) > 0 or 0 > β(i) > β(i + 1), then clearly i ≠ n and i ∈ Des_{B}(β).

b) If i ∈ Des_{R}(β) is such that β(i) < 0 and β(i + 1) > 0, then there exists a k such that

0 ≤ k ≤ i − 1, 0 < β(1) < ⋯ < β(k) and β(k + 1) < ⋯ < β(i) < 0.

If k ≥ 1 then k ∈ Des_{B}(β); if k = 0 then β(1) < 0 and so 0 ∈ Des_{B}(β). Now we consider the major indices. It suffices to check the situation of one descent,

since the general case follows easily by induction. In the first following three cases we let i ∈ Des_{R}(β) be the only descent of β in [1, n − 1].

1) Suppose that β(i) > β(i + 1) > 0. Then 0 < β(1) < ⋯ < β(i), and there are h negative entries (0 ≤ h ≤ n − i − 1) such that

0 < β(i + 1) < ⋯ < β(n − h) and β(n − h + 1) < ⋯ < β(n) < 0.

If h = 0, then maj_{R}(β) − neg(β) = i = maj(β). If h > 0, then Des_{R}(β) = {i, n} while Des_{B}(β) = {i, n − h}. Thus maj_{R}(β) − neg(β) = (i + n) − h = maj(β).

2) Suppose that 0 > β(i) > β(i + 1). Then β(i + 1) < ⋯ < β(n) < 0, and there are k positive entries (0 ≤ k ≤ i − 1) such that

0 < β(1) < ⋯ < β(k) and β(k + 1) < ⋯ < β(i) < 0.

In this case maj_{R}(β) − neg(β) = (i + n) − (n − k) = k + i = maj(β).

3) Suppose that β(i) < 0 and β(i + 1) > 0. Then there exist 0 ≤ k ≤ i − 1 and 0 ≤ h ≤ n − i − 2 such that

0 < β(1) < ⋯ < β(k) and β(k + 1) < ⋯ < β(i) < 0, and

0 < β(i + 1) < ⋯ < β(n − h) and β(n − h + 1) < ⋯ < β(n) < 0. If h, k > 0, we obtain maj_{R}(β)−neg(β) = (i+n)−(h+i−k) = k+(n−h) = maj(β). The cases h = 0 and k = 0 are similar.

4) If n ∈ Des_{R}(β) is the only descent then there exists a k (0 ≤ k ≤ n − 1) such that

0 < β(1) < ⋯ < β(k) and β(k + 1) < ⋯ < β(n) < 0.

Hence maj_{R}(β) − neg(β) = n − (n − k) = k = maj(β). □

Remark 3.2. The first equality d_{R}(β) = des_{B}(β) can also be derived by using their geometric interpretations.

The next new description of the flag major index easily follows from Proposition 3.1.

Corollary 3.3. For every β ∈ B_{n} we have

fmaj(β) = 2 maj_{R}(β) − neg(β).

4. Encoding signed sequences

In this section we introduce a procedure encoding signed sequences by signed permutations and partitions, which will be used in the following sections. The basic idea can be found in Garsia and Gessel [10] and Reiner [14].

Let P_{n} be the set of non decreasing sequences of nonnegative integers (λ_{1}, λ_{2}, …, λ_{n}), i.e., partitions of length less than or equal to n.

Definition 4.1. Given a sequence f = (f_{1}, …, f_{n}) ∈ ℤ^{n} we define a pair (β, λ) ∈ B_{n}×P_{n}, where:

a) β is the unique signed permutation satisfying the following three conditions: 1) |f_{|β(1)|}| ≤ |f_{|β(2)|}| ≤ ⋯ ≤ |f_{|β(n)|}|,

2) sgn(β(i)) := sgn(f_{|β(i)|}),

3) If |f_{|β(i)|}| = |f_{|β(i+1)|}|, then β(i) < β(i + 1);

b) λ = (λ_{1}, …, λ_{n}) is the partition with

λ_{i} := |f_{|β(i)|}| − |{j ∈ Des_{B}(β) | j ≤ i − 1}| for 1 ≤ i ≤ n.

Let π(f) := β and λ(f) := λ.

Remark 4.2. The above sequence λ is clearly a partition since for all i ∈ [n], λ_{i} ≥ 0 and

λ_{i+1} − λ_{i} = |f_{|β(i+1)|}| − |f_{|β(i)|}| − χ(i ∈ Des_{B}(π)) ≥ 0 for i ∈ [n − 1].

Moreover, note that if i ∈ Des_{B}(β) then |f_{|β(i)|}| < |f_{|β(i+1)|}|, and 0 ∈ Des_{B}(β) if and only if f_{|β(1)|} < 0.

We introduce the following statistics on the set of signed sequences ℤ^{n}.

Definition 4.3. For f = (f_{1}, …, f_{n}) ∈ ℤ^{n} we let

max(f) := max{|f_{i}|},  |f| := ∑_{i=1}^{n} |f_{i}|,
ℓ_{B}(f) := ℓ_{B}(π(f)),  neg(f) := |{i ∈ [n] | f_{i} < 0}|.

Proposition 4.4. The map ψ : ℤ^{n} → B_{n} × P_{n} defined by (see Definition 4.1)

f ↦ (π(f), λ(f))

is a bijection. Moreover, if we let β := π(f) and λ := λ(f) then

max(f) = max(λ) + des_{B}(β),  (4.1)
|f| = |λ| + n des_{B}(β) − maj(β).  (4.2)

Proof. To see that ψ is a bijection we construct its inverse as follows. To each (β, λ) ∈ B_{n} × P_{n} associate the partition μ = (μ_{1}, …, μ_{n}) where

μ_{i} := λ_{i} + |{j ∈ Des_{B}(β) | j ≤ i − 1}|,

and define the sequence f = (f_{1}, …, f_{n}) ∈ ℤ^{n} by letting

f_{i} := sgn(β^{−1}(i)) μ_{|β^{−1}(i)|} for 1 ≤ i ≤ n.

It is easy to see that ψ(f) = (β, λ). Since λ is a partition, Equations (4.1) and (4.2) follow from

∑_{i=1}^{n} |{j ∈ Des_{B}(β)|j ≤ i − 1}| = ∑_{j∈Des_{B}(π)}(n − j) = n des_{B}(β) − maj(β).  □

Example 4.5. If f = (−4, 4, 1, −3, 6, 3, −4) then (|f_{|β(1)|}|, …, |f_{|β(7)|}|) = (1, 3, 3, 4, 4, 4, 6), so

π(f) := β = (3, −4, 6, −7, −1, 2, 5) ∈ B_{7}.

Moreover Des_{B}(β) = {1, 3}, so λ = (1, 2, 2, 2, 2, 2, 4). We obtain max(f) = 6 and des_{B}(β) = 2. Hence the identity (4.2) reads 25 = 15 + 14 − 4. Conversely, given the pair

([5, −3, 1, 2, −4], (0, 2, 2, 3, 3)) ∈ B_{5} × P_{5},

we find μ = (0, 3, 3, 4, 5) and f = (3, 4, −3, −5, 0).

5. Main identity

In this section we compute the generating function of (des_{B}, maj, ℓ_{B}, neg) over B_{n}. As special instances, we recover several known identities listed as remarks after the proof.

Theorem 5.1. We have

∑_{n≥0} \frac{u^{n}}{(t; q)_{n+1}[n̂]_{a,p}!} ∑_{β∈B_{n}} t^{des_{B}(β)}q^{maj(β)}p^{ℓ_{B}(β)}a^{neg(β)} = ∑_{k≥0} t^{k} ∏_{j=0}^{k−1} e[q^{j}u]_{p} · ê[q^{k}u]_{a,p}. (5.1)

Proof. The proof consists in computing in two different ways the series

∑_{f∈ℤ^{n}} t^{max(f)}q^{max(f)·n−|f|}p^{ℓ_{B}(f)}a^{neg(f)}.

We need the following preliminary result that can be proved as in [14, Lemma 3.1]. For \underline{n} = (n_{0}, n_{1}, …, n_{k}) ∈ ℕ^{k+1} a composition of n, i.e., n = n_{0} + ⋯ + n_{k}, we let

ℤ^{n}(\underline{n}) := \{f ∈ ℤ^{n} | #\{i : |f_{i}| = j\} = n_{j}\}.

Then

∑_{f∈ℤ^{n}(\underline{n})}p^{ℓ_{B}(f)}a^{neg(f)} = [\begin{matrix}n \\ n_{0}, n_{1}, …, n_{k} \end{matrix}]_{p} \frac{(−ap; p)_{n}}{(−ap; p)_{n_{0}}} .  (5.2)

A version of (5.2) for the more general case of wreath products is given in [5, Lemma 4.2]. We can now start our computation:

∑_{f∈ℤ^{n}|max(f)≤k}q^{k·n−|f|}p^{ℓ_{B}(f)}a^{neg(f)} = ∑_{n_{0}+···+n_{k}=n} q^{k ∑_{i} n_{i}−∑_{i} in_{i}} ∑_{f∈ℤ^{n}(\underline{n})}p^{ℓ_{B}(f)}a^{neg(f)}

= ∑_{n_{0}+···+n_{k}=n} [\begin{matrix}n \\ n_{0}, n_{1}, …, n_{k} \end{matrix}]_{p} \frac{(−ap; p)_{n}}{(−ap; p)_{n_{0}}} q^{∑_{i} n_{i}(k−i)}

= [n̂]_{a,p}! · ⟨u^{n}⟩ (e[u]_{p}e[qu]_{p} ⋯ e[q^{k−1}u]_{p}ê[q^{k}u]_{a,p}) ,

where the notation ⟨u^{n}⟩f(u) stands for the coefficient of u^{n} in f(u).

Using the formula

(1 − t) ∑_{k≥0} a_{≤k}t^{k} = ∑_{k≥0}(a_{≤k} − a_{≤k−1})t^{k} = ∑_{k≥0} a_{k}t^{k},  (5.3)

where a_{≤k} = a_{0} + ⋯ + a_{k}, we derive immediately

∑_{f∈ℤ^{n}} t^{max(f)}q^{max(f)·n−|f|}p^{ℓ_{B}(f)}a^{neg(f)} = (1 − tq^{n}) ∑_{k≥0} t^{k} ∑_{f∈ℤ^{n}|max(f)≤k}q^{kn−|f|}p^{ℓ_{B}(f)}a^{neg(f)}.

Therefore

∑_{n≥0} \frac{u^{n}}{[n̂]_{a,p}!(1 − tq^{n})} ∑_{f∈ℤ^{n}} t^{max(f)}q^{max(f)·n−|f|}p^{ℓ_{B}(f)}a^{neg(f)} = ∑_{k≥0} t^{k} ∏_{j=0}^{k−1} e[q^{j}u]_{p} · ê[q^{k}u]_{a,p}. (5.4)

On the other hand, from the bijection ψ, and Equations (4.1) and (4.2) in Proposition 4.4, it follows that

∑_{f∈ℤ^{n}|π(f)=β} t^{max(f)}q^{|f|} = ∑_{λ} t^{max(λ)+des_{B}(β)}q^{|λ|+n des_{B}(β)−maj(β)}

= \frac{t^{des_{B}(β)}q^{∑_{i∈Des_{B} (β)}(n−i)}}{(tq; q)_{n}} .  (5.5)

Replacing q by q^{−1} and t by tq^{n} in (5.5) we get

∑_{f∈ℤ^{n}|π(f)=β} t^{max(f)}q^{max(f)·n−|f|} = \frac{t^{des_{B}(β)}q^{maj(β)}}{(t; q)_{n}} .  (5.6)

Hence

∑_{f∈ℤ^{n}} t^{max(f)}q^{max(f)·n−|f|}p^{ℓ_{B}(f)}a^{neg(f)} = ∑_{β∈B_{n}} p^{ℓ_{B}(β)}a^{neg(β)} ∑_{f∈ℤ^{n}|π(f)=β} t^{max(f)}q^{max(f)·n−|f|}

= ∑_{β∈B_{n}} \frac{t^{des_{B}(β)}q^{maj(β)}p^{ℓ_{B}(β)}a^{neg(β)}}{(t; q)_{n}} .  (5.7)

By comparing (5.4) and (5.7) the result follows. □

Remark 5.2 (Chow and Gessel’s identities). By letting p = 1, and substituting q ← q^{2}, a ← q, and u ← (1 + q)u in (5.1) we obtain Chow and Gessel’s formula (1.4). Letting p = 1 and replacing u by (1 + a)u in (5.1), then extracting the coefficient of u^{n}/n! yields another result of Chow and Gessel [9, Equation (26)]

\frac{∑_{β∈B_{n}} t^{des_{B}(β)}q^{maj(β)}a^{neg(β)}}{(t; q)_{n+1}} = ∑_{k≥0}([k + 1]_{q} + a[k]_{q})^{n}t^{k}.  (5.8)

This result also follows from (1.3) and Proposition 3.1. Indeed, substituting a ← aq^{−1}, p ← 1 and u ← (1 + aq^{−1})u in (1.3) we get

∑_{n≥0} \frac{∑_{β∈B_{n}} t^{d(β)}q^{maj_{R}(β)−neg(β)}a^{neg(β)}}{(t; q)_{n+1}} \frac{u^{n}}{n!} = ∑_{k≥0} t^{k} exp ([k + 1]_{q} + a[k]_{q}) u.  (5.9)

In view of Proposition 3.1, Equation (5.8) follows then by extracting the coefficient of u^{n}/n! in (5.9).

Since the right-hand side of (5.8) is invariant under the substitution q → 1/q, a → a/q and t → tq^{n} we obtain immediately the following result:

∑_{β∈B_{n}} t^{des_{B}(β)}q^{maj(β)}a^{neg(β)} = ∑_{β∈B_{n}} t^{des_{B}(β)}q^{n des_{B}(β)−maj(β)−neg(β)}a^{neg(β)}.

Remark 5.3 (Reiner and Brenti’s identities). Comparing the right-hand sides of (1.3) and (5.1) we conclude that the distributions of the two quadruples of statistics are different. However, if we set q = 1 in (5.1) we obtain

∑_{n≥0} \frac{u^{n}}{(1 − t)^{n+1}} \frac{∑_{β∈B_{n}} t^{des_{B}(β)}p^{ℓ_{B}(β)}a^{neg(β)}}{[n̂]_{a,p}!} = \frac{1}{1 − te[u]_{p}} · ê[u]_{a,p},  (5.10)

and comparing with Reiner’s equation (1.3) with q = 1 we see that (d_{R}, ℓ_{R}, neg) and (des_{B}, ℓ_{B}, neg) are equidistributed over B_{n}. By letting p = 1 in (5.10) we recover a formula of Brenti [7, (14)]:

∑_{n≥0} ∑_{β∈B_{n}} t^{des_{B}(β)}a^{neg(β)} \frac{u^{n}}{n!} = \frac{(1 − t)e^{u(1−t)}}{1 − te^{(1+a)(1−t)u}} .

Remark 5.4 (Gessel and Roselle’s identity for B_{n}). To compute the generating function of major index and length we proceed as follows. Setting a = 1 in equation (5.1) yields

∑_{n≥0} \frac{(1 − p)^{n}u^{n}}{(t; q)_{n+1}(p^{2}; p^{2})_{n}} ∑_{β∈B_{n}} t^{des_{B}(β)}q^{maj(β)}p^{ℓ_{B}(β)}
= ∑_{k≥0} t^{k}e[u]_{p}e[qu]_{p} ⋯ e[q^{k−1}u]_{p}ê[q^{k}u]_{1,p}.  (5.11)

By multiplying both sides of (5.11) by (1 − t), and then by sending t → 1 we obtain

∑_{n≥0} \frac{((1 − p)u)^{n}}{(q; q)_{n}(p^{2}; p^{2})_{n}} ∑_{β∈B_{n}} q^{maj(β)}p^{ℓ_{B}(β)} = ∏_{i≥0} e[q^{i}u]_{p}.

Replacing u by u/(1 − p) and applying q-binomial formula e[u/(1 − p)]_{p} = ∏_{j≥0} \frac{1}{1−p^{j}u} we get the following B_{n}-analogue of an identity of Gessel and Roselle (see [11, Theorem 8.5] and the historical note after Theorem 4.3 in [3]):

∑_{n≥0} \frac{∑_{β∈B_{n}} q^{maj(β)}p^{ℓ_{B}(β)}}{(q; q)_{n}(p^{2}; p^{2})_{n}} u^{n} = ∏_{i,j≥0} \frac{1}{1 − up^{i}q^{j}} .  (5.12)

We refer the reader to [4, Proposition 5.4] for a different generalization of this identity.

6. The D_{n}-case.

The aim of this section is to obtain a generating series for the four-variate distribution of descents, major index, length and number of negative entries over the group D_{n} by using the encoding of Section 4. This time we are unable to get a nice identity as in the B_{n}-case; this is not so surprising as will be explained in Section 7.

Let ℤ_{e}^{n} be the subset of sequences in ℤ^{n} with an even number of negative entries. For f ∈ ℤ_{e}^{n} Definition 4.3 is still valid and we let

ℓ_{D}(f) := ℓ_{D}(π(f)),

where π(f) ∈ D_{n} is the even signed permutation defined in Definition 4.1.

For \underline{n} = (n_{0}, n_{1}, …, n_{k}) a composition of n, we define

ℤ_{e}^{n}(\underline{n}) = \{f ∈ ℤ_{e}^{n} | #\{i : |f_{i}| = j\} = n_{j}\}.

We have the following lemma.

Lemma 6.1. Let \underline{n} = (n_{0}, n_{1}, …, n_{k}) be a composition of n. Then

∑_{f∈ℤ_{e}^{n}(\underline{n})}p^{ℓ_{D}(f)}a^{neg(f)} = \frac{1}{2} [\begin{matrix}n \\ n_{0}, n_{1}, …, n_{k} \end{matrix}]_{p} · \{\frac{(a; p)_{n}}{(a; p)_{n_{0}}} + \frac{(−a; p)_{n}}{(−a; p)_{n_{0}}} \} .

Proof. It is clear that

∑_{f∈ℤ_{e}^{n}(\underline{n})}p^{ℓ_{D}(f)}a^{neg(f)} = \frac{1}{2} [ ∑_{f∈ℤ^{n}(\underline{n})}p^{ℓ_{D}(f)}a^{neg(f)} + ∑_{f∈ℤ^{n}(\underline{n})}p^{ℓ_{D}(f)}(−a)^{neg(f)}] .

ON SOME ANALOGUES OF DESCENT NUMBERS AND MAJOR INDEX FOR B_{n} 11

By definition we have that ℓ_{B}(γ) = ℓ_{D}(γ) + neg(γ), so by (5.2) with a ← a/p we get

∑_{f∈ℤ^{n}(\underline{n})}p^{ℓ_{D}(f)}a^{neg(f)} = [\begin{matrix}n \\ n_{0}, n_{1}, …, n_{k} \end{matrix}]_{p} · \frac{(−a; p)_{n}}{(−a; p)_{n_{0}}} .

The result follows by replacing a by −a in the above formula. □

In order to obtain our identity, we want to compute the following generating series in two different ways:

∑_{f∈ℤ_{e}^{n}} t^{max(f)}q^{max(f)·n−|f|}p^{ℓ_{D}(f)}a^{neg(f)}.

First of all we have

∑_{f∈ℤ_{e}^{n}|max(f)≤k}q^{k·n−|f|}p^{ℓ_{D}(f)}a^{neg(f)} = ∑_{n_{0}+···+n_{k}=n} q^{∑_{i} n_{i}(k−i)} ∑_{f∈ℤ_{e}^{n}} p^{ℓ_{D}(f)}a^{neg(f)}

= \frac{1}{2} ∑_{n_{0}+···+n_{k}=n} \frac{[n]_{p}!}{[n_{0}]_{p}! ⋯ [n_{k}]!_{p}} q^{∑_{i} n_{i}(k−i)} \{\frac{(a; p)_{n}}{(a; p)_{n_{0}}} + \frac{(−a; p)_{n}}{(−a, p)_{n_{0}}} \}

= \frac{1}{2}[n]_{p}!⟨u^{n}⟩ (e[u]_{p}e[uq]_{p} ⋯ e[uq^{k−1}]_{p} \{(a; p)_{n}ê[uq^{k}]_{−a/p,p} + (−a; p)_{n}ê[uq^{k}]_{a/p,p}\}) .

Using the formula (5.3) we derive immediately

∑_{f∈ℤ_{e}^{n}} t^{max(f)}q^{max(f)·n−|f|}p^{ℓ_{D}(f)}a^{neg(f)} = (1 − tq^{n}) ∑_{k≥0} t^{k} ∑_{f∈ℤ_{e}^{n}|max(f)≤k}q^{k·n−|f|}p^{ℓ_{D}(f)}a^{neg(f)}.

Therefore we obtain

\frac{∑_{f∈ℤ_{e}^{n}} t^{max(f)}q^{max(f)·n−|f|}p^{ℓ_{D}(f)}a^{neg(f)}}{(1 − tq^{n})[n]_{p}!}  (6.1)

= \frac{1}{2} ∑_{k≥0} t^{k}⟨u^{n}⟩ \{e[u]_{p}e[uq]_{p} ⋯ e[uq^{k−1}]_{p} ((a; p)_{n}ê[uq^{k}]_{−a/p,p} + (−a; p)_{n}ê[uq^{k}]_{a/p,p})\} .

On the other hand, we decompose D_{n} as the disjoint union of the three sets

D_{n}^{+} := {γ ∈ D_{n} | 0 ∉ Des_{D}(γ) and γ(1) < 0},
D_{n}^{−} := {γ ∈ D_{n} | 0 ∈ Des_{D}(γ) and γ(1) > 0},
D_{n}^{0} := D_{n} \ (D_{n}^{+} ∪ D_{n}^{−}).

We have the following lemma. Lemma 6.2. For γ ∈ D_{n} we have

∑_{f∈ℤ_{e}^{n}|π(f)=γ} t^{max(f)}q^{max(f)·n−|f|} = \frac{D_{n}^{γ}(t, q)}{(t; q)_{n}},

where

D_{n}^{γ}(t, q) := \{ \begin{matrix}t^{des_{D}(γ)+1}q^{maj(γ)}, & if γ ∈ D_{n}^{+}; \\ t^{des_{D}(γ)−1}q^{maj(γ)}, & if γ ∈ D_{n}^{−}; \\ t^{des_{D}(γ)}q^{maj(γ)}, & if γ ∈ D_{n}^{0}. \end{matrix}

Proof. First of all, for any γ ∈ D_{n} we have {f ∈ ℤ_{e}^{n} | π(f) = γ} = {f ∈ ℤ^{n} | π(f) = γ}. Suppose that γ ∈ D_{n}^{+}, then 0 ∈ Des_{B}(γ) since γ(1) < 0, but 0 ∉ Des_{D}(γ). It follows from Equation (5.6) that

∑_{f∈ℤ^{n}|π(f)=γ} t^{max(f)}q^{max(f)·n−|f|} = \frac{t^{des_{B}(γ)}q^{maj(γ)}}{(t; q)_{n}} = \frac{t^{des_{D}(γ)+1}q^{maj(γ)}}{(t; q)_{n}} .

The other cases are similar. □

For γ ∈ D_{n} set

w(γ) := t^{des_{D}(γ)}q^{maj(γ)}p^{ℓ_{D}(γ)}a^{neg(γ)}.

It follows from Lemma 6.2 that

∑_{f∈ℤ_{e}^{n}} t^{max(f)}q^{max(f)·n−|f|}p^{ℓ_{D}(f)}a^{neg(f)} = ∑_{γ∈D_{n}} p^{ℓ_{D}(γ)}a^{neg(γ)} ∑_{f∈ℤ_{e}^{n}|π(f)=γ} t^{max(f)}q^{max(f)·n−|f|}

= \frac{1}{(t; q)_{n}} ( ∑_{γ∈D_{n}^{0}} w(γ) + \frac{1}{t} ∑_{γ∈D_{n}^{−}} w(γ) + t ∑_{γ∈D_{n}^{+}} w(γ)) .

By comparing the above equation with Equation (6.1) we obtain the following identity.

Theorem 6.3.

∑_{γ∈D_{n}^{0}} \frac{w(γ)}{(t; q)_{n}} + \frac{1}{t} ∑_{γ∈D_{n}^{−}} \frac{w(γ)}{(t; q)_{n}} + t ∑_{γ∈D_{n}^{+}} \frac{w(γ)}{(t; q)_{n}}

= \frac{1}{2} ∑_{k≥0} t^{k}⟨u^{n}⟩ \{e[u]_{p}e[uq]_{p} ⋯ e[uq^{k−1}]_{p} ((a; p)_{n}ê[uq^{k}]_{−a/p,p} + (−a; p)_{n}ê[uq^{k}]_{a/p,p})\} . (6.2)

If a = 1, letting t → 1 in the above identity yields a D_{n}-analogue of Gessel and Roselle’s identity (see (5.12)):

1 + ∑_{n≥1} u^{n} \frac{∑_{γ∈D_{n}} q^{maj(γ)}p^{ℓ_{D}(γ)}}{(−p; p)_{n−1}(q; q)_{n−1}} = ∏_{i,j≥0} \frac{1}{1 − (1 − p)up^{i}q^{j}} .  (6.3)

7. Final Remarks

Note that Brenti [7, Proposition 4.3] computed the generating function of (des_{D}, neg), and Reiner [16, Theorem 7] that of (des_{D}, ℓ_{D}) over D_{n}. Their formulas are much more involved than the corresponding B_{n}-cases, even in the one-variable case, see Equation (1.6). Reiner gave also a method to compute the distribution of (des_{D}, ℓ_{D}, neg) over D_{n}. However, it does not seem that his method allows to include the statistic major index in the computation.

The restriction of the bijection ψ (defined in Proposition 4.4) to ℤ_{e}^{n} is not a well defined map from ℤ_{e}^{n} to D_{n} × P_{n}. For example, consider f = (0, −3, −4) ∈ ℤ_{e}^{3}. Then π(f) = [1, −2, −3] ∈ D_{3}, and λ(f) = (−1, 1, 1) which is not a partition. Hence the following question naturally arises.

Question 7.1. Is there a parametrization of the elements of ℤ_{e}^{n} which reduces the lefthand side of Equation (6.2) to a single sum with a simpler right-hand side ?

Hopefully, the desired equation, for p = a = 1, should provide a nice q-analogue of Brenti’s identity (1.6). This problem was also raised in [9, §5]. Recently Mendes and Remmel [13] computed some generating series over B_{n} and D_{n}, closely related to ours. Unfortunately, their computations do not answer the above question.

In [5] we study the distribution of several statistics over the wreath product of a symmetric group with a cyclic group. In particular, we give an extension of Theorem 5.1.

References

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

[2] R. M. Adin, F. Brenti, Y. Roichman, Descent numbers and major indices for the hyperoctahedral group, Adv. in Appl. Math. 27 (2001), 210–224.

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

[4] R. Biagioli, Equidistribution of negative statistics and quotients of Coxeter groups of type B and D, Adv. in Appl. Math. 41 (2008), 378.–394.

[5] R. Biagioli and J. Zeng, Enumerating wreath products via Garsia–Gessel bijections, available at

arχiv:0909.4009.v1.

[6] A. Björner and F. Brenti, Combinatorics of Coxeter Groups, G.T.M. 231, Springer–Verlag, New York, 2005.

[7] F. Brenti, q-Eulerian polynomials arising from Coxeter groups, European J. Combin. 15 (1994), no. 5, 417–441.

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

[9] C.-O. Chow and I. M. Gessel, On the descent numbers and major indices for the hyperoctahedral group, Adv. in Appl. Math. 38 (2007), 275–301.

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

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

[12] P. A. MacMahon, Combinatorial Analysis, Chelsea, 1960. Originally published in two volumes by Cambridge Univ. Press, 1915–16.

[13] A. Mendes and J. Remmel, Descents, inversions, and major indices in permutation groups, Discrete Math. 308 (2008), 2509–2524.

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

[15] V. Reiner, Signed posets, J. Combin. Theory Ser. A 62 (1993), 324–360.

[16] V. Reiner, The distribution of descents and length in a Coxeter group, Electron. J. Combin. 2 (1995), Research Paper 25.

[17] V. Reiner, Descents and one-dimensional characters for classical Weyl groups, Discrete Math. 140 (1995), 129–140.

Université de Lyon, Université Lyon 1, Institut Camille Jordan, UMR 5208 du CNRS, F-69622, Villeurbanne Cedex, France

E-mail address: biagioli@math.univ-lyon1.fr, zeng@math.univ-lyon1.fr