Séminaire Lotharingien de Combinatoire 51 (2004), Article B51d

EQUIDISTRIBUTION AND SIGN-BALANCE ON 321-AVOIDING PERMUTATIONS

RON M. ADIN^{∗‡} AND YUVAL ROICHMAN^{†‡}

Abstract. Let T_{n} be the set of 321-avoiding permutations of order n. Two properties of T_{n} are proved: (1) The last descent and last index minus one statistics are equidistributed over T_{n}, 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 T_{2n} and T_{2n+1} are essentially equal to the last-descent enumerator for T_{n}. The proofs use a recursion formula for an appropriate multivariate generating function.

1. Introduction

1.1. 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 first substantial result of this kind on permutations, by MacMahon [15], received a remarkable refinement by Foata and Schützenberger [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).

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ützenberger.

Let S_{n} be the symmetric group on n letters, and let

T_{n} := {π ∈ S_{n} | ∄ i < j < k such that π(i) > π(j) > π(k)}

∗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.

be the set of 321-avoiding (or two-row shaped) permutations in S_{n}. For π ∈ T_{n} define the following statistics:

inv(π) := inversion number of π
(= length of π w.r.t. the usual generators of S_{n})
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 T_{n}-analogue of [9, Theorem 1].

Theorem 1.1. The statistics “ ldes” and “ lind −1” are equidistributed over T_{n}. Moreover, for any B ⊆ [n − 2] they are equidistributed over the set

T_{n}(B) := {π ∈ T_{n} | Des(π^{−1}) ∩ [n − 2] = B},

namely:

∑_{π∈T_{n}(B)} q^{ldes(π)} = ∑_{π∈T_{n}(B)} q^{lind(π)−1}.

Let P_{n} be the set of Dyck paths of length 2n. For p = (p_{1}, …, p_{2n}) ∈ P_{n}, let

ldes(p) := max{1 ≤ i ≤ n − 1 | p_{i} = +1, p_{i+1} = −1}
(where ldes(p) := 0 for p = (+ … + − … −))
lind(p) := max{1 ≤ i ≤ n | p_{i} = +1, p_{i+1} = −1}
Des(p^{−1}) := {1 ≤ i ≤ n − 1 | p_{2n−i} = +1, p_{2n−i+1} = −1}

Theorem 1.2.

∑_{π∈T_{n}} q^{ldes(π)} = ∑_{p∈P_{n}} q^{ldes(p)} = ∑_{p∈P_{n}} q^{lind(p)−1}.

Moreover, for any B ⊆ [n − 2],

∑_{π∈T_{n}(B)} q^{ldes(π)} = ∑_{p∈P_{n}(B)} q^{ldes(p)} = ∑_{p∈P_{n}(B)} q^{lind(p)−1},

where T_{n}(B) is as in Theorem 1.1 and

P_{n}(B) := {p ∈ P_{n} | 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 S_{n} are equal if n is even, and differ (up to a sign) by a Catalan number if n is odd. Refined sign balance (i.e., a generating function taking into account the signs of permutations) was investigated by Désarménien and Foata [6] and by Wachs [26]. A beautiful formula for the signed Mahonian (i.e., the sign-and-major-index enumerator on S_{n}) was found by Simion and Gessel [26, Cor. 2]; see also [2].

The last descent statistic is a T_{n}-analogue of the major index on S_{n}, as demonstrated by Theorem 1.1 above; see also the discussion in Section 6. Thus, a T_{n}-analogue of the signed Mahonian on S_{n} is the sum

∑_{π∈T_{n}} sign(π)q^{ldes(π)}.

For this sum we prove

Theorem 1.3.

∑_{π∈T_{2n+1}} sign(π) · q^{ldes(π)} = ∑_{π∈T_{n}} q^{2·ldes(π)}  (n ≥ 0),
∑_{π∈T_{2n}} sign(π) · q^{ldes(π)} = (1 − q) ∑_{π∈T_{n}} q^{2·ldes(π)}  (n ≥ 1).

This result refines (and is actually implicit in) some results in [23]. Our approach is different 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 refinements:

(1) A. Reifegerste gave a bivariate refinement [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

Define the multivariate generating function

(1)  f_{n}(t̄, x, y, z) := ∑_{π∈T_{n}} t_{Des(π^{−1})}x^{inv(π)}y^{ldes(π)}z^{lind(π)},

where t̄= (t_{1}, t_{2}, …) and t_{D} := ∏_{i∈D} t_{i} for D ⊆ [n − 1].

Theorem 2.1. (Recursion Formula)

f_{1}(t̄, x, y, z) = z,

and, for n ≥ 2,

(x − yz)f_{n}(t̄, x, y, z) = t_{n−1}x^{n}yz · f_{n−1}(t̄, x, yz/x, 1)
+ (1 − t_{n−1})x^{n}yz · f_{n−1}(t̄, x, 1, yz/x)
+ (x − yz)z^{n} · f_{n−1}(t̄, x, y, 1)
− xy^{n}z^{n} · f_{n−1}(t̄, x, 1, 1).

Proof. The case n = 1 is clear. Assume n ≥ 2. Given a permutation

π = (π(1), …, π(n − 1)) ∈ T_{n−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)) ∈ S_{n}.

Clearly, a necessary and sufficient condition for π̄ ∈ T_{n} is that π has no descent after the kth place, i.e.,

(2)  ldes(π) ≤ k ≤ n − 1.

If π has no descents, i.e. π = id, this still holds with ldes(π) := 0. The new statistics for π̄ are:

inv(π̄) = inv(π) + (n − 1 − k)
ldes(π̄) = \begin{cases}k + 1, & if k < n − 1; \\ ldes(π), & if k = n − 1. \end{cases}
lind(π̄) = k + 1
Des(π̄^{−1}) = \begin{cases}Des(π^{−1}), & if π^{−1}(n − 1) ≤ k; \\ Des(π^{−1}) ∪ \{n − 1\}, & if k < π^{−1}(n − 1). \end{cases}

Note that, for any π ∈ T_{n−1},

ldes(π) ≤ π^{−1}(n − 1) ≤ n − 1;

321-AVOIDING PERMUTATIONS 5

and, actually, exactly one of the following two cases holds: either

ldes(π) = π^{−1}(n − 1) < n − 1 (if n − 1 is not the last digit in π) or

ldes(π) < π^{−1}(n − 1) = n − 1 (if n − 1 is the last digit in π). We can therefore compute

f_{n} = f_{n}(t̄, x, y, z)
= ∑_{π∈T_{n−1}} ∑_{k=ldes(π)}^{n−1} t_{Des(π̄^{−1})}x^{inv(π̄)}y^{ldes(π̄)}z^{lind(π̄)}
= ∑_{π∈T_{n−1}} t_{Des(π^{−1})}x^{inv(π)} · [ ∑_{k=ldes(π)}^{π^{−1}(n−1)−1} t_{n−1}x^{n−1−k}y^{k+1}z^{k+1}

+ ∑_{k=π^{−1}(n−1)}^{n−2} x^{n−1−k}y^{k+1}z^{k+1} + y^{ldes(π)}z^{n}]

= ∑_{π∈T_{n−1}} t_{Des(π^{−1})}x^{inv(π)} · [t_{n−1}x^{n−1}yz ∑_{k=ldes(π)}^{π^{−1}(n−1)−1}(yz/x)^{k}

+ x^{n−1}yz ∑_{k=π^{−1}(n−1)}^{n−2}(yz/x)^{k} + y^{ldes(π)}z^{n}]

= (1 − yz/x)^{−1} ∑_{π∈T_{n−1}} t_{Des(π^{−1})}x^{inv(π)} ·
· [t_{n−1}x^{n−1}yz ((yz/x)^{ldes(π)} − (yz/x)^{π^{−1}(n−1)})

+ x^{n−1}yz ((yz/x)^{π^{−1}(n−1)} − (yz/x)^{n−1}) + y^{ldes(π)}z^{n}(1 − yz/x)]

= (1 − yz/x)^{−1}[t_{n−1}x^{n−1}yzf_{n−1}(t̄, x, yz/x, 1)

+ (1 − t_{n−1})x^{n−1}yzf_{n−1}(t̄, x, 1, yz/x) − y^{n}z^{n}f_{n−1}(t̄, x, 1, 1)

+ (1 − yz/x)z^{n}f_{n−1}(t̄, x, y, 1)] .

Multiply both sides by (x − yz) to get the claimed recursion. □

Corollary 2.2. The first few values of f_{n} are:

f_{1}(t̄, x, y, z) = z,
f_{2}(t̄, x, y, z) = z^{2} + t_{1}xyz,
f_{3}(t̄, x, y, z) = z^{3} + t_{1}(x^{2}y^{2}z^{2} + xyz^{3}) + t_{2}(x^{2}yz + xy^{2}z^{2}),
f_{4}(t̄, x, y, z) = z^{4} + t_{1}(x^{3}y^{3}z^{3} + x^{2}y^{2}z^{4} + xyz^{4})

+ t_{2}(x^{4}y^{2}z^{2} + x^{3}y^{3}z^{3} + x^{2}y^{3}z^{3} + x^{2}yz^{4} + xy^{2}z^{4}), + t_{3}(x^{3}yz + x^{2}y^{2}z^{2} + xy^{3}z^{3}) + t_{1}t_{3}(x^{3}y^{2}z^{2} + x^{2}y^{3}z^{3}).

3. Equidistribution of ldes and lind −1

In this section we prove Theorem 1.1. Note. Most of the permutations π ∈ T_{n}, namely those with π(n) ≠ n, satisfy lind(π) = ldes(π). Nevertheless, the equidistributed parameters are not ldes and lind but rather ldes and lind −1. Note. T_{n}(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:

qf̂_{n}(t̄, 1, q, 1) = f̂_{n}(t̄, 1, 1, q),

where f̂ denotes f under the additional substitution t_{n−1} = 1. This clearly holds for n = 1 (as well as for n = 2, 3, 4, by Corollary 2.2). By Theorem 2.1, for n ≥ 2:

(1 − yz)f̂_{n}(t̄, 1, y, z) = yzf_{n−1}(t̄, 1, yz, 1) + (1 − yz)z^{n}f_{n−1}(t̄, 1, y, 1)
− y^{n}z^{n}f_{n−1}(t̄, 1, 1, 1).

Letting y = q and z = 1 gives

(1 − q)f̂_{n}(t̄, 1, q, 1) = qf_{n−1}(t̄, 1, q, 1) + (1 − q)f_{n−1}(t̄, 1, q, 1)
− q^{n}f_{n−1}(t̄, 1, 1, 1)
= f_{n−1}(t̄, 1, q, 1) − q^{n}f_{n−1}(t̄, 1, 1, 1),

whereas letting y = 1 and z = q yields

(1 − q)f̂_{n}(t̄, 1, 1, q) = qf_{n−1}(t̄, 1, q, 1) + (1 − q)q^{n}f_{n−1}(t̄, 1, 1, 1)
− q^{n}f_{n−1}(t̄, 1, 1, 1)
= qf_{n−1}(t̄, 1, q, 1) − q^{n+1}f_{n−1}(t̄, 1, 1, 1).

This completes the proof. □

4. Sign Balance of T_{n}

In this section we prove Theorem 1.3. Proof of Theorem 1.3. Substituting t̄= (1, 1, …), z = 1, and x = −1 in the generating function (1), denote

g_{n}(−1, y) := f_{n}(¯1, −1, y, 1) = ∑_{π∈T_{n}}(−1)^{inv(π)}y^{ldes(π)} (n ≥ 1).

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:

g_{n}(1, y) := f_{n}(¯1, 1, y, 1) = ∑_{π∈T_{n}} y^{ldes(π)} (n ≥ 1).

Let g_{0}(1, y) := 1. We have to prove that

g_{2n+1}(−1, y) = g_{n}(1, y^{2}) (n ≥ 0),

and

g_{2n}(−1, y) = (1 − y)g_{n}(1, y^{2}) (n ≥ 1).

By Theorem 2.1, the polynomial g_{n}(−1, y) satisfies the recursion formula

(−1 − y)g_{n}(−1, y) = (−1)^{n}yg_{n−1}(−1, −y) + (−1 − y)g_{n−1}(−1, y)
+ y^{n}g_{n−1}(−1, 1).

Clearly,

g_{1}(−1, y) = 1 = g_{0}(1, y^{2}),

and also

g_{2}(−1, y) = 1 − y = (1 − y)g_{1}(1, y^{2}).

We can proceed by induction. If

g_{2n}(−1, y) = (1 − y)g_{n}(1, y^{2}),

then

(−1 − y)g_{2n+1}(−1, y) = −yg_{2n}(−1, −y) + (−1 − y)g_{2n}(−1, y)

+ y^{2n+1}g_{2n}(−1, 1)

= −y(1 + y)g_{n}(1, y^{2}) + (−1 − y)(1 − y)g_{n}(1, y^{2})

+ 0

= (−1 − y)g_{n}(1, y^{2}),

so that

g_{2n+1}(−1, y) = g_{n}(1, y^{2}).

This, in turn, implies

(−1 − y)g_{2n+2}(−1, y) = yg_{2n+1}(−1, −y) + (−1 − y)g_{2n+1}(−1, y)
+ y^{2n+2}g_{2n+1}(−1, 1)
= yg_{n}(1, y^{2}) + (−1 − y)g_{n}(1, y^{2}) + y^{2n+2}g_{n}(1, 1)
= −g_{n}(1, y^{2}) + y^{2n+2}g_{n}(1, 1),

and therefore

g_{2n+2}(−1, y) = \frac{g_{n}(1, y^{2}) − y^{2n+2}g_{n}(1, 1)}{1 + y} = (1 − y)h_{n}(y^{2}),

where

h_{n}(q) = \frac{g_{n}(1, q) − q^{n+1}g_{n}(1, 1)}{1 − q}.

We need to show that

h_{n}(q) = g_{n+1}(1, q).

Indeed, the equation

(1 − q)g_{n+1}(1, q) = g_{n}(1, q) − q^{n+1}g_{n}(1, 1)

follows immediately from Theorem 2.1. □

Corollary 4.1. (equivalent to [23, Prop. 2]) The sign-balance enumerator for T_{n}

g_{n}(−1, 1) := f_{n}(¯1, −1, 1, 1) = ∑_{π∈T_{n}}(−1)^{inv(π)}

is either a Catalan number or zero:

g_{2n+1}(−1, 1) = |T_{n}| = \frac{1}{n + 1} \frac{2n}{n}  (n ≥ 0)
g_{2n}(−1, 1) = 0  (n ≥ 1).

The amazing connection between T_{n}, T_{2n}, and T_{2n+1} calls for further study.

5. Dyck Paths

Let P_{n} be the set of Dyck paths of length 2n. Thus, each p ∈ P_{n} is a sequence (p_{1}, …, p_{2n}) of n “+1”s and n “−1”s, with nonnegative initial partial sums:

p_{1} + ⋯ + p_{i} ≥ 0 (∀i).

Of course, p_{1} + ⋯ + p_{2n} = 0 by definition.

A peak of a Dyck path p = (p_{1}, …, p_{2n}) ∈ P_{n} is an index 1 ≤ i ≤ 2n − 1 such that p_{i} = +1 and p_{i+1} = −1. Let Peak(p) be the set of all peaks of p. Define the Descent set of p to be

Des(p) := {1 ≤ i ≤ n − 1 | i ∈ Peak(p)}.

Define the inverse path p^{−1} ∈ P_{n} to be

p^{−1} := (−p_{2n}, …, −p_{1}),

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 ϕ : T_{n} → P_{n} such that, if π ∈ T_{n} and p := ϕ(π) ∈ P_{n}, then

Des(p) = Des(π)

and

Des(p^{−1}) = Des(π^{−1}).

Proof. We shall define the bijection ϕ : T_{n} → P_{n} in three steps.

First, let ϕ_{1} : T_{n} → SY T_{2}(n) be the Robinson-Schensted correspondence, where SY T_{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) = \binom{1 3 4 1 2 5}{2 5 , 3 4} .

Next, define ϕ_{2} : SY T_{2}(n) → SY T (n, n), where SY T (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 obtained by rotating P by 180^{0} and replacing each entry 1 ≤ j ≤ n of P by 2n + 1 − j. Example.

ϕ_{2} \binom{1 3 4 1 2 5}{2 5 , 3 4} = 1 2 5 6 9 3 4 7 8 10

Finally, define ϕ_{3} : SY T (n, n) → P_{n} 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} (\begin{matrix}1 & 2 & 5 & 6 & 9 \\ 3 & 4 & 7 & 8 & 10 \end{matrix}) = (+ + − − + + − − +−).

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}} (P, Q) ⟼^{ϕ_{2}} T ⟼^{ϕ_{3}} p,

then

π^{−1} ⟼^{ϕ_{1}} (Q, P) ⟼^{ϕ_{2}} T^{−1} ⟼^{ϕ_{3}} p^{−1}.

Here T^{−1} is the tableau obtained from T ∈ SY T (n, n) by a 180^{0} rotation and replacement of each entry 1 ≤ j ≤ 2n by 2n + 1 − j.

For a standard two-rowed Young tableau P of size n define:

Des(P) := {1 ≤ i ≤ n − 1 | i is in row 1 and i + 1 is in row 2 of P }.

For T ∈ SY T (n, n) (of size 2n) define

Des_{1}(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 π ∈ T_{n},

Des(π) = Des(Q) = Des_{1}(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) = Des_{1}(T^{−1}) = Des(p^{−1}).

This completes the proof. □ Note. The bijection ϕ : T_{n} → P_{n} 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 = (p_{1}, …, p_{2n}) ∈ P_{n}, let

ldes(p) := max Des(p) = max{1 ≤ i ≤ n − 1 | p_{i} = +1, p_{i+1} = −1}.

If Des(p) = ∅, i.e., if p = (+ …+− … −) is the “unimodal path”, we define ldes(p) := 0.

Define also

lind(p) := max{1 ≤ i ≤ n | p_{i} = +1, p_{i+1} = −1}.

In other words,

lind(p) = \begin{cases}n, & if n ∈ Peak(p); \\ ldes(p), & otherwise. \end{cases}

Lemma 5.2. Let

π ⟼^{ϕ_{1}} (P, Q) ⟼^{ϕ_{2}} T ⟼^{ϕ_{3}} 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 definition of ϕ_{2}.

Similarly for conditions 3 and 4, by the definitions of ϕ_{3} and of Peak(p).

□

Lemma 5.3. If π ∈ T_{n} and p := ϕ(π) ∈ P_{n}, then

ldes(p) = ldes(π)

and lind(p) = lind(π).

Proof. The first 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 definition.)

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 definition, lind(p) = ldes(p). Thus

lind(p) = ldes(p) = ldes(π) = lind(π),

as claimed. □

Proof of Theorem 1.2. Combine Lemmas 5.1 and 5.3 with Theorem 1.1.

□

6. Final Remarks

The quotient P_{n}/⟨QS_{n}⟩ of the polynomial ring P_{n} = Q[x_{1}, …, x_{n}] 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 ∈ P_{n}, let

tail(p) := 2n − max{i | p_{i} = +1, p_{i+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 P_{n}/⟨QS_{n}⟩ (graded by total degree) is

∑_{p∈P_{n}} q^{n−tail(p)} = ∑_{k=0}^{n−1} \frac{n − k}{n + k} \frac{n + k}{k} q^{k}.

Corollary 6.2. The Hilbert series of the quotient P_{n}/⟨QS_{n}⟩ (graded by total degree) is equal to

∑_{π∈T_{n}} q^{ldes(π)}.

Proof. By the definitions in Section 5 above, for every Dyck path p ∈ P_{n},

tail(p) = 2n − max Peak(p) = min Des(p^{−1}),

with the convention min ∅ := n. Thus, by Lemma 5.1, if π = ϕ^{−1}(p) ∈ T_{n} then tail(p) = min Des(π^{−1}). Now, define a bijection ψ : T_{n} → T_{n} by

ψ(π) := w_{0}π^{−1}w_{0} (∀π ∈ T_{n}),

where w_{0} = n … 21 is the longest element in S_{n}. If

π ⟼^{ψ} π̂ ⟼^{ϕ} p

then clearly

tail(p) = min Des(π̂^{−1}) = n − max Des(π) = n − ldes(π).

We conclude that

∑_{p∈P_{n}} q^{n−tail(p)} = ∑_{π∈T_{n}} q^{ldes(π)}.

□

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

∑_{π∈S_{n}} q^{maj(π)},

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

Problem 6.3. Find algebraic interpretations and proofs for Theorems 1.1 and 1.3.

For a different 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 S_{n}, Adv. Math. 181 (2004), 353–367.

[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ésarménien 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 refined restricted permutations, J. Combin.

Theory Ser. A, to appear, <http://arXiv.org/abs/math.CO/0212328>.

[9] D. Foata and M.-P. Schützenberger, 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.

[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, Addison-Wesley, 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, Refined sign-balance on 321-avoiding permutations, Europ. J. Com-

    bin. to appear, <http://arXiv.org/abs/math.CO/0305327>.

[19] V. Reiner, D. Stanton and D. White, The cyclic sieving phenomenon, J. Combin. Theory Ser. A, to appear.

[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.

[25] R. P. Stanley, Some remarks on sign-balanced and maj-balanced posets, Adv. Appl.

    Math., to appear, <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.