q-Eulerian polynomials arising from Coxeter groups

Francesco Brenti^{1} Universitá degli Studi di Perugia Dip.to di Matematica Via Vanvitelli 1 06100 Perugia, Italy

Abstract

We study the polynomials obtained by enumerating a finite Coxeter group by number of descents. The type A case gives rise to the familiar Eulerian polynomials while the B and D cases provide two new q-analogues. Various recursion relations, generating functions, and unimodality properties are derived, which generalize and unify earlier results of Dolgachev, Lunts, Stanley, and Stembridge.

1 Introduction

In this work we study the polynomials, P (W; x), obtained by enumerating a (finite) Coxeter system (W, S) with respect to the number of descents (see, section 2 for definitions). It is easy to see that it is enough to study these polynomials for irreducible Coxeter systems. While for type A these polynomials are known to coincide with classical Eulerian polynomials (see, e.g., [8] or [24]), and thus have been extensively studied from a combinatorial point of view (see, e.g., [9]), only some results of a combinatorial nature are known for type B (see, [8], [17], [15]), and very little is known for type D (see [25], and [16]). In this paper we show that essentially all of the classical results for Eulerian polynomials have analogues for these other polynomials, and that it is possible to define natural q-analogues of them which are also q-analogues of the Eulerian polynomials. Our results generalize and unify previous results of Dolgachev, Lunts, Stanley and Stembridge , and generalize the classical theory of Eulerian numbers and polynomials. As a by-product we obtain a combinatorial proof of a simple relation between these three types of polynomials and we are led to several conjectures about them.

1This work was carried out while the author was visiting the Mittag-Leffler Institute in Djursholm, Sweden.

The polynomials P (W; x) are not only of enumerative interest but also of geometric significance. In fact, it is known (see Theorem 2.3) that P (W; x) is also the generating function of the h-vector of the Coxeter complex associated to (W, S). Since this Coxeter complex is isomorphic to the boundary complex of a simplicial convex polytope (see, e.g., [1], Proposition 2.3.9) there follows from standard results in the theory of toric varieties (see, e.g., [14], Chapter 2, and [7], Theorem 10.8) that this h-vector equals the sequence of even dimensional Betti numbers of certain toric projective varieties (which have been studied, e.g., in [8] and [24]) associated to the polytope, and that P (W; x^{2}) is the Poincaré polynomial of these varieties. In light of this, it would be interesting to have geometric proofs of all the results in this work.

The organization of the paper is as follows. In the next section we collect the definitions, notation and preliminary results that will be used in the rest of this work. In §3 we study the polynomials P (W; x) when W is a Coxeter group of type B. It turns out that one can define q-analogues of these polynomials that have the additional property of reducing, when q = 0, to the ordinary Eulerian polynomials. We show that many results on Eulerian polynomials generalize to these q-polynomials. In particular, we obtain recurrence relations, generating functions, a “q-Worpitzky identity”, unimodality and total positivity properties, and several combinatorial interpretations for these q-Eulerian polynomials. In §4 we study the polynomials P (W; x) when W is a Coxeter group of type D. Again, it is possible to define q-analogues of these polynomials which reduce, when q = 0, to the Eulerian polynomials. The main result of this section is a simple relation between these q-Eulerian polynomials and those introduced in §3. This relation generalizes one found by Stembridge and allows us to obtain analogues of most (but not all) of the results in §3. Finally, in §5, we discuss some conjectures and open problems, both of a geometric and combinatorial character, arising from our work.

2 Notation 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, …} and N=^{def}P ∪{0}; for a ∈N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅). The cardinality of a set A will be denoted by |A|.

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, d(σ)) the number of inversions (respectively, descents) of σ.

Given a set T we will let S(T) be the set of all bijections π : T → T, and S_{n} =^{def} S([n]). For n ∈ P and 1 ≤ k ≤ n the number

A(n, k) =^{def} |{π ∈ S_{n} : d(π) = k − 1}|

is called an Eulerian number, the polynomial

A_{n}(x) =^{def} ∑_{k=1}^{n} A(n, k) x^{k}

is called the n-th Eulerian polynomial. Eulerian numbers and polynomials have been widely studied (see, e.g., [9]), for convenience we will let A_{0}(x) =^{def} 1.

By a simplicial complex we will mean a collection of sets Δ with the property that if A ∈ Δ and B ⊆ A then B ∈ Δ. We call the elements of Δ the faces of Δ. For S ∈ Δ, the dimension of S is |S| − 1. The dimension of Δ is max {|A| − 1 : A ∈ Δ}. Given a simplicial complex Δ of dimension d − 1 we let f_{i−1}(Δ) =^{def} |{A ∈ Δ : |A| = i}|, for i = 0, …, d, and call f(Δ) =^{def} (f_{−1}(Δ), f_{0}(Δ), f_{1}(Δ), …, f_{d−1}(Δ)) the f-vector of Δ. We then define the h-vector of Δ, h(Δ) =^{def} (h_{0}(Δ), h_{1}(Δ), …, h_{d}(Δ)), by letting

∑_{i=0}^{d} h_{i}(Δ)x^{d−i} =^{def} ∑_{i=0}^{d} f_{i−1}(Δ)(x − 1)^{d−i} .  (1)

Clearly, knowledge of the f-vector of Δ is equivalent to the knowledge of its h-vector.

Given p ∈ P, we will sometimes use the basis of the vector space V_{p} of real polynomials of degree ≤ p consisting of the polynomials \{(\begin{matrix}x+p−i \\ p \end{matrix})\}_{i=0,...,p}. The reason why this basis is often used in enumerative combinatorics lies in the following result which is, essentially, a restatement of the binomial theorem (see, e.g., [21], p.16).

Theorem 2.1 Let A(x) be a real polynomial of degree d. Then

A(x) = ∑_{i=0}^{d} b_{i} (\begin{matrix}x+d−i \\ d \end{matrix})

if and only if

∑_{n≥0} A(n) x^{n} = \frac{∑_{i=0}^{d} b_{i} x^{i}}{(1 − x)^{d+1}} ,

as formal power series in R[[x]].

A proof of the preceding result can be found in [21], remark (d), p. 209.

A sequence {a_{0}, a_{1}, …, a_{d}} (of real numbers) is log-concave if a_{i}^{2} ≥ a_{i−1}a_{i+1} for i = 1, …, d − 1. It is unimodal if there exists an index 0 ≤ j ≤ d such that a_{i} ≤ a_{i+1} for i = 0, …, j − 1 and a_{i} ≥ a_{i+1} for i = j, …, d − 1. It has no internal zeros if there are not three indices 0 ≤ i < j < k ≤ d such that a_{i}, a_{k} ≠ 0 and a_{j} = 0. It is symmetric if a_{i} = a_{d−i} for i = 0, …, ⌊\frac{d}{2}⌋. A polynomial ∑_{i=0}^{d} a_{i} x^{i} is logconcave (respectively, unimodal, with no internal zeros, symmetric) if the sequence {a_{0}, a_{1}, …, a_{d}} has the corresponding property. It is well known that if ∑_{i=0}^{d} a_{i} t^{i} is a polynomial with nonnegative coefficients and with only real zeros, then the sequence {a_{0}, a_{1}, …, a_{d}} is log-concave and unimodal, with no internal zeros (see, e.g., [3], or [6], Thm. B, p.270). If p(x) is a symmetric unimodal polynomial then we let C(p) =^{def} (deg (p) + mult (0; p))/2 where mult (0, p) is the multiplicity of 0 as a zero of p. We call C(p) the center of symmetry of p (x). So, for example, C(x^{2} + 3x^{3} + x^{4}) = 3 and C(1 + x) = \frac{1}{2}.

We now recall a result that relates the basis \{(\begin{matrix}x+p−i \\ p \end{matrix})\}_{i=0,...,p} with polynomials having only real zeros.

Theorem 2.2 Let

A(x) = ∑_{i=0}^{d} b_{i} (\begin{matrix}x+d−i \\ d \end{matrix})

be a polynomial of degree d. Suppose that A(x) has all its zeros in the interval [−1, 0]. Then the polynomial ∑_{i=0}^{d} b_{i} x^{i} has only real zeros.

Theorem 2.2 is non-trivial and we refer the reader to [3], Thm.4.4.4, for its proof.

We will follow [11] for general Coxeter group notation and terminology. All Coxeter groups in this paper are assumed to be finite. Given a Coxeter system (W, S) and σ ∈ W we denote by l_{W} (σ) the length of σ in W, with respect to S, and we let

D_{W} (σ) =^{def} {s ∈ S : l_{W} (σ s) < l_{W} (σ)} ,

and

d_{W} (σ) = |D_{W} (σ)| .

We call D_{W} (σ) the descent set of σ and say that σ has d_{W} (σ) W -descents. If (W, S) is a Coxeter system of type A_{n} we will write simply l_{A}(σ), d_{A}(σ), etc..., instead of l_{A_{n}}(σ), d_{A_{n}}(σ), etc..., and similarly for type B_{n} and D_{n}. Given a Coxeter system (W, S) we will denote by e the identity of W. Recall that the Coxeter complex of a Coxeter system (W, S) is the simplicial complex Δ(W, S) which is the nerve of the covering of W by left cosets of maximal parabolic subgroups. We denote by Ch(Δ(W, S)) the set of chambers of Δ(W, S) (i.e., the set of all maximal faces of Δ(W, S)).

Now let (W, S) be a finite Coxeter system and Δ(W, S) be the associated Coxeter complex. The following result follows from Theorems 1.6, 2.1, and Proposition 1.2 of [2].

Theorem 2.3 Let (W, S) be a finite Coxeter system of rank n and Δ(W, S) be the associated Coxeter complex. Then

h (Δ(W, S)) = (d_{0}(W), …, d_{n}(W))

where d_{i}(W) =^{def} |{σ ∈ W : d_{W} (σ) = i}|, for i = 0, …, n.

It is well known (see, e.g., [1], Proposition 2.3.9) that Δ(W, S) is isomorphic to the boundary complex of a simplicial convex polytope and (see, e.g., [22], Theorem 20) that the h-vector of a simplicial convex polytope is always a symmetric unimodal sequence, therefore Theorem 2.3 and Proposition 2.3.9 of [1] imply the following result, which is, in a sense, “dual” to Theorem 19 of [22].

Theorem 2.4 Let (W, S) be a finite Coxeter system of rank n. Then the polynomial

∑_{σ∈W} x^{d_{W} (σ)}

is symmetric and unimodal with center of symmetry at ⌊\frac{n}{2}⌋. □

Given a (finite) Coxeter system (W, S) we let

P (W; x) =^{def} ∑_{σ∈W} x^{d_{W} (σ)} .  (2)

3 q-Eulerian polynomials of type B

In this section we examine in detail a natural q-analogue of P (W; x) in the case that W is a Coxeter group of type B_{n}. We slightly abuse notation by denoting this group by B_{n}. We regard B_{n} as the group of all signed permutations on [n]. More precisely, we view each element σ ∈ B_{n} as a function σ : [n] → [−n, n]\{0} such that |σ| ∈ S_{n} (where |σ|(i) =^{def} |σ(i)| for i ∈ [n]). We write σ = a_{1} … a_{n} (or, sometimes, σ = [a_{1}, …, a_{n}]) if a_{i} = σ(i) for i ∈ [n], and call this the one-line notation of σ. We call an element σ ∈ B_{n} a signed cycle if |σ| is a cycle. It is clear that each σ ∈ B_{n} can be expressed as a product of disjoint signed cycles, and it will be convenient to have a canonical way of writing such a product. We say that σ ∈ B_{n} is written in standard disjoint cycle form if:

i) each cycle is written with its largest (in absolute value) element first;

ii) the cycles are written in increasing order of the absolute values of their first el ements.

For example, if σ = [−3, 5, 1, −7, 2, 8, −6, −4] then the standard disjoint cycle form of σ is σ = (−3, 1) (5, 2) (8, −4, −7, −6).

As a set of Coxeter generators for B_{n} we take S =^{def} {s_{1}, …, s_{n}} where s_{i} =^{def}

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

Our first step is that of obtaining an explicit combinatorial description of the polynomial P (B_{n}; x). In order to do this it is necessary first to obtain a simple combinatorial description of the length function of B_{n}. For σ ∈ B_{n} we let

inv_{B}(σ) =^{def} inv (σ(1), …, σ(n)) − ∑_{{j∈[n]: σ(j)<0}} σ(j) .  (3)

For example, if σ = [−3, 2, 7, −1, −6, 5, −4] then inv_{B}(σ) = 12+(3+1+6+4) = 26. Note that inv_{B}(σ) = inv (σ) if and only if σ ∈ S_{n}.

Proposition 3.1 Let n ∈ P. Then

l_{B}(σ) = inv_{B}(σ) ,  (4)

for all σ ∈ B_{n}.

Proof. We prove first that

inv_{B} (σ) ≤ l_{B}(σ)  (5)

for all σ ∈ B_{n}. Let v ∈ B_{n}. Now, it is easy to see that inv (v s_{n}) = inv (v) − v(1) + sgn (v(1)), and it therefore follows from (3) that

inv_{B} (v s_{n}) = inv_{B} (v) + sgn (v(1)) .  (6)

On the other hand, for i ∈ [n − 1] we clearly have that

inv_{B} (v s_{i}) = \{ \begin{matrix}inv_{B} (v) + 1 , & if v(i) < v(i + 1), \\ inv_{B} (v) − 1 , & if v(i) > v(i + 1). \end{matrix}  (7)

Since inv_{B} (e) = l_{B}(e) = 0, (6) and (7) prove (5), as claimed.

We now prove (4) by induction on inv_{B} (σ). If inv_{B} (σ) = 0 then σ = 12 … n = e and (4) clearly holds. So let t ∈ N and v ∈ B_{n} be such that inv_{B} (v) = t + 1. Then v ≠ e and hence there exists s ∈ S such that inv_{B} (v s) = t (otherwise (6) and (7) would imply that 0 < v(1) < v(2) < … < v(n) and hence that v = e). This, by the induction hypothesis, implies that l_{B}(v s) = t and hence that l_{B}(v) ≤ t + 1. Therefore l_{B}(v) ≤ inv_{B} (v) and this, by (5) concludes the induction step and hence the proof. □

Other (more complicated) combinatorial descriptions of the length function of B_{n} appear in [19], §5, eq.(6), [16], §2, and [17], Proposition 2.1.

As a consequence of Proposition 3.1 we obtain the following simple combinatorial description of the number of descents of an element of B_{n}.

Corollary 3.2 Let n ∈ P and v ∈ B_{n}. Then

d_{B}(v) = |{i ∈ [n] : v(i − 1) > v(i)}| ,  (8)

where v(0) =^{def} 0.

Proof. Fix n ∈ P and v ∈ B_{n}. By our definitions and Proposition 3.1 we have that

d_{B}(v) =^{def} |{s ∈ S : l_{B}(v s) < l_{B}(v)}|
= |{s ∈ S : inv_{B} (v s) < inv_{B} (v)}| ,

and the thesis follows from (6) and (7). □

Given σ ∈ B_{n} we let

N(σ) =^{def} |{i ∈ [n] : σ(i) < 0}| ,  (9)

and P (σ) =^{def} n − N(σ). We note the following consequence of (9) and Proposition 3.1, which was also observed (independently) by V. Reiner in [17] (see Proposition 2.2).

Proposition 3.3 For n ∈ P we have that

∑_{σ∈B_{n}} x^{l_{B}(σ)} q^{N(σ)} = ∏_{i=1}^{n}(1 + x + … + x^{i−1})(1 + qx^{i}) .

Proof. We proceed by induction on n ∈ P. Let σ ∈ B_{n−1} and let σ_{i} =^{def} [σ(1), …, σ(i−

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

1)]), for i ∈ [n]. Then it follows easily from (3) and Proposition 3.1 that

l_{B}(σ_{i}) = l_{B}(σ) + n − i , l_{B}(σ_{−i}) = l_{B}(σ) + i − 1 + n

for i ∈ [n]. Hence we conclude that

∑_{w∈B_{n}} x^{l_{B}(w)} q^{N(w)} = ∑_{i=1}^{n} ∑_{σ∈B_{n−1}}(x^{l_{B}(σ_{i})} q^{N(σ_{i})} + x^{l_{B}(σ_{−i})} q^{N(σ_{−i})})
= ∑_{σ∈B_{n−1}} ∑_{i=1}^{n} x^{l_{B}(σ)} q^{N(σ)}(x^{n−i} + q x^{n+i−1})
= ∑_{σ∈B_{n−1}} x^{l_{B}(σ)} q^{N(σ)} (1 + qx^{n})(1 + x + … + x^{n−1}) ,

and the thesis follows by induction. □

Corollary 3.2 enables us to define q-analogues of the polynomials P (B_{n}; x) which have the additional property of reducing, when q = 0, to the Eulerian polynomials. For n ∈ P we let

B_{n}(x; q) =^{def} ∑_{k=0}^{n} B_{n,k}(q) x^{k} =^{def} ∑_{σ∈B_{n}} q^{N(σ)}x^{d_{B}(σ)} .  (10)

Our goal is to generalize to the B_{n,k}(q)’s the theory of the ordinary Eulerian numbers. Many of the results in this section are new even in the case q = 1.

The next result generalizes several well known formulas for ordinary Eulerian polynomials (see, e.g., [6], Exercise 3, p. 292; Theorem F, p. 245; Theorem D, p. 243; eq. [5j], p. 244) as well as Corollary 2 of [8] and Proposition 7.1 (b) of [25].

Theorem 3.4 For n ∈ N, let B_{n}(x; q) be the polynomial defined by (10). Then we have that:

i)

B_{n}(x; q) = (1+((1+q)n−1)x) B_{n−1}(x; q)+(1+q)(x−x^{2}) \frac{∂}{∂x}(B_{n−1}(x; q)) ; (11)
for n ∈ P, where B_{0}(x; q) =^{def} 1;

ii)

∑_{i≥0}((1 + q)i + 1)^{n}x^{i} = \frac{B_{n}(x; q)}{(1 − x)^{n+1}} ;  (12)

as formal power series in Z[q][[x]];

iii)

((1 + q)x + 1)^{n} = ∑_{k=0}^{n} B_{n,k}(q) (\begin{matrix}x+n−k \\ n \end{matrix}) ;  (13)

∑_{n≥0} B_{n}(x; q)\frac{t^{n}}{n!} = \frac{(1 − x) e^{t(1−x)}}{1 − x e^{t(1−x)(1+q)}} .  (14)

as formal power series in Z[x; q][[t]].

Proof.

i) Let σ ∈ B_{n−1}, i ∈ [n] and σ_{i}, σ_{−i} have the same meaning as in the proof of Proposition 3.3. Then it follows from Corollary 3.2 that

d_{B}(σ_{±i}) = \{ \begin{matrix}d_{B}(σ) , & if σ(i − 1) > σ(i), \\ d_{B}(σ) + 1 , & otherwise, \end{matrix}

for i ∈ [n − 1], and

d_{B}(σ_{n}) = d_{B}(σ) ,  d_{B}(σ_{−n}) = d_{B}(σ) + 1 .  (15)

Therefore,

B_{n}(x; q) = ∑_{i=1}^{n} ∑_{σ∈B_{n−1}}(x^{d_{B}(σ_{i})} q^{N(σ_{i})} + x^{d_{B}(σ_{−i})} q^{N(σ_{−i})})
= (1 + x q) B_{n−1}(x, q) + (1 + q) ∑_{σ∈B_{n−1}} q^{N(σ)} ∑_{i=1}^{n−1} x^{d_{B}(σ_{i})} ,

but

∑_{σ∈B_{n−1}} q^{N(σ)} ∑_{i=1}^{n−1} x^{d_{B}(σ_{i})} = ∑_{σ∈B_{n−1}} q^{N(σ)} (d_{B}(σ) x^{d_{B}(σ)} + (n − 1 − d_{B}(σ)) x^{d_{B}(σ)+1})
= (n − 1)x B_{n−1}(x, q) + (1 − x) ∑_{σ∈B_{n−1}} d_{B}(σ) q^{N(σ)} x^{d_{B}(σ)} ,

and (11) follows. ii) It follows from well known properties of rational generating functions (see, e.g., [21], Corollary 4.3.1, p.208) that there exist polynomials W_{n}(x, q) of degree ≤ n in x such that

∑_{i≥0}((1 + q) i + 1)^{n} x^{i} = \frac{W_{n}(x, q)}{(1 − x)^{n+1}} ,  (16)

for n ∈ N, as formal power series in Z[q][[x]]. Therefore we have that

\frac{W_{n}(x, q)}{(1 − x)^{n+1}} = (1 + q) x \frac{∂}{∂ x} [\frac{W_{n−1}(x, q)}{(1 − x)^{n}}] + \frac{W_{n−1}(x, q)}{(1 − x)^{n}} ,

which yields that

W_{n}(x, q) = (1 + q) x [(1 − x) \frac{∂}{∂x} (W_{n−1}(x, q)) + n W_{n−1}(x, q)] + (1 − x) W_{n−1}(x, q) .

(17)

But it follows immediately from (16) that W_{0}(x, q) = 1, so ii) follows from (17), (16), and i). iii) This follows immediately from ii) and Theorem 2.1. iv) By ii) we have that

∑_{n≥0} B_{n}(x, q)\frac{t^{n}}{n!} = ∑_{i≥0} x^{i} ∑_{n≥0}((1 + q) i + 1)^{n} (1 − x)^{n+1} \frac{t^{n}}{n!}
= (1 − x) e^{t (1−x)} ∑_{i≥0} x^{i} e^{t i (1−x)(1+q)} ,

and (14) follows. □

Note that equating the coefficients of q^{k} on both sides of (11) we get, by (10), that

B_{n,k}(q) = [1 + (1 + q)k] B_{n−1,k}(q) + [(1 + q) (n − k + 1) − 1] B_{n−1,k−1}(q) (18)

for all 0 ≤ k ≤ n, n ∈ P.

Lemma 3.5 For n ∈ P we have that

∑_{σ∈B_{n}} x^{d(σ)} q^{N(σ)} = (1 + q)^{n} \frac{A_{n}(x)}{x} .

Proof. Let T =^{def} {σ ∈ B_{n} : d(σ) = 0}. Note that, since an element v ∈ T is uniquely determined by the set {v(i) : v(i) > 0 and i ∈ [n]}, we have that

∑_{v∈T} q^{N(v)} = (1 + q)^{n} .  (19)

Furthermore, if u ∈ S_{n} and σ ∈ T then

d(σ u) = d(u)  (20)

(since σ(i) < σ(j) if and only if i < j, for all i, j ∈ [n]). This implies that if u, v ∈ S_{n} with u ≠ v then T u ∩ T v = ∅ (since if σ_{1} u = σ_{2} v for some σ_{1}, σ_{2} ∈ T then σ_{1} u v^{−1} = σ_{2} and hence 0 = d(σ_{2}) = d(σ_{1} u v^{−1}) = d(u v^{−1}) which implies that u v^{−1} = e). Since |T u| = |T | = 2^{n} for all u ∈ S_{n} this shows that B_{n} = ⨄_{u∈S_{n}} T u. Therefore, using (19) and (20) we obtain that

∑_{σ∈B_{n}} x^{d(σ)} q^{N(σ)} = ∑_{u∈S_{n}} ∑_{σ∈T} x^{d(σ u)} q^{N(σ u)}
= ∑_{u∈S_{n}} x^{d(u)} ∑_{σ∈T} q^{N(σ)}
= (1 + q)^{n} \frac{A_{n}(x)}{x} ,

as desired. □

The following recurrence generalizes a well known recurrence for ordinary Eulerian polynomials (see, e.g., [9]).

Theorem 3.6 The polynomials B_{n}(x; q) defined by (10) satisfy the recurrence relation

B_{n}(x; q) = ∑_{i=1}^{n} (\begin{matrix}n−1 \\ i−1 \end{matrix}) B_{i−1}(x; q) (1 + q)^{n−i+1} x B_{n−i}(x; 0) + (1 − x) B_{n−1}(x; q) , (21)

for n ∈ P, with the initial condition B_{0}(x; q) = 1.

Proof. Let σ ∈ B_{n−1} and σ_{i}, σ_{−i}, for i ∈ [n], have the same meaning as in the proof of Proposition 3.3. Then it follows from Corollary 3.2 that

d_{B}(σ_{±i}) = d_{B}(σ(1), …, σ(i − 1)) + d(σ(i), …, σ(n − 1)) + 1  (22)

(where d_{B}(∅) =^{def} 0), for i ∈ [n − 1]. Using this, (15), and Lemma 3.5, we therefore obtain, reasoning as in the proof of (11), that

B_{n}(x; q) = (1 + xq)B_{n−1}(x; q) + (1 + q) ∑_{i=1}^{n−1} ∑_{σ∈B_{n−1}} x^{d_{B}(σ_{i})} q^{N(σ)} .

But

∑_{i=1}^{n−1} ∑_{σ∈B_{n−1}} x^{d_{B}(σ_{i})} q^{N(σ)} = ∑_{i=1}^{n−1} (\begin{matrix}n−1 \\ i−1 \end{matrix}) ∑_{σ∈B_{i−1}} ∑_{τ∈B_{n−i}} x^{d_{B}(σ)+d(τ)+1} q^{N(σ)+N(τ)}

= ∑_{i=1}^{n−1} (\begin{matrix}n−1 \\ i−1 \end{matrix}) B_{i−1}(x; q) (1 + q)^{n−i} A_{n−i}(x)

and the thesis follows. □

A consequence of Theorem 3.4 is the following strengthening of Theorem 2.4 for Coxeter groups of type B_{n}, and A_{n}. The result follows immediately from Theorem 3.4 iii) and Theorem 2.2.

Corollary 3.7 For each q ≥ 0 and n ∈ N, the polynomial B_{n}(x, q) ∈ R[x] defined by (10) has only real zeros. In particular, the sequence {B_{n,0}(q), B_{n,1}(q), …, B_{n,n}(q)} is log-concave and unimodal. □

Note that for q = 0 the preceding corollary reduces to a well known result for Eulerian polynomials (see, e.g., [6], p.292, Ex.3).

Using a well known result from the theory of total positivity (see, e.g., [12], Chap. 8, §2, or [3], Theorem 2.2.4) we see that the preceding result implies the following determinantal inequalities.

Corollary 3.8 For n, i, r ∈ P and q ≥ 0 we have that

det [ \begin{matrix}B_{n,i}(q) & B_{n,i+1}(q) & … & B_{n,i+r}(q) \\ B_{n,i−1}(q) & B_{n,i}(q) & … & B_{n,i+r−1}(q) \\ ⋮ & ⋮ & & ⋮ \\ B_{n,i−r}(q) & B_{n,i−r+1}(q) & … & B_{n,i}(q) \end{matrix} ] ≥ 0  (23)

(where B_{n,k}(q) =^{def} 0 if k < 0). □

It would be interesting to have a combinatorial, or geometric (for q = 0, 1), interpretation of the numbers on the LHS of (23), in the spirit of [10] and [5]. Let us here only mention that this problem is open even for q = 0 and r = 1.

The presence of the parameter q enables us to obtain several other refinements and generalizations of the unimodality of P (B_{n}; x) and A_{n}(x). For n ∈ N and 0 ≤ k ≤ n let

A_{n,k}(x) =^{def} ∑_{{σ∈B_{n}: N(σ)=k}} x^{d_{B}(σ)} .  (24)

Corollary 3.9 For n ∈ N, and 0 ≤ k ≤ n, the polynomial A_{n,k}(x) defined by (24) has only real zeros. In particular, it is log-concave and unimodal.

Proof. Taking the coefficient of q^{k} on both sides of (12) yields, by (24), that

∑_{i≥0} (\begin{matrix}n \\ k \end{matrix}) i^{k}(i + 1)^{n−k}x^{i} = \frac{A_{n,k}(x)}{(1 − x)^{n+1}} ,  (25)

for k = 0, …, n, as formal power series in Z[[x]]. The thesis then follows from Theorems 2.1 and 2.2. □

Note that, in general, the polynomials A_{n,k}(x) are not symmetric. Therefore, it is not possible to deduce the unimodality of P (B_{n}; x) from (24) and the preceding corollary. However, this is possible if we pair the A_{n,k}(x)’s together correctly. To do this we need the following symmetry property, which generalizes the fact that P (B_{n}; x) is a symmetric polynomial with center of symmetry at ⌊\frac{n}{2}⌋.

Proposition 3.10 For n ∈ N, and 0 ≤ k ≤ n we have that

B_{n,k}(q) = q^{n} B_{n,n−k} (\frac{1}{q}) .

Proof. For v ∈ B_{n} let −v =^{def} [−v(1), …, −v(n)]. Then it follows immediately from Corollary 3.2 , and from (9), that

d_{B}(v) + d_{B}(−v) = n , N(v) + N(−v) = n ,

for all v ∈ B_{n}. The thesis then follows from (10). □

The next result, together with (24), provides a refinement of Theorem 2.4 for Coxeter groups of type B_{n}.

Theorem 3.11 Let n ∈ N, and 0 ≤ k ≤ ⌊\frac{n}{2}⌋. Then the polynomial

A_{n,k}(x) + A_{n,n−k}(x)

is symmetric and unimodal with center of symmetry at ⌊\frac{n}{2}⌋, and has only real zeros. In particular, it is log-concave with no internal zeros.

Proof. Note first that Proposition 3.10 is equivalent, by (24), to the statement that

A_{n,k}(x) = x^{n} A_{n,n−k} (\frac{1}{x}) ,  (26)

for all 0 ≤ k ≤ n. This immediately implies that A_{n,k}(x) + A_{n,n−k}(x) is a symmetric polynomial with center of symmetry at ⌊\frac{n}{2}⌋. Furthermore, since A_{n}(x) is a symmetric polynomial with center of symmetry at ⌊\frac{n+1}{2}⌋ (see, e.g., [6], p. 241, eq. [5c], and p. 292, Ex. 3) we deduce from (26) and (24) that

A_{n,n}(x) = x^{n} A_{n,0} (\frac{1}{x}) = x^{n+1} A_{n} (\frac{1}{x}) = A_{n}(x) = x A_{n,0}(x)  (27)

Now, from (25) we deduce that

∑_{i≥0} (\begin{matrix}n \\ k \end{matrix}) i^{k}(i + 1)^{k}[(i + 1)^{n−2k} + i^{n−2k}]x^{i} = \frac{A_{n,k}(x) + A_{n,n−k}(x)}{(1 − x)^{n+1}}  (28)
∑_{i≥0} (\begin{matrix}2k \\ k \end{matrix}) i^{k}(i + 1)^{k}x^{i} = \frac{A_{2k,k}(x)}{(1 − x)^{2k+1}} ,  (29)

and

∑_{i≥0}[(i + 1)^{n−2k} + i^{n−2k}]x^{i} = \frac{A_{n−2k,0}(x) + A_{n−2k,n−2k}(x)}{(1 − x)^{n−2k+1}} .  (30)

By (27) and Corollary 3.9 the numerators on the RHS of (29) and (30) are polynomials with (nonnegative coefficients and) only real zeros. The thesis now follows from Theorem 2.15 of [26]. □

There is another aspect of the theory of Eulerian polynomials which generalizes to the polynomials B_{n}(x; q) and which provides yet another refinement of the unimodality of P (B_{n}; x) and A_{n}(x).

To state this we will need to use some terminology from the theory of symmetric functions. In particular, we denote by P the set of all integer partitions and, for λ ∈ P, by s_{λ} the Schur function corresponding to λ and by f^{λ} the number of standard tableaux of shape λ (see [13], Chap. I, for details). Also, given an integral domain R, we denote by Λ̂_{R} the subring of R[[x_{1}, x_{2}, …]] consisting of all p ∈ R[[x_{1}, x_{2}, …]] such that p(x_{1}, x_{2}, …) = p(x_{σ(1)}, x_{σ(2)}, …) for all bijections σ : P → P. Theorem 3.12 For each λ ∈ P define a polynomial T_{λ}(x; q) by

∑_{λ} T_{λ}(x; q)s_{λ} =^{def} \frac{∑_{k≥0}(1 + xq)^{k} s_{(k)}}{1 − ∑_{k≥2}(x + x^{2} + … + x^{k−1})(1 + q)^{k} s_{(k)}} ,  (31)

as formal power series in Λ̂ _{Z[x,q]}. Then:

i) T_{λ}(x; 0) and T_{λ}(x; 1) are symmetric unimodal polynomials with center of symmetry at \frac{|λ|−1}{2} and \frac{|λ|}{2}, respectively;

ii) (xq)^{|λ|} T_{λ} (\frac{1}{x}; \frac{1}{q}) = T_{λ}(x; q) for all λ ∈ P;

iii) ∑_{λ⊢n} f^{λ} T_{λ}(x; q) = B_{n}(x; q), for all n ∈ P. Proof. i) is an immediate consequence of Proposition 1 and Theorem 2 of [4]. For T_{λ}(x; 0) this is proved in §3 of [4]. For T_{λ}(x; 1) take a_{λ} = b_{λ} = c_{λ} = s_{λ} for

λ ∈ P, and let S =^{def} {(k) : k ≥ 2}, r_{μ}(x) =^{def} 2^{|μ|}(x + x^{2} + … + x^{|μ|−1}) for μ ∈ S,

T =^{def} {(k) : k ≥ 0}, u(ν)(x) = (1 + x)^{|ν|} for ν ∈ T, in the notation of Theorem 2 of [4].

To prove ii) just substitute x with x^{−1}, q with q^{−1} and x_{i} with xqx_{i}, for i ∈ P, in (31) to obtain

∑_{λ}(xq)^{|λ|}T_{λ} (\frac{1}{x}, \frac{1}{q}) s_{λ} = \frac{∑_{k≥0}(xq)^{k} (1 + \frac{1}{xq} )^{k} s_{(k)}}{1 − ∑_{k≥2} x^{k}(x^{−1} + x^{−2} + … + x^{−k+1})q^{k} (1 + \frac{1}{q})^{k} s_{(k)}}
= ∑_{λ} T_{λ}(x; q) s_{λ} ,

and ii) follows.

To prove iii) define a ring homomorphism R : Λ_{Q[x]} → Q[x][[t]] by

R(p) =^{def} ∑_{n≥0}[x_{1} … x_{n}](p)\frac{t^{n}}{n!}

where p ∈ Λ and [x_{1} … x_{n}](p) denotes the coefficient of x_{1} … x_{n} in p (where ∏_{i=1}^{n} x_{i} =^{def} 1 if n = 0). It is then well known that

R(s_{λ}) = f^{λ} \frac{t^{|λ|}}{|λ|!} ,  (32)

for all λ ∈ P (see, e.g., §4 of [4], for details). Applying now R to both sides of (31) and using (32) we obtain

∑_{λ∈P} f^{λ} T_{λ}(x; q)\frac{t^{|λ|}}{|λ|!} = \frac{e^{(1+xq) t}}{1 − \frac{1}{1−x}(xe^{(1+q)t} − x − e^{x(1+q)t} + 1)}
= \frac{(1 − x) e^{(1+xq)t}}{e^{(1+q)xt} − xe^{(1+q)t}}
= ∑_{n≥0} B_{n}(x; q)\frac{t^{n}}{n!} ,

by part iv) of Theorem 3.4. Equating the coefficients of t^{n} yields iii), as desired. □

For q = 0 the preceding result was first proved by Stanley (see [22], Proposition 12) using results from the theory of representations of the symmetric group and from algebraic geometry. Note that the preceding theorem immediately implies Theorem 2.4 for Coxeter groups of type B_{n} and A_{n} as well as Proposition 3.10.

We now give a combinatorial interpretation to the polynomials T_{λ}(x; q). By an extended signed tableau we mean an array T =^{def} (T_{i,j})_{i,j∈P} such that:

i) T_{i,j} ∈ Z ∪{+∞ − ∞} for all (i, j) ∈ P × P;

ii) T_{i,j} = 0 for all but finitely many (i, j) ∈ P × P;

iii) |T_{i,j}| ≤ |T_{i,j+1}| for all (i, j) ∈ P × P such that T_{i,j+1} ≠ 0;

iv) |T_{i,j}| < |T_{i+1,j}| for all (i, j) ∈ P × P such that T_{i+1,j} ≠ 0.

The shape of an extended signed tableau T is the integer partition sh(T) =^{def} (λ_{1}, λ_{2}, …) where

λ_{i} =^{def} |{j ∈ P : T_{i,j} ≠ 0}| ,

for i ∈ P. Given T as above and α ∈ Z ∪{+∞, −∞}, α ≠ 0, we let m_{α}(T) =^{def} |{(i, j) ∈ P × P : T_{i,j} = α}|, and N(T) =^{def} ∑_{i≥1} m_{−i}(T). We then say that T is admissible if m_{i+1}(T) + m_{−i−1}(T) > 0 implies m_{i}(T) + m_{−i}(T) > 0 for all i ∈ P. For example,

−1 −2 2
2 +∞ −∞
−∞

is an admissible extended signed tableau, while

−1 1 2 +∞
2 −2
−4

is an extended signed tableau, but is not admissible.

A rooted extended signed tableau is a pair (T, R) where T is an extended signed tableau and R ⊆ {(i, j) ∈ P × P : T_{i,j} ≠ 0, ±∞}. Given such a pair we define its index to be

ind(T, R) =^{def} ∑_{(i,j)∈R} |{(a, b) ∈ P × P : |T_{a,b}| = |T_{i,j}| and b < j}| .

We will usually represent (and think of) a rooted extended signed tableau T as an extended signed tableau where some of the entries have been “barred”. For example

\overline{−1} 2 \overline{−3} −∞ +∞
\overline{3} −3
+∞

is a rooted extended signed tableau of index 0 + 0 + 2 = 2.

Theorem 3.13 For λ ∈ P let T_{λ}(x; q) be the polynomial defined by (31). Then

T_{λ}(x; q) = ∑_{(T,R)} x^{ind (T,R)+m_{−∞}(T)} q^{N(T)}  (33)

where the sum is over all rooted admissible extended signed tableaux (T, R) of shape λ such that, for all 1 ≤ i < +∞, exactly one entry equal to ±i is rooted, except the leftmost one.

Proof. For λ ∈ P denote by T′_{λ}(x; q) the polynomial on the RHS of (33) and let

T̃_{λ}(x; q) =^{def} ∑_{(T,R)} x^{ind (T,R)}q^{N(T)}  (34)

where (T, R) ranges over all rooted tableaux appearing in the sum on the RHS of (33) for which m_{+∞}(T) + m_{−∞}(T) = 0. Then it is clear that, for all λ ∈ P,

T′_{λ}(x; q) = ∑_{μ} T̃_{μ}(x; q)(1 + xq)^{|λ\μ|}  (35)

where the sum is over all partitions μ ⊆ λ such that λ \ μ is a horizontal strip. Multiplying both sides of (35) by s_{λ} and using a well known result for the multiplication of Schur functions (see, e.g., [13], eq.(5.16), p.42) we obtain that

∑_{λ∈P} T′_{λ}(x; q)s_{λ} = ∑_{μ} T̃_{μ}(x; q) ∑_{k≥0}(1 + xq)^{k} s_{μ}s_{(k)}
= ∑_{μ} T̃_{μ}(x; q)s_{μ} ∑_{k≥0}(1 + xq)^{k}s_{(k)} .  (36)

On the other hand the definition (34) of the T̃_{λ}(x; q)’s implies that T̃_{(0)}(x; q) = 1 and, for all λ ∈ P \ {0},

T̃_{λ}(x; q) = ∑_{μ} T̃_{μ}(x; q)(x + x^{2} + … + x^{|λ\μ|−1})(1 + q)^{|λ\μ|}  (37)

where the sum is over all partitions μ ⊆ λ such that λ \ μ is a horizontal strip and |λ \ μ| ≥ 2. Multiplying now both sides of (37) by s_{λ} and summing over all λ ∈ P yields that

∑_{λ} T̃_{λ}(x; q)s_{λ} = 1 + ∑_{μ} ∑_{k≥2}(x + x^{2} + … x^{k−1})(1 + q)^{k}T̃_{μ}(x; q)s_{μ}s_{(k)}  (38)
= 1 + ∑_{μ} T̃_{μ}(x; q)s_{μ} ∑_{k≥2}(x + x^{2} + … + x^{k−1})(1 + q)^{k}s_{(k)} ,

where we have used again eq.(5.16) on p.42 of [13]. Rewriting now (38) as

∑_{λ} T̃_{λ}(x; q)s_{λ} = \frac{1}{1 − ∑_{k≥2}(x + x^{2} + … + x^{k−1})(1 + q)^{k}s_{(k)}} ,

and comparing with (36) and (31) yields the desired result. □

It can be shown that for q = 0 the preceding theorem is equivalent to a result of J. Stembridge (see [24], Theorem 4.2).

We now generalize a classical result of Frobenius for Eulerian polynomials, namely, we give a combinatorial interpretation to the coefficients of B_{n}(x, q) when expressed in powers of (x − 1). Let S ⊆ P, a signed partition of S is a collection π = {B_{1}, …, B_{k}} of subsets of −S ∪ S such that {B_{1}, …, B_{k}, −B_{1}, …, −B_{k}} is a parti-

tion of −S ∪ S (where −{a_{1}, …, a_{r}} =^{def} {−a_{1}, …, −a_{r}}, for a_{1}, …, a_{r} ∈ Z). We call

B_{1}, …, B_{k} the blocks of π and say that π has k blocks. We also let

P (π) =^{def} |{x ∈ ⋃_{i=1}^{k} B_{i} : x > 0}| .

A partial signed partition of S is a signed partition of some subset of S. For example, π =^{def} {{−1, 3}, {−4}, {5, 7}} is a partial signed partition of [7] and P (π) = 3. We denote by B Π(S; k) (respectively, B Π_{⊆}(S; k)) the set of all signed partitions (respectively, partial signed partitions) of S having k blocks, and let

S_{B}(n, k; q) =^{def} ∑_{π∈B Π_{⊆}([n],k)} q^{n−P (π)} .  (39)

Theorem 3.14 For n ∈ N, let B_{n}(x; q) be the polynomial defined by (10). Then

B_{n}(x; q) = ∑_{k=0}^{n} k! S_{B}(n, k; q) (x − 1)^{n−k} .  (40)

Proof. We proceed by induction on n ∈N, the thesis being clearly true if n = 0. So fix n ∈ P and let π ∈ B Π_{⊆}([n], k). If {n} (respectively, {−n}) is a block of π then removing it from π yields a partial signed partition of [n − 1] into k − 1 blocks. If n (respectively, −n) is in a block of π of size ≥ 2 then removing n (respectively, −n) from this block yields a partial signed partition of [n−1] into k blocks. Finally, if neither n nor −n appear in π then π ∈ B Π_{⊆}([n − 1], k). Therefore we conclude from (39) that

S_{B}(n, k; q) = (1 + q) S_{B}(n − 1, k − 1; q) + (k(1 + q) + q) S_{B}(n − 1, k; q) , (41)

for 0 ≤ k ≤ n.Multiplying both sides of (41) by k! (x − 1)^{n−k} and summing for k = 0, …, n yields, by our induction hypothesis and part i) of Theorem 3.4,

∑_{k=0}^{n} k! S_{B} (n, k; q) (x − 1)^{n−k} = (1 + q) [(1 − x) \frac{∂}{∂x} (B_{n−1}(x; q)) + n B_{n−1}(x; q)]
+ (1 + q) (x − 1)[(n − 1) B_{n−1}(x; q)
+ (1 − x) \frac{∂}{∂x} (B_{n−1}(x; q))] + q (x − 1) B_{n−1}(x; q)
= B_{n} (x; q) ,

which completes the induction step and hence the proof. □

Note that it follows easily from (39) that

S_{B}(n, k; q) = ∑_{i=k}^{n} (\begin{matrix}n \\ i \end{matrix}) q^{n−i}(1 + q)^{i} S(i, k) .  (42)

In particular, this shows that S_{B}(n, k; 0) = S(n, k) so that Theorem 3.14 does reduce, when q = 0, to Frobenius’ Theorem (see, e.g., [6], Theorem E, p.244). When q = 1, Theorem 3.14 reduces to Corollary 1 of [8], and to Proposition 7.1(a) of [25]. It is also possible to deduce Theorem 3.14 algebraically from (42) and part iv) of Theorem 3.4.

It is well known that excedances and descents are equidistributed on S_{n} and that this distribution is given by the Eulerian polynomials (see, e.g., [21], Prop. 1.3.12). We now show how this result generalizes to the B_{n}(x; q)’s.

Given σ ∈ B_{n} and i ∈ [n] we say that i is an excedance (respectively, weak excedance) of σ if either σ(i) = −i (respectively σ(i) = i) or σ(|σ(i)|) > σ(i) (clearly, these two conditions are mutually exclusive). We say that i is an ascent of σ if σ(i) > σ(i − 1) (where σ(0) =^{def} 0). We denote by e(σ) (respectively, we(σ), a(σ)) the number of excedances (respectively, weak excedances, ascents) of σ. It is clear that if σ ∈ S_{n} then these notions of excedance and weak excedance coincide with the usual ones (see, e.g., [21], p.23). As an example, if σ = [3, −2, 5, 7, −1, −4, −6, −8, 9] then a(σ) = 4, we(σ) = 5, and e(σ) = 6. We then have the following result.

Theorem 3.15 There is a bijection τ : B_{n} → B_{n} such that

a(τ(σ)) = we(σ) ,

and

N(τ(σ)) = N(σ)

for all σ ∈ B_{n}.

Proof. Let σ ∈ B_{n} and let (a_{1 1} … a_{1 i_{1}}) (a_{2 1} … a_{2 i_{2}}) … (a_{s 1} … a_{s i_{s}}) be its standard disjoint cycle form (i.e., each cycle has its largest (in absolute value) element first, and the cycles are written in increasing order of the absolute values of their first elements). Let τ(σ) be the word obtained by deleting all parentheses in the standard disjoint cycle form of σ (we consider this word as the one-line notation of τ(σ)). Clearly τ(σ) ∈ B_{n} and the map τ : B_{n} → B_{n} is a bijection such that N (τ(σ)) = N (σ) for all σ ∈ B_{n}. Fix 1 ≤ j ≤ s and let C_{j} be the j-th cycle in the standard disjoint cycle form of σ, (so C_{j} = (a_{j1} … a_{j i_{j}})). Now, if |C_{j}| ≥ 2, then

we(C_{j}) = |{1 ≤ r ≤ i_{j} : a_{j,r} < a_{j,r+1}}|  (43)

(where a_{j,i_{j}+1} =^{def} a_{j,1}). But (since σ is in standard form) a_{j,i_{j}} < a_{j,1} if and only if a_{j,1} > 0, and this happens if and only if a_{j−1,i_{j−1}} < a_{j,1} (where a_{0,i_{0}} =^{def} 0). Therefore, from (43) we conclude that

we(C_{j}) = |{0 ≤ r ≤ i_{j} − 1 : a_{j,r} < a_{j,r+1}}|  (44)

(where a_{j,0} =^{def} a_{j−1,i_{j−1}}). On the other hand, if |C_{j}| = 1 then we(C_{j}) = 1 if and only if a_{j,1} > 0, and this happens if and only if a_{j−1,i_{j−1}} < a_{j,1}, so that (44) is still valid in this case. Therefore, from (44), we conclude that

we(σ) = ∑_{j=1}^{s} we(C_{j}) = a(τ(σ)) ,

as desired. □

Note that, when restricted to S_{n}, the bijection τ reduces to the “fundamental transformation” of [9], p. 13 (see also [21], p. 17).

Corollary 3.16 For n ∈ P and 0 ≤ k ≤ n we have that

B_{n,k}(q) = ∑_{{σ∈B_{n}: a(σ)=k}} q^{P (σ)} = ∑_{{σ∈B_{n}: we(σ)=k}} q^{P (σ)} = ∑_{{σ∈B_{n}: e(σ)=k}} q^{P (σ)+e(σ)−we(σ)} .

Proof. It follows immediately from our definitions that a(v) = d(−v) for all v ∈ B_{n} (where −v has the same meaning as in the proof of Proposition 3.10). Also, letting

α(v)(i) =^{def} \{ \begin{matrix}−v(i), & if |v(i)| = i, \\ v(i), & otherwise, \end{matrix}

for i ∈ [n] and v ∈ B_{n}, defines an involution α : B_{n} → B_{n} such that e(v) = we(α(v)) and N(α(v)) = N(v) + we(v) − e(v) for all v ∈ B_{n}. The thesis now follows from (10) and Theorem 3.15. □

We should mention that a different notion of excedance for elements of B_{n} (also equidistributed with B-descents) has been defined in [23]. Hence one can obtain yet another combinatorial interpretation for the polynomials B_{n,k}(q) using this notion.

4 q-Eulerian polynomials of type D

In this section we examine in detail a natural q-analogue of P (W; x) in the case that W is a Coxeter group of type D_{n}. We will again slightly abuse notation and denote this group by D_{n}. Recall that

D_{n} =^{def} {σ ∈ B_{n} : N(σ) ≡ 0 (mod 2)} ,

so that D_{n} is a subgroup of B_{n} of index 2. As a set of Coxeter generators for D_{n}

we take S′ =^{def} {s_{1}, …, s_{n−1}, s′_{n}} where s′_{n} = [−2, −1, 3, …, n] (and s_{1}, …, s_{n−1} have

the same meaning as in §3).

As we have done for B_{n} we start by obtaining an explicit combinatorial description of the polynomials P (D_{n}; x). To do this , we first need a simple combinatorial description of the length function of D_{n}. For convenience we let

inv_{D}(σ) =^{def} inv_{B}(σ) − N(σ)  (45)

for all σ ∈ B_{n}.

Proposition 4.1 Let n ∈ P. Then

l_{D}(σ) = inv_{D}(σ)  (46)

for all σ ∈ D_{n}.

Proof. We will prove first that

inv_{D}(σ) ≤ l_{D}(σ)  (47)

for all σ ∈ D_{n}. Let v ∈ D_{n}. Now, if i ∈ [n − 1] then it follows from (7) and (45) that

inv_{D}(v s_{i}) = \{ \begin{matrix}inv_{D}(v) + 1 , & if v(i) < v(i + 1), \\ inv_{D}(v) − 1 , & if v(i) > v(i + 1). \end{matrix}  (48)

On the other hand, since s′_{n} = s_{n} s_{1} s_{n} we obtain from (6) and (7) that

inv_{B}(v s′_{n}) = \{ \begin{matrix}inv_{B}(v) + sgn(v(1)) + sgn(v(2)) + 1 , & if −v(1) < v(2), \\ inv_{B}(v) + sgn(v(1)) + sgn(v(2)) − 1 , & if −v(1) > v(2), \end{matrix}  (49)

and hence we conclude from (45) that

inv_{D}(v s′_{n}) = \{ \begin{matrix}inv_{D}(v) + 1 , & if v(1) + v(2) > 0, \\ inv_{D}(v) − 1 , & if v(1) + v(2) < 0. \end{matrix}  (50)

Since inv_{D}(e) = l_{D}(e) = 0, (48) and (50) imply (47), as claimed.

We now prove (46) by induction on inv_{D}(σ). If inv_{D}(σ) = 0 then inv(σ) = 0 and ∑_{{j∈[n]: σ(j)<0}}(σ(j) + 1) = 0. Therefore σ(1) < … < σ(n) and N(σ) ≤ 1 and this, since σ ∈ D_{n}, implies that σ = e and (46) holds in this case. Now let t ∈ N and v ∈ D_{n} be such that inv_{D}(v) = t + 1. Then v ≠ e and we claim that there exists s ∈ S′ such that inv_{D}(v s) = t. In fact, if inv _{D}(v s) = t + 2 for all s ∈ S′ then (48) and (50) would imply that v(1) < v(2) < … < v(n) and v(1) + v(2) > 0. But this implies that v(1) > 0 and hence that v = e, which proves our claim. So let s ∈ S′ be such that inv_{D}(v s) = t. Then by our induction hypothesis l_{D}(v s) = t and hence l_{D}(v) ≤ t + 1. Therefore l_{D}(v) ≤ inv_{D}(v) and this, by (47), concludes the induction step and hence the proof. □

Other (more complicated) combinatorial descriptions of the length function of D_{n} appear in [19], §6, p.180, and in [16], §2.

Corollary 4.2 Let n ∈ P and v ∈ D_{n}. Then

d_{D}(v) = |{i ∈ [n] : v(i − 1) > v(i)}| ,  (51)

where v(0) =^{def} −v(2) (and v(n + 1) =^{def} 0).

Proof. By definition and Proposition 4.1 we have that

d_{D}(v) = |{s ∈ S′ : l_{D}(v s) < l_{D}(v)}|
= |{s ∈ S′ : inv_{D}(v s) < inv_{D}(v)}|,

and the thesis follows from (48) and (50). □

Corollary 4.2 enables us again to define q-analogues of the polynomials P (D_{n}; x) which have the additional property of reducing, when q = 0, to the Eulerian polynomials. For n ∈ P we let

D_{n}(x; q) =^{def} ∑_{k=0}^{n} D_{n,k}(q)x^{k} =^{def} ∑_{v∈D_{n}} q^{N(v(2),...,v(n))} x^{d_{D}(v)} .  (52)

It may at first sight seem that the most natural q-analogue of P (D_{n}; x) would be given by the joint distribution of d_{D}(v) and N(v) over D_{n}. However, the polynomials D_{n}(x; q) carry more combinatorial information.

Proposition 4.3 For n ∈ N, let D_{n}(x; q) be the polynomial defined by (52). Then

∑_{v∈D_{n}} x^{d_{D}(v)} q^{N(v)} = \frac{1}{2}[(1 + q) D_{n}(x; q) + (1 − q) D_{n}(x; −q)] .  (53)

Proof. Note first that, for any v ∈ B_{n}

N(v) = \{ \begin{matrix}N(v(2), …, v(n)), & if v(1) > 0, \\ N(v(2), …, v(n)) + 1, & if v(1) < 0. \end{matrix}

It therefore follows from (52) that

(1 + q) D_{n}(x; q) = ∑_{v∈D_{n}} x^{d_{D}(v)} (q^{N(v)} + q^{N(v)+sgn (v(1))}) .  (54)

Since N(v) ≡ 0 (mod 2) for all v ∈ D_{n}, (53) follows. □

We note the following consequence of Proposition 4.1.

Proposition 4.4 For n ∈ P we have that

∑_{σ∈D_{n}} x^{l_{D}(σ)}q^{N(σ(2),...,σ(n))} = ∏_{i=2}^{n}(1 + x + … + x^{i−1})(1 + qx^{i−1}) .

Proof. Given v ∈ B_{n} let Γ(v) =^{def} [−v(1), v(2), …, v(n)]. Then Γ is clearly a bijection from D_{n} to B_{n} \ D_{n}, and

N(Γ(v)) = N(v) + sgn(v(1)),  (55)

for all v ∈ B_{n}. Then it follows from (46), (45) and (3) that

l_{D}(Γ(v)) = inv_{B}(Γ(v)) − N(Γ(v))
= inv_{B}(v) + sgn(v(1)) − (N(v) + sgn(v(1))) = l_{D}(v) .

Therefore,

∑_{σ∈B_{n}} x^{l_{D}(σ)} q^{N(σ)} = ∑_{σ∈D_{n}}(x^{l_{D}(σ)}q^{N(σ)} + x^{l_{D}(Γ(σ))}q^{N(Γ(σ))})
= ∑_{σ∈D_{n}} x^{l_{D}(σ)}(q^{N(σ)} + q^{N(Γ(σ))})  (56)
= ∑_{σ∈D_{n}} x^{l_{D}(σ)}q^{N(σ(2),...,σ(n))}(1 + q) .

On the other hand, it follows from (45) that

∑_{σ∈B_{n}} x^{l_{D}(σ)}q^{N(σ)} = ∑_{σ∈B_{n}} x^{l_{B}(σ)} (\frac{q}{x})^{N(σ)} ,  (57)

so the thesis follows from (56), (57) and Proposition 3.3. □

We now wish to develop a theory for the polynomials D_{n,k}(q) parallel to that developed in the preceding section for the B_{n,k}(q)’s.

Proposition 4.5 For n ≥ 2 and 0 ≤ k ≤ n we have that

D_{n,k}(q) = q^{n−1} D_{n,n−k} (\frac{1}{q}) .  (58)

Proof. For v ∈ D_{n} let

Δ(v) =^{def} \{ \begin{matrix}−v, & if n is even, \\ −Γ(v), & if n is odd, \end{matrix}

where Γ : D_{n} → B_{n} \ D_{n} has the same meaning as in the proof of Proposition 4.4. Then it is clear that Δ : D_{n} → D_{n} is a bijection and that N(v(2), …, v(n)) + N(Δ(v)(2), …, Δ(v)(n)) = n − 1. Furthermore, it follows easily from Corollary 4.2 that

d_{D}(v) = d_{D}(Γ(v)) ,  (59)

for all v ∈ B_{n}. This implies that d_{D}(v) + d_{D}(Δ(v)) = n, and (58) follows from (52). □

We now derive a recurrence relation satisfied by the polynomials D_{n}(x; q). In order to do this, however, we need to consider also the polynomials

\overline{D}_{n}(x; q) =^{def} ∑_{v∈B_{n}} x^{d_{D}(v)} q^{N(v)} ,  (60)

for n ∈ N. Note that

\overline{D}_{n}(x; q) = (1 + q) D_{n}(x; q) ,  (61)

for n ≥ 2.

We can now derive a recurrence relation for the polynomials D_{n}(x; q) which is the analogue of Theorem 3.6.

Theorem 4.6 The polynomials D_{n}(x; q) defined by (52) satisfy the recurrence relation

D_{n}(x; q) = ∑_{i=1}^{n} (\begin{matrix}n−1 \\ i−1 \end{matrix}) \overline{D}_{i−1}(x; q) (1 + q)^{n−i} x B_{n−i}(x; 0) + (1 − x) D_{n−1}(x; q) , (62)

for n ≥ 3, with the initial conditions D_{0}(x; q) =^{def} D_{1}(x; q) =^{def} 1, D_{2}(x; q) =^{def} (1 + x)(1 + qx).

Proof. Let σ ∈ B_{n−1} and σ_{i}, σ_{−i}, for i ∈ [n], have the same meaning as in the proof of Proposition 3.3. Then it follows from Corollary 4.2 that

d_{D}(σ_{±i}) = d_{D}(σ(1), …, σ(i − 1)) + d(σ(i), …, σ(n − 1)) + 1 ,

for i ∈ [n − 1] \ {2} (where d_{D}(∅) =^{def} 0), and that d_{D}(σ_{2}) = d(σ(2), …, σ(n − 1)) + 1, d_{D}(σ_{−2}) = d(σ(2), …, σ(n − 1)) + 2, d_{D}(σ_{n}) = d_{D}(σ), and d_{D}(σ_{−n}) = d_{D}(σ) + 1. Using this and Lemma 3.5 we obtain that

∑_{v∈B_{n}} x^{d_{D}(v)} q^{N(v)} = ∑_{i=1}^{n} ∑_{σ∈B_{n−1}}(x^{d_{D}(σ_{i})} q^{N(σ_{i})} + x^{d_{D}(σ_{−i})} q^{N(σ_{−i})})
= (1 + q) ∑_{i∈[n−1]\{2}} ∑_{σ∈B_{n−1}} x^{d_{D}(σ_{i})} q^{N(σ)}
+ (1 + x q) ∑_{σ∈B_{n−1}}(x^{d_{D}(σ_{2})} q^{N(σ)} + x^{d_{D}(σ)} q^{N(σ)})
= (1 + q) ∑_{i∈[n−1]\\{2\}} (\begin{matrix}n−1 \\ i−1 \end{matrix}) ∑_{σ∈B_{i−1}} ∑_{τ∈B_{n−i}} x^{d_{D}(σ)+d(τ)+1} q^{N(σ)+N(τ)}

+ (1 + x q)(\overline{D}_{n−1}(x; q) + ∑_{σ∈B_{n−1}} x^{d(σ(2),...,σ(n−1))+1} q^{N(σ)})
= (1 + q) ∑_{i∈[n−1]\\{2\}} (\begin{matrix}n−1 \\ i−1 \end{matrix}) \overline{D}_{i−1}(x; q) (1 + q)^{n−i} A_{n−i}(x)
+ (1 + x q)(\overline{D}_{n−1}(x; q) + (n − 1)(1 + q) (1 + q)^{n−2}A_{n−2}(x)) ,

and the thesis follows.□

Note that, by Theorems 3.6 and 4.6, the polynomials B_{n}(x; q) and \overline{D}_{n}(x; q) satisfy the same recurrence relation, but with different initial conditions. Despite this similarity, though, it seems to be difficult to derive a recurrence relation analogous to part i) of Theorem 3.4 for the D_{n}(x; q)’s.

However, we can derive analogues of most of the results in §3 thanks to the following consequence of Corollary 4.2.

Theorem 4.7 For n ∈ N we have that

D_{n}(x; q) = \frac{1}{q(1 − x)}[(q−x) B_{n}(x; q)−x(q−1)(1+q)^{n}B_{n}(x; 0)]−n x(1+q)^{n−1}B_{n−1}(x; 0) .

(63)

Proof. By our definitions, and Lemma 3.5 we know that

B_{n}(x, q) = ∑_{σ∈B_{n}} x^{d_{B}(σ)} q^{N(σ)} ,

and

(1 + q)^{n}B_{n}(x; 0) = ∑_{σ∈B_{n}} x^{d(σ)} q^{N(σ)} ,

for n ≥ 2. Therefore, letting B_{n}^{+} =^{def} {v ∈ B_{n} : v(1) > 0} and B_{n}^{−} =^{def} B_{n} \ B_{n}^{+} we have, by Corollary 3.2, that

B_{n}(x; q) − (1 + q)^{n} B_{n}(x; 0) = (x − 1) ∑_{σ∈B_{n}^{−}} x^{d(σ)} q^{N(σ)} ,

and

B_{n}(x; q) − x(1 + q)^{n} B_{n}(x; 0) = (1 − x) ∑_{σ∈B_{n}^{+}} x^{d(σ)} q^{N(σ)} .

Hence we may rewrite (63) as

D_{n}(x; q) = \frac{1}{q} [x ∑_{v∈B_{n}^{−}} x^{d(v)} q^{N(v)} + q ∑_{v∈B_{n}^{+}} x^{d(v)} q^{N(v)}] − n x ∑_{σ∈B_{n−1}} x^{d(σ)} q^{N(σ)}
= ∑_{v∈B_{n}} x^{d_{B}(v)} q^{N(v(2),...,v(n))} − n ∑_{σ∈B_{n−1}} x^{d(σ)+1} q^{N(σ)} ,

and therefore, using (52), as

∑_{v∈B_{n}} x^{d_{B}(v)} q^{N(v(2),...,v(n))} = ∑_{v∈D_{n}} x^{d_{D}(v)} q^{N(v(2),...,v(n))} + n ∑_{σ∈B_{n−1}} x^{d(σ)+1} q^{N(σ)} . (64)

We will prove the theorem by giving a bijection that will establish (64) combinatorially. More precisely, we will construct two bijections

Φ : {v ∈ B_{n} : v(1) > sgn(v(1)) v(2)} → ⋃_{j=1}^{n} B([n] \ {j})  (65)

and

Θ : {v ∈ B_{n} : v(1) < sgn(v(1)) v(2)} → D_{n} ,  (66)

such that d(Φ(v)) = d_{B}(v)−1, N(Φ(v)) = N(v(2), …, v(n)), d_{D}(Θ(v)) = d_{B}(v) and N(Θ(v)(2), …, Θ(v)(n)) = N(v(2), …, v(n)). We construct Φ first. Given v ∈ B_{n} with v(1) > sgn(v(1)) v(2) we let

Φ(v) =^{def} (v(2), …, v(n)) .

Note that, since v(1) > sgn(v(1)) v(2), either v(1) < 0 or v(1) > v(2) (but not both) and therefore

d(Φ(v)) = d(v(2), …, v(n)) = d_{B}(v) − 1 .

Furthermore, if [σ_{1}, …, σ_{n−1}] ∈ B([n]\{j}) for some j ∈ [n] then we let φ(σ_{1}, …, σ_{n−1}) =^{def} [sgn(j − σ_{1}) j , σ_{1}, …, σ_{n−1}]. It is then easy to see that Φ and φ are inverses of each other so that Φ is a bijection.

To construct Θ let v ∈ B_{n} be such that v(1) < sgn(v(1)) v(2) and let

Θ(v) =^{def} \{ \begin{matrix}v , & if v ∈ D_{n}, \\ [ − v(1), v(2), …, v(n)] , & otherwise. \end{matrix}  (67)

Note that, since v(1) < sgn(v(1)) v(2), d_{B}(v) = d_{D}(v) (for if v(1) > 0 then 0 < v(1) < v(2) and hence v(1) + v(2) > 0; while if v(1) < 0 then v(1) < −v(2) and hence v(1) + v(2) < 0). Therefore, from (67) and Corollary 4.2 we conclude that d_{D}(Θ(v)) = d_{D}(v) = d_{B}(v). Now let, for u ∈ D_{n},

θ(u) =^{def} \{ \begin{matrix}u , & if u(1) < sgn(u(1)) u(2), \\ [ − u(1), u(2), …, u(n)] , & otherwise. \end{matrix}

It is then clear that Θ and θ are inverses of each other so that Θ is a bijection and this concludes the proof. □

For q = 1 the preceding theorem yields the following simple relation which was first observed by J. Stembridge (see [25], Lemma 9.1), and which also follows from Theorem 4.2 of [16].

Corollary 4.8 For n ∈ N and 0 ≤ k ≤ n we have that

B_{n,k}(1) = D_{n,k}(1) + n2^{n−1} A(n − 1, k − 1).□  (68)

Corollary 4.9 For n ∈ N, let D_{n}(x; q) be the polynomial defined by (52). Then

∑_{n≥0} D_{n}(x; q) \frac{t^{n}}{n!} = \frac{(q − x) e^{t (1−x)} + x (1 − q − qt + qtx) e^{1+qt (1−x)}}{q(1 − x e^{1+qt (1−x)})}  (69)

as formal power series in Z[x, q][[t]].

Proof. From (63), and part iv) of Theorem 3.4 we obtain that

∑_{n≥0} D_{n}(x; q) \frac{t^{n}}{n!} = \frac{(q − x) e^{t (1−x)}}{q(1 − x e^{1+qt (1−x)})} − x t \frac{(1 − x) e^{1+qt (1−x)}}{1 − x e^{1+qt (1−x)}} − \frac{x(q − 1)e^{t(1+q)(1−x)}}{q(1 − xe^{t(1+q)(1−x)})}

and (69) follows. □

Other consequences of Theorem 4.7 are the following two results which we state, for the sake of simplicity, only in the case q = 1. We denote by B_{n}(x) the n-th Bernoulli polynomial and by B(n) the n-th Bernoulli number, for n ∈ N, ([6], p.48).

Theorem 4.10 For n ≥ 2 we have that

∑_{i≥0}[(2i + 1)^{n} − 2^{n−1}(B_{n}(i + 1) − B(n))] x^{i} = \frac{P (D_{n}; x)}{(1 − x)^{n+1}} ,  (70)

as formal power series in Z[[x]].

Proof. It follows from Theorems 4.7 and 3.4 that

\frac{D_{n}(x; 1)}{(1 − x)^{n+1}} = \frac{B_{n}(x; 1)}{(1 − x)^{n+1}} − 2^{n−1} n \frac{x B_{n−1}(x; 0)}{(1 − x)^{n+1}}
= ∑_{i≥0}[(2i + 1)^{n} − 2^{n−1} n ∑_{j=0}^{i} j^{n−1}] x^{i} ,

and the thesis follows from well known properties of Bernoulli polynomials (see, e.g., [6], p.154, Ex.4). □

Corollary 4.11 For n ≥ 2 we have that

∑_{k=0}^{n} D_{n,k}(1) (\begin{matrix}x+n−k \\ n \end{matrix}) = (2x + 1)^{n} − 2^{n−1}(B_{n}(x + 1) − B(n)).□

Note that the coefficient of x^{i} in the LHS of (70) does not have, in general, only real zeros as a polynomial in i (take, e.g., n = 4). Therefore we cannot use Theorem 2.2 to deduce, from (70), the analogue of Corollary 3.7 for P (D_{n}; x).

We note the following interesting consequence of the preceding result and Theorem 3.4 which gives, essentially, the expansion of Bernoulli polynomials when expressed with respect to the basis \{(\begin{matrix}x+n−i \\ n \end{matrix})\}_{i=0,...,n}.

Corollary 4.12 For n ≥ 2 we have that

2^{n−1}(B_{n}(x + 1) − B(n)) = ∑_{k=0}^{n}(B_{n,k}(1) − D_{n,k}(1)) (\begin{matrix}x+n−k \\ n \end{matrix}) .□

We now give a combinatorial interpretation to the coefficients of P (D_{n}; x) when expressed in powers of (x − 1). Let π be a partial signed partition of [n] and B ∈ π. We say that B is special if P (B) = 1.

Theorem 4.13 For n ≥ 2 we have that

P (D_{n}; x) = (x − 1)^{n} + ∑_{k=1}^{n}(k − 1)! S_{D}(n, k) (x − 1)^{n−k} ,

where S_{D}(n, k) equals the number of partial signed partitions of [n] into k blocks that have one rooted non-special block.

Proof. From Theorems 4.7, 3.14 and (42) we obtain that

D_{n}(x; 1) = B_{n}(x; 1) − 2^{n−1} n [(x − 1)B_{n−1}(x; 0) + B_{n−1}(x; 0)]
= ∑_{k=0}^{n} k! S_{B}(n, k; 1)(x − 1)^{n−k} − 2^{n−1} n ∑_{k=1}^{n}(k − 1)! S(n, k)(x − 1)^{n−k}
= (x − 1)^{n} + ∑_{k=1}^{n}(k − 1)! [k S_{B}(n, k; 1) − 2^{n−1} n S(n, k)](x − 1)^{n−k} .(71)

Now let i ∈ [n], π = {B_{1}, …, B_{k}}, be a partition of [n] into k blocks and S ⊆ [n]\{i}. We may assume that i ∈ B_{1}. We can then construct a partial signed partition π′ =^{def} {B′_{1}, …, B′_{k}} of [n] into k blocks having one rooted special block by letting

B′_{i} =^{def} (B_{i} \ S) ∪ (−(B_{i} ∩ S)) ,

for i = 2, …, k,

B′_{1} =^{def} {i} ∪ (−(B_{1} ∩ S)) ,

and then rooting B′_{1}. It is easy to see that this construction is a bijection. This shows that there are n 2^{n−1} S(n, k) partial signed partitions of [n] into k blocks having one rooted special block and since k S_{B}(n, k; 1) counts elements of BΠ_{⊆}([n], k) having one rooted block, the thesis follows from (71). □

We illustrate the preceding theorem with an example. Suppose n = 2, then there are eight partial signed partitions of [2] that have one rooted non-special block, namely, \overline{−1 − 2}, \overline{12}, \overline{−1}, \overline{−2}, \overline{−1}/2, 1/\overline{−2}, \overline{−1}/ − 2, −1/\overline{−2} (where we have distinguished the rooted block with a bar). Therefore

P (D_{2}; x) = (x − 1)^{2} + 4(x − 1) + 4 .

5 Conjectures and Open Problems

There are several open problems which are suggested by the present work.

As noted in section 1, the polynomials P (W; x) are actually Poincaré polynomials of certain (toric) projective varieties. Therefore, algebra-geometric proofs of all the results presented in this paper would be interesting.

From the enumerative point of view the main one is probably whether there is any q > 0 such that D_{n}(x; q) has only real zeros. In this respect, we feel that this is true at least for q = 1.

Conjecture 5.1 For n ∈ P, the polynomial P (D_{n}; x) has only real zeros. In particular, P (D_{n}; x) is log-concave.

The above conjecture has been verified for n ≤ 23. It is possible that Conjecture 5.1 may be solved using Theorem 4.7 and a more precise knowledge of the location of the zeros of P (A_{n}; x) and P (B_{n}; x). More generally, we feel that the following statement is true.

Conjecture 5.2 For every finite Coxeter group W the polynomial P (W; x) has only real zeros. In particular, P (W; x) is log-concave.

By Corollary 3.7 Conjecture 5.2 holds if W is of type A_{n} and B_{n}. Also, one can check, with the aid of a computer, that P (H_{3}; x), P (H_{4}; x), P (F_{4}; x), P (E_{6}; x), P (E_{7}; x), and P (E_{8}; x) all have only real zeros. Furthermore, it is easy to see that if (W_{1}, S_{1}) and (W_{2}, S_{2}) are (finite) Coxeter systems then P (W_{1} × W_{2}; x) = P (W_{1}; x) P (W_{2}; x) (where W_{1} × W_{2} denotes the direct product of W_{1} and W_{2}). Therefore P (W_{1} × W_{2}; x) has only real zeros (respectively, is log-concave) if both P (W_{1}; x) and P (W_{2}; x) have only real zeros (respectively, are log-concave). This shows that it is enough to study Conjecture 5.2 for irreducible (finite) Coxeter systems. Therefore, by the classification of such Coxeter systems (see, e.g., [11]), to settle either part of Conjecture 5.2 it is enough to decide if P (D_{n}; x) has only real zeros or is log-concave for all n ∈ N.

From a combinatorial point of view, we feel that the main open problems are the following.

Problem 5.3 Is there an analogue of part i) of Theorem 3.4 for the polynomials P (D_{n}; x)? (Or, more generally, for the D_{n}(x; q)’s?)

An affirmative answer to the above question would probably yield a simple recurrence relation which could, in turn, be used to attack Conjecture 5.1 with “interlacing roots” arguments such as those used, e.g., in [3]. It is conceivable that if a geometric proof of (18) can be found, for q = 1, then this would give some insight on what a corresponding recursion for the D_{n,i}(1)’s might look like, and thus on Problem 5.3.

Problem 5.4 Is there a “natural” notion of excedance, for D_{n}, which is equidistributed with D-descents in D_{n}?

By “natural” we mean here that this notion of excedance should coincide, when σ ∈ S_{n}, with the usual one and that the definition of whether σ ∈ D_{n} has an excedance at i ∈ [n] should be independent of whether σ has an excedance at j ∈ [n], for j ≠ i.

Computer evidence suggests the following conjecture. For n ∈ P and 0 ≤ i, k ≤ n let

A_{n,k,i} =^{def} |{σ ∈ B_{n} : N(σ) = k, d_{B}(σ) = i}| ,

so that A_{n,k}(x) = ∑_{i=0}^{n} A_{n,k,i}x^{i}, where A_{n,k}(x) is defined by (24).

Conjecture 5.5 For n ∈ P and 1 ≤ k ≤ n − 1 there exists a simplicial convex ndimensional polytope P_{n,k} such that ∑_{i=0}^{n} h_{i}(P_{n,k})x^{i} = 1 + A_{n,k}(x) + A_{n,n−k}(x) + x^{n}.

Note that, if the preceding conjecture is correct, then Theorem 3.14 yields an explicit combinatorial description of the f-vector of P_{n,k}. It is well known that h-vectors of simplicial convex polytopes have been completely characterized. Using this characterization (see, e.g., [20]) and Theorem 3.11 we obtain that Conjecture 5.5 is equivalent to the existence of a standard graded Q-algebra R such that H(R; 1) = A_{n,k,1} + A_{n,n−k,1} − 1, and H(R; i) = A_{n,k,i} − A_{n,k,i−1} + A_{n,n−k,i} − A_{n,n−k,i−1} for 2 ≤ i ≤ ⌊\frac{n}{2}⌋, (where H(R; i) denotes the Hilbert function of R, see [18] for definitions). There is a numerical characterization of Hilbert functions of standard graded Q-algebras, (see, e.g., [18], Theorem 2.2), which is essentially due to Macaulay. Using this characterization (and a computer), we have verified Conjecture 5.5 for 1 ≤ k ≤ n − 1 ≤ 10. Acknowledgements. I would like to thank Anders Björner, Valery Lunts, and John Stembridge for some useful conversations, and the Institut Mittag-Leffler for hospitality and financial support during the preparation of this work. Also, I would like to thank Volkmar Welker for carrying out some of the computer computations mentioned in §5.

References

[1] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler, Oriented Matroids, Cambridge Univ. Press, to appear.

[2] A. Björner, Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings, Adv. in Math., 52 (1984), 173-212.

[3] F. Brenti, Unimodal, log-concave, and Pólya Frequency sequences in Combinatorics, Memoirs Amer. Math. Soc., no.413, 1989.

[4] F. Brenti, Unimodal polynomials arising from symmetric functions, Proc. Amer. Math. Soc., 108 (1990), 1133-1141.

[5] F. Brenti, Determinants of super-Schur functions, lattice paths, and dotted plane partitions, Adv. in Math., 98 (1993), 27-64.

[6] L. Comtet, Advanced Combinatorics, Reidel, Dordrecht/Boston, 1974.

[7] V. Danilov, The geometry of toric varieties, Russian Math. Surveys, 33 (1978), 97-154.

[8] I. Dolgachev and V. Lunts, A character formula for the representation of a Weyl group in the cohomology of the associated toric variety, J. of Algebra, to appear.

[9] D. Foata and M. Schutzenberger, Theorie geometrique des polynomes euleriens, Lecture Notes in Mathematics, no.138, Springer-Verlag, Berlin-New York, 1970.

[10] I. Gessel and G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math., 58 (1985), 300-321.

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

[12] S. Karlin, Total Positivity, vol.1, Stanford University Press, 1968.

[13] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, New York/London, 1979.

[14] T. Oda, Convex Bodies and Algebraic Geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete 15, Springer-Verlag, Berlin Heidelberg, 1988.

[15] V. Reiner, Signed permutations statistics, preprint.

[16] V. Reiner, Descents and one-dimensional characters for classical Weyl groups, preprint.

[17] V. Reiner, Counting the signs in signed permutations, preprint.

[18] R. Stanley, Hilbert functions of graded algebras, Adv. in Math., 28 (1978), 57-83.

[19] R. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Alg. Disc. Meth., 1 (1980), 168-184.

[20] R. Stanley, The number of faces of simplicial polytopes and spheres, Annals of the New York Academy of Sciences, 440 (1985), 212-223.

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

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

[23] E. Steingrímsson, Indexed Permutations and Poset Permutations, Ph.D. Thesis, 1991, Massachusetts Institute of Technology.

[24] J. Stembridge, Eulerian numbers, tableaux, and the Betti numbers of a toric variety, Discrete Math., 99(1992), 307-320.

[25] J. Stembridge, On the action of a Weyl group on the cohomology of its associated toric variety, preprint.

[26] D. Wagner, Total positivity of Hadamard products, J. Math. Analysis and Appl., 163 (1992), 459-483.