Log-concavity and combinatorial properties of Fibonacci Lattices

by

Francesco Brenti^{1} Department of Mathematics University of Michigan Ann Arbor, Michigan 48109-1003 U.S.A.

Abstract

We prove that two infinite families of polynomials naturally associated to Fibonacci Lattices have only real zeros and give combinatorial interpretations to these polynomials. This in particular implies the log-concavity of several combinatorial sequences arising from Fibonacci Lattices and generalizes a result obtained by R. Stanley.

1 Introduction

Let P be a finite partially ordered set (or, poset, for short) with a bottom element (denoted by ˆ0) and a top element (denoted by ˆ1). For i ∈ N, we let c_{i} (P) be the number of chains of length i from ˆ0 to ˆ1 in P (so that c_{0}(P) = 0, c_{1}(P) = 1) and we define the chain polynomial of P by C(P; t) =^{def} ∑_{i≥1} c_{i}(P) t^{i}. The polynomial C(P; t) is one of the fundamental enumerative invariants of P and has been studied extensively, especially in the case that P is a distributive lattice. In fact, the most remarkable open problem in this area is probably the following. Conjecture 1: Let D be a (finite) distributive lattice. Then the polynomial C(D; t) has only real zeros; in particular, C(D; t) is log-concave and unimodal.

This conjecture was first stated (in a different terminology) by J. Neggers in 1978 (see [12]) and has been further studied in [14], [3], and [22]. The conjecture in its present form was first stated in [2] where it is called the “Distributive Lattice Conjecture” (see, Conj.3 in §6.3). The conjecture is known to be true for many general classes of distributive lattices and we refer the reader to [3] and [22] for a complete discussion of it.

1Partially supported by NSF grant # DMS 8903246

In this paper, motivated by the preceding Conjecture, we continue the study of a naturally related and more general problem, namely: “For which posets P does the polynomial C(P; t) have only real zeros?” This problem had already been considered in [3] (see, §6.3 and Chap. 7) where it is shown that some infinite families of posets arising from the enumeration of non-crossing partitions have chain polynomials with only real zeros. In this paper we prove an analogous result for Fibonacci Lattices.

Fibonacci Lattices have been first introduced and studied (in a special case) by Stanley in [16] and were later generalized in [18]. Further combinatorial properties of them are also developed in [20]. In this paper we prove that, given any element x of a Fibonacci Lattice, (defined in the next section) the chain polynomial of the interval [ˆ0, x] has only real zeros. Our proof relies on the theory of total positivity and this paper may be viewed as another application of this theory to problems involving combinatorial inequalities. The theory of total positivity was first applied to combinatorial problems in [2] and [3] and we refer the reader to these sources for a thorough introduction to the parts of the theory that are most often used in combinatorics as well as for a number of combinatorial applications.

The organization of the paper is as follows. In the next section we collect the definitions, notations, and results that will be used in the rest of this work. For terminology used but not defined here we will always give a reference to a definition. In §3 we derive the main log-concavity properties of Fibonacci Lattices (Theorem 8) and some of their consequences. In §4 we briefly discuss an equivalent formulation of Conjecture 1 (Conjecture 2) and show that the results obtained in §3 imply the validity of these conjectures for a new class of distributive lattices, and posets, respectively. In §5 we give combinatorial interpretations to the polynomials studied in Theorem 8 of §2. As a consequence of our main result (Theorem 15) we obtain a generalization (Corollary 4) of a result of R. Stanley (Prop. 3.2 in [20]). Finally, in §6, we consider some open problems suggested by the present work, a conjecture, and a result related to some work of Stanley.

2 Notations and Preliminaries

In this section we collect some definitions, notations and results that will be used in the rest of the paper. We let P =^{def} {1, 2, 3, …} and N =^{def} P ∪ {0}; for a ∈ N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅). The cardinality of a set A will be denoted by |A|. For i_{1}, …, i_{t} ∈ P we write {i_{1}, i_{2}, …, i_{t}}_{<} if i_{1} < i_{2} < … < i_{t}. A sequence {a_{0}, a_{1}, …, a_{d}} (of real numbers) is called log-concave if a_{i}^{2} ≥ a_{i−1}a_{i+1} for i = 1, …, d − 1,and is said to be unimodal if there exists an index 0 ≤ j ≤ d such that a_{i} ≤ a_{i+1} for i = 0, …, j − 1 and a_{i} ≥ a_{i+1} for i = j, …, d − 1. We say that a polynomial ∑_{i=0}^{d} a_{i} t^{i} is log-concave (respectively, unimodal) if the sequence {a_{0}, a_{1}, …, a_{d}} has the corresponding property. It is well known (see also the comments following Theorem 1, below) that if∑_{i=0}^{d} a_{i} t^{i} is a polynomial with nonnegative coefficients and with only real zeros, then the sequence {a_{0}, a_{1}, …, a_{d}} is log-concave and unimodal (see, e.g., [10], or [6], Thm. B, p.270).

We will follow [17] (Chap. 3) for posets and lattices notation and terminology. We now recall the definition and basic properties of Fibonacci Lattices. Let r ∈ P and let A(r) =^{def} {0, 1, 2, …, r}. We define a poset Fib(r) by taking A(r)^{⋆} (the set of all finite words in A(r)) as ground set and letting v cover u if u is obtained from v by changing a 0 in v into a nonzero digit or by deleting the last digit of v if it is nonzero. We define a second poset Z(r) by taking the same set of elements as for Fib(r) and letting v cover u if u is obtained from v by changing a 0 which is preceded only by other zeros in v into a nonzero digit or by deleting the first nonzero digit in v. So, for example, the word 002012 covers 202012, 022012, 002212, 102012, 012012, 002112, 00201 in Fib(2) and covers 202012, 102012, 022012, 012012, 00012 in Z(2). We will denote by ⪯_{F} (respectively ⪯_{Z}) the partial order thus defined on F ib(r) (respectively, Z(r)). Also, if x is covered by y in F ib(r) (respectively, Z(r)) then we will write x ⊲_{F} y (respectively, x ⊲_{Z} y). We will omit subscripts if there is no danger of confusion. It is easy to see that Fib(r) and Z(r) are (infinite) graded posets with ˆ0 = ∅ (the empty word). We will denote by ρ_{F} (respectively ρ_{Z}) the rank function of F ib(r) (respectively Z(r)). It is then easy to see that, for x ∈ A(r)^{⋆}, ρ_{F} (x) = ρ_{Z}(x) = l + m, where l is the length of x and m is the multiplicity of 0 in x (i.e., the number of = 0 digits in x). So, for example, ρ(022012) = 6 + 2 = 8. We call Z(r) the Fibonacci r-differential lattice and F ib(r) the r-Fibonacci lattice. As the name implies, both Z(r) and F ib(r) are lattices; more precisely, we have the following result. Proposition 1: For r ∈ P, the poset Fib(r) is an (upper) semimodular lattice and the poset Z(r) is a modular lattice.

The proof of Proposition 1 can be easily supplied by the reader for F ib(r) while the statement for Z(r) is proved in [18] Prop.5.4.

We will denote by ∨_{F} and ∧_{F} (respectively, ∨_{Z} and ∧_{Z}) the join, and meet operations in F ib(r) (respectively, Z(r)). We will again omit the subscripts when there is no danger of confusion. Also, for x ∈ A(r)^{⋆}, we will let

P_{x}^{(r)} =^{def} {y ∈ F ib(r) : y ⪯ x} ,  (1)

and

Q_{x}^{(r)} =^{def} {y ∈ Z(r) : y ⪯ x} .  (2)

In fact, P_{x}^{(r)} and Q_{x}^{(r)} will be the principal objects of investigation of this paper. From Proposition 1, the following properties of P_{x}^{(r)} and Q_{x}^{(r)} follow easily. Proposition 2: For r ∈ P and x ∈ A(r)^{⋆}, P_{x}^{(r)} is an upper-semimodular lattice and Q_{x}^{(r)} is a modular lattice. □

For a poset P we let l(P) denote the length of the longest chain of P. So, for example, l(P_{x}^{(r)}) = l(Q_{x}^{(r)}) = ρ(x), for x ∈ A(r)^{⋆}.

We now recall some basic definitions and results from the theory of total positivity that will be needed in the proof of the main result of the next section. A sequence of (real) numbers {a_{n}}_{n∈N} is called a Pólya frequency sequence of infinite order (or, a PF sequence, for short) if all the minors of the infinite matrix {a_{j−i}}_{i,j∈N} (where a_{k} =^{def} 0 if k < 0) have nonnegative determinant. The connection between P F sequences and polynomials with only real zeros lies in the following classical result which was first proved by Edrei in [9]. Theorem 1: Let {a_{0}, a_{1}, …, a_{d}} be a nonnegative sequence. Then the polynomial ∑_{i=0}^{d} a_{i} t^{i} has only real zeros if and only if the sequence {a_{n}}_{n∈N} (where a_{n} = 0 if n > d) is P F.

The proof of the preceding result is difficult and can be found in [11], p.412, Thm.5.3 (see also [3] Thm. 2.2.4). The reader should note that the preceding Theorem implies Newton’s inequalities (see, e.g., [10], p.104, or [6], p.270) for polynomials with only real zeros.

The following Lemma follows easily from Thm.2.2.2 of [3] and its proof is omitted. Lemma 1: Let {a_{n}}_{n∈N} be a sequence of real numbers and let, for n ∈ N,

b_{n} =^{def} ∑_{i=0}^{n} a_{i} .

Then, if {a_{n}}_{n∈N} is a P F sequence, so is {b_{n}}_{n∈N}.

Let t be an indeterminate. For d ∈ N, we denote by V_{d} the vector space of all polynomials in R[t] of degree ≤ d. Let {p_{i}(x)}_{i=0,...,d} be an ordered basis of V_{d} .

We will denote by P F [p_{i}(x)] the subset of V_{d} consisting of all polynomials A(x) = ∑_{i=0}^{d} a_{i} p_{i}(x) such that the sequence {a_{0}, …, a_{d}} is P F. In the proof of Theorem 7 we will need the following results about P F [(\begin{matrix}t+d−i \\ d \end{matrix})], (for more information about the class P F [(\begin{matrix}t+d−i \\ d \end{matrix})] see [3, Chap.4]). Theorem 2 Let A(x) be a polynomial in V_{d}. Then the following are equivalent:

(i) A(x) ∈ P F [(\begin{matrix}x+d−i \\ d \end{matrix})];

(ii) the sequence {A(n)}_{n∈N} is a P F sequence.

Theorem 3 Let A(t) be a polynomial of degree d such that A(x) ∈ P F [(\begin{matrix}t+d−i \\ d \end{matrix})]

and A(0) = 0. Then (x − a) A(x) ∈ P F [(\begin{matrix}t+d+1−i \\ d+1 \end{matrix})] for all −1 ≤ a ≤ 1.

The preceding results first appeared in [3] (see Theorems 4.6.2 and 4.3.1, respectively) and we refer the reader to this source for their proofs.

3 Log-concavity properties

For any poset P with ˆ0 and ˆ1 there is a close connection between its chain polynomial C(P; t) (defined in §1) and its zeta polynomial Z(P; t). This is the polynomial defined by

Z(P; t) =^{def} ∑_{i≥1} c_{i}(P) \binom{t}{i}  (3)

where C(P; t) = ∑_{i≥1} c_{i}(P) t^{i} (we refer the reader to [17], §3.11, and [7] for further information about the zeta polynomial of a finite poset).

The main combinatorial property of Z(P ; t) is given in the next result. Theorem 4: Let P be a poset with ˆ0 and ˆ1. Then, for all n ∈ N, Z(P ; n) equals the number of multichains of P, from ˆ0 to ˆ1, of length n.

The preceding Theorem is well known and also easy to prove directly from (3), a proof of it can be found, e.g., in [17], Prop.3.11.1. There is a third polynomial connected with Z(P ; t) and C(P ; t) which we will consider in this paper. This is the polynomial W (P ; t) defined by

W (P, t) =^{def} ∑_{i=0}^{l} w_{i}(P) t^{i}

where Z(P; t) =^{def} ∑_{i=0}^{l} (\begin{matrix}t+l−i \\ l \end{matrix}) w_{i}(P) and l is the length of the longest chain of P. The following result follows easily from the definition of W (P; t) and the Binomial Theorem (see, e.g., [17], p.16). Theorem 5: Let P be a poset with ˆ0 and ˆ1. Then

∑_{n≥0} Z(P ; n) t^{n} = \frac{W (P ; t)}{(1 − t)^{l+1}} ,  (4)

as formal power series, where l is the length of the longest chain of P. □

The connection between Z(P; t), C(P; t), and W (P; t) is particularly interesting in our case because of the next result which is an immediate consequence of Thm.4.6.2 of [3]. Theorem 6: Let P be a poset with ˆ0 and ˆ1 and suppose that the sequence {Z(P; n)}_{n∈N} is P F; Then the polynomials C(P; t) and W (P; t) have only real zeros. □

We now turn our attention to the posets P_{x}^{(r)}. Theorem 7: Let r ∈ P and let x ∈ F ib(r). Then the sequence {Z(P_{x}^{(r)}; n)}_{n∈N} is P F. Proof: We proceed by induction on ρ(x). If ρ(x) = 0 then x = ˆ0 and Z(P_{x}^{(r)}; n) = 1 for all n ∈ N so that the thesis clearly holds. Let now x = a_{1} … a_{l} and let y =^{def} a_{2} … a_{l}. Then it follows from [20], Lemma 2.2, that

Z(P_{x}^{(r)}; n) = \{ \begin{matrix}∑_{i=0}^{n}Z(P_{y}^{(r)}; i) , & if a_{1} ≠ 0, \\ ∑_{i=0}^{n}((i − 1) r + 1) Z(P_{y}^{(r)}; i) , & if a_{1} = 0. \end{matrix}  (5)

Therefore, by Lemma 1 the thesis clearly holds if a_{1} ≠ 0. So suppose that a_{1} = 0. Then ρ(y) = p − 2 and therefore deg(Z(P_{y}^{(r)}; t)) = p − 2. By the induction hypothesis {Z(P_{y}^{(r)}; n)}_{n∈N} is a P F sequence. By Theorem 2, this implies that Z(P_{y}^{(r)}; t) ∈ P F [\binom{t+p−2−i}{p−2}]. But, by Theorem 3 there follows that

(r t − (r − 1)) Z(P_{y}^{(r)}; t) ∈ P F [\binom{t + p − 1 − i}{p − 1}] .

Hence (again by Theorem 2), the sequence

{(r (n − 1) + 1) Z(P_{y}^{(r)}; n)}_{n∈N}

is P F and this, by (5) and Lemma 1, implies that {Z(P_{x}^{(r)}; n)}_{n∈N} is a P F sequence, as desired. □

From Theorems 7 and 6 we immediately deduce the first main result of this paper. Theorem 8: Let r ∈ P and x ∈ F ib(r). Then the polynomials W (P_{x}^{(r)}; t) and C(P_{x}^{(r)}; t) have only real zeros. In particular, W (P_{x}^{(r)}; t) and C(P_{x}^{(r)}; t) are logconcave and unimodal.□

Using Theorems 8 and 1 we also obtain the following result. Theorem 9: Let r ∈ P, x ∈ F ib(r), and let c_{i} be the number of chains of length i from ∅ to x in F ib(r). Then, for all i, p ≥ 1, we have that

det [ \begin{matrix}c_{i} & c_{i+1} & … & c_{i+p} \\ c_{i−1} & c_{i} & … & c_{i+p−1} \\ ⋮ & ⋮ & & ⋮ \\ c_{i−p} & c_{i−p+1} & … & c_{i} \end{matrix} ] ≥ 0 ,  (6)

where c_{j} =^{def} 0 if j ≤ 0. □

Analogously, from Theorems 7 and 4 and the definition of a P F sequence we obtain the “multi-analogue” of the preceding Theorem. Theorem 10: Let r ∈ P, x ∈ F ib(r), and let Z_{i} be the number of multichains of length i from ∅ to x in F ib(r). Then, for all i, p ≥ 1, we have that

det [ \begin{matrix}Z_{i} & Z_{i+1} & … & Z_{i+p} \\ Z_{i−1} & Z_{i} & … & Z_{i+p−1} \\ ⋮ & ⋮ & & ⋮ \\ Z_{i−p} & Z_{i−p+1} & … & Z_{i} \end{matrix} ] ≥ 0 ,  (7)

where Z_{j} =^{def} 0 if j ≤ 0. In particular, the sequence {Z_{i}}_{i∈N} is log-concave. □

It would be interesting to obtain combinatorial interpretations for the numbers in (6) and (7), a problem already raised, in a more general setting, in [3], p.10.

There is a very close connection between the lattices Fib(r) and Z(r) first pointed out in [18] and later deepened in [20]. The following result appears in [20], Thm.2.4. Theorem 11: Let r ∈ P and x ∈ A(r)^{⋆}. Then Z(P_{x}^{(r)}; t) = Z(Q_{x}^{(r)}; t), as polynomials in t. □

The preceding result, together with (3) and (4), clearly implies that C(P_{x}^{(r)}; t) = C(Q_{x}^{(r)}; t) and W (P_{x}^{(r)}; t) = W (Q_{x}^{(r)}; t). Therefore, Theorems 7 through 10 are still true if we replace “Fib(r)” with “Z(r)” and “P_{x}^{(r)}” with “Q_{x}^{(r)}” throughout their statements.

It should be noted that, even though C(Q_{x}^{(r)}; t) = C(P_{x}^{(r)}; t) it is not true that the posets Q_{x}^{(r)} and P_{x}^{(r)}, defined in (1) and (2) , are always isomorphic as posets. In fact, they don’t even have the same rank sizes, in general, (take, e.g., r = 2 and x = 201).

4 Fibonacci posets and the poset conjecture

There is an equivalent way of stating Conjecture 1 in terms of posets instead than in terms of distributive lattices. Let P be a finite poset. For n ∈ P we let Ω(P; n) be the number of order preserving maps from P to a chain with n elements. It is then not hard to see (see, e.g., [17], p.130, or [3], p.1) that Ω(P; n) is a polynomial function of n of degree |P |. This function is called the order polynomial of P and we refer the reader to [17], p.218, for further information about it. It then follows from well known results in the theory of rational generating functions (see, e.g., [17], Cor. 4.3.1) that there exists a polynomial V (P ; t) of degree ≤ |P | such that

∑_{n≥0} Ω(P ; t) t^{n} = \frac{V (P ; t)}{(1 − t)^{|P |+1}}  (8)

as formal power series. The equivalent statement of Conjecture 1 is then the following. Conjecture 2: Let P be a (finite) poset. Then V (P ; t) has only real zeros; in particular V (P ; t) is log-concave and unimodal.

Conjecture 2 is a special case of what is known as the “Poset Conjecture” (sometimes also called the “Neggers-Stanley Conjecture”). A proof of the equivalence of Conjectures 1 and 2 can be found in [3] (see Thm. 6.3.1, and Conj. 6). We refer the interested reader to [3] (see Chaps.1 and 5), [22] (see Chap.1), [14], and [19] (see Conj.2.3) for a detailed account of this conjecture and the special cases in which it is known to be true. Let us only mention that Conjecture 2 was originally made, though using a different terminology, in 1978 (see [12], p.114) and that it is still open even for the unimodality statement.

To see the connection between the results obtained in the preceding section and Conjecture 2 we need a couple of additional definitions which will also be needed in § 5.

We will denote by K_{1} the infinite poset on the elements a_{1}, a_{2}, a_{3}, … and b_{1}, b_{2}, … partially ordered so that a_{i} ≤ a_{j} and a_{i} ≤ b_{j} if and only if i ≤ j. The notation K_{1} for this infinite poset is taken from [16], p.226, where this poset was first defined and studied. The relation between K_{1} and Fibonacci lattices lies in the fact that

J(K_{1}) ≅ F ib(1) ,  (9)

(where ≅ denotes isomorphism of graded posets and, for a poset P, J(P) denotes the lattice of order ideals of P, (see, e.g., [17], §3.4)) as can be shown by an easily constructed bijection.

A finite poset P is called a Fibonacci poset (sometimes also called a Fibonacci tree, see, e.g., [13]) if P is isomorphic to an order ideal of K_{1}.

[figure]

Figure 1: The poset F_{101}.

By (9) there is a bijection between elements of F ib(1) and Fibonacci posets. In §5 it will be useful to have a convenient notation for this bijection. For x ∈ F ib(1) we therefore let F_{x} be the unique Fibonacci poset such that

J(F_{x}) ≅ P_{x}^{(1)} .  (10)

In other words, F_{x} is the poset of join-irreducible elements of P_{x}^{(1)}. The poset F_{101} is shown in Fig.1.

We can now state and prove the main result of this section. Theorem 12: Let P be a Fibonacci poset. Then Conjecture 2 holds for P. Proof: Let x ∈ F ib(1) be such that P = F_{x}. It is well known (see [17], §3.11) that, for any poset P, Ω(P; t) = Z(J(P); t). Therefore, in our case, we obtain that, by (10),

Ω(F_{x}; t) = Z(J(F_{x}); t) = Z(P_{x}^{(1)}; t) .

Therefore, by (4) and (8), we have that V (F_{x}; t) = W (P_{x}^{(1)}; t) and the thesis now follows from Theorem 6. □

Therefore Theorem 8, in the case that r = 1, gives yet another (new) class of posets for which Conjecture 2 is known to be true.

5 Combinatorial properties

Since the coefficients of polynomials with only real zeros satisfy many inequalities among them (see, e.g., Theorem 1) it is very natural to look for combinatorial interpretations of the coefficients of the polynomials considered in Theorem 8. Since the coefficients of the polynomials C(P_{x}^{(r)}; t) are combinatorially defined, in this section we give a combinatorial interpretation to the coefficients of the polynomials W (P_{x}^{(r)}; t). As a consequence of our main result (Theorem 15) we will obtain a generalization (Corollary 4) of a result of R. Stanley (Prop.3.2 of [20]).

We begin with the following elementary result whose easy proof is omitted. Note that throughout this section we will view A(r) as a subset of F ib(r), with the operations ⪯ and ∨ inherited from F ib(r). Proposition 3: Let r ∈ P and x =^{def} x_{1} … x_{n}, y =^{def} y_{1} … y_{m} ∈ F ib(r). Then:

(i) x ⪯ y if and only if n ≤ m and x_{i} ⪯ y_{i} (in A(r)) for i = 1, …, n;

(ii) x ∨ y = (x_{1} ∨ y_{1})(x_{2} ∨ y_{2}) … (x_{n} ∨ y_{n}) y_{n+1} … y_{m} if n ≤ m (and analogously if n ≥ m). □

Now let r ∈ P and z =^{def} z_{1} … z_{N} be an element of Fib(r), which will remain fixed throughout this section. For an element y = y_{1} … y_{n} ∈ F ib(r) we let

S(y) =^{def} {i ∈ [n] : y_{i} = 0}

For the rest of this section we will assume that r ≥ 2, unless otherwise explicitly stated. It will be seen later that this restriction is immaterial.

To obtain the combinatorial interpretation of the polynomials W (P_{z}^{(r)}; t) considered in §3 we will use a construction due to Stanley (see, e.g., [15], §2, [1], Ex.2.5, or [17], Ex.3.13.5). This requires, in the first place, the construction of an order preserving labeling of the join irreducible elements of P_{z}^{(r)}. Recall that an element x of a poset P is join-irreducible if and only if x covers exactly one element of P. Our first result determines all the join-irreducible elements of P_{z}^{(r)}. Proposition 4: Let r ≥ 2 and y =^{def} y_{1} … y_{m} ∈ P_{z}^{(r)}. Then y is join-irreducible if and only if y_{i} ≠ 0 for i = 1, …, m (i.e. if and only if S(y) = ∅). Proof: Suppose first that y_{i} ≠ 0 for i = 1, …, m. Then, by definition, the only element covered by y is y_{1} … y_{m−1} and so y is join-irreducible.

Conversely, suppose that y is join-irreducible and that there exists i ∈ [m] such that y_{i} = 0. Then the elements y_{1} … y_{i−1}jy_{i+1} … y_{m}, for j = 1, …, r, are all distinct and covered by y, and this contradicts the join-irreducibility of y. Hence y_{i} ≠ 0 for i = 1, …, m, as desired. □

Note that the above Proposition fails if r = 1 since, for example, 1110 is joinirreducible in Fib(1).

We will denote by I_{z}^{(r)} the set of join-irreducible elements of P_{z}^{(r)}. To totally order I_{z}^{(r)} we first totally order all the join-irreducible elements of Fib(r) lexicographically. More precisely, we say that α_{1} … α_{t} lexicographically precedes β_{1} … β_{s} (denoted α_{1} … α_{t} <_{L} β_{1} … β_{s}) if and only if either t < s, or t = s and α_{i} < β_{i} (as positive integers) where i =^{def} min{j ∈ [s] : α_{j} ≠ β_{j}}. So, for example, for r = 3, we have that 1 <_{L} 2 <_{L} 3 <_{L} 11 <_{L} 12 <_{L} 13 <_{L} 21 <_{L} 22 <_{L} 23 <_{L} 31 <_{L} 32 <_{L} 33 <_{L} 111 <_{L} 112 <_{L} . . .. We can now define a labeling ω : I_{z}^{(r)} → [|I_{z}^{(r)}|] by

ω(y) =^{def} |{x ∈ I_{z}^{(r)} : x ≤_{L} y}|.  (11)

The property of ω which we need is the following. Proposition 5: The map ω : I_{z}^{(r)} → [|I_{z}^{(r)}|] defined by (11) is order preserving (i.e., if x ⪯ y then ω(x) ≤ ω(y)). Proof: Let x = x_{1} … x_{t}, y = y_{1} … y_{s} ∈ I_{z}^{(r)} and suppose that x ⪯ y, x ≠ y. Then t ≤ s and x_{i} ⪯ y_{i} for i ∈ [t]. Now, since y ∈ I_{z}^{(r)}, we have that y_{i} ⪯ 0 for i ∈ [s]. Hence x_{i} = y_{i} for i ∈ [t]. Since x ≠ y this implies that t < s and therefore that x <_{L} y. Hence, by (11), ω(x) < ω(y), as desired. □

The second step of the construction is to use ω to label the cover relations of P_{z}^{(r)} as follows. Let x, y ∈ P_{z}^{(r)}, x ⊲ y, then we let

I_{z}^{(r)}(x, y) =^{def} min{α ∈ I_{z}^{(r)} : x ∨ α = y} , λ(x, y) =^{def} ω(I_{z}^{(r)}(x, y)) ,  (12)

(where the minimum is with respect to the lexicographic order). Note that I_{z}^{(r)}(x, y) is always defined since P_{z}^{(r)} is an upper semimodular lattice. For a saturated chain x_{0} ⊲ x_{1} ⊲ … ⊲ x_{n} in P_{z}^{(r)} we also let

λ(x_{0}, x_{1}, …, x_{n}) =^{def} (λ(x_{0}, x_{1}), λ(x_{1}, x_{2}), …, λ(x_{n−1}, x_{n})).

We can now state the first main result of this section. Recall that, given a sequence x =^{def} (x_{1}, …, x_{m}) ∈ Z^{m}, the descent set of x is the set D(x) =^{def} {i ∈ [m − 1] : x_{i} > x_{i+1}}. Theorem 13: Let r ≥ 2 and z ∈ F ib(r). Then

W (P_{z}^{(r)} ; t) = ∑_{ˆ0=x_{0}◁x_{1}◁...◁x_{m}=z} t^{|D(λ(x_{0},x_{1},...,x_{m})|+1}

where m = ρ(z) and the sum is over all maximal chains from ˆ0 to z in Fib(r). Proof: It is known (see, e.g., [17], Chap.3, Ex.67(b)) that for any graded poset P with ˆ0 and ˆ1, of rank m, we have that

∑_{n≥0} Z(P ; n) t^{n} = \frac{∑_{S⊆[m−1]} β(P, S) t^{|S|+1}}{(1 − t)^{m+1}}  (13)

(as formal power series in C[[t]]) where Z(P ; t) is the zeta polynomial of P and where β(P, S) are integers depending only on P and S (see, e.g., [17], §3.12, for the definition of the numbers β(P, S)). So, for P_{z}^{(r)}, we have, from (4) and (13), that

W (P_{z}^{(r)} ; t) = ∑_{S⊆[m−1]} β(P_{z}^{(r)} ; S) t^{|S|+1} .

Now, by Propositions 2 and 5 and by Prop.2.2 of [15], ω is an admissible labeling of P_{z}^{(r)} (see [15], §2, for the definition of an admissible labeling), and the conclusion then follows from Thm.3.1 of [15] and our definition of the labeling λ. □

The combinatorial interpretation of the polynomial W (P_{z}^{(r)} ; t) given by the preceding Theorem is not completely satisfactory because the labelings ω and λ may not be easy to compute. However, as we will now show, it is possible to obtain a more explicit combinatorial interpretation of W (P_{z}^{(r)}; t). To do this it is useful to introduce a new statistic on the elements of Fib(r). For α =^{def} α_{1} … α_{t} ∈ Fib(r) we let

O(α) =^{def} ∑_{i∈S(α)} i ,

and call O(α) the order of α. So, for example, O(10231011) = 2 + 6 = 8. Note that O(α) = 0 if and only if α is join-irreducible and that, by Proposition 3, if x, y ∈ Fib(r) and x ⪯ y, then O(x) ≤ O(y). For x, y ∈ F ib(r) we also let Δ(x, y) =^{def} O(y) − O(x). A useful property of the Δ function is given in the next result whose easy verification is omitted. Lemma 2: Let r ∈ P and x =^{def} x_{1} … x_{m}, y =^{def} y_{1} … y_{n} ∈ F ib(r). Suppose that x ⊲ y, and that Δ(x, y) > 0. Then x_{k} ≠ 0 and y_{k} = 0, where k =^{def} Δ(x, y). □

We also define a map φ : A(r) → A(r) by

φ(a) =^{def} \{ \begin{matrix}a , & if a ≠ 0, \\ 1 , & if a = 0, \end{matrix}  (14)

for a ∈ A(r). For y =^{def} y_{1} … y_{m} ∈ P_{z}^{(r)} we let φ(y) =^{def} φ(y_{1}) … φ(y_{m}) . Note that this defines a map φ : P_{z}^{(r)} → I_{z}^{(r)}.

We can now give an explicit description of the element α ∈ I_{z}^{(r)} which, given x ⊲ y, has the property that λ(x, y) = ω(α).

Proposition 6: Let r ≥ 2, x =^{def} x_{1} … x_{m}, y =^{def} y_{1} … y_{n} ∈ P_{z}^{(r)} and suppose that x ⊲ y. Then

I_{z}^{(r)}(x, y) = \{ \begin{matrix}φ(y) , & if Δ(x, y) = 0, \\ φ(x_{1} … x_{k−1}) a , & if Δ(x, y) > 0, \end{matrix}

where k =^{def} Δ(x, y) and

a =^{def} \{ \begin{matrix}2 , & if x_{k} = 1, \\ 1 , & otherwise. \end{matrix}

Proof: Suppose first that Δ(x, y) = 0. Then n = m + 1 and y = x_{1} … x_{m} i for some i ≠ 0. Now, it is clear that φ(y) ∈ I_{z}^{(r)} and that x ∨ φ(y) = y. So let γ = γ_{1} … γ_{t} ∈ I_{z}^{(r)} be such that x ∨ γ = y. Then t = m + 1 and

x_{1} … x_{m} i = y = x ∨ γ = (x_{1} ∨ γ_{1}) … (x_{m} ∨ γ_{m}) γ_{m+1} .

Therefore, γ_{m+1} = i and x_{j} ∨ γ_{j} = x_{j} for j ∈ [m]. This implies that x_{j} = γ_{j} if j ∉ S(x). Therefore, by (14),

φ(x_{j}) = \{ \begin{matrix}1 , & if j ∈ S(x), \\ γ_{j} , & if j ∉ S(x). \end{matrix}

Hence φ(x_{j}) ≤ γ_{j} (as integers) for j ∈ [m]. Since γ_{m+1} = i this shows that φ(x_{1}) … φ(x_{m}) φ(i) ≤_{L} γ_{1} … γ_{m+1}and hence that φ(y) ≤_{L} γ, as desired.

Suppose now that Δ(x, y) > 0. Then n = m and y = x_{1} … x_{k−1}0x_{k+1} … x_{m}, where k = Δ(x, y) and x_{k} ≠ 0. It is again clear that then φ(x_{1} … x_{k−1}) a ∈ I_{z}^{(r)} and x ∨ (φ(x_{1} … x_{k−1}) a) = y. So let γ = γ_{1} … γ_{t} ∈ I_{z}^{(r)} be such that x ∨ γ = y. Now, if t ≥ k + 1, then clearly φ(x_{1} … x_{k−1}) a ≤_{L} γ_{1} … γ_{t} = γ, as desired. So suppose that t ≤ k. Then

x_{1} … x_{k−1} 0 x_{k+1} … x_{m} = y = x ∨ γ = (γ_{1} ∨ x_{1}) … (γ_{t} ∨ x_{t}) x_{t+1} … x_{m} .

Since x_{k} ≠ 0 we must have that t = k and x_{i} = x_{i} ∨ γ_{i}, for i ∈ [k − 1]. Hence we conclude that x_{j} = γ_{j}, if j ∉ S(x) ∩ [k − 1], and γ_{k} ≠ x_{k}. Therefore, by (14),

φ(x_{j}) = \{ \begin{matrix}1 , & if j ∈ S(x), \\ γ_{j} , & if j ∉ S(x) ∩ [k − 1]. \end{matrix}

Hence φ(x_{j}) ≤ γ_{j} (as integers), for j ∈ [k − 1]. Since γ_{k} ≠ 0, x_{k} we conclude that φ(x_{1}) … φ(x_{k−1}) a ≤_{L} γ_{1} … γ_{k}, and hence that φ(x_{1} … x_{k−1}) a ≤_{L} γ, as desired. □

An immediate consequence of the preceding Proposition is the following. Corollary 1: Let r ≥ 2, x, y ∈ P_{z}^{(r)}, and suppose that x ⊲ y. Then

l (I_{z}^{(r)}(x, y)) ≤ l(y) .□

We can now prove the following result which will be the key step in the proof of the main result of this section. Proposition 7 : Let r ≥ 2, α, β, γ ∈ P_{z}^{(r)}, with α ⊲ β ⊲ γ, and λ be the labeling defined by (12). Then λ(β, γ) < λ(α, β) if and only if Δ(β, γ) > 0 and either one of the following (mutually exclusive) conditions is satisfied:

(i) Δ(β, γ) < Δ(α, β);

(ii) Δ(α, β) = 0 and Δ(β, γ) < l(γ);

(iii) Δ(α, β) = 0, Δ(β, γ) = l(γ), and the last letter of β is ≠ 1.

Proof: Note that λ(β, γ) < λ(α, β) if and only if I_{z}^{(r)}(α, β) >_{L} I_{z}^{(r)}(β, γ). There are essentially three cases to consider. Suppose first that Δ(β, γ) = 0. Then, l(β) = l(γ) − 1. Hence by Proposition 6 and Corollary 1, l (I_{z}^{(r)}(β , γ)) = l (φ(γ)) = l(γ) > l(β) ≥ l (I_{z}^{(r)}(α , β)), and therefore I_{z}^{(r)}(α , β) <_{L} I_{z}^{(r)}(β , γ), in this case. Suppose now that Δ(β, γ) > 0 and that Δ(α, β) > 0. Then, by Proposition 6,

l (I_{z}^{(r)}(α , β)) = Δ(α, β) ,  (15)

and

l (I_{z}^{(r)}(β , γ)) = Δ(β, γ) .  (16)

Furthermore, we claim that Δ(α, β) ≠ Δ(β, γ). In fact, if Δ(α, β) = Δ(β, γ) = k, then applying Lemma 2 twice (with x = α, y = β, and with x = β, y = γ) we obtain a contradiction. Therefore l (I_{z}^{(r)}(α , β)) ≠ l (I_{z}^{(r)}(β , γ)), and hence I_{z}^{(r)}(α , β) >_{L} I_{z}^{(r)}(β , γ) if and only if l (I_{z}^{(r)}(α , β)) > l (I_{z}^{(r)}(β , γ)) which, by (15) and (16), is the desired result. Finally, suppose that Δ(α, β) = 0 and Δ(β, γ) > 0. Then, by Proposition 6 and Corollary 1,

l (I_{z}^{(r)}(α , β)) = l(β) = l(γ) ≥ l (I_{z}^{(r)}(β , γ)) = Δ(β, γ) .  (17)

Furthermore, by Lemma 2, equality holds in (17) if and only if β = α i and γ = α 0 for some i ≠ 0; but, in this case, Proposition 6 implies that I_{z}^{(r)}(α , β) >_{L} I_{z}^{(r)}(β , γ) if and only if i ≠ 1, and the proof follows. □

We can now obtain an explicit combinatorial interpretation of W (P_{z}^{(r)}; t). For a ∈ A(r) we let

\overline{a} =^{def} \{ \begin{matrix}0 , & if a = 0, \\ 1 , & otherwise. \end{matrix}

For any x =^{def} x_{1} … x_{m} ∈ A(r)^{⋆} we then let

\overline{x} =^{def} \overline{x}_{1} … \overline{x}_{m} .  (18)

The next result is an easy verification. Proposition 8 :Let r ∈ P and x, y ∈ F ib(r), then x ⪯ y implies \overline{x} ⪯ \overline{y}. Furthermore ρ(x) = ρ(\overline{x}) and O(x) = O(\overline{x}) for all x ∈ F ib(r). □

We define a map

Φ : M(P_{z}^{(r)}) → M(P (1) ; \overline{z}) × [r]^{S(z)} ,

(where, for a poset P, M(P) denotes the set of all maximal chains of P) as follows. Let x =^{def} (ˆ0 = x_{0} ⊲ x_{1} ⊲ … ⊲ x_{m} = z) be a maximal chain of P_{z}^{(r)} and let x_{i} =^{def} x_{i,1} … x_{i,t_{i}}, for i = 1, …, m. We then let

Φ(x) =^{def} (\overline{x} , f)  (19)

where \overline{x} =^{def} (ˆ0 = \overline{x}_{0} ⊲ \overline{x}_{1} ⊲ … ⊲ \overline{x}_{m} = \overline{z}), and f : S(z) → [r] is defined by letting

f(j) =^{def} x_{ij}  (20)

and where i =^{def} max {k : x_{kj} ≠ 0} (note that {k : x_{kj} ≠ 0} ≠ ∅ since j ∈ S(z)). So, for example, if r = 2, then the image under Φ of the maximal chain ˆ0 < 2 < 21 < 01 < 00 < 002 = z is the pair (ˆ0 < 1 < 11 < 01 < 00 < 001 = \overline{z} , f) where f(1) = 2 and f(2) = 1. It is easy to see that the map Φ just defined is a bijection.

We can now prove the main result of this section. Recall that a linear extension of a poset P is an order preserving bijection σ : P → [|P |] (see, e.g., [17], p. 110, for further details), and that we denote by a_{1}, b_{1}, a_{2}, b_{2}, … the elements of the poset K_{1} (see §4). Theorem 14: Let r ∈ P and z ∈ F ib(r). Then

W (P_{z}^{(r)}; t) = ∑_{σ: F\overline{z}→[ρ(z)]} t^{|D((\overline{σ})^{−1})|+1} ∑_{f : S(z)→[r]} t^{|S(f,σ)|} ,

where S(f, σ) =^{def} \{j ∈ S(z) : σ(b_{j}) = σ(a_{j}) + 1 and f(j) > 1\}, \overline{σ} is the permutation

σ(a_{1}) … σ(a_{i_{1}})σ(b_{i_{1}})σ(a_{i_{1}+1}) … σ(a_{i_{2}})σ(b_{i_{2}})σ(a_{i_{2}+1}) … σ(a_{i_{t}})σ(b_{i_{t}})σ(a_{i_{t}+1}) … σ(a_{N})

(where \{i_{1}, …, i_{t}\}_{<} =^{def} S(z)), and σ runs over all linear extensions of F\overline{z}. Proof: Since, by (10), P (1) ; \overline{z} ≅ J(F\overline{z}), the result follows from (4) and Theorem 6.5.14 of [17] in the case that r = 1. Therefore, we may assume that r ≥ 2. Then by Theorem 13 we have that

W (P_{z}^{(r)}; t) = ∑_{x∈M(P_{z}^{(r)})} t^{|D(λ(x))|+1} = ∑_{\overline{x}∈M(P (1) ; \overline{z})} ∑_{f : S(z)→[r]} t^{|D(λ(x))|+1}

since the map Φ defined by (19) and (20) is a bijection. Now, it is well known that, given a poset P, and a maximal chain \overline{x} = (∅ = \overline{x}_{0} ⊲ \overline{x}_{1} ⊲ … ⊲ \overline{x}_{m} = P) of J(P) one can construct a linear extension σ\overline{x} : P → [|P |], by letting

σ\overline{x}(\overline{x}_{i} \ \overline{x}_{i−1}) =^{def} i ,  (21)

for i = 1, …, m, and that this correspondence is a bijection (see [17], Props. 3.5.1 and 3.5.2, for details). Hence, in our case, we obtain that

W (P_{z}^{(r)}; t) = ∑_{\overline{x}∈M(J(F\overline{z}))} ∑_{f : S(z)→[r]} t^{|D(λ(x))|+1}
= ∑_{σ \overline{x} : F\overline{z}→[ρ(z)]} ∑_{f : S(z)→[r]} t^{|D(λ(x))|+1}

where σ\overline{x} is defined by (21).

Now let x =^{def} (ˆ0 = x_{0} ⊲ x_{1} ⊲ … ⊲ x_{m} = z) be a maximal chain of P_{z}^{(r)}, \overline{x} =^{def} (ˆ0 = \overline{x}_{0} ⊲ \overline{x}_{1} ⊲ … ⊲ \overline{x}_{m} = \overline{z}) and σ be the linear extension of F\overline{z} corresponding to the maximal chain \overline{x} of J(F\overline{z}) = P (1) ; \overline{z}. Then there exist (unique) distinct indices 1 ≤ j_{1} , j_{2} , …, j_{t} ≤ m − 1 such that

\overline{x}_{j_{s}+1} \ \overline{x}_{j_{s}} = \{b_{i_{s}}\} ,  (22)

for s = 1, …, t, (here and in what follows we will freely identify elements of P (1) ; \overline{z} with order ideals (hence subsets ) of F\overline{z}) Therefore, by (21),

σ(b_{i_{s}}) = j_{s} + 1 ,  (23)

and, by (22) and Lemma 2,

i_{s} = Δ(x_{j_{s}} , x_{j_{s}+1}) ,  (24)

for s = 1, …, t. We now claim that, for k = 1, …, t,

λ(x_{j_{k}} , x_{j_{k}+1}) < λ(x_{j_{k}−1} , x_{j_{k}})  (25)

if and only if either one of the following two (mutually exclusive) conditions is satisfied:

(A) σ(b_{i_{k}}) is to the left of σ(b_{i_{k}}) − 1 in \overline{σ};

(B) σ(b_{i_{k}}) = σ(a_{i_{k}}) + 1 and f(i_{k}) > 1 (i.e., i_{k} ∈ S(f, σ)).

So fix k ∈ [t] and assume that (25) holds. By (24), (with s = k), we see that

Δ(x_{j_{k}}, x_{j_{k}+1}) > 0 .

Also, by Proposition 7, (25) implies that at least one of the following (mutually exclusive) conditions hold.

(i) Δ(x_{j_{k}}, x_{j_{k+1}}) < Δ(x_{j_{k}−1}, x_{j_{k}}). Then Δ(x_{j_{k}−1}, x_{j_{k}}) > 0 and hence there is an index 1 ≤ h ≤ t, h ≠ k, such that j_{k} − 1 = j_{h}. Therefore, by (23) (with s = k, and s = h), we get that

σ(b_{i_{k}}) − 1 = j_{k} = j_{h} + 1 = σ(b_{i_{h}}) .  (26)

Furthermore, letting s = h and s = k in (24) and using (i) we obtain that i_{h} = Δ(x_{j_{h}}, x_{j_{h}+1}) = Δ(x_{j_{k}−1}, x_{j_{k}}) > Δ(x_{j_{k}}, x_{j_{k}+1}) = i_{k}. Therefore h > k and hence σ(b_{i_{k}}) is to the left of σ(b_{i_{h}}) in \overline{σ} which, by (26), implies (A). (ii) Δ(x_{j_{k}−1}, x_{j_{k}}) = 0 and Δ(x_{j_{k}}, x_{j_{k}+1}) < l(x_{j_{k}+1}). Then, using (24) (with s = k) we obtain that i_{k} + 1 = Δ(x_{j_{k}}, x_{j_{k}+1}) + 1 ≤ l(x_{j_{k}+1}). But this means that a_{i_{k}+1} ∈ \overline{x}_{j_{k}+1}, and hence that σ(b_{i_{k}}) > σ(a_{i_{k}+1}). Therefore σ(a_{i_{k}}) ≤ σ(b_{i_{k}}) − 2. Since σ is a linear extension this proves that either σ(b_{i_{k}}) − 1 is to the right of σ(b_{i_{k}}), or σ(b_{i_{k}}) − 1 = σ(b_{i_{h}}) for some h < k. But in this latter case we would have that j_{k} = σ(b_{i_{k}}) − 1 = σ(b_{i_{h}}) = j_{h} + 1 and hence that Δ(x_{j_{k}−1}, x_{j_{k}}) = Δ(x_{j_{h}}, x_{j_{h}+1}) = i_{h} > 0, contrary to our hypothesis (ii). Therefore (A) follows. (iii) Δ(x_{j_{k}−1}, x_{j_{k}}) = 0, Δ(x_{j_{k}}, x_{j_{k}+1}) = l(x_{j_{k}+1}), and the last letter of x_{j_{k}} is ≠ 1. Then i_{k} = Δ(x_{j_{k}} , x_{j_{k}+1}) = l(x_{j_{k}+1}) = l(x_{j_{k}}). Since Δ(x_{j_{k}−1}, x_{j_{k}}) = 0 this implies that \overline{x}_{j_{k}} \ \overline{x}_{j_{k}−1} = \{a_{i_{k}}\} and therefore, by (21), that σ(a_{i_{k}}) = j_{k} = σ(b_{i_{k}}) − 1 where we have used (23) with s = k. But, by (20) and our hypothesis (iii), f(l(x_{j_{k}})) ≠ 1. Therefore f(i_{k}) > 1, and (B) follows.

Conversely, suppose that (A) holds. We then have two cases to consider:

(1) Δ(x_{j_{k}−1}, x_{j_{k}}) > 0. Then reasoning as in (i) we conclude that there is an index 1 ≤ h ≤ t, h ≠ k, such that (26) holds. By (A) it then follows that σ(b_{i_{k}}) is to the left of σ(b_{i_{h}}) in \overline{σ} and therefore that i_{k} < i_{h}. Hence, by (24) and (26),

Δ(x_{j_{k}}, x_{j_{k+1}}) = i_{k} < i_{h} = Δ(x_{j_{h}}, x_{j_{h+1}}) = Δ(x_{j_{k}−1}, x_{j_{k}}) ,

which, by (i) of Proposition 7, implies (25).

(2) Δ(x_{j_{k}−1}, x_{j_{k}}) = 0. In this case we claim that Δ(x_{j_{k}}, x_{j_{k}+1}) < l(x_{j_{k}+1}). In fact, if Δ(x_{j_{k}}, x_{j_{k}+1}) = l(x_{j_{k}+1}), then, by (2) we obtain that

\overline{x}_{j_{k}+1} \ \overline{x}_{j_{k}} = \{b_{l(x_{j_{k}+1})}\} ,  (27)
\overline{x}_{j_{k}} \ \overline{x}_{j_{k}−1} = \{a_{l(x_{j_{k}})}\} ,  (28)

and

l(x_{j_{k}+1}) = l(x_{j_{k}}) = l(x_{j_{k}−1}) + 1 .  (29)

Hence, by (27), (28), and (21), we have that σ(b_{l(x_{j_{k}+1})}) = j_{k} + 1, and

σ(a_{l(x_{j_{k}})}) = j_{k} .  (30)

But, comparing (22) (with s = k) with (27), and using (29), we have that l(x_{j_{k}}) = l(x_{j_{k}+1}) = i_{k}. Hence, by (23) and (30), σ(b_{i_{k}})−1 = j_{k} = σ(a_{i_{k}}). Therefore σ(b_{i_{k}})−1 is to the left of σ(b_{i_{k}}) in \overline{σ}, which contradicts (A). This proves our claim and (25) then follows from part (ii) of Proposition 7.

Finally, suppose that (B) holds. Then, by (23), σ(a_{i_{k}}) = j_{k}. Therefore, by (21), \overline{x}_{j_{k}} \ \overline{x}_{j_{k}−1} = \{a_{i_{k}}\}, and l(x_{j_{k}}) = i_{k}. Hence Δ(x_{j_{k}−1}, x_{j_{k}}) = 0, f(l(x_{j_{k}})) ≠ 1, and

l(x_{j_{k}+1}) = l(x_{j_{k}}) = i_{k} = Δ(x_{j_{k}}, x_{j_{k}+1}) ,

and (25) follows from (20) and part (iii) of Proposition 7.

This establishes the equivalence of (25) with either (A) or (B). Since (A) and (B) are mutually exclusive we conclude that

|{k ∈ [t] : λ(x_{j_{k}}, x_{j_{k}+1}) < λ(x_{j_{k}−1}, x_{j_{k}})}| =
|\{j ∈ \{σ(b_{i_{1}}), …, σ(b_{i_{t}})\} : j is to the left of j − 1 in \overline{σ}\}| + |S(f, σ)| .  (31)

Now, if i ∈ [m−1]\\{j_{1}, …, j_{t}\}, then, by (22), \overline{x}_{i+1}\\overline{x}_{i} = \{a_{j}\} for some j ∈ [N]_{l}, and hence Δ(x_{i}, x_{i+1}) = 0, which, by Proposition 7, implies that λ(x_{i}, x_{i+1}) > λ(x_{i−1}, x_{i}). Therefore

|D(λ(x_{0}, …, x_{m}))| = |{k ∈ [t] : λ(x_{j_{k}}, x_{j_{k}+1}) < λ(x_{j_{k}−1}, x_{j_{k}})}| .  (32)

Furthermore, since σ is a linear extension, j − 1 is to the left of j in \overline{σ} if j ∈ {2, …, m} \ {σ(b_{i_{1}}), …, σ(b_{i_{t}})}. But it is easy to see that, for j ∈ {2, …, m}, j − 1 is the descent of (\overline{σ})^{−1} if and only if j is to the left of j − 1 in \overline{σ}. Hence

|D((\overline{σ})^{−1})| = |\{j ∈ \{σ(b_{i_{1}}), …, σ(b_{i_{t}})\} : j is to the left of j − 1 in \overline{σ}\}| . (33)

Comparing (31), (32), and (33), now establishes the Theorem. □

As the next result shows, it is possible to further simplify the expression given in Theorem 14 for W (P_{z}^{(r)}; t). Corollary 2: Let r ∈ P and z ∈ F ib(r). Then

W (P_{z}^{(r)}; t) = ∑_{σ: F\overline{z} →[ρ(z)]} t^{|D((\overline{σ})^{−1})|+1} r^{|S(z)|−|A(σ)|} ((r − 1)t + 1)^{|A(σ)|} ,  (34)

where A(σ) =^{def} \{j ∈ S(z) : σ(b_{j}) = σ(a_{j}) + 1\}, \overline{σ} has the same meaning as in Theorem 14, and σ runs over all linear extensions of F\overline{z}. Proof: Fix a linear extension σ of F\overline{z}. Then, for a function f : S(z) → [r] and i ∈ [|A(σ)|] we have that |S(f; σ)| = i if and only if f is greater than 1 on exactly i elements of A(σ). Therefore there are (\begin{matrix}|A(σ)| \\ i \end{matrix}) (r − 1)^{i} r^{|S(z)\A(σ)|} such functions. Hence

∑_{f : S(z)→[r]} t^{|S(f;σ)|} = ∑_{i=0}^{|A(σ)|} (\begin{matrix}|A(σ)| \\ i \end{matrix}) (r − 1)^{i} r^{|S(z)\A(σ)|} t^{i}
= r^{|S(z)|−|A(σ)|} ((r − 1) t + 1)^{|A(σ)|}

and (34) follows from Theorem 14. □

Note that Corollary 2 shows that W (P_{z}^{(r)}; t) ∈ Q[r; t] (a fact which would also follow directly from (4) and (5), by induction on ρ(z)) and that (34) holds as a polynomial identity in both r and t. In particular, we could have used this fact to deduce Theorem 14 and Corollary 2, for r = 1, without using the result mentioned at the beginning of the proof of Theorem 14.

We can make the statement of Theorem 14 and Corollary 2 still more explicit with just one additional definition. Let π ∈ S_{M} (where S_{M} denotes the symmetric group on M elements), and write π in disjoint cycle form. We then say that π is written in increasing form if:

(i) each cycle has its smallest element first; (ii) the cycles are in increasing order of their first elements. We then denote by \overline{π} the word (actually a permutation) obtained from the increasing form of π by erasing all the parentheses. (Note that we may have \overline{π} = \overline{σ} even if π ≠ σ.) Let now π ∈ S_{M} be an involution with t 2-cycles. We then let S(π) =^{def} {j_{1}, …, j_{t}} where j_{k} denotes the position of the k-th 2-cycle of π when π is written in increasing form, for k = 1, …, t. So, for example, if π = (1)(25)(4)(87)(36) then \overline{π} = 12536478 and S(π) = \{2, 3, 5\}. Given an involution π ∈ S_{M} and a function f : S(π) → [r] we then let S(f, π) =^{def} {j ∈ S(π) : π(j) = j + 1 and f(j) > 1}. We can now restate Theorem 14 in the following form. Theorem 15: Let r ∈ P, z ∈ F ib(r), and M =^{def} ρ(z). Then

W (P_{z}^{(r)}; t) = ∑_{\{π∈S_{M} : π^{2}=1 , S(π)=S(z)\}} t^{|D((\overline{π})^{−1})|+1} ∑_{f : S(π)→[r]} t^{|S(f,π)|} .

Proof: For each linear extension σ : F\overline{z} → [M], the permutation π_{σ} that exchanges σ(a_{i_{k}}) with σ(b_{i_{k}}) for k = 1, …, t (where t =^{def} |S(z)|) and leaves fixed all the other elements of [M] is an involution of S_{M} with S(π_{σ}) = S(z) and it is easy to see that this correspondence σ → π_{σ} is a bijection. The result then follows from Theorem 14. □

We illustrate Theorem 15 with an example. Suppose r = 2 and z = 201. Then M = 4 and S(z) = {2}. Therefore

{π ∈ S_{4} : π^{2} = 1 ; S(π) = {2}} = {(1)(23)(4) , (1)(24)(3)} .

So for π = (1)(23)(4) we have that \overline{π} = (\overline{π})^{−1} = 1234, S(f, π) = ∅ if f(2) = 1, and S(f, π) = {2} if f(2) = 2. On the other hand, for π = (1)(24)(3) we have that \overline{π} = (\overline{π})^{−1} = 1243 and S(f, π) = ∅ for any f : \{2\} → [2]. Since D(1234) = ∅ and D(1243) = {3} we conclude that W (P_{201}^{(2)}; t) = t + 3t^{2}.

Reasoning in the same way as in the proof of Corollary 2 we immediately deduce the following result from Theorem 15. Corollary 3: Let r ∈ P, z ∈ F ib(r), and M =^{def} ρ(z). Then

W (P_{z}^{(r)}; t) = ∑_{\{π∈S_{M} : π^{2}=1 , S(π)=S(z)\}} t^{|D((\overline{π})^{−1})|+1} r^{c_{2}(π)−a(π)} ((r − 1) t + 1)^{a(π)}

where a(π) (respectively, c_{2}(π)) is the number of adjacent transpositions (respectively, transpositions) appearing in the disjoint cycle decomposition of π. □

We conclude this section with an application of Theorem 15 and Corollary 3. In [20] Stanley defines, for each M ∈ P, some polynomials W_{M}(r, t) associated to F ib(r) (see the paragraph preceding Prop.3.2 in [20]). Among the various properties derived in [20] for the W_{M}(r, t)’s is a combinatorial interpretation of the coefficients of W_{M}(1, t), and Stanley asks whether a similar combinatorial interpretation can be given for r ≥ 2. Now, there is a very simple relationship between the W_{M}(r, t)’s and the polynomials W (P_{z}^{(r)}; t) studied in this section. Indeed, it follows immediately from our definitions and those in [20] that

W_{M}(r, t) = ∑_{{z∈F ib(r) : ρ(z)=M}} W (P_{z}^{(r)}; t).  (35)

Therefore, from Theorem 15 we obtain the following combinatorial interpretation of the polynomials W_{M}(r, t), which generalizes Stanley’s combinatorial interpretation (see Prop.3.2 in [20]). Theorem 16: Let r, M ∈ P and let W_{M}(r, t) be the polynomials defined in (35). Then

W_{M}(r, t) = ∑_{\{π∈S_{M} : π^{2}=1\}} t^{|D((\overline{π})^{−1})|+1} ∑_{g: [c(π)]→[r]} t^{|S(f,π)|} ,  (36)

where c(π) is the number of cycles of π, f =^{def} g|_{S(π)}, and S(f, π) has the same meaning as in Theorem 15. Proof: Fix an involution π ∈ S_{M} and let g : [c(π)] → [r]. Let f =^{def} g|_{S(π)} and

z =^{def} z_{1} … z_{c(π)} ∈ F ib(r) be defined by

z_{i} =^{def} \{ \begin{matrix}0 , & if i ∈ S(π), \\ g(i) , & otherwise. \end{matrix}

Then f : S(π) → [r], ρ(z) = c(π) + |S(π)| = M, and S(z) = S(π). It is clear that this is a bijection between {g : [c(π)] → [r]} and {f : S(π) → [r]} × {z ∈ F ib(r) : ρ(z) = M, S(z) = S(π)} and so the result follows from (35) and Theorem 15. □

Reasoning as in the proof of Corollary 2 we deduce the following equivalent formulation of Theorem 16, which is also the last result of this section. Corollary 4: Let r, M ∈ P and let W_{M}(r, t) be the polynomials defined in (35). Then

W_{M}(r, t) = ∑_{\{π∈S_{M} : π^{2}=1\}} t^{|D((\overline{π})^{−1})|+1} r^{c(π)−a(π)} ((r − 1) t + 1)^{a(π)} ,

where c(π) (respectively, a(π)) has the same meaning as in Theorem 16 (respectively, Corollary 3). □

Before closing this section we should mention that it is possible to prove Theorem 14 (and hence all its consequences) combinatorially for r = 1 by carrying out (with some minor modifications) the construction made in this section. However, this would have lengthened the statements and proofs of many of the results of this section and we felt that it was unnecessary. The reader should also note that, by Theorem 11 and its consequences, Theorems 14 through 16 and Corollaries 2 through 4 remain valid if we substitute “P_{z}^{(r)}” with “Q_{z}^{(r)}” and “F ib(r)” with “Z(r)” throughout their statements. However, the combinatorial construction carried out in this section does not seem to generalize easily to Z(r).

6 Conjectures and Open Problems

There are several lines of possible further investigation that are suggested by the present work. In particular, we may ask whether the results of §3 generalize to other intervals [x, y] of F ib(r) when x ≠ ˆ0. We may also ask if similar results can be obtained for other general classes of posets, in particular differential posets.

Finally, Stanley asks in [20] whether the polynomials W_{M}(r, t) defined by (35) have any special properties. In this respect, we feel that the following statement is true. Conjecture 3: Fix r, M ∈ P then the polynomial W_{M}(r, t) defined by (35) has only real zeros. In particular W_{M}(r, t) is log-concave and unimodal.

This conjecture has been verified for r = 1 and M ≤ 20 and for r = 2 and M ≤ 21, but is open even for the unimodality statement and for r = 1. It is possible that the results obtained in this paper (in particular Theorem 8) together with equation (35) may be useful in solving the above conjecture. While we are unable to prove Conjecture 3, we can prove that the polynomials W_{M}(r, t) do have some special property. In fact, we have the following result. For n ∈ N, we denote by H_{n}(x) the n-th Hermite polynomial (see, e.g., [6, p.50]), for the definition of the Hermite polynomials). Proposition 8 Let M ∈ P and W_{M}(r, t) be the polynomial defined by (35). Then

W_{M}(−2x^{2}, 1) = (−x)^{M} H_{M}(x) .  (37)

In particular, W_{M}(x, 1) has only real zeros. Proof: Note first that it follows from Corollary 4 (or from eq. (16) of [20]) that, for N ∈ P,

W_{N}(r, 1) = ∑_{{π∈S_{N} : π^{2}=1}} r^{c(π)} .  (38)

Hence, by [6, §3.3],

∑_{N≥0} W_{N}(x, 1)\frac{t^{N}}{N!} = exp (x t + x \frac{t^{2}}{2} ) ,

and (37) follows from the usual definition of the Hermite polynomials [6, p.50]. The second statement follows from (37) and the well known fact that orthogonal polynomials have only real zeros (see, e.g., [21]). □

The fact that the polynomial on the RHS of (38) has only real zeros is similar to some of the results in [4] and [5] where some polynomials, obtained by enumerating certain sets of permutations with respect to the number of excedances, are studied. We have no idea, however, of whether this can be generalized to other sets of permutations.

References

[1] A. Björner, A. Garsia, and R. Stanley, An introduction to Cohen-Macaulay partially ordered sets, in I. Rival, ed., Ordered Sets, Reidel, Dordrecht/Boston, 1982, pp.583-615.

[2] F. Brenti, Unimodal, Log-concave and Pólya Frequency Sequences in Combinatorics, Ph.D. Thesis, June 1988, Massachusetts Institute of Technology.

[3] F. Brenti, Unimodal, log-concave, and Pólya Frequency sequences in Combinatorics, Memoirs Amer. Math. Soc., no. 413 (1989).

[4] F. Brenti, Unimodal polynomials arising from symmetric functions, Proc. Amer. Math. Soc., 108 (1990), 1133-1141.

[5] F. Brenti, Unimodality, excedances, and symmetric functions, preprint.

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

[7] P. Edelman, The Zeta Polynomial of a Partially Ordered Set, Ph.D. Thesis, June 1980, Massachusetts Institute of Technology.

[8] P. Edelman, Zeta Polynomials and the Möbius Function, Europ. J. Combinatorics, 1 (1980), 335-340.

[9] A. Edrei, Proof of a conjecture of Schoenberg on the generating function of a totally positive sequence, Canad. J. Math., 5 (1953), 86-94.

[10] G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, 2nd ed., Cambridge Univ. Press, Cambridge, 1952.

[11] S. Karlin, Total Positivity, vol.1, Stanford University Press, 1968.

[12] J. Neggers, Representations of finite partially ordered sets, J. Combin. Inform. System Sci., 3 (1978), 113-133.

[13] B. Sagan and Y. Yeh, Probabilistic algorithms for trees, Fibonacci Quart., 27 (1989), 201-208.

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

[15] R. Stanley, Finite lattices and Jordan-Holder sets, Algebra Universalis, 4 (1974), 361-371.

[16] R. Stanley, The Fibonacci lattice, Fibonacci Quart., 13 (1975), 215-232.

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

[18] R. Stanley, Differential Posets, J. Amer. Math. Soc., 1 (1988), 919-961.

[19] R. Stanley, Log-concave and unimodal sequences in Algebra, Combinatorics and Geometry, Annals of the New York Academy of Sciences, 576 (1989), 500-534.

[20] R. Stanley, Further Combinatorial Properties of two Fibonacci lattices, Europ. J. Combinatorics, 11 (1990), 181-188.

[21] G. Szegö, Orthogonal Polynomials, rev. ed., Amer. Math. Soc. Coll. Pub., vol.23, New York, 1959.

[22] D. Wagner, Enumerative Combinatorics of partially ordered sets, and total positivity of Hadamard products, Ph.D. Thesis, 1989, Massachusetts Institute of Technology.

[23] D. Wagner, The partition polynomial of a finite set system, to appear in J. Combin. Theory Ser. A.