Séminaire Lotharingien de Combinatoire 50 (2003), Article B50c

THE CHARNEY-DAVIS QUANTITY FOR CERTAIN GRADED POSETS

V. REINER, D. STANTON, AND V. WELKER

Abstract. Given a naturally labelled graded poset P with r ranks, the alternating sum

W (P, −1) := ∑_{w∈L(P)}(−1)^{des(w)}

is related to a quantity occurring in the Charney-Davis Conjecture on flag simplicial spheres. When |P | − r is odd it vanishes. When |P | − r is even and P satisfies the Neggers-Stanley Conjecture, it has sign (−1)^{\frac{|P |−r}{2}} .

We interpret this quantity combinatorially for several classes of graded posets P, including certain disjoint unions of chains and products of chains. These interpretations involve alternating multiset permutations, Baxter permutations, Catalan numbers, and Franel numbers.

1. Introduction

We begin by recalling the Neggers-Stanley Conjecture; see [2, 14, 19] for background and its current status. For any poset P on [n] := {1, 2, …, n}, with order relation denoted <_{P}, let L(P) be the set of its linear extensions, that is, permutations w = (w_{1}, …, w_{n}), for which i <_{P} j implies w^{−1}(i) < w^{−1}(j). The P -Eulerian polynomial

W (P, t) := ∑_{w∈L(P)} t^{des(w)}

is the generating function for these linear extensions according to the cardinality of their descent sets:

Des(w) := {i ∈ [n − 1] : w_{i} > w_{i+1}}
des(w) := | Des(w)|.

Key words and phrases. Charney-Davis conjecture, Neggers-Stanley conjecture, alternating permutations, Baxter permutations, Catalan numbers, Franel numbers.

First, second author supported by NSF grants DMS-9877047, DMS-0203282 respectively. Third author supported by DFG and European Union grant HPRN-CR-2001-00272.

Conjecture 1.1 (Neggers-Stanley). For any poset P on [n] the polynomial W (P, t) has only real (non-positive) zeroes.

We will mainly be interested in the case where P is naturally labelled, that is i <_{P} j implies i < j. For naturally labelled posets Conjecture 1.1 was made originally by Neggers [13] and proposed in the form above by Stanley in 1986 (see [19, §2]).

In [14], it is shown that if P is naturally labelled and graded with r ranks (that is, every maximal chain has exactly r elements), then there exists a simplicial convex polytope of dimension |P |−r whose boundary complex Δ_{P} has its h-polynomial equal to W (P, t). This implies that W (P, t) is a polynomial in t of degree |P | − r with positive, symmetric and unimodal coefficient sequence, and hence that W (P, −1) vanishes for |P | − r odd. Furthermore, it turns out that in some cases (e.g. if P has width at most 2; see [14, Thm. 3.23]) then Δ_{P} is a flag (or clique) complex. In this case, W (P, t) is related to a conjecture of Charney and Davis [4, Conjecture D] which would imply that

(1.1)  (−1)^{\frac{|P |−r}{2}} W (P, −1) ≥ 0.

For this reason, we call this conjecturally non-negative quantity the Charney-Davis quantity for any graded poset P. It is an easy consequence (see [4, Lemma 7.5] or [14, Proposition 1.4]) of the symmetry of W (P, t) that whenever the Neggers-Stanley Conjecture holds for P, the above Charney-Davis inequality (1.1) follows.

This suggests looking for a combinatorial interpretation for this nonnegative integer in these instances. We give such interpretations for subfamilies of posets of two kinds: disjoint unions of chains (Section 2), and products of two chains (Section 3).

We should remark that there has been recent interest in the quantity analogous to W (P, −1) obtained by replacing the descent number des(w) with the major index maj(w) or the inversion number inv(w); see [18] and the references therein. We are not aware of any relation between those results and ours.

We record here one fact that will be useful in what follows. For any naturally labelled poset P on [n], define the order polynomial Ω(P, m) to be the number of order-preserving maps from P to an m-element chain m. Then it is known [16, Theorem 4.5.14] that

(1.2)  ∑_{m≥1} Ω(P, m)t^{m} = \frac{tW (P, t)}{(1 − t)^{|P |+1}} .

For the naturally labelled posets which we consider, Ω(P, m) has a simple enough form to make the above formula useful.

2. Disjoint unions of chains

In [15], R. Simion gave the first non-trivial results on the Neggers-Stanley Conjecture by proving it in the case P = r_{1} ⊔ ⋯ ⊔ r_{N} is a naturally labelled disjoint union of N chains r_{i}, i ∈ [N], where r_{i} denotes a chain of r_{i} elements.

In this case, one can alternately interpret W (P, t) in terms of rearrangements of a multiset as follows. Let 1^{r_{1}} ⋯ N^{r_{N}} denote a multiset of letters containing r_{i} occurrences of the letter i for each i ∈ [N], and let 𝔖(1^{r_{1}} ⋯ N^{r_{N}}) denote the set of all rearrangements w = w_{1}w_{2} ⋯ w_{n} of these letters, where n = ∑_{i=1}^{N} r_{i}. Then there is an obvious bijection between L(r_{1} ⊔ ⋯ ⊔ r_{N}) and 𝔖(1^{r_{1}} ⋯ N^{r_{N}}), having the property that descents in a permutation in L(P) correspond to (strict) descents w_{i} > w_{i+1} in the rearrangement w. Thus

W (r_{1} ⊔ ⋯ ⊔ r_{N}, t) = ∑_{w∈𝔖(1^{r_{1}}···N^{r_{N}})}t^{des(w)}.

We are mostly interested in the case where P is a graded disjoint union of chains, that is N chains each having r elements; call this poset P_{N,r}. Note that P_{N,r} has an explicit formula for its order polynomial, namely

Ω(P_{N,r}, m) = \binom{r + m − 1}{m − 1}^{N} = \binom{r + m − 1}{r}^{N}.

Hence formula (1.2) yields in this case that (2.1)

\begin{aligned}W (P_{N,r}, t) & = (1 − t)^{Nr+1} ∑_{m≥0} \binom{r + m}{m}^{N}t^{m} \\ & = (1 − t)^{Nr+1} _{N}F_{N−1} (\begin{matrix}r + 1, & r + 1, & ⋯, & r + 1 \\ & 1, & ⋯, & 1 \end{matrix}| t) . \end{aligned}

where _{r}F_{s} denotes the usual hypergeometric function [6, Chapter 2].

We start with small values of r. If r = 1 then P_{N,1} is an antichain on [N]. In this case W (P_{N,1}, t) = ∑_{w∈𝔖_{N}} t^{des(w)} is (essentially) the classical Eulerian polynomial, whose exponential generating function

(2.2)  ∑_{N≥0} W (P_{N,1}, t)\frac{u^{N}}{N!} = \frac{(1 − t)e^{u(1−t)}}{1 − te^{u(1−t)}} .

is well-known, and can be derived easily from (2.1).

Setting t = −1 gives the exponential generating function

\begin{aligned}∑_{N≥0} W (P_{N,1}, −1)\frac{u^{N}}{N!} & = ∑_{N≥0} ∑_{w∈𝔖_{N}}(−1)^{des(w)} \frac{u^{N}}{N!} \\ & = \frac{2e^{2u}}{1 + e^{2u}} = 1 + tanh(u). \end{aligned}

This implies that for N odd (so |P | − r = N − 1 is even) the Charney-Davis quantity (−1)^{\frac{N−1}{2}} W (P_{N,1}, −1) is the Euler number E_{N}. The Euler number E_{N} counts the number of alternating permutations w ∈ 𝔖_{N}, that is, those permutations with Des(w) = {2, 4, …}; see [16, §3.16]. The authors thank Ira Gessel for pointing out the following proof of this fact by a sign-reversing involution.

Proposition 2.1.

There is an involution ι : 𝔖_{N} → 𝔖_{N} satisfying:

• des(ι(w)) = des(w) ± 1 if ι(w) ≠ w,

• if N is even then ι has no fixed points, and

• if N is odd then ι(w) = w ⇔ w is an alternating permutation.

In particular, the following identity holds:

W (P_{N,1}, −1) = ∑_{w∈𝔖_{N}}(−1)^{des(w)} = \begin{cases}(−1)^{\frac{N−1}{2}} E_{N} & for N odd, \\ 0 & for N even. \end{cases}

Proof. We recall a standard encoding of permutations w ∈ 𝔖_{N} as decreasing binary trees on vertex set [N], that is planar binary trees in which the labels along any path away from the root are decreasing (cf. [16, §1.3]). In this encoding we choose the largest letter in w as the root vertex and divide w into a left subword consisting of those letters to the left of the largest letter and an analogously defined right subword. The left and right subtree of the root are then obtained by applying the same procedure recursively to the left and right subword.

Under this correspondence, complete binary trees (those in which every non-leaf has both left and right subtrees non-empty) correspond to alternating permutations. To define ι on each incomplete binary tree, find the smallest labelled vertex having exactly one of its left and right subtrees non-empty, and exchange the empty subtree for the nonempty one. It is easy to see this either removes or creates exactly one descent. □

An intriguing variation holds when r = 2. Generalizing the definition of alternating permutations from sets to multisets, call a multiset permutation w ∈ 𝔖(1^{r_{1}} ⋯ N^{r_{N}}) alternating if

w_{1} ≤ w_{2} > w_{3} ≤ w_{4} > ⋯,

that is if Des(w) = {2, 4, …}. Such multiset permutations were studied by Carlitz [3].

Theorem 2.2.

There is an involution ι : 𝔖(1^{2}2^{2} ⋯ N^{2}) → 𝔖(1^{2}2^{2} ⋯ N^{2}) satisfying:

• des(ι(w)) = des(w) ± 1 if ι(w) ≠ w, and

• ι(w) = w ⇔ w is an alternating permutation. In particular, the following identity holds:

(−1)^{N−1}W (P_{N,2}, −1) = (−1)^{N−1} ∑_{w∈𝔖(1^{2}2^{2}···N^{2})}(−1)^{des(w)}
= #{alternating w ∈ 𝔖(1^{2}2^{2} ⋯ N^{2})}.

Note that the sign (−1)^{N−1} appearing in the proposition is the appropriate sign (−1)^{\frac{|P |−r}{2}} for the Charney-Davis quantity, as |P | − r = 2N − 2.

Proof. Given w ∈ 𝔖(1^{2}2^{2} ⋯ N^{2}), append a 0 to its right, creating a multiset permutation ŵ ∈ 𝔖(0^{1}1^{2}2^{2} ⋯ N^{2}) that ends with 0. As in the proof of Proposition 2.1, encode ŵ ∈ 𝔖(01^{2}2^{2} ⋯ N^{2}) as a decreasing binary tree on vertices labelled 0, 1, 1, 2, 2, …, N, N, with root labelled by the rightmost occurrence of the largest value, defining left and right subtrees recursively. Here decreasing is modified to mean that labels only weakly decrease along edges from a parent to its left-child, but strictly decrease along edges from a parent to its right-child.

One can then define an involution ι as in the proof of Proposition 2.1, by finding the smallest labelled vertex having only a left or right-subtree but not both, in which it is possible to switch it from left to right or vice-versa. When this is possible, it is easy to see that this creates or destroys exactly one descent.

As before, the alternating permutations w exactly correspond to complete decreasing binary trees; the 0 vertex will always occur to the far right, creating an extra descent w_{2N} > 0 as a right-child to w_{2N}. But there will also be other fixed points w. These will correspond to incomplete trees in which there is at least one non-leaf vertex, labelled i for some i ∈ [N], which cannot do the switch required for ι because of one of two possible types of violations: Type 1: i has left-child also labelled i, and empty right subtree, Type 2: i has 0 contained somewhere in its right subtree, and empty left

subtree. It is possible to pair up Type 1 and Type 2 violations as follows. Note that it is impossible for a value i to label both a Type 1 and Type 2 violator. Let i be the smallest labelled vertex among all violators of both types.

If i labels a Type 1 violator, contract the edge between the parent and left-child vertices labelled i, while inserting a vertex labelled i at the appropriate place in the decreasing sequence of right-children one encounters in reading downward to the right from the root N to the 0 vertex. This adds one descent to w arising from this decreasing sequence, while affecting no other descents.

If i labels a Type 2 violator, remove the vertex labelled i which has 0 in its right subtree, replacing it with an edge directly connecting its former parent to its former right child. Meanwhile, replace the other vertex labelled i with an edge between a parent labelled i and left-child labelled i, giving both of its former subtrees to the left-child i, and giving no right subtree to the parent i. This removes one descent. □

Remark 2.3. In light of Proposition 2.1 and Theorem 2.2, one might hope that for general N, r the Charney-Davis quantity

(−1)^{\frac{r(N−1)}{2}} ∑_{w∈𝔖(1^{r}2^{r}···N^{r})}(−1)^{des(w)}

could be interpreted as

\begin{cases}#\{alternating perms w ∈ 𝔖(1^{r}2^{r} ⋯ N^{r})\} & for r(N − 1) even, \\ 0 & for r(N − 1) odd. \end{cases}

Unfortunately, this fails already for r = 3, N = 3.

Having looked at cases where r is small, we turn to those where N is small. If N = 1, then P_{N,r} is a chain, so everything is trivial. When N = 2, one has the following proposition.

Proposition 2.4.

W (P_{2,r}, t) = ∑_{k=0}^{r} \binom{r}{k}^{2}t^{k},

and

W (P_{2,r}, −1) = \begin{cases}(−1)^{\frac{r}{2}} \binom{r}{\frac{r}{2}} & for r even, \\ 0 & for r odd. \end{cases}

Proof. Although various easy combinatorial proofs can be given for both assertions (e.g. [12, Vol. 1, §144, p. 169]), they also follow from (2.1) and Lemma 4.1 with a_{1} = a_{2} = 1. □

For N = 3, one has the following result. Theorem 2.5.

W (P_{3,r}, −1) = (−1)^{r} ∑_{k=0}^{r} \binom{r}{k}^{3}.

Proof. This follows from (2.1) and Lemma 4.2 with a_{1} = a_{2} = a_{3} = 1. □ Remark 2.6. The sum of the cubes of the binomial coefficients appearing in Theorem 2.5 have appeared in the literature under the name Franel numbers [8, 9]. We remark that Proposition 2.4 can be phrased in suggestively similar terms, using the identity \binom{r}{\frac{r}{2}} = ∑k=0^{\frac{r}{2}} \binom{\frac{r}{2}}{k}^{2}. However, for N = 4, there does not appear to be a connection between the quantities

∑_{w∈𝔖(1^{r}2^{r}3^{r}4^{r})}(−1)^{des(w)} and ∑_{k=0}^{r} \binom{\frac{r}{2}}{k}^{4}.

Remark 2.7. MacMahon gave two generating functions for the polynomials W (r_{1} ⊔ ⋯ ⊔ r_{N}, t), which we state here; the authors thank Ira Gessel for pointing out these results. Recall that the elementary symmetric function in N variables is denoted e_{k}(x_{1}, ⋯, x_{N}). Proposition 2.8. [12, pp. 186, 212] W (r_{1}⊔⋯⊔r_{N}, t) is the coefficient of x_{1}^{r_{1}} ⋯ x_{N}^{r_{N}} in

(1 − ∑_{k=1}^{N} e_{k}(x_{1}, ⋯, x_{N})(t − 1)^{k−1})^{−1},

and it is also the same coefficient in

∏_{i=1}^{N}(x_{1} + ⋯ + x_{i} + t(x_{i+1} + ⋯ + x_{N}))^{r_{i}}.

Thus W (P_{3,r}, −1) is the coefficient of x^{r}y^{r}z^{r} in

(x + y + z)^{r}(x + y − z)^{r}(x − y − z)^{r} or (1 − e_{1} + 2e_{2} − 4e_{3})^{−1}.

One would like a simple bijective proof of Theorem 2.5, perhaps via the fact that ∑_{k=0}^{r} \binom{r}{k}^{3} is the coefficient of x^{r}y^{r}z^{r} in

(x + y)^{r}(x + z)^{r}(y + z)^{r},

but we have no such proof so far.

3. Direct Product of Chains

The direct product P = r×s of chains of size r, s is a prime example of a Gaussian poset [16, Exercise 4.25]. Brenti proved the Neggers-Stanley conjecture for naturally labelled Gaussian posets [2, Theorem 5.6.5], using the fact that their order polynomial has the following simple expression in terms of their rank function r(x):

(3.1)  Ω(P, m) = ∏_{x∈P} \frac{m + r(x)}{1 + r(x)}.

In this subsection, we examine combinatorial interpretations for the Charney-Davis quantity of P = r × s for small values of s.

For these particular Gaussian posets, combining (1.2) with (3.1) yields the expression

(3.2)  W (s × r, t) = (1 − t)^{rs+1} ∑_{m≥0} ∏_{i=1}^{s} \frac{(i + m)_{r}}{(i)_{r}} t^{m}

where (a)_{r} := (a)(a + 1) ⋯ (a + r − 1).

If s = 1 then s × r ≅ r is a chain, so everything is trivial.

If s = 2, renaming r = n, the identity

W (2 × n, t) = ∑_{k=0}^{n−1} \frac{1}{n}\binom{n}{k}\binom{n}{k + 1}t^{k}

can be deduced either from (3.2) and the first equality in Lemma 4.1 specialized to a_{1} = 2, a_{2} = 1, or using the standard interpretation for the Narayana number \frac{1}{n} \binom{n}{k}\binom{n}{k+1} as the number of lattice paths from (0, 0) to (n, n) taking north or east steps which stay weakly above the diagonal y = x and have exactly k right turns [17, Problem 6.36]. The Charney-Davis quantity in this case can be evaluated using the second equality of Lemma 4.1 specialized to a_{1} = 2, a_{2} = 1 (see also [10, §4]):

Proposition 3.1.

W (2 × n, −1) = \begin{cases}0 & for n even, \\ (−1)^{m}C_{m} & for n = 2m + 1 odd. \end{cases}

where C_{m} = \frac{1}{m+1} \binom{2m}{m} is the Catalan number.

For s = 3, Baxter permutations come into play. A permutation π = π_{1} ⋯ π_{n} ∈ S_{n} is called a Baxter permutation if for all 1 ≤ i < j < k < l ≤ n the following two conditions are satisfied:

▷ if π_{i} + 1 = π_{l} and π_{j} > π_{l} then π_{k} > π_{l},

▷ if π_{l} + 1 = π_{i} and π_{k} > π_{i} then π_{j} > π_{i}.

In [5] it was shown that there are exactly

\begin{aligned}Baxter(n) : & = \frac{1}{\binom{n+1}{1}\binom{n+1}{2}} ∑_{m=0}^{n−1} \binom{n + 1}{m}\binom{n + 1}{m + 1}\binom{n + 1}{m + 2} \\ & = _{3}F_{2} (\begin{matrix}1 − n, & −n, & −1 − n \\ & 2, & 3 \end{matrix}| − 1) \end{aligned}

Baxter permutations in 𝔖_{n}.

The following result was discovered by computer experimentation.

Theorem 3.2.

W (3 × n, −1) = (−1)^{n−1} Baxter(n − 1).

Proof. When s = 3, one has from (3.2) that

\begin{aligned}\frac{tW (3 × n, t)}{(1 − t)^{3n+1}} & = ∑_{m≥1} t^{m} \frac{(m)_{n}(m + 1)_{n}(m + 2)_{n}}{(1)_{n}(2)_{n}(3)_{n}} \\ & = t _{3}F_{2} (\begin{matrix}n + 3, & n + 2, & n + 1 \\ & 2, & 3 \end{matrix}| t) . \end{aligned}

Applying Lemma 4.2 with a_{1} = 3, a_{2} = 1, a_{3} = 2 we have

\begin{aligned}W (3 × n, −1) & = (−1)^{n−1} _{3}F_{2} (\begin{matrix}2 − n, & 1 − n, & −n \\ & 2, & 3 \end{matrix}| − 1) \\ & = (−1)^{n−1} Baxter(n − 1). \end{aligned}

□

Remark 3.3. The previous theorem begs for a combinatorial proof. W (3×n, t) is the generating function for standard Young tableaux of shape 3×n counted by their number of descents. Dulucq and Guibert [7] have shown that Baxter(n−1) counts those standard Young tableaux of shape 3×(n−1) having no consecutive values in the same row. We were unable to find a combinatorial proof based on these tempting facts.

Remark 3.4. From (2.1) and (3.2), one can write down explicit double sums for the polynomials W (P, t) when P = P_{N,r} or P = r×n. Unfortunately, even when one sets t = −1, these double sums involve alternating signs, and hence don’t explain the sign of the associated Charney-Davis quantity W (P, −1). More temptingly, both for P = P_{4,r} and P = 4 × r, it is possible to re-express W (P, −1) in terms of a single sum, provable using the W Z-method. We state here (without proof) the explicit answer for P = P_{4,r}. If r is odd then W (P_{4,r}, −1) = 0. For r even, setting R = \frac{r}{2}, one has

W (P_{4,r}, −1) = (−1)^{R} ∑_{k=0}^{r}(−1)^{k} 2^{2r−2k} \binom{r + k}{k, k, r − k}\binom{r + 2k}{R, k, R + k}.

Note that this single sum of integer terms involves alternating signs. However, an anonymous referee pointed out that this can be rewritten. Applying a _{3}F_{2}(1) = _{4}F_{3}(1) hypergeometric transformation, which is a limit of Singh’s q-quadratic _{4}ϕ_{3}-transformation [11, (III.21), p. 243]), one obtains

W (P_{4,r}, −1) = (−1)^{R}\binom{r}{R} ∑_{k=0}^{R} \binom{r}{2k} (\frac{1}{k!} (\frac{r + 1}{2})_{k} 2^{2k})^{2} 2^{2r−4k},

a summation with positive integer summands. Unfortunately, we have no conjecture for a combinatorial interpretation in this case. Similarly, for W (r_{1} × ⋯ × r_{N}, −1) with N ≥ 3, we have no such combinatorial interpretation.

4. Appendix: Hypergeometric lemmas

In this appendix we collect the lemmas for the proofs in the previous sections.

Lemma 4.1. Let r, a_{1}, and a_{2} be non-negative integers with r+a_{2}−1 ≥ a_{1} − a_{2} ≥ 0. Then

p_{r}(t) =(1 − t)^{2r+2a_{2}−1} _{2}F_{1} (\begin{matrix}r + a_{1}, & r + a_{2} \\ & 1 + a_{1} − a_{2} \end{matrix}| t)

=\binom{r + a_{2} − 1}{a_{1} − a_{2}}^{−1} ∑_{s=0}^{r+a_{2}−1} \binom{r − a_{2} + 1}{s}\binom{r + a_{2} − 1}{a_{1} − a_{2} + s}t^{s}

= ∑_{s=0}^{(r+2a_{2}−a_{1}−1)/2} \binom{r + 2a_{2} − a_{1} − 1}{2s}×

\frac{(2s)!}{s!(1 + a_{1} − a_{2})_{s}} t^{s}(1 + t)^{r+2a_{2}−a_{1}−1−2s}.

Proof. The first statement is Euler’s transformation [6, p. 105, (2)] while the second is a quadratic transformation [6, p. 113, (35)]. □

Lemma 4.2. Let r, a_{1}, a_{2}, and a_{3} be non-negative integers with

a_{1} ≥ a_{3} ≥ a_{2}, r + a_{2} + a_{3} ≥ a_{1} + 1.

THE CHARNEY–DAVIS QUANTITY FOR CERTAIN GRADED POSETS 11

If

\begin{matrix}f_{r}(t) = \\ (1 − t)^{3r−2−a_{1}+2a_{2}+2a_{3}} _{3}F_{2} (\begin{matrix}r + a_{1}, & r + a_{2}, & r + a_{3} \\ & 1 + a_{1} − a_{2}, & 1 + a_{1} − a_{3} \end{matrix}| t) , \end{matrix}

then f_{r}(t) is a polynomial in t of degree 2r − 2 − 2a_{1} + 2a_{2} + 2a_{3}. Moreover

\begin{matrix}f_{r}(−1) = \\ C _{3}F_{2} (\begin{matrix}1 + a_{1} − 2a_{2} − r, & 1 − a_{2} − r, & 1 − a_{3} + a_{1} − a_{2} − r \\ & 1 + a_{1} − a_{2}, & 1 + a_{3} − a_{2} \end{matrix}| − 1) , \end{matrix}

where

C = (−1)^{r+a_{1}+a_{2}+a_{3}+1} \frac{(1 + a_{3} − a_{2})_{r+a_{3}+a_{2}−a_{1}−1}}{(1 + a_{1} − a_{3})_{r+a_{3}+a_{2}−a_{1}−1}} .

Proof. If we apply the well-poised _{3}F_{2} transformation [6, p. 190, (1)] we have

\begin{matrix}f_{r}(t) = (1 − t)^{2r−2−2a_{1}+2a_{2}+2a_{3}}× \\ _{3}F_{2} (\begin{matrix}(r + a_{1})/2, & (r + a_{1} + 1)/2, & 1 + a_{1} − a_{2} − a_{3} − r \\ & 1 + a_{1} − a_{2}, & 1 + a_{1} − a_{3} \end{matrix}| \frac{−4t}{(1 − t)^{2}} ) , \end{matrix}

which establishes polynomiality of f_{r}(t), and shows that f_{r}(−1) is a 3F_{2}(1).

We apply two _{3}F_{2}(1) transformations to derive the second part of Lemma 4.2. First use [1, p. 98, Ex. 7]

\begin{matrix}_{3}F_{2} (\begin{matrix}a, & b, & c \\ & d, & e \end{matrix}| 1) \\ = \frac{Γ(e)Γ(e + d − a − b − c)}{Γ(e − c)Γ(d + e − a − b)} _{3}F_{2} (\begin{matrix}d − a, & d − b, & c \\ & d, & d + e − a − b \end{matrix}| 1) \end{matrix}

with

\begin{aligned}a & = (r + a_{1})/2 \\ b & = (r + a_{1} + 1)/2 \\ c & = 1 + a_{1} − a_{2} − a_{3} − r \\ d & = 1 + a_{1} − a_{2} \\ e & = 1 + a_{1} − a_{3}. \end{aligned}

Then use the terminating transformation [1, p. 21, (1)]

(d)_{N} _{3}F_{2} (\begin{matrix}a, & b, & −N \\ & c, & 1 − d − N \end{matrix}| 1) = (a+d)_{N} _{3}F_{2} (\begin{matrix}a, & c − b, & −N \\ & c, & a + d \end{matrix}| 1)

with

\begin{aligned}a & = 1 + a_{1}/2 − a_{2} − r/2 \\ b & = 1 + a_{1} − a_{2} − a_{3} − r \\ N & = r/2 + a_{2} − a_{1}/2 − 1/2 \\ c & = 1 + a_{1} − a_{2} \\ 1 − d − N & = 3/2 + a_{1} − a_{2} − a_{3} − r. \end{aligned}

□

Acknowledgments

The authors thank Ira Gessel, Olivier Guibert and an anonymous referee for helpful comments.

References

[1] W.N. Bailey, Generalized Hypergeometric Series. Cambridge Tracts in Math. and Math. Phys. 32, Cambridge University Press, 1935.

[2] F. Brenti, Unimodal, Log-Concave and Polya Frequency Sequences in Combinatorics. Memoirs Amer. Math. Soc. 413, Amer. Math. Soc., Providence, 1989.

[3] L. Carlitz, Enumeration of up-down sequences. Discrete Math. 4 (1973), 273– 286.

[4] R. Charney and M. Davis, Euler characteristic of a nonpositively curved, piecewise Euclidean manifold. Pac. J. Math., 171 (1995), 117–137.

[5] F.R.K. Chung, R.L. Graham, V.E. Hoggatt, and M. Kleiman, The number of Baxter permutations. J. Combin. Theory Ser. A 24 (1978), 382–394.

[6] A. Erdélyi, W. Magnus, F. Oberhettinger, and F.G. Tricomi, Higher Transcendental Functions. Vol. I. Based on notes left by Harry Bateman. McGraw-Hill, 1953.

[7] S. Dulucq and O. Guibert, Stack words, standard tableaux and Baxter permutations. Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics (New Brunswick, NJ, 1994). Discrete Math. 157 (1996), 91–106.

[8] J. Franel, On a question of Laisant. L’intermédiaire des mathématiciens 1(1894), 45–47.

[9] J. Franel, On a question of J. Franel. L’intermédiaire des mathématiciens 2(1895), 33–35.

[10] N.C. Leung and V. Reiner, The signature of a toric variety. Duke Math. J. 111 (2002), 253–286.

[11] G. Gasper and M. Rahman, Basic hypergeometric series. Encyclopedia of Mathematics and its Applications 35, Cambridge University Press, Cambridge, 1990.

[12] P.A. MacMahon, Combinatory Analysis – Two Volumes in One, Chelsea Publishing, New York 1960.

[13] J. Neggers, Representations of finite partially ordered sets. J. Comb. Inf. Syst. Sci. 3 (1978), 113–133.

[14] V. Reiner and V. Welker, On the Charney-Davis and Neggers-Stanley conjec-

    tures. Available at http://www.math.umn.edu/~reiner.

[15] R. Simion, A multiindexed Sturm sequence of polynomials and unimodality of certain combinatorial sequences. J. Comb. Theory, Ser. A 36 (1984), 15–22.

[16] R.P. Stanley, Enumerative Combinatorics, Vol. 1. Cambridge Studies in Advanced Mathematics 49. Cambridge University Press, Cambridge, 1997.

[17] R.P. Stanley, Enumerative Combinatorics Vol. 2. Cambridge Studies in Advanced Mathematics 62. Cambridge University Press, Cambridge, 1999.

[18] R.P. Stanley, Some remarks on sign-balanced and maj-balanced posets, math

    Arχiv preprint math.CO/0211113.

[19] D. Wagner, Enumeration of functions from posets to chains. Eur. J. Comb. 13 (1992), 313–324.

School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA

  E-mail address: reiner@math.umn.edu

School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA

  E-mail address: stanton@math.umn.edu

Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, 35032 Marburg, Germany

  E-mail address: welker@mathematik.uni-marburg.de