Séminaire Lotharingien de Combinatoire 74 (2016), Article B74c

ENUMERATING EXCEDANCES WITH LINEAR CHARACTERS IN CLASSICAL WEYL GROUPS

Sivaramakrishnan Sivasubramanian

Department of Mathematics Indian Institute of Technology, Bombay

                  email: krishnan@math.iitb.ac.in

Abstract. Several signed excedance-type statistics have nice formulae when summed over the symmetric group and over the hyperoctahedral group. Motivated by these, we consider sums of the form f_{χ,n}(q) = ∑_{w∈W} χ(w)q^{exc(w)} where W is a classical Weyl group of rank n, χ is a non-trivial one-dimensional character of W, and exc(w) is the excedance statistic of w.

We give formulae for these sums in a more general multivariate setting. We sharpen existing results for types A and B and give new results for classical Weyl groups of type B and type D.

1. Introduction

For a positive integer n, let [n] = {1, 2, …, n} and let 𝔖_{n} be the set of permutations on [n]. Let 𝔅_{n} be the set of permutations σ of {−n, −(n−1), …, −1, 1, 2, … n} satisfying σ(−i) = −σ(i). Clearly any such σ is well defined when given σ(i) for i ∈ [n]. 𝔅_{n} is referred to as the hyperoctahedral group or the group of signed permutations on [n]. Clearly, |𝔖_{n}| = n! and |𝔅_{n}| = 2^{n}n!. For σ ∈ 𝔅_{n} we alternatively denote σ(i) as σ_{i}. For 1 ≤ k ≤ n, we also denote −k alternatively as \overline{k}. For σ ∈ 𝔅_{n}, define NegSet(σ) = \{σ_{i} : i > 0, σ_{i} < 0\} be the set of elements which occur with a negative sign. Define 𝔇_{n} = {σ ∈ 𝔅_{n} : |NegSet(σ)| is even}. That is, 𝔇_{n} consists of the elements of 𝔅_{n} with an even number of negative elements. The three families of groups 𝔖_{n}, 𝔅_{n} and 𝔇_{n} are the classical Weyl groups of type A, type B and type D respectively.

Let π = π_{1}, π_{2}, …, π_{n} ∈ 𝔖_{n} be the one-line representation of π. Define its excedance set ExcSet_{A}(π) as {i ∈ [n] : π_{i} > i} and its number of excedances as exc(π) = |ExcSet_{A}(π)|. For π ∈ 𝔖_{n}, define its number of inversions as inv_{A}(π) = |{1 ≤ i < j ≤ n : π_{i} > π_{j}}|.

For a positive integer n ≥ 1, define SgnExc_{n}(q) = ∑_{π∈𝔖_{n}}(−1)^{inv_{A}(π)}q^{exc(π)} as the signed excedance enumerator of 𝔖_{n}. Let 𝔖𝔇_{n} be the set of derangements on [n]. We recall that, for a non-negative integer i, its q-analogue is defined as [i]_{q} = 1+q+q^{2}+⋯+q^{i−1}, where q is an indeterminate and [0]_{q} = 0. For n ≥ 1, define DerSgnExc_{n}(q) = ∑_{π∈𝔖𝔇_{n}}(−1)^{inv_{A}(π)}q^{exc(π)} as the signed excedance enumerator over derangements. The motivation for this work stems from the following two attractive results of Mantaci [6] and of Mantaci and Rakotondrajao [7].

Theorem 1 (Mantaci). For n ≥ 1, SgnExc_{n}(q) = (1 − q)^{n−1}.

Theorem 2 (Mantaci and Rakotondrajao). Let n ≥ 1 be a positive integer. Then,

DerSgnExc_{n}(q) = (−1)^{n−1}q · [n − 1]_{q}.

The original proofs of both results used sign reversing involutions and both papers prove more detailed results as well. An alternate proof of both these results was given by Sivasubramanian in [9]. Later, in [10], Sivasubramanian extended these results to 𝔅_{n}, in a more general bivariate setting.

For σ = σ_{1}, σ_{2}, …, σ_{n} ∈ 𝔅_{n}, Brenti [4] defined its number of excedances as exc(σ) = |{i ∈ [n] : σ_{|σ_{i}|} > σ_{i}}| + |{i ∈ [n] : σ_{i} = −i}|. This definition of Brenti was used by Sivasubramanian in [10]. For a multivariable generalisation, one definition of the set of excedances could thus be ExcSet(σ) = {i ∈ [n] : σ_{|σ_{i}|} > σ_{i}} ∪ {i ∈ [n] : σ_{i} = −i}. We have a different definition, which we give next.

For σ ∈ 𝔅_{n}, we define ExcSet_{A}(σ) = {|σ_{i}| : σ_{|σ_{i}|} > σ_{i}}, NegFixPtSet = {i ∈ [n] : σ_{i} = −i} and ExcSet_{B}(σ) = ExcSet_{A}(σ)∪NegFixPtSet(σ). Note that the union above is a disjoint union as ExcSet_{A}(σ) ∩ NegFixPtSet(σ) = ∅. This definition of ExcSet_{B}(σ) differs slightly from ExcSet(σ) given in the previous paragraph, though we still have exc(σ) = |ExcSet_{B}(σ)|. We mention our reason for this change. One way to think of this definition of excedances is to use the cycles of σ which we now discuss. Our definition of cycles of σ differs from the standard definition and so we define what we mean by cycles of σ. For σ ∈ 𝔅_{n}, let |σ| ∈ 𝔖_{n} be the permutation obtained by converting all negative entries \overline{i} for each i ∈ NegSet(σ) to i. Let C be a cycle of |σ| and in C change back each element i ∈ NegSet(σ) to \overline{i} and do this for all cycles C of σ. This gives the cycles of σ ∈ 𝔅_{n}.

When we write σ ∈ 𝔅_{n} or π ∈ 𝔖_{n} in one-line notation, then we do not place a parenthesis bordering its elements, but we use parenthesis to write the cycles of σ or π as follows. For example, if σ = 4, \overline{2}, 3, 5, \overline{1}, then |σ| = 4, 2, 3, 5, 1. The cycles of |σ| are C = (1, 4, 5), D = (2) and E = (3). Hence, the cycles of σ are C′ = (\overline{1}, 4, 5), D′ = (\overline{2}) and E′ = (3) and ExcSet_{B}(σ) = {1, 2, 4}. For 1 ≤ i ≤ n, to get σ_{i}, we locate ±i among the cycles of σ and define σ_{i} as the successor of ±i in that cycle. Our slightly modified definition of ExcSet_{B}(σ) is motivated by the 𝔖_{n} case where we say position i is an index of excedance if, in the cycle containing i, its successor is larger than i. Zhao in [11] also defines the excedance set ExcSet_{B}(σ) as we have done, and uses it to define exc(σ) = |ExcSet_{B}(σ)|, but does not enumerate excedances with several variables as we do.

We next give the definition of inversions in 𝔅_{n}. For σ ∈ 𝔅_{n}, recall that NegSet(σ) = {σ_{i} : σ_{i} < 0} is the set of negative values taken by σ, and let nsum(σ) = − ∑_{i∈NegSet(σ)} i be the absolute value of the sum of the negative elements that occur in σ. Define the number of type-A inversions of σ as before as inv_{A}(σ) = |{1 ≤ i < j ≤ n : σ_{i} > σ_{j}}|. Here, comparison is done with respect to the standard order on ℤ. Define the number of inversions of σ ∈ 𝔅_{n} as inv_{B}(σ) = nsum(σ) + inv_{A}(σ). This combinatorial definition of inversions in 𝔅_{n} is also due to Brenti (see [4, Proposition 3.1]). If σ ∈ 𝔅_{n}, define pos n(σ) as the index i ∈ [n] such that |σ_{i}| = n. Define

BSgnExc_{n}(q, t) = ∑_{σ∈𝔅_{n}}(−1)^{inv_{B}(σ)}q^{exc(σ)}t^{pos n(σ)}.

Let 𝔅𝔇_{n} = {σ ∈ 𝔅_{n} : σ_{i} ≠ i, for all i ∈ [n]} be the set of type-B derangements. Define

BDerSgnExc_{n}(q, t) = ∑_{σ∈𝔅𝔇_{n}}(−1)^{inv_{B}(σ)}q^{exc(σ)}t^{pos n(σ)}.

The following was shown by Sivasubramanian [10, Theorems 8, 22].

Theorem 3 (Sivasubramanian). For n ≥ 1, BSgnExc_{n}(q, t) = t^{n}(1−q)^{n} and, for n ≥ 1, BDerSgnExc_{n}(q, t) = (−qt)^{n}.

More general results with the exponent of t being the position of i were also given in [10]. Inspired by this result, Sivasubramanian proved the following bivariate generalisation of Theorem 1 and Theorem 2 for the type-A case. For π = π_{1}, π_{2}, …, π_{n} ∈ 𝔖_{n}, define pos n(π) as the index i such that π_{i} = n and define SgnExc_{n}(q, t) = ∑_{π∈𝔖_{n}}(−1)^{inv_{A}(π)}q^{exc(π)}t^{pos n(π)}. Similarly, for a positive integer n, define

DerSgnExc_{n}(q, t) = ∑_{π∈𝔖𝔇_{n}}(−1)^{inv_{A}(π)}q^{exc(π)}t^{pos n(π)}.

Sivasubramanian showed the following in [10, Theorems 10, 24].

Theorem 4 (Sivasubramanian). For n ≥ 1, SgnExc_{n}(q, t) = t^{n−1}(1 − q)^{n−2}(t − q) and for n ≥ 1, DerSgnExc_{n}(q, t) = (−1)^{n−1}qt[n − 1]_{qt}.

Note that setting t = 1 in Theorem 4 gives us Theorem 1 and Theorem 2. In this paper, we give multivariate generalisations of both results given in Theorem 4 (see Theorem 6 and Theorem 7) and, more generally, give similar multivariate results for classical Weyl groups when a non-trivial linear character of the Weyl group is used. Among other results, we prove the following more general type-B generalisation of Theorem 3. For σ ∈ 𝔅_{n}, define the monomial m_{σ} = ∏_{i∈ExcSet_{B}(σ)} q_{i}, where the q_{i}’s are commuting variables, and define the multivariate polynomial BSgnMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = ∑_{σ∈𝔅_{n}}(−1)^{inv_{B}(σ)}t^{pos n(σ)}m_{σ}. In Section 4, we prove the following.

Theorem 5. For n ≥ 1, we have

BSgnMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = t^{n} ∏_{i=1}^{n}(1 − q_{i}).

Note that setting q_{i} = q for all i ∈ [n] results in m_{σ} = q^{exc(σ)}. A similar multivariate result when enumeration is done over 𝔖𝔇_{n} is given in Theorem 13. Thus, Theorem 3 is a special case of Theorem 5 and Theorem 13. The proof in this paper is entirely different from the proof of Theorem 3 given in [10] and shows somewhat surprisingly, that when we fix S, the set of negative elements that σ ∈ 𝔅_{n} can take, then there are only four choices for S that result in non-zero enumerators (see Theorem 11). A similar four-choice based result is true when the term (−1)^{inv_{B}(σ)} is replaced by another non-trivial linear character (see Theorem 14).

Further, as a simple corollary of our proofs, we get similar signed excedance enumerators for type D Weyl groups. Recall that 𝔇_{n} = {σ ∈ 𝔅_{n} : |NegSet(σ)| is even}. The definition of excedance for elements σ ∈ 𝔇_{n} is identical to the definition when considered as an element of 𝔅_{n}. For σ ∈ 𝔇_{n}, the minimum number of generators required to write σ as a word for a suitable choice of generators (that is, its length in the Coxeter sense) is defined as inv_{D}(σ), see Section 5. With these generators, it is known that inv_{D}(σ) = inv_{B}(σ) − |NegSet(σ)| (see Brenti [4, Equation 45]). Thus, for σ ∈ 𝔇_{n}, we have (−1)^{inv_{D}(σ)} ≡ (−1)^{inv_{B}(σ)} (mod 2). Our main result about excedance enumeration in type-D Weyl groups is Theorem 18.

Reiner [8] enumerated descents in classical Weyl groups with respect to a linear character, and our work can be thought of as a counterpart of his, with excedances replacing descents.

For the symmetric group 𝔖_{n} it is well known that excedances and descents are identically distributed and that both are enumerated by the Eulerian polynomial (see MacMahon [5, vol. I, p. 186]). A comparison of Reiner’s results with ours reveals striking similarities when we enumerate descents and excedances along with non-trivial linear characters. This is true in the univariate case and true most of the times in the multivariate setting.

Signed enumeration of Mahonian statistics is also a well studied area. Adin, Gessel and Roichman gave formulae enumerating signed major indices in classical Weyl groups [1]. Later, Biagioli [2] gave formulae enumerating major indices twisted by a linear character in classical Weyl groups. Here we also give similar formulae, though we enumerate Eulerian statistics twisted by linear characters in classical Weyl groups.

2. Preliminaries on linear characters

We mention very briefly the relevant background on linear characters in this section. For a classical Weyl group W, a linear character is a group homomorphism χ : W → ℂ^{∗} where ℂ^{∗} is the multiplicative group of non-zero complex numbers. It is known that 𝔖_{n} has two linear characters, denoted triv and sign. For all positive integers n and π ∈ 𝔖_{n}, we have

1. the trivial character triv(π) = 1 and 2. the sign character sign(π) = (−1)^{inv_{A}(π)}. 𝔅_{n} has four linear characters denoted triv_{B}, sign_{B}, neg_{B} and prod_{B} defined as follows. For

all n ≥ 1, and σ ∈ 𝔅_{n}, we have (1) the trivial character triv_{B}(σ) = 1,

(2) the sign character sign_{B}(σ) = (−1)^{inv_{B}(σ)},

(3) the negative character neg_{B}(σ) = (−1)^{|NegSet(σ)|}, and

(4) the product character prod_{B}(σ) = (−1)^{inv_{B}(σ)+|NegSet(σ)|}. It can be checked that prod_{B}(σ) = sign(|σ|).

𝔇_{n} has two linear characters, denoted triv_{D} and sign_{D}. For all n ≥ 1 and σ ∈ 𝔇_{n}, we have 1. the trivial character triv_{D}(σ) = 1 and 2. the sign character sign_{D}(σ) = (−1)^{inv_{D}(σ)}. It can again be checked that sign_{D}(σ) = sign(|σ|). We refer the reader to Reiner [8] for a

proof that these are the only linear-characters for W. Since enumerating excedance with the trivial character gives us Eulerian polynomials of types A, B and D respectively, we focus in this paper on enumeration with non-trivial linear characters.

3. Type A Weyl Groups

In this section, we present Theorem 6, which is a multivariate generalization of a part of Theorem 4.

For π = π_{1}, π_{2}, …, π_{n} ∈ 𝔖_{n}, recall that ExcSet_{A}(π) = {i ∈ [n] : π_{i} > i}. Let pos n(π) be the index i such that π_{i} = n. Furthermore, let m_{π} = ∏_{i∈ExcSet_{A}(π)} q_{i}, where the q_{i}’s are commuting variables. Define

SgnMultiExc_{n}(q_{1}, q_{2}, …, q_{n−1}, t) = ∑_{π∈𝔖_{n}}(−1)^{inv_{A}(π)}t^{pos n(π)}m_{π}.

Note that when q_{i} = q for all i, then SgnMultiExc_{n}(q_{1}, q_{2}, …, q_{n−1}, t) = SgnExc_{n}(q, t).

Define the n × n matrix M_{n} = (m_{i,j})_{1≤i,j≤n} as follows. If j ≠ n and if i < j set m_{i,j} = q_{i}. If j ≠ n and if i ≥ j, set m_{i,j} = 1. If j = n and if i < n, set m_{i,n} = q_{i}t^{i} and set m_{n,n} = t^{n}.

In other words,

M_{n} = ( \begin{matrix}1 & q_{1} & q_{1} & ⋯ & q_{1}t \\ 1 & 1 & q_{2} & ⋯ & q_{2}t^{2} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & 1 & 1 & ⋯ & t^{n} \end{matrix} ) .

Theorem 6. For n ≥ 2, we have

SgnMultiExc_{n}(q_{1}, q_{2}, …, q_{n−1}, t) = t^{n−1}(t − q_{n−1}) ∏_{i=1}^{n−2}(1 − q_{i}).

Proof. We only sketch the proof as one part of it is identical to the proof of [10, Theorems 10, 24]. The identical part of the proof is to show SgnMultiExc_{n}(q_{1}, q_{2}, …, q_{n−1}, t) = det M_{n}. We then need to evaluate det M_{n}. For this, we will induct on n. The base case when n = 2 is clear. For 1 ≤ i ≤ n, let C_{i} denote the i-th column of M_{n}. Performing the column operation C_{1} = C_{1} − C_{2} and then evaluating the determinant, we get det M_{n} = t(1 − q_{1}) det M′_{n−1}, where M′_{n−1} is a matrix almost identical to M_{n}, but with variables q_{2}, q_{3}, …, q_{n−1}. Evaluating det M′_{n−1} by induction completes the proof. □

3.1. Enumeration over derangements. In this subsection, we derive a multivariate generalization of a part of Theorem 4 on derangements. For π = π_{1}, π_{2}, …, π_{n} ∈ 𝔖𝔇_{n}, let m_{π} be as defined above in Section 3. Define

DerSgnMultiExc_{n}(q_{1}, q_{2}, …, q_{n−1}, t) = ∑_{π∈𝔖_{n}}(−1)^{inv_{A}(π)}t^{pos n(π)}m_{π}.

Note that, when q_{i} = q for all i, then

DerSgnMultiExc_{n}(q_{1}, q_{2}, …, q_{n−1}, t) = DerSgnExc_{n}(q, t).

Define the n × n matrix D_{M_{n}} = (m_{i,j})_{1≤i,j≤n} as follows. First set D_{M_{n}} = M_{n} and then reset all its diagonal elements to be zero. In other words,

D_{M_{n}} = ( \begin{matrix}0 & q_{1} & q_{1} & ⋯ & q_{1}t \\ 1 & 0 & q_{2} & ⋯ & q_{2}t^{2} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & 1 & 1 & ⋯ & 0 \end{matrix} ) .

Theorem 7. For n ≥ 2, we have

DerSgnMultiExc_{n}(q_{1}, q_{2}, …, q_{n−1}, t) = (−1)^{n−1} {∑_{i=1}^{n−1} t^{i} ∏_{j=1}^{i} q_{j}} .

We again omit our proof as it is identical to the proof of Theorem 6. We only mention that we show DerSgnMultiExc_{n}(q_{1}, q_{2}, …, q_{n−1}, t) = det D_{M_{n}} and we then evaluate det D_{M_{n}}.

4. Type B Weyl groups

In this section, we prove results for excedance enumeration in 𝔅_{n}. There are three main results, one for each non-trivial linear character. In each case, we enumerate multivariate excedance with a different non-trivial linear character. In Subsection 4.1 we prove Theorem 11, in Subsection 4.2 we prove Theorem 14 and in Subsection 4.3 we prove Theorem 16. Further, we show results when summation is over the set of derangements 𝔅𝔇_{n} for two linear characters. These results are given in Subsections 4.1.1and 4.3.1.

4.1. The linear character sign_{B}. For a subset S ⊆ [n], define

𝔅_{n,S} = {σ ∈ 𝔅_{n} : NegSet(σ) = S}

to be the set of signed permutations in 𝔅_{n} with S as its set of negative elements. Clearly, for all S ⊆ [n], we have |𝔅_{n,S}| = n!. Define

BSgnMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t) = ∑_{σ∈𝔅_{n,S}}(−1)^{inv_{B}(σ)}t^{pos n(σ)}m_{σ}.

We will need the following refinement of 𝔅_{n,S}. Let n ≥ 1 and let S ⊆ [n]. For 1 ≤ k ≤ n, define 𝔅_{n,S,k} = {σ ∈ 𝔅_{n,S} : pos n(σ) = k}. Define

BSgnMultiExc_{n,S,k}(q_{1}, q_{2}, …, q_{n}, t) = ∑_{σ∈𝔅_{n,S,k}}(−1)^{inv_{B}(σ)}t^{pos n(σ)}m_{σ}.

Lemma 8. For n ≥ 3 and all S ⊆ [n], BSgnMultiExc_{n,S,k}(q_{1}, q_{2}, …, q_{n}, t) = 0 for k ≤ n − 2.

Proof. Let σ ∈ 𝔅_{n,S,k}. Clearly, pos n(σ) = k where k ≠ n, n − 1. Let σ_{n−1} = α and let σ_{n} = β. Since pos n(σ) ≠ n, n − 1, we get α ≠ n and β ≠ n. Let ψ be obtained from σ by swapping α and β. That is ψ = σ ∘ s_{n−1}, where s_{n−1} is the transposition (n − 1, n). Clearly ψ ∈ 𝔅_{n,S,k}.

We claim that we have inv_{B}(σ) ≢ inv_{B}(ψ) (mod 2), pos n(π) = pos n(σ) and m_{σ} = m_{ψ}. Since ψ = σ∘s_{n−1}, clearly inv_{B}(σ) ≢ inv_{B}(ψ) (mod 2). Further, since pos n(σ) ∉ {n−1, n}, we get pos n(σ) = pos n(ψ). Let C_{1} be the cycle of σ that contains the element ±n with the sign of n as it occurs in σ and likewise let cycle C_{2} contain ±(n − 1). Since σ_{n−1} = α and σ_{n} = β, in C_{1}, β will be the successor of n and, in C_{2}, α will be the successor of n − 1. Clearly, swapping α and β will not have any effect on elements i ∈ ExcSet_{B} with |i| < n − 1. If i = n − 1, then i ∈ ExcSet_{B}(σ) if and only if n − 1 occurs in σ with negative sign and this is independent of α and β. A similar argument is true for i = n as well. Thus, when i = n−1 or i = n, i ∈ ExcSet_{B}(σ) if and only if i ∈ ExcSet_{B}(ψ). Thus, ExcSet_{B}(σ) = ExcSet_{B}(ψ) and hence m_{σ} = m_{π}.

As we have paired up elements σ and ψ of 𝔅_{n,S,k} such that m_{σ} = m_{ψ}, pos n(σ) = pos n(ψ) and inv_{B}(σ) ≢ inv_{B}(ψ) (mod 2), the sum over elements of 𝔅_{n,S,k} is zero, completing the proof. □

Thus, for all S ⊆ [n], to calculate BSgnExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t), we only need to sum over those σ ∈ 𝔅_{n,S} with pos n(σ) ∈ {n − 1, n}. We next show that both of these can be done by induction on n. We need the following lemma when n = 2 for various subsets S ⊆ [n].

Lemma 9. Fix n = 2. Then,

BSgnMultiExc_{2,S}(q_{1}, q_{2}, t) = \begin{cases}t^{2} − tq_{1}, & ifS = ∅, \\ q_{1}(t − t^{2}), & ifS = \{1\}, \\ q_{2}(t − t^{2}), & ifS = \{2\}, \\ t^{2}q_{1}q_{2} − tq_{2}, & ifS = \{1, 2\}. \end{cases}

Proof. A simple calculation completes the proof. □

A simple consequence of Lemma 9 is obtained in the case |S| = 1, upon setting t = 1.

Corollary 10. For any S ⊆ [2] with |S| = 1, BSgnMultiExc_{2,S}(q_{1}, q_{2}, 1) = 0.

Our next result is the main result of this subsection. It shows, surprisingly, that only four of the 2^{n} choices for S give non-zero enumerator values.

Theorem 11. Let n ≥ 2 and S ⊆ [n]. Then BSgnMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t) takes the following values:

S  BSgnMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t)
∅  t^{n−1}(t − q_{n−1}) ∏_{i=1}^{n−2}(1 − q_{i})
[n] − {n} (t^{n−1} − t^{n})q_{n−1} ∏_{i=1}^{n−2}(1 − q_{i})
{n}  (t^{n−1} − t^{n})q_{n} ∏_{i=1}^{n−2}(1 − q_{i})
[n]  −t^{n−1}q_{n}(1 − tq_{n−1}) ∏_{i=1}^{n−2}(1 − q_{i})
otherwise 0

Proof. Recall that S is the set of negative elements for all the σ that we consider. When n = 2, the proof follows from Lemma 9 and so we assume n ≥ 3. When NegSet(σ) = S = ∅, there are no negative elements. When there are no negative elements, such σ ∈ 𝔅_{n} are actually elements of 𝔖_{n}. Considering π ∈ 𝔖_{n} as an element of 𝔅_{n}, from the definition, we clearly have inv_{A}(π) = inv_{B}(π). Thus, this case follows from Theorem 6. Hence, assume that S ≠ ∅. We split the rest of the proof into two cases.

Case 1 (when n ∉ S): Thus n occurs for all such σ as +n and S ⊆ [n − 1]. By Lemma 8, we only need to sum over σ ∈ 𝔅_{n,S,k} for k = n − 1 and k = n.

First, consider the case when k = n. Recall that 𝔅_{n,S,n} = {σ ∈ 𝔅_{n,S} : pos n(σ) = n}, and recall that

BSgnMultiExc_{n,S,n}(q_{1}, q_{2}, …, q_{n}, t) = ∑_{σ∈𝔅_{n,S,n}}(−1)^{inv_{B}(σ)}t^{pos n(σ)}m_{σ}.

For σ ∈ 𝔅_{n,S,n}, since pos n(σ) = n we get a common factor t^{n} from all terms in the summation. Since n ∉ S, we must have σ_{n} = +n for all σ ∈ 𝔅_{n,S,n}. Let ψ be the restriction of σ to indices 1, 2, …, n − 1. Clearly ψ ∈ 𝔅_{n−1,S} and all elements of 𝔅_{n−1,S} arise in this manner. Clearly, inv_{B}(σ) = inv_{B}(ψ). Further, as n occurs as +n in σ, n ∉ ExcSet_{B}(σ) and as other indices of excedance are identical, ExcSet_{B}(σ) = ExcSet_{B}(ψ). Thus, BSgnMultiExc_{n,S,n}(q_{1}, q_{2}, …, q_{n}, t) is t^{n} times BSgnMultiExc_{n−1,S}(q_{1}, q_{2}, …, q_{n−1}, t) with t set to 1. That is,

BSgnMultiExc_{n,S,n}(q_{1}, q_{2}, …, q_{n}, t) = t^{n}BSgnMultiExc_{n−1,S}(q_{1}, q_{2}, …, q_{n−1}, t = 1).

Next, consider σ ∈ 𝔅_{n,S} with pos n(σ) = n − 1. Recall that

𝔅_{n,S,n−1} = {σ ∈ 𝔅_{n,S} : pos n(σ) = n − 1},

and recall that

BSgnMultiExc_{n,S,n−1}(q_{1}, q_{2}, …, q_{n}, t) = ∑_{σ∈𝔅_{n,S,n−1}}(−1)^{inv_{B}(σ)}t^{pos n(σ)}m_{σ}.

Again, for all σ ∈ 𝔅_{n,S,n−1}, since pos n(σ) = n − 1 we get a common factor of t^{n−1} from all terms. As before, since n ∉ S, we must have σ_{n−1} = +n. Writing σ in cycle notation, we see that in the cycle containing n, the predecessor of n exists and is either n − 1 if n − 1 ∉ S or \overline{n − 1} if n − 1 ∈ S. Let ψ be obtained from σ by deleting the occurrence of +n from the cycles of σ. This means in cycle notation, we short circuit +n and set the successor of ±(n − 1) in ψ to be the successor of +n in σ. Clearly ψ ∈ 𝔅_{n−1,S} and all elements of 𝔅_{n−1,S} arise in this manner. We claim that inv_{B}(σ) ≢ inv_{B}(ψ) (mod 2). To see this, define ψ′ ∈ 𝔅_{n,S} by ψ′(i) = ψ(i) for 1 ≤ i ≤ n − 1 and ψ′(n) = n. Then it is easy to see that inv_{B}(ψ) ≡ inv_{B}(ψ′) (mod 2). Since ψ′ = σ ∘ s_{n−1}, we have inv_{B}(ψ′) ≢ inv_{B}(σ) (mod 2). Thus, inv_{B}(σ) ≢ inv_{B}(ψ) (mod 2). The relation between ExcSet_{B}(σ) and ExcSet_{B}(ψ) needs two more cases.

If n − 1 ∈ S, then, we claim ExcSet_{B}(σ) = ExcSet_{B}(ψ). To see this last equality, since n − 1 ∈ S, all σ have only occurrences of \overline{n − 1}. Thus, n − 1 ∈ ExcSet_{B}(ψ) as \overline{n − 1} is the minimum element and all successors of \overline{n − 1} in the cycle of ψ containing it will be equal or larger. In σ, the successor of \overline{n − 1} is +n and so n − 1 ∈ ExcSet_{B}(σ) and similarly, as n is the largest element, n ∉ ExcSet_{B}(σ). Thus, in this case,

BSgnMultiExc_{n,S,n−1}(q_{1}, q_{2}, …, q_{n}, t) = −t^{n−1}BSgnMultiExc_{n−1,S}(q_{1}, q_{2}, …, q_{n−1}, 1).

If n − 1 ∉ S, then, we claim ExcSet_{B}(σ) = ExcSet_{B}(ψ) ∪ {n − 1}. To see this, note that, as n − 1 ∉ S, and as (n − 1) is the largest element of ψ, n − 1 ∉ ExcSet_{B}(ψ). In σ, since the successor of n − 1 is +n, we have n − 1 ∈ ExcSet_{B}(σ) and, clearly, other excedance indices remain identical. Thus, in this case, we get

BSgnMultiExc_{n,S,n−1}(q_{1}, q_{2}, …, q_{n}, t)

= −t^{n−1}q_{n−1}BSgnMultiExc_{n−1,S}(q_{1}, q_{2}, …, q_{n−1}, 1).

Summing the relevant cases, if n ∉ S, we get

(1) BSgnMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t)

= \begin{cases}(t^{n} − t^{n−1}q_{n−1})BSgnMultiExc_{n−1,S}(q_{1}, q_{2}, …, q_{n−1}, 1), & if n − 1 ∉ S. \\ (t^{n} − t^{n−1})BSgnMultiExc_{n−1,S}(q_{1}, q_{2}, …, q_{n−1}, 1), & if n − 1 ∈ S. \end{cases}

Case 2 (when n ∈ S): Thus, \overline{n} appears in σ. The arguments are similar in this case. As before, we just need to sum the two cases when pos n(σ) = n and when pos n(σ) = n − 1. Recall the definitions of 𝔅_{n,S,n} and 𝔅_{n,S,n−1} and let T = S − {n}. When pos n(σ) = n, we claim that BSgnExc_{n,S,n}(q_{1}, q_{2}, …, q_{n}, t) = −t^{n}q_{n}BSgnExc_{n−1,T} (q_{1}, q_{2}, …, q_{n−1}, 1). To see this, restricting σ ∈ 𝔅_{n,S,n} to indices in [n − 1] gives us ψ where ψ ∈ 𝔅_{n−1,T} and every ψ ∈ 𝔅_{n−1,T} appears in this manner. Under this restriction, clearly ExcSet_{B}(σ) = ExcSet_{B}(ψ) ∪ \{n\} as σ_{n} = \overline{n}. Moreover, it is easy to see that inv_{B}(σ) ≢ inv_{B}(ψ) (mod 2). Thus, we get

BSgnMultiExc_{n,S,n}(q_{1}, q_{2}, …, q_{n}, t) = −t^{n}q_{n}BSgnMultiExc_{n−1,T} (q_{1}, q_{2}, …, q_{n−1}, 1).

If pos n(σ) = n−1, and if n−1 ∉ S, then n−1 occurs as +(n−1). Hence, when viewed as cycles, n − 1 is succeeded by \overline{n}. We claim that BSgnMultiExc_{n,S,n−1}(q_{1}, q_{2}, …, q_{n}, t) = t^{n−1}q_{n}BSgnMultiExc_{n−1,T} (q_{1}, q_{2}, …, q_{n−1}, 1). To see this, note that pos n(σ) = n − 1, and so we get a common factor of t^{n−1} from all such terms. Further, we have ExcSet_{B}(σ) = ExcSet_{B}(ψ) ∪ \{n\}. To see this, as \overline{n} is the least element of σ, it will be smaller than its successor and so n ∈ ExcSet_{B}(σ). Clearly, the other excedance indices are identical. Further, it is easy to see that inv_{B}(σ) ≡ inv_{B}(ψ) (mod 2). Thus, we get

BSgnMultiExc_{n,S,n−1}(q_{1}, q_{2}, …, q_{n}, t) = t^{n−1}q_{n}BSgnMultiExc_{n−1,T} (q_{1}, q_{2}, …, q_{n−1}, 1).

If pos n(σ) = n − 1, and if n − 1 ∈ S, then n − 1 occurs as \overline{n − 1}. In this case, we claim that

BSgnMultiExc_{n,S,n−1}(q_{1}, q_{2}, …, q_{n}, t)

= t^{n−1}q_{n}/q_{n−1}BSgnMultiExc_{n−1,T} (q_{1}, q_{2}, …, q_{n−1}, 1).

To see this, let ψ ∈ 𝔅_{n−1,T} be obtained from σ ∈ 𝔅_{n,S} by short-circuiting n. Under this correspondence, it is easy to see that inv_{B}(σ) ≡ inv_{B}(ψ) (mod 2). Further, we claim that ExcSet_{B}(σ) = ExcSet_{B}(ψ) − \{n − 1\} ∪ \{n\}. To see this, note that, as \overline{n − 1} is the smallest element of ψ, n − 1 ∈ ExcSet_{B}(ψ). In σ, however, since \overline{n} is the successor of \overline{n − 1}, n − 1 ∉ ExcSet_{B}(σ), while n ∈ ExcSet_{B}(σ) as \overline{n} is the smallest element. As the other indices of excedance are identical, we get

BSgnMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t)

= t^{n−1}q_{n}/q_{n−1} · BSgnMultiExc_{n−1,T} (q_{1}, q_{2}, …, q_{n−1}, 1).

Adding the relevant cases, if n ∈ S, recalling T = S − {n}, we get

(2) BSgnMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t)

= \begin{cases}(t^{n−1} − t^{n})q_{n}BSgnMultiExc_{n−1,T} (q_{1}, q_{2}, …, q_{n−1}, 1), & if n − 1 ∉ S, \\ (t^{n−1}/q_{n−1} − t^{n})q_{n}BSgnMultiExc_{n−1,T} (q_{1}, q_{2}, …, q_{n−1}, 1), & if n − 1 ∈ S. \end{cases}

We next show by induction on n that BSgnMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, 1) ≠ 0 only when S = ∅ and S = [n]. The base case is when n = 2 and follows from Corollary 10. Assume that the statement is true for all positive integers up to n − 1 and for all S ⊆ [n − 1]. Consider the next positive integer n. If BSgnMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, 1) ≠ 0, and if n ∉ S, by reverse induction on n, using (1) we get that S = ∅ is the only possibility. Similarly, if n ∈ S, using (2) we get that S = [n] is the only possibility.

When S = ∅, it is easy to see from (1) that

BSgnMultiExc_{n,∅}(q_{1}, q_{2}, …, q_{n}, 1) = ∏_{i=1}^{n−1}(1 − q_{i}).

This also follows from the type-A result, that is, from Theorem 6. When S = [n], we claim that

BSgnMultiExc_{n,[n]}(q_{1}, q_{2}, …, q_{n}, 1) = −q_{n} ∏_{i=1}^{n−1}(1 − q_{i}).

This can be seen as follows. Let π = π_{1}, π_{2}, …, π_{n} ∈ 𝔖_{n} and let \overline{π} ∈ 𝔅_{n} be obtained from π by negating π_{i} for all i ∈ [n]. It is easy to see when π and \overline{π} are viewed as elements of 𝔅_{n}, that inv_{B}(π) = (−1)^{n} · inv_{B}(\overline{π}) and that ExcSet_{B}(π) = [n] − ExcSet_{B}(\overline{π}). Coupling these observations with Theorem 6 gives us

BSgnExc_{n,[n]}(q_{1}, q_{2}, …, q_{n}, 1) = −q_{n} ∏_{i=1}^{n−1}(1 − q_{i}).

Hence, we infer that BSgnMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t) ≠ 0 for only four values of S. These four values are given in the statement of the theorem. Further, it is simple to compute this value for each of the four choices of S and to see that they agree with the given expression. This completes the proof of the theorem. □

A simple corollary of Theorem 11 is Theorem 5.

Proof of Theorem 5. BSgnMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = t^{n} ∏_{i=1}^{n}(1−q_{i}) can be obtained by summing over the four choices of S given in Theorem 11, completing the proof. □

4.1.1. Enumeration over Derangements. Recall that 𝔅𝔇_{n} ⊆ 𝔅_{n} is the set of type B derangements. Here, we present results when enumeration is done over 𝔅𝔇_{n}. However, we are unable to find results when the set S of negative elements is fixed. Hence, our proof is somewhat different.

Before we state Theorem 13, which is our main result, we need a preliminary lemma. At the heart, our proof is identical to the proof of [10, Theorem 8]. However, since the definition of ExcSet_{B}(σ) is different in this paper when compared to that given in [10], we present a proof.

The involution τ_{r}: For r ∈ [n], define an involution τ_{r} : 𝔅_{n} → 𝔅_{n} as follows. We let τ_{r}(σ) = ψ_{1}ψ_{2} … ψ_{n}, where ψ_{i} = σ_{i} if ψ_{i} ≠ ±r, and ψ_{i} = −σ_{i} otherwise. We prove the following property of τ_{r}.

Lemma 12. Let σ ∈ 𝔅_{n} and m > 0 be the minimal element in absolute value in a cycle of σ of length at least two. That is, m ≠ |σ_{m}| and m = min(m, |σ(m)|, |σ^{2}(m)|, …). Furthermore, let ψ = τ_{|m|}(σ). Then ExcSet_{B}(σ) = ExcSet_{B}(ψ).

Proof. Let C be a cycle of σ with length larger than two and let m = min{|x| : x ∈ C}. Assume that m appears with positive sign in σ and \overline{m} appears in ψ (otherwise, change the names of σ and ψ). Thus, for this proof we may assume m > 0. As C has length larger than 2, denote the successor of m by succ(m) and the predecessor of m by pred(m). The cycles of ψ are identical to those of σ, with the only difference being the sign of m. Since m changes sign, ExcSet_{A}(σ) − ExcSet_{A}(ψ) ⊆ {m, pred(m)}. We claim that ExcSet_{A}(σ) = ExcSet_{A}(ψ).

Since ExcSet_{A}(σ) = {|σ_{i}| : σ_{|σ_{i}|} > σ_{i}}, if m ∈ ExcSet_{A}(σ), then m < succ(m). Thus −m < succ(m) and m ∈ ExcSet_{A}(ψ). Similarly, if m ∉ ExcSet_{A}(σ), then by definition m > succ(m). As m has least |x| value over x ∈ C, we must have succ(m) < 0. Hence \overline{m} > succ(m) and so m ∉ ExcSet_{A}(ψ). Thus, m ∈ ExcSet_{A}(σ) if and only if m ∈ ExcSet_{A}(ψ).

If pred(m) ∈ ExcSet_{A}(σ), then we must have pred(m) < m. Since m > 0 and m has least absolute value, pred(m) < 0. Thus, in our notation, |pred(m)| ∈ ExcSet_{A}(σ) and we clearly have pred(m) < \overline{m} and so |pred(m)| ∈ ExcSet_{A}(ψ). Likewise, if pred(m) ∉ ExcSet_{A}(σ), then, we must have pred(m) > m. Since m > 0, and m has least absolute value, pred(m) > m > 0. Thus, pred(m) > \overline{m} and thus pred(m) ∉ ExcSet_{A}(ψ). Thus, pred(m) ∈ ExcSet_{A}(σ) if and only if pred(m) ∈ ExcSet_{A}(ψ). Since NegFixPtSet(σ) = NegFixPtSet(ψ), we have ExcSet_{B}(σ) = ExcSet_{B}(ψ). □

For n ≥ 1, define

BDerSgnMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = (−1)^{inv_{B}(σ)}t^{pos n(σ)}m_{σ}.

Our main result is the following generalization of a part of Theorem 3.

Theorem 13. For n ≥ 1, we have

BDerSgnMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = (−t)^{n} ∏_{i=1}^{n} q_{i}.

Proof. For σ ∈ 𝔅𝔇_{n}, let ℓ(σ) be the largest index i ∈ [n] such that σ_{i} ≠ −i. As σ ∈ 𝔅𝔇_{n}, σ_{i} ≠ i for all i, and thus ℓ(σ) is not defined if and only if |σ| is the identity permutation id.

For σ ∈ 𝔅𝔇_{n} with |σ| ≠ id, let m be the smallest element in absolute value such that σ(m) ≠ −m and let ψ = τ_{|m|}(σ). Clearly, ψ ∈ 𝔅𝔇_{n}. By Lemma 12, ExcSet_{B}(σ) = ExcSet_{B}(ψ). By [10, Lemma 3], inv_{B}(σ) ≢ inv_{B}(ψ) (mod 2). Thus, the multivariate polynomial BDerSgnMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t) will not get any contribution from any such σ.

Hence, the only σ that contribute are those with ℓ(σ) undefined. Stated differently, only σ such that |σ| = id survive the cancellations. Thus, only one element ψ = −id ∈ 𝔅𝔇_{n} with ψ_{i} = −i for i ∈ [n] contributes. Clearly, pos n(ψ) = n, sign_{B}(ψ) = (−1)^{n} and since ExcSet_{B}(ψ) = [n], m_{ψ} = ∏_{i=1}^{n} q_{i}. That is, BDerSgnMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t) = (−t)^{n} ∏_{i=1}^{n} q_{i}, completing the proof. □

4.2. The linear character prod_{B}. Recall that prod_{B}(σ) = (−1)^{inv_{B}(σ)+|NegSet(σ)|} for σ ∈ 𝔅_{n}. For a positive integer n ≥ 1, define

BProdMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = ∑_{σ∈𝔅_{n}} prod_{B}(σ)t^{pos n(σ)}m_{σ}

As before, define

BProdMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t) = ∑_{σ∈𝔅_{n,S}} prod_{B}(σ)t^{pos n(σ)}m_{σ}

for S ⊆ [n]. The main result of this section is the following counterpart of Theorem 11.

Theorem 14. Let n ≥ 2. Then BProdMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t) takes the following values:

S  BProdMultiExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t)
∅  t^{n−1}(t − q_{n−1}) ∏_{i=1}^{n−2}(1 − q_{i})
[n] − {n} (−1)^{n}(t^{n} − t^{n−1})q_{n−1} ∏_{i=1}^{n−2}(1 − q_{i})
{n}  (t^{n} − t^{n−1})q_{n} ∏_{i=1}^{n−2}(1 − q_{i})
[n]  (−t)^{n−1}q_{n}(1 − tq_{n−1}) ∏_{i=1}^{n−2}(1 − q_{i})
otherwise 0

Proof. The proof of this theorem works in the same way as the proof of Theorem 11, and hence we only sketch the salient points. To see that the earlier proof works, note that those terms which cancel due to Lemma 8 when the exponent of (−1) is inv_{B}(σ) also cancel when the exponent of (−1) is inv_{B}(σ) + |NegSet(σ)|, as we only switch the elements at the two positions n − 1, n, and thus NegSet(σ) = NegSet(ψ), where ψ is as defined in Lemma 8. Moreover, cancellations in the inductive step also work as we do not flip the sign of any element in the earlier proof. The only difference is that, since the exponent of (−1) now has an extra term of |NegSet(σ)|, we multiply the enumerator in the case when NegSet(σ) = S by |S|. This change manifests itself in slightly modified enumerators. This completes the proof of the theorem. □

Define without the term t^{pos n(σ)},

BProdMultiExc_{n}(q_{1}, q_{2}, …, q_{n}) = ∑_{σ∈𝔅_{n}} prod_{B}(σ)m_{σ}.

A simple corollary of Theorem 14 is the following, whose straightforward proof we omit.

Theorem 15. For positive integers n, we have

BProdMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t)

= \begin{cases}t^{n}(1 + q_{n}) ∏_{i=1}^{n−1}(1 − q_{i}), & ifn is odd, \\ \{t^{n}(1 + q_{n−1} + q_{n} + q_{n}q_{n−1}) − 2t^{n−1}(q_{n−1} + q_{n})\} ∏_{i=1}^{n−2}(1 − q_{i}), & ifn is even. \end{cases}

In particular, for positive integers n, we have

BProdMultiExc_{n}(q_{1}, q_{2}, …, q_{n}) = \begin{cases}(1 + q_{n}) ∏_{i=1}^{n−1}(1 − q_{i}), & ifn is odd, \\ ∏_{i=1}^{n}(1 − q_{i}), & ifn is even. \end{cases}

4.3. The linear character neg_{B}. Recall that neg_{B}(σ) = (−1)^{|neg(σ)|} for σ ∈ 𝔅_{n}. For a positive integer n ≥ 1, define

BNegMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = ∑_{σ∈𝔅_{n}} neg_{B}(σ)t^{pos n(σ)}m_{σ}.

For this enumerator, we are unable to get detailed information with respect to a given subset S of negative elements as in the previous two subsections. Nonetheless, we show the following about BNegMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t). Our proof needs both the involution τ_{r} defined in Subsubsection 4.1.1and Lemma 12. Our main result is the following.

Theorem 16. For n ≥ 1, we have BNegMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = t^{n} ∏_{i=1}^{n}(1 − q_{i}).

Proof. For σ ∈ 𝔅_{n}, let ℓ(σ) be the largest index i ∈ [n] such that σ_{i} ≠ ±i. Note that ℓ(σ) is not defined if and only if |σ| is the identity permutation id. For σ ∈ 𝔅_{n} with |σ| ≠ id, let m be the smallest element in absolute value such that σ(m) ≠ −m and let ψ = τ_{|m|}(σ). By Lemma 12, ExcSet_{B}(σ) = ExcSet_{B}(π) and, since the element m has its sign changed,

|NegSet(σ)| ≢ |NegSet(ψ)| (mod 2).

Thus, all such σ do not contribute to BNegMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t).

Hence, only those σ obtained by changing the signs of some elements of the identity permutation id survive. All such permutations have pos n(σ) = n and any such σ with NegSet(σ) = S will contribute (−1)^{|S|} ∏_{i∈S} q_{i}. Since S ⊆ [n], we have

BNegMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = t^{n} ∑_{S⊆[n]}(−1)^{|S|} ∏_{i∈S} q_{i}.

That is,

BNegMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = t^{n} ∏_{i=1}^{n}(1 − q_{i}),

completing the proof. □

4.3.1. Enumeration over Derangements. We prove an analogue of Theorem 13 for the linear character neg_{B}(σ). Define

BDerNegMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = ∑_{σ∈𝔅𝔇_{n}} neg_{B}(σ)t^{pos n(σ)}m_{σ}.

For this enumerator, we show the following.

Theorem 17. For n ≥ 1, we have

BDerNegMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = (−t)^{n} ∏_{i=1}^{n} q_{i}.

Proof. Arguments as in the proof of Theorem 13 show that only one σ ∈ 𝔅_{n} survives the cancellations. This is the permutation ψ = −id with ψ_{i} = −i for all i ∈ [n]. We clearly get

BDerNegMultiExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = (−t)^{n} ∏_{i=1}^{n} q_{i},

completing the proof. □

5. Type D Weyl Groups

Recall that 𝔇_{n} = {σ ∈ 𝔅_{n} : |NegSet(σ)| = even}. It is well known (see [3]) that 𝔇_{n} is generated by s\overline{1}, s_{1}, s_{2}, …, s_{n−1}, where s\overline{1} = (−2, −1) and s_{i} for 1 ≤ i < n is as in the type-A case. Define

DSgnExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = ∑_{σ∈𝔇_{n}}(−1)^{inv_{D}(σ)}t^{pos n(σ)}m_{σ}.

The main result of this section is the following.

Theorem 18. For even positive integers n = 2k, with k ≥ 1, we have

DSgnExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = (∏_{i=1}^{n−2}(1 − q_{i})) [t^{n−1}(−q_{n−1} − q_{n}) + t^{n}(1 + q_{n−1}q_{n})].

For odd positive integers n = 2k+1, we have DSgnExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = t^{n} ∏_{i=1}^{2k}(1−q_{i}).

Proof. As mentioned in Section 1, though each σ ∈ 𝔇_{n} has two statistics inv_{B}(σ) and inv_{D}(σ), we have (−1)^{inv_{B}(σ)} ≡ (−1)^{inv_{D}(σ)} (mod 2). Thus, we have

DSgnExc_{n}(q_{1}, q_{2}, …, q_{n}, t) = ∑_{S⊆[n],|S| even}BSgnExc_{n,S}(q_{1}, q_{2}, …, q_{n}, t).

Consider the case when n is an even positive integer first. For n ≥ 2, from Theorem 11, we need to add the two cases when S = ∅ and when S = [n]. A simple addition proves the result. Next, consider the case when n is odd. Here, we need to add the cases when S = ∅ and S = [n] − {n}. Adding these two cases completes the proof. □

We end this paper with a problem. The set T_{n} of σ ∈ 𝔇_{n} which survive the cancellations that occur in the proof of Theorem 18 has an inductive structure. We have another candidate set Q_{n} with

∑_{σ∈Q_{n}}(−1)^{inv_{D}(σ)}t^{pos n(σ)}m_{σ} = DSgnExc_{n}(q_{1}, q_{2}, …, q_{n}, t).

However, we are unable to show a sign reversing involution on the elements σ ∈ 𝔇_{n} − Q_{n}. We define the set Q_{n} for even positive integers n first. For n = 2, Q_{2} = 𝔇_{2}. For n = 2(k+1), consider each σ ∈ Q_{2k} and form four signed permutations ψ_{r} for r = 1, 2, 3, 4 as follows. For each r = 1, 2, 3, 4 and i ∈ [2k], define ψ_{r}(i) = σ(i). Further, define

ψ_{1}(2k + 1) = 2k + 1 and ψ_{1}(2k + 2) = 2k + 2,
ψ_{2}(2k + 1) = 2k + 2 and ψ_{2}(2k + 2) = 2k + 1,
ψ_{3}(2k + 1) = −(2k + 1) and ψ_{3}(2k + 2) = −(2k + 2),
ψ_{4}(2k + 1) = −(2k + 2) and ψ_{4}(2k + 2) = −(2k + 1).

Thus, we get four signed permutations for each σ ∈ Q_{2k} and denote by Q_{2k+2} the set of such signed permutations obtained. Clearly, for all k, Q_{2k} ⊆ 𝔇_{2k} and |Q_{2k}| = 2^{2k}. As an example, we illustrate this procedure and get Q_{4} from Q_{2}. We write σ ∈ 𝔇_{n} consecutively for brevity. Since Q_{2} = \{12, 21, \overline{12}, \overline{21}\}, we get

Q_{4} = \{1234, 1243, 12\overline{34}, 12\overline{43}\} ∪ \{2134, 2143, 21\overline{34}, 21\overline{43}\}

∪ \{\overline{12}34, \overline{12}43, \overline{1234}, \overline{1243}\} ∪\{\overline{21}34, \overline{21}43, \overline{2134}, \overline{2143}\},

where the set of ψ_{i}’s obtained from each σ ∈ 𝔇_{2} is given separately for clarity. For odd positive integers n = 2k + 1 define Q_{n} as follows. In this case, we obtain Q_{2k+1} from Q_{2k} by the following process. For each σ ∈ Q_{2k}, define ψ by ψ(i) = σ(i) for i ∈ [2k] and define ψ(2k + 1) = 2k + 1. Do this for each σ ∈ Q_{2k} and let Q_{2k+1} be the set of ψ so obtained. Clearly, Q_{2k+1} ⊆ 𝔇_{2k+1} and |Q_{2k+1}| = 2^{2k}. For example, Q_{3} = \{123, 213, \overline{12}3, \overline{21}3\}. It is easy to check by induction on n that

∑_{σ∈Q_{n}}(−1)^{inv_{D}(σ)}t^{pos n(σ)}m_{σ} = DSgnExc_{n}(q_{1}, q_{2}, …, q_{n}, t).

With this notation, we state our problem below.

Problem 19. Show that for all n there is an involution ϕ : (𝔇_{n} − Q_{n}) → (𝔇_{n} − Q_{n}) such that for all σ ∈ 𝔇_{n} − Q_{n}, pos n(σ) = pos n(ϕ(σ)), ExcSet_{B}(σ) = ExcSet_{B}(ϕ(σ)) and inv_{D}(σ) ≢ inv_{D}(ϕ(σ)) (mod 2).

Acknowledgement

I thank the referees for their valuable comments and helpful suggestions. Support from project grant 15IRCCFS003, given by IRCC, IIT Bombay is gratefully acknowledged.

References

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

[2] Biagioli, R. Signed Mahonian polynomials for classical Weyl groups. European Journal of Combinatorics 27 (2006), 207–217. [4]

[3] Björner, A., and Brenti, F. Combinatorics of Coxeter Groups. GTM 231, Springer Verlag, 2005. [13]

[4] Brenti, F. q-Eulerian polynomials arising from Coxeter groups. European Journal of Combinatorics 15 (1994), 417–441. [2, 3]

[5] MacMahon, P. A. Combinatory Analysis. Cambridge University Press, 1915-1916 (Reprinted by AMS Chelsea, 2000). [3]

[6] Mantaci, R. Statistiques Eulériennes sur les Groupes de Permutation. Ph.D. thesis, Université Paris, 1991. [1]

[7] Mantaci, R., and Rakotondrajao, F. Exceedingly deranging! Advances in Applied Mathematics 30 (2003), 177–188. [1]

[8] Reiner, V. Descents and one-dimensional characters for classical Weyl groups. Discrete Mathematics 140 (1995), 129–140. [3, 4]

[9] Sivasubramanian, S. Signed excedance enumeration via determinants. Advances in Applied Mathematics 47 (2011), 783–794. [2]

[10] Sivasubramanian, S. Signed excedance enumeration in the hyperoctahedral group. Electronic Journal of Combinatorics 21(2) (2014), P2.10. [2, 3, 5, 10, 11]

[11] Zhao, A. F. Excedance numbers for permutations of type B. Electronic Journal of Combinatorics 20(2) (2013), #P 28. [10]