Séminaire Lotharingien de Combinatoire 53 (2006), Article B53f

ON THE EXCEDANCE NUMBER OF COLORED PERMUTATION GROUPS

ELI BAGNO AND DAVID GARBER

Abstract. We generalize the results of Ksavrelof and Zeng about the multidistribution of the excedance number of S_{n} with some natural parameters to the colored permutation group and to the Coxeter group of type D. We define two different orders on these groups which induce two different excedance numbers. Surprisingly, in the case of the colored permutation group, we get the same generalized formulas for both orders.

1. Introduction

Let r and n be two positive integers. The colored permutation group G_{r,n} consists of all permutations of the set

Σ = {1, …, n, ¯1, …, n̄, …, 1^{[r−1]}, …, n^{[r−1]}}

satisfying π(ī) = \overline{π(i)}.

The symmetric group S_{n} is a special case of G_{r,n} for r = 1. In S_{n} one can define the following well-known parameters: given σ ∈ S_{n}, i ∈ [n] is an excedance of σ if and only if σ(i) > i. The number of excedances is denoted by exc(σ). Two other natural parameters on S_{n} are the number of fixed points and the number of cycles of σ, denoted by fix(σ) and cyc(σ) respectively.

Consider the following generating function over S_{n}:

P_{n}(q, t, s) = ∑_{σ∈S_{n}} q^{exc(σ)}t^{fix(σ)}s^{cyc(σ)}.

P_{n}(q, 1, 1) is the classical Eulerian polynomial, while P_{n}(q, 0, 1) is the counter part for the derangements, i.e., the permutations without fixed points, see [2].

In the case s = −1, the two polynomials P_{n}(q, 1, −1) and P_{n}(q, 0, −1) have simple closed formulas:

(1)  P_{n}(q, 1, −1) = −(q − 1)^{n−1}

(2)  P_{n}(q, 0, −1) = −q[n − 1]_{q}

Recently, Ksavrelof and Zeng [1] proved some new recursive formulas which induce Equations (1) and (2).

A natural problem is to generalize the results of [1] to the colored permutation groups. The main challenge here is to choose a suitable order on the alphabet Σ of the group G_{r,n} and define the parameters properly.

In this paper we cope with this challenge. We define two different orders on Σ, one of them ’forgets’ the colors, while the other is much more natural, since it takes into account the color structure of G_{r,n}. The parameter exc will be defined according to both orders in two different ways. The interesting point is that for the group G_{r,n} we get the same recursive formulas for both cases.

Define

P_{G_{r,n}}(q, t, s) = ∑_{π∈G_{r,n}} q^{exc(π)}t^{fix(π)}s^{cyc(π)}.

Concerning G_{r,n}, we prove the following two main results:

Theorem 1.1.

P_{G_{r,n}}^{Abs}(q, 1, −1) = P_{G_{r,n}}^{Clr}(q, 1, −1) = (q^{r} − 1)P_{G_{r,n−1}}(q, 1, −1).

Hence,

P_{G_{r,n}}^{Abs}(q, 1, −1) = P_{G_{r,n}}^{Clr}(q, 1, −1) = −\frac{(q^{r} − 1)^{n}}{q − 1} .

Theorem 1.2.

P_{G_{r,n}}^{Abs}(q, 0, −1) = P_{G_{r,n}}^{Clr}(q, 0, −1) = [r]_{q}(P_{G_{r,n−1}}(q, 0, −1) − q^{n−1}[r]_{q}^{n−1}).

Hence,

P_{G_{r,n}}^{Abs}(q, 0, −1) = P_{G_{r,n}}^{Clr}(q, 0, −1) = −q[r]_{q}^{n}[n − 1]_{q}.

Even though P_{G_{r,n}}(q, 0, −1) is a special case of P_{G_{r,n}}(q, s, t), we can deduce a formula for the exponential generating function of the general case as presented in the following corollary:

Corollary 1.3.

∑_{n≥0} P_{G_{r,n}}(q, s, t)\frac{x^{n}}{n!} = (∑_{n≥0} (\frac{[r]_{q}^{n}}{1 − q} ((q − s)^{n} − q(1 − s)^{n})) \frac{x^{n}}{n!} )^{−t} .

One can easily check that the formulas appeared in Theorem 1.1, Theorem 1.2 and Corollary 1.3 indeed generalize the formulas of Ksavrelof and Zeng (for r = 1).

As noted above, in the symmetric group case, the polynomials P_{n}(q, 1, 1) are equal to the Eulerian polynomials, which are usually defined using descent numbers. It is possible to define descent numbers for the colored permutation groups, which are equidistributed with our parameters. A work in this direction is in progress.

We apply our techniques also to obtain permutations statistics on the group of even signed permutations, D_{n}, also known as the Coxeter group of type D. We get the following results:

Theorem 1.4.

P_{D_{n}}^{Clr}(q, 1, −1) = (q^{2} − 1)P_{D_{n−1}}^{Clr}(q, 1, −1).

Hence,

P_{D_{n}}^{Clr}(q, 1, −1) = (1 − q^{2})^{n−1}.

Theorem 1.5.

P_{D_{n}}^{Abs}(q, 1, −1) = −\frac{1}{2}(q − 1)^{n−1}((1 + q)^{n} + (1 − q)^{n}).

This paper is organized as follows. In Section 2, we recall some properties of G_{r,n}. In Section 3 we define the new statistics on G_{r,n}. Sections 4 and 5 deal with the proofs of Theorems 1.1 and 1.2 respectively. Section 6 deals with the proof of Corollary 1.3. Section 7 includes the proofs of Theorems 1.4 and 1.5.

2. Preliminaries

2.1. Notations. For n ∈ ℕ, let [n] := {1, 2, …, n} (where [0] := ∅). Also, let

[n]_{q} := \frac{1 − q^{n}}{1 − q} = 1 + q + ⋯ + q^{n−1}

(so [0]_{q} = 0), and

[n]_{q}! := [n]_{q} · [n − 1]_{q} ⋯ [1]_{q}.

2.2. The group of colored permutations.

Definition 2.1. Let r and n be positive integers. The group of colored permutations of n digits with r colors is the wreath product

G_{r,n} = ℤ_{r} ≀ S_{n} = ℤ_{r}^{n} ⋊ S_{n},

consisting of all the pairs (z, τ) where z is an n-tuple of integers between 0 and r − 1 and τ ∈ S_{n}. The multiplication is defined by the following rule: for z = (z_{1}, ..., z_{n}) and z′ = (z′_{1}, ..., z′_{n})

(z, τ) · (z′, τ′) = ((z_{1} + z′_{τ(1)}, ..., z_{n} + z′_{τ(n)}), τ ∘ τ′)

(here + is taken modulo r).

We use some conventions along this paper. For an element π = (z, τ) ∈ G_{r,n} with z = (z_{1}, ..., z_{n}) we write z_{i}(π) = z_{i}. For π = (z, τ), we denote |π| = (0, τ), (0 ∈ ℤ_{r}^{n}). An element

(z, τ) = ((1, 0, 3, 2), (2, 1, 4, 3)) ∈ G_{3,4}

will be written as (¯21¯¯¯4¯¯3).

A much more natural way to present G_{r,n} is the following. Consider the alphabet Σ = {1, …, n, ¯1, …, n̄, …, 1^{[r−1]}, …, n^{[r−1]}} as the set [n] colored by the colors 0, …, r − 1. Then, an element of G_{r,n} is a colored permutation, i.e., a bijection π : Σ → Σ such that π(ī) = \overline{π(i)}.

In particular, G_{1,n} = C_{1} ≀S_{n} is the symmetric group S_{n}, while G_{2,n} = C_{2} ≀ S_{n} is the group of signed permutations B_{n}, also known as the hyperoctahedral group, or the classical Coxeter group of type B. We also define here the following normal subgroup of B_{n} of index 2, called the even signed permutation group or the Coxeter group of type D:

D_{n} = {π ∈ B_{n} | ∑_{i=1}^{n} z_{i}(π) ≡ 0 (mod 2)}.

3. Statistics on G_{r,n}

Given any ordered alphabet Σ′, we recall the definition of the excedance set of a permutation π on Σ′:

Exc(π) = {i ∈ Σ′ | π(i) > i}

and the excedance number is defined to be exc(π) = |Exc(π)|. We start by defining two orders on the set

Σ = {1, …, n, ¯1, …, n̄, …, 1^{[r−1]}, …, n^{[r−1]}}.

Definition 3.1. The absolute order on Σ is defined to be

1^{[r−1]} <⋯ < ¯1 < 1 < 2^{[r−1]} < ⋯ < ¯2 < 2 < ⋯ < n^{[r−1]} < ⋯ < n̄<n.

The color order on Σ is defined to be

1^{[r−1]} <⋯ < n^{[r−1]} < 1^{[r−2]} < 2^{[r−2]} < ⋯ < n^{[r−2]} < ⋯ < 1 < ⋯< n.

Example 3.2. Given the color order

¯¯1 < ¯ ¯2 < ¯ ¯3 < ¯1 < ¯2 < ¯3 < 1 < 2 < 3,

we write σ = (3¯1¯¯2) ∈ G_{3,3} in an extended form,

(\begin{matrix}¯¯1 & ¯¯2 & ¯¯3 & ¯1 & ¯2 & ¯3 & 1 & 2 & 3 \\ ¯¯3 & 1 & ¯2 & ¯3 & ¯¯1 & 2 & 3 & ¯1 & ¯¯2 \end{matrix})

and calculate Exc(σ) = {¯¯1, ¯ ¯2, ¯ ¯3, ¯1, ¯3, 1} and exc(σ) = 6.

Before defining the excedance numbers with respect to both orders, we have to introduce some notions.

Let σ ∈ G_{r,n}. We define

csum(σ) = ∑_{i=1}^{n} z_{i}(σ),
Exc_{A}(σ) = {i ∈ [n − 1] | σ(i) > i},

where the comparison is with respect to the color order, and

exc_{A}(σ) = |Exc_{A}(σ)|.

Example 3.3. Take σ = (¯1¯¯34¯2) ∈ G_{3,4}. Then csum(σ) = 4, Exc_{A}(σ) = {3} and hence exc_{A}(σ) = 1.

Let σ ∈ G_{r,n}. Recall that for σ = (z, τ) ∈ G_{r,n}, |σ| is the permutation of [n] satisfying |σ|(i) = τ(i). For example, if σ = (¯2¯¯31¯4) then |σ| = (2314).

Now we can define the excedance numbers for G_{r,n}.

Definition 3.4. Define

exc^{Abs}(σ) = exc(|σ|) + csum(σ),
exc^{Clr}(σ) = r · exc_{A}(σ) + csum(σ).

Note that the computation of the parameter exc^{Abs} uses the absolute order.

The parameters exc^{Abs} and exc^{Clr} are indeed different: for σ = (21) ∈ G_{r,2}, (r > 1) one has exc^{Abs}(σ) = 1 but exc^{Clr}(σ) = r.

One can view exc^{Clr}(σ) in a different way:

Lemma 3.5. Let σ ∈ G_{r,n}. Consider the set Σ ordered by the color order. Then

exc(σ) = exc^{Clr}(σ).

Proof. Let i ∈ [n]. We divide our proof into two cases: z_{i}(σ) = 0 and z_{i}(σ) ≠ 0.

If z_{i}(σ) = 0, then i ∈ Exc_{A}(σ) if and only if σ(i) > i. In this case, we have σ(i^{[j]}) > i^{[j]} for every color 1 ≤ j ≤ r − 1. Hence, we have {i, i^{[1]}, ⋯, i^{[r−1]}} ⊆ Exc(σ). Hence, each i ∈ Exc_{A}(σ) contributes r excedances to exc(σ).

On the other hand, if z_{i}(σ) = k ≠ 0, we have that i ∉ Exc(σ). By definition, we have σ(i^{[j]}) = |σ(i)|^{[(j+k) (mod r)]} for all j. Thus, for 0 ≤ j ≤ r − k − 1, i^{[j]} ∉ Exc(σ), and for the k indices r − k ≤ j ≤ r − 1, i^{[j]} ∈ Exc(σ). Consequently, we have

exc(σ) = exc^{Clr}(σ).

□

Recall that any permutation of S_{n} can be decomposed into a product of disjoint cycles. This notion can be easily generalized to the group G_{r,n} as follows. Given any π ∈ G_{r,n} we define the cycle number of π = (z, τ) to be the number of cycles in τ.

We say that i ∈ [n] is an absolute fixed point of σ ∈ G_{r,n} if |σ(i)| = i.

4. Proof of Theorem 1.1

In this section we prove Theorem 1.1. The idea of proving this type of identities is constructing a subset S of G_{r,n} whose contribution to the generating function is exactly the right side of the identity and a killing involution on G_{r,n} − S, i.e., an involution on G_{r,n} − S which preserves the number of excedances but changes the sign of every element of G_{r,n} − S and hence shows that G_{r,n} − S contributes nothing to the generating function.

4.1. Proof for the absolute order. We divide G_{r,n} into 2r+1 disjoint subsets as follows:

K_{r,n} = {σ ∈ G_{r,n} | |σ(n)| ≠ n, |σ(n − 1)| ≠ n},
T_{r,n}^{i} = {σ ∈ G_{r,n} | σ(n) = n^{[i]}}, (0 ≤ i ≤ r − 1),
R_{r,n}^{i} = {σ ∈ G_{r,n} | σ(n − 1) = n^{[i]}}, (0 ≤ i ≤ r − 1).

We first construct a killing involution on the set K_{r,n}. Let σ ∈ K_{r,n}. Define φ : K_{r,n} → K_{r,n} by

σ′ = φ(σ) = (σ(n − 1), σ(n))σ.

Note that φ exchanges σ(n − 1) with σ(n). It is obvious that φ is indeed an involution.

We will show that exc^{Abs}(σ) = exc^{Abs}(σ′). First, for i < n − 1, it is clear that i ∈ Exc(|σ|) if and only if i ∈ Exc(|σ′|). Now, as σ(n−1) ≠ n, n − 1 ∉ Exc(|σ|) and thus n ∉ Exc(|σ′|). Finally, |σ(n)| ≠ n implies that n − 1 ∉ Exc(|σ′|) and thus exc^{Abs}(σ) = exc^{Abs}(σ′).

On the other hand, cyc(σ) and cyc(σ′) have different parities due to a multiplication by a transposition. Hence, φ is indeed a killing involution on K_{r,n}.

We turn now to the sets T_{r,n}^{i} (0 ≤ i ≤ r − 1) . Note that there is a natural bijection between T_{r,n}^{i} and G_{r,n−1} defined by ignoring the last digit. Let σ ∈ T_{r,n}^{i}. Denote the image of σ ∈ T_{r,n}^{i} under this bijection by σ′. Since n ∉ Exc(|σ|), we have exc(|σ|) = exc(|σ′|). Now, csum(σ′) = csum(σ) − i, since z_{n}(σ) = i and hence we have

exc^{Abs}(σ) − i = exc^{Abs}(σ′).

Finally, since n is an absolute fixed point of σ, cyc(σ′) = cyc(σ) − 1 and we get that the total contribution of T_{r,n}^{i} is

P_{T_{r,n}^{i}}^{Abs} = −q^{i}P_{G_{r,n−1}}^{Abs}(q, 1, −1)

for 0 ≤ i ≤ r − 1.

Now, we treat the sets R_{r,n}^{i} (0 ≤ i ≤ r − 1). There is a bijection between R_{r,n}^{i} and T_{r,n}^{i} using the same function φ we used above. Let σ ∈ R_{r,n}^{i}. Define φ : R_{r,n}^{i} → T_{r,n}^{i} by

σ′ = φ(σ) = (σ(n − 1), σ(n))σ.

In σ, we have that n − 1 ∈ Exc(|σ|) (since |σ(n − 1)| = n) and n ∉ Exc(|σ|), but in σ′, n − 1, n ∉ Exc(|σ′|). Hence, exc(|σ|) − 1 = exc(|σ′|). We also have that csum(σ) = csum(σ′) (since z_{n−1}(σ) + z_{n}(σ) = z_{n−1}(σ′) + z_{n}(σ′)). Hence, we have that

exc^{Abs}(σ) − 1 = exc^{Abs}(σ′).

As before, the number of cycles changes its parity due to the multiplication by a transposition, and thus (−1)^{cyc(σ)} = −(−1)^{cyc(σ′)}.

Hence, the total contribution of the elements in R_{r,n}^{i} is

P_{R_{r,n}^{i}}^{Abs} = q^{i+1} · P_{G_{r,n−1}}^{Abs}(q, 1, −1)

for 0 ≤ i ≤ r − 1.

Now, if we sum up all the parts, we get

P_{G_{r,n}}^{Abs}(q, 1, −1) = P_{K_{r,n}}^{Abs}(q, 1, −1)

+ ∑_{i=0}^{r−1} P_{T_{r,n}^{i}}^{Abs}(q, 1, −1) + ∑_{i=0}^{r−1} P_{R_{r,n}^{i}}(q, 1, −1)

= ∑_{i=0}^{r−1}(−q^{i}P_{G_{r,n−1}}^{Abs}(q, 1, −1)) + ∑_{i=0}^{r−1} q^{i+1}P_{G_{r,n−1}}^{Abs}(q, 1, −1)

= (q^{r} − 1)P_{G_{r,n−1}}^{Abs}(q, 1, −1)

as claimed.

Now, for n = 1, G_{r,1} is the cyclic group of order r and thus

P_{G_{r,1}}^{Abs}(q, 1, −1) = −(1 + q + ⋯ + q^{r−1}) = −\frac{q^{r} − 1}{q − 1},

so we have

P_{G_{r,n}}^{Abs}(q, 1, −1) = −\frac{(q^{r} − 1)^{n}}{q − 1} .

4.2. Proof for the color order. As in the previous proof, we divide G_{r,n} into the same 2r + 1 disjoint subsets K_{r,n}, T_{r,n}^{i} (0 ≤ i ≤ r − 1) and R_{r,n}^{i} (0 ≤ i ≤ r − 1) used there.

As before, we first construct a killing involution on the set K_{r,n}. Let σ ∈ K_{r,n}. As before, define φ : K_{r,n} → K_{r,n} by

σ′ = φ(σ) = (σ(n − 1), σ(n))σ.

The proof that φ is a killing involution is similar to the one we presented in Section 4.1.

We turn now to the sets T_{r,n}^{i}. We use again the bijection between T_{r,n}^{i} and G_{r,n−1} defined by ignoring the last digit. Let σ ∈ T_{r,n}. As in the previous proof, we have

exc^{Clr}(σ) − i = exc^{Clr}(σ′).

Now, since n is an absolute fixed point of σ, cyc(σ′) = cyc(σ) − 1.

To summarize, we get that the total contribution of elements in T_{r,n}^{i} is

P_{T_{r,n}^{i}}^{Clr} = −q^{i}P_{G_{r,n−1}}^{Clr}(q, 1, −1)

for 0 ≤ i ≤ r − 1.

Finally, we treat the sets R_{r,n}^{i}. Let σ ∈ R_{r,n}^{i}. Recall the bijection φ : R_{r,n}^{i} → T_{r,n}^{i} defined in Section 4.1 by

σ′ = φ(σ) = (σ(n − 1), σ(n))σ.

When we compute the change in the excedance, we split our treatment into two cases: i = 0 and i > 0. For the case i = 0, we get exc^{Clr}(σ) − r = exc^{Clr}(σ′). For the case i > 0, we show that exc^{Clr}(σ) = exc^{Clr}(σ′).

We start with case i = 0. Note that n−1 ∈ Exc_{A}(σ) (since σ(n−1) = n) and n ∉ Exc_{A}(σ). On the other hand, in σ′, n − 1, n ∉ Exc_{A}(σ′). Hence, exc_{A}(σ) − 1 = exc_{A}(σ′).

Now, for the case i > 0 : n − 1, n ∉ Exc_{A}(σ) (since σ(n − 1) = n^{[i]} is not an excedance with respect to the color order). We also have n − 1, n ∉ Exc_{A}(σ′), and thus Exc_{A}(σ) = Exc_{A}(σ′) for σ ∈ R_{r,n}^{i} where i > 0.

In both cases, we have that csum(σ) = csum(σ′). Hence, we have that exc^{Clr}(σ) − r = exc^{Clr}(σ′) for i = 0 and exc^{Clr}(σ) = exc^{Clr}(σ′) for i > 0.

As before, the number of cycles changes its parity due to the multiplication by a transposition, and hence (−1)^{cyc(σ)} = −(−1)^{cyc(σ′)}. Hence, the total contribution of elements in R_{r,n}^{i} is

q^{r}P_{G_{r,n−1}}^{Clr}(q, 1, −1)

for i = 0, and

q^{i}P_{G_{r,n−1}}^{Clr}(q, 1, −1)

for i > 0.

Now, if we sum up all the parts, we get

P_{G_{r,n}}^{Clr}(q, 1, −1) = ∑_{i=0}^{r−1}(−q^{i}P_{G_{r,n−1}}^{Clr}(q, 1, −1))

+ q^{r}P_{G_{r,n−1}}^{Clr}(q, 1, −1) + ∑_{i=1}^{r−1} q^{i}P_{G_{r,n−1}}^{Clr}(q, 1, −1)

= (q^{r} − 1)P_{G_{r,n−1}}^{Clr}(q, 1, −1)

as needed.

Now, for n = 1, G_{r,1} is the cyclic group of order r and thus

P_{G_{r,1}}^{Clr}(q, 1, −1) = −(1 + q + ⋯ + q^{r−1}) = −\frac{q^{r} − 1}{q − 1},

so we have

P_{G_{r,n}}^{Clr}(q, 1, −1) = −\frac{(q^{r} − 1)^{n}}{q − 1} .

5. Derangements in G_{r,n} and the proof of Theorem 1.2

In this section, we prove Theorem 1.2. As in the previous section, we will prove Theorem 1.2 for both orders.

We start with the definition of a derangement.

Definition 5.1. An element σ ∈ G_{r,n} is called a derangement if it has no absolute fixed points, i.e., |σ(i)| ≠ i for every i ∈ [n]. Denote by D_{r,n} the set of all derangements in G_{r,n}

5.1. Proof for the absolute order. We divide D_{r,n} into r+2 disjoint subsets in the following way:

A_{r,n}^{i} = {σ ∈ D_{r,n} | σ(2) = 1^{[i]}, |σ(1)| ≠ 2}, i = 0, …, r − 1,

T_{r,n} = {σ ∈ D_{r,n} | |σ| = (123 ⋯ n)},

D̂_{r,n} = D_{r,n} − (⋃_{i=0}^{r−1} A_{r,n}^{i} ∪ T_{r,n}).

We start by constructing a killing involution φ on D̂_{r,n}. Given any σ ∈ D̂_{r,n}, let i be the first number such that |σ(i)| ≠ i + 1. Define

σ′ = φ(σ) = (σ(i), σ(i + 1))σ.

For example, if σ = (¯34¯1¯5¯¯2) then σ′ = (4¯3¯1¯5¯¯2).

It is easy to see that φ is a well-defined involution on D̂_{r,n}. We proceed to prove that exc^{Abs}(σ) = exc^{Abs}(σ′). Indeed, csum(σ) = csum(σ′).

Let i be the first number such that |σ(i)| ≠ i + 1 so that in the pass from σ to σ′ we exchange σ(i) with σ(i + 1). For every j ≠ i, i + 1, clearly j ∈ Exc(|σ|) if and only if j ∈ Exc(|σ′|). Since σ ∈ D_{r,n}, |σ(i)| ≠ i+1 and |σ(j)| = j+1 for j < i, we have that |σ(i)|, |σ(i+1)| ∈ {1, i + 2, ⋯, n}. Thus, exchanging σ(i) with σ(i + 1) does not change Exc(|σ|).

Note also that the parity of cyc(σ′) is opposite to the parity of cyc(σ) due to the multiplication by a transposition. Hence, we have proven that φ is a killing involution.

Now, let us calculate the contribution of each set in our decomposition to P_{D_{r,n}}^{Abs}(q, 0, −1). As we have shown, D̂_{r,n} contributes nothing. Define a bijection

ψ : A_{r,n}^{i} → D_{r,n−1}

by ψ(σ) = σ′, where σ′(1) = (|σ(1)| − 1)^{z_{1}(σ)} and for i > 1, σ′(i) = (|σ(i + 1)| − 1)^{z_{i+1}(σ)}. For example, if σ = (3¯14¯2), then σ′ = (23¯1). It is easy to see that exc(|σ|) = exc(|σ′|). On the other hand, csum(σ′) = csum(σ) − i and cyc(σ) = cyc(σ′) and thus the contribution of A_{r,n}^{i} to P_{D_{r,n}}^{Abs}(q, 0, −1) is q^{i}P_{D_{r,n−1}}^{Abs}(q, 0, −1) for 1 ≤ i ≤ r − 1.

Finally, we treat the set T_{r,n}. For every σ ∈ T_{r,n} we have exc(|σ|) = n − 1 and cyc(σ) = 1. Concerning csum(σ) we have

∑_{σ∈T_{r,n}} q^{csum(σ)} = (1 + q + ⋯ q^{r−1})^{n}.

To summarize, we get

P_{D_{r,n}}^{Abs}(q, 0, −1) = ∑_{i=0}^{r−1}(q^{i}P_{D_{r,n−1}}^{Abs}(q, 0, −1)) + q^{n−1}(1 + q + ⋯ q^{r−1})^{n}
= (1 + q + ⋯ q^{r−1})P_{D_{r,n−1}}^{Abs}(q, 0, −1)
+ q^{n−1}(1 + q + ⋯ q^{r−1})^{n}
= [r]_{q}(P_{D_{r,n−1}}^{Abs}(q, 0, −1) − q^{n−1}[r]_{q}^{n−1})

as needed.

Now, for n = 2, we have

P_{D_{r,2}}^{Abs}(q, 0, −1) = −q[r]_{q}^{2}

and thus

P_{D_{r,n}}^{Abs}(q, 0, −1) = −q[r]_{q}^{n}[n − 1]_{q}.

5.2. Proof for the color order. We use the same decomposition of D_{r,n} as before. The killing involution will be also the same, due to the following observation: one can replace Exc(|σ|) in the previous proof by Exc_{A}(σ), and the argument still holds. Note that i ∉ Exc_{A}(σ) if z_{i}(σ) ≠ 0.

Now, let us calculate the contribution of each set in our decomposition to P_{D_{r,n}}^{Clr}(q, 0, −1). As we have shown, D̂_{r,n} contributes nothing.

As before, define a bijection

ψ : A_{r,n}^{i} → D_{r,n−1}

by ψ(σ) = σ′, where σ′(1) = (|σ(1)| − 1)^{z_{1}(σ)} and for i > 1, σ′(i) = (|σ(i+1)|−1)^{z_{i+1}(σ)}. As before, it is easy to see that exc_{A}(σ) = exc_{A}(σ′) (since |σ(2)| = 1). On the other hand, csum(σ′) = csum(σ) − i and cyc(σ) = cyc(σ′), and thus the contribution of A_{r,n}^{i} to P_{D_{r,n}}^{Clr}(q, 0, −1) is q^{i}P_{D_{r,n−1}}^{Clr}(q, 0, −1) for 0 ≤ i ≤ r − 1.

Now, we treat the set T_{r,n}. Let σ ∈ T_{r,n}. Observe that for i < n, i ∈ Exc_{A}(σ) if and only if z_{i}(σ) = 0. In this case, the place i contributes r to exc^{Clr}(σ). Hence, it will be natural to construct the following bijection between T_{r,n} and the following subset W of G_{r+1,n}:

W = {σ ∈ G_{r+1,n} | |σ| = (12 ⋯ n), z_{i}(σ) ≠ 0 for 1 ≤ i ≤ n − 1, z_{n}(σ) ≠ r}

by ψ(σ) = σ′, where

σ′(i) = \{ \begin{matrix}σ(i) & i = n or z_{i}(σ) ≠ 0, \\ |σ(i)|^{[r]} & otherwise. \end{matrix}

Note that exc^{Clr}(σ) = csum(σ′).

Now we compute

∑_{σ∈T_{r,n}} q^{exc^{Clr}(σ)}(−1)^{cyc(σ)} = ∑_{σ′∈W} q^{csum(σ′)}(−1)^{cyc(σ′)}

= − ∑_{σ′∈W} q^{csum(σ′)}

= −(q + q^{2} + ⋯ + q^{r})^{n−1}(1 + q + ⋯ + q^{r−1}).

To summarize, we get

P_{D_{r,n}}^{Clr}(q, 0, −1) = ∑_{i=0}^{r−1}(q^{i}P_{D_{r,n−1}}^{Clr}(q, 0, −1))
− (q + q^{2} + ⋯ + q^{r})^{n−1}(1 + q + ⋯ + q^{r−1})

= (1 + q + ⋯ q^{r−1})(P_{D_{r,n−1}}^{Clr}(q, 0, −1) + (q + ⋯ q^{r})^{n−1})

= [r]_{q}(P_{D_{r,n−1}}^{Clr}(q, 0, −1) − q^{n−1}[r]_{q}^{n−1})

Now, for n = 2, we have

P_{D_{r,2}}^{Clr}(q, 0, −1) = −q[r]_{q}^{2}

and thus P_{D_{r,n}}^{Clr}(q, 0, −1) = −q[r]_{q}^{n}[n − 1]_{q}.

6. Proof of Corollary 1.3

In this section, we provide a complete proof for Corollary 1.3. The proof follows the ideas of Ksavrelov and Zeng [1].

We first compute P_{G_{r,n}}(q, s, −1). The polynomial counting the permutations of G_{r,n} with a given number k of absolute fixed points (0 ≤ k ≤ n) is

(−s)^{k}(1 + q + ⋯ q^{r−1})^{k}P_{G_{r,n−k}}(q, 0, −1).

Hence,

P_{G_{r,n}}(q, s, −1) = ∑_{k=0}^{n} \binom{n}{k}[r]_{q}^{k}(−s)^{k}P_{G_{r,n−k}} =

= ∑_{k=0}^{n} \binom{n}{k}[r]_{q}^{k}(−s)^{k}(−q)[r]_{q}^{n−k}[n − k − 1]_{q} =

= [r]_{q}^{n} ∑_{k=0}^{n} \binom{n}{k}(−s)^{k}(−q)\frac{1 − q^{n−k−1}}{1 − q} =

= \frac{[r]_{q}^{n}}{1 − q} ∑_{k=0}^{n} (\binom{n}{k}q^{n−k}(−s)^{k} − q\binom{n}{k}(−s)^{k}) =

= \frac{[r]_{q}^{n}}{1 − q} ((q − s)^{n} − q(1 − s)^{n}).

Thus

(3)  P_{G_{r,n}}(q, s, −1) = \frac{[r]_{q}^{n}}{1 − q} ((q − s)^{n} − q(1 − s)^{n}).

Now we compute an exponential generating function for

∑_{n≥0} P_{G_{r,n}}(q, s, t).

Denote by C_{r,n} the set of cycles of length n in G_{r,n}. For example, in G_{2,2} = B_{2} we have

C_{2,2} = {(12), (21), (¯12), (2¯1), (1¯2), (2¯1), (¯1¯2)}.

Note that in the following computation we use the fact that all parameters exc(π), fix(π), cyc(π) are additive. We have

∑_{n≥0}P_{G_{r,n}}(q, s, t)\frac{x^{n}}{n!}

= ∑_{n≥0} ∑_{π∈G_{r,n}} (q^{exc(π)}s^{fix(π)}t^{cyc(π)}) \frac{x^{n}}{n!}

= ∑_{n≥0} ∑_{n_{i_{1}}+···+n_{i_{k}} =n^{(c_{1},...,c_{k})∈Cr,n_{i_{1}} ×···×Cr,n_{i_{k}}}} \frac{1}{k!}

· (q^{( ∑_{i=1}^{k} exc(c_{i}))}s^{( ∑_{i=1}^{k} fix(c_{i}))}t^{( ∑_{i=1}^{k} cyc(c_{i}))}) \frac{x^{|c_{1}|+···+|c_{k}|}}{|c_{1}|! ⋯ |c_{k}|!}

= ∑_{n≥0} ∑_{n_{i_{1}}+···+n_{i_{k}} =n^{(c_{1},...,c_{k})∈Cr,n_{i_{1}} ×···×Cr,n_{i_{k}}}} \frac{1}{k!}

· ∏_{i=1}^{k} (q^{exc(c_{i})}s^{fix(c_{i})}t^{cyc(c_{i})}) \frac{x^{|c_{1}|+···+|c_{k}|}}{|c_{1}|! ⋯ |c_{k}|!}

= ∑_{k≥0} \frac{1}{k!} (∑_{n≥0} ∑_{c∈C_{r,n}} q^{exc(c)}s^{fix(c)}t^{cyc(c)} \frac{x^{|c|}}{|c|!})^{k}

= exp (∑_{n≥0} ∑_{c∈C_{r,n}} q^{exc(c)}s^{fix(c)}t^{cyc(c)} \frac{x^{|c|}}{|c|!})

= (exp (− ∑_{n≥0} ∑_{c∈C_{r,n}} q^{exc(c)}s^{fix(c)} \frac{x^{|c|}}{|c|!}))^{−t} .

Hence we have

(4) ∑_{n≥0} P_{G_{r,n}}(q, s, t)\frac{x^{n}}{n!} = (exp (− ∑_{n≥0} ∑_{c∈C_{r,n}} q^{exc(c)}s^{fix(c)} \frac{x^{|c|}}{|c|!}))^{−t} .

Substituting t = −1 in Equation (4), we get

(5) ∑_{n≥0} P_{G_{r,n}}(q, s, −1)\frac{x^{n}}{n!} = exp (− ∑_{n≥0} ∑_{c∈C_{r,n}} q^{exc(c)}s^{fix(c)} \frac{x^{|c|}}{|c|!}) .

Now, by Equation (3) we have

∑_{n≥0} (\frac{[r]_{q}^{n}}{1 − q} ((q − s)^{n} − q(1 − s)^{n})) \frac{x^{n}}{n!}

= exp (− ∑_{n≥0} ∑_{c∈C_{r,n}} q^{exc(c)}s^{fix(c)} \frac{x^{|c|}}{|c|!}) .

Substituting the last equation back in Equation (4) we get

∑_{n≥0} P_{G_{r,n}}(q, s, t)\frac{x^{n}}{n!} = (∑_{n≥0} (\frac{[r]_{q}^{n}}{1 − q} ((q − s)^{n} − q(1 − s)^{n})) \frac{x^{n}}{n!} )^{−t} .

7. Statistics on the group of even signed permutations

In this section we deal with the Coxeter group of type D, namely the group of even signed permutations. We recall its definition,

D_{n} = {π ∈ B_{n} | ∑_{i=1}^{n} z_{i}(π) ≡ 0 (mod 2)}.

Unlike the case of the groups G_{r,n}, in D_{n} the distribution of the excedance numbers with respect to the color order is different from the distribution with respect to the absolute order. We start with the color order.

7.1. Proof of Theorem 1.4. We divide D_{n} into 5 subsets:

K_{n} = {σ ∈ D_{n} | |σ(n)| ≠ n, |σ(n − 1)| ≠ n},
T_{n}^{0} = {σ ∈ D_{n} | σ(n) = n},
T_{n}^{1} = {σ ∈ D_{n} | σ(n) = n̄},
R_{n}^{0} = {σ ∈ D_{n} | σ(n − 1) = n},
R_{n}^{1} = {σ ∈ D_{n} | σ(n − 1) = n̄}.

We write

a_{n} = P_{D_{n}}^{Clr}(q, 1, −1),
b_{n} = P_{D_{n}^{c}}^{Clr}(q, 1, −1),

where D_{n}^{c} is the complement of D_{n} in B_{n}.

Define φ : K_{n} → K_{n} by

σ′ = φ(σ) = (σ(n − 1), σ(n))σ.

Note that φ exchanges σ(n − 1) with σ(n). It is easy to see that φ is a killing involution on K_{n}.

We turn now to the set T_{n}^{0}. Note that there is a natural bijection between T_{n}^{0} and D_{n−1}, defined by ignoring the last digit. Let σ ∈ T_{n}^{0}. Denote the image of σ under this bijection by σ′. Note that csum(σ′) = csum(σ), Exc_{A}(σ′) = Exc_{A}(σ) and Exc^{Clr}(σ′) = Exc^{Clr}(σ). On the other hand, cyc(σ′) = cyc(σ) − 1 and thus the restriction of a_{n} to T_{n}^{0} is just −a_{n−1}.

For the contribution of the set T_{n}^{1}, note that the function φ defined above gives us a bijection between T_{n}^{1} and D_{n−1}^{c}. In this case, csum(σ′) = csum(σ)−1, exc_{A}(σ′) = exc_{A}(σ) and exc^{Clr}(σ′) = exc^{Clr}(σ). On the other hand, cyc(σ′) = cyc(σ) − 1 as before. Hence, the restriction of a_{n} to T_{n}^{1} is −qb_{n−1}.

Now, for the set R_{n}^{0}, we have the following bijection between R_{n}^{0} and D_{n−1}: for σ ∈ R_{n}^{0}, exchange the last two digits, and then ignore the last digit. If we denote the image of σ by σ′, we have csum(σ′) = csum(σ), exc_{A}(σ′) = exc_{A}(σ)−1, exc^{Clr}(σ′) = exc^{Clr}(σ)−2 and cyc(σ′) ≡ cyc(σ) (mod 2). Hence, the restriction of a_{n} to R_{n}^{0} is q^{2}a_{n−1}.

For the set R_{n}^{1}, we have a bijection between R_{n}^{1} and D_{n−1}^{c}: for σ ∈ R_{n}^{1}, exchange the last two digits, and then ignore the last digit. Denoting the image of σ by σ′, we have csum(σ′) = csum(σ) − 1, exc_{A}(σ′) = exc_{A}(σ), and hence exc^{Clr}(σ′) = exc^{Clr}(σ) − 1. Also, we have cyc(σ′) ≡ cyc(σ) (mod 2). Hence, the restriction of a_{n} to R_{n}^{1} is qb_{n−1}.

We summarize all the contributions over all the four subsets, and we have

a_{n} = −a_{n−1} − qb_{n−1} + q^{2}a_{n−1} + qb_{n−1} = (q^{2} − 1)a_{n−1}

For computing a_{1}, note that D_{1} = {1} and thus a_{1} = −1. Therefore, we have

P_{D_{n}}^{Clr}(q, 1, −1) = a_{n} = −(q^{2} − 1)^{n−1},

and we are done.

7.2. Proof of Theorem 1.5. In this subsection we present the proof of Theorem 1.5 which is based on the absolute order.

We start by dividing D_{n} into 5 subsets just as was shown in the proof of Theorem 1.4 and define as before

a_{n} = P_{D_{n}}^{Abs}(q, 1, −1),
b_{n} = P_{D_{n}^{c}}^{Abs}(q, 1, −1),

where D_{n}^{c} is the complement of D_{n} in B_{n}.

It is easy to check that the sets T_{n}^{0} and T_{n}^{1} give the same contributions as before so we turn to the set R_{n}^{0}. By using the bijection between R_{n}^{0} and D_{n−1} defined above which exchanges the last two digits, and then ignores the last digit, we have csum(σ′) = csum(σ), exc(|σ′|) = exc(|σ|) − 1. Thus, exc^{Abs}(σ′) = exc^{Abs}(σ) − 1. Also, cyc(σ′) ≡ cyc(σ) (mod 2). Hence, the restriction of a_{n} to R_{n}^{0} is qa_{n−1}.

For the set R_{n}^{1}, we use the same bijection, now between R_{n}^{1} and D_{n−1}^{c} to get csum(σ′) = csum(σ) − 1, exc(|σ′|) = exc(|σ|) − 1. Thus exc^{Abs}(σ′) = exc^{Abs}(σ) − 2. Also, we have cyc(σ′) ≡ cyc(σ) (mod 2). Hence, the restriction of a_{n} to R_{n}^{1} is q^{2}b_{n−1}.

To summarize, we have

a_{n} = (q − 1)(a_{n−1} + qb_{n−1}),

and by symmetry

b_{n} = (q − 1)(b_{n−1} + qa_{n−1}).

Since D_{1} = {1} we get a_{1} = −1, b_{1} = −q. Solving the above system of recursive equations yields

P_{D_{n}}^{Abs}(q, 1, −1) = \frac{1}{2}(q − 1)^{n−1} ∑_{\begin{matrix}k=0 \\ k even \end{matrix}}^{n} \binom{n}{k}q^{k}

= −\frac{1}{2}(q − 1)^{n−1}((1 + q)^{n} + (1 − q)^{n}),

as needed.

Acknowledgements

We wish to thank Alex Lubotzky and Ron Livne. We also wish to thank the Einstein Institute of Mathematics at the Hebrew University for hosting their stays.

References

[1] G. Ksavrelof and J. Zeng, Two involutions for signed excedance numbers, Séminaire Lotharingien Combin. 49 (2003), Art. B49e, 8 pp. (Electronic,

  available at http://igd.univ-lyon1.fr/~slc).

[2] R. P. Stanley, Enumerative combinatorics, Vol. 1 and 2, Cambridge University Press, 1998/99.

Einstein institute of Mathematics, The Hebrew University, Givat Ram, 91904 Jerusalem, Israel, and The Jerusalem College of Technology, Jerusalem, Israel

E-mail address: bagnoe@math.huji.ac.il, bagnoe@jct.ac.il

Einstein institute of Mathematics, The Hebrew University, Givat Ram, 91904 Jerusalem, Israel, and School of Sciences, Holon Institute of Technology, PO Box 305, 58102 Holon, Israel

E-mail address: garber@math.huji.ac.il, garber@hait.ac.il