The permutation enumeration of wreath products Ck§Sn of cyclic and symmetric groups

Advances in Applied Mathematics 30 (2003) 343–368 www.elsevier.com/locate/aam The permutation enumeration of wreath products Ck § Sn of cyclic and symmetric groups Jennifer D. Wagner 1 Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, 851 S. Morgan (m/c 249), Chicago, IL 60607, USA Received 28 September 2001; accepted 5 March 2002 Abstract Brenti introduced a homomorphism from the symmetric functions to polynomials in one variable with rational coefficients. His map is defined on the elementary symmetric functions. When it is applied to the homogeneous and power symmetric functions the results are generating functions for descents and excedences of permutations in the symmetric group, respectively. Beck and Remmel gave proofs of Brenti’s results based on combinatorial definitions of the transition matrices between the bases. In addition, they gave an analog for the hyperoctahedral group. We extend the ideas of these proofs to obtain similar results for wreath products of an arbitrary cyclic group with the symmetric group.  2003 Elsevier Science (USA). All rights reserved. Keywords: Symmetric functions; Permutation statistics; Wreath products 1. Introduction Let Λk denote the space of symmetric polynomials
in an infinite number of variables which are homogeneous of degree k, and let Λ = k
0 Λk . Brenti [3] introduced a homomorphism ξ : Λ → Q(x) defined on the elementary symmetric functions by ξ(ek ) = (1 − x)k . k! E-mail address: jwagner@math.uic.edu. 1 This work was completed as part of the author’s doctoral dissertation under the direction of Jeffrey B. Remmel at the University of California, San Diego. 0196-8858/03/$ – see front matter  2003 Elsevier Science (USA). All rights reserved. doi:10.1016/S0196-8858(02)00539-0 344 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 He proved that the homomorphism ξ has the remarkable property that when it is applied to a homogeneous symmetric function hk , the result is the well-known Eulerian polynomial, which is also the generating function for the number of descents of a permutation in Sk : ξ(hk ) = Ak =  x des(σ ) , σ ∈Sk where des(σ ) = |{i: 1
i
n − 1, σ (i) > σ (i + 1)}|. In addition, if ξ is applied to a power symmetric function, the result is a generating function for the number of excedences over conjugacy classes:    ξ pλ (x) = x e(σ ) , σ ∈C (λ) where e(σ ) = |{i: 1
i
n, σ (i) > i}| and C(λ) is the conjugacy class of Sn indexed by the partition λ. Beck and Remmel [1,2] gave combinatorial proofs of these and other related results, including q-analogs. In addition, Beck used these combinatorial methods to develop an analog of Brenti’s results for Bn , the hyperoctahedral group. Since Bn is of course isomorphic to C2 § Sn , it is natural to extend these ideas to arbitrary wreath products Ck § Sn . We do this here. We begin by giving notation and definitions, along with some background necessary for the proofs to come, including definitions of certain statistics on elements of Ck § Sn and an analog and a q-analog of Brenti’s homomorphism ξ . In Sections 3 and 4 we give the images of the homogeneous and power bases under these homomorphisms. We then state without proof the images of the other major bases in Section 5. We conclude by indicating other statistics and analogs of ξ that can be used and the theorems that those definitions lead to. 2. Preliminaries In this section we will give some notation and definitions. Let λ ⊢ n denote the fact that λ is a partition of n. If λ = (λ1 , λ2 , . . . , λl(λ) ), the number of parts of λ is denoted by l(λ) and |λ| = λ1 + λ2 + · · · + λl(λ) . If λ is written as λ = (1m1 , 2m2 , . . . , nmn ) where mi is the number of parts of size i, then let zλ = 1m1 2m2 · · · nmn (m1 !)(m2 !) · · · (mn !). Given k partitions λ(1) , λ(2) , . . . , λ(k) such that |λ(1) | + |λ(2)| + · · · + |λ(k) | = n, we write (λ(1) , . . . , λ(k) ) ⊢ n. We denote the elementary, homogeneous, power, monomial, Schur, and forgotten symmetric functions by eλ , hλ , pλ , mλ , sλ , and fλ , respectively (see [7]). J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 345 Consider an element of Ck § Sn as a signed permutation with signs in the set {ǫ, ǫ 2 , . . . , ǫ k } where ǫ = e2πi/ k . An element can be written in two-line form as  1 ǫ1 σ1 2 ǫ2 σ2 ··· n · · · ǫn σn σ = ǫ1 σ1 ǫ2 σ2 ··· σ=  , in one-line form as ǫn σn , or in cycle form with cycles of the form (ǫm i1 , ǫ1 i2 , . . . , ǫm−1 σm ) where i1 is mapped to ǫ1 i2 , i2 is mapped to ǫ2 i3 and so on. We often  abuse notation by referring to ǫi σi as just σi . ǫ(σi ) denotes ǫi and we then set ǫ(σ ) = ni=1 ǫ(σi ). We define a partial ordering Ω on the signed letters that make up elements of Ck § Sn by 1 ǫ1 <Ω <Ω 2 ǫ2 <Ω · · · <Ω <Ω · · · <Ω .. . n, ǫn, ǫ k−1 1 <Ω ǫ k−1 2 <Ω · · · <Ω ǫ k−1 n. In addition, we use a partial ordering Γ which in equates letters that have the same base letter, i.e., ǫ i a <Γ ǫ j b if a < b for all i, j. We use the partial orderings Ω and Γ to define a number of statistics on elements of Ck § Sn . The number of (Ck § Sn )-descents of an element σ is given by   desk (σ ) = {i: 1
i
n − 1, σi >Ω σi+1 }. The number of (Ck § Sn )-inversions of an element σ is given by   invk (σ ) =  (i, j ): 1
i < j
n, σi >Γ σj . If an element σ is given in cycle notation as σ = (σ11 , σ12 , . . . , σ1l1 )(σ21 , σ22 , . . . , σ2l2 ) · · · (σm1 , σm2 , . . . , σmlm ), then the number of (Ck § Sn )-descedances is given by 346 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 dek (σ ) = m      j : 1
j
li − 1, ǫ(σi ) = ǫ(σi ), σi > σi j j j+1 j+1 i=1   + χ(σili > σi1 )χ ǫ(σili ) = ǫ(σi1 ) , where for a statement A, χ(A) = 1 if A is true and χ(A) = 0 if A is false. Our final statistic depends not only on an element of Ck § Sn , but also on a partition λ = (λ1 , λ2 , . . . , λl(λ) ) ⊢ n. The number of λ-descents of an element of Ck § Sn , denoted desk,λ , is defined in the following way. Write σ = σ1 σ2 · · · σn in one-line notation and break it into pieces of lengths λ1 , λ2 , . . . , λl(λ) . Then count only the (Ck § Sn )-descents that occur with both i and i +1 in the same piece. For example if σ = ǫ7 ǫ5 4 2 1 ǫ 2 8 ǫ 2 3 ǫ6 ∈ C3 § Sn and λ = (1, 3, 4), then σ is broken into pieces [ǫ7][ǫ5 4 2][1 ǫ 2 8 ǫ 2 3 ǫ6]. Here desk (σ ) = 4 but desk,λ (σ ) = 2 since the descents in the first and fourth positions are not counted as λ-descents because 1 and 2 do not lie in the same block, and neither do 4 and 5. For our study of the q-analogs of the results, we need notation for q-analogs of the factorial, binomial coefficient, and multinomial coefficient. These are defined by the following expressions. [n] = 1 + q + q 2 + · · · + q n−1 , [n]! = [n][n − 1][n − 2] · · · [1], [n]! n , = k [k]![n − k]! [n]! n . = k1 k2 · · · kl [k1 ]![k2]! · · · [kl ]! The following is a useful theorem regarding q-analogs, which is due to Carlitz [4]. Let l i=1 ai = n, then  r∈R(1a1 ,2a2 ,...,l al ) q inv(r) = n , a1 a2 . . . al (1) where R(1a1 , 2a2 , . . . , l al ) is the set of rearrangements of a1 1’s, a2 2’s, . . . , and al l’s. Note that if k = 2 the partial order Ω and the statistics defined here are not consistent with the usual ordering and statistics for Bn . In the case of Ck § Sn , we have much more choice than in the Sn and Bn cases. In Bn , there is an ordering on the letters that make up Bn elements which is natural when considering it as a Coxeter group. Since we do not have the geometric interpretation in Ck § Sn , we have more freedom to determine an ordering on the letters that make up elements of Ck § Sn . There are k ways that we can define these orderings, which in turn lead to different definitions of statistics on these elements, and to different definitions of the analog of ξ . For example, we can have letters with certain signs be ordered in the reverse order, which is similar to the usual definitions for Bn . We can choose to give this reverse ordering to up to k − 1 of the signs. We choose here to use the ordering of Ck § Sn where no sign has the reverse ordering because it gives results which are J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 347 most easily generalizable. Note that in doing so, however, we sacrifice some information that we could otherwise have gained. The results obtained using these different orderings, including the appropriate definitions of statistics and the analog of ξ , are stated without proof in Section 6. If the product of the signs in a cycle is ǫ i , we say that it is an ǫ i -cycle. The cycle structure of an element in Ck § Sn is given by (λ(1) , . . . , λ(k) ) where λ(i) gives the lengths of the ǫ i -cycles. Let     Ck § Sn λ(1) , . . . , λ(k) = σ ∈ Ck § Sn : cycle structure of σ = λ(1) , . . . , λ(k) . In fact, {Ck § Sn (λ(1) , . . . , λ(k) ): (λ(1) , . . . , λ(k) ) ⊢ n} is the set of conjugacy classes of Ck § Sn . In [9], the author and Remmel give a characteristic map analogous to the Frobenius characteristic which sends the class functions of Ck § Sn into  ΛWk,n (X, Y, Z) = Λa (X) ⊗ Λb (Y ) ⊗ Λc (Z). a+b+c=n This characteristic map is slightly different than that given by Poirier [8], which he uses to express the number of
elements of Ck § Sn with a given descent set in terms of characters of Ck § Sn . Set ΛWk = n
0 Λk,n . Some of the important bases of ΛWk,n are given below. With the exception of the analog of the power symmetric functions, they are given in a version of λ-ring notation which is extended to include roots of unity by requiring that pr (ǫX) = ǫpr (X) [9]. The bases are indexed by k-tuples of partitions (λ(1) , . . . , λ(k) ) ⊢ n. Let X(1) , . . . , X(k) denote k different alphabets. Then the analog of the power, Schur, elementary, homogeneous, monomial, and forgotten symmetric functions are: k  i=1 k  i=1 k  i=1 k  i=1     pλ(1) X(1) · · · pλ(k) X(k) ,   sλ(i) ǫ 1·i X(1) + · · · + ǫ k·i X(k) ,   eλ(i) ǫ 1·i X(1) + · · · + ǫ k·i X(k) ,   hλ(i) ǫ 1·i X(1) + · · · + ǫ k·i X(k) ,   mλ(i) ǫ 1·i X(1) + · · · + ǫ k·i X(k) , and k  i=1   fλ(i) ǫ 1·i X(1) + · · · + ǫ k·i X(k) , 348 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 Fig. 1. The (1,1,1,2)-brick tabloids of shape (2,3). respectively. The proofs of the theorems we give require combinatorial interpretations of the transition matrices between bases of ΛWk,n . Most of the matrices are just k-tuples of the transition matrices between the bases of Λn as defined by Eğecioğlu and Remmel [6]. The transition matrices that involve the power basis are more interesting and are developed in detail by the author in [10]. Here we introduce the combinatorial objects involved, and state the identities needed in the following. A µ-brick tabloid of shape λ can be defined in the following way. Make bricks of lengths corresponding to the sizes of the parts of µ and place them in the Ferrers’ diagram of shape λ such that each brick lies horizontally in a row and no bricks overlap. The (1, 1, 1, 2)-brick tabloids of shape (3, 2) are shown in Fig. 1. We will denote by Bµ,λ the set of µ-brick tabloids of shape λ, and let Bµ,λ = |Bµ,λ |. We then have the following expression due to Eğecioğlu and Remmel [6]: hλ =  (−1)n−l(µ) Bµ,λ eµ . (2) µ⊢n Let the shape λ(1) ∗ · · · ∗ λ(k) be the shape obtained by placing the Ferrers’ diagrams (1) ,...,α (k) of λ(1) , . . . , λ(k) corner to corner. Then let Fλα(1)∗···∗λ (k) be the set of tabloids of shape λ(1) ∗ · · · ∗ λ(k) filled with α (1) -, . . . , α (k) -bricks such that each row is filled with only (1) ,α (2) ,α (3) one type of brick. An example of Fλα(1)∗λ (2) ∗λ(3) (in the C3 § Sn case) is given in Fig. 2 with (1) 2 2 (2) 3 α = (1, 2 , 3 ), α = (1, 2 , 3, 4), α (3) = (15 , 22 ), λ(1) = (4, 6, 7), λ(2) = (3, 5), and λ(3) = (32 , 4). (1) ,...,α (k) Assign to each element f of Fλα(1)∗···∗λ (k) a weight w(f ) defined by w(f ) =  w(b), b∈f where the product is over the bricks in f and the weight of a brick b is defined by w(b) =  |b|, b is at the end of a row in f, 1, otherwise. The following expressions are given in [10]: 349 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 (1) (2) (3) Fig. 2. An element of F α(1) ,α(2) ,α (3) . λ     pλ(1) X(1) · · · pλ(k) X(k)  = (−1)n−l(α  (α (1) ,...,α (k) )⊢n f ∈F α(1) ,...,α(k) (t) k l(λ ∗λ ∗λ (1))−···−l(α (k) ) (1) )+···+l(λ(k) ) ǫ k α (t) (λ(s) ) s,t=1 −st l w(f ) λ(1) ∗···∗λ(k)     × eα (1) ǫ 1·1 X(1) + · · · + ǫ 1·k X(k) · · · eα (k) ǫ k·1 X(1) + · · · + ǫ k·k X(k) , (3) where l α (λ(s) ) is the number of rows of λ(s) filled with α (t ) -bricks,     mλ(1) ǫ 1·1X(1) + · · · + ǫ 1·k X(k) · · · mλ(k) ǫ k·1 X(1) + · · · + ǫ k·k X(k)  = (−1)l(α  zα (1) · · · zα (k) (α (1) ,...,α (k) )⊢n f ∈F α(1) ,...,α(k) ×ǫ (1))+···+l(α (k) )−l(λ(1))−···−l(λ(k) ) ǫ k α (t) (λ(s) ) s,t=1 −st l λ(1) ∗···∗λ(k) k α (t) (λ(s) ) s,t=1 −st l and     w(f )pα (1) X(1) · · · pα (k) X(k) , (4)     fλ(1) ǫ 1·1 X(1) + · · · + ǫ 1·k X(k) · · · fλ(k) ǫ k·1 X(1) + · · · + ǫ k·k X(k) (1) =   (α (1) ,...,α (k) )⊢n f ∈F α(1) ,...,α(k) (−1)n−l(λ )−···−l(λ zα (1) · · · zα (k) (k) ) ǫ k α (t) (λ(s) ) s,t=1 −st l λ(1) ∗···∗λ(k)  × w(f )pα (1) X (1)    · · · pα (k) X(k) . (5) We now define the concept of special rim hooks and special rim hook tabloids. Consider a Ferrers’ diagram Fλ of shape λ. A rim hook of λ is a sequence of cells in Fλ , such that any two consecutive cells share an edge, and removal of the cells from the diagram results 350 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 Fig. 3. An example of a rim hook tabloid and a special rim hook tabloid. in another Ferrers’ diagram. A rim hook tabloid of shape λ and type µ is a sequence of partitions   T = ∅ = λ(0) ⊂ λ(1) ⊂ · · · ⊂ λ(k) = λ , such that for each 1
i
k, λ(i) − λ(i−1) is a rim hook of size µi . A rim hook of λ is a special rim hook if one of its cells lies in the first column of λ. A special rim hook tabloid of shape λ and type µ is a rim hook tabloid of shape λ and type µ such that all of the rim hooks  are special rim hooks. The sign of a special rim hook tabloid is defined by sgn(T ) = h∈T sgn(h), where the sign of a hook is sgn(h) = (−1)r(h)−1 , and r(h) is the number of rows occupied by the hook h. An example of a rim hook tabloid and a special rim hook tabloid, both of shape (1, 1, 2, 3, 4, 4) and type (3, 3, 4, 5), are given in Fig. 3. Eğecioğlu and Remmel [5] showed that for λ and µ partitions of n, the (µ, λ)th entry of the inverse Kostka matrix is given by −1 Kµ,λ =  w(T ), T ∈SRHµ,λ where SRHµ,λ is the set of all special rim hook tabloids of shape λ and type µ. We will use this combinatorial interpretation along with the identity sλ =  −1 Kµ,λ hµ (6) µ⊢n in the following. We also need definitions of analogs of ξ and ξ for Ck § Sn . These are given below. Definition 1. The homomorphism ξk : ΛWk → Q[ǫ][x] is defined on the elementary basis by    ξk en ǫ m·1 X(1) + · · · + ǫ m·k X(k) = ǫ m·1 (ǫ m·1 − ǫ m·1 x)n−1 + · · · + ǫ m·k (ǫ m·k − ǫ m·k x)n−1 k n n! for each m = 1, 2, . . . , k. J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 351 Definition 2. The homomorphism ξ k : ΛWk → Q[q][ǫ][x] is defined on the elementary basis by    ξ k en ǫ m·1 X(1) + · · · ǫ m·k X(k) n q (2) (ǫ m·1 (ǫ m·1 − ǫ m·1 x)n−1 + · · · + ǫ m·k (ǫ m·k − ǫ m·k x)n−1 ) = k n [n]! for each m = 1, 2, . . . , k. Note that these definitions are not given in the most concise form possible. This is because this form suggests the combinatorial proofs to come. 3. ΛWk -homogeneous bases under ξk When ξk and ξ k are applied to the homogeneous basis, the following results are obtained. Theorem 1. Let ξk and ξ k be the homomorphisms defined in Definitions 1 and 2. Then for m = 1, 2, . . . , k, we have    k n n! ξk hn ǫ m·1 X(1) + · · · + ǫ m·k X(k) =    k n n! ξk hλ ǫ m·1 X(1) + · · · + ǫ m·k X(k) =    k n n! ξ k hn ǫ m·1 X(1) + · · · + ǫ m·k X(k) =  ǫ(σ )m x desk (σ ) , (7)  ǫ(σ )m x desk,λ (σ ) , (8)  ǫ(σ )m x desk (σ ) q invk (σ ) , (9) ǫ(σ )m x desk,λ (σ ) q invk (σ ) , (10) σ ∈Ck §Sn σ ∈Ck §Sn σ ∈Ck §Sn and    k n n! ξ k hλ ǫ m·1 X(1) + · · · + ǫ m·k X(k) =  σ ∈Ck §Sn where desk (σ ), desk,λ (σ ), and invk (σ ) are the number of (Ck § Sn )-descents, the number of Ck § Sn λ-descents, and the number of Ck § Sn inversions of σ , respectively. Proof of (7). We begin with the following relation, which can be found in [6]: hn =  (−1)n−l(µ) Bµ,(n) eµ . µ⊢n Multiply by k n n! and apply ξk to obtain (11) 352 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368    k n n! ξk hn ǫ m·1 X(1) + · · · + ǫ m·k X(k)     = (−1)n−l(µ) Bµ,(n) k n n! ξk eµ ǫ m·1 X(1) + · · · + ǫ m·k X(k) µ⊢n =  (−1)n−l(µ) Bµ,(n) k n n! µ⊢n l(µ)  ǫ m·1 (ǫ m·1 − ǫ m·1 x)µi −1 + · · · + ǫ m·k (ǫ m·k − ǫ m·k x)µi −1 k µi µi ! i=1     n = µ1 , . . . , µl(µ) × µ⊢n T ∈Bµ,(n) × l(µ)  i=1 µ −1   µ −1  m·1  m·1 . ǫ x − ǫ m·1 i + · · · + ǫ m·k ǫ m·k x − ǫ m·k i ǫ (12) We interpret this as a sum of signed, weighted objects o ∈ Okhn . For a given partition µ, and a µ-brick tabloid of shape (n), the multinomial coefficient fills each brick with a decreasing sequence of integers such that exactly the integers 1, 2, . . . , n are used. Each brick is designated as an i-brick for some i = 1, 2, . . . , k. Each cell c is weighted in the following way: w(c) =  ǫ mi , −ǫ mi c is at the end of an i-brick, or ǫ mi x, c is elsewhere in an i-brick. (13) µi −1 terms. Define the weight of an object o by w(o) = This  accounts for the (x − 1) o∈Okhn w(o). An example of c∈o w(c). Then we can write the expression in (12) as such an object is given in Fig. 4. We perform a sign-changing, weight-preserving involution on the objects. Definition 3. The involution is as follows. Traverse the tabloid from left to right. At the first occurrence of one of the following, perform the appropriate operation. • If a cell c has weight −ǫ mi , split the brick after c and change the weight of c from −ǫ mi to +ǫ mi . Fig. 4. An example of an object in Okhn in the k = 3 case. J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 353 • If there is a decrease between the integer filling of the last cell c of a brick and the first cell of the next brick and both are i-bricks for some i, join the two bricks together and change the weight of c from +ǫ mi to −ǫ mi . An example of the involution in the k = 3 case is given in Fig. 5. The fixed points of the involution are µ-brick tabloids of shape (n) filled with the integers 1, 2, . . . , n such that the integers decrease within each brick and increase between consecutive bricks of the same type. Each brick is designated as an i-brick for some i = 1, 2, . . . , k. Each cell is weighted by the following: ′ w (c) =  c is at the end of an i-brick, ǫ mi , mi ǫ x, c is elsewhere in an i-brick. (14) An example of a fixed point of the involution is given in Fig. 6. Reading left to right, we consider the filling of each fixed point to be an element of Ck § Sn with each cell in an i-brick corresponding to an element with sign ǫ i . The descents of the element have an x-weight and cells that do not correspond to a descent do not have an x-weight. Thus the x-weights count the (Ck § Sn )-descents. In addition, each cell in an i-brick has a sign of ǫ mi so the sign counted here is the mth power of the sign of the element. This completes the proof of (7). ✷ Proof of (8). We outline this proof, as it is similar to the proof of (7). By the same steps as before, we obtain the expression    k n n! ξk hλ ǫ m·1 X(1) + · · · + ǫ m·k X(k) Fig. 5. An example of the involution on Okhn in the k = 3 case. Fig. 6. An example of a fixed point of the involution in the k = 3 case. 354 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 Fig. 7. An example of an object in Okhλ in the k = 3 case. =    µ⊢n T ∈Bµ,λ × n µ1 , . . . , µl(µ)  l(µ)  i=1 µ −1   µ −1  m·1  m·1 . ǫ x − ǫ m·1 i + · · · + ǫ m·k ǫ m·k x − ǫ m·k i ǫ (15) We interpret this as a sum of signed, weighted objects o ∈ Okhλ . These objects are the same as those in Okhn except that for a given partition µ, we now have a µ-brick tabloid of shape  λ, rather than one-row shapes. The weight of an object is again defined by w(o) = c∈o w(c) so the expression (15) can then be written as o∈Okh w(o). An λ example of such an object in the k = 3 case is given in Fig. 7. We perform the sign-changing, weight-preserving involution given in Definition 3 on these objects, considering the rows from top to bottom. Note that to join two bricks they must be in the same row. The fixed points of the involution are µ-brick tabloids of shape λ filled with the integers 1, 2, . . . , n such that the integers decrease within bricks and increase between consecutive bricks of the same type in the same row. Each brick is designated as an i-brick, and each cell is weighted as in (14). Again consider the integer fillings of the fixed points, read left to right and top to bottom, as elements of Ck § Sn , with each cell in an i-brick corresponding to an letter with sign ǫ i . The cells that correspond to (Ck § Sn )-descents within each row are counted by an x, but we have no idea what happens between rows. Thus the x-weights count the (Ck § Sn )-descents. As in the proof of (7), the ǫ-weights contribute (ǫ(σ ))m . ✷ Proof of (9). We again begin with the identity (11). Multiply by k n [n]!, apply ξ k , and simplify to get    k n [n]! ξ k hn ǫ m·1 X(1) + · · · + ǫ m·k X(k) =   µ⊢n T ∈Bµ,(n) n µ1 , . . . , µl(µ) J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 × l(µ)  i=1 355 µi   µ −1  µ −1  q ( 2 ) ǫ m·1 ǫ m·1 − ǫ m·1 x i + · · · + ǫ m·k ǫ m·k − ǫ m·k x i . We interpret this as a sum of signed, weighted objects o ∈ Okhn q . The objects are similar to those in Okhn . They are µ-brick tabloids of shape (n). Each brick is designated as an i-brick for some i = 1, 2, . . . , k. Each cell is given an x-weight according to the rule (13). The cells are again filled with the integers 1, 2, . . . , n, but this time they are filled in the following way, which also associates a q-weight to each cell. For a given tabloid, let B1 , B2 , . . . , Bl be the bricks that occur in order from left to right. Let bi = |Bi | so b1 , b2 , . . . , bn is a rearrangement of µ1 , µ2 , . . . , µl . We associate bi i’s with Bi and consider rearrangements in R(1b1 , 2b2 , . . . , l bl ). For each rearrangement r ∈ R(1b1 , 2b2 , . . . , l bl ), we create a permutation σ (r) in the following way. Number, from right to left, first the 1’s, then the 2’s, and so on. We then take the inverse permutation σ −1 (r). Here is an example of this process for a rearrangement of (14 , 22 , 35 ). r = 1 3 2 1 3 3 1 2 1 3 3, σ (r) = 4 11 6 3 10 9 2 5 1 8 7, σ −1 (r) = 9 7 4 1 8 3 11 10 6 5 2. By the way we constructed σ −1 (r), we have decreasing sequences of lengths b1 , b2 , . . . , bl , which then fit into the bricks B1 , B2 , . . . , Bl . By a theorem of Carlitz [4], n = µ1 , µ2 , . . . , µl  q inv(r) . r∈R(1b1 ,2b2 ,...,l bl ) By the construction of σ (r), we then have           b1 b2 bl inv σ −1 (r) = inv σ (r) = inv(r) + + + ··· + . 2 2 2 This allows us to add a q-weight to each cell. Let this weight be q p(c) where p(c) is the number of cells to the right of c whose integer fillings are less than the integer filling of c. The q-weight of a tabloid will then give the number of inversions of the integer filling. The rest of the proof is the same as that of (7). Note that the involution does not change the integer fillings, and therefore does not change the q-weight. ✷ The proof of (10) is a combination of the proofs of (8) and (9), so we do not include it here. 4. ΛWk -power symmetric functions under ξk When ξk is applied to the power basis, the following result is obtained. 356 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 Theorem 2. Let ξk be the homomorphism defined in Definition 1. If (λ(1) , . . . , λ(k) ) ⊢ n, then      k n n! ξk pλ(1) X(1) · · · pλ(k) X(k) = zλ(1) · · · zλ(k)  x dek (σ ) , σ ∈C(λ(1) ,...,λ(1) ) where C(λ(1),...,λ(k) ) is the conjugacy class of Ck § Sn indexed by (λ(1) , . . . , λ(k) ) and dek (σ ) is the number of (Ck § Sn )-descedances of σ . Proof. We begin by multiplying the expression (3) by k n n!/(zλ(1) · · · zλ(k) ) and applying ξk to obtain the following expression:      k n n! ξk pλ(1) X(1) · · · pλ(k) X(k) zλ(1) · · · zλ(k)  = (α (1) ,...,α (k) )⊢n k n n!(−1)n−l(α  k (1) (k) f ∈F α(1) ,...,α (k) λ ∗···∗λ (m) × l(λ(1) )+···+l(λ(k) ) (m) k l(α  ) ǫ m·1 (ǫ m·1 − ǫ m·1 x)αi  m=1 i=1 (1) )−···−l(α (k) ) −1 zλ(1) · · · zλ(k) ǫ k α (t) (λ(s) ) s,t=1 −st l (m) + · · · + ǫ m·k (ǫ m·k − ǫ m·k x)αi w(f ) −1 . (m) k αi αi(m) ! This in turn is equal to  1  (α (1) ,...,α (k) )⊢n f ∈F α(1) ,...,α(k) k l(λ (1) )+···+l(λ(k) ) zλ(1) · · · zλ(k) ǫ k α (t) (λ(s) ) s,t=1 −st l w(f ) λ(1) ∗···∗λ(k)  n × (1) (1) (k) (k) α1 , . . . , αl(α (1) ) , . . . , α1 , . . . , αl(α (k) )  (m) × k l(α )  m=1 i=1 α (m) −1 α (m) −1   . + · · · + ǫ m·k ǫ m·k x − ǫ m·k i ǫ m·1 ǫ m·1 x − ǫ m·1 i If bm,i is the brick in f corresponding to αi(m) , define α̂i(m) =  (m) αi − 1, bm,i is at the end of a row in f, (m) αi , otherwise. (m) Then set α̂ (m) (f ) = (α̂1(m) , α̂2(m) , . . . , α̂l(α (m) ) ). We may then rewrite the above as J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368  1  (α (1) ,...,α (k) )⊢n f ∈F α(1) ,...,α(k) (1) (k) k l(λ )+···+l(λ ) zλ(1) · · · zλ(k) ǫ 357 k α (t) (λ(s) ) s,t=1 −st l λ(1) ∗···∗λ(k)         n − l(λ(1) ) − · · · − l(λ(k) ) × n(n − 1) · · · n − l λ(1) − · · · − l λ(k) + 1 α̂ (1) (f ) · · · α̂ (k) (f ) (m) × k l(α )  m=1 i=1  α (m) −1  α (m) −1 ǫ m·1 ǫ m·1 x − ǫ m·1 i + · · · + ǫ m·k ǫ m·k x − ǫ m·k i . (16) We interpret the above expression as a sum of signed, weighted objects o ∈ Okp . (1) (k) ,...,α They are elements of Fλα(1)∗···∗λ (k) , with each brick designated as an i-brick for some i = 1, 2, . . . , k. Each cell is given a weight according to the following rule. If c is a cell in an i-brick in an α (m) -row, then  m(i−s) ,  c is at the end of a row in λ(s) , ǫ w(c) = ǫ mi , c is at the end of a brick but not a row,   mi mi −ǫ or ǫ x, otherwise. In addition, the cells are filled with the integers 1, 2, . . . , n in the following way. The term n(n − 1) · · · (n − l(λ(1) ) − · · · − l(λ(k) ) + 1) fills the last cell of the last brick in each row. The multinomial coefficient fills all of the remaining cells with the integers not yet used in such a way that the numbers decrease within each brick, with the possible exception of the last cell in the row. To rectify this, for each row, we find the smallest integer si , appearing in that row and move it to the last cell in the row. We move the number that was originally in the last cell, ai , to the brick previously occupied by si and rearrange the numbers in that brick so they are decreasing. Place a star over the cell now occupied by ai . For a row of length l, there are l ways to obtain a given filling. For a simple example of this, see Fig. 8. We would like to ignore the marked cells and consider only the fillings where the smallest number is at the end of each row, so we must divide by the length of each row. In addition, we would like to ignore the order of the rows within each λ(i) , so we divide by zλ(1) · · · zλ(k) . An example of such an object in the k = 3 case is given in Fig. 9. Fig. 8. A row of length 5 has 5 possible origins. 358 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 Fig. 9. An example of the objects in Okp in the k = 3 case. Traversing the diagram, considering first λ(1) , then λ(2) , and so on, and in each part, considering the rows from top to bottom and within each row, considering the cells from left to right, perform the involution given in Definition 3. The fixed points have the (1) ,...,α (k) following properties. They are elements of Fλα(1)∗···∗λ (k) , filled with the integers 1, 2, . . . , n such that the integers decrease within each brick and increase between consecutive bricks of the same type, with the smallest number in each row appearing at the end. The weight of a cell c in an i-brick in an α (m) -row is given by  m(i−s) ,  ǫ w(c) = ǫ mi ,   mi ǫ x, c is at the end of a row in λ(s) , c is at the end of a brick but not a row, otherwise. Define a k-volution to be a function from a set S to itself such that for any s ∈ S, if the function is applied k times to s, the image is s. We now perform a k-volution on the fixed points of the previous involution. For m = 1, 2, . . . , k − 1, change each α (m) -row into an α (m+1) -row. In addition, change each α (k) -row into an α (1) -row. All of this is to be done with the appropriate changes of weight. Apply this k-volution k times. An example of the k-volution in the k = 3 case is given in Fig.10. Fig. 10. An example of the k-volution in λ(1) in the k = 3 case. J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 359 Consider an α (k) -row in one of the objects, and say that its weight is w. Let bi be the number of cells that appear in i-bricks in the row. If we assume that the row lies in λ(s) , then when the row is an α (m) -row, its weight can be written as ǫ −ms+ k i=1 mibi w. The sum of these weights is  k  m=1 ǫ m(−s+ k i=1 ibi )  w. If ki=1 ibi ≡ s (mod k), then this sum is kw. Otherwise, the sum is 0. Thus we are only left with rows in λ(s) with ki=1 ibi ≡ s (mod k). It no longer matters what type of row we (1) (k) have, since it can be considered as an α (k) -row, so we must divide by k l(λ )+···+l(λ ) . (1) (k) Our objects are now diagrams of shape λ ∗ · · · ∗ λ , filled with bricks of lengths the parts of α (1) , . . . , α (k) . Each brick is designated as an i-brick for some i. The cells are filled with the integers 1, 2, . . . , n such that each integer is used exactly once, the smallest integer in each row appears at the end of the row, the integers decrease within each brick, and they increase between consecutive bricks of the same type in the same row. The cells are weighted according to the following rule. w(c) =  1, c is at the end of a brick, x, otherwise. Interpret each row as a cycle in a Ck § Sn element, where if a is the filling of a cell in an i-brick, then it corresponds to ǫ i a in the Ck § Sn cycle. Within each cycle, decreases between elements of the same type are weighted by x. All other transitions are weighted by 1. Note that there can never be a decrease from the last cell of the row to the first cell, since the last cell is filled with the smallest integer in the row. Thus the x-weight counts the decedences of the cycle. In λ(s) , we have cycles with ki=1 ibi ≡ s (mod k), so the sign of the cycle is ǫ s . This holds for each s, so the element consisting of the cycles formed by all of the rows belongs to the conjugacy class indexed by (λ(1) , . . . , λ(k) ). ✷ The image of the power basis under the map ξ k is a corollary of the proof of the following theorem. Theorem 3. For any i = 1, 2, . . . , k, the following holds.    k j [j ]! ξ k pj X(i) = (i)  (i) σ ∈Ck §Sj   x desk (σ )+1−t (σ )q invk (σ ) x t (σ ) − (x − 1)t (σ ) , where Ck § Sj is the set {σ ∈ Ck § Sj : ǫ(σ ) = ǫ i }, and t (σ ) is the length of the cofinal strictly decreasing sequence of elements of the same type in the one-line notation of σ . 360 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 Proof. We begin by specializing the expression (3) by setting λ(i) = (j ) and by letting all of the other partitions be empty:   kpj X(i) =   (−1)j −l(α (1) )−···−l(α (k) ) ǫ− k α (t) (λ(i) ) t=1 it l w(f ) (α (1) ,...,α (k) )⊢j f ∈F α(1) ,...,α(k) ∅∗···∗(j)∗···∗∅     × eα (1) ǫ 1·1 X(1) + · · · + ǫ 1·k X(k) · · · eα (k) ǫ k·1 X(1) + · · · + ǫ k·k X(k) . Multiply this by k j [j ]!, apply ξ k , and simplify to get    k j +1 [j ]!ξ k pj X(i)  =  w(f )ǫ − k α (t) (λ(i) ) t=1 it l (α (1) ,...,α (k) )⊢j f ∈F α(1) ,...,α(k) j (1) (k) α1 , . . . , αl(α (k)) q ∅∗···∗(j)∗···∗∅ (m) × k l(α  ) almr 2 q( m=1 r=1   (m) (m) ) ǫ m·1 ǫ m·1 x − ǫ m·1 αr −1 + · · · + ǫ m·k ǫ m·k x − ǫ m·k αr −1 . We interpret this as a sum of signed, weighted objects o ∈ Okpq . The objects are in (1) (k) α ,...,α (m) -row for some F∅∗···∗(j )∗···∗∅ so they consist of one row which is designated as an α m = 1, 2, . . . , k. We consider the sum separately for each possible value of m. Note that α (t) k (i) the term ǫ − t=1 it l (λ ) is accounted for my multiplying by ǫ −it the rest of the sum corresponding to α (t ) -rows. Thus we have    k j +1 [j ]! ξ k pj X(i) = k  ǫ −im  α (m) ⊢j f ∈Bα(m) ,(j) m=1 ×  (m) l(α ) r=1 q( (m) αr 2 w(f ) j (m) (m) α1 , . . . , αl(α (m))   (m) (m) ) ǫ m·1 ǫ m·1 x − ǫ m·1 αr −1 + · · · + ǫ m·k ǫ m·k x − ǫ m·k αr −1 . (17) We fix m and interpret the rest of the sum (not including ǫ −mi ). We have a α (m) -brick tabloid of shape (j ). Each brick is designated as an a-brick for some a = 1, 2, . . . , k. Fill the cells with the integers 1, 2, . . . , j and associate a q-weight, wq (c), to each cell as in the proof of (9). This q-weight counts the number of inversions of the filling and may be ignored for now as it will not change with what is to follow. In addition, associate to each cell an x-weight, given by wx (c) =  c is at the end of an a-brick, ǫ ma , ma ma −ǫ or ǫ x, c is elsewhere in an a-brick. 361 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 The last brick in the row is also weighted by its length. The weight of the object is then defined by w(o) =  wx (c)wq (c) c∈o = ǫ   |b| χ(b is at the end of the row) b∈o k a a=1 maN (o)  c∈o Wx (c)wq (c)   |b|  χ(b is at the end of the row) b∈o  , where N a (o) is the number of cells occurring in a-bricks in o, and Wx (c) is a modified weight given by Wx (c) =  1, c is at the end of a brick, −1, wx (c) = −ǫ ma for some m and a, x, wx (c) = ǫ ma x for some m and a. Then the sum can be written as o∈Okpq w(o). We perform a sign-changing, weight-preserving involution on these objects. Note that changing the size of the last brick in the row will change the weight of the object, since the last brick is weighted by its size. Thus in the following involution, we do not change anything about the last brick. Proceed through the brick from left to right. At the first occurrence of one of the following, perform the appropriate operation, unless the first occurrence involves the last brick. • If there is a cell c with Wx (c) = −1, divide the brick after c and change Wx (c) from −1 to +1. • If there is a decrease between the integer filling of the last cell c of one brick and that of the first cell of the next and both bricks are of the same type, join the bricks together and change Wx (c) from 1 to −1. The fixed points of the involution are α (m) -brick tabloids of shape (j ), filled with the integers 1, 2, . . . , j such that the integers decrease within bricks and increase between consecutive bricks of the same type, with the possible exception of a decrease between the second to last and last brick. The last brick has weight 1 in the last cell and either −1 or x in the other cells. The other bricks have weight 1 in the last cell and x in the other cells. Each cell also has a q-weight. In addition, the objects are weighted by the length of k a the last brick, and by ǫ a=1 maN (o) . Let t (σ ) be the length of the cofinal strictly decreasing sequence of integers in bricks of the same type. Note that this might correspond to either just the last brick, or the last two bricks. Let L be the length of the last brick. See Fig. 11 for an example of what this might look like. We want to count all of the descents of the object, so we pull these out. This means we divide each of the weights, except for the weight of the last cell in the row, by x. The adjusted weights are shown in Fig. 12. 362 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 Fig. 11. An example of t (σ ) and L. Fig. 12. An example of the adjusted weights. We can now rewrite  ǫ k a a=1 maN (o) x w(o) as o∈Okpq desk (σ ) invk (σ ) q σ ∈Ck §Sj       t (σ )−1  1  1 t (σ )−1 1 L−1 L + t (σ ) 1 − 1− x x x L=1 by splitting the possibilities into the case in which the second to last brick is part of the cofinal decreasing sequence, and the case when it is not. In both cases, we have pulled out the terms x desW (σ ) q invW (σ ) , so we need only determine the adjusted weights. The first sum is over all possible lengths of the last brick, assuming that the second to last brick is part of the cofinal decreasing sequence. The 1/x comes from the last cell of the second to last brick. Within the sum, the L is from the weight of the last brick, and the term (1 − 1/x)L−1 gives all the possible weights of the other cells of the last brick. The last term corresponds to the case where the cofinal decreasing sequence occurs only within the last brick. In this case, the weight of the last brick is L = t (σ ). The last cell of the brick must have weight 1, but the term (1 − 1/x)t (σ )−1 counts all of the possible weights of the other cells in the brick. We can then rewrite the last part of the sum in the following ways to get the desired formula:     t (σ )−1  1  1 L−1 1 t (σ )−1 1− L + t (σ ) 1 − x x x L=1 =x t (σ )−1   1− L=1 d =x dx  t (σ )−1   L=1 1 x L−1 1 1− x L x2 L     1 t (σ )−1 + t (σ ) 1 − x   1 t (σ )−1 + t (σ ) 1 − x J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 363     d (1 − 1/x)t (σ ) − 1 1 t (σ )−1 =x + t (σ ) 1 − dx (1 − 1/x) − 1 x       1 t (σ ) d 1 t (σ )−1 =x x 1− 1− + t (σ ) 1 − dx x x  t (σ ) 1 . =x −x 1− x a This with the fact that ǫ aN (o) corresponds to ǫ(σ ) where σ is the element of Ck § Sj corresponding to the object gives  o∈Ok pq w(o) =  σ ∈Ck §Sj   ǫ(σ )m x desW (σ )+1−t (σ )q invW (σ ) x t (σ ) − (x − 1)t (σ ) . Putting this back into (17) gives k     k j +1 [j ]! ξ k pj X(i) = ǫ −mi m=1  = σ ∈Ck §Sj  σ ∈Ck §Sj   ǫ(σ )m x desk (σ ) q invk (σ ) x t (σ ) − (x − 1)t (σ ) k   ǫ −im ǫ(σ )m . x desk (σ ) q invk (σ ) x t (σ ) − (x − 1)t (σ ) m=1 Note that k  ǫ −im ǫ(σ ) = m=1  0, k, ǫ(σ ) ≡ i (mod k), ǫ(σ ) ≡ i (mod k). Thus we are left with only those elements σ of Ck § Sj such that ǫ(σ ) = ǫ i . Let Ck § Sj(i) be the set of all such elements. Then    k j +1 [j ]! ξ k pj X(i) =  (i) σ ∈Ck §Sj   kx desk (σ ) q invk (σ ) x t (σ ) − (x − 1)t (σ ) , which implies the theorem. ✷ If (λ(1) , . . . , λ(k) ) ⊢ n, let Ck § Sn (λ(1) , . . . λ(k) ) be the set of all σ = σ1 σ2 · · · σn ∈ (1) (k) Ck § Sn such that if σ is broken into segments of lengths λ(1) 1 , . . . , λl(λ(1) ) , . . . , λ1 , . . . , (k) λl(λ(k)) , in that order, then each segment corresponding to a part of λ(i) has total sign ǫ i . We then have the following corollary. 364 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 Corollary 1. If j1 + j2 + · · · + jk = m, then      k n [n]! ξ k pj1 X(1) · · · pjk X(k) =  x desk,(j1 ,...,jk ) (σ ) q invk (σ ) k  i=1 σ ∈Ck §Sn ((ji ),...,(jk ))   x 1−ti (σ ) x ti (σ ) − (x − 1)ti (σ ) , where ti (σ ) is the length of the cofinal strictly decreasing sequence of letters of the same type in the (j1 + · · · + ji−1 + 1)st through (j1 + · · · + ji )th letters of the one-line notation of σ . Note that in the above corollary, desk,(j1 ,...,jk ) (σ ) is desk,ρ (σ ) where ρ is the nondecreasing rearrangement of (j1 , . . . , jk ). The proof follows the above proof, and is easily generalized to prove the following corollary. Note that the partition (λ(1) ∪ · · · ∪ λ(k) ) is (1) (1) (k) (k) defined to be the nondecreasing rearrangement of (λ1 , . . . , λl(λ(1) ) , . . . , λ1 , . . . , λl(λ(k) ) ). Corollary 2. If (λ(1) , . . . , λ(k) ) ⊢ n, then      k n [n]! ξ k pλ(1) X(1) · · · pλ(k) X(k)  des (σ ) = x k,(λ(1) ∪···∪λ(k) ) q invk (σ ) σ ∈Ck §Sn (λ(1) ,...,λ(k) ) (m) k l(λ  )    x 1−tm,i (σ ) x tm,i (σ ) − (x − 1)tm,i (σ ) , × m=1 i=1 where tm,i (σ ) denotes the length of the cofinal decreasing sequence of elements of the same (m) type in the segment of σ corresponding to λi . 5. Images of the other bases under ξk and ξ k For the sake of completeness, we give expressions for the images of the Schur, monomial, and forgotten bases of ΛWk . Application of ξk and ξ k to (6) immediately gives the following theorem. Theorem 4. Let ξk and ξ k be the homomorphisms defined in Definitions 1 and 2. Then for m = 1, 2, . . . , k, we have      −1 desk,λ (σ ) ǫ(σ )m Kµ,λ x , k n n! ξk sλ ǫ m·1 X(1) + · · · + ǫ m·k X(k) = µ⊢n σ ∈Sn and      −1 desk,λ (σ ) invk (σ ) ǫ(σ )m Kµ,λ x q . k n [n]! ξ k sλ ǫ m·1 X(1) + · · · + ǫ m·k X(k) = µ⊢n σ ∈Sn J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 365 Application of ξk and ξ k to (4) and (5) immediately give the following results. Theorem 5. Let ξk and ξ k be the homomorphisms defined in Definitions 1 and 2. Then we have      k n n! ξk mλ(1) ǫ 1·1 X(1) + · · · + ǫ1 · kX(k) · · · mλ(k) ǫ k·1 X(1) + · · · + ǫ k·k X(k)   k α (t) (s) (1) (k) (1) (k) = (−1)l(α )+···+l(α )−l(λ )−···−l(λ ) ǫ s,t=1 −st l (λ ) (α (1) ,...,α (k) )⊢n f ∈F α(1) ,...,α(k) λ(1) ∗···∗λ(k) x dek (σ ) ,  × w(f ) σ ∈C(α(1) ,···,α(k) )      k n n! ξk fλ(1) ǫ 1·1 X(1) + · · · + ǫ1 · kX(k) · · · fλ(k) ǫ k·1 X(1) + · · · + ǫ k·k X(k)   k α (t) (s) (1) (k) = (−1)n−l(λ )−···−l(λ ) ǫ s,t=1 −st l (λ ) (α (1) ,...,α (k) )⊢n f ∈F α(1) ,...,α(k) λ(1) ∗···∗λ(k) x dek (σ ) ,  × w(f ) σ ∈C(α(1) ,···,α(k) )     k n [n]! ξ k mλ(1) ǫ 1·1X(1) + · · · + ǫ1 · kX(k) · · · mλ(k) ǫ k·1X(1) + · · · + ǫ k·k X(k)   k α (t) (s) (1) (k) (1) (k) = (−1)l(α )+···+l(α )−l(λ )−···−l(λ ) ǫ s,t=1 −st l (λ )  (α (1) ,...,α (k) )⊢n f ∈F α(1) ,...,α(k) λ(1) ∗···∗λ(k)  × w(f ) σ ∈Ck §Sn x desk,(α(1) ∪···∪α(k) ) (σ ) invk (σ ) q (α (1) ,...,α (k) ) (m) k l(α  )    x 1−tm,i (σ ) x tm,i (σ ) − (x − 1)tm,i (σ ) , × m=1 i=1 and      k n [n]! ξ k fλ(1) ǫ 1·1 X(1) + · · · + ǫ1 · kX(k) · · · fλ(k) ǫ k·1 X(1) + · · · + ǫ k·k X(k)   k α (t) (s) (1) (k) (1) (k) = (−1)l(α )+···+l(α )−l(λ )−···−l(λ ) ǫ s,t=1 −st l (λ ) (α (1) ,...,α (k) )⊢n f ∈F α(1) ,...,α(k) λ(1) ∗···∗λ(k)  × w(f ) σ ∈Ck §Sn (m) x desk,(α(1) ∪···∪α(k) ) (σ ) invk (σ ) q (α (1) ,...,α (k) ) k l(α  )    x 1−tm,i (σ ) x tm,i (σ ) − (x − 1)tm,i (σ ) , × m=1 i=1 366 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 where tm,i (σ ) denotes the length of the cofinal decreasing sequence of elements of the same type in the segment of σ corresponding to λ(m) i . 6. The permutation enumeration of Ck § Sn for other choices of orderings Here we state without proof the definitions and results for orderings on the letters that make up elements of Ck § Sn which is different than that above. The definitions of descents are designed to correspond to what happens in the Bn case, that is, for some signs the order of the letters of that sign is reversed and that sign causes descents at any change of sign or at the end of the element. For r = 1, 2, . . . , k − 1, we say i is an r-modified (Ck § Sn )-descent of σ ∈ Ck § Sn if one of the following conditions holds: • • • • 1
i
n − 1, ǫ(i) = ǫ(i + 1) = 1, . . . , r − 1 or k, and σi > σi+1 . 1
i
n − 1, ǫ(i) = ǫ(i + 1) = r, . . . , k − 1, and σi < σi+1 . 1
i
n − 1, ǫ(i) = ǫ(i + 1), and ǫ(i) = r, . . . , k − 1. i = n and ǫ(i) = r, . . . , k − 1. Denote the number of r-modified (Ck § Sn )-descents of σ by des(r) k (σ ). If an element σ = σ1 σ2 · · · σn is divided into segments of lengths λ1 , λ2 , . . . , λl(λ) for some λ ⊢ n, then the number of r-modified Ck § Sn λ-descents is the number of r-modified (Ck § Sn )(r) descents, desk,λ , which occur with both i and i + 1 in the same segment. The number of r-modified (Ck § Sn )-descedences, denoted de(r) k (σ ), is the number of decreases, in the sense of r-modified (Ck § Sn )-descents, which occur between consecutive elements of a cycle in σ . The definition of (Ck § Sn )-inversions is not modified and remains invk (σ ) = |{(i, j ): 1
i < j
n, σi >Γ σj }|. We define r-modified versions of ξk and ξ k as follows. Definition 4. Define the homomorphism ξk(r) : ΛWk → Q[x] on the elementary basis by (r)  ξk   en ǫ m·1 X(1) + · · · + ǫ m·k X(k) 1 = n k n!  r−1   j =1 k−1  m·j  m·j n−1   n−1   ǫ x ǫ x − ǫ m·j ǫ m·j ǫ m·j − ǫ m·j x + j =r   n−1 , + ǫ m·k ǫ m·k − ǫ m·k x for m = 1, 2, . . . , k. 367 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 (r) Definition 5. Define the homomorphism ξ k : ΛWk → (Q[q])[x] on the elementary basis by    m·1 (1) X + · · · + ǫ m·k X(k) ξ (r) k en ǫ  r−1 n k−1 n−1   m·j  m·j    q (2)  m·j  m·j m·j n−1 ǫ x ǫ x − ǫ m·j ǫ + ǫ −ǫ x = n k [n]! j =r j =1   n−1 , + ǫ m·k ǫ m·k − ǫ m·k x for m = 1, 2, . . . , k. When ξk(r) and ξ (r) k are applied to the homogeneous basis we have the following results. Note that here, λ ⊢ n.    k n n! ξk(r) hn ǫ m·1 X(1) + · · · + ǫ m·k X(k) =  (r)   k n n! ξk hλ ǫ m·1 X(1) + · · · + ǫ m·k X(k) = (r)    hn ǫ m·1 X(1) + · · · + ǫ m·k X(k) = k n [n]! ξ k (r)  ǫ(σ )m x desk  ǫ(σ )m x desk,λ (σ ) ,  ǫ(σ )m x desk (σ ) , σ ∈Ck §Sn (r) σ ∈Ck §Sn (r) (σ ) invk (σ ) q , σ ∈Ck §Sn and (r)  k n [n]! ξ k   hλ ǫ m·1 X(1) + · · · + ǫ m·k X(k) =  (r) ǫ(σ )m x desk,λ (σ ) q invk (σ ) . σ ∈Ck §Sn When ξk(r) is applied to the power basis the result is     k n n! (r)  ξk pλ(1) X(1) · · · pλ(k) X(k) = zλ(1) · · · zλ(k)  (r) x dek (σ ) , σ ∈C(λ(1) ,...,λ(k) ) where C(λ(1),...,λ(k) ) is the conjugacy class of Ck § Sn indexed by (λ(1) , . . . , λ(k) ). For the q-analog, recall that Ck § Sn (λ(1) , λ(k) ) is the set of all σ = σ1 σ2 · · · σn ∈ Ck § Sn such that (1) (k) (k) if σ is broken into segments of lengths λ(1) 1 , . . . , λl(λ(1) ) , . . . , λ1 , . . . , λl(λ(k) ) , in that order, then each segment corresponding to a part of λ(i) has total sign ǫ i . Then the image of the power basis under ξ (r) k is given by 368 J.D. Wagner / Advances in Applied Mathematics 30 (2003) 343–368 (r)  k n [n]! ξ k =     pλ(1) X(1) · · · pλ(k) X(k) (r)  des (σ )−1 invk (σ ) x k,(λ(1) ∪···∪λ(k) ) q σ ∈Ck §Sn (λ(1) ,...,λ(k) ) (m) × k l(λ  )  m=1 i=1 (m) rx 2−ti (σ )  (m) x ti (σ ) (m) − (x − 1)ti (σ )    (m) + (k − r) 1 − (1 − x)ti (σ ) , (1) (k) where (λ(1) ∪ · · · ∪ λ(k) ) is the nondecreasing rearrangement of λ1 , . . . , λl(λ(k)) , and ti(m) (σ ) is the cofinal strictly decreasing sequence of elements of the same type of the segment of σ corresponding to λ(m) i . References [1] D.A. Beck, J.B. Remmel, Permutation enumeration of the symmetric group and the combinatorics of symmetric functions, J. Combin. Theory Ser. A 72 (1995) 1–49. [2] D.A. Beck, Permutation enumeration of the symmetric and hyperoctahedral group and the combinatorics of symmetric functions, PhD thesis, University of California, San Diego, La Jolla, CA, 1993. [3] F. Brenti, Permutation enumeration, symmetric functions, and unimodality, Pacific J. Math. 157 (1993) 1– 28. [4] L. Carlitz, Sequences and inversions, Duke Math. J. 37 (1970) 193–198. [5] Ö. Eğecioğlu, J.B. Remmel, A combinatorial interpretation of the inverse Kostka matrix, Linear and Multilinear Algebra 26 (1990) 59–84. [6] Ö. Eğecioğlu, J.B. Remmel, Brick tabloids and the connection matrices between bases of symmetric functions, Discrete Appl. Math. 34 (1991) 107–120. [7] I.G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd edition, Oxford Univ. Press, Oxford, 1995. [8] S. Poirier, Cycle type and descent set in wreath products, Discrete Math. 180 (1998) 315–343. [9] J.B. Remmel, J.D. Wagner, A Frobenius characteristic for wreath products Ck §Sn , submitted. [10] J.D. Wagner, The combinatorics of the permutation enumeration of wreath products between cyclic and symmetric groups, PhD thesis, University of California, San Diego, La Jolla, CA, 2000.