9512.net
甜梦文库
当前位置:首页 >> >>

Equi-distribution over Descent Classes of the Hyperoctahedral Group


Formal Power Series and Algebraic Combinatorics S? eries Formelles et Combinatoire Alg? ebrique Vancouver 2004

Equi-distribution over Descent Classes of the Hyperoctahedral Group (Extended Abstract)
Ron M. Adin, Francesco Brenti, and Yuval Roichman
Abstract. A classical result of MacMahon shows that the length function and the major index are equidistributed over the symmetric group. Foata and Sch¨ utzenberger gave a remarkable re?nement and proved that these parameters are equi-distributed over inverse descent classes, implying bivariate equi-distribution identities. Type B analogues and further re?nements and consequences are given in this paper. R? esum? e. Un r? esultat classique de MacMahon montre l’? equidistribution de l’indice majeur et de la fonction de longueur sur le groupe symm? etrique. Foata et Sch¨ utzenberger ont donn? e une am? elioration remarquable et montr? e l’? equidistribution sur les classes de descentes inverse, impliquant ainsi des ? equidistributions bivariante. Les analogues pour le type B et d’autres ra?nements et cons? equences sont donn? es dans cet article.

1. Introduction Many combinatorial identities on groups are motivated by the fundamental works of MacMahon [M]. Let Sn be the symmetric group acting on 1, . . . , n. We are interested in a re?ned enumeration of permutations according to (non-negative, integer valued) combinatorial parameters. Two parameters that have the same generating function are said to be equi-distributed. MacMahon [M] has shown, about a hundred years ago, that the inversion number and the major index statistics are equi-distributed on Sn (Theorem 2.4 below). In the last three decades MacMahon’s theorem has received far-reaching re?nements and generalizations. Bivariate distributions were ?rst studied by Carlitz [C]. Foata [F] gave a bijective proof of MacMahon’s theorem; then Foata and Sch¨ utzenberger [FS] applied this bijection to re?ne MacMahon’s identity, proving that the inversion number and the major index are equi-distributed over subsets of Sn with prescribed descent set of the inverse permutation (Theorem 2.5 below). Garsia and Gessel [GG] extended the analysis to multivariate distributions. In particular, they gave an independent proof of the Foata-Sch¨ utzenberger theorem, relying on an explicit and simple generating function (see Theorem 2.8 below). Further re?nements and analogues of the Foata-Sch¨ utzenberger theorem were found recently, involving left-to-right minima and maxima [RR, FH2] and pattern-avoiding permutations [RR, AR2]. For a representation theoretic application of Theorem 2.5 see [Roi]. Since the length and descent parameters may be de?ned via the Coxeter structure of the symmetric group, it is very natural to look for analogues of the above theorems in other Coxeter groups. This is a
1991 Mathematics Subject Classi?cation. Primary 05A15, 05A19; Secondary 20F55. Key words and phrases. permutation statistics, type B, major index, length, descent class. The research of all authors was partially supported by the EC’s IHRP Programme, within the Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272.

1

2

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

challenging open problem. In this paper we focus on the hyperoctahedral group Bn , also known as the classical Weyl group of type B . Despite the fact that an increasing number of enumerative results of this nature have been generalized to the hyperoctahedral group Bn (see, e.g., [Br, FH1, Re3, Re4, Sta1]) and that several “major index” statistics have been introduced and studied for Bn (see, e.g., [CF1, CF2, CF3, Re1, Re2, Ste, FK]), no generalization of MacMahon’s result to Bn has been found until the recent paper [AR1]. There a new statistic, the ?ag major index, de?ned in terms of Coxeter elements, was introduced and shown to be equidistributed with length, which is the natural analogue of inversion number from a Coxeter group theoretic point of view. A search was then initiated for a corresponding “descent statistic” that would allow the generalization to Bn of the Carlitz identity for descent number and major index [C], a problem ?rst posed by Foata. In [ABR1] we introduced and studied two families of statistics on the hyperoctahedral group B n , and showed that they give two generalizations of the Carlitz identity. Another solution of Foata’s problem, also involving the ?ag major index, was presented most recently by Chow and Gessel [CG]. Combinatorial and algebraic properties of the ?ag major index were further investigated in [AR1, HLR, AGR]. In particular, it was shown to play an important role in the study of polynomial algebras, see [AR1, ABR2, Ba]. A natural goal now is to ?nd a type B analogue of the Foata-Sch¨ utzenberger theorem (Theorem 2.5); namely, to prove the equi-distribution of the ?ag major index and the length function on inverse descent classes of Bn . This will be carried out by ?nding a type B analogue of the Garsia-Gessel theorem (Theorem 2.8), which expresses the re?ned enumeration of the classical major index on shu?e permutations in terms of q -binomial coe?cients. The last digit parameter is involved in several closely related identities on Sn , see e.g. [AR2, AGR, RR]. Theorems 4.4 and 4.5 below present a re?nement involving the last digit. This re?nement implies a MacMahon type theorem for the classical Weyl group of type D, which is the same as the one recently proved in [BC]. See Subsection 5.1. 2. Background and Notation 2.1. Notation. Let P := {1, 2, 3, . . .}, N := P ∪ {0}, and Z the ring of integers. For n ∈ P let [n] := {1, 2, . . . , n}, and also [0] := ?. Given m, n ∈ Z, m ≤ n, let [m, n] := {m, m + 1, . . . , n}. For n ∈ P denote [±n] := [?n, n] \ {0}. For S ? N write S = {a1 , . . . , ar }< to mean that S = {a1 , . . . , ar } and a1 < . . . < ar . The cardinality of a set A will be denoted by |A|. For n, k ∈ N denote [n]q := 1 ? qn ; 1?q
n

[n]q ! :=
i=1

[i]q

(n ≥ 1),

[0]q ! := 1;

n k

:=
q

[n]q ! . [k ]q ![n ? k ]q !

Given a sequence σ = (a1 , . . . , an ) ∈ Zn we say that a pair (i, j ) ∈ [n] × [n] is an inversion of σ if i < j and ai > aj . We say that i ∈ [n ? 1] is a descent of σ if ai > ai+1 . We denote by inv (σ ) (respectively, des (σ )) the number of inversions (respectively, descents) of σ . We also let maj (σ ) :=
{i: ai >ai+1 }

i

and call it the major index of σ .

EQUI-DISTRIBUTION OVER DESCENT CLASSES

3

Let M = {m1 , . . . , mt }< ? [n ? 1]. Denote m0 := 0 and mt+1 := n. A sequence σ = (a1 , . . . , an ) is an M -shu?e if it satis?es: if mi < a < b ≤ mi+1 for some 0 ≤ i ≤ t, then σ = (. . . , a, . . . , b, . . .) (i.e. a appears to the left of b in σ ). 2.2. Binomial Identities. In this subsection we recall some binomial identities which will be used in the proof of Theorem 3.3. Lemma 2.1. For every subset M = {m1 , . . . , mt }< ? [n ? 1]
n

(2.1)
j =1

(1 + q j ) ·

n m1 ? m0 , m2 ? m1 , . . . , mt+1 ? mt

=
q
?

{(r0 ,...,rt ) | mi ≤ri ≤mi+1 (?i)}

n r0 ? m0 , m1 ? r0 , . . . , rt ? mt , mt+1 ? rt

·q
q2

i (ri ?mi )

,

where m0 := 0 and mt+1 := n. For t = 0 (i.e., M = ?), identity (2.1) is equivalent to a well-known classical result of Euler, comparing partitions into distinct parts with partitions into odd parts [An, Corollary 1.2]. The proof of the lemma is obtained by induction on t, see [ABR3, Lemma 3.1]. The following “q -binomial theorem” is well-known. Theorem 2.2.
n n

(1 + q i x) =
i=1 k=0

n (k+1 q 2 ) xk . k q

2.3. The Symmetric Group. Let Sn be the symmetric group on [n]. Recall that Sn is a Coxeter group with respect to the Coxeter generators S := {si | 1 ≤ i ≤ n ? 1}, where si may be interpreted as the adjacent transposition (i, i + 1). The classical combinatorial statistics of π ∈ Sn , de?ned by viewing π as a sequence (π (1), . . . , π (n)), may also be de?ned via the Coxeter generators. For π ∈ Sn let (π ) be the standard length of π with respect to the set of generators S . It is well-known that (π ) = inv (π ). Given a permutation π in the symmetric group Sn , the descent set of π is Des (π ) := {1 ≤ i < n | (π ) > (πsi )} = {1 ≤ i < n | π (i) > π (i + 1)}. The descent number of π ∈ Sn is des (π ) := |Des (π )|. The major index, maj (π ) is the sum (possibly zero) maj (π ) :=
i∈Des (π )

i.

The inverse descent class in Sn corresponding to M ? [n ? 1] is the set {π ∈ Sn | Des(π ?1 ) = M }. Note the following relation between inverse descent classes and shu?es. Fact 2.3. For every M ? [n ? 1], {π ∈ Sn | Des (π ?1 ) ? M } = {π ∈ Sn | (π (1), . . . , π (n)) is an M -shu?e}. MacMahon’s classical theorem asserts that the length function and the major index are equi-distributed on Sn . Theorem 2.4. (MacMahon’s Theorem) q
π ∈Sn (π )

=
π ∈Sn

q maj (π) = [n]q !.

4

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

Foata [F] gave a bijective proof of this theorem. Foata and Sch¨ utzenberger [FS] applied this bijection to prove the following re?nement. Theorem 2.5. (The Foata-Sch¨ utzenberger Theorem [FS, Theorem 1]) For every subset B ? [n ? 1], q
{π ∈Sn | Des (π ?1 )=B } (π )

=
{π ∈Sn | Des (π ?1 )=B }

q maj (π) .

This theorem implies Corollary 2.6. q
π ∈Sn

(π ) des(π ?1 )

t

=
π ∈Sn

q maj (π) tdes(π

?1

)

and q
π ∈Sn

(π ) maj (π ?1 )

t

=
π ∈Sn

q maj (π) tmaj (π

?1

)

.

An alternative proof of Theorem 2.5 may be obtained using the following classical fact [Sta2, Prop. 1.3.17]. Fact 2.7. Let M = {m1 , . . . , mt }< ? [n ? 1]. Denote m0 := 0 and mt+1 := n. Then q inv(π) =
{π ∈Sn | Des(π ?1 )?M }

n m1 ? m0 , m2 ? m1 , . . . , mt+1 ? mt

.
q

Garsia and Gessel proved that a similar identity holds for the major index. Theorem 2.8. [GG, Theorem 3.1] Let M = {m1 , . . . , mt }< ? [n ? 1]. Denote m0 = 0 and mt+1 = n. Then n . q maj (π) = m1 ? m0 , m2 ? m1 , . . . , mt+1 ? mt q ?1
{π ∈Sn | Des(π )?M }

Combining this theorem with Fact 2.7 implies Theorem 2.5. 2.4. The Hyperoctahedral Group. We denote by Bn the group of all bijections σ of the set [±n] := [?n, n] \ {0} onto itself such that σ (?a) = ?σ (a) (?a ∈ [±n]), with composition as the group operation. This group is usually known as the group of “signed permutations” on [n], or as the hyperoctahedral group of rank n. We identify Sn as a subgroup of Bn , and Bn as a subgroup of S2n , in the natural ways. If σ ∈ Bn then write σ = [a1 , . . . , an ] to mean that σ (i) = ai for 1 ≤ i ≤ n, and let inv (σ ) := inv (a1 , . . . , an ), Des A (σ ) := Des (a1 , . . . , an ), des A (σ ) := des (a1 , . . . , an ), maj A (σ ) := maj (a1 , . . . , an ), N eg (σ ) := {i ∈ [n] : ai < 0}, and neg (σ ) := |N eg (σ )|. It is well-known (see, e.g., [BB, Proposition 8.1.3]) that Bn is a Coxeter group with respect to the generating set {s0 , s1 , s2 , . . . , sn?1 }, where s0 := [?1, 2, . . . n]

EQUI-DISTRIBUTION OVER DESCENT CLASSES

5

and si := [1, 2, . . . , i ? 1, i + 1, i, i + 2, . . . n] (1 ≤ i < n). This gives rise to two other natural statistics on Bn (similarly de?nable for any Coxeter group), namely
B (σ )

:= min{r ∈ N : σ = si1 . . . sir

for some i1 , . . . , ir ∈ [0, n ? 1]}

(known as the length of σ ) and des B (σ ) := |Des B (σ )|, where the B -descent set Des B (σ ) is de?ned as Des B (σ ) := {i ∈ [0, n ? 1] | Remark 2.9. Note that for every σ ∈ Bn DesA (σ ) = DesB (σ ) \ {0}. There are well-known direct combinatorial ways to compute the statistics for σ ∈ B n (see, e.g., [BB, Propositions 8.1.1 and 8.1.2] or [Br, Proposition 3.1 and Corollary 3.2]), namely
B (σ ) B (σsi )

<

B (σ )}.

= inv (σ ) ?
i∈N eg (σ )

σ (i)

and des B (σ ) = |{i ∈ [0, n ? 1] : σ (i) > σ (i + 1)}|, where σ (0) := 0. For example, if σ = [?3, 1, ?6, 2, ?4, ?5] ∈ B6 then inv (σ ) = 9, des A (σ ) = 3, maj A (σ ) = 11, neg (σ ) = 4, B (σ ) = 27, and des B (σ ) = 4. We shall also use the following formula, ?rst observed by Incitti [I]: inv (σ ) + neg (σ ) (?σ ∈ Bn ), 2 where σ denotes the sequence (σ (?n), . . . , σ (?1), σ (1), . . . , σ (n)). For example, if we take σ = [?3, 5, ?7, 1, 2, ?4, 6] = 19. then inv (σ ) = 35 and B (σ ) = 35+3 2 (2.2)
B (σ )

=

3. Main Results The ?ag major index of a signed permutation σ ∈ Bn is de?ned by f maj (σ ) := 2 · majA (σ ) + neg (σ ), where majA (σ ) is the major index of the sequence (σ (1), . . . , σ (n)) with respect to the natural order ?n < · · · < ?1 < 1 < · · · < n. The following is a type B analogue of the Garsia-Gessel theorem (Theorem 2.8). Theorem 3.1. For every subset M = {m1 , . . . , mt }< ? [0, n ? 1]
n

q f maj (σ) =
{σ ∈Bn | DesB (σ ?1 )?M } i=m1 +1

(1 + q i ) ·

n m1 ? m0 , . . . , mt+1 ? mt

,
q

where m0 := 0 and mt+1 := n. The following is a type B analogue of a classical result (Fact 2.7). Theorem 3.2. For every subset M = {m1 , . . . , mt }< ? [0, n ? 1]
n

q
{σ ∈Bn | DesB (σ ?1 )?M }

B (σ )

=
i=m1 +1

(1 + q i ) ·

n m1 ? m0 , . . . , mt+1 ? mt

,
q

where m0 := 0 and mt+1 := n.

6

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

We deduce a Foata-Sch¨ utzenberger type theorem for Bn . Theorem 3.3. For every subset M ? [0, n ? 1] q
{σ ∈Bn | DesB (σ ?1 )=M }
B (σ )

=
{σ ∈Bn | DesB (σ ?1 )=M }

q f maj (σ) .

The following result re?nes Theorem 3.3. Theorem 3.4. For every subset M ? [0, n ? 1] and j ∈ [±n] q
{σ ∈Bn | DesB (σ ?1 )=M, σ (n)=j }
B (σ )

=
{σ ∈Bn | DesB (σ ?1 )=M, σ (n)=j }

q f maj (σ) .

An analogue of MacMahon’s theorem for Dn follows; see Corollary 5.2 below. 4. Proof Outlines Observation 4.1. Let M = {m1 , . . . , mt }< ? [n ? 1]. (Note: 0 ∈ M .) Let m0 := 0 and mt+1 := n. For σ ∈ Bn , if DesA (σ ?1 ) = M then there exist ri (0 ≤ i ≤ t) such that mi ≤ ri ≤ mi+1 and σ is a shu?e of the following increasing sequences: (?r0 , ?r0 + 1, . . . , ?1 ( = ?(m0 + 1) )), (r0 + 1, r0 + 2, . . . , m1 ), (?r1 , ?r1 + 1, . . . , ?(m1 + 1)), (r1 + 1, r1 + 2, . . . , m2 ), . . . (?rt , ?rt + 1, . . . , ?(mt + 1)) and (rt + 1, rt + 2, . . . , n ( = mt+1 )). For every i, if ri ? mi = 0 (mi+1 ? ri = 0) then the sequence (?ri , . . . , ?(mi + 1)) (respectively, (ri + 1, . . . , mi+1 )) is understood to be empty. Also, with the above notations: 0 ∈ Des B (σ ?1 ) if and only if r0 > 0. First, we prove the following special cases. Theorem 4.2. For every subset M = {m1 , . . . , mt }< ? [n ? 1] q f maj (σ) =
{σ ∈Bn | DesA (σ ?1 )?M } n {σ ∈Bn | DesA (σ ?1 )?M }

q

B (σ )

=

=
i=1

(1 + q i ) ·

n m1 ? m0 , . . . , mt+1 ? mt

,
q

where m0 := 0 and mt+1 := n. Theorem 4.3. For every subset M = {m1 , . . . , mt }< ? [n ? 1] q f maj (σ) =
{σ ∈Bn | DesB (σ ?1 )?M } n {σ ∈Bn | DesB (σ ?1 )?M }

q

B (σ )

=

=
i=m1 +1

(1 + q i ) ·

n m1 ? m0 , . . . , mt+1 ? mt

,
q

where m0 := 0 and mt+1 := n.

EQUI-DISTRIBUTION OVER DESCENT CLASSES

7

The proofs of Theorems 4.2 and 4.3 rely on Theorem 2.8, binomial identities (mentioned in Subsection 2.2), combinatorial properties of the length and descent functions on Bn (mentioned in Subsection 2.4) and Observation 4.1. For detailed proofs see [ABR3]. Proof of Theorems 3.1 and 3.2. Combine Theorems 4.2 and 4.3 with Remark 2.9. Proof of Theorem 3.3. Combine Theorems 3.1 and 3.2, and apply the Principle of InclusionExclusion. Theorem 3.4 is an immediate consequence of the following re?nements of Theorems 3.1 and 3.2. Theorem 4.4. Let n ∈ P, M = {m1 , m2 , . . . , mt }< ? [0, n ? 1] and i ∈ [±n]. Then q f maj (σ) =
{σ ∈Bn : DesB (σ ?1 )?M, σ (n)=i} n?1 n m1 ?m0 ,...,mt+1 ?mt q n m1 ?m0 ,...,mt+1 ?mt

=

? ? ? [mr ?mr?1 ]q ? ? ? [n]q ? ? ?
[mr+1 ?mr ]q ? ? [n]q ? ? ? ? ? ? 0,

· q n?mr
j =m ? 1 +1 n?1

(1 + q j ), (1 + q j ),
j =m1 +1

if i = mr for r ∈ [t + 1]; if i = ?mr ? 1 for r ∈ [t]; otherwise.

q

· q n+mr

Here m0 := 0, mt+1 := n, and m ? 1 := m1 ? 1, m1 , if i = m1 ; otherwise.
B (σ )

Theorem 4.5. Let n ∈ P, M = {m1 , m2 , . . . , mt }< ? [0, n ? 1] and i ∈ [±n]. Then q exactly the same formula as does q f maj (σ) in Theorem 4.4. The proofs of Theorems 4.4 and 4.5 use case-by-case analysis.

satis?es

Proof of Theorem 3.4. Combine Theorems 4.4 and 4.5, and apply the Principle of InclusionExclusion. Problem 4.6. Find combinatorial (bijective) proofs for Theorems 4.4 and 4.5. 5. Final Remarks 5.1. Classical Weyl Groups of Type D. Let Dn be the classical Weyl group of type D and rank n. For an element σ ∈ Dn , let D (σ ) be the length of σ with respect to the Coxeter generators of Dn . It is well-known that we may take Dn = {σ ∈ Bn | neg (σ ) ≡ 0 mod 2}. Let σ = [σ (1), . . . , σ (n)] ∈ Dn . Biagioli and Caselli [BC] introduced a ?ag major index for Dn : f majD (σ ) := f maj (σ (1), . . . , σ (n ? 1), |σ (n)|). By de?nition, (5.1)
σ ∈Dn

q f majD (σ) =
{σ ∈Bn | σ (n)>0}

q f maj (σ) .

8

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

Proposition 5.1. q
{σ ∈Bn | σ (n)>0}
B (σ )

=
σ ∈Dn

q

D (σ )

.

For a proof see [ABR3, Proposition 6.1]. We deduce the following type D analogue (?rst proved in [BC]) of MacMahon’s theorem. Corollary 5.2. q D (σ) . q f majD (σ) =
σ ∈Dn σ ∈Dn

Proof. Combine identity (5.1) and Proposition 5.1 with Theorem 3.4. Problem 5.3. Find an analogue of the Foata-Sch¨ utzenberger theorem for D n . The obvious candidate for such an analogue is false. 5.2. Two Versions of the Flag Major Index. The ?ag major index of σ ∈ Bn was originally de?ned as the length of a distinguished canonical expression for σ . In [AR1] this length was shown to be equal to 2 · majA (σ ) + neg (σ ), where the major index of the sequence (σ (1), . . . , σ (n)) was taken with respect to the order ?1 < · · · < ?n < 1 < · · · < n. In [ABR1] we considered a di?erent order: ?n < · · · < ?1 < 1 < · · · < n (i.e., we de?ned f maj as in Section 3 above). While both versions give type B analogues of the MacMahon and Carlitz identities, only the second one gives an analogue of the Foata-Sch¨ utzenberger theorem. On the other hand, the ?rst one has the alternative natural interpretation as length, as mentioned above, and also produces a natural analogue of the signed Mahonian formula of Gessel and Simion, see [AGR]. The relation between these two versions and their (possibly di?erent) algebraic roles requires further study. References
[ABR1] R. M. Adin, F. Brenti and Y. Roichman, Descent numbers and major indices for the hyperoctahedral group, Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia, PA 2000), Adv. Appl. Math. 27 (2001), 210–224. [ABR2] R. M. Adin, F. Brenti and Y. Roichman, Descent representations and multivariate statistics, Trans. Amer. Math. Soc., to appear, <http://arXiv.org/abs/math.CO/0112073>. [ABR3] R. M. Adin, F. Brenti and Y. Roichman, A type B analogue of the Foata-Sch¨ utzenberger theorem, preprint, 2003. [AGR] R. M. Adin, I. M. Gessel and Y. Roichman, Signed Mahonians, in preparation. [AR1] R. M. Adin and Y. Roichman, The ?ag major index and group actions on polynomial rings. Europ. J. Combin. 22 (2001), 431–446. [AR2] R. M. Adin and Y. Roichman, Equidistribution and sign-balance on 321-avoiding permutations, S? em. Lothar. Combin., to appear, <http://arXiv.org/abs/math.CO/0304429>. [An] G. E. Andrews, The Theory of Partitions, Cambridge Univ. Press, Cambridge, 1984. [Ba] E. Bagno, Combinatorial parameters on classical groups, Ph.D. Thesis, Bar-Ilan Univ., Ramat-Gan, 2003. [BC] R. Biagioli and F. Caselli, Invariant algebras and major indices for classical Weyl groups, preprint, 2002. [BB] A. Bj¨ orner and F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, Springer-Verlag, to appear. [Br] F. Brenti, q -Eulerian polynomials arising from Coxeter groups, Europ. J. Combin. 15 (1994), 417–441. [C] L. Carlitz, A combinatorial property of q -Eulerian numbers, Amer. Math. Monthly 82 (1975), 51–54. [CF1] R. J. Clarke and D. Foata, Eulerian calculus. I. Univariable statistics, Europ. J. Combin. 15 (1994), 345–362. [CF2] R. J. Clarke and D. Foata, Eulerian calculus. II. An extension of Han’s fundamental transformation, Europ. J. Combin. 16 (1995), 221–252. [CF3] R. J. Clarke and D. Foata, Eulerian calculus. III. The ubiquitous Cauchy formula, Europ. J. Combin. 16 (1995), 329–355. [CG] C. O. Chow and I. M. Gessel, On the descent numbers and major indices for the hyperoctahedral group, preprint, 2003. [F] D. Foata, On the Netto inversion number of a sequence, Proc. Amer. Math. Soc. 19 (1968), 236–240. [FH1] D. Foata and G.-N. Han, Calcul basique des permutations sign? ees. I. Longueur et nombre d’inversions, Adv. Appl. Math. 18 (1997), 489–509. [FH2] D. Foata and G.-N. Han, Further properties of the second fundamental transformation on words, preprint, 2003.

EQUI-DISTRIBUTION OVER DESCENT CLASSES

9

[FK] [FS] [GG] [HLR] [H] [I] [M] [RR] [Re1] [Re2] [Re3] [Re4] [Roi] [Ros] [Sta1] [Sta2] [Sta3] [Ste]

D. Foata and C. Krattenthaler, Graphical major indices, II, S? em. Lothar. Combin. 34 (1995), B34k, 16 pp. D. Foata and M. P. Sch¨ utzenberger, Major index and inversion number of permutations. Math. Nachr. 83 (1978), 143–159. A. M. Garsia and I. Gessel, Permutation statistics and partitions. Adv. Math. 31 (1979), 288–305. J. Haglund, N. Loehr and J. Remmel, Statistics on wreath products, perfect matchings and signed words, preprint, 2003. J. E. Humphreys, Re?ection Groups and Coxeter Groups, Cambridge Studies in Advanced Math., no. 29, Cambridge Univ. Press, Cambridge, 1990. F. Incitti, The Bruhat order on the involutions of the hyperoctahedral group, preprint, 2003. P. A. MacMahon, Combinatory Analysis I-II. Cambridge Univ. Press, London/New-York, 1916. (Reprinted by Chelsea, New-York, 1960.) A. Regev and Y. Roichman, Permutation statistics on the alternating group, Adv. Appl. Math., to appear, <http://arXiv.org/abs/math.CO/0302301>. V. Reiner, Signed permutation statistics, Europ. J. Combin. 14 (1993), 553–567. V. Reiner, Signed permutation statistics and cycle type, Europ. J. Combin. 14 (1993), 569–579. V. Reiner, Upper binomial posets and signed permutation statistics, Europ. J. Combin. 14 (1993), 581–588. V. Reiner, The distribution of descent and length in a Coxeter group, Electron. J. Combin. 2 (1995), R25. Y. Roichman, Schubert polynomials, Kazhdan-Lusztig basis and characters, Discrete Math. 217 (2000), 353–365. D. P. Roselle, Coe?cients associated with the expansion of certain products, Proc. Amer. Math. Soc. 45 (1974), 144–150. R. P. Stanley, Binomial posets, M¨ obius inversion, and permutation enumeration, J. Combin. Theory (Ser. A) 20 (1976), 336–356. R. P. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth and Brooks/Cole, Monterey, CA, 1986. R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge Univ. Press, New York/Cambridge, 1999. E. Steingrimsson, Permutation statistics of indexed permutations, Europ. J. Combin. 15 (1994), 187–205.

Department of Mathematics and Statistics, Bar-Ilan University, Ramat-Gan 52900, Israel E-mail address : radin@math.biu.ac.il ? di Roma “Tor Vergata”, Via della Ricerca Scientifica, 00133 Roma, Dipartimento di Matematica, Universita Italy E-mail address : brenti@mat.uniroma2.it Department of Mathematics and Statistics, Bar-Ilan University, Ramat-Gan 52900, Israel E-mail address : yuvalr@math.biu.ac.il



更多相关文章:
Equi-distribution over Descent Classes of the Hyper....pdf
Equi-distribution over Descent Classes of the Hyperoctahedral Group_专业资料。Abstract. A classical result of MacMahon shows that the length function and ...
A maj-inv bijection for C_2 wr A_n.pdf
We give a bijective proof of the MacMahon-type equidistribution over the ...Equi-distribution overs descent classes of the hyperoctahedral group. arXiv:...
A Decomposition of 2--Weak Vertex-Packing Polytopes.pdf
s with elements of the hyperoctahedral group Bd....descent statistic on a subset of Bd de ned in...Moreover, the triangulation is such that its h{...
Statistics on Signed Permutations Groups (Extended ....pdf
the major index are equidistributed over the ...the pair consisting of the descent number and ...The hyperoctahedral group of order n ∈ N (...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图