9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # Equidistribution and Sign-Balance on 321-Avoiding Permutations

arXiv:math/0304429v3 [math.CO] 12 Jan 2004

Equidistribution and Sign-Balance on 321-Avoiding Permutations

Ron M. Adin? Yuval Roichman?? Submitted: May 5, 2003; Revised: January 12, 2004

Abstract Let Tn be the set of 321-avoiding permutations of order n. Two properties of Tn are proved: (1) The last descent and last index minus one statistics are equidistributed over Tn , and also over subsets of permutations whose inverse has an (almost) prescribed descent set. An analogous result holds for Dyck paths. (2) The sign-and-last-descent enumerators for T2n and T2n+1 are essentially equal to the last-descent enumerator for Tn . The proofs use a recursion formula for an appropriate multivariate generating function.

1

1.1

Introduction

Equidistribution

One of the frequent themes in combinatorics is identifying two distinct parameters on the same set which are equidistributed, i.e., share the same generating function. The ?rst substantial result of this kind on permutations, by MacMahon [15], received a remarkable re?nement by Foata and Sch¨ utzenberger [9] (see also [12, 10]). They proved the equidistribution of inversion number and major index, not only on the whole symmetric group, but also on distinguished subsets of permutations (those whose inverses have a prescribed descent set).

Department of Mathematics and Statistics, Bar-Ilan University, Ramat-Gan 52900, Israel. Email: radin@math.biu.ac.il ? Department of Mathematics and Statistics, Bar-Ilan University, Ramat-Gan 52900, Israel. Email: yuvalr@math.biu.ac.il ? Both authors partially supported by the EC’s IHRP Programme, within the Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272.

?

1

Equidistribution theorems on descent classes were shown to be closely related to the study of polynomial rings; see, e.g., [20, 1]. Motivated by the properties of certain quotient rings, studied by Aval and Bergeron [3, 4] (see also Section 6 below), we looked for an analogue for the set of 321-avoiding permutations of the above mentioned theorem of Foata and Sch¨ utzenberger. Let Sn be the symmetric group on n letters, and let Tn := {π ∈ Sn | ? i < j < k such that π (i) > π (j ) > π (k)} be the set of 321-avoiding (or two-row shaped) permutations in Sn . For π ∈ Tn de?ne the following statistics: inv(π ) := inversion number of π (= length of π w.r.t. the usual generators of Sn ) ldes(π ) := last descent of π = max{1 ≤ i ≤ n ? 1 | π (i) > π (i + 1)} (where ldes(π ) := 0 for π = id) lind(π ) := π ?1 (n), the index of the digit “n” in π Des(π ?1 ) := descent set of π ?1 = {1 ≤ i ≤ n ? 1 | π ?1 (i) > π ?1 (i + 1)} The following theorem is a Tn -analogue of [9, Theorem 1]. Theorem 1.1 The statistics “ ldes” and “ lind ? 1” are equidistributed over Tn . Moreover, for any B ? [n ? 2] they are equidistributed over the set Tn (B ) := {π ∈ Tn | Des(π ?1 ) ∩ [n ? 2] = B }, namely: q ldes(π) =

π ∈Tn (B ) π ∈Tn (B )

q lind(π)?1 .

Let Pn be the set of Dyck paths of length 2n. For p = (p1 , . . . , p2n ) ∈ Pn , let ldes(p) := max{1 ≤ i ≤ n ? 1 | pi = +1, pi+1 = ?1} (where ldes(p) := 0 for p = (+ . . . + ? . . . ?)) lind(p) := max{1 ≤ i ≤ n | pi = +1, pi+1 = ?1} Des(p?1 ) := {1 ≤ i ≤ n ? 1 | p2n?i = +1, p2n?i+1 = ?1} 2

Theorem 1.2 q ldes(π) =

π ∈Tn p∈Pn

q ldes(p) =

p∈Pn

q lind(p)?1 .

Moreover, for any B ? [n ? 2], q ldes(π) =

π ∈Tn (B ) p∈Pn (B )

q ldes(p) =

p∈Pn (B )

q lind(p)?1 ,

where Tn (B ) is as in Theorem 1.1 and Pn (B ) := {p ∈ Pn | Des(p?1 ) ∩ [n ? 2] = B }.

1.2

Signed Enumeration

Sign balance for linear extensions of posets was studied in [21, 27, 25]. The study of sign balance for pattern-avoiding permutations started with Simion and Schmidt [23], who proved that the numbers of even and odd 123-avoiding permutations in Sn are equal if n is even, and di?er (up to a sign) by a Catalan number if n is odd. Re?ned sign balance (i.e., a generating function taking into account the signs of permutations) was investigated by D? esarmenien and Foata [6] and by Wachs [26]. A beautiful formula for the signed Mahonian (i.e., the sign-and-major-index enumerator on Sn ) was found by Simion and Gessel [26, Cor. 2]; see also [2]. The last descent statistic is a Tn -analogue of the major index on Sn , as demonstrated by Theorem 1.1 above; see also the discussion in Section 6. Thus, a Tn -analogue of the signed Mahonian on Sn is the sum sign(π )q ldes(π) .

π ∈Tn

For this sum we prove Theorem 1.3 sign(π ) · q ldes(π) =

π ∈T2n+1 π ∈Tn

q 2·ldes(π)

(n ≥ 0), (n ≥ 1).

sign(π ) · q ldes(π) = (1 ? q )

π ∈T2n π ∈Tn

q 2·ldes(π)

3

This result re?nes (and is actually implicit in) some results in [23]. Our approach is di?erent from that of [23]; see Subsection 1.3 below. After the archive posting of the current paper, Theorem 1.3 has been followed by various extensions, analogues and re?nements: (1) A. Reifegerste gave a bivariate re?nement [18, Cor. 4.4]. (2) T. Mansour proved an analogue for 132-avoiding permutations [16]. (3) M. Shynar found analogues for the signed enumeration of tableaux with respect to certain natural statistics [22]. The following phenomenon appears, with small variations, in all these results: the standard enumerator of objects of size n is essentially equal to the signed enumerator of objects of size 2n. This phenomenon deserves further study; it seems to be related to the cyclic sieving phenomenon of [19].

1.3

Recursion

Our main tool in proving the above results is a new recursive formula for the multivariate generating function, on 321-avoiding permutations, involving the inversion number, the last descent, the last index, and the descent set of the inverse (Theorem 2.1 below). It should be noted that, shortly after the archive posting of this paper, bijective proofs of Theorems 1.1 and 1.3 were presented by A. Reifegerste [18].

2

A Recursion Formula

?, x, y, z ) := fn (t

π ∈Tn

De?ne the multivariate generating function tDes(π?1 ) xinv(π) y ldes(π) z lind(π) ,

i∈D ti

(1)

? = (t1 , t2 , . . .) and tD := where t

for D ? [n ? 1].

Theorem 2.1 (Recursion Formula) ?, x, y, z ) = z f1 (t and, for n ≥ 2, ?, x, y, z ) = tn?1 xn yz · fn?1 (t ?, x, yz/x, 1) (x ? yz )fn (t 4

?, x, 1, yz/x) + (1 ? tn?1 )xn yz · fn?1 (t n ?, x, y, 1) + (x ? yz )z · fn?1 (t ?, x, 1, 1) ? xy n z n · fn?1 (t Proof. The case n = 1 is clear. Assume n ≥ 2. Given a permutation π = (π (1), . . . , π (n ? 1)) ∈ Tn?1 , insert the digit n between the kth and (k + 1)st places in π (0 ≤ k ≤ n ? 1) to get a permutation π ? = (π (1), . . . , π (k), n, π (k + 1), . . . , π (n ? 1)) ∈ Sn . Clearly, a necessary and su?cient condition for π ? ∈ Tn is that π has no descent after the kth place, i.e., ldes(π ) ≤ k ≤ n ? 1. (2)

If π has no descents, i.e. π = id, this still holds with ldes(π ) := 0. The new statistics for π ? are: inv(? π ) = inv(π ) + (n ? 1 ? k) k + 1, if k < n ? 1; ldes(? π) = ldes(π ), if k = n ? 1. lind(? π) = k + 1 Des(π ?1 ), if π ?1 (n ? 1) ≤ k; Des(? π ?1 ) = ? 1 Des(π ) ∪ {n ? 1}, if k < π ?1 (n ? 1). Note that, for any π ∈ Tn?1 , ldes(π ) ≤ π ?1 (n ? 1) ≤ n ? 1; and, actually, exactly one of the following two cases holds: either ldes(π ) = π ?1 (n ? 1) < n ? 1 or ldes(π ) < π ?1 (n ? 1) = n ? 1 (if n ? 1 is the last digit in π ). (if n ? 1 is not the last digit in π )

5

We can therefore compute ?, x, y, z ) fn = fn (t

n?1

=

π ∈Tn?1 k =ldes(π )

inv(? π ) ldes(? π ) lind(? π) tDes(? y z π ?1 ) x

=

π ∈Tn?1

tDes(π?1 ) x

n?2

inv(π )

·?

?

π ?1 (n?1)?1

tn?1 xn?1?k y k+1 z k+1

k =ldes(π ) ldes(π ) n ?

+

k =π ?1 (n?1)

x

n?1?k k +1 k +1

y

z

+y

z

?

=

π ∈Tn?1

tDes(π?1 ) x + xn?1 yz

inv(π )

n?2 k =π ?1 (n?1)

· ?tn?1 xn?1 yz

?

π ?1 (n?1)?1

(yz/x)k

k =ldes(π )

= (1 ? yz/x)?1

π ∈Tn?1

tDes(π?1 ) xinv(π) ·

(yz/x)k + y ldes(π) z n ?

?1 (n?1)

?

· t n?1 x

n?1

yz (yz/x)ldes(π) ? (yz/x)π

?1 (n?1)

+ xn?1 yz (yz/x)π

? (yz/x)n?1 + y ldes(π) z n (1 ? yz/x)

?, x, yz/x, 1) = (1 ? yz/x)?1 [tn?1 xn?1 yzfn?1 (t ?, x, 1, yz/x) ? y n z n fn?1 (t ?, x, 1, 1) + (1 ? tn?1 )xn?1 yzfn?1 (t ?, x, y, 1)] . + (1 ? yz/x)z n fn?1 (t Multiply both sides by (x ? yz ) to get the claimed recursion. 2 Corollary 2.2 The ?rst few values of fn are: ?, x, y, z ) = z f1 (t ?, x, y, z ) = z 2 + t1 xyz f2 (t ?, x, y, z ) = z 3 + t1 (x2 y 2 z 2 + xyz 3 ) + t2 (x2 yz + xy 2 z 2 ) f3 (t ?, x, y, z ) = z 4 + t1 (x3 y 3 z 3 + x2 y 2 z 4 + xyz 4 ) f4 (t + t2 (x4 y 2 z 2 + x3 y 3 z 3 + x2 y 3 z 3 + x2 yz 4 + xy 2 z 4 ) + t3 (x3 yz + x2 y 2 z 2 + xy 3 z 3 ) + t1 t3 (x3 y 2 z 2 + x2 y 3 z 3 ) 6

3

Equidistribution of ldes and lind ? 1

In this section we prove Theorem 1.1. Note. Most of the permutations π ∈ Tn , namely those with π (n) = n, satisfy lind(π ) = ldes(π ). Nevertheless, the equidistributed parameters are not ldes and lind but rather ldes and lind ? 1. Note. Tn (B ) “forgets” whether or not n ? 1 belongs to Des(π ?1 ). The corresponding claim, without this “forgetfulness”, is false! Proof of Theorem 1.1. We have to show that, letting x = 1: ? ? ?, 1, q, 1) = f ?, 1, 1, q ), qf n (t n (t ? denotes f under the additional substitution tn?1 = 1. This clearly where f holds for n = 1 (as well as for n = 2, 3, 4, by Corollary 2.2). By Theorem 2.1, for n ≥ 2: ? ?, 1, y, z ) = yzfn?1 (t ?, 1, yz, 1) + (1 ? yz )z n fn?1 (t ?, 1, y, 1) (1 ? yz )f n (t n n ?, 1, 1, 1). ? y z fn?1 (t Letting y = q and z = 1 gives ? ?, 1, q, 1) = qfn?1 (t ?, 1, q, 1) + (1 ? q )fn?1 (t ?, 1, q, 1) (1 ? q )f n (t n ?, 1, 1, 1) ? q fn?1 (t ?, 1, q, 1) ? q n fn?1 (t ?, 1, 1, 1), = fn?1 (t whereas letting y = 1 and z = q yields ? ?, 1, 1, q ) = qfn?1 (t ?, 1, q, 1) + (1 ? q )q n fn?1 (t ?, 1, 1, 1) (1 ? q )f n (t n ?, 1, 1, 1) ? q fn?1 (t ?, 1, q, 1) ? q n+1 fn?1 (t ?, 1, 1, 1). = qfn?1 (t This completes the proof. 2

4

Sign Balance of Tn

In this section we prove Theorem 1.3. ? = (1, 1, . . .), z = 1, and x = ?1 in Proof of Theorem 1.3. Substituting t the generating function (1), denote gn (?1, y ) := fn (? 1, ?1, y, 1) =

π ∈Tn

(?1)inv(π) y ldes(π)

(n ≥ 1).

7

This function records the sign and the last descent of 321-avoiding permutations. Recall also the generating function for last descent, from Theorem 1.1: gn (1, y ) := fn (? 1, 1, y, 1) =

π ∈Tn

y ldes(π)

(n ≥ 1).

Let g0 (1, y ) := 1. We have to prove that g2n+1 (?1, y ) = gn (1, y 2 ) and g2n (?1, y ) = (1 ? y )gn (1, y 2 ) (n ≥ 1). By Theorem 2.1, the polynomial gn (?1, y ) satis?es the recursion formula (?1 ? y )gn (?1, y ) = (?1)n ygn?1 (?1, ?y ) + (?1 ? y )gn?1 (?1, y ) + y n gn?1 (?1, 1). Clearly, g1 (?1, y ) = 1 = g0 (1, y 2 ) and also g2 (?1, y ) = 1 ? y = (1 ? y )g1 (1, y 2 ). We can proceed by induction. If g2n (?1, y ) = (1 ? y )gn (1, y 2 ) then (?1 ? y )g2n+1 (?1, y ) = ?yg2n (?1, ?y ) + (?1 ? y )g2n (?1, y ) + y 2n+1 g2n (?1, 1) = ?y (1 + y )gn (1, y 2 ) + (?1 ? y )(1 ? y )gn (1, y 2 ) +0 = (?1 ? y )gn (1, y 2 ), so that g2n+1 (?1, y ) = gn (1, y 2 ). This, in turn, implies (?1 ? y )g2n+2 (?1, y ) = yg2n+1 (?1, ?y ) + (?1 ? y )g2n+1 (?1, y ) + y 2n+2 g2n+1 (?1, 1) = ygn (1, y 2 ) + (?1 ? y )gn (1, y 2 ) + y 2n+2 gn (1, 1) = ?gn (1, y 2 ) + y 2n+2 gn (1, 1) 8 (n ≥ 0),

and therefore g2n+2 (?1, y ) = where hn (q ) = We need to show that hn (q ) = gn+1 (1, q ). Indeed, the equation (1 ? q )gn+1 (1, q ) = gn (1, q ) ? q n+1 gn (1, 1) follows immediately from Theorem 2.1. 2 Corollary 4.1 (equivalent to [23, Prop. 2]) The sign-balance enumerator for Tn gn (?1, 1) := fn (? 1, ?1, 1, 1) =

π ∈Tn

gn (1, y 2 ) ? y 2n+2 gn (1, 1) = (1 ? y )hn (y 2 ), 1+y gn (1, q ) ? q n+1 gn (1, 1) . 1?q

(?1)inv(π)

is either a Catalan number or zero: g2n+1 (?1, 1) = |Tn | = g2n (?1, 1) = 0 1 2n n+1 n (n ≥ 0)

(n ≥ 1)

The amazing connection between Tn , T2n , and T2n+1 calls for further study.

5

Dyck Paths

Let Pn be the set of Dyck paths of length 2n. Thus, each p ∈ Pn is a sequence (p1 , . . . , p2n ) of n “+1”s and n “?1”s, with nonnegative initial partial sums: p1 + . . . + pi ≥ 0 (?i). Of course, p1 + . . . + p2n = 0 by de?nition. 9

A peak of a Dyck path p = (p1 , . . . , p2n ) ∈ Pn is an index 1 ≤ i ≤ 2n ? 1 such that pi = +1 and pi+1 = ?1. Let Peak(p) be the set of all peaks of p. De?ne the Descent set of p to be Des(p) := {1 ≤ i ≤ n ? 1 | i ∈ Peak(p)}. De?ne the inverse path p?1 ∈ Pn to be p?1 := (?p2n , . . . , ?p1 ), i.e., p?1 is obtained by reversing the order of steps as well as the sign of each step in p. Clearly, i ∈ Peak(p?1 ) ?? 2n ? i ∈ Peak(p), so that Des(p?1 ) = {1 ≤ i ≤ n ? 1 | i ∈ Peak(p?1 )} = {1 ≤ i ≤ n ? 1 | 2n ? i ∈ Peak(p)}. Thus the peaks strictly before the midpoint of p record the descents of p, whereas those strictly after the midpoint of p record the descents of p?1 , in reverse order. The reason for this terminology is the following result. Lemma 5.1 There exists a bijection φ : Tn → Pn such that, if π ∈ Tn and p := φ(π ) ∈ Pn , then Des(p) = Des(π ) and Des(p?1 ) = Des(π ?1 ). Proof. We shall de?ne the bijection φ : Tn → Pn in three steps. First, let φ1 : Tn → SYT 2 (n) be the Robinson-Schensted correspondence, where SYT 2 (n) is the set of all pairs (P, Q) of standard Young tableaux of size n with the same two-rowed shape. Example. φ1 (25134) = 1 2 3 4 5 , 1 2 5 3 4

Next, de?ne φ2 : SYT 2 (n) → SYT (n, n), where SYT (n, n) is the set of standard Young tableaux of (size 2n and) shape (n, n). T = φ2 (P, Q) is obtained by gluing Q along its “eastern frontier” to the skew tableau 10

obtained by rotating P by 1800 and replacing each entry 1 ≤ j ≤ n of P by 2n + 1 ? j . Example. φ2 1 2 3 4 5 1 2 5 , 3 4 = 1 3 2 5 4 7 6 9 8 10

Finally, de?ne φ3 : SYT (n, n) → Pn as follows: the increasing (+1) steps in φ3 (T ) are at places indexed by the entries in row 1 of T , whereas the decreasing (?1) steps are at places indexed by row 2 of T . Example. φ3 1 2 5 3 4 7 6 9 8 10 = (+ + ? ? + + ? ? +?)

The bijection we want is the composition φ = φ3 φ2 φ1 . Let us examine what happens to the descent sets of π and of π ?1 under this sequence of transformations. By a well-known property of the Robinson-Schensted correspondence φ1 , if φ1 φ2 φ3 π ?→ (P, Q) ?→ T ?→ p then π ?1 ?→ (Q, P ) ?→ T ?1 ?→ p?1 . Here T ?1 is the tableau obtained from T ∈ SYT (n, n) by a 1800 rotation and replacement of each entry 1 ≤ j ≤ 2n by 2n + 1 ? j . For a standard two-rowed Young tableau P of size n de?ne: Des(P ) := {1 ≤ i ≤ n ? 1 | i is in row 1 and i + 1 is in row 2 of P }. For T ∈ SYT (n, n) (of size 2n) de?ne Des1 (T ) := Des(T ) ∩ [n ? 1] = {1 ≤ i ≤ n ? 1 | i is in row 1 and i + 1 is in row 2 of T }. Using all this notation we now have, for π ∈ Tn , Des(π ) = Des(Q) = Des1 (T ) = Des(p), where the equality Des(π ) = Des(Q) is again a well-known property of the Robinson-Schensted correspondence. Similarly, Des(π ?1 ) = Des(P ) = Des1 (T ?1 ) = Des(p?1 ). 11

φ1 φ2 φ3

This completes the proof. 2 Note. The bijection φ : Tn → Pn in the proof of Lemma 5.1, so well suited for our purposes, is essentially due to Knuth [13, p. 64] (up to an extra rotation of T ). Its ingredient φ2 was already used by MacMahon [15, p. 131]. For other bijections between these two sets see [5, 14, 7, 8]. For a Dyck path p = (p1 , . . . , p2n ) ∈ Pn , let ldes(p) := max Des(p) = max{1 ≤ i ≤ n ? 1 | pi = +1, pi+1 = ?1}. If Des(p) = ?, i.e., if p = (+ . . . + ? . . . ?) is the “unimodal path”, we de?ne ldes(p) := 0. De?ne also lind(p) := max{1 ≤ i ≤ n | pi = +1, pi+1 = ?1}. In other words, lind(p) = Lemma 5.2 Let n, if n ∈ Peak(p); ldes(p), otherwise.

φ2 φ3

π ?→ (P, Q) ?→ T ?→ p, as in the proof of Lemma 5.1. The following conditions are equivalent: 1. π (n) = n. 2. n is in row 1 of both P and Q. 3. n is in row 1 of T , and n + 1 is in row 2 of T . 4. n ∈ Peak(p). Proof. If π (n) = n then n is the last element inserted into P , and it stays in row 1 due to its size. Thus n is in row 1 of both P and Q. Conversely, if n is in row 1 of both P and Q then it is necessarily the last element in each of these rows. Thus it is the last element inserted into P , i.e., π (n) = n. This proves the equivalence of conditions 1 and 2. Conditions 2 and 3 are clearly equivalent, by the de?nition of φ2 . Similarly for conditions 3 and 4, by the de?nitions of φ3 and of Peak(p). 2 12

φ1

Lemma 5.3 If π ∈ Tn and p := φ(π ) ∈ Pn , then ldes(p) = ldes(π ) and lind(p) = lind(π ). Proof. The ?rst claim follows immediately from Lemma 5.1, since ldes(p) = max Des(p) = max Des(π ) = ldes(π ). (If Des(p) = Des(π ) = ? then ldes(p) = ldes(π ) = 0 by de?nition.) If π (n) = n then lind(π ) = π ?1 (n) = n, and also lind(p) = n by Lemma 5.2. Otherwise (π (n) = n) clearly π ?1 (n) ∈ Des(π ); and π ?1 (n) is actually the last descent of π , because of the 321-avoiding condition. Thus ldes(π ) = lind(π ). On the other hand, n ∈ / Peak(p) by Lemma 5.2 so that, by de?nition, lind(p) = ldes(p). Thus lind(p) = ldes(p) = ldes(π ) = lind(π ), as claimed. 2 Proof of Theorem 1.2. Combine Lemmas 5.1 and 5.3 with Theorem 1.1. 2

6

Final Remarks

The quotient Pn / QSn of the polynomial ring Pn = Q[x1 , . . . , xn ] by the ideal generated by the quasi-symmetric functions without constant term was studied by Aval, Bergeron and Bergeron [4]. They determined its Hilbert series with respect to grading by total degree. For a Dyck path p ∈ Pn , let tail(p) := 2n ? max{i | pi = +1, pi+1 = ?1} be its “tail length”, i.e., the number of consecutive decreasing steps at its end. With this notation, the result of [4] can be formulated as follows. Theorem 6.1 [4, Theorem 5.1] The Hilbert series of the quotient Pn / QSn (graded by total degree) is

n?1

q n?tail(p) =

p∈Pn

n?k n+k k q . n+k k k =0 13

Corollary 6.2 The Hilbert series of the quotient Pn / QSn (graded by total degree) is equal to q ldes(π) .

π ∈Tn

Proof. By the de?nitions in Section 5 above, for every Dyck path p ∈ Pn , tail(p) = 2n ? max Peak(p) = min Des(p?1 ), with the convention min ? := n. Thus, by Lemma 5.1, if π = φ?1 (p) ∈ Tn then tail(p) = min Des(π ?1 ). Now, de?ne a bijection ψ : Tn → Tn by ψ (π ) := w0 π ?1 w0 (?π ∈ Tn ),

where w0 = n . . . 21 is the longest element in Sn . If π ?→ π ? ?→ p then clearly tail(p) = min Des(? π ?1 ) = n ? max Des(π ) = n ? ldes(π ). We conclude that q n?tail(p) =

p∈Pn π ∈Tn ψ φ

q ldes(π) . 2

Theorem 6.1 was proved in [4] by constructing a monomial basis for the quotient ring Pn / QSn . By the proof of Corollary 6.2, the elements of this basis may be indexed by permutations π ∈ Tn , with total degree given by ldes(π ). It is well known that the Hilbert series of the graded coinvariant algebra Pn /In , where In is the ideal generated by the symmetric functions without constant term, is equal to q maj(π) ,

π ∈Sn

where maj(π ) := i∈Des(π) i. A monomial basis idexed by permutations π ∈ Sn , with total degree given by maj(π ), was constructed in [11]. In this sense, the last descent may be considered as a Tn -analogue of the major index.

14

Problem 6.3 Find algebraic interpretations and proofs for Theorems 1.1 and 1.3. For a di?erent algebraic interpretation of the generating function in Theorem 6.1 see [17]. Acknowledgments. Thanks to Nantel Bergeron for stimulating discussions, and to Astrid Reifegerste and an anonymous referee for their comments.

References

[1] R. M. Adin, F. Brenti and Y. Roichman, Descent representations and multivariate statistics, Trans. Amer. Math. Soc., to appear. [2] R. M. Adin, I. M. Gessel and Y. Roichman, Signed Mahonians, preprint, 2003. [3] J.-C. Aval and N. Bergeron, Catalan paths and quasi-symmetric functions, Proc. Amer. Math. Soc. 131 (2003), 1053–1062. [4] J.-C. Aval, F. Bergeron and N. Bergeron, Ideals of quasi-symmetric polynomials and super-covariant polynomials for Sn , preprint, 2002, <http://arXiv.org/abs/math.CO/0202071>. [5] S. Billey, W. Jockusch, and R. P. Stanley, Some combinatorial properties of Schubert polynomials, J. Alg. Combin. 2 (1993), 345–374. [6] J. D? esarmenien and D. Foata, The signed Eulerian numbers, Discrete Math. 99 (1992), 49–58. [7] S. Elizalde, Fixed points and excedances in restricted permutations, preprint, 2002, <http://arXiv.org/abs/math.CO/0212221>. [8] S. Elizalde and I. Pak, Bijections for re?ned restricted permutations, preprint, 2002, <http://arXiv.org/abs/math.CO/0212328>. [9] D. Foata and M.-P. Sch¨ utzenberger, Major index and inversion number of permutations, Math. Nachr. 83 (1978), 143–159. [10] A. M. Garsia and I. M. Gessel, Permutation statistics and partitions, Adv. Math. 31 (1979), 288–305. 15

[11] A. M. Garsia and D. Stanton, Group actions of Stanley-Reisner rings and invariants of permutation groups, Adv. Math. 51 (1984), 107–201. [12] I. M. Gessel, Generating functions and enumeration of sequences, Ph.D. Thesis, M.I.T., 1977. [13] D. E. Knuth, The Art of Computer Programming, vol. 3, AddisonWesley, Reading, MA, 1973. [14] C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. 27 (2001), 510–530. [15] P. A. MacMahon, Combinatory analysis, vol. 1, Cambridge Univ. Press, Cambridge, 1915. [16] T. Mansour, Equidistribution and sign-balance on 132-avoiding permutations, preprint, 2003. [17] D. I. Panyushev, AD-nilpotent ideals of a Borel subalgebra: generators and duality, preprint, 2003, <http://arXiv.org/abs/math.RT/0303107>. [18] A. Reifegerste, Re?ned sign-balance on 321-avoiding permutations, preprint, 2003, <http://arXiv.org/abs/math.CO/0305327>. [19] V. Reiner, D. Stanton and D. White, The cyclic sieving phenomenon, preprint, 2003. [20] Y. Roichman, Schubert polynomials, Kazhdan-Lusztig basis and characters, Discrete Math. 217 (2000), 353–365. [21] F. Ruskey, Generating linear extensions of posets by transpositions, J. Combin. Theory Ser. B 54 (1992), 77–101. [22] M. Shynar, On Inversions in Standard Young Tableaux, M.Sc. Thesis, Bar-Ilan Univ., Ramat-Gan, 2003. [23] R. Simion and F. W. Schmidt, Restricted permutations, Europ. J. Combin. 6 (1985), 383–406. [24] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, New York/Cambridge, 1999.

16

[25] R. P. Stanley, Some remarks on sign-balanced and maj-balanced posets, preprint, 2002, <http://arXiv.org/abs/math.CO/0211113>. [26] M. Wachs, An involution for signed Eulerian numbers, Discrete Math. 99 (1992), 59–62. [27] D. E. White, Sign-balanced posets, J. Combin. Theory Ser. A 95 (2001), 1–38.

17

- Refined Sign-Balance on 321-Avoiding Permutations, preprint
- Permutations Containing and Avoiding 123 and 132 Patterns
- Classification of bijections between 321- and 132-avoiding permutations
- 321-polygon-avoiding permutations and Chebyshev polynomials
- On bijections between 231-avoiding permutations and Dyck paths
- The fine structure of 321-avoiding permutations
- On the number of permutations avoiding a given pattern
- Short note on complexity and approximability of unimodal partitions of permutations
- High strength and fracture toughness balance on the extruded Mg–Ca–Zn alloy
- On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia

更多相关文章：
**
...***and* *Sign-Balance* *on* *321-Avoiding* *Permutations*.pdf

*Equidistribution* *and* *Sign-Balance* *on* *321-Avoiding* *Permutations*_专业资料。Let $T_n$ be the set of *321-avoiding* *permutations* of order $n$. Two properties...**
...Article B51d ***EQUIDISTRIBUTION* *AND* *SIGN*-B.pdf

S? eminaire Lotharingien de Combinatoire 51 (2004), Article B51d*EQUIDISTRIBUTION* *AND* *SIGN-BALANCE* *ON* *321-AVOIDING* *PERMUTATIONS* RON M. ADIN?? *AND* ... 更多相关标签：

S? eminaire Lotharingien de Combinatoire 51 (2004), Article B51d