arXiv:0909.4009v1 [math.CO] 22 Sep 2009 ENUMERATING WREATH PRODUCTS VIA GARSIA-GESSEL BIJECTIONS RICCARDO BIAGIOLI AND JIANG ZENG Abstract. We generalize two bijections due to Garsia and Gessel to compute the generating functions of the two vector statistics (desG , maj, ℓG , col) and (desG , idesG , maj, imaj, col, icol) over the wreath product of a symmetric group by a cyclic group. Here desG , ℓG , maj, col, idesG , imajG , and icol denote the number of descents, length, major index, color weight, inverse descents, inverse major index, and inverse color weight, respectively. Our main formulas generalize and unify several known identities due to Brenti, Carlitz, Chow-Gessel, Garsia-Gessel, and Reiner on various distributions of statistics over Coxeter groups of type A and B. Contents 1. Introduction 2. Definitions and notation 3. Encoding colored sequences 4. Quotients of G(r, n) 5. The distribution of (desG , maj, ℓG , col) 6. Encoding colored biwords 7. The distribution of (desG , idesG , maj, imaj, col, icol) 8. Specializations References 1 2 5 8 12 13 15 16 18 1. Introduction Permutation statistics have a very natural setting within the theory of partitions as observed by MacMahon [17], Gordon [14], Stanley [22], Gessel [16], and Reiner [19], among others. This was made even more clear thanks to the work of Garsia and Gessel [15] who gave two remarkable bijections. The first one between sequences and pairs made of a permutation and a partition [15, §1]; the second one between bipartite partitions and triplets made of a permutation and a coupe of special partitions [15, §2]. Thanks to these two bijections they were able to give elegant computations of the generating series P X X σ∈S tdes(σ) q maj(σ) pinv(σ) un n Qn = tk e[u]p e[qu]p · · · e[q k u]p , (1.1) i [n] ! (1 − tq ) p i=0 n≥0 k≥0 The two authors are supported by the grant ANR-08-BLAN-0243-03 and by the Program P2R franco-israélien Mathématiques. 1 2 RICCARDO BIAGIOLI AND JIANG ZENG and X n≥0 X des(σ) des(σ−1 ) maj(σ) maj(σ−1 ) un t1 t2 q1 q2 (t1 ; q1 )n+1 (t2 ; q2 )n+1 σ∈Sn = X k1 ,k2 ≥0 tk11 tk22 . (u; q1 , q2 )k1 +1,k2 +1 (1.2) Here des, maj, and inv denote the number of descents, the major index, and the number of inversions over the symmetric group Sn . Extensions of the above bijections were given in [5, 6, 8, 19]. In particular, Reiner [19, 20] generalized Garsia and Gessel’s work to the hyperoctahedral group Bn , using P -partition theory. He obtained analogues of (1.1) and (1.2) for Bn and G(r, n), the wreath product of the symmetric group Sn with the cyclic group Zr (cf. [19, Corollary 7.2 and 7.3]). In this paper, we give G(r, n)-analogues of the two Garsia and Gessel bijections (cf. Proposition 3.8 and Theorem 6.4). A fundamental notion will be that of γ-compatible partitions, which generalizes that of σ-compatible partitions introduced by Garsia and Gessel in [15]. We use our bijections to give two different extensions of (1.1) and (1.2) for G(r, n), by computing the generating functions of the two vector statistics (desG , maj, ℓG , col) and (desG , idesG , maj, imaj, col, icol), whose definitions will be given in the next sections (cf. Theorem 5.1 and Theorem 7.1). The aforementioned Reiner’s results also compute similar generating functions but his definitions of the length and the major index are slightly different from ours due to a different choice of the generating set for G(r, n). In the case of the hyperoctahedral group, more details explaining differences and relations between our and Reiner’s results are given in a separate paper [9], where connections with the work [13] of Chow-Gessel are also established. The choice of our statistics is motivated by the aim to take into account the flag-major index introduced by Adin and Roichman in [1]. Indeed Theorem 5.1 unify and generalize several known results due to Brenti, Carlitz, Chow-Gessel, Gessel, and Reiner, on various distributions of statistics over Coxeter groups of type A and B. Moreover, Theorem 7.1 will allow us to give an explicit description of the generating function of the Hilbert series of some G(r, n)-invariant algebras, studied by Adin and Roichman [1], and involving the flag-major index. Clearly, if we set r = 2 in the identities given in Theorem 5.1 and Theorem 7.1, we find the analogous results for the hyperoctahedral group Bn . We point out that these identities are actually equivalent, and we show how to recover the general G(r, n)-case from the knowledge of the Bn -case. 2. Definitions and notation In this section we give some definitions, notation and results that will be used in the rest of this work. For n ∈ N we let [n] := {1, 2, . . . , n} (where [0] := ∅). Given n, m ∈ Z, n ≤ m, we let [n, m] := {n, n + 1, . . . , m}. The cardinality of a set A will be denoted either by |A| or by #A. Let P be a statement: the characteristic function χ of P is defined as χ(P ) = 1 if P is true, and 0 otherwise. As usual for n ∈ N, we let  1, if n = 0; (a; p)n := (1 − a)(1 − ap) · · · (1 − apn−1 ), if n ≥ 1. ENUMERATING WREATH PRODUCTS VIA GARSIA-GESSEL BIJECTIONS 3 Moreover, for n, m ∈ N we let (a; p, q)n,m  1,  Y :=  Y (1 − ap i−1 j−1 q if n or m are zero; ), if n, m ≥ 1. 1≤i≤n 1≤j≤m For our study we need notation for p-analogues of integers and factorials. These are defined by the following expressions [n]p : = 1 + p + p2 + . . . + pn−1 , [n]p ! : = [n]p [n − 1]p · · · [2]p [1]p , [n̂]a,p ! : = (−ap; p)n [n]p !, where [0]p ! := 1. For n = n0 + n1 + · · · + nk with n0 , . . . , nk ≥ 0 we define the p-analogue of multinomial coefficient by   [n̂]a,p ! n̂ . := [n̂0 ]a,p ![n1 ]p ! · · · [nk ]p ! n̂0 , n1 , . . . , nk a,p Finally, e[u]p := X un , [n]p ! and ê[u]a,p := n≥0 X un [n̂]a,p ! (2.1) n≥0 are a classical p-analogue and a (a, p)-analogue of the exponential function. Let Sn be the symmetric group on [n]. A permutation σ ∈ Sn will be denoted by σ = σ(1) · · · σ(n). Let r, n ∈ P. The wreath product Zr ≀ Sn of Zr by Sn is defined by G(r, n) := {(c1 , . . . , cn ; σ) | ci ∈ [0, r − 1], σ ∈ Sn }. (2.2) Any ci can be considered as the color of the corresponding entry σ(i). This is why this group is also called the group of r-colored permutations. Sometimes we will represent its elements in window notation as γ = [γ(1), . . . , γ(n)] = [σ(1)c1 , . . . , σ(n)cn ]. Sometimes we will call σ(i) the absolute value of γ(i), denoted |γ(i)|. When it is not clear from the context, we will denote ci by ci (γ). Moreover, if ci = 0, it will be omitted in the window notation of γ. We denote by n X ci , Col(γ) := (c1 , . . . , cn ) and col(γ) := i=1 the color vector and the color weight of any γ := (c1 , . . . , cn ; σ) ∈ G(r, n). For example, if γ = [41 , 3, 24 , 12 ] ∈ G(5, 4) then Col(γ) = (1, 0, 4, 2) and col(γ) = 7. The product in G(r, n) is defined as follows: (c1 , . . . , cn ; σ) · (d1 , . . . , dn ; τ ) := (d1 + cσ(1) , . . . , dn + cσ(n) ; στ ), where the product στ is from right to left as usual. 4 RICCARDO BIAGIOLI AND JIANG ZENG Clearly for a colored permutation γ = (c1 , . . . , cn ; σ) ∈ G(r, n) the inverse colored permutation is given by γ −1 = (c′1 , . . . , c′n ; σ −1 ), where  ′ ci = cσ−1 (i) , if ci = 0; (2.3) c′i = r − cσ−1 (i) , otherwise. In this paper we will use mostly a different type of inverse. We define the skew inverse permutation of γ by γ̃ −1 := (cσ−1 (1) , . . . , cσ−1 (n) ; σ −1 ). (2.4) For example, if γ = [3, 61 , 43 , 72 , 21 , 1, 5] ∈ G(4, 7) then γ̃ −1 = [6, 51 , 1, 33 , 7, 21 , 42 ], while γ −1 = [6, 53 , 1, 31 , 7, 23 , 42 ]. Note that when G(r, n) is a Coxeter group, the skew inverse is actually the inverse. The group G(r, n) is generated by the set SG := {s0 , s1 , . . . , sn−1 } where for i ∈ [n − 1] si := [1, . . . , i − 1, i + 1, i, i + 2, . . . , n] and s0 := [11 , 2, . . . , n], (2.5) with relations given by the following Dynkin-like diagram 2r s0 s1 s2 sn−2 sn−1 Figure 1. The Dynkin-like diagram of G(r, n) Definition 2.1. In all the paper we will use the following order nr−1 < . . . < n1 < . . . < 1r−1 < . . . < 11 < 0 < 1 < . . . < n (2.6) on the set {0, 1, . . . , n, 11 , . . . , n1 , . . . , 1r−1 , . . . , nr−1 } of colored integers. The following characterization of the length of γ = σ(1)c1 · · · σ(n)cn ∈ G(r, n) is well-known (see e.g., [19, 23], [4, Theorem 4.3]) X ℓG (γ) = inv(γ) + (σ(i) + ci − 1) , (2.7) ci 6=0 where the inversion number is defined by inv(γ) := |{(i, j) ∈ [n] × [n] | γ(i) > γ(j)}|. The generating function for the length is given by X pℓG (γ) = [n]p !(−p[r − 1]p ; p)n = [n̂][r−1]p ,p !. (2.8) γ∈G(r,n) The descent set of γ ∈ G(r, n) is defined by DesG (γ) := {i ∈ [0, n − 1] | γ(i) > γ(i + 1)}, (2.9) where γ(0) := 0, and its cardinality is denoted by desG (γ). Note that 0 ∈ DesG (γ) if and only if c1 (γ) > 0. ENUMERATING WREATH PRODUCTS VIA GARSIA-GESSEL BIJECTIONS 5 As usual the major index is defined to be the sum of descent positions: X maj(γ) = i, i∈DesG (γ) and the flag-major index (see [1]) is defined by fmaj(γ) := r · maj(γ) + col(γ). For example, for γ = [41 , 3, 24 , 12 ] ∈ G(5, 4) we have inv(γ) = 2, ℓG (γ) = 13, DesG (γ) = {0, 1}, desG (γ) = 2, maj(γ) = 2, and fmaj(γ) = 17. 3. Encoding colored sequences In this section we collect some notions and results that will be needed in the rest of this paper. First of all we generalize Garsia-Gessel and Reiner’s method of encoding sequences and signed sequences (see [15, §1] and [19, §2]) to colored sequences. Let Pn be the set of nondecreasing sequences of nonnegative integers (λ1 , λ2 , . . . , λn ), that is partitions of length less than or equal to n. Define by N(r,n) the set of n-tuples f = (f1c1 , . . . , fncn ) of colored integers, where fi ∈ N, and ci ∈ [0, r − 1]. We will mostly consider its subset (r,n) N0 := {(f1c1 , . . . , fncn ) | fi ∈ N, ci ∈ [0, r − 1] : if fi = 0 then ci = 0} . When it is not clear from the context, we will denote ci by ci (f ). For f = (f1c1 , . . . , fncn ) ∈ N(r,n) , we define n X fi . (3.1) max(f ) := max{fi } and |f | := i∈[n] i=1 Definition 3.1 (The colored permutation π(f )). Given a colored sequence f = (f1c1 , . . . , fncn ) ∈ (r,n) N0 , we construct the colored permutation π(f ) as follows. For ν ∈ N, we first define the sets Aν := {ici | fi = ν and ci = ci (f )}, (3.2) and arrange the entries in each nonempty “bloc” Aν in increasing order (cf. (2.6)), obtaining ↑ Aν . Then π(f ) := [↑ Aν1 , ↑ Aν2 , . . . , ↑ Aνk ] is obtained by juxtaposing the entries of the nonempty blocs ↑ Aν1 , ↑ Aν2 , . . ., where ν1 < ν2 < · · · . (4,7) Example 3.2. Let f = (42 , 41 , 1, 33 , 6, 31 , 42 ) ∈ N0 . Then A1 = {3}, A3 = {43 , 61 }, A4 = {12 , 21 , 72 }, and A6 = {5}. Hence ↑ A1 = {3}, ↑ A3 = {61 , 43 }, ↑ A4 = {72 , 21 , 12 }, ↑ A6 = {5}, and π(f ) = [↑ A1 , ↑ A3 , ↑ A4 , ↑ A6 ] = [3, 61 , 43 , 72 , 21 , 12 , 5] ∈ G(4, 7). The following equivalent characterization of the colored permutation π(f ) can be derived from Definition 3.1, and will be frequently used along the paper. (r,n) Proposition 3.3. Let f = (f1c1 , . . . , fncn ) ∈ N0 colored permutation satisfying: 1) fσ(1) ≤ fσ(2) ≤ . . . ≤ fσ(n) ; . Then π(f ) = γ = (c1 , . . . , cn ; σ) is the unique 6 RICCARDO BIAGIOLI AND JIANG ZENG 2) ci (γ) = cσ(i) (f ); 3) If fσ(i) = fσ(i+1) , then γ(i) < γ(i + 1). (r,n) Definition 3.4. Let γ = (c1 , . . . , cn ; σ) ∈ G(r, n). We say that a sequence f ∈ N0 with γ if π(f ) = γ. (r,n) We remark that if f ∈ N0 have is associated is associated with γ, then by parts 1) and 3) of Proposition 3.3 we i ∈ DesG (γ) =⇒ fσ(i) < fσ(i+1) . (3.3) (r,n) Lemma 3.5 (The partition λ(f )). Given a colored sequence f = (f1c1 , . . . , fncn ) ∈ N0 λi := fσ(i) − |{j ∈ DesG (γ) | j ≤ i − 1}| for 1 ≤ i ≤ n, , define (3.4) where π(f ) = γ = (c1 , . . . , cn ; σ). Then the sequence λ(f ) := (λ1 , . . . , λn ) is a partition. (r,n) Proof. If 0 ∈ DesG (γ) then c1 (γ) > 0. Since c1 (γ) = cσ(1) (f ) and f ∈ N0 fσ(1) > 0. Hence λ1 ≥ 0. If i > 1, , this implies that λi+1 − λi = fσ(i+1) − fσ(i) − χ(i ∈ DesG (γ)). Since f is associated with γ, if i ∈ DesG (γ) then fσ(i) < fσ(i+1) . Hence λi+1 −λi ≥ 0 and λ ∈ Pn .  (4,7) Example 3.6. Let f = (42 , 41 , 1, 33 , 6, 31 , 42 ) ∈ N0 be the sequence of Example 3.2. Then (fσ(1) , . . . , fσ(n) ) = (1, 3, 3, 4, 4, 4, 6). Since DesG (π(f )) = {1, 3}, we have λ = (1, 2, 2, 2, 2, 2, 4). Definition 3.7 (The colored sequence λγ ). Given a partition λ ∈ Pn and a colored permutation γ = (c1 , . . . , cn ; σ) ∈ G(r, n) we denote by λγ the following colored sequence n 1 ) ∈ N(r,n) . λγ := (λcσ(1) , . . . , λcσ(n) (3.5) (r,n) Proposition 3.8. The map f 7→ (π(f ), λ(f )) is a bijection between N0 over, if γ := π(f ) and λ := λ(f ) then and G(r, n) × Pn . More- max(f ) = max(λ) + desG (γ), |f | = |λ| + n desG (γ) − maj(γ). (3.6) (3.7) Proof. To see that this map is a bijection, we construct its inverse. Starting from γ = (c1 , . . . , cn ; σ) and λ in G(r, n) × Pn , we denote by µ = (µ1 , . . . , µn ) the partition µi := λi + |{j ∈ DesG (γ) | j ≤ i − 1}|. Then we define f = (f1c1 , . . . , fncn ) f := µ γ̃ −1 ∈ N(r,n) (3.8) by letting that is, for each i ∈ [n]  fi = µσ−1 (i) ci (f ) = cσ−1 (i) (γ). (3.9) Let us prove that the image of f by this map is (γ, λ). We have π(f ) = γ because γ satisfies the three conditions of Proposition 3.3: 1) since fσ(i) = µi then (fσ(1) , . . . , fσ(n) ) = µ is nondecreasing; 2) ci (f ) = cσ−1 (i) (γ) =⇒ cσ(i) (f ) = ci (γ); 3) if fσ(i) = fσ(i+1) then µi = µi+1 , and (3.8) implies that i 6∈ DesG (γ). ENUMERATING WREATH PRODUCTS VIA GARSIA-GESSEL BIJECTIONS 7 (r,n) It is clear that λ(f ) = λ. To see that f ∈ N0 , we need to show that µi = 0 implies ci (γ) = 0. If µi = 0, then by (3.8) λi = 0 and j 6∈ DesG (γ) for all j ≤ i − 1. In particular 0 is not a descent of γ. Hence c1 (γ) = . . . = ci (γ) = 0. Equation (3.6) follows from max(f ) = fσ(n) = λσ(n) + desG (γ). Since |f | − |λ| = n X |{j ∈ DesG (γ)|j ≤ i − 1}| = i=1 X (n − j) = n desG (γ) − maj(γ), j∈DesG (γ) we have Equation (3.7).  Example 3.9. This is an example of the construction in the above proof. Let (γ, λ) be the pair ([51 , 31 , 1, 22 , 42 ], (0, 2, 2, 3, 3)) ∈ G(3, 5) × P5 . We find DesG (γ) = {0, 1, 3, 4}, so µ = (1, 4, 4, 6, 7). Now γ̃ −1 = [3, 42 , 21 , 52 , 11 ] and f := µγ̃ −1 (3,5) = (4, 62 , 41 , 72 , 1) ∈ N0 . Definition 3.10. Analogously to the case of the symmetric group [15, (2.12)], we say that a partition λ is γ-compatible if λi < λi+1 for all i ∈ DesG (γ), where we let λ0 := 0. Notice that if λ is γ-compatible and 0 ∈ DesG (γ), then λ1 ≥ 1. The following result gives a relation between γ-compatible partitions and sequences associated with γ, which will be used in the proof of Theorem 7.1. Proposition 3.11. Let µ ∈ Pn , and γ = (c1 , . . . , cn ; σ) ∈ G(r, n). Then µ is γ-compatible ⇐⇒ π(µγ̃ −1 ) = γ. −1 Proof. To simplify the notation, as in (3.9), we let f := µγ̃ within this proof. Suppose that µ is γ-compatible. We show that γ verifies all three conditions of Proposition 3.3. The first one is clear since µi = fσ(i) , and µ is a partition. Secondly, by definition (see (2.4)) cσ−1 (i) (γ) = ci (γ̃ −1 ). Hence ci (γ) = cσ(i) (γ̃ −1 ) = cσ(i) (f ), where the last equality follows from Definition 3.7. Now suppose that fσ(i) = fσ(i+1) , that is µi = µi+1 . The γ-compatibility of µ implies that γ(i) < γ(i + 1), so the third condition. Conversely, if π(f ) = γ then condition 3) of Proposition 3.3 implies that µ is γ-compatible, since µi = fσ(i) , for every i ∈ [n]. In the case 0 ∈ DesG (γ), we let σ(0) = 0, and f0 = 0, as in Definition 3.10.  The next result will be a basic tool in the proofs of Theorem 5.1 and Theorem 7.1. Proposition 3.12. Let γ ∈ G(r, n). Then X (r,n) f ∈N0 |π(f )=γ tmax(f ) q max(f )·n−|f | = tdesG (γ) q maj(γ) . (t; q)n (3.10) 8 RICCARDO BIAGIOLI AND JIANG ZENG Proof. It follows from the bijection in Proposition 3.8, (3.6), and (3.7) that X X tmax(f ) q |f | = tmax(λ)+desG (γ) q |λ|+n desG (γ)−maj(γ) (r,n) f ∈N0 λ∈Pn |π(f )=γ = tdesG (γ) q n desG (γ)−maj(γ) . (tq; q)n By replacing q by q −1 and t by tq n in (3.11) we get the result. (3.11)  Setting r = 2 we have G(2, n) = Bn the hyperoctahedral group or group of signed permutations. As usual, the weight color will be denoted by neg, the number of negative entries, and the descent set by DesB . There is a natural projection of G(r, n) into Bn for every r ≥ 2, which “forgets the colors”. Definition 3.13 (Projection of G(r, n) onto Bn ). We define φ : G(r, n) → Bn by sending γ = (c1 , . . . , cn ; σ) to  0 , if ci = 0; φ(γ) = (ĉ1 , . . . , ĉn ; σ), where ĉi := 1 , if ci ≥ 1. It is easy to see that φ is not a group homomorphism, and that φ(γ −1 ) = φ(γ)−1 . The following lemma, relating the statistics of G(r, n) with those of Bn , refines a result of Reiner [19, §7]. The proof is similar. Lemma 3.14. We have 1) DesG (γ) = DesB (φ(γ)); 2) DesG (γ −1 ) = DesB (φ(γ)−1 ); 3) For any γ̂ ∈ Bn we have X pℓG (γ) acol(γ) = pℓB (γ̂) (a[r − 1]ap )neg(γ̂) . γ∈G(r,n)|φ(γ)=γ̂ It is clear that for the skew inverse we have φ(γ −1 ) = φ(γ̃ −1 ). (3.12) The next result follows from Proposition 3.12 and part 1) of Lemma 3.14. Corollary 3.15. Let γ ∈ G(r, n). Then X tmax(f ) q max(f )·n−|f | = (r,n) f ∈N0 |π(f )=φ(γ) X tmax(f ) q max(f )·n−|f | . (3.13) (r,n) f ∈N0 |π(f )=γ 4. Quotients of G(r, n) There exists a well-known decomposition of any Coxeter group as the product of a quotient by a parabolic subgroup, see for example [10, Proposition 2.4.4]. The following analogue result for G(r, n) is probably known. Due to the lack of an adequate reference, we provide a proof. Let SG := {s0 , . . . , sn−1 } be the generating set of G(r, n) defined in (2.5). For J ⊆ [0, n − 1] we let GJ := hsi | i ∈ Ji be the parabolic subgroup generated by J. ENUMERATING WREATH PRODUCTS VIA GARSIA-GESSEL BIJECTIONS 9 Proposition 4.1. For J ⊆ [0, n − 1] let GJ be the parabolic subgroup of G(r, n) generated by J, and GJ := {τ ∈ G(r, n) | DesG (γ) ⊆ [0, n − 1] \ J}, the (right) quotient. Then every γ ∈ G(r, n) has a unique factorization γ = τ · δ, with τ ∈ GJ and δ ∈ GJ , such that ℓG (γ) = ℓG (τ ) + ℓG (δ) and col(γ) = col(τ ) + col(δ). (4.1) Proof. We let [0, n − 1] \ J := {d1 , . . . , dk }, where d1 < . . . < dk . We have two cases to consider. a) Suppose 0 6∈ J, hence d1 = 0. This means that GJ ≃ S[1, d2 ] × S[d2 + 1, d3 ] × . . . × S[dk + 1, n], and GJ = {τ ∈ G(r, n) | DesG (τ ) ⊆ {0, d2 , . . . , dk }}, where S[a, b] denotes the symmetric group of the set [a, b]. We can write any element γ ∈ G(r, n) as juxtaposition of k words γ = γ1 | γ2 | . . . | γk, (4.2) where γ i := [γ(di + 1), . . . , γ(di+1 )], for i = 1, . . . , k, and dk+1 := n. We define τ :=↑ γ 1 · · · ↑ γ k and δ = δ1 · · · δk , ↑ γi where is the increasing arrangement of the letters in the unique permutation in S[di + 1, di+1 ] such that (↑ γ i ) · δi = γ i , for γi, (4.3) (cf. Definition 3.1), and δi is i ∈ [k]. (4.4) For example, suppose γ = [5, 22 , 41 , 3, 11 , 62 , 8, 72 ] ∈ G(3, 8) and J = {1, 2, 4, 5, 7}. We have d1 = 0, d2 = 3, d3 = 6, and γ 1 | γ 2 | γ 3 = [5, 22 , 41 | 3, 11 , 62 | 8, 72 ]. Then τ = [41 , 22 , 5 | 62 , 13 , 3 | 72 , 8], and δ = [3, 2, 1 | 6, 5, 4 | 8, 7]. Clearly, from (4.4) and definition of product follows that γ = τ · δ. This decomposition is unique due to the uniqueness of τ and δ. Since δ ∈ Sn , and τ has the same colored entries of γ we have X X (σ(i) + ci − 1) = (|τ (i)| + ci − 1), (4.5) ci (γ)6=0 ci (τ )6=0 where recall that |τ (i)| stands for the absolute value of τ (i). Therefore col(γ) = col(τ ) + col(δ). For i < j, we denote inv(γ i | γ j ) := |{(a, b) | a ∈ γ i , b ∈ γ j }| the number of inversions between blocs. Clearly we have X X inv(γ) = inv(γ i ) + inv(γ i | γ j ). (4.6) 1≤i≤k 1≤i<j≤k Note that inv(↑ γ i ) = inv(δi | δj ) = 0, inv(γ i ) = inv(δi ), and inv(γ i | γ j ) = inv(↑ γ i |↑ γ j ), (4.7) for 1 ≤ i ≤ k and 1 ≤ i < j ≤ k. Thus by (4.6) we have inv(γ) = inv(τ ) + inv(δ). This, (4.5), and the definition (2.7) imply ℓG (γ) = ℓG (τ ) + ℓG (δ). 10 RICCARDO BIAGIOLI AND JIANG ZENG b) Now suppose 0 ∈ J, hence d1 > 0. Then GJ ≃ G(r, d1 ) × S[d2 + 1, d3 ] × . . . × S[dk + 1, n], and GJ = {τ ∈ G(r, n) | DesG (τ ) ⊆ {d1 , d2 , . . . , dk }}, If γ = [σ(1)c1 , . . . , σ(n)cn ] ∈ G(r, n), we let τ :=↑ σ 1 ↑ γ 2 · · · ↑ γ k , where ↑ γ j is defined as in (4.2), and ↑ σ 1 is the increasing arrangement of the absolute values of the entries in γ 1 . We define δ1 ∈ G(r, d1 ) as the unique colored permutation such that γ 1 =↑ σ 1 · δ1 and δ2 , . . . , δk as in (4.3). For example, if γ = [5, 22 , 41 , 3, 11 , 62 ] ∈ G(3, 6), and [0, 5] \ J = {0, 3}, then τ = [2, 4, 5 | 62 , 13 , 3] and δ = [3, 12 , 21 | 6, 5, 4]. As before we have γ = τ · δ, with τ ∈ GJ and δ ∈ GJ , and the uniqueness of the decomposition. Since 0 6∈ DesG (τ ) and ↑ σ 1 is an increasing sequence, all entries in ↑ σ 1 are positive. Notice that δ1 is an order and color preserving reduction of γ 1 . cd cd More precisely, if γ 1 = [ac11 , . . . ad11 ] then δ1 = [bc11 , . . . bd11 ] ∈ G(r, d1 ), and the two corresponding absolute value sequences are ordered in the same way. In the above example we have γ 1 = [5, 22 , 41 ] and δ1 = [3, 12 , 21 ]. From this and the definitions of τ and δ, it follows that col(γ) = col(↑ γ 2 | · · · |↑ γ k ) + col(δ1 ) = col(τ ) + col(δ). Since the colors are preserved by the decomposition, the equation ℓG (γ) = ℓG (τ ) + ℓG (δ), is equivalent to X X X inv(γ) + σ(i) = inv(τ ) + |τ (i)| + inv(δ) + |δ(i)|. (4.8) ci (γ)6=0 ci (τ )6=0 ci (δ)6=0 For i > 2 all equations in (4.7) hold also in this case. However the last of those fails for the blocs γ 1 and ↑ γ 1 . So we can proceed as in case a) for all entries except for the colored entries of γ 1 . So let us consider ci 6= 0, with σ(i)ci ∈ γ 1 , and σ(i) = τ (j) with j ∈ [d1 ]. Since ↑ γ 1 is an order and color preserving reduction of γ 1 , we have |δ(i)| = j. Hence any colored entry σ(i)ci contributes σ(i) on the LHS of (4.8), but only j on the RHS. It suffices to show that this difference σ(i) − j is balanced by the extra inversions created by τ (j) = σ(i) in τ , namely by inv(τ (j) |↑ γ 2 · · · ↑ γ k ) − inv(γ(i) | γ 2 · · · γ k ). Note that inv(τ (j) |↑ γ 2 · · · ↑ γ k ) = inv(σ(i) | γ 2 · · · γ k ). From this and the definition of the order (2.6), the above difference is equal to the number of elements in γ 2 . . . γ k which are smaller in absolute value than σ(i). This number is equal to σ(i) − j since ↑ γ 1 is an increasing sequence and σ(i) is the entry in position j of τ . The proof is now completed.  (r,n) Definition 4.2. Let f = (f1c1 , . . . , fncn ) ∈ N0 Definition 3.1). We define inv(f ) := ℓG (π(f )) and π(f ) the associated colored permutation (cf. and col(f ) := col(π(f )). (4.9) ENUMERATING WREATH PRODUCTS VIA GARSIA-GESSEL BIJECTIONS 11 Let n = (n0 , n1 , . . . , nk ) be a composition of n, i.e., ni ∈ N and n0 + · · · + nk = n. We let (r,n) N0 (r,n) (n) := {f ∈ N0 | #{i : fi = j} = nj }. Lemma 4.3. If n = (n0 , n1 , . . . , nk ) is a composition of n, then   X n̂ inv(f ) col(f ) p a = . n̂0 , n1 , . . . , nk a[r−1]ap ,p (r,n) f ∈N0 (4.10) (n) (r,n) Proof. We recall that for any f ∈ N0 the descents of π(f ) can occur only between two different blocs (see (3.2)). This implies that the restriction of the map f 7→ π(f ) induces a bijection between (r,n) N0 (n) and the quotient associated to J := [0, n − 1] \ {n0 , n0 + n1 , . . . , n0 + . . . + nk−1 }, namely (r,n) N0 (n) ←→ GJ = {γ ∈ G(r, n) | DesG (γ) ⊆ {n0 , n0 + n1 , . . . , n0 + . . . + nk−1 }} . From (4.11) and (4.9) it follows that X (r,n) f ∈N0 pinv(f ) acol(f ) = X (4.11) pℓG (τ ) acol(τ ) . τ ∈GJ (n) Since the parabolic subgroup GJ is isomorphic to G(r, n0 ) × Sn1 × . . . × Snk , from Proposition 4.1 we derive X X X pℓG (γ) acol(γ) = pℓG (τ ) acol(τ ) · pℓG (σ) acol(σ) . σ∈GJ τ ∈GJ γ∈G(r,n) Hence X τ ∈GJ ℓG (γ) acol(γ) γ∈G(r,n) p P P ℓG (σ) · · · ℓG (σ) acol(σ) · σ∈Snk σ∈G(r,n0 ) p σ∈Sn1 p P pℓG (τ ) acol(τ ) = P pℓG (σ) . (4.12) P To compute γ∈G(r,n) pℓG (g) acol(g) we use again the decomposition of Proposition 4.1. This time we take the maximal parabolic subgroup generated by J0 := [1, n − 1]. It is easy to see that GJ0 = {τ ∈ G(r, n) | τ (1) < . . . < τ (n)} and GJ0 = Sn . Hence X X X pℓG (γ) acol(γ) = pℓG (σ) . pℓG (τ ) acol(τ ) · σ∈Sn τ ∈GJ0 γ∈G(r,n) P pℓG (σ) = [n]p !. Denote the first factor It is well known (see (2.8)) that the second factor is σ∈Sn P ℓ (τ ) col(τ ) by An (p, a) := τ ∈GJ0 p G a . Since the position of n in τ ∈ GJ0 can only be the first if its color is bigger than 0 or the last if it is 0, we see that An (p, a) = (1 + apn [r − 1]ap ) · An−1 (p, a), with A0 (p, a) := 1. By induction we get An (p, a) = n Y (1 + api [r − 1]ap ), i=1 therefore X γ∈G(r,n) pℓG (γ) acol(γ) = [n]p ! · n Y (1 + api [r − 1]ap ). (4.13) i=1 By substituting the above results into (4.12) we obtain (4.10).  12 RICCARDO BIAGIOLI AND JIANG ZENG Note that (4.13) can be also derived from part 3) of Proposition 3.14 together with [11, Proposition 3.3]. 5. The distribution of (desG , maj, ℓG , col) Reiner [19, Theorem 7.2] computed the generating function of a triple of statistics (dR , majR , invR ) of “type” number of descents, major index, and length. We refer the reader to his paper for the precise definitions. Reiner’s result and Theorem 5.1 impliy that the equidistributions of the pairs (dR , invR ) and (desG , ℓG ) are the same. However, the tri-variate distributions of (dR , majR , invR ) and (desG , maj, ℓG ) are different. In this section, by using our encoding, the tools developed in § 3, and Lemma 4.3, we compute the generating function of (desG , maj, ℓG , col) and obtain the following identity. Theorem 5.1. We have X un (t; q)n+1 [n̂]a[r−1]ap ,p ! n≥0 X t desG (γ) maj(γ) ℓG (γ) col(γ) q p a = X t k e[q i u]p · ê[q k u]a[r−1]ap ,p . i=0 k≥0 γ∈G(r,n) k−1 Y (5.1) Proof. The proof consists in computing in two different ways the series X tmax(f ) q max(f )·n−|f | pinv(f ) acol(f ) . (r,n) f ∈N0 First, by using the formula (1 − t) X a≤k tk = k≥0 X (a≤k − a≤k−1 )tk = k≥0 k≥0 (r,n) f ∈N0 By Lemma 4.3 we can write the second sum as X X q k·n−|f |pinv(f ) acol(f ) = (r,n) qk n0 +···+nk =n |max(f )≤k X = ak tk , (5.2) k≥0 where a≤k = a0 + · · · + ak , we derive immediately X X tmax(f ) q max(f )·n−|f | pinv(f ) acol(f ) = (1 − tq n ) tk f ∈N0 X n0 +···+nk =n (r,n) f ∈N0 P X i ni − P q kn−|f | pinv(f ) acol(f ) . |max(f )≤k i X ini (r,n) f ∈N0  n̂ n̂0 , n1 , . . . , nk  pinv(f ) acol(f ) (n) q P i ni (k−i) a[r−1]ap ,p which is equal to the coefficient of un in e[u]p e[qu]p . . . ê[q k u]a[r−1]ap ,p × [n̂]a[r−1]ap ,p !. Thus we obtain X n≥0 un [n̂]a[r−1]ap ,p !(1 − tq n ) X tmax(f ) q max(f )·n−|f | pinv(f ) acol(f ) (r,n) f ∈N0 = X k≥0 tk e[u]p e[qu]p · · · e[q k−1 u]p ê[q k u]a[r−1]ap ,p . , ENUMERATING WREATH PRODUCTS VIA GARSIA-GESSEL BIJECTIONS On the other hand, by using Lemma 3.12 and (4.9), we obtain X X tmax(f ) q max(f )·n−|f | pinv(f ) acol(f ) = pℓG (γ) acol(γ) (r,n) γ∈G(r,n) f ∈N0 = X X (r,n) f ∈N0 tmax(f ) q max(f )·n−|f | |π(f )=γ tdesG (γ) q maj(γ) pℓG (γ) acol(γ) γ∈G(r,n) 13 (t; q)n . By comparing the above two formulas the result follows.  Remark 5.2. Note that in the case r = 2, we obtain the corresponding identity for Bn . Conversely, starting from Equation (5.1) with r = 2, thanks to Proposition 3.14 we can recover Equation (5.1) for general r, by the substitution a ← a[r − 1]ap . Therefore we can say that the two identities are equivalent. In [9] we give an independent proof of Theorem 5.1 for r = 2. 6. Encoding colored biwords In this paragraph we are going to show a result which will be fundamental in the proof of Theorem 7.1. It generalizes a well-known bijection of Garsia and Gessel concerning bipartite partitions [15, Theorem 2.1]. For other extensions of this bijection see [5, 6, 8, 19].
(r,n) g ,...,g
Definition 6.1. We define B(r, n) to be the set of colored biwords fg = f c11 ,...,fncn ∈ Pn × N0 n 1 satisfying the following condition:  ci+1 fi 6= fi+1 , then fici < fi+1 ; if gi = gi+1 and (6.1) fi = fi+1 , then ci = 0 ⇒ ci+1 = 0, where i ≥ 0, and by convention g0 := 0 and f0 := 0. Remark 6.2. In other words, if gi = gi+1 and fi = fi+1 , with ci 6= 0, there are no restrictions on the color of fi+1 . Note that, in the case gi = 0 then condition (6.1) implies ci (f ) = 0. Example 6.3. The followings are three elements of B(3, 4)       1 1 3 3 1 1 3 3 1 1 3 3 , , , 42 41 62 0 41 42 62 0 41 4 62 0 while   1 1 3 3 6∈ B(3, 4). 4 41 62 0 Theorem 6.4. There exists a bijection   g ϕ −→ (γ, λ, µ), f between the set of colored biwords B(r, n) and the triplets (γ, λ, µ), where i) γ ∈ G(r, n), ii) λ is a partition γ̃ −1 -compatible. iii) µ is a partition γ-compatible. 14 RICCARDO BIAGIOLI AND JIANG ZENG (r,n) Proof. For g = (g1 , . . . , gn ) ∈ Pn and f = (f1c1 , . . . , fncn ) ∈ N0 γ := π(f ) := (c1 , . . . , cn ; σ), λ := g , we define ϕ( g
f ) = (γ, λ, µ) by and µ := (fσ(1) , . . . , fσ(n) ). (6.2) First of all, we have to show that the triplet (γ, λ, µ) satisfies the above three conditions. To simplify the notation we let c̃i := ci (γ̃ −1 ), within this proof. The condition i) is clear. To check that λ is γ̃ −1 -compatible, we need to show that λi < λi+1 −1 ), then c̃ > 0, and so γ = [. . . , 1c̃1 , . . .]. Since π(f ) = γ for i ∈ DesG (γ̃ −1 ). If i = 0 ∈ Des G (γ̃ 1
this implies c1 (f ) > 0. Since fg ∈ B(r, n), Remark 6.2 implies λ1 = g1 > 0. Now, let i > 1 be a descent of γ̃ −1 . We have three cases to consider. a) σ −1 (i) > σ −1 (i + 1) and c̃i = c̃i+1 = 0. In this case the window notation of γ will be of the form γ = [. . . , (i + 1), . . . , i, . . .].
Since π(f ) = γ we have fi+1 < fi . Now fg ∈ B(r, n) and so this implies gi < gi+1 . b) σ −1 (i) > σ −1 (i + 1), c̃i = 0, and c̃i+1 > 0. In this case γ = [. . . , (i + 1)c̃i+1 , . . . , i, . . .]. c̃ i+1 Hence fi+1 ≤ fi . In both cases, equal or strictly smaller, we have fi+1 < fi . Since g
∈ B(r, n) this implies g < g . i i+1 f c) σ −1 (i) < σ −1 (i + 1), c̃i ≥ 0, and c̃i+1 > 0. In this case γ = [. . . , ic̃i , . . . , (i + 1)c̃i+1 , . . .].
c̃i+1 Hence fi < fi+1 . Moreover fi+1 < fic̃i . Since fg ∈ B(r, n) this implies once again gi < gi+1 . Thus part ii) is checked. Condition iii) holds, since µ is clearly γ-compatible in view of (3.3)). By construction the map ϕ is clearly injective. Since any triplet (γ, λ, µ) satisfying the above
−1 three conditions is equal to ϕ( fg ) with g := λ and f := µγ̃ (see Proposition 3.11), to show
that the map is surjective, it suffices to prove that fg ∈ B(r, n). Hence we need to check the condition (6.1). So suppose gi = gi+1 . Since g is γ̃ −1 -compatible, by definition γ̃ −1 (i) < γ̃ −1 (i + 1), so either 1) σ −1 (i) < σ −1 (i + 1), with c̃i ≥ 0 and c̃i+1 = 0, or 2) σ −1 (i) > σ −1 (i + 1), with c̃i > 0 and c̃i+1 ≥ 0. In the first case, since µ is a nondecreasing sequence, we have fi = µσ−1 (i) ≤ µσ−1 (i+1) = fi+1 . As c̃i+1 = 0 we have fic̃i ≤ fi+1 , and condition (6.1) follows. c̃i+1 In the second case we obtain fi ≥ fi+1 . If fi > fi+1 then fic̃i < fi+1 . Otherwise fi = fi+1 and condition (6.1) holds since c̃i > 0.  Example 6.5. For r = 4 and n = 7 we have  1 3 2 1      γ = [3, 6 , 4 , 7 , 2 , 1, 5], g 0 1 1 3 3 4 5 ϕ = −−→ λ = (0, 1, 1, 3, 3, 4, 5),  4 41 1 33 6 31 42 f µ = (1, 3, 3, 4, 4, 4, 6). We find γ̃ −1 = [6, 51 , 1, 33 , 7, 21 , 42 ], λγ = (1, 41 , 33 , 52 , 11 , 0, 3), and µγ̃ −1 f . Note that π(λγ ) = γ̃ −1 , and π(µγ̃ ) = γ. −1 = (4, 41 , 1, 33 , 6, 31 , 42 ) = ENUMERATING WREATH PRODUCTS VIA GARSIA-GESSEL BIJECTIONS 15
Remark 6.6. It is clear that to each biwords fg ∈ B(r, n), we can associate the multiset of o n gi
ci of its columns. This multiset can be decomposed into r-disjoint multisets of total f i i∈[n] cardinality n, depending on the colors of fi :    r−1  [  gi  gi | gi ≥ 0, fi ≥ 0 ∪ | gi > 0, fi > 0 . fi fih h=1 o (h) i
nij Conversely given such a multiset , where nij (h) is the multiplicity of the jh 0≤h≤r−1
nij i
column j h , there exist n (1),...,n (r−1) biwords in B(r, n) corresponding to it, where nij := ij ij Pr−1 n (h) is the number of colored entries. ij h=1 n 7. The distribution of (desG , idesG , maj, imaj, col, icol) In this section we compute the distribution of the vector statistic (desG , idesG , maj, imaj, col, icol) over the set of colored permutations G(r, n), and obtain the following identity. Theorem 7.1. We have X un (t1 ; q1 )n+1 (t2 ; q2 )n+1 n≥0 X desG (γ) desG (γ −1 ) maj(γ) maj(γ −1 ) col(γ) col(γ −1 ) t2 q1 q2 a b (7.1) tk11 tk22 . (u; q1 , q2 )k1 +1,k2 +1 (ab[r − 1]a,b u; q1 , q2 )k1 ,k2 (7.2) t1 γ∈G(r,n) = X k1 ,k2 ≥0 where [r − 1]a,b := ar−1 −br−1 . a−b Proof. We will count in two ways the expression X max(f ) max(g) n max(f )−|f | n max(g)−|g| col(f ) col(f −1 ) t1 t2 q1 q2 a b , g (f )∈B(r,n) (7.3) where we let col(f −1 ) := col(π(f )−1 ). As before, by using (5.2), first rewrite the above sum as X X nk −|f | nk2 −|g| col(f ) col(f −1 ) (1 − t1 q1n )(1 − t2 q2n ) tk11 tk22 q1 1 q2 a b . g k1 ,k2 ≥0 (f )∈B(r,n) max(f )≤k1 ,max(g)≤k2 P P By writing the exponents of q1 (resp. q2 ) as s (k1 − |fs |) (resp. t (k2 − |gt |)) we derive from Remark 6.6 that the sum X nk −|f | nk2 −|g| col(f ) col(f −1 ) q1 1 q2 a b g ∈B(r,n) (f ) max(f )≤k1 ,max(g)≤k2 16 RICCARDO BIAGIOLI AND JIANG ZENG is equal to the coefficient of un in the expansion of X Y (uq1i q2j )nij (0) 0≤i≤k1 0≤j≤k2 nij (0)≥0 X Y × nij ≥0 nij (1)+...+nij (r−1)=nij 0≤i≤k1 −1 0≤j≤k2 −1 1 Y = 1 − uq1i q2j 0≤i≤k1 0≤j≤k2 1− 0≤i≤k1 0≤j≤k2 = Y 0≤i≤k1 −1 0≤j≤k2 −1 1 Y = uq1i q2j X   r−1 Y nij (uah br−h q1i q2j )nij (h) nij (1), . . . , nij (r − 1) h=1 nij X  ubr (a/b + · · · + (a/b)r−1 )q1i q2j (7.4) nij ≥0 1 Y 0≤i≤k1 −1 0≤j≤k2 −1 1 − ab[r − 1]a,b uq1i q2j 1 1 . (u; q1 , q2 )k1 +1,k2 +1 (ab[r − 1]a,b u; q1 , q2 )k1 ,k2 Finally, the sum (7.3) is equal to the coefficient of un in (1 − t1 q1n )(1 − t2 q2n ) X k1 ,k2 ≥0 tk11 tk22 . (u; q1 , q2 )k1 +1,k2 +1 (ab[r − 1]a,b u; q1 , q2 )k1 ,k2 (7.5) On the other hand, from Theorem 6.4, and Proposition 3.11 the sum (7.3) is equal to X X X max(λ) n max(λ)−|λ| col(γ −1 ) max(µ) n max(µ)−|µ| col(γ) t2 q2 b t1 q1 a γ∈G(r,n) = µ∈Pn −1 π(µγ̃ )=γ X λ∈Pn π(λγ )=γ̃ −1 X max(f ) n max(f )−|f | col(γ) q1 a t1 γ∈G(r,n) f ∈N(r,n) |π(f )=γ = X γ∈G(r,n) X g∈N(r,n) |π(g)=γ̃ −1 desG (γ) maj(γ) col(γ) desG (γ −1 ) maj(γ −1 ) col(γ −1 ) t2 q2 b q1 a t1 (t1 ; q1 )n max(g) n max(g)−|g| col(γ −1 ) q2 b t2 (t2 ; q2 )n , where the last equality follows from Proposition 3.12, (3.12), and Corollary 3.15. Finally, comparing this expression with (7.5) we get the theorem.  Remark 7.2. As Equation (5.1), Equation (7.1) is also equivalent to the case of r = 2. Since col(γ −1 ) = nr − col(γ), Equation (7.1) is clearly equivalent to the b = 1 case. Now, we can recover the general r-case from the r = 2 case, via the substitution a ← a[r − 1]a and Lemma 3.14. 8. Specializations In this section we consider four specializations of Identity (5.1) giving all possible distributions of pair of statistics. In particular we get generalizations of four classical results dues to Carlitz, Brenti, Reiner and Gessel-Roselle for the symmetric and hyperoctahedral group. Finally show a relation between Theorem 7.1 and a result of Adin-Roichman. ENUMERATING WREATH PRODUCTS VIA GARSIA-GESSEL BIJECTIONS 17 Letting p = 1 and substituting u by ([r]a )u in (5.1), then extracting the coefficient of un /n! yields a G(r, n) analogue of a result of Chow-Gessel [13, Equation (26)]: P desG (γ) q maj(γ) acol(γ) X γ∈G(r,n) t = ([k + 1]q + a[r − 1]a [k]q )n tk . (8.1) (t; q)n+1 k≥0 Letting q ← q r , p = 1, a = q in (8.1) yields a formula for the distribution of descents and flag-major index over G(r, n). Proposition 8.1 (Carlitz’s identity for G(r, n)). Let r, n ∈ P. Then P desG (γ) q fmaj(γ) X γ∈G(r,n) t = tk [rk + 1]nq . (t; q r )n+1 (8.2) k≥0 The above formula gives a nice generalization of two identities of Carlitz over the symmetric group, and of Chow-Gessel over the hyperoctahedral group. Moreover it gives a q-analogue of [23, Theorem 17] on the Eulerian polynomials of type G(r, n), due to Steingrı́msson. The distribution of descents and length has been computed by Reiner [21] for finite and affine Coxeter groups. We extend his results to wreath products as follows. Proposition 8.2 (Reiner identity for G(r, n)). Let r, n ∈ P. Then X X tdesG (γ) pℓG (γ) n≥0 γ∈G(r,n) un [n̂][r−1]p ,p ! = (1 − t)ê[(1 − t)u][r−1]p ,p . 1 − te[(1 − t)u]p (8.3) It easily follows from Equation (5.1) for a = q = 1 and by letting u ← (1 − t)u. The distribution of descent and number of negative entries has been computed by Brenti [11]. For p = q = 1, u ← u[r]a (1 − t) in Equation (5.1), we obtain the following generalization. Proposition 8.3 (Brenti identity for G(r, n)). X X un (1 − t)e(u(1 − t)) tdesG (γ) acol(γ) = . n! 1 − te((1 + a[r − 1]a )u(1 − t)) (8.4) n≥0 γ∈G(r,n) To compute the generating function of major index and length we proceed as follows. Setting a = 1 in equation (5.1) yields X n≥0 un (t; q)n+1 [n̂][r−1]p ,p ! X γ∈G(r,n) t desG (γ) maj(γ) ℓG (γ) q p = X k≥0 t k k−1 Y e[q i u]p · ê[q k u][r−1]p ,p . (8.5) i=0 By multiplying both sides of (8.5) by (1 − t), and then by sending t → 1 we obtain Y X X un = e[q i u]p . q maj(γ) pℓG (γ) (q; q)n [n̂][r−1]p ,p ! n≥0 γ∈G(r,n) i≥0 Q Replacing u by u/(1 − p) and applying q-binomial formula e[u/(1 − p)]p = j≥0 1−p1 j u we get the following G(r, n)-analogue of an identity of Gessel-Roselle (see [16, Theorem 8.5] and the historical note after Theorem 4.3 in [3]): 18 RICCARDO BIAGIOLI AND JIANG ZENG Proposition 8.4 (Gessel-Roselle identity for G(r, n)). P maj(γ) pℓG (γ) X γ∈G(r,n) q n≥0 where (u; p, q)∞,∞: = Y (q; q)n (−p[r − 1]p ; p)n (p; p)n un = 1 , (u; p, q)∞,∞ (8.6) (1 − upi q j ). i,j≥0 By substitution q1 ← q1r , q2 ← q2r , a ← q1 , and b ← q2 , by multiplying both sizes of (7.1) by (1 − t1 )(1 − t2 ) and by letting t1 → 1 and t2 → 1 we obtain Proposition 8.5 (Adin-Roichman identity for G(r, n)). We have X X 1 un fmaj(γ) fmaj(γ −1 ) q1 q2 = . r r r r r r (q1 ; q1 )n (q2 ; q2 )n (u; q1 , q2 )∞,∞ (q1 q2 [r − 1]q1 ,q2 u; q1r , q2r )∞,∞ n≥0 γ∈G(r,n) Note that this identity gives an explicit formula for the generating function of the Hilbert series of the diagonal invariant algebra DIA, studied by Adin and Roichman in [1, Theorem 4.1]. This identity and the previous one (8.6), coincide in the case of the symmetric group, that is for r = 1, while in the general case give rise to two different natural extensions of Gessel-Roselle identity for the symmetric group. References [1] R. M. Adin and Y. Roichman, The Flag Major Index and Group Actions on Polynomial Rings, Europ. J. Combinatorics, 22 (2001), 431-446. [2] R. M. Adin, F. Brenti, Y. Roichman, Descent numbers and major indices for the hyperoctahedral group, Adv. in Appl. Math., 27 (2001), 210–224. [3] R. M. Adin, I. Gessel and Y. Roichman, Signed Mahonians, J. Combin. Theory Ser. A 109 (2005), no. 1, 25–43. [4] E. Bagno, Euler-Mahonian parameter on colored permutation groups, Sém. Loth. Combin., B51f (2004), 16 pp. [5] F. Bergeron and R. Biagioli, Tensorial square of the hyperoctahedral group coinvariant space, Electron. J. Combin., 13 (2006), R38. [6] F. Bergeron and F. Lamontagne, Decomposition of the diagonal action of Sn on the coinvariant space of Sn × Sn , Sém. Lothar. Combin. 52 (2004/07), Art. B52e, 24 pp. [7] R. Biagioli, Equidistribution of negative statistics and quotients of Coxeter groups of type B and D, Adv. in Appl. Math., 41 (2008), no. 3, 378-394. [8] R. Biagioli and F. Caselli, Invariant algebras and major indices for classical Weyl groups, Proc. Lond. Math. Soc., 88 (2004), 603-631. [9] R. Biagioli and J. Zeng, Remarks on some analogues of Carlitz’s identity, preprint, 2009. [10] A. Björner and F. Brenti, Combinatorics of Coxeter Groups, G.T.M. 231, Springer-Verlag, New York, 2005. [11] F. Brenti, q-Eulerian polynomials arising from Coxeter groups, European J. Combin., 15 (1994), no. 5, 417–441. [12] L. Carlitz, A combinatorial property of q-Eulerian numbers, Amer. Monthly, 82 (1975), 51–54. [13] C.-O. Chow and I. M. Gessel, On the descent numbers and major indices for the hyperoctahedral group, Adv. in Appl. Math., 38 (2007), 275–301. [14] B. Gordon, Two theorems on multipartite partitions, J. London Math. Soc. 38 1963 459–464. [15] A. M. Garsia and I. Gessel, Permutation statistics and partitions, Adv. Math., 31 (1979), 288–305. [16] I. Gessel, Generating functions and enumeration of sequences, M.I.T. doctoral thesis, 1977. [17] P.A. MacMahon, Combinatorial Analysis, Chelsea, 1960. Originally published in two volumes by Cambridge Univ. Press, 1915-16. [18] A. Mendes and J. Remmel, Descents, inversions, and major indices in permutation groups, Discrete Math., 308 (2008), 2509–2524. ENUMERATING WREATH PRODUCTS VIA GARSIA-GESSEL BIJECTIONS 19 [19] V. Reiner, Signed permutation statistics, European J. Combin., 14 (1993), no. 6, 553–567. [20] V. Reiner, Signed posets, J. Combin. Theory Ser. A 62 (1993), no. 2, 324–360. [21] V. Reiner, The distribution of descents and length in a Coxeter group, Electron. J. Combin. 2 (1995), Research Paper 25. [22] R. P. Stanley, Enumerative Combinatorics, vol. 1, Cambridge University Press, Cambridge, 1997. [23] E. Steingrimsson, Permutation statistics of indexed permutations, European J. Combin., 15 (1994), 187-205. Université de Lyon, Université Lyon 1, Institut Camille Jordan, UMR 5208 du CNRS, F-69622, Villeurbanne Cedex, France E-mail address: biagioli@math.univ-lyon1.fr, zeng@math.univ-lyon1.fr