THESIS FOR THE DEGREE OF LICENTIATE OF PHILOSOPHY

On q-Narayana numbers and real-rooted polynomials in

combinatorics

PETTER BRÄNDÉN

Department of Mathematics CHALMERS UNIVERSITY OF TECHNOLOGY AND GÖTEBORG UNIVERSITY Göteborg, Sweden 2003 On q-Narayana numbers and real-rooted polynomials in combinatorics PETTER BRÄNDÉN

\begin{matrix}c \\ ◯ \end{matrix}PETTER BRÄNDÉN, 2003 Preprint no 2003:14 ISSN 0347-2809 Department of Mathematics Chalmers University of Technology and Göteborg University SE-412 96 Göteborg Sweden Telephone + 46(0)31-7721000

Matematiskt Centrum Göteborg, Sweden 2003

ABSTRACT

This thesis consists of three papers: “On operators on polynomials preserving real-rootedness and the Neggers-Stanley Conjecture”, “The generating function of 2-stack sortable permutations by descents is real-rooted and q-Narayana numbers and the flag h-vector of J(2 × n)”.

The first paper is concerned with real-rooted polynomials. Here we extend and refine a theorem of Wagner on Hadamard products of Toeplitz matrices. We also apply our results to polynomials for which the Neggers-Stanley Conjecture is known to hold. More precisely, we settle interlacing properties for E-polynomials of series-parallel posets and column-strict labelled Ferrers posets.

The second paper is a note on a conjecture of Bóna. For fixed n ≥ 0 and t ≥ 1, the generating function of t-stack sortable permutations by descents is conjectured to be real-rooted. The conjecture is known to be true for t = 1 and t = n − 1. Here we prove it for t = 2.

The third paper is a about Narayana- and q-Narayana numbers. The Narayana numbers are N(n, k) = \frac{1}{n} \binom{n}{k}\binom{n}{k+1}. There are several natural statistics on Dyck paths with a distribution given by N(n, k). We show the equidistribution of Narayana statistics by computing the flag h-vector of J(2×n) in different ways. In the process we discover new Narayana statistics and provide co-statistics for which the Narayana statistics in question have a distribution given by Fürlinger and Hofbauer’s q-Narayana numbers. We interpret the flag h-vector in terms of semi-standard Young tableaux, which enables us to express the q-Narayana numbers in terms of Schur functions. We also introduce what we call pre-shellings of simplicial complexes. They are certain partial orders on the facets of the complex with the property that every linear extension is a shelling.

ACKNOWLEDGEMENTS

First of all I would like thank my advisor, Einar Steingrímsson, for his interest in this work, and for his guidance and enthusiasm. I also thank my friends and colleagues at the department of Mathematics; especially Anders, Fredrik, Henrik, Håkan, Jonas, Marcus, Robert and Sergey.

ON OPERATORS ON POLYNOMIALS PRESERVING REAL-ROOTEDNESS AND THE NEGGERS-STANLEY CONJECTURE

PETTER BRÄNDÉN

Abstract. We refine a technique used in a paper by Schur on realrooted polynomials. This amounts to an extension of a theorem of Wagner on Hadamard products of Toeplitz matrices. We also apply our results to polynomials for which the Neggers-Stanley Conjecture is known to hold. More precisely, we settle interlacing properties for Epolynomials of series-parallel posets and column-strict labelled Ferrers posets.

1. Introduction

Several polynomials associated to combinatorial structures are known to have real zeros. In most cases one can say more about the location of the zeros, than just that they are on the real axis. The matching polynomial of a graph is not only real-rooted, but it is known that the matching polynomial of the graph obtained by deleting a vertex of G interlaces that of G [4]. The same is true for the characteristic polynomial of graph (see e.g., [3]). If A is a nonnegative matrix and A′ is the matrix obtained by either deleting a row or a column, then Nijenhuis [7] showed that the rook polynomial of A′ interlaces that of A.

The Neggers-Stanley Conjecture asserts that certain polynomials associated to posets, see Section 3, have real zeros; see [1, 9, 13] for the state of the art. For classes of posets for which the conjecture is known to hold we will exhibit explicit interlacing relationships.

The first part of this paper is concerned with operators on polynomials which preserve real-rootedness. The following classical theorem is due to Schur [10]: Theorem 1 (Schur). Let f = a_{0} + a_{1}x + ⋯ + a_{n}x^{n} and g = b_{0} + b_{1}x + ⋯ + b_{m}x^{m} be polynomials in ℝ[x]. Suppose that f and g have only real zeros and that the zeros of g are all of the same sign. Then the polynomial

f ⊙ g := ∑_{k} k!a_{k}b_{k}x^{k},

has only real zeros. If a_{0}b_{0} ≠ 0 then all the zeros of f ⊙ g are distinct.

Date: 7th March 2003.

In this paper we will refine the technique used in Schur’s proof of the theorem to extend a theorem of Wagner [14, Theorem 0.3]. The diamond product of two polynomials f and g is the polynomial

f◇g = ∑_{n≥0} \frac{f^{(n)}(x)}{n!} \frac{g^{(n)}(x)}{n!}x^{n}(x + 1)^{n}.

Brenti [1] conjectured an equivalent form of Theorem 2 and Wagner proved it in [14].

Theorem 2 (Wagner). If f, g ∈ ℝ[x] have all their zeros in the interval [−1, 0] then so does f◇g.

This theorem has important consequences in combinatorics [13], and it also has implications to the theory of total positivity [14].

In the second part of the paper we settle interlacing properties for Epolynomials of series-parallel posets and column-strict labelled Ferrers posets.

We will implicitly use the fact that the zeros of a polynomial are continuous functions of the coefficients of the polynomial. In particular, the limit of real-rooted polynomials will again be real-rooted. For a treatment of these matters we refer the reader to [6].

2. Sturm sequences and linear operators preserving real-rootedness

Let f and g be real polynomials. We say that f and g alternate if f and g are real-rooted and either of the following conditions hold:

(A) deg(g) = deg(f) = d and

α_{1} ≤ β_{1} ≤ α_{2} ≤ ⋯ ≤ β_{d−1} ≤ α_{d} ≤ β_{d},

where α_{1} ≤ ⋯ ≤ α_{d} and β_{1} ≤ ⋯ ≤ β_{d} are the zeros of f and g respectively

(B) deg(f) = deg(g) + 1 = d and

α_{1} ≤ β_{1} ≤ α_{2} ≤ ⋯ ≤ β_{d−1} ≤ α_{d}

where α_{1} ≤ ⋯ ≤ α_{d} and β_{1} ≤ ⋯ ≤ β_{d−1} are the zeros of f and g respectively.

If all the inequalities above are strict then f and g are said to strictly alternate. Moreover, if f and g are as in (B) then we say that g interlaces f, denoted g ⪯ f. In the strict case we write g ≺ f. If the leading coefficient of f is positive we say that f is standard.

For z ∈ ℝ let T_{z} : ℝ[x] → ℝ[x] be the translation operator defined by T_{z}(f(x)) = f(x + z). For any linear operator ϕ : ℝ[x] → ℝ[x] we define a linear transform L_{ϕ} : ℝ[x] → ℝ[x, z] by

L_{ϕ}(f) := ϕ(T_{z}(f))
= ∑_{n} ϕ(f^{(n)})(x)\frac{z^{n}}{n!}  (1)

= ∑_{n} \frac{ϕ(x^{n})}{n!}f^{(n)}(z).

Definition 3. Let ϕ : ℝ[x] → ℝ[x] be a linear operator and let f ∈ ℝ[x]. If ϕ(f^{(n)}) = 0 for all n ∈ ℕ, we let d_{ϕ}(f) = −∞. Otherwise let d_{ϕ}(f) be the smallest integer d such that ϕ(f^{(n)}) = 0 for all n > d.

The set 𝒜^{+}(ϕ) is defined as follows: If d_{ϕ}(f) = −∞, or d_{ϕ}(f) = 0 and ϕ(f) is standard real- and simple-rooted, then f ∈ 𝒜^{+}(ϕ). Moreover, f ∈ 𝒜^{+}(ϕ) if d = d_{ϕ}(f) ≥ 1 and all of the following conditions are satisfied:

(i) ϕ(f^{(i)}) is standard for all i and deg(ϕ(f^{(i−1)})) = deg(ϕ(f^{(i)})) + 1 for 1 ≤ i ≤ d,

(ii) ϕ(f) and ϕ(f′) have no common real zero, (iii) ϕ(f^{(d)}) ≺ ϕ(f^{(d−1)}), (iv) for all ξ ∈ ℝ the polynomial L_{ϕ}(f)(ξ, z) is real-rooted.

Let 𝒜^{−}(ϕ) := {−f : f ∈ 𝒜^{+}(ϕ)} and 𝒜 (ϕ) := 𝒜^{−}(ϕ) ∪ 𝒜^{+}(ϕ).

The following theorem is the basis for our analysis: Theorem 4. Let ϕ : ℝ[x] → ℝ[x] be a linear operator. If f ∈ 𝒜 (ϕ) then ϕ(f) is real- and simple-rooted and if d_{ϕ}(f) ≥ 1 we have

ϕ(f^{(d)}) ≺ ϕ(f^{(d−1)}) ≺ ⋯ ≺ ϕ(f′) ≺ ϕ(f).

Before we give a proof of Theorem 4 we will need a couple of lemmas. Note that \frac{∂}{∂z} L_{ϕ}(f) = L_{ϕ}(f′) so by Rolle’s Theorem we know that L_{ϕ}(f′) is realrooted (in z) if L_{ϕ}(f) is. By Theorem 4 it follows that 𝒜 (ϕ) is closed under differentiation. A (generalised) Sturm sequence is a sequence f_{0}, f_{1}, …, f_{n} of standard polynomials such that deg(f_{i}) = i for 0 ≤ i ≤ n and

f_{i−1}(θ)f_{i+1}(θ) < 0,  (2)

whenever f_{i}(θ) = 0 and 1 ≤ i ≤ n − 1. If f is a standard polynomial with real simple zeros, we know from Rolle’s Theorem that the sequence {f^{(i)}}_{i} is a Sturm sequence. The following lemma is folklore. Lemma 5. Let f_{0}, f_{1}, …, f_{n} be a sequence of standard polynomials with deg(f_{i}) = i for 0 ≤ i ≤ n. Then the following statements are equivalent:

(i) f_{0}, f_{1}, …, f_{n} is a Sturm sequence,

(ii) f_{0} ≺ f_{1} ≺ ⋯ ≺ f_{n}.

The next lemma is of interest for real-rooted polynomials encountered in combinatorics.

Lemma 6. Let a_{m}x^{m} + a_{m+1}x^{m+1} + ⋯ + a_{n}x^{n} ∈ ℝ[x] be real-rooted with a_{m}a_{n} ≠ 0. Then the sequence a_{i} is strictly log-concave, i.e.,

a_{i}^{2} > a_{i−1}a_{i+1}, (m + 1 ≤ i ≤ n − 1).

Proof. See Lemma 3 on page 337 of [5]. □

Proof of Theorem 4. Let f ∈ 𝒜^{+}(ϕ). Clearly we may assume that d = d_{ϕ}(f) > 1. We claim that for 1 ≤ n ≤ d − 1:

ϕ(f^{(n)})(θ) = 0 ⟹ ϕ(f^{(n−1)})(θ)ϕ(f^{(n+1)})(θ) < 0.  (3)

If 1 ≤ n ≤ d − 1 and ϕ(f^{(n)})(θ) = 0, then by condition (ii) and (iii) of Definition 3 we have that there are integers 0 ≤ ℓ < n < k ≤ d with ϕ(f^{(ℓ)})(θ)ϕ(f^{(k)})(θ) ≠ 0. By Lemma 6 and the real-rootedness of L_{ϕ}(f)(θ, z) this verifies (3).

If ϕ(f^{(d)}) is a constant then {ϕ(f^{(n)})}_{n} is a Sturm sequence. Otherwise let g = ϕ(f^{(d)}). Then, since g′ ≺ g ≺ ϕ(f^{(d−1)}), we have that (2) is satisfied everywhere in the sequence {g^{(n)}}_{n} ∪ {ϕ(f^{(n)})}_{n}. This proves the theorem by Lemma 5. □

In order to make use of Theorem 4 we will need further results on realrootedness and interlacings of polynomials. There is a characterisation of alternating polynomials due to Obreschkoff and Dedieu. Obreschkoff proved the case of strictly alternating polynomials, see [8, Satz 5.2], and Dedieu [2] generalised it in the case deg(f) = deg(g). But his proof also covers this slightly more general theorem: Theorem 7. Let f and g be real polynomials. Then f and g alternate (strictly alternate) if and only if all polynomials in the space

{αf + βg : α, β ∈ ℝ}

are real-rooted (real- and simple-rooted).

A direct consequence of Theorem 7 is the following theorem, which the author has not seen previously in the literature. Theorem 8. If ϕ : ℝ[x] → ℝ[x] is a linear operator preserving real-rootedness, then ϕ(f) and ϕ(g) alternate if f and g alternate. Moreover, if ϕ preserves real- and simple-rootedness then ϕ(f) and ϕ(g) strictly alternate if f and g strictly alternate.

Proof. The theorem is an immediate consequence of Theorem 7 since the concept of alternating zeros is translated into a linear condition. □

Lemma 9. Let 0 ≠ h, f, g ∈ ℝ[x] be standard and real-rooted. If h ≺ f and h ≺ g, then h ≺ αf + βg for all α, β ≥ 0 not both equal to zero.

Note that Lemma 9 also holds (by continuity arguments) when all instances of ≺ are replaced by ⪯ in Lemma 9.

Proof. If θ is a zero of h then clearly αf+βg has the same sign as f and g at θ. Since {h^{(i)}}_{i}∪{f} is a Sturm sequence by Lemma 5, so is {h^{(i)}}_{i}∪{αf +βg}. By Lemma 5 again the proof follows. □

We will need two classical theorems on real-rootedness. The first theorem is essentially due to Hermite and Poulain and the second is due to Laguerre. Theorem 10 (Hermite, Poulain). Let f(x) = a_{0} + a_{1}x + ⋯ + a_{n}x^{n} and g be real-rooted. Then the polynomial

f(\frac{d}{dx})g := a_{0}g(x) + a_{1}g′(x) + ⋯ + a_{n}g^{(n)}(x)

is real-rooted. Moreover, if x^{N} ∤ f and deg(g) ≥ N − 1 then any multiple zero of f(\frac{d}{dx})g is a multiple zero of g.

Proof. The case N = 1 is the Hermite-Poulain theorem. A proof can be found in any of the references [5, 8, 10]. For the general result it will suffice to prove that if deg(g) ≠ 0 then any multiple zero of g′ is a multiple zero of g. Let

g = c_{0} + c_{1}(x − θ) + ⋯ + c_{M}(x − θ)^{M},

where c_{M} ≠ 0, M > 0 and (x − θ)^{2}|g′. Then c_{1} = c_{2} = 0 and M > 2. If c_{0} = 0 we are done and if c_{0} ≠ 0 we have by Lemma 6 that 0 = c_{1}^{2} > c_{0}c_{2} = 0, which is a contradiction. □

Theorem 11 (Laguerre). If a_{0} + a_{1}x + a_{2}x^{2} + ⋯ + a_{n}x^{n} is real-rooted then so is

a_{0} + a_{1}x + \frac{a_{2}}{2!} x^{2} + ⋯ + \frac{a_{n}}{n!} x^{n}.

Proof. Claim (ii) can be derived from (i) when applied to x^{n}, (see [1]), or from Theorem 1 as in [5, 10]. □

We are now in a position to extend Theorem 2. Theorem 12. Let h be [−1, 0]-rooted and let f be real-rooted.

(a) Then f◇h is real-rooted, and if g ⪯ f then

g◇h ⪯ f◇h.

(b) If h is (−1, 0)- and simple-rooted and f is simple-rooted then f◇h is

simple-rooted and

g◇h ≺ f◇h,

for all g ≺ f.

Proof. First we assume that deg(h) > 0 and that h is standard, (−1, 0)- rooted and has simple zeros. Let ϕ : ℝ[x] → ℝ[x] be the linear operator defined by ϕ(f) = f◇h.

We will show that f ∈ 𝒜^{+}(ϕ) if f is standard real- and simple-rooted. Clearly we may assume that deg(f) = d ≥ 1. Condition (i) of Definition 3 follows immediately from the definition of the diamond product. Now, f^{(d−1)} = ax + b, where a, b ∈ ℝ and a > 0 so

ϕ(f^{(d)}) = ah and
ϕ(f^{(d−1)}) = (ax + b)h + ax(x + 1)h′,

and since h ⪯ (ax + b)h and h ⪯ x(x + 1)h′ we have by the discussion following Lemma 9 that h ⪯ ϕ(f^{(d−1)}). If θ is a common zero of h and ϕ(f^{(d−1)}), then θ(θ + 1)h′(θ) = 0, which is impossible since θ ∈ (−1, 0) and h′(θ) ≠ 0. Thus ϕ(f^{(d)}) ≺ ϕ(f^{(d−1)}), which verifies condition (iii) of Definition 3. Given ξ ∈ ℝ we have

L_{ϕ}(f)(ξ, z) = ∑_{n} \frac{h^{(n)}(ξ)}{n!n!}ξ^{n}(ξ + 1)^{n} \frac{d^{n}f(ξ + z)}{dz^{n}}

= H_{ξ}(\frac{d}{dz})f(ξ + z),

where

H_{ξ}(x) = ∑_{n} \frac{h^{(n)}(ξ)}{n!n!}\{ξ(ξ + 1)x\}^{n}.

By Theorem 11 H_{ξ} is real-rooted, which by Theorem 10 verifies condition (iv).

Suppose that ξ is a common zero of ϕ(f′) and ϕ(f). From the definition of the diamond product it follows that ξ ∉ {0, −1}, so x^{2} ∤ H_{ξ}(x). Since ξ is supposed to be a common zero of ϕ(f′) and ϕ(f) we have, by (1), that 0 is a multiple zero of L_{ϕ}(f)(ξ, z). It follows from Theorem 10 that 0 is a multiple zero of f(z + ξ), that is, ξ is a multiple zero of f, contrary to assumption that f is simple-rooted. This verifies condition (ii), and we can conclude that f ∈ 𝒜^{+}(ϕ). Part (b) of the theorem now follows from Theorem 8.

If h is merely [−1, 0]-rooted and f is real-rooted then we can find polynomials h_{n} and f_{n} whose limits are h and f respectively, such that h_{n} and f_{n} are real- and simple-rooted and h_{n} is (−1, 0)-rooted. Now, f_{n}◇h_{n} is realrooted by the above and, by continuity, so is f◇g. The proof now follows from Theorem 8. □

There are many products on polynomials for which a similar proof applies. With minor changes in the above proof, Theorem 12 also holds for the product

(f, g) → ∑_{n≥0} \frac{f^{(n)}(x)g^{(n)}(x)}{n!}x^{n}(x + 1)^{n}.

3. Interlacing zeros and the Neggers-Stanley Conjecture

Let P be any finite poset of cardinality p. An injective function ω : P → ℕ is called a labelling of P and (P, ω) is a called a labelled poset. A (P, ω)- partition with largest part ≤ n is a map σ : P → [n] such that

• σ is order reversing, that is, if x ≤ y then σ(x) ≥ σ(y),

• if x < y and ω(x) > ω(y) then σ(x) > σ(y). The number of (P, ω)-partitions with largest part ≤ n is denoted Ω(P, ω, n) and is easily seen to be a polynomial in n. Indeed, if we let e_{k}(P, ω) be the number of surjective (P, ω)-partitions σ : P → [k], then by a simple counting argument we have:

Ω(P, ω, x) = ∑_{k=1}^{|P |} e_{k}(P, ω)\binom{x}{k}.  (4)

The polynomial Ω(P, ω, x) is called the order polynomial of (P, ω). The Epolynomial of (P, ω) is the polynomial

E(P, ω) = ∑_{k=1}^{p} e_{k}(P, ω)x^{k},

so E(P, ω) is the image of Ω(P, ω, x) under the invertible linear operator E : ℝ[x] → ℝ[x] which takes \binom{x}{k} to x^{k}. The Neggers-Stanley Conjecture asserts that the polynomial E(P, ω) is real-rooted for all choices of P and ω. The conjecture has been verified for series-parallel posets [13], column-strict labelled Ferrers posets [1] and for all labelled posets having at most seven elements.

There are two operations on labelled posets under which E-polynomials behave well. The first operation is the ordinal sum:

Let (P, ω) and (Q, ν) be two labelled posets. The ordinal sum, P ⊕ Q, of P and Q is the poset with the disjoint union of P and Q as underlying set and with partial order defined by x ≤ y if either x ≤_{P} y, x ≤_{Q} y, or x ∈ P, y ∈ Q. For i = 0, 1 let ω ⊕_{i} ν be any labellings of P ⊕ Q such that

• (ω⊕_{0}ν)(x) < (ω⊕_{0}ν)(y) if ω(x) < ω(y), ν(x) < ν(y) or x ∈ P, y ∈ Q.

• (ω⊕_{1}ν)(x) < (ω⊕_{1}ν)(y) if ω(x) < ω(y), ν(x) < ν(y) or x ∈ Q, y ∈ P. The following result follows easily by combinatorial reasoning: Proposition 13. Let (P, ω) and (Q, ν) be as above. Then

E(P ⊕ Q, ω ⊕_{1} ν) = E(P, ω)E(Q, ν)

and

xE(P ⊕ Q, ω ⊕_{0} ν) = (x + 1)E(P, ω)E(Q, ν),

if P and Q are nonempty.

Proof. See [1, 13]. □

The disjoint union, P ⊔ Q, of P and Q is the poset on the disjoint union with x < y in P ⊔ Q if and only if x <_{P} y or x <_{Q} y. Let ω ⊔ ν be any labelling of P ⊔ Q such that

(ω ⊔ ν)(x) < (ω ⊔ ν)(y),

if ω(x) < ω(y) or ν(x) < ν(y). It is immediate by construction that

Ω(P ⊔ Q, ω ⊔ ν) = Ω(P, ω)Ω(Q, ν)

Here is where the diamond product comes in. Wagner [13] showed that the diamond product satisfies

f◇g = E(E^{−1}(f)E^{−1}(g)),  (5)

which implies:

E(P ⊔ Q, ω ⊔ ν) = E(P, ω)◇E(Q, ν),  (6)

for all pairs of labelled posets (P, ω) and (Q, ν).

If P is nonempty and x ∈ P we let P \ x be the poset on P \ {x} with the order inherited by P. If (P, ω) is labelled then P \ x is labelled with the restriction of ω to P \ x. By a slight abuse of notation we will write (P \ x, ω) for this labelled poset. A series-parallel labelled poset (S, μ) is either the empty poset, a one element poset or

(a) (S, μ) = (P ⊕ Q, ω ⊕_{0} ν),

(b) (S, μ) = (P ⊕ Q, ω ⊕_{1} ν) or

(c) (S, μ) = (P ⊔ Q, ω ⊔ ν) where (P, ω) and (Q, ν) are series-parallel. Note that if (S, μ) is series-parallel then so is (S \ x, μ) for all x ∈ S. Let ℐ denote the set of all finite labelled posets (S, μ) such that E(S, μ) is real-rooted and

E(S \ x, μ) ⪯ E(S, μ),

for all x ∈ S. Note that the empty poset and the singleton posets are members of ℐ which by the following theorem gives that series-parallel posets are in ℐ. Theorem 14. The set ℐ is closed under ordinal sum and disjoint union.

Proof. Suppose that (P, ω), (Q, ν) ∈ ℐ. (a): Let (S, μ) = (P ⊕ Q, ω ⊕_{0} ν). Now, if y ∈ P we have

(S \ y, μ) = (P \ y ⊕ Q, ω ⊕_{0} ν).

If |P | = 1 then by Proposition 13 we have E(S \ y, μ) = E(Q, ν) and E(S, μ) = (x + 1)E(Q, ν) so E(S \ y, μ) ⪯ E(S, μ). If |P | > 1 then

xE(S \ y, μ) = (x + 1)E(P \ y, ω)E(Q, ν)
⪯ (x + 1)E(P, ω)E(Q, ν)
= xE(S, μ),

which gives E(S \ y, μ) ⪯ E(S, μ). A similar argument applies to the case y ∈ Q.

Figure 1. From left to right: A column-strict labelling ω of P_{λ} with λ = (3, 2, 2, 1), a (P_{λ}, ω)-partition and the corresponding reverse SSYT.

8 7 6 5 4 3 2 1  9 10 9 7 10 8 7 2  10 10 9 8 9 7 7 2

(b): The case (S, μ) = (P ⊕ Q, ω ⊕_{0} ν) follows as in (a). (c): (S, μ) = (P ⊔ Q, ω ⊔ ν). If y ∈ P we have by (6) and Theorem 12:

E(S \ y, μ) = E(P \ y ⊔ Q, ω ⊔ ν)
= E(P \ y, ω)◇E(Q, ν)
⪯ E(P, ω)◇E(Q, ν)
= E(S, μ).

This proves the theorem. □

In [11] Simion proved a special case of the following corollary. Namely the case when S is a disjoint union of chains and μ is order-preserving. Corollary 15. If (S, μ) is series-parallel and x ∈ S then

E(S \ x, μ) ⪯ E(S, μ).

Next we will analyse interlacings of E-polynomials of Ferrers posets. For undefined terminology in what follows we refer the reader to [12, Chapter 7]. Let λ = (λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{ℓ} > 0) be a partition. The Ferrers poset P_{λ} is the poset

P_{λ} = {(i, j) ∈ ℙ × ℙ : 1 ≤ i ≤ ℓ, 1 ≤ j ≤ λ_{i}},

ordered by the standard product ordering. A labelling ω of P_{λ} is column strict if ω(i, j) > ω(i + 1, j) and ω(i, j) < ω(i, j + 1) for all (i, j) ∈ P_{λ}. If ω is a column strict labelling then any (P_{λ}, ω)-partition must necessarily be strictly decreasing in the x-direction and weakly decreasing in the y-direction. It follows that the (P_{λ}, ω)-partitions are in a one-to-one correspondence with with the reverse SSYT’s of shape λ (see Figure 1). The number of reverse SSYT’s of shape λ with largest part ≤ n is by the combinatorial definition of the Schur function equal to s_{λ}(1^{n}) which by the hook-content formula [12, Corollary 7.21.4] gives us.

Ω(P_{λ}, ω, z) = ∏_{u∈P_{λ}} \frac{z + c_{λ}(u)}{h_{λ}(u)},  (7)

where for u = (x, y) ∈ P_{λ}

h_{λ}(u) := |{(x, j) ∈ λ : j ≥ y}| + |{(i, y) ∈ λ : i ≥ x}| − 1

and c_{λ}(u) := y −x are the hook length respectively content at u. In [1] Brenti showed that the E-polynomials of column strict labelled Ferrers posets are real-rooted. In the next theorem we refine this result. If x < y in a poset P and x < z < y for no z ∈ P we say that y covers x. If we remove an element from P_{λ} the resulting poset will not necessarily be a Ferrers poset. But if we remove a maximal element m from P_{λ} we will have P_{λ} \ m = P_{μ} for a partition μ covered by λ in the Young’s lattice. Theorem 16. Let (P_{λ}, ω) be labelled column strict. Then E(P_{λ}, ω) is realrooted. Moreover, if λ covers μ in the Young’s lattice, then

E(P_{μ}, ω) ⪯ E(P_{λ}, ω).

Proof. The proof is by induction over n, where λ ⊢ n. It is trivially true for n = 1. If λ ⊢ n + 1 and λ covers μ we have that P_{λ} = P_{μ} ∪ {m} for some maximal element m ∈ P_{λ}. By definition c_{μ}(u) = c_{λ}(u) for all u ∈ P_{μ}, so by (7) we have that for some C > 0:

Ω(P_{λ}, ω, x) = C(x + c_{λ}(m))Ω(P_{μ}, ω, x),

and by (5):

E(P_{λ}, ω) = C(x + c_{λ}(m))◇E(P_{μ}, ω).

Wagner [13] showed that all real zeros of E-polynomials are necessarily in [−1, 0], so by induction we have that E(P_{μ}, ω) is [−1, 0]-rooted. By Theorem 12 this suffices to prove the theorem. □

References

[1] Francesco Brenti. Unimodal, log-concave and Pólya frequency sequences in combinatorics. Mem. Amer. Math. Soc., 81(413):viii+106, 1989.

[2] Jean-Pierre Dedieu. Obreschkoff’s theorem revisited: what convex sets are contained in the set of hyperbolic polynomials? J. Pure Appl. Algebra, 81(3):269–278, 1992.

[3] C. D. Godsil. Algebraic combinatorics. Chapman and Hall Mathematics Series. Chapman & Hall, New York, 1993.

[4] Ole J. Heilmann and Elliott H. Lieb. Theory of monomer-dimer systems. Comm. Math. Phys., 25:190–232, 1972.

[5] B. Ja. Levin. Distribution of zeros of entire functions. American Mathematical Society, Providence, R.I., 1964.

[6] Morris Marden. Geometry of polynomials. Second edition. Mathematical Surveys, No. 3. American Mathematical Society, Providence, R.I., 1966.

[7] Albert Nijenhuis. On permanents and the zeros of rook polynomials. J. Combinatorial Theory Ser. A, 21(2):240–244, 1976.

[8] Nikola Obreschkoff. Verteilung und Berechnung der Nullstellen reeller Polynome. VEB Deutscher Verlag der Wissenschaften, Berlin, 1963.

[9] V. Reiner and V. Welker. On the Charney-Davis and the Neggers-Stanley conjectures. http://www.math.umn.edu/ reiner/Papers/papers.html, 2002.

[10] J. Schur. Zwei sätze über algebraische gleichungen mit lauter reellen wurzeln. J. Reine Angew. Math., 144(2):75–88, 1914.

[11] Rodica Simion. A multi-indexed Sturm sequence of polynomials and unimodality of certain combinatorial sequences. J. Combin. Theory Ser. A, 36(1):15–22, 1984.

[12] Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

[13] David G. Wagner. Enumeration of functions from posets to chains. European J. Combin., 13(4):313–324, 1992.

[14] David G. Wagner. Total positivity of Hadamard products. J. Math. Anal. Appl., 163(2):459–483, 1992.

Matematik, Chalmers tekniska högskola och Göteborgs universitet, S-412 96 Göteborg, Sweden

   E-mail address: branden@math.chalmers.se

THE GENERATING FUNCTION OF 2-STACK SORTABLE PERMUTATIONS BY DESCENTS IS REAL-ROOTED

PETTER BRÄNDÉN

Abstract. Bóna has conjectured that, for fixed n ≥ 0 and t ≥ 1, the generating function of t-stack sortable permutations by descents is realrooted. The conjecture is known to be true for t = 1 and t = n − 1. Here we prove it for t = 2.

1. Introduction

Let W_{t}(n, k) be the number of t-stack sortable permutations in the symmetric group, S_{n}, with k descents. Recently Bóna [1] showed that for fixed n and t the numbers W_{t}(n, k) form a log-concave sequence, that is,

W_{t}(n, k)^{2} ≥ W_{t}(n, k − 1)W_{t}(n, k + 1),

for 1 ≤ k ≤ n − 2. Let W_{n,t}(x) = ∑_{k=0}^{n−1} W_{t}(n, k)x^{k}. A sufficient condition on a sequence to be log-concave is that the corresponding polynomial is realrooted. When t = n − 1 and t = 1 we get the Eulerian and the Narayana polynomials respectively. These are known to be real-rooted and Bóna conjectures that the same is true for general t. In what follows we will prove the conjecture for t = 2.

Let W be the set of finite words on ℕ without repetitions. If w is any nonempty word we may write it as the concatenation w = LnR where n is the greatest letter of w and L and R are the subwords to the left and right of n respectively. The stack-sorting operation s : W → W may be defined recursively by

s(w) = \begin{cases}w, if w is the empty word, \\ s(L)s(R)n, if w = LnR is nonempty. \end{cases}

The stack sortable permutations in S_{n} are the permutations which are mapped by s to the identity permutation. Similarly, a permutation is called t-stack sortable if s^{t}(π) is the identity permutation.

Date: 4th March 2003.

2. Stack sortable permutations and Jacobi polynomials

The number of stack sortable permutations of length n with k descents are known [9] to be the famous Narayana numbers [10, 11]

W_{1}(n, k) = \frac{1}{n}\binom{n}{k}\binom{n}{k + 1}.

The Narayana polynomials W_{n,1}(x) are known to have real zeros. A simple proof of this fact is obtained by expressing W_{n,1}(x) in terms of Jacobi polynomials. Recall the definition of the hypergeometric function _{2}F_{1}:

2F_{1} (a, b; c; z) = ∑_{n=0}^{∞} \frac{(a)_{n}(b)_{n}z^{n}}{(c)_{n}n!} ,

where (α)_{0} = 1 and (α)_{n} = α(α + 1) ⋯ (α + n − 1) when n ≥ 1. The Jacobi polynomial P_{n}^{(α,β)}(x) can be expressed in the following two ways [8, Page 254]:

P_{n}^{(α,β)}(x) = \frac{(1 + α)_{n}}{n!}_{2}F_{1} (−n, 1 + α + β + n; 1 + α; \frac{1 − x}{2}) , (1)

P_{n}^{(α,β)}(x) = \frac{(1 + α)_{n}}{n!} (\frac{x + 1}{2})^{n} _{2}F_{1} (−n, −β − n; 1 + α; \frac{x − 1}{x + 1}) . (2)

Rewriting W_{1}(n + 1, k) we end up with

W_{n+1,1}(x) = _{2}F_{1} (−n, −n − 1; 2; x) ,

which by (2) gives

W_{n+1,1}(x) = \frac{1}{n + 1}(1 − y)^{n}P_{n}^{(1,1)} (\frac{1 + y}{1 − y} ) .

Since the Jacobi polynomials are orthogonal when α, β > −1 we know that W_{n,1}(x) is real- and simple-rooted and that the zeros of W_{n,1}(x) strictly interlace the zeros of W_{n+1,1}(x), that is, {W_{n+1,1}(x)}_{n=0}^{∞} form a Sturm sequence.

The numbers W_{2}(n, k) are surprisingly hard to determine despite of their compact and simple form. It was recently shown that

W_{2}(n, k) = \frac{(n + k)!(2n − k − 1)!}{(k + 1)!(n − k)!(2k + 1)!(2n − 2k − 1)!}.

See [2, 5, 6, 7] for proofs and more information on 2-stack sortable permutations.

A sequence of real numbers Γ = {γ_{k}}_{k=0}^{n} is called an n-sequence (of the first kind) if for any real-rooted polynomial f = a_{0}+a_{1}x+⋯+a_{n}x^{n} of degree at most n the polynomial Γ(f) := a_{0}γ_{0} + a_{1}γ_{1} + ⋯ + a_{n}γ_{n}x^{n} is real-rooted. There is a simple algebraic characterisation of n-sequences [4]:

Theorem 1. Let Γ = {γ_{k}}_{k=0}^{n} be a sequence of real numbers. Then Γ is an n-sequence of the first kind if and only if Γ[(x + 1)^{n}] is real-rooted with all its zeros of the same sign.

We need the following lemma: Lemma 2. Let n be a positive integer and r a non-negative real number. Then Γ = \{\binom{−n−r}{k}\}_{k=0}^{n} is an n-sequence.

Proof. Let r > 0. Then

Γ[(x + 1)^{n}] = ∑_{k=0}^{n} \binom{−n − r}{k}\binom{n}{k}x^{k}
= _{2}F_{1} (−n, n + r; 1; x)
= P_{n}^{(0,r−1)}(1 − 2x),

where the last equality follows from (1). Since the Jacobi polynomials are known to have all their zeros in [−1, 1] when α, β > −1 we have that Γ[(x + 1)^{n}] has all its zeros in [0, 1]. The case r = 0 follows by continuity when we let r tend to zero from above. □

From the case r = 0 in Lemma 2 and the identity

∑_{k=0}^{n} \binom{2n − k − 1}{n − 1}\binom{n}{k}x^{k} = (−1)^{n} ∑_{k=0}^{n} \binom{−n}{k}\binom{n}{k}(−x)^{n−k},

it follows that \binom{2n−k−1}{n−1} is an n-sequence.

Theorem 3. For all n ≥ 0 the polynomial W_{2,n}(x), which records 2-stack sortable permutations by descents, is real-rooted.

Proof. We may write W_{2}(n, k) as

W_{2}(n, k) = \frac{\binom{2n−k−1}{n−1}\binom{n+k}{n−1}\binom{2n}{2k+1}}{n^{2}\binom{2n}{n}}.

A well known result on real-rooted polynomials reads as follows: If ∑_{i} a_{i}x^{i} is a polynomial having only real non-positive zeros then so is the polynomial ∑_{i} a_{ki}x^{i}, where k is any positive integer. For a proof see [3, Theorem 3.5.4]. Applying this result to the polynomial x(1 + x)^{2n} we see that ∑_{k} \binom{2n}{2k+1}x^{k} is real-rooted. Now,

∑_{k=0}^{n−1} \binom{n + k}{n − 1}\binom{2n}{2k + 1}x^{k} = ∑_{k=0}^{n−1} \binom{2n − k − 1}{n − 1}\binom{2n}{2k + 1}x^{n−1−k},

which by the discussion after Lemma 2 is real-rooted. Another application of Lemma 2 gives that W_{n,2}(x) is real-rooted. □

References

[1] Miklós Bóna. Log-concavity for t-stack sortable permutations. Submitted, http://www.math.ufl.edu/ bona/, 2002.

[2] Mireille Bousquet-Mélou. Multi-statistic enumeration of two-stack sortable permutations. Electron. J. Combin., 5(1):Research Paper 21, 12 pp. (electronic), 1998.

[3] Francesco Brenti. Unimodal, log-concave and Pólya frequency sequences in combinatorics. Mem. Amer. Math. Soc., 81(413):viii+106, 1989.

[4] Thomas Craven and George Csordas. Multiplier sequences for fields. Illinois J. Math., 21(4):801–817, 1977.

[5] S. Dulucq, S. Gire, and O. Guibert. A combinatorial proof of J. West’s conjecture. Discrete Math., 187(1-3):71–96, 1998.

[6] I. P. Goulden and J. West. Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations. J. Combin. Theory Ser. A, 75(2):220–242, 1996.

[7] Benjamin Jacquard and Gilles Schaeffer. A bijective census of nonseparable planar maps. J. Combin. Theory Ser. A, 83(1):1–20, 1998.

[8] Earl D. Rainville. Special functions. The Macmillan Co., New York, 1960.

[9] Rodica Simion. Combinatorial statistics on noncrossing partitions. J. Combin. Theory Ser. A, 66(2):270–301, 1994.

[10] Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

[11] Robert A. Sulanke. The Narayana distribution. J. Statist. Plann. Inference, 101(1-2):311–326, 2002. Special issue on lattice path combinatorics and applications (Vienna, 1998).

Matematik, Chalmers tekniska högskola och Göteborgs universitet, S-412 96 Göteborg, Sweden

E-mail address: branden@math.chalmers.se

q-NARAYANA NUMBERS AND THE FLAG h-VECTOR OF J(2 × n)

PETTER BRÄNDÉN

Abstract. The Narayana numbers are N(n, k) = \frac{1}{n} \binom{n}{k}\binom{n}{k+1}. There are several natural statistics on Dyck paths with a distribution given by N(n, k). We show the equidistribution of Narayana statistics by computing the flag h-vector of J(2×n) in different ways. In the process we discover new Narayana statistics and provide co-statistics for which the Narayana statistics in question have a distribution given by Fürlinger and Hofbauer’s q-Narayana numbers. We interpret the flag h-vector in terms of semi-standard Young tableaux, which enables us to express the q-Narayana numbers in terms of Schur functions. We also introduce what we call pre-shellings of simplicial complexes.

1. Introduction

One of the most common refinements of the famous Catalan numbers, \frac{1}{n+1} \binom{2n}{n}, [11, Exercise 6.19] is given by the Narayana numbers,

N(n, k) = \frac{1}{n}\binom{n}{k}\binom{n}{k + 1}.

They appear in many combinatorial problems. Some examples are the number of noncrossing partitions of {1, 2, …, n} of rank k [4], the number of stack sortable permutations with k descents [9], and also several problems involving Dyck paths.

A Dyck path of length 2n is a path in ℕ × ℕ from (0, 0) to (n, n) using steps v = (0, 1) and h = (1, 0), which never goes below the line x = y. The set of all Dyck paths of length 2n is denoted 𝒟_{n}. A statistic on 𝒟_{n} having a distribution given by the Narayana numbers will be referred to as a Narayana statistic. The first Narayana statistics to be discovered were des(w): the number of descents (valleys) (sequences hv) in w, Narayana [8], ea(w): the number of even ascents, i.e., the number of letters v in an even

position in w, Kreweras [6], lnfs(w): the number of long non-final sequences, more precisely the number

of sequences vvh and hhv in w, Kreweras and Moszkowski [5].

Date: 4th March 2003.

Key words and phrases. Narayana numbers, flag h-vector, Schur Function, shelling.

Recently, [2], Deutsch discovered a new Narayana statistic, hp, and it counts the number of high peaks, i.e., peaks that have vertices strictly above the line y = x + 1. Also, in [12, 13] Sulanke found numerous new Narayana statistics with the help of a computer. See [14] for more information on Narayana numbers. For terminology on posets in what follows, we refer the reader to [10].

Our main objective is to show that the statistics des, hp and lnfs arise naturally when studying different shellings of Δ(J(2×n)), the order complex of the lattice of order ideals of the poset 2 × n. More precisely, we show that they can be computed as invariants of certain shellings. From this follows not only that the statistics all have the same distribution, but that the results can be extended to set-valued statistics. In the process we will also find a new family of Narayana statistics. Since our methods are not restricted to Dyck paths, we will consider a more general setting.

In Section 2 we review some theory on shellings of simplicial complexes and order complexes and define what we call a pre-shelling of a complex. In Section 3 we give different pre-shellings of order complexes of certain plain distributive lattices, and finally in Section 4 we apply our results to Dyck paths. There is a q-analog of the Narayana numbers,

N_{q}(n, k) = \frac{1}{[n]}\left[{n \atop k}\right]\left[{n \atop k + 1}\right]q^{k^{2}+k},  (1)

introduced by Fürlinger and Hofbauer in [3]. Here [n] and \left[{n \atop k}\right] are the usual q-analogs. To each statistic we treat we associate a co-statistic together with which the Narayana statistic has a joint distribution given by the q-Narayana numbers.

2. Pre-shellings of Simplicial complexes

An (abstract) simplicial complex Δ on a vertex set V is a collection of subsets F of V satisfying:

(i) if x ∈ V then {x} ∈ Δ, (ii) if F ∈ Δ and G ⊆ F, then G ∈ Δ.

The elements of Δ are called faces and a maximal face (with respect to inclusion) is called a facet. A simplicial complex is said to be pure if all its facets have the same cardinality. A total order Ω on the set of facets of a pure simplicial complex Δ is a shelling if whenever F <^{Ω} G there is an x ∈ G and E <^{Ω} G such that

F ∩ G ⊆ E ∩ G = G \ {x}.

q-NARAYANA NUMBERS 19

A simplicial complex which allows a shelling is said to be shellable. Instead of finding a particular shellings we will find partial orders on the set of facets with the property that every linear extension is a shelling. In our attempts to prove that our partial orders had this property we found ourselves proving Theorem 1 and Corollary 2. We therefore take the opportunity to take a general approach and define what we call a pre-shelling. Though we have found examples of pre-shellings implicit in the literature we have not found explicit references, so we provide proofs.

Let Ω be a partial order on the set of facets of a pure simplicial complex Δ. The restriction, r_{Ω}(F), of a facet F is the set

r_{Ω}(F) = {x ∈ F : ∃E s.t E <^{Ω} F and E ∩ F = F \ {x} }.

We say that Ω is a pre-shelling if any of the equivalent conditions in Theorem 1 are satisfied. Theorem 1. Let Ω be a partial order on the set of facets of a pure simplicial complex Δ. Then the following conditions on Ω are equivalent:

(i) For all facets F, G we have

r_{Ω}(F) ⊆ G and r_{Ω}(G) ⊆ F ⟹ F = G.

(ii) Δ is the disjoint union

Δ = ⋃_{F} · [r_{Ω}(F), F].

(iii) For all facets F, G

r_{Ω}(F) ⊆ G ⇒ F ≤^{Ω} G.

(iv) For all facets F and G: if F ≱^{Ω} G then there is an x ∈ G and E <^{Ω} G such that

F ∩ G ⊆ E ∩ G = G \ {x}.

Proof. (i) ⇒ (ii): Let F and G be facets of Δ. If there is an H ∈ [r_{Ω}(F), F]∩ [r_{Ω}(G), G] then r_{Ω}(F) ⊆ G and r_{Ω}(G) ⊆ F, so by (i) we have F = G. Hence the union is disjoint. Suppose that H ∈ Δ, and let F_{0} be a minimal element, with respect to Ω, of the set

{F : F is a facet and H ⊆ F }.

If r_{Ω}(F_{0}) ⊈ H then let x ∈ r_{Ω}(F_{0}) \ H and let E <^{Ω} F_{0} be such that F_{0} ∩ E = F_{0} \ {x}. Then H ⊆ E, contradicting the minimality of F_{0}. Therefore H ∈ [r(F_{0}), F_{0}].

(ii) ⇒ (i): If r_{Ω}(F) ⊆ G and r_{Ω}(G) ⊆ F we have that F ∩G ∈ [r_{Ω}(F), F]∩ [r_{Ω}(G), G], which by (ii) gives us F = G.

(i) ⇒ (iii): If r_{Ω}(F) ⊆ G then by (i) we have either F = G or r_{Ω}(G) ⊈ F. If F = G we have nothing to prove, so we may assume that there is an x ∈ r_{Ω}(G) \ F. Then, by assumption, there is a facet E_{1} <^{Ω} G such that

r_{Ω}(F) ⊆ G ∩ E_{1} = G \ {x} ⊂ E_{1}.

If E_{1} = F we are done. Otherwise we continue until we get

F = E_{k} <^{Ω} E_{k−1} <^{Ω} ⋯ <^{Ω} E_{1} <^{Ω} G,

and we are done.

(iii) ⇔ (iv): It is easy to see that (iv) is just the contrapositive of (iii) (iii) ⇒ (i): Immediate. □

The set of all partial orders on the same set is partially ordered by inclusion, i.e Ω ⊆ Λ if x <^{Ω} y implies x <^{Λ} y. Corollary 2. Let Δ be a pure simplicial complex. Then

(i) every shelling of Δ is a pre-shelling, (ii) if Ω is a pre-shelling of Δ and Λ is a partial order such that Ω ⊆ Λ,

then Λ is a pre-shelling of Δ with r_{Λ}(F) = r_{Ω}(F) for all facets F. In fact, the set of pre-shellings of Δ is a principal upper ideal of the poset of all partial orders on the set of facets of Δ,

(iii) every linear extension of a pre-shelling is a shelling, with the same restriction function.

Proof. (i): Follows immediately from Theorem 1(iv).

(ii): That Λ is a pre-shelling follows from Theorem 1(iv). If F is a facet then by definition r_{Ω}(F) ⊆ r_{Λ}(F), and if r_{Ω}(F) ⊂ r_{Λ}(F) for some facet F we would have a contradiction by Theorem 1(ii). It remains to show that there is a unique minimal order with r_{Ω} as a pre-shelling. Define a partial order Υ as the transitive closure of the relation R defined by: F RG if

F <^{Ω} G and |F ∩ G| = |F | − 1.  (2)

It follows that Υ is a partial order with r_{Ω} as restriction function, so Υ is a pre-shelling by Theorem 1(i) . Since (2) only depends on r_{Ω}, and Υ ⊆ Ω we are done.

(iii): Is implied by (ii). □

There are interesting examples of the unique minimal pre-shelling afforded by Corollary 2: Example 3. Let Δ be the barycentric subdivision of a simplex of dimension n − 1. Then there is a standard way of identifying the facets of Δ with the permutations in the symmetric group S_{n}. The lexicographic order <_{L} on S_{n} is then a shelling of Δ, and it follows that the unique minimal pre-shelling with the same restriction function as <_{L} is the weak Bruhat order on S_{n}.

See also Example 6 for another example of a minimal pre-shelling.

In Section 4 we will need some facts about flag h-vectors of order complexes which we state here for reference. Let P be any finite graded poset with a smallest element ˆ0 and a greatest element ˆ1 and let ρ be the rank function of P with ρ(ˆ1) = n. For S ⊆ [n − 1] let

α_{P} (S) := |{c is a chain of P : ρ(c) = S}|,

and

β_{P} (S) := ∑_{T ⊆S}(−1)^{|S−T |}α_{P} (T).

The functions α_{P} , β_{P} : 2^{[n−1]} → ℤ are called the flag f-vector and the flag h-vector of P respectively. The order complex, Δ(P), of P is the simplicial complex of all chains of P. A simplicial complex Δ is partitionable if it can be written as

Δ = [r(F_{1}), F_{1}]∪· [r(F_{2}), F_{2}]∪⋯ ∪· [r(F_{n}), F_{n}],  (3)

where each F_{i} is a facet of Δ and r is any function on the set of facets such that r(F) ⊆ F for all facets F. The right hand side of (3) is a partitioning of Δ. By Theorem 1(iii) we see that shellable complexes are partitionable. We need the following well known fact about partitionable order complexes. Let ℳ (P) be the set of maximal chains of P. Lemma 4. Let Δ(P) be partitionable and let

Δ(P) = ⋃_{c} · [r(c), c]  (4)

be a partitioning of Δ(P). Then the flag h-vector is given by

β_{P} (S) = |{c ∈ ℳ (P) : ρ(r(c)) = S}|.

Proof. Let γ_{P} (S) = |{c ∈ ℳ (P) : ρ(r(c)) = S}|. Note that if c is a maximal chain then ρ(c) = [0, ρ(ˆ1)]. By (4) we have

α_{P} (S) = |{c ∈ Δ(P) : ρ(c) = S}|
= |{c ∈ ℳ (P) : ρ(r(c)) ⊆ S}|
= ∑_{T ⊆S} γ_{P} (T),

which, by inclusion-exclusion, gives γ_{P} (S) = β_{P} (S). □

3. Some pre-shellings of plane distributive lattices

We will here study different pre-shellings of certain distributive lattices. Let V, W be lattice paths in ℤ^{2} using steps v = (0, 1) and h = (1, 0) with the same starting- and end-point, ˆ0 = (0, 0) and ˆ1 respectively. Let R = R(V, W) be the closed region in ℝ^{2} bounded by V and W, and let L = L(V, W) = R(V, W) ∩ ℤ^{2}, ordered by the product ordering. It is not hard to see that L is a distributive lattice. The maximal chains in L are the lattice paths from ˆ0 to ˆ1 which stay inside R, and we denote them by ℳ = ℳ (V, W). The set of Dyck paths, 𝒟_{n}, is thus ℳ (V, W) where V = vhvh ⋯ vh and W = vv ⋯ vhh ⋯ h are of length 2n. Fix a path W_{0} ∈ ℳ. We say that a point x = u_{1} + u_{2} + ⋯ + u_{i} in a lattice path u = u_{1}u_{2} ⋯ u_{n} is facing W_{0} if (see Figure 1)

• u_{i}u_{i+1} = vh and x is strictly north-west of W_{0} or

• u_{i}u_{i+1} = hv and x is strictly south-east of W_{0}.

Figure 1. The vertices of the dotted path facing the undotted path are displayed as stars

• • • • • • • • ⋆ ⋆ • • • • ⋆ ⋆ • • • • • •  • ⋆ •  • • • • • • • ⋆

Define a function r_{W_{0}} : ℳ → L by

r_{W_{0}}(u) = {x ∈ u : x is facing W_{0}}.

For any W_{0} ∈ ℳ we may now define a partial order on ℳ (the facets of Δ(L(V, W))) by

u ≤_{W_{0}} w iff R(u, W_{0}) ⊆ R(w, W_{0}),

so that r_{W_{0}} is the restriction function of ≤_{W_{0}}. Theorem 5. For all W_{0} ∈ L(V, W), the partial order ≤_{W_{0}} is a pre-shelling of Δ(L(V, W)).

Proof. If x ∈ L let R(x) be the region enclosed by W_{0} and the horizontal and vertical lines emanating from x. If u ∈ ℳ contains r_{W_{0}}(w) then R(u, W_{0}) contains the union of all R(x), x ∈ r_{W_{0}}(w). But this union is R(w, W_{0}). This verifies condition (iii) of Theorem 1. □

Note that ≤_{W_{0}} is the smallest pre-shelling with r_{W_{0}} as restriction function. Example 6. Let V = W_{0} = udud ⋯ ud and W = uu ⋯ udd ⋯ d be of length 2n in Theorem 5. Then ≤_{W_{0}} is a distributive lattice with rank function, ρ(w), given by the area of R(w, W_{0}). Moreover, it the unique smallest partial order with r_{W_{0}} as restriction function. The rank generating function of this lattice is thus the well known Carlitz-Riordan q-analog of the Catalan numbers, C_{n}(q), satisfying

C_{n+1}(q) = ∑_{k=0}^{n} q^{k}C_{k}(q)C_{n−k}(q).

See [1, 3].

We will now study a pre-shelling linked with long non-final sequences. For j ≥ 1 let t_{j} be the mapping on lattice paths which transposes the letters in positions j and j + 1. An element x = u_{1} + u_{2} + ⋯ + u_{i} ∈ L is a long Figure 2. The partial order Ω on 𝒟_{4}, with long non-final sequences marked with bars.

[figure: vvv̄hhh̄vh; vvvv̄hhhh; vvv̄hh̄vhh; vv̄hh̄vv̄hh; vvv̄hvhhh; vv̄hh̄vhvh; vv̄hvv̄hhh; vv̄hvhh̄vh; vhvvv̄hhh; vv̄hvhvhh; vhvv̄hh̄vh; vhvv̄hvhh; vhvhvv̄hh; vhvhvhvh]

non-final vertex of u = u_{1}u_{2} ⋯ u_{n} if u_{i−1}u_{i}u_{i+1} = vvh or u_{i−1}u_{i}u_{i+1} = hhv. We say that x is an inner long non-final vertex, ILNFV, of u if x is a long non-final vertex and t_{i}(u) ∈ ℳ.

Let S = {s_{1}, s_{2}, …, s_{n−2}} denote the set of mappings

s_{i}(u) = \begin{cases}t_{i}(u) & if x = u_{1} + ⋯ + u_{i} is an ILNFV \\ u & otherwise. \end{cases}

Thus the elements in S flip valleys into peaks, and vice versa, in long non-final sequences provided that the resulting path is still in ℳ. Define a relation Ω, by u <^{Ω} w whenever u ≠ w and u = σ_{1}σ_{2} ⋯ σ_{k}(w) for some mappings σ_{i} ∈ S (see Figure 2).

Lemma 7. The relation Ω on ℳ (V, W) is a partial order.

Proof. We need to prove that Ω is anti-symmetric. To do this we define a mapping σ : ℳ → ℕ × ℕ, where ℕ × ℕ is ordered lexicographically, with the property

u <^{Ω} w ⇒ σ(u) < σ(w).

Define σ(w) = (da(w), MAJ(w)), where da(w) is the number of double ascents (sequences vv) in w. Now, suppose that s_{i} ∈ S and s_{i}(w) ≠ w = a_{1}a_{2} ⋯ a_{2n}. Then da(s_{i}(w)) ≤ da(w), and if we have equality we must have a_{i−1}a_{i}a_{i+1}a_{i+2} = vvhv or a_{i−1}a_{i}a_{i+1}a_{i+2} = hhvh which implies MAJ(s_{i}(w)) < MAJ(w), so σ has the desired properties. □

Figure 3. Illustration of the proof of Theorem 8.

•  • •_{a_{k−1}}•_{a_{k}}_{b_{k}} • … _{a_{ℓ}} •_{a_{ℓ+1}}

If u, w ∈ ℳ intersect maximally i.e., |u ∩ w| = |u| − 1 we have either s(u) = w or s(w) = u for some s ∈ S, so the restriction r_{Ω}(u) is the set of inner long non-final vertices of u. Theorem 8. Suppose that V and W have the same initial step. Then Ω is a pre-shelling of Δ(L(V, W)).

Proof. We prove that Ω satisfies the contrapositive of condition (i) of Theorem 1. Suppose that u = a_{1}a_{2} ⋯ a_{n} ≠ w = b_{1}b_{2} ⋯ b_{n} and let k be the coordinate such that a_{i} = b_{i} for i < k and a_{k} ≠ b_{k}. By symmetry we may assume that a_{k} = h. Now, if a_{k−1} = h then the valley of u which is determined by the first v (at, say, coordinate ℓ + 1) after k will correspond to an element

x = a_{1} + ⋯ + a_{ℓ} ∈ r_{Ω}(u) \ w

(see Figure 3).

If a_{k−1} = v = b_{k−1}, then if ℓ + 1 is the coordinate for the first h after k we have that

x = b_{1} + ⋯ + b_{ℓ} ∈ r_{Ω}(w) \ u,

so Ω is a pre-shelling. □

4. The restriction to Dyck paths

When V = vhvh ⋯ vh and W = vv ⋯ vhh ⋯ h are of length 2n we have that L(V, W) = J(2 × n), the set of order ideals of 2 × n. See Example 3.5.5 in [10]. Moreover, ℳ (V, W) = 𝒟_{n}, the set of Dyck paths of length 2n. The descent set D(w), the set of high peaks HP (w) and the set of long non-final sequences LS(w) are defined as

D(w) = {i ∈ [2n − 1] : w_{i}w_{i+1} is a descent},
HP (w) = {i ∈ [2n − 1] : w_{i}w_{i+1} is a high peak},
LS(w) = {i ∈ [2n − 1] : w_{i−1}w_{i}w_{i+1} is a long non-final sequence},

where w = w_{1}w_{2} ⋯ w_{2n}. For each W_{0} ∈ 𝒟_{n} we also define

D_{W_{0}}(w) = {i ∈ [2n − 1] : w_{0} + w_{1} + ⋯ + w_{i} is facing W_{0}}.

Figure 4. An example of a SSYT of shape (6, 5, 4, 4, 2).

1 2 2 3 5 5
2 3 4 4 6
4 5 5 6
5 6 6 8
7 8  .

Theorem 9. The set functions D, HP, LS and D_{W_{0}} have the same distribution and it is given by

|{w ∈ 𝒟_{n} : D(w) = S}| = β_{J(2×n)}(S).

Proof. We have that D = D_{W_{0}} where W_{0} = uuu ⋯ ddd and HP = D_{W_{0}} where W_{0} = udud ⋯ ud. Since all long non final vertices are inner the theorem follows from Lemma 4. □

In particular, for every choice of W_{0} ∈ 𝒟_{n}, we get a Narayana statistic, namely the number of vertices facing W_{0}.

We will now take a closer look at the flag h-vector of J(2 × n) which we hereafter will denote by β_{n}. The function β_{n} can be described nicely in terms of partitions. Let λ = (λ_{1}, λ_{2}, …, λ_{ℓ}) be a partition of a nonnegative integer. The index ℓ is called the length, ℓ(λ), of λ. A semistandard Young tableau (SSYT) of shape λ is an array T = (T_{ij}) of positive integers, where 1 ≤ i ≤ ℓ(λ) and 1 ≤ j ≤ λ_{i}, that is weakly increasing in every row and strictly increasing in every column, see Figure 4. For any SSYT of shape λ let

x^{T} := x_{1}^{α_{1}(T)}x_{2}^{α_{2}(T)} ⋯,

where α_{i}(T) denotes the number of entries of T that are equal to i. The Schur function s_{λ}(x) of shape λ is the formal power series

s_{λ}(x) = ∑_{T} x^{T} ,

where the sum is over all SSYTs T of shape λ. If T is any SSYT we let row(T) = (γ_{1}(T), γ_{2}(T), …) where γ_{i}(T) = ∑_{j} T_{ij}. Let ⟨2^{k}⟩ be the partition (2, 2, …, 2) with k 2’s. Theorem 10. For any n > 0 and S ⊆ [2n − 1], |S| = k, we have that β_{n}(S) counts the number of SSYTs T of shape ⟨2^{k}⟩ with row(T) = S and with parts less than n.

Proof. Let T be a SSYT as in the statement of the theorem. We want to construct a Dyck path w(T) with descent set S.

Let w(T) = w_{1}w′_{1}w_{2}w′_{2} ⋯ w_{k+1}w′_{k+1} where Figure 5. An illustration of Theorem 10 for n = 7.

1 2 3 5 5 6 → • • • • • • • • • • • • • • •

• w_{1} is the word consisting of T_{12} vertical steps and w′_{1} is the word consisting of T_{11} horizontal steps,

• w_{i} is the word consisting of T_{i2} − T_{(i−1)2} vertical steps and w′_{i} is the word consisting of T_{i1} − T_{(i−1)1} horizontal steps, when 2 ≤ i ≤ k,

• w_{k+1} is the word consisting of n − T_{k2} vertical steps and w′_{k+1} is the

word consisting of n − T_{k1} horizontal steps. It is clear that w(T) is indeed a Dyck path with descent set S, and each such Dyck path is given by w(T) for a unique SSYT T. □

The statistic MAJ on Dyck paths is defined as

MAJ(w) = ∑_{i∈D(w)} i.

In [3] Fürlinger and Hofbauer defined the q-Narayana numbers, N_{q}(n, k), by

N_{q}(n, k) := ∑_{w∈𝒟_{n},des(w)=k} q^{MAJ(w)}.

We will see that N_{q}(n, k) can be written in the explicit form of (1). For each set-valued statistic in Theorem 9 we get a bi-statistic with a distribution given by the q-Narayana numbers . Theorem 11. For all n, k ≥ 0 we have

N_{q}(n, k) = s_{⟨2^{k}⟩}(q, q^{2}, …, q^{n−1}).

Proof. By Theorem 10 we have that

∑_{w∈𝒟_{n},des(w)=k} q^{MAJ(w)} = ∑_{|S|=k} β_{n}(S)q^{∑_{s∈S} s}

= ∑_{T} q^{∑ T_{ij}},

where the last sum is over all SSY T s T of shape ⟨2^{k}⟩ with parts less than n. By the combinatorial definition of the Schur function this is equal to s_{⟨2^{k}⟩}(q, q^{2}, …, q^{n−1}), and the theorem follows. □

To re-derive the formula (1) of the q-Narayana numbers we apply the hook-content formula, Theorem 12, to the expression in Theorem 11. If we identify a partition λ with its diagram {(i, j) : 1 ≤ j ≤ λ_{i}} then the hook length, h(u), at u = (x, y) ∈ λ is defined by

h(u) = |{(x, j) ∈ λ : j ≥ y}| + |{(i, y) ∈ λ : i ≥ x}| − 1,

and the content, c(u), is defined by c(u) = y −x. Let [n] := 1+q +⋯+q^{n−1}, [n]! := [n][n − 1] ⋯ [1] and

\left[{n \atop k}\right] := \frac{[n]!}{[n − k]![k]!}.

Theorem 12 (Hook-content formula). For any partition λ and n > 0,

s_{λ}(q, q^{2}, …, q^{n}) = q^{∑ iλ_{i}} ∏_{u∈λ} \frac{[n + c(u)]}{[h(u)]}.

For a proof see Theorem 7.21.2 of [11]. We now have an alternative proof of the following result which was proved in [3], and is a special case of a result of MacMahon, stated without proof in [7, p. 1429]. Corollary 13 (Fürlinger, Hofbauer, MacMahon). The q-Narayana numbers are given by:

N_{q}(n, k) = \frac{1}{[n]}\left[{n \atop k}\right]\left[{n \atop k + 1}\right]q^{k^{2}+k}

Proof. The Corollary follows from Theorem 11 after an elementary application of the hook-content formula, which is left to the reader. □

Remark 14. The Narayana statistic ea (even ascents) cannot in a natural way be associated to a shelling of Δ(J(2 × n)). However, it would be interesting to find a co-statistic s for ea such that the bi-statistic (ea, s) has the q-Narayana distribution.

References

[1] L. Carlitz and J. Riordan. Two element lattice permutation numbers and their qgeneralization. Duke Math. J., 31:371–388, 1964.

[2] Emeric Deutsch. A bijection on Dyck paths and its consequences. Discrete Math., 179(1-3):253–256, 1998.

[3] J. Fürlinger and J. Hofbauer. q-Catalan numbers. J. Combin. Theory Ser. A, 40(2):248–264, 1985.

[4] G. Kreweras. Sur les partitions non croisées d’un cycle. Discrete Math., 1(4):333–350, 1972.

[5] G. Kreweras and P. Moszkowski. A new enumerative property of the Narayana numbers. J. Statist. Plann. Inference, 14(1):63–67, 1986.

[6] Germain Kreweras. Joint distributions of three descriptive parameters of bridges. In Combinatoire énumérative (Montreal, Que., 1985/Quebec, Que., 1985), volume 1234 of Lecture Notes in Math., pages 177–191. Springer, Berlin, 1986.

[7] Percy Alexander MacMahon. Collected papers. Vol. I. MIT Press, Cambridge, Mass., 1978. Combinatorics, Mathematicians of Our Time, Edited and with a preface by George E. Andrews, With an introduction by Gian-Carlo Rota.

[8] T.V. Narayana. Sur les treillis formés par les partitions d’un entier et leurs applications à la théorie des probabilités. C. R. Acad. Sci. Paris, 240:1188–1189, 1955.

[9] Rodica Simion. Combinatorial statistics on noncrossing partitions. J. Combin. Theory Ser. A, 66(2):270–301, 1994.

[10] Richard P. Stanley. Enumerative combinatorics. Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original.

[11] Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

[12] Robert A. Sulanke. Catalan path statistics having the Narayana distribution. In Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995), volume 180, pages 369–389, 1998.

[13] Robert A. Sulanke. Constraint-sensitive Catalan path statistics having the Narayana distribution. Discrete Math., 204(1-3):397–414, 1999.

[14] Robert A. Sulanke. The Narayana distribution. J. Statist. Plann. Inference, 101(1-2):311–326, 2002. Special issue on lattice path combinatorics and applications (Vienna, 1998).

Matematik, Chalmers tekniska högskola och Göteborgs universitet, S-412 96 Göteborg, Sweden

E-mail address: branden@math.chalmers.se