Séminaire Lotharingien de Combinatoire 58 (2008), Article B58b

EXCEDANCE NUMBERS FOR PERMUTATIONS IN COMPLEX REFLECTION GROUPS

Toufik Mansour

Department of Mathematics, University of Haifa, 31905 Haifa, Israel

E-mail: toufik@math.haifa.ac.il

Yidong Sun^{∗}

Department of Mathematics, Dalian Maritime University, 116026 Dalian, P.R. China

E-mail: sydmath@yahoo.com.cn

Abstract. Recently, Bagno, Garber and Mansour [Sém. Lotharingien Combin. 56 (2007), Art. B56d] studied a kind of excedance number on the complex reflection groups and computed its multidistribution with the number of fixed points on the set of involutions in these groups. In this note, we consider the similar problems in more general cases and make a correction of one result obtained by them.

1. Introduction

It is well known that there is a single infinite family of groups G_{r,s,n} and exactly 34 other “exceptional” complex reflection groups [4]. The infinite family G_{r,s,n}, where r, s, n are positive integers with s | r, consists of the groups of n × n matrices such that

• the entries are either 0 or r^{th} roots of unity;

• there is exactly one nonzero entry in each row and each column;

• the (r/s)^{th} power of the product of the nonzero entries is 1. The classical Weyl groups appear as special cases: for r = s = 1 we have the

symmetric group G_{1,1,n} = S_{n}, for r = 2, s = 1 we have the hyperoctahedral group G_{2,1,n} = B_{n}, and for r = s = 2 we have the group of even-signed permutations G_{2,2,n} = D_{n}.

We say that a permutation π ∈ G_{r,s,n} is an involution if π^{2} = 1. More generally, we define G_{r,s,n}^{m} = {σ ∈ G_{r,s,n}|σ^{m} = 1}. Recently, Bagno, Garber and Mansour [2] studied an excedance number on the complex reflection groups (see [5]) and computed the number of involutions having specific numbers of fixed points and excedances. In this note, we consider the similar problems on the set G_{r,s,n}^{m}.

This paper is organized as follows. In Section 2, we recall some properties of G_{r,s,n} and define some parameters on G_{r,n} = G_{r,1,n} and hence also on G_{r,s,n}. In Section 3, we present our main results and compute the corresponding recurrences together with explicit formulas.

2000 Mathematics Subject Classification. Primary 05A05, 05A15.

Key words and phrases. Complex reflection group, excedance, colored permutations.

∗Corresponding author: Yidong Sun.

∗The author is supported by The National Science Foundation of China (10726021).

2. Preliminaries

Let r and n be any two 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 ∈ ℤ_{r}^{n} and τ ∈ S_{n}. Let τ, τ′ ∈ S_{n}, z = (z_{1}, ..., z_{n}) ∈ ℤ_{r}^{n} and z′ = (z′_{1}, ..., z′_{n}) ∈ ℤ_{r}^{n}, the multiplication in G_{r,n} is defined by (z, τ) · (z′, τ′) = ((z_{1} + z′_{τ^{−1}(1)}, ..., z_{n} + z′_{τ^{−1}(n)}), τ ∘ τ′), where + 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}).

A much more natural way to present G_{r,n} is the following: consider the alphabet Σ = {1^{[0]}, …, n^{[0]}, 1^{[1]}, …, n^{[1]}, …, 1^{[r−1]}, …, n^{[r−1]}} as the set ⟦n⟧ = {1, …, n} colored by the colors 0, …, r − 1. Then, an element of G_{r,n} is called a colored permutation, i.e., a bijection σ : Σ → Σ such that if σ(i) = k^{[t]} then σ(i^{[j]}) = k^{[t+j]} where 0 ≤ j ≤ r − 1 and the addition is taken modulo r. Occasionally, we write j bars over a digit i instead of i^{[j]}. For example, an element (z, τ) = ((1, 2, 1, 2), (3, 1, 2, 4)) ∈ G_{3,4} will be written as (¯3¯¯1¯2¯¯4).

For each s | r, the complex reflection group can also be defined as:

G_{r,s,n} := {σ ∈ G_{r,n} | csum(σ) ≡ 0 mod s},

where csum(σ) = ∑_{i=1}^{n} z_{i}(σ).

One can define the following well-known statistics on S_{n}. For any permutation σ ∈ S_{n}, i ∈ ⟦n⟧ is an excedance of σ if and only if σ(i) > i. We denote the number of excedances by exc(σ). Another natural statistic on S_{n} is the number of fixed points, denoted by fix(σ). We can similarly define some statistics on G_{r,n}. The complex reflection group G_{r,s,n} inherits all of them. 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 define the color order on the set Σ = {1, …, n, ¯1, …, n̄, …, 1^{[r−1]}, …, n^{[r−1]}} for 0 ≤ j < i < r by 1^{[i]} < 2^{[i]} < ⋯ < n^{[i]} < 1^{[j]} < 2^{[j]} < ⋯ < n^{[j]}. We note that there are some other possible ways of defining orders on Σ, some of them lead to other versions of the excedance number, see for example [1]. For example, given the color order ¯ ¯1 < ¯ ¯2 < ¯ ¯3 < ¯1 < ¯2 < ¯3 < 1 < 2 < 3, we write σ = (2¯1¯¯3) ∈ G_{3,3} in an extended form

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

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

Define Exc_{A}(σ) = {i ∈ ⟦n − 1⟧ | σ(i) > i}, where the comparison is with respect to the color order, and denote exc_{A}(σ) = |Exc_{A}(σ)|. For instance, if σ = (¯1¯¯32¯¯4) ∈ G_{3,4}, then csum(σ) = 5, Exc_{A}(σ) = {3} and hence exc_{A}(σ) = 1.

Now we can define the colored excedance number for G_{r,n} by

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

Let Σ be ordered by the color order, then we can state that exc(σ) = exc^{Clr}(σ) obtained by Bagno and Garber [1] for any σ ∈ G_{r,n}.

For σ = (z, τ) ∈ G_{r,n}, |σ| is the permutation of ⟦n⟧ satisfying |σ|(i) = τ(i). We say that i ∈ ⟦n⟧ is an absolute fixed point of σ ∈ G_{r,n} if |σ|(i) = i. We denote the number of absolute fixed point of σ ∈ G_{r,n} by fix(σ).

3. Main results and proofs

Recall that G_{r,s,n}^{m} = {σ ∈ G_{r,s,n}|σ^{m} = 1}, define

H_{r,s,n}^{(m)}(u, v, w) = ∑_{σ∈G_{r,s,n}^{m}} u^{fix(σ)}v^{exc_{A}(σ)}w^{csum(σ)},

H_{r,s}^{(m)}(x; u, v, w) = ∑_{n≥0} H_{r,s,n}^{(m)}(u, v, w)\frac{x^{n}}{n!} .

It is well known that the Eulerian number, A_{d−1,k}, is the number of permutations on ⟦d − 1⟧ with k − 1 excedances for k ∈ ⟦d − 1⟧, which is also the number of cyclic permutations in S_{d} with k excedances. A bijective proof of this fact is given in [3, Theorem 1.19].

Our main result can be formulated as follows.

Theorem 3.1. For any integers r, m ≥ 1, the generating function H_{r,1}^{(m)}(x; u, v, w) is

exp \{ ∑_{\{t|0≤t<r,r|tm\}} xuw^{t} + ∑_{d|m,d≥2} \frac{x^{d}}{d!} ∑_{k=1}^{d−1} A_{d−1,k} ∑_{i=0}^{k} \binom{k}{i}v^{k−i} ∑_{r| \frac{tm}{d}} U_{d−k,t}^{(i)}w^{t}\} ,

where U_{d−k,t}^{(i)} is the coefficient of x^{t} in (x + x^{2} + ⋯ + x^{r−1})^{i}(1 + x + ⋯ + x^{r−1})^{d−k}, i.e.,

U_{d−k,t}^{(i)} = ∑_{j=0}^{i}(−1)^{i−j}\binom{i}{j} ∑_{ℓ≥0}(−1)^{ℓ}\binom{d + j − k}{ℓ}\binom{d + j + t − k − ℓr − 1}{t − ℓr}.

Proof. For any π ∈ G_{r,1,n}^{m}, the length of each cycle of π is a factor of m, then there exist k_{1}, k_{2}, …, k_{d−1} ∈ ⟦n − 1⟧ with d|m such that k_{1}, k_{2}, …, k_{d−1} and n form a cycle of |π|.

If d = 1, that is π(n) = n^{[j]} for some j with 0 ≤ j ≤ r − 1, then π^{m}(n) = n^{[jm]} = n which implies that r|jm. Define π′ ∈ G_{r,1,n−1}^{m} by ignoring the last digit of π. Then we have

fix(π) = fix(π′) + 1,
exc_{A}(π) = exc_{A}(π′),
csum(π) = csum(π′) + j.

If d ≥ 2, we know that there are A_{d−1,k} cyclic permutations in S_{d} with k excedances for k ∈ ⟦d − 1⟧. For any cyclic permutation C of length d in S_{d} with

Exc(C) = {j ∈ ⟦d − 1⟧|C(j) > j}

such that exc(C) = k, we can color the symbols in C with the color set {[0], [1], …, [r − 1]} and obtain the colored cyclic permutation C′. Suppose that exc_{A}(C′) = k − i, we know that Exc_{A}(C′) ⊆ Exc(C), which means that exc(C)−exc_{A}(C) = i, in other words, there are i number of symbols in Exc(C) with color numbers ranging from [1] to [r − 1], so there are \binom{k}{i} ways to do this.

Let t = csum(C′) and t_{ℓ} be the color number of ℓ ∈ ⟦d⟧, then we have the equation t = t_{1} + t_{2} + ⋯ + t_{d} with 0 ≤ t_{1}, t_{2}, ⋯, t_{d} ≤ r − 1 such that

• t_{j} = 0 for j ∈ Exc(C) and j has a color number [0], and

• 1 ≤ t_{j} ≤ r − 1 for all j ∈ Exc(C) − Exc_{A}(C′), so there are i number of such j’s.

Therefore there are U_{d−k,t}^{(i)} number of solutions of the above equation, totally, there are \binom{k}{i}U_{d−k,t}^{(i)} ways to color the symbols in C such that csum(C′) = t and exc_{A}(C′) = k − i, where U_{d−k,t}^{(i)} is the coefficient of x^{t} in (x + x^{2} + ⋯ + x^{r−1})^{i}(1 + x + ⋯ + x^{r−1})^{d−k}, which can be expressed as

U_{d−k,t}^{(i)} = [x^{t}](x + x^{2} + ⋯ + x^{r−1})^{i}(1 + x + ⋯ + x^{r−1})^{d−k}

= [x^{t}] (\frac{1 − x^{r}}{1 − x} − 1)^{i} (\frac{1 − x^{r}}{1 − x} )^{d−k}

= [x^{t}] ∑_{j=0}^{i}(−1)^{i−j}\binom{i}{j}(\frac{1 − x^{r}}{1 − x} )^{d+j−k}

= ∑_{j=0}^{i}(−1)^{i−j}\binom{i}{j} ∑_{ℓ≥0}(−1)^{ℓ}\binom{d + j − k}{ℓ}\binom{d + j + t − k − ℓr − 1}{t − ℓr}.

Let C′ = (i_{1}^{[t_{1}]}, i_{2}^{[t_{2}]}, …, i_{d}^{[t_{d}]}), then C^{′d} = (i_{1}^{[t]}, i_{2}^{[t]}, …, i_{d}^{[t]}) with t = t_{1} +t_{2} +⋯+t_{d}, hence C^{′m} = (i_{1}^{[ \frac{tm}{d}]}, i_{2}^{[ \frac{tm}{d}]}, …, i_{d}^{[ \frac{tm}{d}]}) = 1 implies that r|\frac{tm}{d}. For any π ∈ G_{r,1,n}^{m} such that the symbol n lies in a cycle C′ of length d ≥ 2 with d|m (note that there are \binom{n−1}{d−1} ways to choose the digits of such a cycle), define π′′ ∈ G_{r,1,n−d}^{m} in the following way: write π in its complete notation, i.e., as a matrix of two rows, see (⋆). The first row of π′′ is (1, 2, …, n − d) while the second row is obtained from the second row of π by ignoring the digits in C′ and the other digits are placed with the numbers 1, 2, …, n − d in an order preserving way with respect to the second row of π. The parameters satisfy

fix(π) = fix(π′′),
exc_{A}(π) = exc_{A}(π′′) + exc_{A}(C′),
csum(π) = csum(π′′) + csum(C′).

The above consideration gives the following recurrence

H_{r,1,n}^{(m)}(u, v, w) = H_{r,1,n−1}^{(m)}(u, v, w) ∑_{{t|0≤t<r,r|tm}} uw^{t}

+ ∑_{d|m,d≥2} H_{r,1,n−d}^{(m)}(u, v, w)\binom{n − 1}{d − 1}A_{m,d}(v, w),

where

A_{m,d}(v, w) = ∑_{k=1}^{d−1} A_{d−1,k} ∑_{i=0}^{k} \binom{k}{i}v^{k−i} ∑_{r| \frac{tm}{d}} U_{d−k,t}^{(i)}w^{t}.

Rewriting the recurrence in terms of generating functions, we obtain that

\frac{∂}{∂x}H_{r,1}^{(m)}(x; u, v, w) = ∑_{n≥1} H_{r,1,n}^{(m)}(u, v, w)\frac{x^{n−1}}{(n − 1)!}

= ∑_{n≥1} \frac{x^{n−1}}{(n − 1)!}H_{r,1,n−1}^{(m)}(u, v, w) ∑_{\{t|0≤t<r,r|tm\}} uw^{t}

+ ∑_{d|m,d≥2} A_{m,d}(v, w)\frac{x^{d−1}}{(d − 1)!} ∑_{n≥d} \frac{x^{n−d}}{(n − d)!}H_{r,1,n−d}^{(m)}(u, v, w)

= H_{r,1}^{(m)}(x; u, v, w)( ∑_{\{t|0≤t<r,r|tm\}} uw^{t} + ∑_{d|m,d≥2} A_{m,d}(v, w)\frac{x^{d−1}}{(d − 1)!}).

Thus, the generating function H_{r,1}^{(m)}(x; u, v, w) satisfies

\frac{\frac{∂}{∂x}H_{r,1}^{(m)}(x; u, v, w)}{H_{r,1}^{(m)}(x; u, v, w)} = ∑_{\{t|0≤t<r,r|tm\}} uw^{t} + ∑_{d|m,d≥2} A_{m,d}(v, w)\frac{x^{d−1}}{(d − 1)!}.

Integrating with respect to x on both sides of the above differential equation, using the fact that H_{r,1}^{(m)}(0; u, v, w) = 1, we obtain the explicit expression for H_{r,1}^{(m)}(x; u, v, w) given in Theorem 3.1, and hence we complete the proof. □

Specially, if m = p is a prime, then we have

Corollary 3.2. Let r ≥ 1 and p be a prime. The generating function H_{r,1}^{(p)}(x; u, v, w) is

exp \{uxλ_{r,p}(w) + \frac{x^{p}}{p!} ∑_{k=1}^{p−1} A_{p−1,k} ∑_{i=0}^{k} \binom{k}{i}v^{k−i} ∑_{j≥0} U_{p−k,jr}^{(i)}w^{jr}\} ,

where λ_{r,p}(w) = ∑_{i=0}^{p−1} w^{\frac{ir}{p}} for p | r, and λ_{r,p}(w) = 1 for p ∤ r.

For the sake of comparison, the cases p = 2 and p = 3 in Corollary 3.2 generate the explicit formulas for H_{r,1}^{(2)}(x; u, v, w) and H_{r,1}^{(3)}(x; u, v, w), that is

H_{r,1}^{(2)}(x; u, v, w) = exp(uxλ_{r,2}(w) + \frac{x^{2}}{2} (v + (r − 1)w^{r})),
H_{r,1}^{(3)}(x; u, v, w) = exp(uxλ_{r,3}(w) + \frac{x^{3}}{6} B_{3,3}(v, w)),

where B_{3,3}(v, w) = v^{2} + v(1 + 3(r − 1)w^{r}) + (r^{2} − 1)w^{r} + (r − 1)(r − 2)w^{2r}.

Now let us compute the exponential generating function H_{r,s}^{(m)}(x; u, v, w) for the sequence {H_{r,s,n}^{(m)}(u, v, w)}_{n≥0}. For any σ ∈ G_{r,s,n}^{m}, we have csum(σ) ≡ 0 (mod s), so we should collect all the terms in which the exponent of w in H_{r,1}^{(m)}(u, v, w) is a multiplication of s. This observation can make us get the following:

Theorem 3.3. For r, m, s ≥ 1, let H_{r,1}^{(m)}(x; u, v, yw) = ∑_{n≥0} G_{m,r,n}(x; u, v, w)y^{n}. Then

H_{r,s}^{(m)}(x; u, v, w) = ∑_{k≥0} G_{m,r,sk}(x; u, v, w).

Now let us focus on the case m = 2. Recall that

H_{r,1}^{(2)}(x; u, v, w) = \begin{cases}e^{ux+ \frac{1}{2} x^{2}(v+(r−1)w^{r})}, & if r odd, \\ e^{ux(1+w^{\frac{r}{2}} )+ \frac{1}{2} x^{2}(v+(r−1)w^{r})}, & if r even . \end{cases}

Then by Theorem 3.3, we can compute the explicit formula for H_{r,s}^{(2)}(x; u, v, w). Since s | r, we have two cases either r odd or r even.

• If r is an odd number, then it is clear that the exponent of y in each term of the expansions of H_{r,1}^{(2)}(x; u, v, yw) is always a multiplication of s. Hence,

H_{r,s}^{(2)}(x; u, v, w) = H_{r,1}^{(2)}(x; u, v, w).

• Similarly, if r is an even number and s | \frac{r}{2}, we have that

H_{r,s}^{(2)}(x; u, v, w) = H_{r,1}^{(2)}(x; u, v, w).

• Let r be any even number such that s ∤ \frac{r}{2}. Since e^{ux(1+(yw)^{\frac{r}{2}} )} = e^{ux} ∑_{k≥0} \frac{(ux(yw)^{\frac{r}{2}} )^{k}}{k!} and e^{\frac{1}{2} x^{2}(v+(r−1)(yw)^{r})} = e^{\frac{1}{2} x^{2}v} ∑_{k≥0} \frac{((r−1)x^{2}(yw)^{r})^{k}}{2^{k}k!} , then by collecting the coefficients of y in H_{r,1}^{(2)}(x; u, v, w) such that the exponent y is a multiplication of s, we get that

e^{\frac{1}{2} x^{2}(v+(r−1)(yw)^{r})} ∑_{k≥0} \frac{(ux)^{2k}(yw)^{kr}}{(2k)!} = e^{ux+ \frac{1}{2} x^{2}(v+(r−1)(yw)^{r})} \frac{e^{uxw^{\frac{r}{2}}} + e^{−uxw^{\frac{r}{2}}}}{2} .

Therefore, the above cases give the following result.

Proposition 3.4. We have

H_{r,s}^{(2)}(x; u, v, w) = \begin{cases}e^{ux+ \frac{1}{2} x^{2}(v+(r−1)w^{r})}, & if r odd, \\ e^{ux(1+w^{\frac{r}{2}} )+ \frac{1}{2} x^{2}(v+(r−1)w^{r})}, & if r even and s | \frac{r}{2}, \\ e^{ux+ \frac{1}{2} x^{2}(v+(r−1)w^{r})}^{\frac{e^{uxw \frac{r}{2}} +e^{−uxw \frac{r}{2}}}{2}} , & if r even and s ∤ \frac{r}{2}. \end{cases}

Note that H_{r,s}^{(2)}(x; u, v, w) is the generating function for the number of involutions in G_{r,s,n}^{(2)}. By expanding the generating functions, Bagno, Garber and Mansour [2] obtained the explicit formulas for the number of involutions in G_{r,s,n}^{(2)}. But the expression in Proposition 5.7 [2] should be corrected by the third case of H_{r,s}^{(2)}(x; u, v, w) and hence Corollary 5.8 − 5.10 therein should be the following three corollaries, respectively.

Corollary 3.5. The polynomial H_{r,s,n}^{(2)}(u, v, w) is given by

∑_{k_{1}+2k_{2}+2k_{3}=n} \frac{n!}{k_{1}!(2k_{2})!k_{3}!} · \frac{u^{k_{1}+2k_{2}}w^{rk_{2}}(v + (r − 1)w^{r})^{k_{3}}}{2^{k_{3}}} .

Corollary 3.6. Let r ≥ 1. The number of colored involutions in G_{r,s,n}^{(2)} (r even, s ∤ \frac{r}{2}) with exactly k absolute fixed points and exc_{A}(π) = ℓ is given by

∑_{k+2k_{3}=n,k_{1}+2k_{2}=k} \binom{k_{3}}{ℓ} · \frac{n!}{k_{1}!(2k_{2})!k_{3}!} · \frac{(r − 1)^{k_{3}−ℓ}}{2^{k_{3}}} .

Corollary 3.7. The number of involutions π ∈ G_{r,s,n}^{(2)} (r even, s ∤ \frac{r}{2}) with exc^{Clr}(π) = k is given by

∑_{k_{1}+2k_{2}+2k_{3}=n, r(k_{2}+k_{3})=k} \frac{n!}{k_{1}!(2k_{2})!k_{3}!} · (\frac{r}{2})^{\frac{k}{r}} .

Acknowledgment: The authors would like to thank Eli Bagno and David Garber for reading previous version of the present paper and for a number of helpful discussions.

References

[1] E. Bagno and D. Garber, On the excedance number of colored permutation groups, Sém. Lotharingien Combin. 53 (2006), Art.”B53f, 17pp. (Electronic, available at

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

[2] E. Bagno, D. Garber and T. Mansour, Excedance number for involutions in complex reflection groups, Sém. Lotharingien Combin. 56 (2007), Art. B56d, 11 pp. (Electronic, available at

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

[3] D. Foata and M. Schützenberger, Théorie géométrique des polynômes Eulériens, Lecture Note in Math., Springer-Verlag, 138 (1970).

[4] G, C. Shephard and J. A. Todd, Finite unitary reflection groups, Canad. J. Math. 6 (1954), 274–304.

[5] E. Steingrímsson, Permutation statistics on indexed permutations, Europ. J. Comb. 15:2 (1994), 187–205.