Séminaire Lotharingien de Combinatoire 60 (2009), Article B60e

COUNTING DESCENT PAIRS WITH PRESCRIBED COLORS IN THE COLORED PERMUTATION GROUPS

ELI BAGNO, DAVID GARBER, AND TOUFIK MANSOUR

Abstract. We define new statistics, (c, d)-descents, on the colored permutation groups ℤ_{r} ≀ S_{n} and compute the distribution of these statistics on the elements in these groups. We use some combinatorial approaches, recurrences, and generating functions manipulations to obtain our results.

1. Introduction

A permutation statistic on the symmetric group S_{n}, or more generally over a group, is a function from the group to the set of nonnegative integers. The study of permutation statistics started with Euler, who considered the number of descents of a permutation. Netto, at the beginning of the last century, considered the number of inversions, and Major Percy MacMahon [6, Vol. I, pp. 135, 186; Vol. II, p. viii], [7] considered the parameter called today major index and the excedance number.

On the symmetric group S_{n}, a descent pair of a permutation π ∈ S_{n} is a pair (i, i+1) such that π_{i} > π_{i+1}. The descent set of a permutation π = π_{1}π_{2} ⋯ π_{n} ∈ S_{n}, denoted by Des(π), is the set of indices i such that (i, i + 1) is a descent pair. The number of descents in a permutation π, denoted by des(π) = |Des(π)|, is a classical permutation statistic. This statistic was first studied by MacMahon [6] almost a century ago, and it still plays an important role in the study of permutation statistics.

Kitaev and Remmel [5] counted descents in S_{n} according to the parity of the first or second element of the descent pair. In [4], they generalize it to the case where the first or the second element in the descent pair is divisible by k for some k ≥ 2. Some more research was done in the direction of studying the corresponding distribution for words (see [1, 2, 3]).

Let r, n be positive integers. A colored permutation on of n objects with r colors is a bijection π on the set

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

satisfying the following condition: if π(i^{[α]}) = j^{[β]}, then π(i^{[α+1]}) = j^{[β+1]}, where the exponents are taken modulo r. If π_{k} = i^{[j]}, we define |π_{k}| = i, where π_{k} = π(k^{[0]}) for each k. Moreover, the color of the position k, denoted by c_{k}(π), is j. The set of all such colored permutations form a group, G_{r,n}, which is isomorphic to the wreath product ℤ_{r} ≀ S_{n} = ℤ_{r}^{n} ⋊ S_{n}. The classical Weyl groups appear as special cases: the symmetric group G_{1,n} = S_{n} and the hyperoctahedral group G_{2,n} = B_{n}.

We fix two different orders on the set Σ_{r,n}:

• The color order:

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

• The absolute order:

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

Let ≺ be one of the orders defined above. Let π ∈ G_{r,n} and let c, d be two nonnegative integers such that c ≤ d. A (c, d)-descent in position i is a descent (with respect to ≺) in position i such that c_{i}(π) = c and c_{i+1}(π) = d. For example, if π = 6^{[1]}2^{[2]}4^{[0]}3^{[1]}5^{[2]}1^{[2]}, then π has two (1, 2)-descents with respect to the color order: i = 1 and i = 4, but only one (1, 2)-descent with respect to the absolute order: i = 1. The number of (c, d)-descents in π with respect to the color order (respectively absolute order) is denoted by des_{c,d}^{Clr}(π) (respectively des_{c,d}^{Abs}(π)).

It should be noted that actually, in the case of (c, d)-descents where c < d with respect to the color order, one can forget about the colored permutations and deal with the underlying color words. For example, the underlying color word of π = 6^{[1]}2^{[2]}4^{[0]}3^{[1]}5^{[2]}1^{[2]} is 120122, so our problem reduces to finding the number of words over {0, …, r − 1} having a fixed number of places where the color d is subsequent to c. Hence, the enumeration of (c, d)-descents in the case of the color order can be done as a special case of the work of Hall and Remmel [2] where they compute the generating function of (X, Y)-descents (where X and Y are subsets of the alphabet). Nevertheless, since our enumeration covers both orders at once, we present here a simple and direct combinatorial proof for these enumerations.

In Section 2, we study the generating function for the number of colored permutations in G_{r,n} having exactly m (c, d)-descents where c < d.

We get the following results.

COLORED DESCENTS IN G_{r,n} 3

Proposition 1.1. The number of colored permutations in G_{r,n} with exactly 0 (c, d)-descents (0 ≤ c < d ≤ r − 1), with respect to both orders is

n! ∑_{k=0}^{n}(r − 1)^{k} + n! ∑_{k=1}^{n−1} ∑_{b=1}^{k} \binom{k}{b}\binom{n − k}{b}(r − 2)^{b}(r − 1)^{n−k−b}.

The number of colored permutations in G_{r,n} with exactly m > 0 (c, d)-descents (0 ≤ c < d ≤ r − 1) with respect to the color order, is given by

n! ∑_{k=1}^{n−1} ∑_{b=1}^{k} \binom{k}{b}\binom{n − k}{b}\binom{b}{m}(r − 2)^{b−m}(r − 1)^{n−k−b}.

The number of colored permutations in G_{r,n} with exactly m > 0 (c, d)-descents (0 ≤ c < d ≤ r − 1) with respect to the absolute order, is given by

\frac{n!}{2^{m}} ∑_{k=1}^{n−1} ∑_{b=1}^{k} \binom{k}{b}\binom{n − k}{b}\binom{b}{m}(r − 2)^{b−m}(r − 1)^{n−k−b}.

Note that when n = 2, there will be no dependency on the value of r, as a simple verification shows.

The following is a special case for the hyperoctahedral group B_{n} = G_{2,n}.

Proposition 1.2. The number of signed permutations in B_{n} with exactly m (0, 1)-descents is given by n!\binom{n+1}{n−2m}.

In Section 3, we study the generating function for the number of colored permutations in G_{r,n} having exactly m (c, c)-descents. Here, we obtain our results by using recurrences and manipulations with exponential generating functions.

Proposition 1.3. The number of colored permutations in G_{r,n} with exactly m (c, c)-descents, 0 ≤ c ≤ r − 1, with respect to both orders is given by

n! ∑_{j=0}^{n} ∑_{i=0}^{m}(−1)^{i}(r − 1)^{j}\binom{j + m − i}{j}\binom{n + 1}{i}\frac{(m − i + j + 1)^{n−j}}{(n − j)!} .

2. Counting (c, d)-descents with c < d by a direct combinatorial approach

Our approach for enumerating (c, d)-descents is based on a counting argument. We enumerate for both orders simultaneously.

Let π = π_{1}^{[c_{1}]}π_{2}^{[c_{2}]} ⋯ π_{n}^{[c_{n}]} ∈ G_{r,n}. Define a c-block (respectively c̄- block) in π to be a maximal subsequence π_{i}^{[c_{i}]}π_{i+1}^{[c_{i+1}]} ⋯ π_{j}^{[c_{j}]} of π such that for all k ∈ [i, j], c_{k} = c (respectively c_{k} ≠ c). The cardinalities of the blocks form a composition of n. For example, in G_{6,6}, with c = 2, d = 3, if π = 2^{[2]}4^{[2]}5^{[3]}1^{[4]}6^{[2]}3^{[1]}, then the corresponding blocks of π are

{2^{[2]}, 4^{[2]}}, {5^{[3]}, 1^{[4]}}, {6^{[2]}}, {3^{[1]}},

while the corresponding composition is (2, 2, 1, 1).

Note that (c, d)-descents can appear in the transitions from a c-block to a c̄-block, but not necessarily in all of these transitions.

Let Comp(n) be the set of compositions of n, and let Comp^{clr}(n) = Comp(n) × {c, c̄}. For each φ ∈ Comp(n) and x ∈ {c, c̄}, the element (φ, x) ∈ Comp^{clr}(n) represents the composition φ where the first part is colored by x.

Now, let μ = (φ, x) ∈ Comp^{clr}(n). We define the following parameters:

• e_{φ} is the sum of parts in the even places of φ. For example, if φ = (2, 3, 4, 5) then e_{φ} = 3 + 5 = 8.

• k = k_{μ} = \begin{cases}n − e_{φ} & if x = c, \\ e_{φ} & if x = c̄. \end{cases}

• b = b_{μ} is the number of c-blocks and b̄_{μ} is the number of c̄- blocks. Explicitly,

b_{μ} = \begin{cases}\frac{|φ|}{2} & if |φ| even, \\ \frac{|φ|+1}{2} & if |φ| odd, x = c, \\ \frac{|φ|−1}{2} & if |φ| odd, x = c̄, \end{cases}

where |φ| is the number of parts of φ, and b̄_{μ} = |φ| − b_{μ}.

• t_{μ} is the number of transitions between a c-block to a c̄-block.

Define

A_{r,n}^{Ord}(q) = ∑_{π∈G_{r,n}} q^{des_{c,d}^{Ord}(π)},

where Ord stands for the orders Clr or Abs. For calculating A_{r,n}^{Ord}(q), we run over the elements of Comp^{clr}(n), instead of running over the elements of G_{r,n}.

Lemma 2.1. For all n ≥ 0,

(2.1)  A_{r,n}^{Clr}(q) = n! ∑_{μ∈Comp^{clr}(n)}(q + r − 2)^{t_{μ}}(r − 1)^{n−k_{μ}−t_{μ}}.

(2.2)  A_{r,n}^{Abs}(q) = n! ∑_{μ∈Comp^{clr}(n)} (\frac{q}{2} + r − 2)^{t_{μ}} (r − 1)^{n−k_{μ}−t_{μ}}.

Proof. Each μ ∈ Comp^{clr}(n) gives rise to n!(r−1)^{n−k_{μ}} elements of G_{r,n}. π ∈ G_{r,n} contributes a (c, d)-descent with respect to the color order in each transition from a c-block to a c̄-block such that the first digit of the c̄-block is colored by d. This proves Equation (2.1).

Only half of the (c, d)-descents with respect to the color order are also (c, d)-descents with respect to the absolute order (see an example in the introduction), so we have Equation (2.2) too. □

In order to get an explicit expression for the formulas appearing in Lemma 2.1, we treat separately Comp(n) × {c} and Comp(n) × {c̄}. We do this only for the color order. The other computation is similar.

Let μ = (φ, c) ∈ Comp(n) × {c}.

We split the contribution into three cases according to |φ|.

(1) |φ| = 1: in this case we have k_{μ} = n and t_{μ} = 0, thus its contribution is

n!_{∑_{μ=(φ,c)∈Comp^{clr}(n)} ; |φ|=1}(q + r − 2)^{t_{μ}}(r − 1)^{n−k_{μ}−t_{μ}} = n!.

(2) |φ| is even: in this case, k_{μ} can vary in {1, …, n − 1} and hence b_{μ} ∈ {1, …, k_{μ}}. Moreover, b̄_{μ} = t_{μ} = b_{μ}. Then the contribution is

n!_{∑_{μ=(φ,c)∈Comp^{clr}(n)} |φ| even}(q + r − 2)^{t_{μ}}(r − 1)^{n−k_{μ}−t_{μ}}

= n! ∑_{k=1}^{n−1} ∑_{b=1}^{k} \binom{k − 1}{k − b}\binom{n − k − 1}{n − k − b}(q + r − 2)^{b}(r − 1)^{n−k−b}.

Note that the first binomial coefficient corresponds to the choice of dividing the k digits colored by c into b non-empty blocks, while the second binomial coefficient corresponds to the choice of dividing the remaining n − k digits (which are not colored by c) into b̄ non-empty blocks.

(3) |φ| > 1 odd: In this case, k_{μ} can vary in {2, …, n − 1} and hence b_{μ} ∈ {2, …, k_{μ}}. Moreover, b̄_{μ} = b − 1, t_{μ} = b_{μ} − 1. Then

the contribution is

n!_{∑_{μ=(φ,c)∈Comp^{clr}(n)} |φ| odd}(q + r − 2)^{t_{μ}}(r − 1)^{n−k_{μ}−t_{μ}}

= n! ∑_{k=2}^{n−1} ∑_{b=1}^{k} \binom{k − 1}{k − b}\binom{n − k − 1}{n − k − b + 1}(q + r − 2)^{b−1}(r − 1)^{n−k−b+1}.

Now, let us treat the set Comp(n)×{c̄}. Let μ = (φ, c̄) ∈ Comp(n)× {c̄}.

As in the case of Comp(n)×{c}, we split the computation into three cases according to |φ|.

(1) |φ| = 1:

n!_{∑_{μ=(φ,c̄)∈Comp^{clr}(n)} ; |φ|=1}(q + r − 2)^{t_{μ}}(r − 1)^{n−k_{μ}−t_{μ}} = n!(r − 1)^{n}.

(2) |φ| is even: in this case, k_{μ} ∈ {1, …, n − 1} and hence b_{μ} ∈ {1, …, k_{μ}}. Moreover, b̄_{μ} = t_{μ} = b_{μ} − 1. Then we have

n!_{∑_{μ=(φ,c̄)∈Comp^{clr}(n)} |φ| even}(q + r − 2)^{t_{μ}}(r − 1)^{n−k_{μ}−t_{μ}}

= n! ∑_{k=1}^{n−1} ∑_{b=1}^{k} \binom{k − 1}{k − b}\binom{n − k − 1}{n − k − b}(q + r − 2)^{b−1}(r − 1)^{n−k−b+1}.

(3) |φ| > 1 odd: in this case, k_{μ} can vary in {1, …, n − 2} and hence b_{μ} ∈ {2, …, k_{μ}}. Moreover, b̄_{μ} = b_{μ} + 1, t_{μ} = b_{μ}. Then we have

n!_{∑_{μ=(φ,c̄)∈Comp^{clr}(n)} |φ| odd}(q + r − 2)^{t_{μ}}(r − 1)^{n−k_{μ}−t_{μ}}

= n! ∑_{k=1}^{n−2} ∑_{b=1}^{k} \binom{k − 1}{k − b}\binom{n − k − 1}{n − k − b − 1}(q + r − 2)^{b}(r − 1)^{n−k−b}.

Summing up all the parts, we get

A_{r,n}^{Clr}(q) = n!(1 + (r − 1)^{n})

+ n! ∑_{k=1}^{n−1} ∑_{b=1}^{k} \binom{k − 1}{k − b}\binom{n − k}{n − k − b}(q + r − 2)^{b}(r − 1)^{n−k−b}

+ n! ∑_{k=1}^{n−1} ∑_{b=1}^{k} \binom{k − 1}{k − b}\binom{n − k}{n − k − b + 1}

· (q + r − 2)^{b−1}(r − 1)^{n−k−b+1}

= n! ∑_{k=0}^{n} (r − 1)^{k}

+ n! ∑_{k=1}^{n−1} ∑_{b=1}^{k} \binom{k}{b}\binom{n − k}{b}(q + r − 2)^{b}(r − 1)^{n−k−b}.

Here is the analogous result for the absolute order.

Corollary 2.2.

A_{r,n}^{Abs}(q) = n! ∑_{k=0}^{n} (r − 1)^{k}

+ n! ∑_{k=1}^{n−1} ∑_{b=1}^{k} \binom{k}{b}\binom{n − k}{b} (\frac{q}{2} + r − 2)^{b} (r − 1)^{n−k−b}.

Hence, we get the following result.

Proposition 2.3. The number of colored permutations in G_{r,n} with exactly 0 (c, d)-descents, 0 ≤ c < d ≤ r − 1, is

n! ∑_{k=0}^{n} (r − 1)^{k} + n! ∑_{k=1}^{n−1} ∑_{b=1}^{k} \binom{k}{b}\binom{n − k}{b}(r − 2)^{b}(r − 1)^{n−k−b}.

The number of colored permutations in G_{r,n} with exactly m > 0 (c, d)-descents (0 ≤ c < d ≤ r − 1) with respect to the color order, is given by

n! ∑_{k=1}^{n−1} ∑_{b=1}^{k} \binom{k}{b}\binom{n − k}{b}\binom{b}{m}(r − 2)^{b−m}(r − 1)^{n−k−b}.

The number of colored permutations in G_{r,n} with exactly m > 0 (c, d)-descents (0 ≤ c < d ≤ r − 1) with respect to the absolute order, is given by

\frac{n!}{2^{m}} ∑_{k=1}^{n−1} ∑_{b=1}^{k} \binom{k}{b}\binom{n − k}{b}\binom{b}{m}(r − 2)^{b−m}(r − 1)^{n−k−b}.

This proves Proposition 1.1.

3. (c, c)-descents

In this section, we calculate the number of permutations of G_{r,n} having a fixed number of (c, c)-descents. Note that in this case, the enumeration is identical in the color order and the absolute order, since both orders satisfy

1^{[c]} < 2^{[c]} < ⋯ < n^{[c]}.

Hence, we denote: des_{c}(π) = des_{c,c}^{Clr}(π) = des_{c,c}^{Abs}(π).

We use here a recursive approach. Let π = i_{1}^{[j_{1}]} ⋯ i_{n}^{[j_{n}]} ∈ G_{r,n}. Using a map f : G_{r,n} → G_{r,n} which takes each colored digit i^{[j]} to i^{[(j+1) (mod r)]}, we are led to the following.

Observation 3.1. For each color c ∈ {0, …, r−1}, the number of colored permutations with exactly m (c, c)-descents is equal to the number of colored permutations with exactly m (0, 0)-descents.

By the above observation, it suffices to find the generating function for the number of colored permutations in G_{r,n} having (0, 0)-descents.

Let

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

In order to find a recurrence for g_{r,n}(q), we will use the following notations. Define

g_{r,n}^{+}(q) = ∑_{π∈G_{r,n}, c_{1}(π)=0} q^{des_{0}(π)},

g_{r,n}^{−}(q) = ∑_{π∈G_{r,n}, c_{1}(π)≠0} q^{des_{0}(π)}.

Note that g_{r,n}(q) = g_{r,n}^{+}(q) + g_{r,n}^{−}(q).

Let π ∈ G_{r,n}. If |π_{n}| = n, denote π = π′π_{n} and we have

des_{0}(π) = des_{0}(π′).

Otherwise, let j < n be such that |π_{j}| = n. Denote: π = π′π_{j}π′′ ∈ G_{r,n}. If π_{j} = n^{[c]} for c ≠ 0, then des_{0}(π) = des_{0}(π′) + des_{0}(π′′). If π_{j} = n, we have two cases depending on the color of π′′_{1} (the first element of π′′):

des_{0}(π) = \begin{cases}des_{0}(π′) + des_{0}(π′′) & if c_{1}(π′′) ≠ 0, \\ 1 + des_{0}(π′) + des_{0}(π′′) & otherwise. \end{cases}

Since there are no restrictions on the positions of the digits 1, 2, …, n − 1, we have the following recurrences.

Lemma 3.2. For all n ≥ 1, we have

g_{r,n}(q) = rg_{r,n−1}(q) + (r − 1) ∑_{j=1}^{n−1} \binom{n − 1}{j − 1}g_{r,j−1}(q)g_{r,n−j}(q)

+ ∑_{j=1}^{n−1} \binom{n − 1}{j − 1}g_{r,j−1}(q)(g_{r,n−j}^{−}(q) + qg_{r,n−j}^{+}(q)),

and for n ≥ 2, we have

g_{r,n}^{+}(q) = rg_{r,n−1}^{+}(q) + (r − 1) ∑_{j=2}^{n−1} \binom{n − 1}{j − 1}g_{r,j−1}^{+}(q)g_{r,n−j}(q)

+ ∑_{j=1}^{n−1} \binom{n − 1}{j − 1}g_{r,j−1}^{+}(q)(g_{r,n−j}^{−}(q) + qg_{r,n−j}^{+}(q)).

Proof. In both expressions, the first summand corresponds to the case |π_{n}| = n, the second corresponds to the case π_{j} = n^{[c]} (c ≠ 0) for some j, 1 ≤ j ≤ n−1, and the third corresponds to the case π_{j} = n for some j, 1 ≤ j ≤ n − 1. □

In order to find an explicit formula for g_{r,n}(q), we rewrite the above recurrences in terms of exponential generating functions. Define

G_{r}(x, q) = ∑_{n≥0} g_{r,n}(q)\frac{x^{n}}{n!} , G_{r}^{+}(x, q) = ∑_{n≥0} g_{r,n}^{+}(q)\frac{x^{n}}{n!} ,

and

G_{r}^{−}(x, q) = ∑_{n≥0} g_{r,n}^{−}(q)\frac{x^{n}}{n!} .

Since g_{r,n}(q) = g_{r,n}^{+}(q) + g_{r,n}^{−}(q), we have

G_{r}(x, q) = G_{r}^{+}(x, q) + G_{r}^{−}(x, q).

Moreover, for all n ≥ 1, Lemma 3.2 yields

\frac{d}{dx} (\frac{g_{r,n}(q)}{n!}x^{n}) = \frac{rg_{r,n−1}(q)}{(n − 1)!}x^{n−1}

+ (r − 1)x^{n−1} ∑_{j=0}^{n−2} \frac{g_{r,j}(q)}{j!} · \frac{g_{r,n−1−j}(q)}{(n − 1 − j)!}

+ x^{n−1} ∑_{j=0}^{n−2} \frac{g_{r,j}(q)}{j!} · \frac{g_{r,n−1−j}^{−}(q) + qg_{r,n−1−j}^{+}(q)}{(n − 1 − j)!},

and

\frac{d}{dx} (\frac{g_{r,n}^{+}(q)}{n!}x^{n}) = r\frac{g_{r,n−1}^{+}(q)}{(n − 1)!}x^{n−1}

+ (r − 1)x^{n−1} ∑_{j=1}^{n−2} \frac{g_{r,j}^{+}(q)}{j!} · \frac{g_{r,n−1−j}(q)}{(n − 1 − j)!}

+ x^{n−1} ∑_{j=0}^{n−2} \frac{g_{r,j}^{+}(q)}{j!} · \frac{g_{r,n−1−j}^{−}(q) + qg_{r,n−1−j}^{+}(q)}{(n − 1 − j)!}.

Summing over all n ≥ 1 and using the initial conditions g_{r,0}(q) = g_{r,0}^{+}(q) = g_{r,1}^{+}(q) = 1, g_{r,0}^{−}(q) = 0 and g_{r,1}^{−}(q) = r − 1, we get

G_{r}(x, q) = G_{r}^{+}(x, q) + G_{r}^{−}(x, q),
\frac{d}{dx} (G_{r}(x, q)) = (1 − q)G_{r}(x, q) + (r − 1)(G_{r}(x, q))^{2}
+ G_{r}(x, q)G_{r}^{−}(x, q) + qG_{r}(x, q)G_{r}^{+}(x, q),
\frac{d}{dx} (G_{r}^{+}(x, q)) = (1 − q)G_{r}^{+}(x, q) + (r − 1)G_{r}^{+}(x, q)G_{r}(x, q)
+ G_{r}^{+}(x, q)G_{r}^{−}(x, q) + q(G_{r}^{+}(x, q))^{2}.

Using any computer algebra package, such as Maple or Mathematica, we obtain the following result.

Theorem 3.3. The generating functions G_{r}(x, q), G_{r}^{+}(x, q) and G_{r}^{−}(x, q) are given by

G_{r}(x, q) = \frac{1 − q}{(r − 1)x(q − 1) − q + e^{(q−1)x}} ,

G_{r}^{+}(x, q) = \frac{(1 − q)(1 − (r − 1)x)}{(r − 1)x(q − 1) − q + e^{(q−1)x}} ,

G_{r}^{−}(x, q) = \frac{x(r − 1)(1 − q)}{(r − 1)x(q − 1) − q + e^{(q−1)x}} ,

respectively.

In order to obtain an explicit formula for the number of colored permutations in G_{r,n} with exactly m (0, 0)-descents, we find the coefficient of x^{n}q^{m} in G_{r}(x, q):

G_{r}(x, q) = \frac{1 − q}{e^{(q−1)x} − q} · \frac{1}{1 − \frac{(r−1)x(1−q)}{e^{(q−1)x}−q}}

= ∑_{j≥0} \frac{(r − 1)^{j}x^{j}(1 − q)^{j+1}}{(e^{(q−1)x} − q)^{j+1}}

= ∑_{j,i,k≥0}(r − 1)^{j}x^{j}(1 − q)^{j+1}\binom{j + i}{j}q^{i} \frac{(1 − q)^{k}x^{k}(i + j + 1)^{k}}{k!}

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

· q^{ℓ+i}x^{j+k} \frac{(i + j + 1)^{k}}{k!} .

Thus the coefficient of x^{n}q^{m} in G_{r}(x, q) is given by

∑_{j=0}^{n} ∑_{i=0}^{m}(−1)^{i}(r − 1)^{j}\binom{j + m − i}{j}\binom{n + 1}{i}\frac{(m − i + j + 1)^{n−j}}{(n − j)!} .

This implies that the number of colored permutations in G_{r,n} with exactly m (0, 0)-descents (or (c, c)-descents for any 0 ≤ c ≤ r − 1) is

n! ∑_{j=0}^{n} ∑_{i=0}^{m}(−1)^{i}(r − 1)^{j}\binom{j + m − i}{j}\binom{n + 1}{i}\frac{(m − i + j + 1)^{n−j}}{(n − j)!} ,

as stated in Proposition 1.3.

Acknowledgements

The authors would like to thank Ron Adin for some helpful advice.

References

[1] J. Hall, J. Liese and J. Remmel, q-Analogues of formulas counting descent pairs with prescribed tops and bottoms, preprint.

[2] J. Hall and J. Remmel, Counting descent pairs with prescribed tops and bottoms, J. Combin. Theory Ser. A 115(5) (2008), 693–725.

[3] S. Kitaev, T. Mansour and J. Remmel, Counting descents, rises, and levels, with prescribed first element, in words, Discrete Math. Theoret. Comp. Sci. 10(3) (2008), 1–22.

[4] S. Kitaev and J. Remmel, Classifying descents according to equivalence mod k, Electronic J. Combin. 13(1) (2006), Article #R64.

[5] S. Kitaev and J. Remmel, Classifying descents according to parity, Ann. Combin. 11 (2007), 173–193.

[6] P. A. MacMahon, Combinatory Analysis, Vol. 1 and 2, Cambridge Univ. Press, Cambridge, 1915 (reprinted by Chelsea, New York, 1955).

[7] P. A. MacMahon, The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer. J. Math. 35 (1913), 281–322.

Eli Bagno, The Jerusalem College of Technology, Jerusalem, Israel

E-mail address: bagnoe@jct.ac.il

David Garber, Department of Applied Mathematics, Faculty of Sciences, Holon Institute of Technology, PO Box 305, 58102 Holon, Israel

E-mail address: garber@hit.ac.il

Toufik Mansour, Department of Mathematics, University of Haifa, 31905 Haifa, Israel.

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