Séminaire Lotharingien de Combinatoire 51 (2004), Article B51f

EULER-MAHONIAN PARAMETERS ON COLORED PERMUTATION GROUPS

Eli Bagno

Einstein Institute of Mathematics, The Hebrew University Givat Ram, Israel

              E-mail: bagnoe@math.huji.ac.il

Abstract. New combinatorial statistics on colored permutation groups are introduced here. We present two different generalizations of major index and descent number, one of them is combinatorial in nature and the other is algebraic. We also present Euler-Mahonian type joint distributions of our parameters.

1. Introduction

One of the most active branches in Enumerative Combinatorics is the study of permutation statistics. Let S_{n} be the symmetric group on n letters and let f_{i} : S_{n} ⟶ Z_{+}, (1 ≤ i ≤ t) be (non-negative, integer valued) combinatorial parameters. Then one is interested in the refined enumeration of permutations according to these parameters:

∑_{π∈S_{n}} q_{1}^{f_{1}(π)} ⋯ q_{t}^{f_{t}(π)},

where q_{i} are variables. Some of the most important parameters are the following: A descent in a permutation π = π_{1}, …, π_{n} is a position i such that π(i + 1) < π(i), an inversion is a pair i < j such that π(i) > π(j), and the major index of π is the sum of its descents. The last parameter was introduced by MacMahon in [9] and [10]. He called it the “greater index” . He proved algebraically that the major index and the inversion number are equi-distributed over the symmetric group. In other words:

∑_{π∈S_{n}} q^{inv(π)} = ∑_{π∈S_{n}} q^{maj(π)} = [n]_{q}!,

where [n]_{q} = \frac{1−q^{n}}{1−q}. (In fact, MacMahon proved the same result for the more general case where S_{n} is replaced by the set of all rearrangements of a given word - see [11]. The first combinatorial proof of this result was given by Foata [5]).

A permutation statistic that is equi-distributed with the number of descents is called Eulerian, while a permutation statistic that is equidistributed with the inversion number is called Mahonian.

A natural extension of the study of permutation statistics is the study of pairs of permutation statistics and their joint distributions. Of particular interest is the joint distribution of the descent number and the major index. The generating function for this joint distribution is given by Carlitz’s q-Eulerian polynomial:

A_{n}(t, q) = ∑_{π∈S_{n}} t^{des(π)}q^{maj(π)} = ∏_{i=0}^{n} (1 − tq^{i}) ∑_{k≥0} [k + 1]_{q}^{n}t^{k}.

(See [4], [7]).

The following problem was first suggested by Foata:

Problem 1.1. (Foata), Extend the Euler-Mahonian distribution of descent number and major index to the hyperoctahedral group B_{n}.

A solution of this problem was given by Adin, Brenti and Roichman [1] meanwhile generalizing the concept of major index in two different ways, one of them algebraic in nature (fmaj) and the other combinatorial in nature (nmaj). Let G_{r,n} = ℤ_{r} ≀ S_{n} be the group of colored permutations (see Section 2.2 below). In this paper we further extend the major index to G_{r,n} in two different ways:

• The parameter lmaj is equi-distributed with the length function of G_{r,n}. We prove the following (See Theorem 5.2):

Theorem.

∑_{π∈G_{r,n}} q^{lmaj(π)} = ∑_{π∈G_{r,n}} q^{ℓ(π)}

where ℓ is the length function with respect to the standard generators of G_{r,n} (see Section 2.2 below).

We define also the parameter ldes which is a length-oriented generalization of the descent number. The parameters ldes and lmaj have Euler-Mahonian type joint distribution. We prove (see Theorem 5.3):

Theorem.

\frac{∑_{π∈G_{r,n}} q^{lmaj(π)}t^{ldes(π)}}{∏_{i=0}^{n} (1 − tq^{i})Π_{k=1}^{n}(1 + q^{k}t[r − 1]_{qt})} = ∑_{k≥0} [k + 1]_{q}^{n}t^{k}.

• The second direction is to generalize the negative descent number, ndes, and the negative major index, nmaj, defined for B_{n} in [1]. The pair (ndes, nmaj) has a simpler Euler-Mahonian type joint distribution. We prove (see Theorem 6.8):

Theorem.

∑_{π∈G_{r,n}} q^{nmaj(π)}t^{ndes(π)} = \frac{(t^{r}; q^{r})_{n+1}}{[r]_{t}} ∑_{k≥0} [k + 1]_{q}^{n}t^{k}

The notation (t^{r}; q^{r})_{n+1} will be explained in Section 2.1.

The rest of this paper is organized as follows: In the next section we present some needed notations to be used in the sequel, including the colored permutation groups. In Section 3 we present some basic statistics on them. In Section 4 we present a formula for the length function of G_{r,n} (see also [13]). In Section 5 we introduce the parameters ldes and lmaj and find their joint distributions. The parameters nmaj and ndes will be presented in Section 6 along with their joint distribution. It should be noted that, unlike lmaj, nmaj is not equi-distributed with the standard length function.

2. Preliminaries

2.1. Notations. Let ℕ := {0, 1, 2, 3, … } and let ℤ be the ring of integers, ℚ be the field of rational numbers and ℂ the field of complex numbers.

For a ∈ ℕ let [a] := {1, 2, …, a} (where [0] := ∅). The cardinality of a set A will be denoted by |A|. More generally, given a multiset

M = {1^{a_{1}}, 2^{a_{2}}, …, r^{a_{r}}}, denote by |M| its cardinality, so |M| = ∑_{i=1}^{r} a_{i}.

Given a variable q and a commutative ring R, denote by R[q] (respectively, R[[q]]) the ring of polynomials (respectively, formal power series) in q with coefficients in R.

Define:

(a; q)_{n} := \begin{cases}1 & if n = 0; \\ (1 − a)(1 − aq) ⋯ (1 − aq^{n−1}) & otherwise. \end{cases}

Also, let:

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

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

[n]_{q}! := \frac{(q; q)_{n}}{(1 − q)^{n}} = [n]_{q} · [n − 1]_{q} ⋯ [1]_{q}.

Let n be a non-negative integer. A partition of n is an infinite sequence of non-negative integers with finitely many non-zero terms

λ = (λ_{1}, λ_{2}, …), where λ_{1} ≥ λ_{2} ≥ ⋯ and ∑_{i=1}^{∞} λ_{i} = n.

The sum ∑ λ_{i} = n is called the size of λ, denoted |λ|; write also λ ⊢ n. The number of parts of λ, ℓ(λ), is the maximal j for which λ_{j} > 0. The unique partition of n = 0 is the empty partition ∅ = (0, 0, …), which has length ℓ(∅) := 0.

For any partition λ with at most n positive parts let

m_{j}(λ) := | {1 ≤ i ≤ n | λ_{i} = j} | (for all j ≥ 0),

and let \binom{n}{m̄(λ)} denote the multinomial coefficient \binom{n}{m_{0}(λ),m_{1}(λ),...}.

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}(1)}, …, z_{n} + z′_{τ^{−1}(n)}), τ ∘ τ′)

(here + is taken mod r).

Here are some conventions we use 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 write |π| = (0, τ), (0 ∈ ℤ_{r}^{n}).

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 this manner we write, for example, the colored permutation (z, τ) =

((1, 0, 3, 2), (2, 1, 4, 3)) ∈ G_{3,4} as (\begin{matrix}1 & 2 & 3 & 4 \\ ¯2 & 1 & ¯¯¯4 & ¯¯3 \end{matrix}) or even just as: ¯21¯¯¯4¯¯3.

The group G_{r,n} is generated by the set S_{G_{r,n}} = {s_{0}, s_{1}, …, s_{n−1}} defined by their action on the set [n] as follows:

s_{i}(j) := \begin{cases}i + 1, & if j = i; \\ i, & if j = i + 1; \\ j, & otherwise. \end{cases}

whereas the exceptional generator s_{0} is defined by

s_{0}(j) := \begin{cases}¯1, & if j = 1; \\ j, & otherwise. \end{cases}

Note that, unlike the case of Coxeter groups, here the set of generators is not symmetric. Note also that 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, also known as the hyperoctahedral group, or the classical Weyl group of type B.

Returning now to the view of G_{r,n} as a semidirect product: ℤ_{r}^{n} ⋊ S_{n}, we note that it would be worthwhile to consider ℤ_{r}^{n} in another way: Given any order on the alphabet Σ, ℤ_{r}^{n} can be identified with the subgroup T of G_{r,n} consisting of the ordered permutations, i.e. those satisfying: i < j ⟹ π(i) < π(j) with respect to the given order. (This is done by sending a vector z = (z_{1}, …, z_{n}) ∈ ℤ_{r}^{n} to the unique ordered permutation π ∈ G_{r,n} satisfying z_{i}(π) = z_{i}. For example, given the order ¯3 < ¯2 < ¯1 < 1 < 2 < 3 on the set {1, 2, 3, ¯1, ¯2, ¯3}, the vector (0, 1, 1) ∈ ℤ_{2}^{3} corresponds to the colored permutation (¯3¯21) ∈ G_{2,3}). Note that if we denote by 𝕊 the group, isomorphic to S_{n}, generated by S = S_{G_{r,n}} − {s_{0}}, then T is just a set of coset representatives of 𝕊. (Indeed, any colored permutation π ∈ G_{r,n} can be written uniquely in the following way: π = σ · u where σ is an ordered permutation and u ∈ 𝕊).

3. Basic Statistics on G_{r,n}

For π ∈ G_{r,n} we define the negative set of π by :

Neg(π) = {i|z_{i}(π) ≠ 0}.  (1)

The size of the set Neg(π) will be denoted by neg(π). The following parameters we define on G_{r,n} depend on the assumption that we have some order on the alphabet Σ. Let π ∈ G_{r,n}. We say that the pair i < j is an inversion of π if π(i) > π(j). The number of inversions in π is denoted by inv(π).

i ∈ [n − 1] is a descent of π if π(i) > π(i + 1). We define:

Des(π) := {1 ≤ i ≤ n − 1 | π(i) > π(i + 1)}

to be the descent set of π and we denote by des(π) the size of Des(π). We also let

maj(π) := ∑_{i∈Des(π)} i

and call it the major index of π.

For example, consider the order ¯1 < ¯2 < ¯3 < 1 < 2 < 3 defined on the set {1, 2, 3, ¯1, ¯2, ¯3}. Also consider the colored permutation:

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

Then one has inv(π) = 2, des(π) = 1 and maj(π) = 2.

Now, given any order on the alphabet Σ, we write π = σ · u where σ ∈ T and u ∈ 𝕊 (T and 𝕊 were defined at the end of Section 2.2). We present a few simple facts concerning this coset decomposition which will be used later.

des(π) = des(u).  (2)
neg(π) = neg(σ).  (3)
∑_{i=1}^{n} z_{i}(π) = ∑_{i=1}^{n} z_{i}(σ).  (4)
maj(π) = maj(u).  (5)
∑_{z_{i}(π)≠0} |π(i)| = ∑_{z_{i}(σ)≠0} |σ(i)|.  (6)

4. A Length function for G_{r,n}

In this section we present a formula for the length of G_{r,n} with respect to S_{G_{r,n}}. A similar expression appears in [13]. The proof of our formula depends on the length order we define next although the length function itself is independent of order. We start with the definition of a length function for G_{r,n}:

Definition 4.1. For every π ∈ G_{r,n} define the length of π with respect to the set of the generators S_{G_{r,n}} = {s_{0}, s_{1}, …, s_{n−1}} to be the minimal number of generators satisfying that their product is π. Formally:

ℓ(π) = min{r ∈ N : π = s_{i_{1}} ⋯ s_{i_{r}}, for some i_{1}, …, i_{r} ∈ [0, n − 1]}.

Definition 4.2. The length order on the alphabet

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

is defined as follows:

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

Theorem 4.3. For every π ∈ G_{r,n}:

ℓ(π) = inv(π) + ∑_{z_{i}(π)≠0} (|π(i)| + z_{i}(π) − 1)

where inv(π) is calculated with respect to the length order defined above.

Proof. Denote

L(π) = inv(π) + ∑_{z_{i}(π)≠0} (|π(i)| + z_{i}(π) − 1).

We prove first that ℓ(π) ≤ L(π) by presenting an algorithm which expresses π as a product of L(π) generators. For π ∈ G_{r,n} write π = σu where σ ∈ T, u ∈ 𝕊. Our algorithm sends the identity permutation first to σ and then from σ to σu = π. This is done by multiplying on the right by Coxeter generators.

Start with the identity permutation.

• For every j = |π(i)| such that i ∈ Neg(π), in increasing order

of j:

– Move j to place 1 by multiplying on the right by the j − 1 successive decreasing generators: s_{j−1}, …, s_{1}.

– Equip j with z_{i}(π) bars, to get π(i). This will be done by multiplying on the right by s_{0}^{z_{i}(π)} and thus will cost exactly z_{i}(π) steps.

After doing this process once for every ‘colored digit‘ we get σ ∈ T, i.e., σ is increasing according to the length order.

• Mix the permutation σ in order to get π out of it. This will

cost inv(π) steps. Example: π = ¯ ¯3¯24¯1. Here σ = ¯ ¯3¯2¯14, and u = 1243. The process is (Multiplication is always on the right):

1234 →^{s_{0}} ¯1234 →^{s_{1}} 2¯134 →^{s_{0}} ¯2¯134 →^{s_{2}} ¯23¯14 →^{s_{1}} 3¯2¯14 →^{s_{0}} ¯3¯2¯14 →^{s_{0}} ¯ ¯3¯2¯14 = σ.

Now, we are left with an increasing ordered permutation which we have to mix. This will be done by inv(π) elements of the generating set S = S_{G_{r,n}} − {s_{0}} which form u and thus we have π = σu. In

summary, we used inv(π)+ ∑_{z_{i}(π)≠0} (|π(i)| − 1)+ ∑_{i=1}^{n} z_{i} steps. This proves

ℓ(π) ≤ L(π).

We prove now the other direction. For r = 2, ℤ_{r} ≀ S_{n} is the Coxeter group of type B. In this case it is known that L(π) = ℓ(π) (See for example [3]).

Take r > 2 and let π = ((z_{1}, …, z_{n}), τ) ∈ G_{r,n}. We construct π′ = ((z′_{1}, …, z′_{n}), τ) ∈ G_{2,n} by defining:

z′_{i} = \{ \begin{matrix}0 & z_{i} = 0; \\ 1 & z_{i} > 0. \end{matrix}

For example, if π = ¯ ¯4¯32¯1 ∈ G_{3,4} then π′ = ¯4¯32¯1 ∈ G_{2,4}.

Denoting k = ∑_{i=1}^{n} z_{i} − ∑_{i=1}^{n} z′_{i} we have, by the construction of π′, that

L(π) = L(π′) + k. Now, assume to the contrary that L(π) > ℓ(π). We have ℓ(π) ≥ ℓ(π′) + k. (Indeed, take any reduced word representing π and delete from it the k occurrences of the generator s_{0}, which are responsible for coloring the digits in π that are reducing colors in the passage to π′. This will give us a word representing π′).

We have now:

L(π′) + k = L(π) > ℓ(π) ≥ ℓ(π′) + k

which contradicts the fact that L(π′) = ℓ(π′) in G_{2,n}. □

We proceed to the calculation of the generating function of the length function.

Theorem 4.4.

∑_{π∈G_{r,n}} q^{ℓ(π)} = [n]_{q}! · ∏_{i=1}^{n} (1 + q^{i}[r − 1]_{q}).

Proof. If π ∈ G_{r,n} then using the coset decomposition we can write π = σ · u where σ ∈ T, u ∈ 𝕊. As can be easily deduced by the proof of Theorem 4.3, the length function can also be written as:

ℓ(π) = inv(u) + ℓ(σ)

where ℓ(σ) = ∑_{z_{i}(σ)≠0} (|σ(i)| − 1 + z_{i}(σ)) is the length function of σ.

Now, it is well known that ∑_{u∈𝕊}q^{inv(u)} = [n]_{q}!. Thus,

∑_{π∈G_{r,n}} q^{ℓ(π)} = ∑_{u∈𝕊}q^{inv(u)} · ∑_{σ∈T} q^{ℓ(π)} = [n]_{q}!A_{n}

where by induction

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

We have in summary:

∑_{π∈G_{r,n}} q^{ℓ(π)} = [n]_{q}! ∏_{i=1}^{n} (1 + q^{i}[r − 1]_{q}).

□

5. The Parameter lmaj

In this section we introduce the first generalization of the parameter maj defined for the symmetric groups and prove its equi-distribution with the length function of G_{r,n}. We introduce also the parameter ldes which is a generalization of the parameter des defined for the symmetric groups. We start with the following definitions:

Definition 5.1. For every π ∈ G_{r,n} we define:

ldes(π) = des(π) + ∑_{i=1}^{n} z_{i}(π)

and

lmaj(π) = maj(π) + ∑_{z_{i}(π)≠0} (|π(i)| − 1) + ∑_{i=1}^{n} z_{i}(π)

where the descents are computed with respect to the length order.

Theorem 5.2. The parameter lmaj equi distributes with the length function over G_{r,n}, i.e.,

∑_{π∈G_{r,n}} q^{ℓ(π)} = ∑_{π∈G_{r,n}} q^{lmaj(π)}.

Proof. We use the semidirect decomposition of G_{r,n} and the equations (3), (4), (5) and (6) to get:

∑_{π∈G_{r,n}} q^{lmaj(π)} = ∑_{σu∈G_{r,n}} q^{maj(σu)+ ∑_{z_{i}(σu)≠0} (|σu(i)|−1+z_{i}(σu))}

= ∑_{u∈𝕊}q^{maj(u)} ∑_{σ∈T} q^{∑_{z_{i}(σ)≠0} (|σ(i)|−1+z_{i}(σ))}

= ∑_{u∈𝕊}q^{inv(u)} ∑_{σ∈T} q^{∑_{z_{i}(σ)≠0} (|σ(i)|−1+z_{i}(σ))}

= ∑_{π∈G_{r,n}} q^{ℓ(π)}.

□

5.1. Euler-Mahonian Type Distribution. In this section we present an Euler-Mahonian type bi-distribution for the parameters lmaj and ldes over G_{r,n}.

Theorem 5.3.

\frac{∑_{π∈G_{r,n}} t^{ldes(π)}q^{lmaj(π)}}{(t; q)_{n+1}(1 + q^{k}t[r − 1]_{qt})} = ∑_{k≥0} [k + 1]_{q}^{n}t^{k}.

Proof. We use the semidirect decomposition of G_{r,n} and the equations (2), (3), (4), (5) and (6) to get:

∑_{π∈G_{r,n}} t^{ldes(π)}q^{lmaj(π)} = ∑_{π∈G_{r,n}} t^{des(π)+ ∑_{i=1}^{n} z_{i}(π)}q^{maj(π)+ ∑_{z_{i}(π)≠0} (|π(i)|−1+z_{i}(π))}

= ∑_{σ∈T} ∑_{u∈𝕊}t^{des(u)+ ∑_{i=1}^{n} z_{i}(σ)}q^{maj(u)+ ∑_{z_{i}(σ)≠0} (|σ(i)|−1+z_{i}(σ))}

= ∑_{σ∈T} t^{∑_{i=1}^{n} z_{i}(σ)}q^{∑_{z_{i}(σ)≠0} (|σ(i)|−1+z_{i}(σ))} ∑_{u∈𝕊}t^{des(u)}q^{maj(u)}.

By [1, Theorem 2.2], we have:

∑_{u∈𝕊}t^{des(u)}q^{maj(u)} = ∏_{i=0}^{n} (1 − tq^{i}) ∑_{k≥0} [k + 1]_{q}^{n}t^{k},  (7)

so we are left with the sum :

∑_{σ∈T} t^{∑_{i=1}^{n} z_{i}(σ)}q^{∑_{z_{i}(σ)≠0} (|σ(i)|−1+z_{i}(σ))}.

By the same technique we adopted in the proof of Theorem 4.4 we can prove that

∑_{σ∈T} t^{∑_{i=1}^{n} z_{i}(σ)}q^{∑_{z_{i}(σ)≠0} (|σ(i)|−1+z_{i}(σ))} = ∏_{i=1}^{n} (1 + q^{i}t[r − 1]_{qt}).

Combining this with equation (7) we get:

∑_{π∈G_{r,n}} t^{ldes(π)}q^{lmaj(π)} =

∏_{k=1}^{n} (1 + q^{k}t[r − 1]_{qt}) ∏_{i=0}^{n} (1 − tq^{i}) ∑_{k≥0} [k + 1]_{q}^{n}t^{k},

and thus

\frac{∑_{π∈ℤ_{r}≀S_{n}} t^{ldes(π)}q^{lmaj(π)}}{Π_{i=0}^{n}(1 − tq^{i})Π_{k=1}^{n}(1 + q^{k}t[r − 1]_{qt})} = ∑_{k≥0} [k + 1]_{q}^{n}t^{k}.

□

6. The Parameter nmaj

In this section we define another parameter on ℤ_{r}≀S_{n}. This parameter is a generalization of the parameter nmaj defined in [2]. The results of this section do not depend depend on the order one chooses on the alphabet Σ = {1, …, n, ¯1, …, n̄, …, 1^{[r−1]}, …, n^{[r−1]}}.

Definition 6.1. For π ∈ ℤ_{r} ≀ S_{n} define the multiset:

NNeg(π) = {i^{z_{i}(π)}}.

Note that each i with z_{i}(π) > 0 appears z_{i}(π) times.

Definition 6.2. For π ∈ G_{r,n} define the multiset:

NDes(π) = Des(π) ⊎ NNeg(π^{−1}).

We define also ndes(π) = |NDes(π)|.

Definition 6.3. For π ∈ G_{r,n} define

nmaj(π) = ∑_{i∈NDes(π)} i,

and also

ndes(π) = |NDes(π)|.

Example 6.4. Consider the order ¯1 < ¯2 < ¯3 < 1 < 2 < 3 and take π = ¯3¯¯12. Here Des(π) = {1}, π^{−1} = ¯23¯¯1, NNeg(π^{−1}) = {1, 3, 3}, NDes(π) = {1, 1, 3, 3}, nmaj(π) = 1 + 1 + 3 + 3 = 8 and ndes(π) = 4.

We define also some refinements of the parameters ndes and nmaj. They will be used in the proof of the main result of this section.

Definition 6.5. For every π ∈ G_{r,n} define

d_{i}(π) := |{j ∈ Des(π) : j ≥ i}| (1 ≤ i ≤ n).

This is the number of descents in π from position i on.

Define also for every π ∈ G_{r,n}

n_{i}(π) = |{j ∈ NNeg(π) : j ≥ i}|.

Note that n_{i}(π) counts the number of colors from position i on.

Observation 6.6. Let π ∈ G_{r,n}. Then

ndes(π) = d_{1}(π) + n_{1}(π^{−1}),

nmaj(π) = ∑_{i=1}^{n} [d_{i}(π) + n_{i}(π^{−1})].

6.1. Euler-Mahonian Distribution. In what follows we present an Euler-Mahonian type distribution of the parameters ndes and nmaj defined earlier. We use here the Hilbert series of the algebra ℂ[q_{1}, …, q_{n}] with respect to multi-degree rearranged into a weakly decreasing sequence, i.e., a partition. The right-hand side in the following result is the Hilbert series of the above algebra.

Theorem 6.7.

∑_{ℓ(λ)≤n} \binom{n}{m̄(λ)} ∏_{i=1}^{n} q_{i}^{λ_{i}} = \frac{∑_{π∈G_{r,n}} ∏_{i=1}^{n} q_{i}^{d_{i}(π)+n_{i}(π^{−1})}}{∏_{i=1}^{n}(1 − q_{1}^{r} ⋯ q_{i}^{r})}

in ℂ[[q_{1}, …, q_{n}]].

Proof. Recall from Section 3 the definition of T ⊆ G_{r,n} as the set of ordered permutations. As already shown in Section 3, T can be seen as a copy of ℤ_{r}^{n} and thus the fact that G_{r,n} = ℤ_{r}^{n} ⋊ S_{n} implies that every π ∈ G_{r,n} can be uniquely written as π = σu where σ ∈ T and u ∈ 𝕊, where 𝕊 is the subgroup of G_{r,n} generated by S_{G_{r,n}} − {s_{0}}.

It is clear from the definitions that d_{i}(σu) = d_{i}(u) and n_{i}(u^{−1}σ^{−1}) = n_{i}(σ^{−1}) for all σ ∈ T, u ∈ S_{n} and 1 ≤ i ≤ n. Therefore

∑_{π∈G_{r,n}} ∏_{i=1}^{n} q_{i}^{d_{i}(π)+n_{i}(π^{−1})} = ∑_{u∈𝕊} ∑_{σ∈T} ∏_{i=1}^{n} q_{i}^{d_{i}(σu)+n_{i}((σu)^{−1})}

= ∑_{u∈𝕊} ∑_{σ∈T} ∏_{i=1}^{n} q_{i}^{d_{i}(u)+n_{i}(σ^{−1})}

= ∑_{u∈𝕊} ∏_{i=1}^{n} q_{i}^{d_{i}(u)} · ∑_{σ∈T} ∏_{i=1}^{n} q_{i}^{n_{i}(σ^{−1})}.

In [2, Theorem 6.2], it is proven that the Hilbert series with respect to multi-degree of ℂ[q_{1}, …, q_{n}] can be written as a product of the generating function of the descent basis for type A and the generating function of the symmetric functions. Explicitly:

∑_{ℓ(λ)≤n} \binom{n}{m̄(λ)} ∏_{i=1}^{n} q_{i}^{λ_{i}} = \frac{∑_{π∈S_{n}} ∏_{i=1}^{n} q_{i}^{d_{i}(π)}}{∏_{i=1}^{n}(1 − q_{1} ⋯ q_{i})}  (8)

in ℂ[[q_{1}, …, q_{n}]], where the sum on the left-hand side is taken over all partitions with at most n parts.

Thus, in order to complete the proof we have to prove that:

∑_{σ∈T} ∏_{i=1}^{n} q_{i}^{n_{i}(σ^{−1})} = \begin{matrix}∏_{i=1}^{n} & (1 − q_{1}^{r} ⋯ q_{i}^{r}) \\ ∏_{i=1}^{n} & (1 − q_{1} ⋯ q_{i}) \end{matrix}.  (9)

Define a function ϕ : {0, …, r − 1} → {0, .., r − 1} by

ϕ(i) = \{ \begin{matrix}0 & i = 0 \\ r − i & i ≠ 0 \end{matrix} .

Note that there is a bijection between the elements σ ∈ T and the multisets of the form {1^{j_{1}}, …, n^{j_{n}}} where 0 ≤ j_{i} ≤ r − 1, given by

σ ↦ NNeg(σ^{−1}) = {|σ(i)|^{ϕ(z_{i})(σ)}}.

(Indeed, given any multiset A = {1^{j_{1}}, …, n^{j_{n}}}, define τ by τ(i) = i_{ϕ(j_{i})} for every 1 ≤ i ≤ n and then order τ to get σ. For example, given A = {1, 1, 2, 2, 3}, we form τ = ¯1¯2¯¯34 and then σ = ¯ ¯3¯2¯14).

Now, in order to calculate the sum ∑_{σ∈T} ∏_{i=1}^{n} q_{i}^{n_{i}(σ^{−1})}, we can run over

the multisets of the form {1^{j_{1}}, …, n^{j_{n}}} where 0 ≤ j_{i} ≤ r − 1. Here, every i, inserted to such a multiset j_{i} times, contributes the monomial (q_{1} ⋯ q_{i})^{j_{i}} to our sum. This gives us:

∑_{σ∈T} ∏_{i=1}^{n} q_{i}^{n_{i}(σ^{−1})}

= (1 + q_{1} + ⋯ + q_{1}^{r−1})(1 + q_{1}q_{2} + (q_{1}q_{2})^{2} + ⋯ + (q_{1}q_{2})^{r−1})

⋯ (1 + q_{1} ⋯ q_{n} + (q_{1} ⋯ q_{n})^{2} + ⋯ + (q_{1} ⋯ q_{n})^{r−1})

= \begin{matrix}∏_{i=1}^{n} & (1 − q_{1}^{r} ⋯ q_{i}^{r}) \\ ∏_{i=1}^{n} & (1 − q_{1} ⋯ q_{i}) \end{matrix}.

□

This leads us to the following generalization of the Carlitz identity for the parameters ndes and nmaj.

Theorem 6.8.

∑_{π∈G_{r,n}} q^{nmaj(π)}t^{ndes(π)} = \frac{(t^{r}; q^{r})_{n+1}}{[r]_{t}} ∑_{k≥0} [k + 1]_{q}^{n}t^{k}.

Proof. Substitute, in Theorem 6.7, q_{1} = qt and q_{2} = q_{3} = ⋯ = q_{n} = q to get:

∑_{ℓ(λ)≤n} \binom{n}{m̄(λ)}q^{∑_{i=1}^{n} λ_{i}} · t^{λ_{1}} = \frac{∑_{π∈G_{r,n}} q^{nmaj(π)}t^{ndes(π)}}{∏_{i=1}^{n} (1 − t^{r}q^{ir})} .

Dividing by (1 − t) we have:

\frac{∑_{π∈G_{r,n}} q^{nmaj(π)}t^{ndes(π)}}{(1 − t) ∏_{i=1}^{n} (1 − t^{r}q^{ir})} = ∑_{k=0}^{∞} ∑_{\begin{matrix}ℓ(λ)≤n \\ λ_{1}≤k \end{matrix}} \binom{n}{m̄(λ)}q^{∑_{i=1}^{n} λ_{i}}t^{k},

and thus the coefficient of t^{k} is

∑_{\begin{matrix}ℓ(λ)≤n \\ λ_{1}≤k \end{matrix}} \binom{n}{m̄(λ)}q^{∑_{i=1}^{n} λ_{i}} = ∑_{(l_{1},...,l_{n})∈[0,k]^{n}} q^{∑_{i=1}^{n} l_{i}} = (∑_{j=0}^{k} q^{j})^{n} = [k + 1]_{q}^{n},

and we have proved:

∑_{π∈G_{r,n}} q^{nmaj(π)}t^{ndes(π)} = (1 − t) ∏_{i=1}^{n} (1 − t^{r}q^{ir}) ∑_{k≥0} [k + 1]_{q}^{n}t^{k}

= \frac{(t^{r}; q^{r})_{n+1}}{[r]_{t}} ∑_{k≥0} [k + 1]_{q}^{n}t^{k}.

□

Appendix A. The distribution of nmaj

After the completion of this work we were told about the preprint of J. Haglund, N. Loehr and J. B. Remmel [8] : ’Statistics on wreath products, perfect matchings and signed words’. A variant of the parameter defined here as nmaj appears also in their work. Its distribution over

G_{r,n} is proven there to be ∏_{i=1}^{n} [ri]_{q}. We enclose here another proof of

this distribution, based on the proof of Theorem 6.8 of the last section.

Theorem Appendix A.1.

∑_{π∈G_{r,n}} q^{nmaj(π)} = ∏_{i=1}^{n} [ri]_{q}.

Proof. We write:

∑_{π∈G_{r,n}} q^{nmaj(π)} = ∑_{π∈G_{r,n}} q^{∑_{i=1}^{n} d_{i}(π)+ ∑_{i=1}^{n} n_{i}(π^{−1})}

= ∑_{u∈𝕊}q^{∑_{i=1}^{n} d_{i}(u)} ∑_{σ∈T} q^{∑_{i=1}^{n} n_{i}(σ^{−1})}.

By substituting q = q_{1} = ⋯ = q_{n} in equation 8 we get:

∑_{u∈𝕊}q^{∑_{i=1}^{n} d_{i}(u)} = Hilb(ℂ[x_{1}, …, x_{n}], q) · ∏_{i=1}^{n} (1 − q^{i})

but on the other hand

Hilb(ℂ[x_{1}, …, x_{n}], q) = \frac{1}{(1 − q)^{n}}

so we have

∑_{u∈𝕊}q^{∑_{i=1}^{n} d_{i}(u)} = ∏_{i=1}^{n} (1 − q^{i}) · \frac{1}{(1 − q)^{n}} .

We turn now to the calculation of ∑_{σ∈T} q^{∑_{i=1}^{n} n_{i}(σ^{−1})}.

Substituting q = q_{1} = ⋯ = q_{n} in equation 9 we get:

∑_{σ∈T} q^{∑_{i=1}^{n} n_{i}(σ^{−1})} = \begin{matrix}∏_{i=1}^{n} & (1 − q^{ri}) \\ ∏_{i=1}^{n} & (1 − q^{i}) \end{matrix}.

We have now:

∑_{π∈G_{r,n}} q^{nmaj(π)} = ∏_{i=1}^{n} (1 − q^{i}) · \frac{1}{(1 − q)^{n}} · \begin{matrix}∏_{i=1}^{n} & (1 − q^{ri}) \\ ∏_{i=1}^{n} & (1 − q^{i}) \end{matrix} = ∏_{i=1}^{n} [ri]_{q}.

□

Acknowledgments. I want to thank Ron Adin and Yuval Roichman for useful discussions and fruitful ideas.

References

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

multivariate Statistics, Trans. Amer. Math. Soc., to appear.

[3] A. Björner and F. Brenti, Combinatorics of Coxeter groups, preprint.

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

[5] D. Foata, Distributions Euleriennes et Mahoniennes sur le groupe des permutations, M. Aigner (ed), Higher Combinatorics, 27–49, Reidel, Boston, Berlin Combinatorics Symposium, (1976).

[6] D. Foata, Rearrangements of words, in M.Lothaire, Combinatorics on words, Encyclopedia of Math. and its Appl., Vol. 17, Addison-Wesley Publishing Company, (1983).

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

[8] J. Haglund, N. Loehr and J. B. Remmel, Statistics on wreath products perfect matchings and signed words, European Journal of Combinatorics, to appear.

[9] P. A. MacMahon, Combinatory analysis, vol. 1, Cambridge Univ. Press, Cambridge, 1918.

[10] P. A. MacMahon, The indices of permutations and the derivation therefrom of functions of a single varaible asscoiated with the permutations of any assemblage of objects, Amer. J. Math., 35 (1913), 281-322.

[11] P. A. MacMahon, Two applications of general thorems in combinatory analysis, Proc. London Math. Soc., 15 (1916), 314-321.

[12] V. Reiner, Upper binomial posets and signed permutation statistics, Europ. J. Combinatorics, 14, (1993), 581–588.

[13] E. Steingrímsson, Permutation statistics of indexed permutations, Europ. J. Combin. 15 (1994), 187–205.