Enumerative properties of shifted Dyck partitions

Francesco Brenti^{1} Dipartimento di Matematica Universitá di Roma “Tor Vergata” Via della Ricerca Scientifica, 1 00133 Roma, Italy brenti@mat.uniroma2.it

1 Introduction

Shifted-Dyck partitions are a class of (possibly skew) shifted partitions that arise in the study of certain parabolic Kazhdan-Lusztig polynomials (see [5]). While their algebraic and combinatorial properties are studied in [5] in this paper we focus mainly on their enumerative properties. More precisely, we show that shifted Dyck partitions include, in a precise sense, the Dyck partitions studied in [3] and [4] and that most of the results that hold for Dyck partitions actually hold for shifted Dyck partitions. As consequences of our results we obtain new identities for the parabolic Kazhdan-Lusztig polynomials of Hermitian symmetric pairs and for the ordinary Kazhdan-Lusztig polynomials of certain Weyl groups.

The organization of the paper is as follows. In the next section we recall some definitions and results that are used in the sequel. In Section 3 we prove our main result, namely an explicit closed product formula for a partial generating function of shifted Dyck partitions. In Section 4 we study, using the result in the previous one, the generating function of all shifted Dyck partitions. More precisely, we show that this can be expressed as a generating function over ballot sequences, that it can be computed explicitly if one of the variables is set equal to 1, and that it includes as its “constant term” the generating function for all Dyck partitions studied in [4]. Finally, in Section 5, using our results and the connection between shifted Dyck partitions and the parabolic Kazhdan-Lusztig polynomials established in [5] we obtain some new identities for the parabolic Kazhdan-Lusztig polynomials of Hermitian symmetric pairs and for the Kazhdan-Lusztig polynomials of certain Weyl groups.

1Partially supported by EU grant HPRN-CT-2001-00272. Part of this research was carried out while the author was a member of the Mittag-Leffler Institut in Djürsholm, Sweden, whose hospitality and financial support are gratefully acknowledged.

2 Preliminaries

In this section we collect some definitions, notation and results that are used in the rest of this paper. We let P =^{def} {1, 2, 3, …} and N=^{def}P ∪{0}. For m, n ∈ N, m ≥ n, we let [n, m] =^{def} {n, n + 1, …, m − 1, m}. The cardinality of a set A will be denoted by |A|.

We follow Chapter 3 of [9] for poset notation and terminology. In particular, given a poset (P, ≤) we denote by J(P) the set of order ideals of P, partially ordered by set inclusion. Given any Q ⊆ P we will always consider Q as a poset with the partial ordering induced by P.

We follow §7.2 of [10] for any undefined notation and terminology concerning partitions. Let H =^{def} {(i, j) ∈ P^{2} : i ≤ j}, with the ordering induced by the product ordering on P^{2}. We denote by S (resp., P) the set of all finite order ideals of H (resp., P^{2}). We call the finite order ideals of H (resp., P^{2}) shifted partitions (resp., partitions). We will always assume that S and P are partially ordered by set inclusion. It is well known that this makes S and P into distributive lattices. Note that there is an obvious bijection between sequences of strictly decreasing positive integers and shifted partitions, given by

(λ_{1}, …, λ_{k}) ↔ {(i, j) ∈ H : 1 ≤ i ≤ k, i ≤ j ≤ λ_{i} + i − 1}.

For this reason we will freely identify these objects, and use expressions such as “the shifted partition (5, 2, 1)”. We also identify each shifted partition with its diagram, which we draw rotated counterclockwise by \frac{3}{4}π radians with respect to the usual (Anglophone) convention. So, for example, the diagram of the shifted partition (5, 2, 1) is shown in Figure 1. We let δ_{n} =^{def} (n, n − 1, …, 2, 1).

[figure]

Figure 1

We call the elements of P^{2} cells. Given a cell x = (i, j) ∈ P^{2} we define its level to be lv(x) =^{def} i+j −1. Expressions such as “leftmost” or “to the right of” always refer to the rotated diagrams. In particular, given a cell x = (i, j) ∈ P^{2} (i, j ≥ 2) the cell directly below x is the cell x^{(1)} =^{def} (i − 1, j − 1) (see Figure 2). Similarly, we define directly above, directly northwest, etc... Also, we let x^{(2)} =^{def} (x^{(1)})^{(1)} and for a subset S ⊂ H we let S^{(k)} =^{def} {x^{(k)} : x ∈ S}, k = 1, 2. We say that a cell y = (k, l) ∈ H is below x = (i, j) if l − k = j − i and j ≥ l.

Let μ, λ ∈ S (resp., P), μ ⊆ λ. We then call λ \ μ a skew shifted partition (resp., skew partition). Given a skew shifted partition η we let

d(η) =^{def} |{(i, j) ∈ η : i = j}|.

Note that, if η is a skew partition then there exist λ, μ ∈ S, μ ⊆ λ, such that λ \ μ is a translate of η. In fact, a skew shifted partition is a translate of a skew partition if and only if it has exactly one rightmost cell. For this reason we will identify skew partitions with skew shifted partitions which have exactly one rightmost cell.

We say that a skew shifted partition is a border strip if it never contains a cell and the cell directly above it. For brevity, we call a connected border strip (by which we mean “rookwise connected”) a cbs. Let λ, μ ∈ S be such that μ ⊆ λ. The outer border strip θ of λ \ μ is the set of cells of λ \ μ such that the cell directly above it is not in λ \ μ. For example, the cells of the outer border strip of the skew shifted partition illustrated in Figure 2 are numbered from 1 to 13. 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 y ∈ θ, y > 1, then y − 1 is the cell of θ immediately to the left of y. The vertical strip of λ \ μ is

V(λ \ μ) =^{def} {x ∈ θ : lv(x − 1) < lv(x)} ∪ {1}.

So, for example, the vertical strip of the skew shifted partition illustrated in Figure 2 is {1, 2, 3, 4, 7, 10, 11, 13}.

[figure: 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; x; x^{(1)}]

Figure 2

Let θ ⊆ H be a connected border strip. We say that θ is ballot if lv(x) ≥ lv(1) for all x ∈ θ. We say that θ is Dyck if it is ballot and lv(|θ|) = lv(1). Let θ be a ballot cbs. Let z be the rightmost cell of θ such that lv(z) = lv(1). We define θ_{S} =^{def} θ ∪ {y^{(1)} : z < y ≤ |θ|}. So, for example, if θ is the cbs depicted in Figure 3 then θ_{S} is depicted in Figure 4. Note that θ = θ_{S} if and only if θ is Dyck.

[figure]

Figure 3

[figure]

Figure 4

Let η ⊆ H be a skew shifted partition. Recall from [5] that η is defined to be shifted-Dyck (or, s-Dyck, for short) in the following inductive way:

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

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

a) the outer border strip θ of η is ballot, θ_{S} ⊆ η, and |θ| is odd;

b) η \ θ_{S} is s-Dyck.

Finally, ∅ is s-Dyck.

This definition is equivalent to the one given in [5], although it is formulated in a slightly different way.

Let η ⊂ H be an s-Dyck skew shifted partition. Following [5] we define the depth of η, denoted dp (η), inductively by letting the depth of η be the sum of the depths of its connected components, and if η is connected letting

dp (η) =^{def} 1 + dp (η \ θ_{S})

(and dp (∅) =^{def} 0), where θ is the outer border strip of η. So, for example, the skew shifted partition depicted in Figure 5 is not s-Dyck, while that depicted in Figure 2 is and has depth 6.

The following combinatorial property of s-Dyck skew shifted partitions is proved in [5] and will be used in what follows.

Lemma 2.1 Let η be a connected s-Dyck skew shifted partition and x be in the outer border strip of η. Then the number of cells of η that are below x is at most lv(x) − lv(1) + 1.

[figure]

Let η ⊂ P^{2} be a skew partition. Recall from [3] that η is defined 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) η \ θ is Dyck.

Finally, ∅ is Dyck. Let η ⊂ P^{2} be a skew partition. We define dep (η) inductively by letting

dep (η) =^{def} c(θ) + dep (η \ θ)

(and dep (∅) =^{def} 0), where θ is the outer border strip of η, and c(θ) denotes the number of connected components of θ.

3 Shifted-Dyck final segments

In this section we count, given a shifted partition λ, all the shifted partitions μ ⊆ λ such that λ\μ is s-Dyck. This result is used in the next section for the enumeration of s-Dyck skew shifted partitions.

Let η be a skew shifted partition and θ be its outer border strip. For x ∈ V(η) we let θ(x) be the maximal subset of θ which is a cbs such that:

i) x is the leftmost cell of θ(x);

ii) θ(x) is ballot.

So, for example, if η is the skew shifted partition whose diagram is depicted in Figure 2 then θ(2) = [2, 8], θ(3) = [3, 5], θ(10) = [10, 13], and θ(11) = {11}. We let

V^{∗}(η) =^{def} {x ∈ V(η) : |θ(x)| is odd }.

Given a shifted partition λ we let

SD(λ) =^{def} {μ ∈ S : μ ⊆ λ , λ \ μ is s-Dyck}.

Theorem 3.1 Let λ ∈ S. Then

∑_{μ∈SD(λ)} q^{|λ\μ|} t^{dp(λ\μ)} s^{⌊ \frac{d(λ\μ)}{2} ⌋} = ∏_{x∈V^{∗}(λ)} (1 + q^{|θ(x)_{S}|}t s^{⌊\frac{d(θ(x)_{S})}{2}⌋}) .

Proof. Let, for brevity,

F_{ν}(q, t, s) =^{def} ∑_{μ∈SD(ν)} q^{|ν\μ|} t^{dp(ν\μ)} s^{⌊ \frac{d(ν\μ)}{2} ⌋}

for any ν ∈ S.

We proceed by induction on |λ|. Let θ be the outer border strip of λ. For x ∈ V^{∗}(λ) let, for brevity, a(x) =^{def} ⌊\frac{d(θ(x)_{S})}{2}⌋.

Suppose first that θ is not ballot. Let x_{0} be the leftmost cell of θ such that lv(x_{0}) ≤ lv(y) for all y ∈ θ. Say x_{0} = (j, i). Note that this implies that λ_{j+1} = i − j. Let, for convenience, λ_{L} =^{def} (λ_{1} − λ_{j+1} − 1, …, λ_{j} − λ_{j+1} − 1) and λ_{R} =^{def} (λ_{j+1}, λ_{j+2}, …). Let μ ∈ SD(λ). Then x_{0} ∈ μ (else the outer border strip of λ \ μ would not be ballot). Therefore (i, i−1, …, i−j +1) ⊆ μ. Hence λ\μ is the disjoint union of (translates of) λ_{L}\(μ_{1}−λ_{j+1}−1, …, μ_{j} −λ_{j+1}−1) and λ_{R}\(μ_{j+1}, μ_{j+2}, …). Since λ\μ is s-Dyck, both λ_{L}\(μ_{1}−λ_{j+1}−1, …, μ_{j}−λ_{j+1}−1) and λ_{R}\(μ_{j+1}, μ_{j+2}, …) are s-Dyck. Conversely, given two shifted partitions ν = (ν_{1}, ν_{2}, …) ∈ SD(λ_{L}) and ρ = (ρ_{1}, ρ_{2}, …) ∈ SD(λ_{R}) then (by Lemma 2.1, applied to λ_{L}\ν and x_{0}−1) ν_{j−1} ≥ 1 so ⌊\frac{d(λ_{L}\ν)}{2}⌋ = 0 and λ \ (ν_{1} + λ_{j+1} + 1, …, ν_{j} + λ_{j+1} + 1, ρ_{1}, ρ_{2}, …) is s-Dyck. This is clearly a bijection so

F_{λ}(q, t, s) = F_{λ_{L}}(q, t, s) F_{λ_{R}}(q, t, s)
= ∏_{x∈V^{∗}(λ_{L})}(1 + q^{|θ(x)_{S}|} t) ∏_{x∈V^{∗}(λ_{R})}(1 + q^{|θ(x)_{S}|} t s^{⌊ \frac{d(θ(x)_{S})}{2} ⌋})
= ∏_{x∈V^{∗}(λ)}(1 + q^{|θ(x)_{S}|} t s^{⌊ \frac{d(θ(x)_{S})}{2} ⌋}).

Suppose now that θ is ballot. Then λ_{2} = λ_{1} − 1.

Suppose first that λ_{1} is even. Let μ ∈ SD(λ). We claim that then 1 ∈ μ. Suppose not. Let θ′ be the outer border strip of the connected component of λ \ μ that contains 1. Note that θ′ ⊆ θ. Let z′ be the rightmost cell of θ′ such that lv(z′) = lv(1) (possibly z′ = 1) and let w be the rightmost cell of θ′. Since |θ| = λ_{1} is even z′ is not the rightmost cell of θ. Furthermore, lv(z′ + 1) = lv(z′) + 1, so z′ ≠ w. Hence, since λ \ μ is s-Dyck, w^{(1)} ∈ λ \ μ which implies that w = |θ|. Hence |θ′| = |θ| ≡ 0 (mod 2), which contradicts the fact that λ \ μ is s-Dyck. This proves our claim. Hence λ\μ is a vertical translate of (λ_{2}, λ_{3}, …)\(μ_{2}, μ_{3}, …) and therefore (λ_{2}, λ_{3}, …)\(μ_{2}, μ_{3}, …) is s-Dyck. Conversely, if ρ = (ρ_{1}, ρ_{2}, …) ∈ SD((λ_{2}, λ_{3}, …)) then λ \ (λ_{1}, ρ_{1}, ρ_{2}, …) is s-Dyck. This is clearly a bijection so

F_{λ}(q, t, s) = F_{(λ_{2},λ_{3},...)}(q, t, s)
= ∏_{x∈V^{∗}((λ_{2},λ_{3},...))}(1 + q^{|θ(x)_{S}|} t s^{⌊ \frac{d(θ(x)_{S})}{2} ⌋})
= ∏_{x∈V^{∗}(λ)}(1 + q^{|θ(x)_{S}|} t s^{⌊ \frac{d(θ(x)_{S})}{2} ⌋}).

Suppose now that λ_{1} is odd. Reasoning as in the previous case we conclude that

∑_{\{μ∈SD(λ): 1∈μ\}} q^{|λ\μ|} t^{dp(λ\μ)} s^{⌊ \frac{d(λ\μ)}{2} ⌋} = F_{(λ_{2},λ_{3},...)}(q, t, s).  (1)

Let now μ ∈ SD(λ) be such that 1 ∉ μ. We claim that then μ ⊆ λ \ θ. In fact, suppose by contradiction that 1, 2, …, a−1 ∉ μ but a ∈ μ. Then lv(a−1) = lv(a)+1 and hence, since θ is ballot, lv(a − 1) > lv(1). But θ′ =^{def} {1, 2, …, a − 1} is the outer border strip of the connected component η of λ \ μ that contains 1. Since η is s-Dyck, θ′_{S} ⊆ η, so (a − 1)^{(1)} ∈ λ \ μ. But this implies that a ∈ λ \ μ, contrary to our assumption. This proves our claim. Hence θ is the outer border strip of λ \ μ and therefore, since λ\μ is s-Dyck, μ ⊆ λ\θ_{S} and (λ\θ_{S})\μ is s-Dyck. Also, by Lemma 2.1, d(λ \ μ) = d((λ \ θ_{S}) \ μ) + 1 = 1 if θ is Dyck, while d(λ \ μ) = d((λ \ θ_{S}) \ μ) + 2 if θ is not Dyck. Conversely, if ρ ∈ SD(λ \ θ_{S}) then, since |θ| = λ_{1} is odd, λ \ ρ is s-Dyck and 1 ∉ ρ. Therefore

F_{λ}(q, t, s) = ∑_{\{μ∈SD(λ): 1∈μ\}} q^{|λ\μ|} t^{dp(λ\μ)} s^{⌊ \frac{d(λ\μ)}{2} ⌋} + ∑_{\{μ∈SD(λ): 1∉μ\}} q^{|λ\μ|} t^{dp(λ\μ)} s^{⌊ \frac{d(λ\μ)}{2} ⌋}
= F_{(λ_{2},λ_{3},...)}(q, t, s) + q^{|θ_{S}|} t s^{⌊ \frac{d(θ_{S})}{2} ⌋} ∑_{μ∈SD(λ\θ_{S})} q^{|(λ\θ_{S})\μ|} t^{dp((λ\θ_{S})\μ)} s^{⌊ \frac{d((λ\θ_{S})\μ)}{2} ⌋}
= ∏_{x∈V^{∗}((λ_{2},λ_{3},...))}(1 + q^{|θ(x)_{S}|} t s^{a(x)}) + q^{|θ_{S}|} t s^{⌊ \frac{d(θ_{S})}{2} ⌋} ∏_{x∈V^{∗}(λ\θ_{S})}(1 + q^{|θ(x)_{S}|} t s^{a(x)}).

Let x ∈ V^{∗}(λ) \ {1}. Let z be the rightmost cell of θ such that lv(z) = lv(1). Assume first that x < z. Then since θ is ballot, lv(x) > lv(x − 1) ≥ lv(1) so θ(x) is Dyck and θ(x)_{S} = θ(x). But then x^{(1)} ∈ V(λ \ θ_{S}), θ(x^{(1)}) is Dyck, and |θ(x^{(1)})_{S}| = |θ(x^{(1)})| = |θ(x)| = |θ(x)_{S}| so x^{(1)} ∈ V^{∗}(λ\θ_{S}). Assume now that x > z. Then x > z +1 (for |θ(z +1)| = |θ|−z is even since |θ| is odd). Then x^{(2)} ∈ V(λ\θ_{S}) and θ(x^{(2)}) = θ(x)^{(2)}. Hence x^{(2)} ∈ V^{∗}(λ \ θ_{S}) and |θ(x^{(2)})_{S}| = |θ(x)_{S}|. Conversely, let x ∈ θ, 2 ≤ x ≤ z, be such that x^{(1)} ∈ V^{∗}(λ \ θ_{S}). Then x < z and x ∈ V(λ). Also, since θ is ballot, lv(x^{(1)}) ≥ lv(1) − 1 while lv(z^{(1)}) = lv(1) − 2. Hence θ(x^{(1)}) is Dyck and θ(x^{(1)}) ⊆ {y^{(1)} : y ∈ θ, y < z}, so θ(x) = {y ∈ θ : y^{(1)} ∈ θ(x^{(1)})} and therefore x ∈ V^{∗}(λ). Similarly, if x ∈ θ, x > z, is such that x^{(2)} ∈ V^{∗}(λ \ θ_{S}) then x ∈ V(λ) and θ(x) = {y ∈ θ : y^{(2)} ∈ θ(x^{(2)})} so x ∈ V^{∗}(λ). Therefore the map f defined by

x ↦ \{ \begin{matrix}x^{(1)}, & if x < z, \\ x^{(2)}, & if x > z, \end{matrix}

is a bijection between V^{∗}(λ) \ {1} and V^{∗}(λ \ θ_{S}) such that |θ(x)_{S}| = |θ(f(x))_{S}| and d(θ(x)_{S}) = d(θ(f(x))_{S}) for all x ∈ V^{∗}(λ) \ {1}. Hence

∏_{x∈V^{∗}(λ\θ_{S})}(1 + q^{|θ(x)_{S}|} t s^{⌊ \frac{d(θ(x)_{S})}{2} ⌋}) = ∏_{x∈V^{∗}(λ)\\{1\}}(1 + q^{|θ(x)_{S}|} t s^{⌊ \frac{d(θ(x)_{S})}{2} ⌋})  (2)

and therefore

F_{λ}(q, t, s) = ∏_{x∈V^{∗}(λ)\\{1\}}(1 + q^{|θ(x)_{S}|} t s^{a(x)}) + q^{|θ_{S}|} t s^{⌊ \frac{d(θ_{S})}{2} ⌋} ∏_{x∈V^{∗}(λ)\\{1\}}(1 + q^{|θ(x)_{S}|} t s^{a(x)})

and the result follows since 1 ∈ V^{∗}(λ) and θ(1) = θ. □

4 Enumeration

In this section we study the generating function for s-Dyck skew shifted partitions according to four natural statistics.

Let

D(t, q, x, s) =^{def} ∑_{ν} t^{dp(ν)}q^{|ν|}x^{w(ν)}s^{⌊ \frac{d(ν)}{2} ⌋}  (3)

where the sum is over all (up to translation) the connected s-Dyck skew shifted partitions ν ≠ ∅, and w(ν) is the width of ν (i.e., the size of the outer border strip of ν) and write

D(t, q, x, s) = ∑_{n≥1} SD_{n}(t, q, s) x^{n}  (4)

so that

SD_{n}(t, q, s) = ∑_{ν} t^{dp(ν)}q^{|ν|}s^{⌊ \frac{d(ν)}{2} ⌋}  (5)

where ν runs over all (up to translation) the connected s-Dyck skew shifted partitions whose outer border strip has size n. So, for example, SD_{3}(t, q, s) = tq^{5}s + t^{2}q^{6}s + t^{2}q^{4} + tq^{3}. Note that d(ν) is not invariant under translation, while ⌊\frac{d(ν)}{2}⌋ is.

We begin by establishing the relationship between the generating function D(t, q, x, s) and the generating function F(t, q, x) studied in [4], namely

F(t, q, x) =^{def} ∑_{ν} t^{dep(ν)} q^{|ν|}x^{\frac{w(ν)+1}{2}}  (6)

where ν runs over all (up to translation) the non-empty connected Dyck skew partitions.

This rests on the following result, which is also of independent interest. Proposition 4.1 Let η be a skew shifted partition with only one rightmost cell. Then η is s-Dyck (as a skew shifted partition) if and only if η is Dyck (as a skew partition). Furthermore, in this case dep(η) = dp(η). Proof. We may clearly assume that η is connected. It is easy to see that any skew partition η that is Dyck (as a skew partition) is also s-Dyck (as a skew shifted partition), and dep(η) = dp(η). Conversely, assume that η is s-Dyck. We proceed by induction on |η|. Let m be the (unique) rightmost cell of η. Then m ∈ θ (where θ is the outer border strip of η) while m^{(1)} ∉ η (by the uniqueness of m). Hence, since θ_{S} ⊆ η, lv(m) = lv(1). Therefore θ is Dyck, and η \ θ = η \ θ_{S}. But η \ θ_{S} is s-Dyck, and η \θ_{S} has only one rightmost cell. Therefore, by our induction hypothesis, η \θ_{S} is Dyck, and dep(η \ θ_{S}) = dp(η \ θ_{S}). Hence η \ θ is Dyck, and therefore η is Dyck and dep(η) = dp(η). □ Corollary 4.2

xD(t, q, x, 0) = F(t, q, x^{2})

Proof. It follows from (3) that

xD(t, q, x, 0) = ∑_{ν} t^{dp(ν)} q^{|ν|} x^{w(ν)+1}

where ν runs over all the connected s-Dyck skew shifted partitions ν such that d(ν) ≤ 1. But these s-Dyck skew shifted partitions are exactly those that have exactly one rightmost cell, so the result follows from Proposition 4.1 and (6). □

Using Theorem 3.1 we can show that the coefficients SD_{n}(t, q, s) are, essentially, generating functions over ballot paths.

Proposition 4.3 Let n ∈ P. Then

SD_{n}(t, q, s) = \{ \begin{matrix}0, & if n is even, \\ ∑_{θ} t q^{|θ_{S}|}s^{⌊ \frac{d(θ_{S})}{2} ⌋} ∏_{x∈V^{∗}(θ)\\{1\}}(1 + t q^{|θ(x)_{S}|} s^{⌊ \frac{d(θ(x)_{S}}{2} ⌋}), & if n is odd, \end{matrix}

where θ runs over all (up to translation) the ballot cbs’s of size n.

Proof. We may clearly assume that all the skew shifted partitions appearing in the sum on the RHS of (5) have (1, n) as their leftmost cell. If n is even then SD_{n}(t, q, s) = 0 so assume that n is odd, n = 2m + 1. Let λ \ μ be such a partition, and θ be its outer border strip. Note that θ is also the outer border strip of λ, and that λ is uniquely determined by θ. Since λ \ μ is s-Dyck, θ is ballot, θ_{S} ⊆ λ \ μ, and μ ∈ SD(λ \ θ_{S}). Conversely, given a ballot cbs θ of size n whose leftmost cell is (1, n) and μ ∈ SD(λ \ θ_{S}) (where λ is the only shifted partition whose outer border strip is θ) then λ \ μ is a connected s-Dyck skew shifted partition having (1, n) as its leftmost cell and outer border strip of size n. Furthermore, if d(θ_{S}) = 1 then θ is Dyck so lv(|θ|) = lv(1) and hence, by Lemma 2.1, d(λ \ μ) = 1. Therefore

SD_{n}(t, q, s) = ∑_{θ} tq^{|θ_{S}|}s^{⌊ \frac{d(θ_{S})}{2} ⌋} ∑_{μ∈SD(λ\θ_{S})} t^{dp((λ\θ_{S})\μ)} q^{|(λ\θ_{S})\μ|} s^{⌊ \frac{d((λ\θ_{S})\μ)}{2} ⌋}

where θ runs over all the ballot cbs’s having size n and leftmost cell (1, n). Now, by Theorem 3.1 we have that

∑_{μ∈SD(λ\θ_{S})} t^{dp((λ\θ_{S})\μ)} q^{|(λ\θ_{S})\μ|} s^{⌊ \frac{d((λ\θ_{S})\μ)}{2} ⌋} = ∏_{x∈V^{∗}(λ\θ_{S})}(1 + q^{|θ(x)_{S}|} t s^{⌊ \frac{d(θ(x)_{S})}{2} ⌋}).

But, reasoning as in the proof of (2) (note that |θ| is odd and θ is ballot) we conclude that

∏_{x∈V^{∗}(λ\θ_{S})}(1 + q^{|θ(x)_{S}|} t s^{⌊ \frac{d(θ(x)_{S})}{2} ⌋}) = ∏_{x∈V^{∗}(λ)\\{1\}}(1 + q^{|θ(x)_{S}|} t s^{⌊ \frac{d(θ(x)_{S})}{2} ⌋}).

Therefore

SD_{n}(t, q, s) = ∑_{θ} t q^{|θ_{S}|}s^{⌊ \frac{d(θ_{S})}{2} ⌋} ∏_{x∈V^{∗}(λ)\\{1\}}(1 + q^{|θ(x)_{S}|} t s^{⌊ \frac{d(θ(x)_{S})}{2} ⌋})

where θ runs over all (up to translation) the ballot cbs’s of size n, and the result follows. □

The results obtained so far make it natural to try to understand V^{∗}(η) more in detail. We show next that its cardinality is not hard to compute. For a cbs θ let

m(θ) =^{def} min{j ∈ N : lv(x) ≥ lv(1) − j for all x ∈ θ}.  (7)

Proposition 4.4 Let θ be a connected border strip. Then

|V^{∗}(θ)| = \{ \begin{matrix}⌈\frac{|θ|}{2}⌉ , & if θ is ballot, \\ ⌈\frac{|θ|−m(θ)+1}{2}⌉ , & otherwise. \end{matrix}

Proof. Suppose first that θ is ballot. Write lv(|θ|) = lv(1) + t. Then t ∈ N and t + 1 ≡ |θ| (mod 2). For i ∈ [0, t] let

x_{i} =^{def} max {x ∈ [|θ|] : lv(x) = lv(1) + i}.

Then 1 ≤ x_{0} < x_{1} < ⋯ < x_{t} = |θ| (for x_{i−1} < x_{i} implies lv(x_{i} + 1) = lv(x_{i}) + 1, so x_{i+1} > x_{i}) and x_{i} ≡ i + 1 (mod 2) for i = 0, …, t.

Now let x ∈ V(θ). If x_{i−1} + 2 ≤ x ≤ x_{i} for some i ∈ [0, t] (where x_{−1} =^{def} 0) then θ(x) is Dyck (for lv(x) > lv(x − 1) ≥ lv(1) + i = lv(x_{i})) so |θ(x)| is odd and hence x ∈ V^{∗}(θ). If x = x_{i−1} + 1 for some i ∈ [0, t] then θ(x) = {y ∈ θ : y > x_{i−1}} so |θ(x)| = |θ| − x_{i−1} ≡ t + 1 − i (mod 2), and therefore x ∈ V^{∗}(θ) if and only if i ≡ t (mod 2). Therefore

|V^{∗}(θ)| = |V^{∗}(θ) ∩ {1, x_{0} + 1, …, x_{t−1} + 1}| + ∑_{i=0}^{t} |V^{∗}(θ) ∩ [x_{i−1} + 2, x_{i}]|
= ⌊\frac{t}{2}⌋ + 1 + ∑_{i=0}^{t} |V(θ) ∩ [x_{i−1} + 2, x_{i}]|
= ⌊\frac{t}{2}⌋ + 1 + ∑_{i=0}^{t} \frac{x_{i} − x_{i−1} − 1}{2},

since [x_{i−1} + 1, x_{i}] is a Dyck cbs for i = 0, …, t, and the result follows in this case.

Suppose now that θ is not ballot. Let z be the leftmost cell of θ such that lv(z) = lv(1) − m(θ). Then z ≢ m(θ) (mod 2). Let x ∈ V(θ), x < z. Then lv(x) > lv(z) so θ(x) is Dyck hence |θ(x)| is odd and therefore x ∈ V^{∗}(θ). Furthermore, [z, |θ|] is a ballot cbs and therefore

|V^{∗}(θ) ∩ [z, |θ|]| = ⌈\frac{|θ| − z}{2} ⌉ ,

by what we have just proved (note that z ∉ V(θ), but z ∈ V^{∗}([z, |θ|]) if and only if |θ| ≡ z (mod 2)). Therefore

|V^{∗}(θ)| = |V^{∗}(θ) ∩ [1, z − 1]| + |V^{∗}(θ) ∩ [z, |θ|]|
= |V(θ) ∩ [1, z − 1]| + ⌈\frac{|θ| − z}{2} ⌉
= 1 + \frac{z − 1 − m(θ)}{2} + ⌈\frac{|θ| − z}{2} ⌉
= ⌈\frac{|θ| − m(θ) + 1}{2}⌉ ,

and the result again follows. □

The preceding result has the following consequence.

Corollary 4.5 Let λ ∈ S and θ be its outer border strip. Then

|SD(λ)| = \{ \begin{matrix}2^{⌈^{\frac{|θ|}{2}}⌉}, & if θ is ballot, \\ 2^{⌈^{\frac{|θ|−m(θ)+1}{2}}⌉}, & otherwise, \end{matrix}

where m(θ) is defined in (7).

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

We are unable to find a formula for D(t, q, x, s). In fact, no formula is currently known for D(t, q, x, 0). However, there is an explicit formula if q = 1.

Theorem 4.6

D(t, 1, x, s) = t(1 − s) \frac{1 − \sqrt{1 − 4(1 + t)x^{2}}}{2(1 + t)x(1 + ts)}

+\frac{tsx(1 + t)^{2} (1 − \sqrt{1 − 4(1 + t)x^{2}})}{2x^{2}(1 + t)(1 + ts)(2 + t + ts) − (1 + ts)^{2} (1 − \sqrt{1 − 4(1 + t)x^{2}})}.

Proof. We have from (4) and Proposition 4.3 that

D(t, 1, x, s) = ∑_{m≥0} SD_{2m+1}(t, 1, s) x^{2m+1}.  (8)

Now note that, by the first part of the proof of Proposition 4.4, if θ is a ballot cbs of size 2m + 1 then (using the notation in the proof of Proposition 4.4) |{x ∈ V^{∗}(θ) : d(θ(x)_{S}) = 2}| = |V^{∗}(θ) ∩ {1, x_{0} + 1, …, x_{t−2} + 1}| = h(θ)/2 where h(θ) =^{def} lv(|θ|) − lv(1). Therefore we have from Propositions 4.3 and 4.4 that

SD_{2m+1}(t, 1, s) = ∑_{θ} \frac{ts^{⌊ \frac{d(θ_{S})}{2} ⌋}}{1 + ts^{⌊ \frac{d(θ_{S})}{2} ⌋}} (1 + ts)^{\frac{h(θ)}{2}} (1 + t)^{m+1− \frac{h(θ)}{2}}

where θ runs over all the ballot cbs’s of size 2m + 1. We therefore conclude from (8) that

D(t, 1, x, s) = ∑_{m≥0} ∑_{θ} \frac{ts^{⌊ \frac{d(θ_{S})}{2} ⌋}}{1 + ts^{⌊ \frac{d(θ_{S})}{2} ⌋}} (\frac{1 + ts}{1 + t})^{\frac{h(θ)}{2}} x^{2m+1}(1 + t)^{m+1}
= ∑_{m≥0} x^{2m+1}(1 + t)^{m+1} ∑_{h=0}^{m} ∑_{\{θ: h(θ)=2h\}} \frac{t s^{⌊ \frac{d(θ_{S})}{2} ⌋}}{1 + t s^{⌊ \frac{d(θ_{S})}{2} ⌋}} (\frac{1 + ts}{1 + t})^{h} .

Now note that a ballot cbs θ of size 2m + 1 such that h(θ) = 2h is equivalent to a lattice path (with (0, 1) and (1, 0) steps) having 2m + 1 steps, from the origin to (m − h, m + 1 + h), that never intersects the line y = x except at the origin. Therefore, by a well known result (see, e.g., [6, Theorem B, p.21])

D(t, 1, x, s) = ∑_{m≥0} x^{2m+1}(1 + t)^{m+1} [\frac{t}{(2m + 1)(1 + t)} (\begin{matrix}2m+1 \\ m \end{matrix})

+\frac{ts}{1 + ts} ∑_{h=1}^{m} \frac{2h + 1}{2m + 1} (\begin{matrix}2m+1 \\ m−h \end{matrix}) (\frac{1 + ts}{1 + t})^{h}]

= ∑_{m≥0} x^{2m+1}(1 + t)^{m+1} [\frac{1}{2m + 1} (\begin{matrix}2m+1 \\ m \end{matrix}) \frac{t(1 − s)}{(1 + t)(1 + ts)}

+\frac{ts}{1 + ts} ∑_{h=0}^{m} \frac{2h + 1}{2m + 1} (\begin{matrix}2m+1 \\ m−h \end{matrix}) (\frac{1 + ts}{1 + t})^{h}] .

But, as is well known

∑_{m≥h} \frac{2h + 1}{2m + 1} (\begin{matrix}2m+1 \\ m−h \end{matrix}) y^{m−h} = ( ∑_{m≥0} \frac{1}{2m + 1} (\begin{matrix}2m+1 \\ m \end{matrix}) y^{m})^{2h+1} = (\frac{1 − \sqrt{1 − 4y}}{2y} )^{2h+1}

so

∑_{m≥0}((1 + t)x^{2})^{m} \frac{1}{2m + 1} (\begin{matrix}2m+1 \\ m \end{matrix}) = \frac{1 − \sqrt{1 − 4(1 + t)x^{2}}}{2(1 + t)x^{2}}

while

∑_{m≥0}((1 + t)x^{2})^{m} ∑_{h=0}^{m} \frac{2h + 1}{2m + 1} (\begin{matrix}2m+1 \\ m−h \end{matrix}) (\frac{1 + ts}{1 + t})^{h}

= ∑_{h≥0} (\frac{1 + ts}{1 + t})^{h} ∑_{m≥h} \frac{2h + 1}{2m + 1} (\begin{matrix}2m+1 \\ m−h \end{matrix}) ((1 + t)x^{2})^{m}
= ∑_{h≥0}((1 + ts)x^{2})^{h} (\frac{1 − \sqrt{1 − 4(1 + t)x^{2}}}{2(1 + t)x^{2}} )^{2h+1}
= \frac{1 − \sqrt{1 − 4(1 + t)x^{2}}}{2(1 + t)x^{2}} \frac{1}{1 − (1 + ts)^{\frac{(1−\sqrt{1−4(1+t)x^{2}})^{2}}{4(1+t)^{2}x^{2}}}}

= \frac{1 − \sqrt{1 − 4(1 + t)x^{2}}}{2(1 + t)x^{2}} \frac{2x^{2}(1 + t)^{2}}{2x^{2}(1 + t)^{2} − (1 + ts) [1 − 2(1 + t)x^{2} − \sqrt{1 − 4(1 + t)x^{2}}]},

and the result follows. □

Note that when s = 0 Theorem 4.6 reduces, by Corollary 4.2, to Proposition 5.4 of [4].

The preceding theorem has the following elegant and surprisingly simple consequence.

Corollary 4.7 The number of connected s-Dyck skew shifted partitions of width

2m + 1 is 2^{m} ( \begin{matrix}2m \\ m \end{matrix}).

Proof. We have from Theorem 4.6 and the Binomial Theorem that

D(1, 1, x, 1) = \frac{4x (1 − \sqrt{1 − 8x^{2}})}{32x^{2} − 4 (1 − \sqrt{1 − 8x^{2}})}
= \frac{x}{\sqrt{1 − 8x^{2}}}
= x ∑_{m≥0} ( \begin{matrix}2m \\ m \end{matrix}) (2x^{2})^{m},

so the result follows from (4) and (5). □

It would be interesting to have a direct combinatorial proof of Corollary 4.7.

5 Applications

In this section, as consequences of our main results, we derive some new identities for the parabolic Kazhdan-Lusztig polynomials of Hermitian symmetric pairs, and for the ordinary Kazhdan-Lusztig polynomials of some Weyl groups.

We follow [1] for Coxeter groups notation and terminology. In particular, given a Coxeter system (W, S) and J ⊆ S we let W_{J} be the parabolic subgroup generated by J and

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

We always assume that W^{J} is partially ordered by Bruhat order, which we denote by ≤. It is well known that W^{J}, with this partial order, is a graded poset having l as its rank function.

For J ⊆ S we denote by {P_{u,v}^{J,q}(q)}_{u,v∈W^{J}} the parabolic Kazhdan-Lusztig polynomials of W^{J} of type q (we refer the reader to [7] for the definition of these polynomials). It follows immediately from [7, §§2-3] and from well known facts (see, e.g., [8, §7.5] and [8, §§7.9-11]) that P_{u,v}^{∅,q}(q) is the (ordinary) Kazhdan-Lusztig polynomial of u, v ∈ W which we denote simply by P_{u,v}(q), as customary.

Shifted-Dyck skew shifted partitions arise in the study of the parabolic Kazhdan-Lusztig polynomials of certain quotients W^{J} such that (W, W_{J}) is a Hermitian symmetric pair (see [3] and [5]). These quotients have been classified (see, e.g., [2]) and there are five infinite families and two exceptional ones. Using the standard notation for the classification of the finite Coxeter systems (see, e.g., [1, App. A1]), the Hermitian symmetric pairs are: (A_{n}, A_{i−1} × A_{n−i}), (B_{n}, A_{n−1}), (B_{n}, B_{n−1}), (D_{n}, A_{n−1}), (D_{n}, D_{n−1}), (E_{6}, D_{5}), (E_{7}, E_{6}), (n ≥ 3, 1 ≤ i ≤ n). The connection between the Hermitian symmetric pairs (B_{n}, A_{n−1}) and (D_{n}, A_{n−1}), their parabolic Kazhdan-Lusztig polynomials, and (s-Dyck) skew shifted partitions is given by the following result (see [5, §2 and Theorem 4.1]).

Theorem 5.1 Let W^{J} be such that (W, W_{J}) = (B_{n}, A_{n−1}) (resp., (D_{n}, A_{n−1})). Then:

i) there is an explicit poset isomorphism Λ_{B} : W^{J} → {λ ∈ S : λ ⊆ δ_{n}} (resp., Λ_{D} : W^{J} → {λ ∈ S : λ ⊆ δ_{n−1}});

ii) for all u, v ∈ W^{J}, u ≤ v

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

where μ =^{def} Λ_{B}(u), λ =^{def} Λ_{B}(v) (resp., μ =^{def} Λ_{D}(u), λ =^{def} Λ_{D}(v)).

We refer the reader to [5] for the definition of the maps Λ_{B} and Λ_{D}. Theorem 5.1 allows the transfer of enumerative and combinatorial properties from s-Dyck skew shifted partitions to these parabolic Kazhdan-Lusztig polynomials. In particular, Theorem 3.1 implies the following result.

Corollary 5.2 Let W^{J} be such that (W, W_{J}) = (B_{n}, A_{n−1}) (resp., (D_{n}, A_{n−1})) and v ∈ W^{J}. Then

∑_{u∈W^{J}} P_{u,v}^{J,q}(q) = ∏_{x∈V^{∗}(λ)} (1 + q^{\frac{|θ(x)_{S} |−1}{2}} )

where λ =^{def} Λ_{B}(v) (resp., Λ_{D}(v)).

Proof. This follows immediately from Theorems 3.1 and 5.1. □. The preceding result, and Corollary 6.2 of [4], make it natural to wonder if such a factorization actually holds for all Hermitian symmetric pairs. Surprisingly, the answer is yes.

Theorem 5.3 Let (W, W_{J}) be a Hermitian symmetric pair and v ∈ W^{J}. Then there exists a set E(v) and a map θ_{v} : E(v) → N such that

∑_{u∈W^{J}} P_{u,v}^{J,q}(q) = ∏_{x∈E(v)}(1 + q^{θ_{v}(x)}).

In particular, ∑_{u∈W^{J}} P_{u,v}^{J,q}(1) = 2^{|E(v)|}.

Proof. This follows from Corollary 6.2 of [4], Corollary 5.2, Theorems 4.2 and 4.3 of [5] and from computer calculations for the exceptional Hermitian symmetric pairs. □

The parabolic Kazhdan-Lusztig polynomials for the exceptional Hermitian symmetric pairs have been computed by implementing in Maple 6 the recursions given by [7, Proposition 3.1]. These implementations use two Maple packages for handling finite Coxeter groups (Version 2.3) and posets (Version 2.2) developed by John Stembridge.

The preceding result, and Corollary 4.4 of [5], imply that there is a bijection between the u ∈ W^{J} such that P_{u,v}^{J,q}(q) ≠ 0 and the subsets of E(v). Such a bijection is given by Theorem 4.1 of [4] for the Hermitian symmetric pairs (A_{n}, A_{i−1} × A_{n−i}) (n ≥ 3, 1 ≤ i ≤ n). It would be interesting to find such a bijection in general.

It is well known (see, e.g., [7, Proposition 3.4]) that the parabolic Kazhdan-Lusztig polynomials of type q can be expressed as alternating sums of ordinary Kazhdan-Lusztig polynomials. We may therefore derive from Theorem 5.3 the following identity for the (ordinary) Kazhdan-Lusztig polynomials. Recall (see, e.g., [1, Proposition 2.4.4]) that given u ∈ W and J ⊆ S there are unique elements u_{J} ∈ W_{J} and u^{J} ∈ W^{J} such that u = u_{J}u^{J}.

Corollary 5.4 Let (W, W_{J}) be a Hermitian symmetric pair and v ∈ W^{J}. Then there exists a set E(v) and a map θ_{v} : E(v) → N such that

∑_{u∈W}(−1)^{l(u_{J})}P_{u,v}(q) = ∏_{x∈E(v)}(1 + q^{θ_{v}(x)}).

Proof. This follows immediately from Theorem 5.3 and Proposition 3.4 of [7]. □

Acknowledgments. Most of the computer calculations in this paper have been carried out using a Maple package for finite Coxeter groups and a Maple package for handling posets developed by John Stembridge.

References

[1] A. Björner, F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, 231, Springer-Verlag, New York, 2005.

[2] B. Boe, Kazhdan-Lusztig polynomials for Hermitian symmetric spaces, Trans. Amer. Math. Soc., 309 (1988), 279-294.

[3] F. Brenti, Kazhdan-Lusztig and R-polynomials, Young’s lattice, and Dyck partitions, Pacific J. Math., 207 (2002), 257-286.

[4] F. Brenti, Enumerative and combinatorial properties of Dyck partitions, J. Comb. Theory, Ser. A, 99 (2002), 51-74.

[5] F. Brenti, Parabolic Kazhdan-Lusztig polynomials for Hermitian symmetric pairs, Trans. Amer. Math. Soc., to appear.

[6] L. Comtet, Advanced Combinatorics, Reidel, Dordrecht/Boston, 1974.

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

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

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

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