Kazhdan-Lusztig and R-polynomials, Young’s lattice, and Dyck partitions ^{1}

Francesco Brenti^{2} Dipartimento di Matematica Universitá di Roma “Tor Vergata” Via della Ricerca Scientifica 00133 Roma, Italy

1 Introduction

In their fundamental paper [9] Kazhdan and Lusztig defined, for every Coxeter group W, a family of polynomials, indexed by pairs of elements of W, which have become known as the Kazhdan-Lusztig polynomials of W (see, e.g., [8], Chap. 7). These polynomials are intimately related to the Bruhat order of W and to the geometry of Schubert varieties, and are of fundamental importance in representation theory. In order to prove the existence of these polynomials Kazhdan and Lusztig defined another family of polynomials (see [9], §2) which are now known as the Rpolynomials of W (see, e.g., [8], §7.5). Their importance stems mainly from the fact that their knowledge is equivalent to that of the Kazhdan-Lusztig polynomials.

In 1987 Deodhar [5] introduced parabolic analogues of the Kazhdan-Lusztig and R-polynomials. These polynomials are related to their ordinary counterparts in several ways (see, e.g., §2). In particular, one type of parabolic Kazhdan-Lusztig and Rpolynomials equals an alternating sum, over the corresponding parabolic subgroup, of the ordinary ones. Aside from these connections, the parabolic Kazhdan-Lusztig polynomials also play a direct role in the theories of generalized Verma modules ([4]), tilting modules ([13], [14]), quantized Schur algebras ([17]), and in the representation theory of the Lie algebra gl_{n} ([11]).

Our purpose in this paper is to study the maximal parabolic Kazhdan-Lusztig and R-polynomials of the symmetric group. Our main results are explicit combinatorial product formulas for these polynomials. These formulas imply, in particular, that the polynomials are combinatorial invariants, and that the coefficients of the Kazhdan-Lusztig ones are nonnegative, thus verifying in this case a widely held belief (see, e.g., [11, §1]). The combinatorial formulas are most naturally stated in terms of Young’s lattice, and the one for the Kazhdan-Lusztig polynomials depends on a new combinatorial concept, namely a class of skew partitions which we call (for very natural reasons) Dyck partitions (see §4). These skew partitions possess remarkable combinatorial and enumerative properties which make them interesting also in their own right, and are closely related to Dyck paths, which have been widely studied in combinatorics (see, e.g., [7]).

11991 Mathematics Subject Classification: Primary 05E99; Secondary 20F55.

2Partially supported by GNSAGA of CNR and by MURST.

The organization of the paper is as follows. In the next section we collect some definitions and results that are needed in the rest of this work. In section 3 we prove a combinatorial product formula for the maximal parabolic R-polynomials. We give two statements of this result, one in terms of permutations (Theorem 3.1) and one in terms of partitions (Corollary 3.4), and derive some consequences of it. In §4 we introduce the main new combinatorial concept of this work, namely Dyck partitions, and study some of its basic properties. These are the cornerstones of the proof of our main result in the following section. In section 5 we prove our main theorem, namely an explicit combinatorial product formula for the maximal parabolic Kazhdan-Lusztig polynomials (Theorem 5.1) and derive some consequences of it, such as the fact that the polynomials are combinatorial invariants (Corollary 5.6). Finally, in §6, we give some further consequences of our results. These include some identities for the ordinary Kazhdan-Lusztig and R-polynomials, a combinatorial invariance result for the ordinary Kazhdan-Lusztig polynomials of Grassmannian permutations, and some further combinatorial and enumerative properties of Dyck partitions.

2 Notation, Definitions, and preliminaries

In this section we collect some definitions, notation and results that will be used in the rest of this work. We let P =^{def} {1, 2, 3, …} , N=^{def}P ∪{0}, Z be the set of integers, and Q be the set of rational numbers; for a ∈N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅). The cardinality of a set A will be denoted by |A|. Given a polynomial P (q), and i ∈ Q, we denote by [q^{i}](P (q)) the coefficient of q^{i} in P (q) (so [q^{i}](P (q)) = 0 unless i ∈ N).

Given a set T we let S(T) be the set of all bijections π : T → T, and S_{n} =^{def} S([n]). If σ ∈ S_{n} then we write σ = σ_{1} … σ_{n} to mean that σ(i) = σ_{i}, for i = 1, …, n. If σ ∈ S_{n} then we will also write σ in disjoint cycle form (see, e.g., [15], p.17) and we will usually omit to write the 1-cycles of σ. For example, if σ = 365492187 then we also write σ = (9, 7, 1, 3, 5)(2, 6). Given σ, τ ∈ S_{n} we let στ =^{def} σ ∘ τ (composition of functions) so that, for example, (1, 2)(2, 3) = (1, 2, 3).

We follow Chapter 3 of [15] for poset notation and terminology. In particular, given a poset (P, ≤) and u, v ∈ P we let [u, v] =^{def} {z ∈ P : u ≤ z ≤ v} and call this an interval of P. We say that v covers u, denoted u < v (or, equivalently, that u is covered by v) if |[u, v]| = 2. The Hasse graph of P is the graph having P as vertex set and {{u, v} ⊆ P : u < v or v < u} as set of edges. If P has a minimum element, denoted ˆ0, then we call a subset of the form [ˆ0, u], for u ∈ P, a lower interval of P. Similarly, we define an upper interval. Given any Q ⊆ P we will always consider Q as a poset with the partial ordering induced by P and call Q a subposet of P. If u, v ∈ P are such that {z ∈ P : z ≥ u, z ≥ v} has a minimum element then we call it the join of u and v. Similarly, we define the meet of u and v if {z ∈ P : z ≤ u, z ≤ v} has a maximum element. We say that z ∈ P is join-irreducible (respectively, minimal) if it covers at most one element (respectively, no elements) of P. Similarly, we define meet-irreducible and maximal. Given two posets P and Q we write P ≅ Q to mean that they are isomorphic as posets.

We follow §7.2 of [16] for any undefined notation and terminology concerning partitions. By an (integer) partition we mean a sequence of positive integers λ = (λ_{1}, …, λ_{k}) such that λ_{1} ≥ λ_{2} ≥ … ≥ λ_{k}. We identify a partition λ with its diagram,

{(i, j) ∈ P^{2} : 1 ≤ i ≤ k, 1 ≤ j ≤ λ_{i}},

and consider λ as a poset with the partial ordering induced by P^{2} (where P^{2} has the product ordering induced by the natural ordering on P). For this reason we draw the diagram of a partition λ rotated counterclockwise by \frac{3}{4}π radians with respect to the usual (Anglophone) convention (see, e.g., [15, §1.3]). So, for example, the diagram of (7, 4, 2, 1) is illustrated in Figure 1.

[figure]

Figure 1

We call the elements of P^{2}, and hence of λ, cells. Expressions such as “to the left of”, or “directly above”, always refer to these rotated diagrams. We define the level of a cell (i, j) ∈ P^{2} by lv((i, j)) =^{def} i + j. We denote by P the set of all integer partitions. We will always assume that P is partially ordered by set inclusion. It is well known, and not hard to see, that this makes P into a lattice, usually called Young’s lattice (see, e.g., [16, §7.2]). Given n ∈ P and i ∈ [n − 1] we let

P(n, i) =^{def} {μ ∈ P : μ ⊆ (n − i)^{i}}. Given λ = (λ_{1}, …, λ_{k}) ∈ P we let d(λ) be the

length of the Durfee square of λ, so

d(λ) =^{def} max {i ∈ [k] : λ_{i} ≥ i}.  (1)

Let μ, λ ∈ P, μ ⊆ λ. We then call λ \ μ a skew partition. Note that, in poset theoretic language, partitions (respectively, skew-partitions) are the finite order ideals (respectively, finite convex subsets) of P^{2}. Given a skew partition η ⊆ P^{2} its conjugate is

η′ =^{def} {(j, i) ∈ P^{2} : (i, j) ∈ η}.

A connected (by which we mean “rookwise connected” so, e.g., (2, 1) \ (1) is not connected) skew partition is uniquely determined, up to translation, by the two ordered sequences of the lengths of the sides of the “polygon” that it determines. For example, the skew partition depicted in Figure 2 is uniquely determined by the sequences (4, 2, 1, 2, 2, 1, 1, 3) and (3, 1, 1, 1, 1, 2, 2, 1, 1, 3) (in this order). We will use this “polygon notation” for skew partitions in §5. Let θ be a connected skew partition, and consider θ as a subposet of P^{2}. We say that a cell x of θ is an upper peak (respectively, lower valley) of θ if it is maximal (respectively, minimal). We call an element x ∈ θ an upper valley of θ if x is covered by exactly two elements of θ whose join is not in θ. Similarly, we define a lower peak.

We say that a skew partition is a border strip (also called a ribbon) if it contains no 2 × 2 square of cells. For brevity, we call a connected border strip a cbs. Let λ, μ, ν ∈ P be such that μ ⊆ ν ⊆ λ. We then say that λ \ ν is a final segment of λ \ μ. The outer border strip θ of λ \ μ is the largest final segment of λ \ μ which is a border strip. In other words, a cell of λ \ μ is in θ if and only if there is no cell of λ \ μ directly above it. For example, the cells of the outer border strip of the skew partition illustrated in Figure 2 are numbered from 1 to 15. We will usually number the cells of θ consecutively from left to right in this way, and identify them with their corresponding number. So, for example, 1 is the leftmost cell of θ, and if x ∈ θ, x > 1, then x − 1 is the cell of θ immediately to the left of x.

[figure: 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15]

Figure 2

In a similar way, we define the inner border strip η of λ \ μ as the cells of λ \ μ which have no cells of λ \ μ directly below them.

Given two skew partitions ρ, ν ⊂ P^{2} we write ρ ≈ ν if ρ is a translate of ν. The verification of the following observation is left to the reader.

Proposition 2.1 Let λ, μ ∈ P, μ ⊆ λ, and θ, η be the outer and inner border strips of λ \ μ, respectively. Then (λ \ μ) \ θ ≈ (λ \ μ) \ η.

We follow [8] for general Coxeter groups notation and terminology. In particular, given a Coxeter system (W, S) and σ ∈ W we denote by l(σ) the length of σ in W, with respect to S, and we let D(σ) =^{def} {s ∈ S : l(σs) < l(σ)}. We denote by e the identity of W, and we let T =^{def} {σsσ^{−1} : σ ∈ W, s ∈ S} be the set of reflections of W. Given J ⊆ S we let W_{J} be the parabolic subgroup generated by J and

W^{J} =^{def} {σ ∈ W : l(sσ) > l(σ) for all s ∈ J}.

Note that W^{∅} = W. If W_{J} is finite then we denote by w_{0}^{J} its longest element. We will always assume that W^{J} is partially ordered by (strong) Bruhat order. Recall (see, e.g., [8], §5.9) that this means that x ≤ y if and only if there exist r ∈ N and t_{1}, …, t_{r} ∈ T such that t_{r} … t_{1} x = y and l(t_{i} … t_{1} x) > l(t_{i−1} … t_{1}x) for i = 1, …, r. Given u, v ∈ W^{J}, u ≤ v, we let

[u, v]_{J} =^{def} {z ∈ W^{J} : u ≤ z ≤ v},

and consider [u, v]_{J} as a poset with the partial ordering induced by W^{J}.

The following two results are due to Deodhar, and we refer the reader to [5, §§2-3] for their proofs.

Theorem 2.2 Let (W, S) be a Coxeter system, and J ⊆ S. Then, for each x ∈ {−1, q}, there is a unique family of polynomials {R_{u,v}^{J,x}(q)}_{u,v∈W^{J}} ⊆ Z[q] such that, for all u, v ∈ W^{J}:

i) R_{u,v}^{J,x}(q) = 0 if u ≰ v;

ii) R_{u,u}^{J,x}(q) = 1;

iii) if u < v and s ∈ D(v) then

R_{u,v}^{J,x}(q) = \{ \begin{matrix}R_{us,vs}^{J,x}(q), & if s ∈ D(u), \\ (q − 1)R_{u,vs}^{J,x}(q) + qR_{us,vs}^{J,x}(q), & if s ∉ D(u) and us ∈ W^{J}, \\ (q − 1 − x)R_{u,vs}^{J,x}(q), & if s ∉ D(u) and us ∉ W^{J}. \end{matrix}

Theorem 2.3 Let (W, S) be a Coxeter system, and J ⊆ S. Then, for each x ∈ {−1, q}, there is a unique family of polynomials {P_{u,v}^{J,x}(q)}_{u,v∈W^{J}} ⊆ Z[q], such that, for all u, v ∈ W^{J}:

i) P_{u,v}^{J,x}(q) = 0 if u ≰ v;

ii) P_{u,u}^{J,x}(q) = 1;

iii) deg(P_{u,v}^{J,x}(q)) ≤ \frac{1}{2} (l(v) − l(u) − 1), if u < v;

iv)

q^{l(v)−l(u)} P_{u,v}^{J,x} (\frac{1}{q}) = ∑_{u≤z≤v} R_{u,z}^{J,x}(q) P_{z,v}^{J,x}(q) ,

if u ≤ v.

The polynomials R_{u,v}^{J,x}(q) and P_{u,v}^{J,x}(q), whose existence is guaranteed by the two previous theorems, are called the parabolic R-polynomials and parabolic Kazhdan-Lusztig polynomials (respectively) of W^{J} of type x. It follows immediately from Theorems 2.2 and 2.3 and from well known facts (see, e.g., [8, §7.5] and [8, §§7.9-11]) that R_{u,v}^{∅,−1}(q) (= R_{u,v}^{∅,q}(q)) and P_{u,v}^{∅,−1}(q) (= P_{u,v}^{∅,q}(q)) are the (ordinary) R-polynomials and Kazhdan-Lusztig polynomials of W which we will denote simply by R_{u,v}(q) and P_{u,v}(q), as customary.

The parabolic Kazhdan-Lusztig and R-polynomials are related to their ordinary counterparts also in the following way.

Proposition 2.4 Let (W, S) be a Coxeter system, J ⊆ S, and u, v ∈ W^{J}. Then we have that

R_{u,v}^{J,x}(q) = ∑_{w∈W_{J}}(−x)^{l(w)}R_{wu,v}(q),

for all x ∈ {−1, q}, and

P_{u,v}^{J,q}(q) = ∑_{w∈W_{J}}(−1)^{l(w)}P_{wu,v}(q).

Furthermore, if W_{J} is finite then

P_{u,v}^{J,−1}(q) = P_{w_{0}^{J} u,w_{0}^{J} v}(q).

A proof of this result can be found in [5] (see Propositions 2.12 and 3.4, and Remark 3.8). Yet another relation (which, however, we will not use) between parabolic and ordinary Kazhdan-Lusztig polynomials is given in [5, Proposition 3.5].

There are two more properties of the parabolic Kazhdan-Lusztig and R-polynomials that we will use and that we recall here for the reader’s convenience. Proofs of them can be found in [6, Corollary 2.2], and [5, Proposition 3.10].

Proposition 2.5 Let (W, S) be a Coxeter system, and J ⊆ S. Then

q^{l(v)−l(u)}R_{u,v}^{J,x} (\frac{1}{q}) = (−1)^{l(v)−l(u)}R_{u,v}^{J,q−1−x}(q)

for all u, v ∈ W^{J}, and x ∈ {−1, q}.

For u, v ∈ W^{J} let, as customary,

μ(u, v) =^{def} [q^{\frac{1}{2} (l(v)−l(u)−1)}](P_{u,v}^{J,q}(q)).

Proposition 2.6 Let (W, S) be a Coxeter system, J ⊆ S, and u, v ∈ W^{J}, u ≤ v. Then for each s ∈ D(v) we have that

P_{u,v}^{J,q}(q) = P̃ − ∑_{\{u≤w≤vs: ws<w\}} μ(w, vs)q^{\frac{l(v)−l(w)}{2}} P_{u,w}^{J,q}(q)

where

P̃ = \{ \begin{matrix}P_{us,vs}^{J,q} + qP_{u,vs}^{J,q}, & if us < u, \\ qP_{us,vs}^{J,q} + P_{u,vs}^{J,q}, & if u < us ∈ W^{J}, \\ 0, & if u < us ∉ W^{J}. \end{matrix}

Our purpose in this paper is to study the maximal parabolic Kazhdan-Lusztig and R-polynomials of the symmetric group S_{n}. Therefore, from now on we fix n ∈ P and i ∈ [n − 1], and we let W =^{def} S_{n}, s_{i} =^{def} (i, i + 1) for i = 1, …, n − 1, S =^{def} {s_{1}, …, s_{n−1}}, and J =^{def} S \ {s_{i}}. It is well known that (S_{n}, S) is a Coxeter system of type A_{n−1} (see, e.g., [8]) and that the following characterization holds (see, e.g., [12]).

Proposition 2.7 Let v ∈ S_{n}. Then

l(v) = |{(i, j) ∈ [n]^{2} : i < j, v(i) > v(j)}|

and

D(v) = {s_{i} ∈ S : v(i) > v(i + 1)}.

Given v ∈ W^{J} we associate to v the partition

Λ(v) =^{def} (v^{−1}(i) − i, …, v^{−1}(2) − 2, v^{−1}(1) − 1).  (2)

The following is well known (see, e.g., [12]).

Proposition 2.8 The map Λ defined by (2) is a bijection between W^{J} and P(n, i). Furthermore u ≤ v in W^{J} if and only if Λ(u) ⊆ Λ(v).

We will find it sometimes convenient to identify a partition λ ∈ P(n, i) with a lattice path, with (1, 1) and (1, −1) steps, starting at (0, 0) and ending at (n, 2i − n) (equivalently, having n steps and exactly i (1, 1)-steps). We call a (1, 1)-step (respectively, (1, −1)-step) an up-step (respectively, down-step). Given j ∈ [n − 1] we say that λ has a peak at j if the j-th step of λ is up and its (j + 1)-st step is down. Note that there is an obvious bijection between the peaks of λ (as a path) and the upper peaks of λ (as a partition). For example, if λ = (4, 3, 2, 2, 1) ∈ P(9, 5) then the associated path is the one shown in Figure 3 and it has peaks at 1, 3, 6, and 8. Note that this bijection between partitions and paths depends on n and i. For example, the partition (4, 3, 2, 2, 1) corresponds to the path in Figure 4 if n = 12 and i = 6. Since n and i are fixed throughout this work, this will cause no confusion.

[figure]

Figure 3: the lattice path corresponding to (4, 3, 2, 2, 1) if n = 9 and i = 5.

[figure]

Figure 4: the lattice path corresponding to (4, 3, 2, 2, 1) if n = 12 and i = 6.

The following elementary lemma is certainly well known. However, for lack of an adequate reference, and because we will use it often, we give a proof here.

Lemma 2.9 Let v ∈ W^{J}, and j ∈ [n − 1]. Then s_{j} ∈ D(v) if and only if Λ(v) has a peak at n − j.

Proof. By Proposition 2.7 we have that s_{j} ∈ D(v) if and only if v(j) > v(j + 1). On the other hand Λ(v) (as a path) has a peak at n − j if and only if its (n − j)-th step is up and its (n − j + 1)-th step is down. But the k-th step of Λ(v) is an up step if and only if

k ∈ {n + 1 − v^{−1}(i), n + 1 − v^{−1}(i − 1), …, n + 1 − v^{−1}(1)}.  (3)

Therefore Λ(v) has a peak at n − j if and only if

j = v^{−1}(k) − 1  (4)

for some k ∈ [i], and

j ≠ v^{−1}(k)  (5)

for all k ∈ [i]. But if this is true then, clearly, v(j) > i ≥ v(j + 1).

Conversely, if v(j) > v(j + 1) then, since v ∈ W^{J}, we have that v(j) ∉ [i] and v(j + 1) ∈ [i], which implies (5) and (4), and therefore that Λ(v) has a peak at n − j. □

3 Parabolic R-polynomials

In this section we prove an explicit combinatorial product formula for the maximal parabolic R-polynomials of the symmetric group. We give two formulations of this result, one in terms of permutations and one in terms of partitions, and we derive some consequences of it. Recall that throughout this work we fix n ∈ P and i ∈ [n − 1], and we let J =^{def} S \ {s_{i}}.

Let u, v ∈ W^{J}, u ≤ v. For j ∈ [n] let

a_{j}(u, v) =^{def} |{r ∈ u^{−1}([i]) : r < j}| − |{r ∈ v^{−1}([i]) : r < j}|.  (6)

For example, if n = 9, i = 5, u = 126347589, and v = 671823945 then

(a_{1}(u, v), …, a_{9}(u, v)) = (0, 1, 2, 1, 2, 2, 1, 2, 1).  (7)

Note that it follows easily from Proposition 2.8 that a_{j}(u, v) ≥ 0 for j = 1, …, n if and only if u ≤ v, and that a_{j}(u, v) > 0 if j ∈ v^{−1}([i]) \ u^{−1}([i]) and u ≤ v. Also note that, if u ∈ W^{J} and j ∈ [n], then

|\{r ∈ u^{−1}([i]) : r < j\}| = \{ \begin{matrix}u(j) − 1, & if j ∈ u^{−1}([i]), \\ j + i − u(j), & if j ∉ u^{−1}([i]). \end{matrix}

This may be used to obtain a more explicit formula for a_{j}(u, v), if desired.

Theorem 3.1 Let u, v ∈ W^{J}, u ≤ v. Then

R_{u,v}^{J,−1}(q) = q^{l(v)−l(u)} ∏_{j∈v^{−1}([i])\u^{−1}([i])}(1 − q^{−a_{j}(u,v)}).  (8)

Proof. Let, for brevity, R_{u,v}^{J}(q) =^{def} R_{u,v}^{J,−1}(q), and D_{i}(u, v) =^{def} v^{−1}([i]) \ u^{−1}([i]).

We proceed by induction on l(v), the result being trivially true if u = v = e. So suppose that l(v) ≥ 1. Let s = (k, k + 1) be such that s ∈ D(v). Note that, since v ∈ W^{J}, this implies that k + 1 ∈ v^{−1}([i]) and k ∉ v^{−1}([i]). We have three cases to consider.

a) s ∈ D(u).

Since u ∈ W^{J} this implies that k ∉ u^{−1}([i]) and k + 1 ∈ u^{−1}([i]). Therefore (us, vs ∈ W^{J}, and) D_{i}(u, v) = D_{i}(us, vs) and a_{j}(u, v) = a_{j}(us, vs) for all j ∈ [n].

Hence, by Theorem 2.2 and our induction hypothesis,

R_{u,v}^{J}(q) = R_{us,vs}^{J}(q)
= q^{l(vs)−l(us)} ∏_{j∈D_{i}(us,vs)}(1 − q^{−a_{j}(us,vs)})
= q^{l(v)−l(u)} ∏_{j∈D_{i}(u,v)}(1 − q^{−a_{j}(u,v)}),

as desired.

b) s ∉ D(u), and us ∉ W^{J}. Then either k, k + 1 ∉ u^{−1}([i]) or k, k + 1 ∈ u^{−1}([i]). In the first case

D_{i}(u, vs) = (D_{i}(u, v) \ {k + 1}) ∪ {k}

and a_{j}(u, v) = a_{j}(u, vs) for j ∈ [n] \ {k + 1}, a_{k+1}(u, v) = a_{k}(u, vs). Therefore, by Theorem 2.2 and our induction hypothesis,

R_{u,v}^{J}(q) = qR_{u,vs}^{J}(q)
= q q^{l(vs)−l(u)} ∏_{j∈D_{i}(u,vs)}(1 − q^{−a_{j}(u,vs)})
= q^{l(v)−l(u)} ∏_{j∈D_{i}(u,v)}(1 − q^{−a_{j}(u,v)}),  (9)

as desired. In the second case D_{i}(u, vs) = D_{i}(u, v) and a_{j}(u, v) = a_{j}(u, vs) for all j ∈ [n] \ {k + 1}, and we again conclude as in (9).

c) s ∉ D(u) and us ∈ W^{J}.

Then k ∈ u^{−1}([i]) and k + 1 ∉ u^{−1}([i]). But

D_{i}(u, vs) = D_{i}(u, v) \ {k + 1},

and a_{j}(u, v) = a_{j}(u, vs) for j ∈ [n] \ {k + 1}. On the other hand

D_{i}(us, vs) = (D_{i}(u, v) \ {k + 1}) ∪ {k},

and

a_{j}(us, vs) = a_{j}(u, v)  (10)

for j ∈ [n] \ {k + 1},

a_{k+1}(u, v) = a_{k+1}(us, vs) + 2.  (11)

Therefore we have from our induction hypothesis that

R_{u,vs}^{J}(q) = q^{l(vs)−l(u)} ∏_{j∈D_{i}(u,vs)}(1 − q^{−a_{j}(u,vs)})
= q^{l(v)−l(u)−1} ∏_{j∈D_{i}(u,v)\{k+1}}(1 − q^{−a_{j}(u,v)})  (12)

and, if us ≤ vs,

R_{us,vs}^{J}(q) = q^{l(vs)−l(us)} ∏_{j∈D_{i}(us,vs)}(1 − q^{−a_{j}(us,vs)})
= q^{l(v)−l(u)−2}(1 − q^{−a_{k}(u,v)}) ∏_{j∈D_{i}(u,v)\{k+1}}(1 − q^{−a_{j}(u,v)}).

Hence, by Theorem 2.2,

R_{u,v}^{J}(q) = ((q − 1)q + q(1 − q^{−a_{k}(u,v)}))q^{l(v)−l(u)−2} ∏_{j∈D_{i}(u,v)\{k+1}}(1 − q^{−a_{j}(u,v)})
= (1 − q^{−a_{k}(u,v)−1})q^{l(v)−l(u)} ∏_{j∈D_{i}(u,v)\{k+1}}(1 − q^{−a_{j}(u,v)}),

and the result follows since a_{k+1}(u, v) = a_{k}(u, v) + 1.

If us ≰ vs then from (10) and (11), and the comments at the beginning of this section we conclude that a_{k+1}(u, v) = 1. Hence, by Theorem 2.2 and (12),

R_{u,v}^{J}(q) = (q − 1)R_{u,vs}^{J}
= (q − 1)q^{l(v)−l(u)−1} ∏_{j∈D_{i}(u,v)\{k+1}}(1 − q^{−a_{j}(u,v)})
= q^{l(v)−l(u)} ∏_{j∈D_{i}(u,v)}(1 − q^{−a_{j}(u,v)}),

and the result again follows.

This completes the induction step and hence the proof. □

We illustrate the preceding theorem with an example. Let n, i, u and v be as in the example preceding Theorem 3.1. Then D_{i}(u, v) = {3, 6, 8, 9} and hence, by (8) and (7),

R_{u,v}^{J,−1}(q) = q^{16−4}(1 − q^{−2})^{3}(1 − q^{−1}) = q^{5}(q^{2} − 1)^{3}(q − 1).

As an immediate consequence of the previous result we obtain a corresponding formula for the other type of maximal parabolic R-polynomials. Corollary 3.2 Let u, v ∈ W^{J}, u ≤ v. Then

R_{u,v}^{J,q}(q) = (−1)^{l(v)−l(u)} ∏_{j∈v^{−1}([i])\u^{−1}([i])}(1 − q^{a_{j}(u,v)}),

where a_{j}(u, v) is defined in (6).

Proof. This follows immediately from Theorem 3.1 and Proposition 2.5. □

Note that, although a nonrecursive formula for the parabolic R-polynomials is given in [5, Theorem 2.11], it does not seem to be easy to deduce Theorem 3.1 or Corollary 3.2 from it.

Because W^{J} is isomorphic, as a poset, to a lower interval in Young’s lattice (by Proposition 2.8), it is natural to rephrase Theorem 3.1 in the language of partitions rather than in that of permutations.

Let μ, λ ∈ P(n, i), with μ ⊆ λ. Think of μ and λ as paths as explained in §2. Then, by Proposition 2.8, the path λ lies (weakly) above the path μ. Let 1 ≤ j ≤ n and consider the j-th step of λ (from the left). We say that such a step is allowable with respect to μ if it is an up-step and the j-th step of μ is a down-step. For example, if n = 18, i = 9, λ = (9, 8, 6, 6, 5, 5, 3, 3, 3), and μ = (4, 3, 3, 2, 2, 2, 1) then the j-th step of λ is allowable with respect to μ exactly if j ∈ {1, 3, 7, 10, 14}. Now let ã_{j}(μ, λ) be the vertical distance (divided by two, since it is always even) between the (right end of the) j-th step of λ and the (right end of the) j-th step of μ.

Proposition 3.3 Let u, v ∈ W^{J}, u ≤ v. Then

a_{j}(u, v) = ã_{n+1−j}(Λ(u), Λ(v))

for j = 1, …, n. Furthermore n + 1 − j ∈ v^{−1}([i]) \ u^{−1}([i]) if and only if the j-th step of Λ(v) is allowable with respect to Λ(u).

Proof. Let 1 ≤ j ≤ n. Clearly, the vertical height of a path λ after j steps, h_{j}(λ), equals the difference between the number of up-steps and that of down-steps among the first j steps of λ. But, by our definitions, the k-th step of λ is an up-step if and only if

k ∈ {n − i + 1 − λ_{1}, n − i + 2 − λ_{2}, …, n − λ_{i}}.

Therefore

h_{j}(λ) = 2|{k ∈ [i] : n − i + k − λ_{k} ≤ j}| − j,

and hence

h_{j}(Λ(v)) = 2|{k ∈ [i] : n + 1 − v^{−1}(i + 1 − k) ≤ j}| − j
= 2|{k ∈ [i] : n + 1 − v^{−1}(k) ≤ j}| − j
= 2(i − |{k ∈ [i] : n + 1 − v^{−1}(k) > j}|) − j.

So

ã_{j}(Λ(u), Λ(v)) = \frac{1}{2} (h_{j}(Λ(v)) − h_{j}(Λ(u)))
= |{k ∈ [i] : u^{−1}(k) < n + 1 − j}| − |{k ∈ [i] : v^{−1}(k) < n + 1 − j}|
= |{r ∈ u^{−1}([i]) : r < n + 1 − j}| − |{r ∈ v^{−1}([i]) : r < n + 1 − j}|
= a_{n+1−j}(u, v),

as desired.

Furthermore, it follows from (3) that the j-th step of Λ(v) is an up-step if and only if j = n + 1 − v^{−1}(k) for some k ∈ [i], which in turn happens if and only if n + 1 − j ∈ v^{−1}([i]). Therefore, the j-th step of Λ(v) is allowable with respect to Λ(u) if and only if n + 1 − j ∈ v^{−1}([i]) \ u^{−1}([i]). □

We can now rephrase Corollary 3.2 in terms of partitions.

Corollary 3.4 Let u, v ∈ W^{J}, u ≤ v. Then

R_{u,v}^{J,q}(q) = (−1)^{|λ\μ|} ∏_{j}(1 − q^{ã_{j}(μ,λ)})  (13)

where μ = Λ(u), λ = Λ(v) and j runs over all the allowable steps of λ with respect to μ. In particular, R_{u,v}^{J,q}(q) depends only on Λ(v) \ Λ(u). □

Because of the preceding corollary we will sometimes write R_{θ}^{J,q}(q), and R_{μ,λ}^{J,q}(q), if θ is a skew partition, and μ, λ ∈ P.

In the case of a lower interval, the formula in Corollary 3.4 takes up a particularly simple form.

Corollary 3.5 Let v ∈ W^{J}. Then

R_{e,v}^{J,q}(q) = (−1)^{|μ|} ∏_{j=1}^{d(μ)}(1 − q^{j}),

where μ = Λ(v) and d(μ) is the length of the Durfee square of μ.

Proof. We know from Corollary 3.4 that

R_{e,v}^{J,q}(q) = (−1)^{|μ|} ∏_{j}(1 − q^{ã_{j}(∅,μ)})  (14)

where j runs over all the allowable steps of μ with respect to ∅. But, clearly, an up step of μ is allowable with respect to ∅ if and only if it is one of the leftmost n − i steps of μ (seen as a path).

Let a be the number of such up steps. Since every up step (among the leftmost n−i steps of μ) increases the vertical distance from ∅ to μ by 2, and every down step (among the leftmost n − i steps of μ) leaves this distance unchanged, we conclude that this vertical distance, after the leftmost n − i steps of μ, is 2a, and that the vertical distance between the j-th allowable step of μ and ∅ is 2j, for j = 1, …, a. Therefore, by (14),

R_{e,v}^{J,q}(q) = (−1)^{|μ|} ∏_{j=1}^{a}(1 − q^{j}).

On the other hand, by the definition (1) of d(μ), the vertical distance between the (n − i)-th step of μ and ∅ is 2d(μ). Hence a = d(μ) and the result follows. □

In the theory of the ordinary R-polynomials an interesting open problem [1] is that of deciding whether any R-polynomial of W can be obtained as the Rpolynomial of a lower interval (i.e., if given u, v ∈ W there is a w ∈ W such that R_{u,v}(q) = R_{e,w}(q)). The last two results show that the analogous question has a negative answer in the maximal parabolic case.

We conclude this section by noting a further consequence of Corollary 3.4 that will be used in §6 to obtain a non-trivial combinatorial property of Dyck partitions (defined in the next section).

Proposition 3.6 Let λ, μ be partitions, μ ⊆ λ. Then

lim_{q→1} (\frac{R_{λ\μ}^{J,q}(q)}{q − 1}) = \{ \begin{matrix}(−1)^{|λ\μ|+1}, & if λ \ μ is a cbs, \\ 0, & otherwise. \end{matrix}  (15)

Proof. Suppose that λ\μ is a cbs. Then it is clear that there is exactly one allowable step of λ with respect to μ (namely, the leftmost step where λ and μ differ) and its vertical distance from the corresponding step of μ is 2. Hence, by (13),

R_{λ\μ}^{J,q}(q) = (−1)^{|λ\μ|}(1 − q)

and the first equality in (15) follows.

Suppose now that λ \ μ is not a cbs. There are two cases to consider.

If λ \ μ is not connected then there are at least two allowable steps of λ with respect to μ (namely, the leftmost steps of each connected component of λ \ μ). Hence, by Corollary 3.4, (1 − q)^{2} divides R_{λ\μ}^{J,q}(q), and the result follows.

If λ \ μ is not a border strip then there is a step of λ that is at a vertical distance of at least 4 from the corresponding step of μ. But this implies that there are at least two allowable steps of λ with respect to μ to the left of this step (since each allowable step increases the vertical distance between corresponding steps of λ and μ by 2, while non-allowable steps weakly decrease it). Therefore, by Corollary 3.4, (1 − q)^{2} divides R_{λ\μ}^{J,q}(q) and the result again follows. □

Corollary 3.4, as well as the well known combinatorial invariance conjecture for Kazhdan-Lusztig polynomials (see, e.g., [8, §8.6]), suggest the question of whether the polynomials R_{u,v}^{J,q}(q) (and hence, by Theorem 2.3 and Proposition 2.5, also P_{u,v}^{J,q}(q), R_{u,v}^{J,−1}(q), and P_{u,v}^{J,−1}(q)) depend only on the poset [u, v]_{J}. Although it is possible to answer this question using the results obtained so far, this is easier to do using those in §5.

4 Dyck partitions

In this section we introduce the main new combinatorial concept of this work, namely Dyck partitions, and study some of its basic properties. These form the cornerstones of the proof of our main result on the parabolic Kazhdan-Lusztig polynomials in the next section. Dyck partitions possess several other interesting combinatorial and enumerative properties, some of which are given in §6.

Let θ ⊂ P^{2} be a connected border strip. We say that θ is a Dyck cbs if it is a “Dyck path” (see, e.g., [16, p. 173]). In other words, it is a Dyck cbs if no cell of θ has level strictly less than that of either the leftmost or rightmost of its cells. In particular, in a Dyck cbs the leftmost and rightmost cells have the same level. For example, the cbs’s in Figures 5 and 6 are Dyck, while those of Figures 7 and 8 are not. It is clear that a cbs is Dyck if and only if its conjugate is Dyck.

[figure]

Figure 5

[figure]

Figure 6

[figure]

Figure 7

[figure]

Figure 8

Given λ, μ ∈ P, μ ⊆ λ, we let (λ \ μ)^{(1)} =^{def} (λ \ μ) \ θ, where θ is the outer border strip of λ \ μ. We now come to the crucial definition of this work. Let η ⊂ P^{2} be a skew partition. We define η to be Dyck in the following inductive way:

i) η is Dyck if and only if each one of its connected components is Dyck;

ii) if η is connected then η is Dyck if and only if:

a) its outer border strip is a Dyck cbs;

b) η^{(1)} is Dyck.

Finally, we define ∅ to be Dyck. So, for example, (4, 4, 4, 3) is not Dyck while (4, 4, 4, 4) \ (1) and (4, 4, 4, 3) \ (1) are Dyck. Note that it follows immediately from our definitions that η is Dyck if and only if η′ is Dyck.

Let η ⊂ P^{2} be a skew partition (not necessarily Dyck). We define the depth of η, denoted dp (η), inductively by letting

dp (η) =^{def} c(θ) + dp (η^{(1)})

(and dp (∅) =^{def} 0), where θ is the outer border strip of η, and c(θ) denotes the number of connected components of θ. So, for example, dp ((4, 4, 4, 3)) = dp ((4, 4, 4, 4) \ (1)) = 3, while dp ((4, 4, 4, 3) \ (1)) = 4. Note that, if η is Dyck, then

dp (η) ≡ |η| (mod 2)

(since a Dyck cbs has always odd cardinality, so c(θ) ≡ |θ| (mod 2)). Also note that dp (η) ≤ |η| for all η, and that dp (η) = 1 if and only if η is a cbs.

We begin with the following simple but fundamental property of Dyck partitions.

Proposition 4.1 Let η be Dyck. Then, below every upper peak of η there is either a lower peak or a lower valley.

Proof. We may clearly assume that η is connected and that |η| ≥ 2. We proceed by induction on |η|.

Let x be an upper peak of η. Since η is Dyck x cannot be the leftmost nor the rightmmost cell of η. Hence x − 1 and x + 1 are exactly one level below that of x. If the cell directly below x is not in η then clearly η has a lower peak below x. So assume that the cell directly below x, call it x^{(1)}, is in η (see Figure 9). Let θ be the outer border strip of η.

[figure: x−1; x; x+1; x^{(1)}]

Figure 9

Then, clearly, x − 1, x, x + 1 ∈ θ and hence x^{(1)} is an upper peak of η^{(1)}. But, since η is Dyck, η^{(1)} is also Dyck. Hence, by induction, there is either a lower peak or a lower valley below x^{(1)}, and therefore below x. □

Let η be a skew partition and x be one of its cells. We denote by d_{η}(x) the number of cells of η that are below x, including x. So, for example, if η is the skew partition depicted in Figure 2 then d_{η}(1) = 1, d_{η}(5) = 3, and d_{η}(9) = 1.

The following technical fact is needed in the proof of the main result of this section.

Lemma 4.2 Let η be Dyck, and x be an upper peak of η. Then

lv(x) ≥ lv(1) + d_{η}(x) − 1,

where 1 is the leftmost cell of the connected component of η that contains x.

Proof. We proceed by induction on d_{η}(x), the result being clear if d_{η}(x) = 1. So suppose d_{η}(x) ≥ 2. Then reasoning as in the proof of the last proposition (and keeping the same notation) we conclude that η^{(1)} is Dyck and has an upper peak, x^{(1)}, directly below x. Therefore from our induction hypothesis we have that

lv(x) = lv(x^{(1)}) + 2 ≥ lv(1^{(1)}) + d_{η^{(1)}}(x^{(1)}) + 1
≥ lv(1) + d_{η^{(1)}}(x^{(1)})
= lv(1) + d_{η}(x) − 1,

as desired, where 1^{(1)} denotes the leftmost cell of the connected component of η^{(1)} that contains x^{(1)}. □

We now come to the main result of this section.

Theorem 4.3 Let η be a skew partition, and x be an upper peak of η. Suppose that η has a lower valley, y, below x, y ≠ x. Then the following are equivalent:

i) η is Dyck;

ii) either η \ {x} or η \ {x, y} is Dyck, but not both;

iii) η \ {y} is Dyck.

Furthermore,

dp(η) = dp(η \ {x}) + 1 = dp(η \ {x, y}) = dp(η \ {y}) + 1.

Proof. We may clearly assume that η is connected. Then, since x ≠ y, we conclude that 1 < x < m (where 1 and m are the leftmost and rightmost cells of η). Therefore |η| ≥ 4, and d_{η}(x) ≥ 2.

We proceed by induction on d_{η}(x), the result being not hard to check for d_{η}(x) = 2.

So assume d_{η}(x) ≥ 3. Let θ be the outer border strip of η. Then x−1, x, x+1 ∈ θ, and therefore x^{(1)} is an upper peak of η^{(1)} (where x^{(1)} is the cell directly below x), and η^{(1)} has the lower valley y below x^{(1)}. Furthermore, the outer border strip of both η \{x} and η \{x, y} is (θ \{x})∪{x^{(1)}}, while the outer border strip of η \{y} is θ. Therefore,

η^{(1)} \ {x^{(1)}} = (η \ {x})^{(1)},  (16)
η^{(1)} \ {x^{(1)}, y} = (η \ {x, y})^{(1)},  (17)

and

η^{(1)} \ {y} = (η \ {y})^{(1)}.

These observations immediately imply, by our induction hypotheses, the equivalence of i) and iii), They also imply, by our definitions and induction hypotheses, that

dp (η \ {x}) = c((θ \ {x}) ∪ {x^{(1)}}) + dp ((η \ {x})^{(1)})
= c(θ) + dp (η^{(1)} \ {x^{(1)}})
= c(θ) + dp (η^{(1)}) − 1
= dp (η) − 1,

and similarly

dp (η \ {x, y}) = c((θ \ {x}) ∪ {x^{(1)}}) + dp ((η \ {x, y})^{(1)})
= c(θ) + dp (η^{(1)} \ {x^{(1)}, y})
= c(θ) + dp(η^{(1)})
= dp (η),

and

dp (η \ {y}) = c(θ) + dp ((η \ {y})^{(1)})
= c(θ) + dp (η^{(1)} \ {y})
= c(θ) + dp (η^{(1)}) − 1
= dp(η) − 1.

This proves the equalities after “Furthermore”.

We now prove the equivalence of i) and ii).

Assume first that η is Dyck. Then θ is Dyck and η^{(1)} is Dyck. Hence, by our induction hypotheses, either η^{(1)} \ {x^{(1)}} or η^{(1)} \ {x^{(1)}, y} are Dyck, but not both. But (θ \ {x}) ∪ {x^{(1)}} is a Dyck cbs since, by Lemma 4.2,

lv(x^{(1)}) = lv(x) − 2 ≥ lv(1)

(since d_{η}(x) ≥ 3) and θ is Dyck. Therefore we conclude from (16) and (17) that either η \ {x} or η \ {x, y} is Dyck, but not both, and this proves ii).

Conversely, suppose that η is not Dyck.

Suppose first that θ is not Dyck. Then (θ \ {x}) ∪ {x^{(1)}} is not Dyck (for if it were θ would also be), so η \ {x} and η \ {x, y} are not Dyck.

Suppose now that θ is Dyck. Then η^{(1)} is not Dyck. Hence, by induction, η^{(1)} \ {x^{(1)}} and η^{(1)} \ {x^{(1)}, y} are not Dyck. But, by (16) and (17), this implies that η \ {x} and η \ {x, y} are not Dyck. □

The preceding result has the following “dual version” which we will also need in the next section.

Proposition 4.4 Let η be a skew partition, and x be an upper peak of η. Suppose that η has a lower peak below x, and let y be the cell directly below this lower peak. Then the following are equivalent:

i) η is Dyck;

ii) either η \ {x} or (η \ {x}) ∪ {y}, are Dyck, but not both.

Furthermore

dp(η) = dp((η \ {x}) ∪ {y}) = dp(η \ {x}) − 1.

Proof. We know from Theorem 4.3 that, in our current hypotheses, η is Dyck if and only if η ∪ {y} is Dyck. But, by Theorem 4.3 , η ∪ {y} is Dyck if and only if either (η ∪ {y}) \ {x} or (η ∪ {y}) \ {x, y} are Dyck, but not both, and

dp ((η ∪ {y}) \ {x}) + 1 = dp (η \ {x}) = dp (η) + 1.

The result follows. □

5 Parabolic Kazhdan-Lusztig polynomials

In this section, using the results in the previous one, we prove the main result of this work, namely an explicit combinatorial formula for the maximal parabolic Kazhdan-Lusztig polynomials of the symmetric group. We then derive some consequences of this formula and in particular use it to prove that the polynomials are combinatorial invariants. Recall that throughout this work we fix n ∈ P and i ∈ [n − 1], and we

let J =^{def} S \ {s_{i}}.

Theorem 5.1 Let u, v ∈ W^{J}, u ≤ v. Then

P_{u,v}^{J,q}(q) = \{ \begin{matrix}q^{\frac{1}{2} (|λ\μ|−dp(λ\μ))}, & if λ \ μ is Dyck, \\ 0, & otherwise, \end{matrix}

where μ =^{def} Λ(u) and λ =^{def} Λ(v). In particular, P_{u,v}^{J,q}(q) depends only on Λ(v) \ Λ(u). Proof. We proceed by induction on l(v) = |λ|, the result being clearly true if v = e (i.e., if λ = ∅). Let, for notation simplicity, P_{x,y}^{J} =^{def} P_{x,y}^{J,q}(q), for all x, y ∈ W^{J}. We may clearly assume that l(v) − l(u) ≥ 2.

Let x be an upper peak of λ\μ, and s be the corresponding element of D(v) (see Lemma 2.9). Note that Λ(vs) = λ \ {x}. Then we have from Proposition 2.6 that

P_{u,v}^{J} = P̃ − ∑_{\{u≤w≤vs: ws<w\}} μ(w, vs)q^{\frac{l(v)−l(w)}{2}} P_{u,w}^{J}  (18)

where

P̃ = \{ \begin{matrix}P_{us,vs}^{J} + qP_{u,vs}^{J}, & if us < u, \\ qP_{us,vs}^{J} + P_{u,vs}^{J}, & if u < us ∈ W^{J}, \\ 0, & if u < us ∉ W^{J}. \end{matrix}

Now let w ∈ W^{J} be such that u ≤ w ≤ vs and ws < w, and ν =^{def} Λ(w). Then from Lemma 2.9 we have that ν has an upper peak, y, below x. Note that this implies that x is neither the leftmost nor the rightmost cell of λ \ μ. Now, since l(vs) < l(v), we conclude from our induction hypothesis that if μ(w, vs) ≠ 0 then necessarily (λ \ {x}) \ ν is Dyck and dp((λ \ {x}) \ ν) = 1. This, as observed in the previous section, implies that (λ \ {x}) \ ν is a cbs.

[figure: y; z; x]

Figure 10

Therefore, there is exactly one cell, z, strictly below x and above y (for if there were none then (λ \ {x}) \ ν would not be connected, and if there were more than one then (λ \ {x}) \ ν would not be a border strip). Therefore z is a lower peak and, at the same time, an upper valley, of (λ \ ν) \ {x} (see Figure 10), which contradicts the fact that (λ \ ν) \ {x} is a cbs. This shows that μ(w, vs) = 0 and hence that the sum on the RHS of (18) is also = 0. Therefore

P_{u,v}^{J} = \{ \begin{matrix}P_{us,vs}^{J} + qP_{u,vs}^{J}, & if us < u, \\ qP_{us,vs}^{J} + P_{u,vs}^{J}, & if u < us ∈ W^{J}, \\ 0, & if u < us ∉ W^{J}. \end{matrix}  (19)

There are now three cases to consider.

a) u < us ∉ W^{J}.

Then, by Lemma 2.9, λ \ μ has neither a lower valley nor a lower peak below x. But, in this case, we conclude from Proposition 4.1 that λ \ μ is not Dyck, and the result follows from (19).

b) u < us ∈ W^{J}.

Then, by Lemma 2.9, λ \ μ has a lower valley, y, below x and, clearly, Λ(us) = μ ∪ {y}.

Suppose that λ \ μ is not Dyck. Then by Theorem 4.3 we conclude that (λ \ μ) \ {x, y} and (λ \ μ) \ {x} are not Dyck. Hence we conclude from (19) and our induction hypothesis that P_{u,v}^{J} = 0, as desired.

Suppose now that λ\μ is Dyck. Then from Theorem 4.3 we conclude that exactly one of (λ \ μ) \ {x, y} and (λ \ μ) \ {x} is Dyck. If (λ \ μ) \ {x, y} is Dyck then from Theorem 4.3, (19), and our induction hypothesis we conclude that

P_{u,v}^{J} = qP_{us,vs}^{J}
= q q^{\frac{1}{2} (|(λ\μ)\\{x,y\}|−dp((λ\μ)\\{x,y\}))}
= q q^{\frac{1}{2} (|(λ\μ)|−2−dp(λ\μ))}
= q^{\frac{1}{2} (|λ\μ|−dp(λ\μ))}

as desired. If (λ \ μ) \ {x} is Dyck then we conclude similarly that

P_{u,v}^{J} = P_{u,vs}^{J}
= q^{\frac{1}{2} (|(λ\μ)\\{x\}|−dp((λ\μ)\\{x\}))}
= q^{\frac{1}{2} (|(λ\μ)|−1−(dp(λ\μ)−1))}
= q^{\frac{1}{2} (|λ\μ|−dp(λ\μ))}

as desired.

c) u > us.

Then, by Lemma 2.9, λ \ μ has a lower peak below x. Let y be the cell directly below this lower peak. Then, clearly, Λ(us) = μ \ {y}.

Suppose that λ \ μ is not Dyck. Then, by Proposition 4.4, (λ \ μ) \ {x} and ((λ \ μ) \ {x}) ∪ {y} are not Dyck. Hence we conclude from (19) and our induction hypothesis that P_{u,v}^{J} = 0 , as desired.

Suppose now that λ \ μ is Dyck. Then from Proposition 4.4 we conclude that exactly one of (λ \ μ) \ {x} and ((λ \ μ) \ {x}) ∪ {y} is Dyck. If (λ \ μ) \ {x} is Dyck then from (19), Proposition 4.4, and our induction hypothesis we conclude that

P_{u,v}^{J} = q q^{\frac{1}{2} (|(λ\μ)\\{x\}|−dp((λ\μ)\\{x\}))}
= q^{\frac{1}{2} (|λ\μ|−dp(λ\μ))}

as desired. If ((λ \ μ) \ {x}) ∪ {y} is Dyck then we conclude similarly that

P_{u,v}^{J} = q^{\frac{1}{2} (|((λ\μ)\\{x\})∪\{y\}|−dp (((λ\μ)\\{x\})∪\{y\}))}
= q^{\frac{1}{2} (|λ\μ|−dp(λ\μ))}

and the result again follows.

This concludes the induction step and hence the proof. □

Because of the preceding theorem we sometimes also write P_{μ,λ}^{J,q}(q) and P_{θ}^{J,q}(q) if μ, λ ∈ P, and θ is a skew partition.

We illustrate Theorem 5.1 with an example. Let u, v ∈ W^{J} be such that Λ(v) \ Λ(u) equals the skew partition depicted in Figure 2. Then Λ(v) \ Λ(u) is Dyck and dp(Λ(v) \ Λ(u)) = 7 so

P_{u,v}^{J,q}(q) = q^{\frac{1}{2} (33−7)} = q^{13}.

Note that from Proposition 2.4 we have that P_{u,v}^{J,−1}(q) = P_{w_{0}^{J} u,w_{0}^{J} v}(q) for all u, v ∈ W^{J}. On the other hand, the polynomials P_{w_{0}^{J} u,w_{0}^{J} v}(q) have been computed combinatorially (for u, v ∈ W^{J}, J = S \ {s_{i}}) in [10] (see also [18]). Thus Theorem 5.1 completes the computation of the maximal parabolic Kazhdan-Lusztig polynomials of the symmetric groups.

We give below three consequences of Theorem 5.1. The first one deals with the special case of lower intervals. Its simple verification is left to the reader. Recall that given a partition λ we denote by d(λ) the length of its Durfee square (see (1)).

Corollary 5.2 Let v ∈ W^{J}. Then

P_{e,v}^{J,q}(q) = \{ \begin{matrix}q^{\frac{1}{2} (|λ|−d(λ))}, & if λ is a square, \\ 0, & otherwise, \end{matrix}

where λ =^{def} Λ(v). □

Theorem 5.1 and Corollary 5.2 show that (just as for the polynomials R_{u,v}^{J,q}(q), see the comments following Corollary 3.5) given u, v ∈ W^{J} there may not exist a w ∈ W^{J} such that P_{u,v}^{J,q}(q) = P_{e,w}^{J,q}(q). This situation contrasts strikingly with that for upper intervals, as the next result shows. We denote by w_{0}(J) the longest element of W^{J}.

Corollary 5.3 Let m ∈ P, and μ ⊆ (m^{m}). Then

P_{μ,(m^{m})}^{J,q}(q) = \{ \begin{matrix}q^{(\begin{matrix}m \\ 2 \end{matrix})− \frac{1}{2} (|μ|−d(μ))}, & if μ is self-conjugate, \\ 0, & otherwise. \end{matrix}  (20)

In particular, for all u, v ∈ W^{J} there is a w ∈ W^{J} such that P_{u,v}^{J,q}(q) = P_{w,w_{0}(J)}^{J,q}(q).

Proof. The statements before “In particular” are an easy consequence of Theorem 5.1. Let u, v ∈ W^{J}. If P_{u,v}^{J,q}(q) = 0 then the result is clear. So assume P_{u,v}^{J,q}(q) ≠ 0. Then u ≤ v. Let η =^{def} Λ(v) \ Λ(u). From Theorem 5.1 we then have that η is Dyck and P_{u,v}^{J,q}(q) = q^{j} where j = \frac{1}{2} (|η| − dp (η)). But it is easy to see (e.g., by induction on dp (η)) that for any Dyck partition η

4(|η| − dp (η)) ≤ |θ|^{2} − 1,  (21)

where θ denotes the outer border strip of η. Since θ is Dyck and η ⊆ (n − i)^{i} we conclude that |θ| ≤ 2m−1 where m =^{def} min(n−i, i). Therefore from (21) we deduce that

j = \frac{1}{2}(|η| − dp (η)) ≤ \frac{m}{4}(2m − 2) = (\begin{matrix}m \\ 2 \end{matrix}) .

On the other hand, it is easy to see that then there is a self-conjugate partition μ ⊆ (m^{m}) such that \frac{1}{2}(|μ| − d(μ)) = (\begin{matrix}m \\ 2 \end{matrix}) − j. Therefore, by (20) and Theorem 5.1, P_{ν,(n−i)^{i}}^{J,q}(q) = P_{μ,(m^{m})}^{J,q}(q) = q^{j} = P_{u,v}^{J,q}(q), where ν is the unique partition in P(n, i) such that (n − i)^{i} \ ν ≈ (m^{m}) \ μ. □

The following result is an immediate consequence of Theorem 5.1 and the comments preceding Proposition 4.1.

Corollary 5.4 Let u, v ∈ W^{J}, u ≤ v. Then

μ(u, v) = \{ \begin{matrix}1, & if Λ(v) \ Λ(u) is a Dyck cbs, \\ 0, & otherwise. □ \end{matrix}

Note that, by Proposition 2.4 and part iii) of Theorem 2.3,

μ(u, v) = [q^{\frac{1}{2} (l(v)−l(u)−1)}](P_{u,v}),

for all u, v ∈ W^{J}. In this formulation Corollary 5.4 is equivalent to a result in [10].

We conclude this section by answering the question raised at the end of section 3, namely of whether P_{u,v}^{J,q} (and hence, by Theorem 2.3 and Proposition 2.5, also R_{u,v}^{J,q}, R_{u,v}^{J,−1}, and P_{u,v}^{J,−1}) depend only on [u, v]_{J}. To do this we need a purely order theoretic result on skew partitions.

Lemma 5.5 Let θ, η be two connected skew partitions that are isomorphic as posets. Then either θ ≈ η or θ ≈ η′.

Proof. Let (a_{1}, b_{1}, …, a_{r}, b_{r}), (c_{1}, d_{1}, …, c_{s}, d_{s}) be the polygon notation of θ introduced in §2. It is clear that these two sequences (in this order) uniquely determine θ up to translation. We will show that either the two sequences (a_{1}, b_{1}, …, a_{r}, b_{r}), (c_{1}, d_{1}, …, c_{s}, d_{s}) (in this order) or the two sequences (b_{r}, a_{r}, …, b_{1}, a_{1}), (d_{s}, c_{s}, …, d_{1}, c_{1}) (in this order) are uniquely determined by the isomorphism class of θ as a poset. Since (b_{r}, a_{r}, …, b_{1}, a_{1}), (d_{s}, c_{s}, …, d_{1}, c_{1}) is the polygon notation of θ′, this will establish the result.

First note that there are exactly r maximal (respectively, s minimal) elements in θ. So r and s (in this order) are uniquely determined by the isomorphism class of θ as a poset.

Next consider the set E(θ) consisting of those elements x ∈ θ such that

|{a ∈ θ : a > x}| ≤ 1 , |{a ∈ θ : a < x}| ≤ 1,

(i.e., x is both join and meet-irreducible) and θ \ {x} is connected. Note that E(θ) depends only on the isomorphism class of θ as a poset. Clearly, 1 and m (the leftmost and rightmost cells of θ) are in E(θ). Let x ∈ E(θ), x ≠ 1, m. Then necessarily

|{a ∈ θ : a > x}| = |{a ∈ θ : a < x}| = 1.

Let a (respectively, b) be the only element of θ covering (respectively, covered by) x. Then a and b must lie on opposites sides of x (else x would be either the leftmost or rightmost element of θ). But this implies that θ \ {x} is not connected (see Figure 11) and contradicts the assumption that x ∈ E(θ). This shows that E(θ) = {1, m}.

[figure: b; x; a; b; x; a; or]

Figure 11: In these cases θ \ {x} is not connected.

Choose x ∈ E(θ). Suppose that x = 1. Let x_{1} be the maximal element of θ which is closest to x (in the sense of the distance in the Hasse graph of θ). Then the distance between x and x_{1} is a_{1} − 1 (note that x_{1} can equal x). Now let y_{1} be the upper valley of θ which is closest to x_{1}. Then the distance between x_{1} and y_{1} is b_{1}. Now let x_{2} be the closest element to y_{1} among the maximal elements of θ which are different from x_{1}. Then the distance between x_{2} and y_{1} is a_{2}. Continuing in this way we see that the sequence (a_{1}, b_{1}, …, a_{r}, b_{r}) depends only on the isomorphism class of θ as a poset. Similarly, we obtain the same conclusion for the sequence (c_{1}, d_{1}, …, c_{s}, d_{s}). If instead x = m then the procedure just described yields that the sequences (b_{r}, a_{r}, …, b_{1}, a_{1}), (d_{s}, c_{s}, …, d_{1}, c_{1}), in this order, depend only on the isomorphism class of θ as a poset.

Therefore, if η ≅ θ as a poset, then the above procedure applied to η will yield either the pair of sequences (a_{1}, b_{1}, …, a_{r}, b_{r}), (c_{1}, d_{1}, …, c_{s}, d_{s}), in this order, or their reverses in the same order. But this, as already remarked, implies that either θ ≈ η or θ ≈ η′, as desired. □

We can now prove the second main result of this section.

Corollary 5.6 Let L, K ⊆ S, |L| = |K| = |S| − 1, and u, v ∈ W^{L}, w, z ∈ W^{K} be such that [u, v]_{L} ≅ [w, z]_{K}. Then

P_{u,v}^{L,q}(q) = P_{w,z}^{K,q}(q)

(and hence also R_{u,v}^{L,q}(q) = R_{w,z}^{K,q}(q), R_{u,v}^{L,−1}(q) = R_{w,z}^{K,−1}(q), and P_{u,v}^{L,−1}(q) = P_{w,z}^{K,−1}(q)).

Proof. By Proposition 2.8 we have that [u, v]_{L} is isomorphic, as a poset, to the interval [Λ(u), Λ(v)] in Young’s lattice. But it follows immediately from the definitions and well known results in the theory of partially ordered sets (see, e.g., [15, §3.4]) that the subposet of join-irreducibles of [Λ(u), Λ(v)] is isomorphic to Λ(v)\Λ(u), where the skew partition Λ(v)\Λ(u) is seen as a poset. Therefore, since [u, v]_{L} ≅ [w, z]_{K}, we conclude that Λ(v) \ Λ(u) ≅ Λ(z) \ Λ(w) (as posets), and the result follows from Lemma 5.5, Theorem 5.1, and the definitions of Dyck partition and depth. □

Note that the preceding result gives an explicit procedure for computing P_{u,v}^{J,q} (and hence also R_{u,v}^{J,q}, R_{u,v}^{J,−1}, and P_{u,v}^{J,−1}) from [u, v]_{J}.

6 Consequences

In this section we derive some consequences of our main results. These include some identities for the ordinary Kazhdan-Lusztig and R-polynomials, a combinatorial invariance result for the ordinary Kazhdan-Lusztig polynomials of Grassmannian permutations, and some further combinatorial and enumerative properties of Dyck partitions.

Our first two results concern the ordinary Kazhdan-Lusztig and R-polynomials. Although their proof is immediate from Proposition 2.4, Theorem 5.1, and Theorem 3.1, we feel that they should be stated explicitly.

Corollary 6.1 Let u, v ∈ W^{J}, u ≤ v. Then

∑_{w∈W_{J}}(−1)^{l(w)}P_{wu,v}(q) = \{ \begin{matrix}q^{\frac{1}{2} (|λ\μ|−dp(λ\μ))}, & if λ \ μ is Dyck, \\ 0, & otherwise, \end{matrix}

where μ = Λ(u) and λ = Λ(v). □

Corollary 6.2 Let u, v ∈ W^{J}, u ≤ v, and x ∈ {−1, q}. Then

∑_{w∈W_{J}}(−x)^{l(w)}R_{wu,v}(q) = (q−1−x)^{l(v)−l(u)} ∏_{j∈v^{−1}([i])\u^{−1}([i])} (1 − (\frac{x^{2}}{q} )^{j+i+1−u(j)−v(j)}) .□

The combinatorial invariance conjecture for Kazhdan-Lusztig polynomials (see, e.g., [8, §8.6]) states that P_{u,v}(q) depends only on [u, v] as a poset. Although, as mentioned in the comments following Theorem 5.1, an explicit combinatorial formula for P_{u,v}(q) is known if u and v are Grassmannians (i.e, if |D(v)| = |D(u)| = |S| − 1) the conjecture is open even in that case (we refer the interested reader to [3, §7] for further information on the combinatorial invariance conjecture). Using Corollary 5.6 we can prove a very similar, and computationally simpler, statement. Note that it is well known (see, e.g., [8, Corollary 7.14]) that if u, v ∈ W then there exists u′ ∈ W such that D(u′) ⊇ D(v) and P_{u,v}(q) = P_{u′,v}(q).

Corollary 6.3 Let u, v ∈ W be such that D(u) = D(v) and |D(u)| = |S| − 1. Then P_{u,v}(q) depends only on

{x ∈ [u, v] : D(x) = D(u)}  (22)

as a poset.

Proof. Let w, z ∈ W be such that D(w) = D(z) and |D(w)| = |S| − 1, and suppose that {x ∈ [w, z] : D(x) = D(w)} is isomorphic to (22) as a poset. We will show that then P_{u,v}(q) = P_{w,z}(q). Let, for brevity, L =^{def} D(u) and K =^{def} D(w). We claim that

{x ∈ [u, v] : D(x) = L} ≅ [w_{0}^{L}u^{−1}, w_{0}^{L}v^{−1}]_{L}  (23)

as posets. To see this note first that if x ∈ W then D(x) = L if and only if w_{0}^{L}x^{−1} ∈ W^{L}. Also, if x, y ∈ W with D(x) = D(y) = L then

l(w_{0}^{L}x^{−1}) = l(x^{−1}) − l(w_{0}^{L}) = l(x) − l(w_{0}^{L}),

and similarly for y. So l(y) > l(x) if and only if l(w_{0}^{L}y^{−1}) > l(w_{0}^{L}x^{−1}). Finally, if x, y ∈ W then yx^{−1} ∈ T if and only if w_{0}^{L}(y^{−1}x)w_{0}^{L} ∈ T. This shows, by the definition of Bruhat order, that if x, y ∈ W are such that D(x) = D(y) = L then x ≤ y if and only if w_{0}^{L}x^{−1} ≤ w_{0}^{L}y^{−1}. Therefore the map x ↦ w_{0}^{L}x^{−1} is a poset isomorphism from (22) to [w_{0}^{L}u^{−1}, w_{0}^{L}v^{−1}]_{L}, and this proves (23). We therefore conclude from our assumptions that [w_{0}^{L}u^{−1}, w_{0}^{L}vv^{−1}]_{L} ≅ [w_{0}^{K}w^{−1}, w_{0}^{K}z^{−1}]_{K}. This, by Corollary 5.6, Proposition 2.4, and a well known property of the Kazhdan-Lusztig polynomials (see, e.g., [2, Corollary 4.4]), implies that P_{u,v}(q) = P_{u^{−1},v^{−1}}(q) = P_{w_{0}^{L}u^{−1},w_{0}^{L}v^{−1}}^{L,−1}(q) = P_{w_{0}^{K}w^{−1},w_{0}^{K}z^{−1}}^{K,−1}(q) = P_{w^{−1},z^{−1}}(q) = P_{w,z}(q), as desired. □

We feel that the poset in (22) is the “right” poset to consider for the computation of the Kazhdan-Lusztig polynomials, and that Corollary 6.3 holds even without the (strong) hypothesis that |D(u)| = |S| − 1.

The close connection given by Theorem 5.1 between Dyck partitions and the maximal parabolic Kazhdan-Lusztig polynomials of S_{n} allows a transfer of information between combinatorial properties of the partitions and algebraic properties of the polynomials. We close by giving two such examples.

Let λ be a partition and θ be its outer border strip. We call a cell x ∈ θ a left-to-right minimum (or lrm, for short) of λ if

i) lv(y) ≥ lv(x) for all y ∈ θ, y ≤ x;

ii) lv(x) < lv(1).

So 1, in particular, is never a lrm. Furthermore, we say that x is a descending lrm (or dlrm, for short) if x is a lrm and x is not an upper valley of λ. We denote by dlrm(λ) the number of dlrms of λ. So, for example, if λ = (7, 4, 2, 1) then its descending left-to-right minimums are the cells 2, 3 and 6 of its outer border strip (see Figure 1) so dlrm(λ) = 3. We let DF S(λ) be the number of Dyck final segments of λ. So,

DF S(λ) = |{μ ∈ P : μ ⊆ λ, λ \ μ is Dyck }|.

Theorem 6.4 Let λ = (λ_{1}, λ_{2}, …, λ_{l}) be a partition. Then

DF S(λ) = 2^{λ_{1}−dlrm(λ)}.

Proof. We proceed by induction on |λ|, the result being clear if |λ| = 1.

Assume first that the outer border strip θ of λ is not Dyck. Since the number of Dyck final segments of λ and λ′ are clearly the same, we may assume that there is a cell of θ which is at a level strictly below the level of cell 1 (say lv(1) = r). Let x ∈ θ be the leftmost such cell. Suppose that x = (h, k) ∈ P^{2}. Then x is at level r − 1, and is also the leftmost left-to-right minimum of λ. Clearly, x cannot be in any Dyck final segment of λ. Therefore, the Dyck final segments of λ are contained

in λ_{L} ⊎ λ_{R}, where λ_{L} =^{def} (λ_{1} − k, λ_{2} − k, …, λ_{h} − k) and λ_{R} =^{def} (λ_{h+1}, λ_{h+2}, …, λ_{l}).

Hence, by induction, their number is

2^{(λ_{L})_{1}}2^{(λ_{R})_{1}−dlrm(λ_{R})}.

Let x + a be the leftmost cell of λ_{R} ∩ θ (so a ≥ 1). Then the level of x + a is r − a + 1 and the level of x + i is r − i − 1 for i = 0, …, a − 1. Therefore, the cells x, x + 1, …, x + a − 2 are exactly the descending left-to-right minimums of λ that are weakly to the left of x + a. This implies that a cell of θ ∩ λ_{R} is a dlrm of λ_{R} if and only if it is a dlrm of λ. Therefore we have that dlrm(λ) = dlrm(λ_{R}) + a − 1. But, clearly, (λ_{L})_{1} + (λ_{R})_{1} + a − 1 = λ_{1}. Hence

2^{(λ_{L})_{1}} 2^{(λ_{R})_{1}−dlrm(λ_{R})} = 2^{λ_{1}−dlrm(λ)},

as desired.

Assume now that θ is Dyck. Let ν ⊆ λ be a Dyck final segment of λ. If 1 ∈ ν then, since the outer border strip of ν is Dyck, we conclude that θ ⊆ ν. If 1 ∉ ν then, by a similar reasoning, m ∉ ν (where m is the rightmost cell of θ). Therefore either ν ⊇ θ or ν ∌ 1, m. If ν ⊇ θ then the outer border strip of ν coincides with θ and ν \ θ is a Dyck final segment of λ \ θ, and this is a bijection. If 1, m ∉ ν then ν ∩η = ∅ (where η is the inner border strip of λ) and hence ν is a Dyck final segment of λ \ η. Therefore DF S(λ) = DF S(λ \ θ) + DF S(λ \ η). But, by Proposition 2.1, λ \ θ ≈ λ \ η, hence

DF S(λ) = 2 DF S(λ \ θ).  (24)

Furthermore, by our induction hypothesis,

DF S(λ \ θ) = 2^{(λ\θ)_{1}−dlrm(λ\θ)}.  (25)

Also, since θ is Dyck,

(λ \ θ)_{1} = λ_{1} − 1,  (26)

and each one of its cells is at level ≥ r. This implies that dlrm(λ) = 0 and that each cell of θ^{(1)} (the outer border strip of λ \ θ) is at level ≥ r − 1 except possibly for some upper valley of λ \ θ which could be at level r − 2. Since the leftmost cell of θ^{(1)} is at level r − 1 this implies that the only lrm’s of λ \ θ are upper valleys of λ \ θ. Hence dlrm(λ \ θ) = 0 and therefore, by (24), (25), and (26),

DF S(λ) = 2 2^{(λ\θ)_{1}−dlrm(λ\θ)} = 2^{λ_{1}},

as desired, since dlrm(λ) = 0. □

One consequence of the preceding theorem is particularly elegant.

Corollary 6.5 Let λ be a partition whose outer border strip is Dyck. Then

DF S(λ) = 2^{λ_{1}}.

Proof. It is clear from our definitions that if the outer border strip of λ is Dyck then dlrm(λ) = 0, so the result follows from Theorem 6.4. □

The enumeration of the Dyck final segments of a partition that we have just carried out immediately “translates”, by Theorem 5.1, into an identity for the maximal parabolic Kazhdan-Lusztig polynomials of S_{n}.

Corollary 6.6 Let v ∈ W^{J}. Then

∑_{u∈W^{J}} P_{u,v}^{J,q}(1) = 2^{λ_{1}−dlrm(λ)},

where λ = Λ(v). □

We conclude this section with an example in the “opposite direction”. Namely a purely combinatorial result on Dyck partitions that follows rather easily from algebraic properties of the maximal parabolic Kazhdan-Lusztig and R-polynomials of S_{n}.

Proposition 6.7 Let λ \ μ be a skew partition. Then λ \ μ is Dyck if and only if

|{μ ⊂ ν ⊆ λ : λ \ ν is Dyck, ν \ μ is a cbs of odd size }| >
|{μ ⊂ ν ⊆ λ : λ \ ν is Dyck, ν \ μ is a cbs of even size }|.  (27)

Proof. From Theorems 2.3, 5.1 and Proposition 2.8 we have that

q^{|λ\μ|}P_{μ,λ}^{J,q} (\frac{1}{q}) − P_{μ,λ}^{J,q}(q) = ∑_{μ⊂ν⊆λ} R_{μ,ν}^{J,q}(q)P_{ν,λ}^{J,q}(q).

Therefore

lim_{q→1} (\frac{q^{|λ\μ|}P_{μ,λ}^{J,q} (\frac{1}{q}) − P_{μ,λ}^{J,q}(q)}{q − 1}) = ∑_{μ⊂ν⊆λ} lim_{q→1} (\frac{R_{μ,ν}^{J,q}(q)}{q − 1}P_{ν,λ}^{J,q}(q)) .  (28)

But, by Theorem 5.1 and Proposition 3.6, the limit on the RHS of (28) is 0 unless λ \ ν is Dyck and ν \ μ is a cbs, in which case it equals (−1)^{|ν\μ|+1}. Therefore the RHS of (28) equals

|{μ ⊂ ν ⊆ λ : λ \ ν is Dyck, ν \ μ is a cbs of odd size }|
−|{μ ⊂ ν ⊆ λ : λ \ ν is Dyck, ν \ μ is a cbs of even size }|.

On the other hand, by Theorem 5.1, the LHS of (28) is 0 unless λ \ μ is Dyck in which case it equals dp(λ \ μ). The result follows. □

Note that, since |λ\ν| < |λ\μ| for all partitions ν appearing in (27), Proposition 6.7 gives an alternative definition of Dyck partitions. It would be interesting to have a purely combinatorial proof of Proposition 6.7. Acknowledgments. I would like to thank T. Braden, I. Goulden, D. Jackson, P. Littelmann, G. Papadopoulo, W. Soergel, and D.Wagner for useful conversations.

References

[1] A. Björner, private communication, March 1992.

[2] F. Brenti, A combinatorial formula for Kazhdan-Lusztig polynomials, Invent. Math., 118 (1994), 371-394.

[3] F. Brenti, Kazhdan-Lusztig and R-polynomials from a combinatorial point of view, Discrete Math., 193 (1998), 93-116.

[4] L. Casian, D. Collingwood, The Kazhdan-Lusztig conjecture for generalized Verma modules, Math. Zeit., 195 (1987), 581-600.

[5] V. Deodhar, On some geometric aspects of Bruhat orderings. II. The parabolic analogue of Kazhdan-Lusztig polynomials, J. Algebra, 111 (1987), 483-506.

[6] V. Deodhar, Duality in parabolic setup for questions in Kazhdan-Lusztig theory, J. Algebra, 142 (1991), 201-209.

[7] E. Deutsch, Dyck path enumeration, Discrete Math., 204 (1999), 167-202.

[8] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, no.29, Cambridge Univ. Press, Cambridge, 1990.

[9] D. Kazhdan, G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math., 53 (1979), 165-184.

[10] A. Lascoux, M.-P. Schützenberger, Polynômes de Kazhdan & Lusztig pour les grassmanniennes, Young tableaux and Schur functions in algebra and geometry, Astérisque, 87-88 (1981), pp. 249-266.

[11] B. Leclerc, J.-Y. Thibon, Littlewood-Richardson coefficients and Kazhdan-Lusztig polynomials, preprint.

[12] I. G. Macdonald, Notes on Schubert Polynomials, Publ. LACIM, UQAM, Montreal, 1991.

[13] W. Soergel, Kazhdan-Lusztig polynomials and a combinatoric for tilting modules, Represent. Theory, 1 (1997), 83-114.

[14] W. Soergel, Character formulas for tilting modules over Kac-Moody algebras, Represent. Theory, 1 (1997), 115-132.

[15] R. P. Stanley, Enumerative Combinatorics , vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

[16] R. P. Stanley, Enumerative Combinatorics , vol.2, Cambridge Studies in Advanced Mathematics, no.62, Cambridge Univ. Press, Cambridge, 1999.

[17] M. Varagnolo, E. Vasserot, On the decomposition matrices of the quantized Schur algebra, Duke Math. J., 100 (1999), 267-297.

[18] A. Zelevinski, Small resolutions of singularities of Schubert varieties, Funct. Anal. Appl., 17 (1983), 142-144.