Séminaire Lotharingien de Combinatoire 51 (2004), Article B51b

Enumerative properties of generalized associahedra

Frédéric Chapoton

Institut Girard Desargues, Université Claude Bernard (Lyon 1) 21 Avenue Claude Bernard F-69622 Villeurbanne Cedex, FRANCE

Abstract. Some enumerative aspects of the fans called generalized associahedra, introduced by S. Fomin and A. Zelevinsky in their theory of cluster algebras, are considered in relation with a bicomplex and its two spectral sequences. A precise enumerative relation with the lattices of generalized noncrossing partitions is conjectured and some evidence is given.

Keywords and Phrases: Generalized associahedra, noncrossing partition, f-vector

0 Introduction

In their work on cluster algebras [9, 10, 11], S. Fomin and A. Zelevinsky have introduced simplicial fans associated to finite crystallographic root systems. These fans are associated with convex polytopes called generalized associahedra [8] and have been shown to be related to classical combinatorial objects such as triangulations, noncrossing and nonnesting partitions and Catalan numbers. The lattice of noncrossing partitions, which was defined first for symmetric groups by G. Kreweras [12], has been recently generalized to all finite Coxeter groups [4, 5, 6]. Surveys of its properties can be found in [14] and [18]. The aim of the present article is twofold. First, a refined enumerative invariant, called the F -triangle, of the fan associated to a root system is introduced and an inductive procedure is given for its computation. The F -triangle is then related to a simple combinatorial bicomplex and its spectral sequences. The second theme is a conjecture which relates, through an explicit change of variables, the F -triangle of a root system and a bivariate polynomial defined in terms of the noncrossing partition lattice for the corresponding Weyl group. Considerable evidence is given for this conjecture. The final section contains the computation of the F -triangle for the root systems of type A and B, using arguments based on hypergeometric functions. Thanks to C. Krattenthaler for his help with hypergeometric identities.

1 The simplicial fans of clusters

Let Φ be the root system associated to an irreducible Dynkin diagram X_{n} of finite type and rank n. Thus X_{n} is among the Killing-Cartan list A_{n}, B_{n}, C_{n}, D_{n} or E_{6}, E_{7}, E_{8}, F_{4}, G_{2}. Let I be the underlying set of the Dynkin diagram and {α_{i}}_{i∈I} be the set of simple positive roots in Φ. Let us recall briefly the construction by S. Fomin and A. Zelevinsky of the simplicial fan Δ(Φ). Let Φ_{≥−1} be the union of the set of negative simple roots {−α_{i}}_{i∈I} with the set Φ_{>0} of positive roots. Elements of Φ_{≥−1} are called almost positive roots. A symmetric binary relation on Φ_{≥−1} called compatibility was defined in [11]. The following is [11, Theorem 1.10].

Theorem 1 The cones spanned by subsets of mutually compatible elements in Φ_{≥−1} define a complete simplicial fan Δ(Φ).

From now on, cones of the fan Δ(Φ) will be identified with their spanning set of mutually compatible elements of Φ_{≥−1}. The cones of dimension n of Δ(Φ) are in bijection with maximal mutually compatible subsets of Φ_{≥−1}, which are called clusters. The cones of dimension 1 of Δ(Φ) are in bijection with Φ_{≥−1} and will be called roots. A cone of Δ(Φ) is called positive if it is spanned by positive roots and non-positive else. One can define a fan Δ(Φ) also for a non-irreducible root system Φ, as the product of the fans associated to its irreducible components. Let P be the closed cone spanned by simple positive roots. This is not a cone of Δ(Φ) in general.

Proposition 1 The cone P is exactly the union of all positive cones of Δ(Φ).

Proof. Each positive cone is spanned by positive roots, hence is contained in P. Conversely, as the fan is complete, P is contained in the union of all cones whose interior meet P. The interior of a non-positive cone does not meet P as it consists of vectors with at least one negative coordinate in the basis of simple roots. Hence P is contained in the union of all positive cones.

As a special case of the description of the fan Δ(Φ) in [11], the following Lemma holds.

Lemma 1 The span of negative simple roots is a cone of Δ(Φ)

We recall [11, Proposition 3.6] for later use.

Proposition 2 For every subset J ⊆ I, the correspondence c ↦ c \ {−α_{i}}_{i∈J} is a bijection between cones of Δ(Φ) whose negative part is J and positive cones of Δ(Φ(I \ J)), where Φ(I \ J) is the restriction of the root system Φ to I \ J.

2 The F -triangle and the bicomplex of cones

Let us define the F -triangle by its generating function

F (Φ) = F (x, y) = ∑_{k=0}^{n} ∑_{ℓ=0}^{n} f_{k,ℓ}x^{k}y^{ℓ},  (1)

where f_{k,ℓ} is the cardinality of the set C_{k,ℓ} of cones of Δ(Φ) spanned by exactly k positive roots and ℓ negative simple roots. The coefficient f_{k,ℓ} vanishes if k + ℓ > n, hence the name triangle.

Proposition 3 The F -triangle has the following properties.

1. If Φ and Φ′ are two root systems, one has F (Φ × Φ′) = F (Φ) × F (Φ′).

2. If Φ is an irreducible root system on I, then one has

∂_{y}F (Φ(I)) = ∑_{i∈I} F (Φ(I \ {i})),  (2)

where Φ(I \ {i}) is the restriction of the root system Φ to I \ {i}.

Proof. The first statement is obvious. The proof of the second statement is by double counting of the sets of pairs

{(i, c) | −α_{i} ∈ c and c ∈ C_{k,ℓ}},  (3)

for all k and ℓ. Let us fix k and ℓ. On the one hand, the cardinality of this set is just ℓf_{k,ℓ} by definition of C_{k,ℓ}. On the other hand, by [11, Proposition 3.5 (3)], the cardinality is given by the sum over i ∈ I of f_{k,ℓ−1}^{i} where f^{i} is the F -triangle for the root system induced on I \ {i}. This gives the equality

ℓf_{k,ℓ} = ∑_{i∈I} f_{k,ℓ−1}^{i},  (4)

which proves the second assertion of the proposition.

The usual f-vector is given by the generating series

f(x) = ∑_{k=0}^{n} f_{k}x^{k} = F (x, x),  (5)

where f_{k} is the number of cones of dimension k. The following is [11, Proposition 3.7].

Proposition 4 The f-vector has the following properties.

1. If Φ and Φ′ are two root systems, one has f(Φ × Φ′) = f(Φ) × f(Φ′).

2. If Φ is an irreducible root system on I, then one has

∂_{x}f(Φ(I)) = \frac{h + 2}{2} ∑_{i∈I} f(Φ(I \ \{i\})),  (6)

where h is the Coxeter number of Φ.

Together Proposition 3 and Proposition 4 are sufficient to compute simultaneously the F -triangle and the f-vector by induction on the cardinality of I, using (5). For example, the A_{3} f-vector is (1, 9, 21, 14) and the A_{3} F -triangle is presented below, with k = 0 to 3 from top to bottom and ℓ = 0 to 3 from left to right.

[\begin{matrix}1 & 3 & 3 & 1 \\ 6 & 8 & 3 \\ 10 & 5 \\ 5 \end{matrix}]  (7)

This matrix corresponds to the pictures in Figure 1 (see the end of the paper), through the description of clusters of type A by triangulations of a regular polygon given by Fomin and Zelevinsky in [11]. The F -triangle has a nice symmetry property, which is a refined version of the classical Dehn-Sommerville equations for complete simplicial fans.

Proposition 5 One has

F (x, y) = (−1)^{n}F (−1 − x, −1 − y).  (8)

Proof. The proof is just an adaptation of the original proof of the Dehn-Sommerville equations (see [3, p. 212-213]), taking care of the two different kind of half-edges of the fan. The proposition is equivalent to the set of equations

f_{i,j} = ∑_{k,ℓ}(−1)^{n+k+ℓ}\binom{k}{i}\binom{ℓ}{j}f_{k,ℓ},  (9)

for all i, j. Let us now fix i and j and compute f_{i,j}. First, it is given by

f_{i,j} = ∑_{c∈C_{i,j}} 1.  (10)

Then using Lemma 2, this is rewritten as

∑_{c∈C_{i,j}} ∑_{c⊆d}(−1)^{n+dim(d)}.  (11)

Exchanging summations, one obtains

∑_{k,ℓ}(−1)^{n+k+ℓ} ∑_{d∈C_{k,ℓ}} ∑_{{c⊆d \atop c∈C_{i,j}}} 1.  (12)

Enumerative properties of generalized associahedra 5

As the fan is simplicial, this is

∑_{k,ℓ}(−1)^{n+k+ℓ}\binom{k}{i}\binom{ℓ}{j}f_{k,ℓ}.  (13)

The proposition is proved. The following lemma is classical. It follows from the fact that the link of a simplex in a homology sphere is again a homology sphere, see [3, p. 214]. Lemma 2 Let c be a cone in a complete simplicial fan of dimension n. Then

∑_{c⊆d}(−1)^{n+dim(d)} = 1.  (14)

Let us now introduce two specializations of the F -triangle. The positive f^{+}-vector is given by the generating series

f^{+}(x) = ∑_{k=0}^{n} f_{k}^{+}x^{k} = F (x, 0),  (15)

where f_{k}^{+} = f_{k,0} is the number of positive cones of dimension k. The natural f^{♮}-vector is given by the generating series

f^{♮}(x) = ∑_{k=0}^{n} f_{k}^{♮}x^{k} = F (x, −1).  (16)

Its interpretation will be given later in Proposition 8. The symmetry obtained in Proposition 5 has the following consequences. Corollary 1 The f^{+}-vector and f^{♮}-vector determine each other. One has

F (x, 0) = (−1)^{n}F (−1 − x, −1).  (17)

Corollary 2 One has

F (0, x) = (−1)^{n}F (−1, −1 − x) = (x + 1)^{n}.  (18)

Equivalently, one has F (−1, y) = y^{n}. Proof. By Lemma 1, each subset of the set of negative simple roots is a cone of Δ(Φ).

Let us define a bicomplex on cones and study its two spectral sequences. This bicomplex is essentially the complex associated to the simplicial set defined by the fan, where the differential is split according to the two kinds of elements of Φ_{≥−1}. In the unital exterior algebra generated over ℤ by the set Φ_{≥−1}, consider the linear span D of the monomials associated to the cones of the fan Δ(Φ). The simplicial differential of a monomial in D is defined by

d(α_{1} ∧ α_{2} ∧ ⋯ ∧ α_{k}) = ∑_{ℓ=1}^{k}(−1)^{ℓ−1}α_{1} ∧ α_{2} ∧ … α̂_{ℓ} ⋯ ∧ α_{k},  (19)

where α̂_{ℓ} means that α_{ℓ} has been removed. This gives a complex (D, d) computing the reduced homology of a sphere. The differential d is the sum of two maps d_{+} and d_{−} which correspond respectively to the removal of a positive root or a negative simple root in a monomial. It is clear that each of d_{+} and d_{−} is a differential. This defines a bicomplex structure on D when bigraded by the number of positive roots and negative simple roots.

Proposition 6 The spectral sequence of D starting with d_{+} degenerates at first step.

Proof. The complex (D, d_{+}) decomposes as a direct sum of complexes D_{S_{−}} according to the fixed negative part S_{−}. If this negative part S_{−} is not the full set {−α_{i}}_{i∈I}, the subcomplex D_{S_{−}} has no homology. To prove this, it is enough to consider the complex of positive cones for the differential d_{+} for all root systems, as the subcomplex D_{S_{−}} with fixed negative part S_{−} is isomorphic to the complex of positive cones for a smaller root system by Proposition 2. The complex of positive cones for the differential d_{+} has no homology because it computes the reduced homology of the contractible simplicial complex P, by Proposition 1.

Proposition 7 The spectral sequence of D starting with d_{−} degenerates at second step.

Proof. The complex (D, d_{−}) decomposes as a direct sum of complexes D_{S_{+}} according to the fixed positive part S_{+} of pairwise compatible positive roots. Let N(S_{+}) be the set of negative simple roots compatible with all roots of S_{+}. Then the complex D_{S_{+}} is isomorphic to the tensor product over the set N(S_{+}) of contractible complexes of the following shape

0 ⟶ ℤ ⟶^{≃} ℤ ⟶ 0.  (20)

Hence either N(S_{+}) is empty and d_{−} vanishes on D_{S_{+}}, or the subcomplex D_{S_{+}} has no homology. Therefore the homology of (D, d_{−}) is concentrated in positive cones and is given exactly by positive cones which cannot be extended with negative simple roots. This implies the collapsing of the spectral sequence at second step.

A positive cone which is not a subcone of a non-positive cone is called a natural cone.

Proposition 8 The number of natural cones of dimension k is f_{k}^{♮}.

Proof. The natural f^{♮}-vector is by definition the Euler characteristic of the complex (D, d_{−}). By the proof of Proposition 7, the homology of d_{−} is concentrated in degree 0 and has dimension given by the numbers of natural cones.

The first step of the spectral sequence starting with d_{−} is therefore a complex on natural cones. Its homology is concentrated in degree n.

3 The Lattice of noncrossing partitions

The lattice L_{W} of noncrossing partitions associated to a finite Coxeter group W has been introduced independently in [4, 5, 6]. The surveys [14, 18] give a good feeling of its importance in different parts of mathematics. Let us recall shortly its definition. Let n be the rank of W. Let S = {s_{1}, …, s_{n}} be the set of simple reflections in W. Let T be the set of all reflections in W. As W is also generated by T, one can define a length function ℓ_{T} on W with respect to the generators in T. Using this length function, a partial order is defined on W as follows. Let v and w be two elements of W. Then v ≤ w if and only if there exists t_{1}, …, t_{k} in T such that w = t_{1} … t_{k}v and ℓ_{T} (w) = ℓ_{T} (v) + k. Maximal elements for this partial order are exactly Coxeter elements of W, i.e. products in some order of the set S of simple reflections. The group W acting by conjugation gives automorphisms of this partial order, as the set T of all reflections is stable by conjugation. As all Coxeter elements are conjugated, one can define, up to isomorphism, the noncrossing partition lattice L_{W} to be the interval between the unit and a Coxeter element for this partial order. From this description, one can see that the noncrossing partition poset associated to the product of two Coxeter groups is isomorphic to the product of the noncrossing partition posets associated to these groups. It is known that one recovers for type A the usual noncrossing partition lattices introduced by Kreweras [12], which are by now classical objects in combinatorics [18, 14]. In type B, one recovers the noncrossing partition lattices of type B introduced by Reiner [17]. We shall now recall some properties of L_{W}. The poset L_{W} is a finite lattice which is graded of rank n and self-dual. Let ˆ0 and ˆ1 be the minimum and maximum elements of L_{W}. Let μ be the Möbius function of L_{W}. Then the lattice L_{W} has the following invariants.

Proposition 9 The Zeta polynomial of L_{W} is

Z_{W} (X) = ∏_{i=1}^{n} \frac{hX − e_{i} + 1}{e_{i} + 1}.  (21)

The cardinality of L_{W} is

#L_{W} = ∏_{i=1}^{n} \frac{h + e_{i} + 1}{e_{i} + 1},  (22)

and the Möbius number of L_{W} is

μ(ˆ0, ˆ1) = (−1)^{n} ∏_{i=1}^{n} \frac{h + e_{i} − 1}{e_{i} + 1},  (23)

where h is the Coxeter number and e_{1}, …, e_{n} are the exponents of W. The number of maximal chains of L_{W} is h^{n}n!/|W |.

This proposition follows from the known formulas for the Zeta polynomial of L_{W} in the classical cases [2, 17] and from the computation of the Zeta polynomials in the exceptional cases by V. Reiner [16]. The statements about cardinality, Möbius numbers and maximal chains follow from the knowledge of the Zeta polynomial. The cardinality part of the Proposition can also be checked from the data in [15]. To find a uniform proof of Proposition 9 is an interesting open problem. Let rk be the rank function of L_{W}. Consider the following generating function for Möbius numbers of intervals in L_{W} according to the ranks:

M(x, y) = ∑_{a≤b} μ(a, b)x^{rk(b)}y^{rk(a)}.  (24)

This generating function is called the M-triangle for W. Let us assume from now on that W is the Weyl group of a crystallographic root system Φ. Here is the main Conjecture.

Conjecture 1 The F -triangle for Φ and the M-triangle for W are related by the following invertible transformation:

(1 − y)^{n}F (\frac{x + y}{1 − y} , \frac{y}{1 − y}) = M(−x, −y/x).  (25)

Let us note that the left-hand side of (25) can be rewritten using Proposition 5 as

(y − 1)^{n}F (\frac{x + 1}{y − 1}, \frac{1}{y − 1}).  (26)

It is not hard to check by hand that Conjecture 1 holds for root systems of small ranks. It is probably possible to prove it for classical types using the combinatorial descriptions of the noncrossing partition lattices [2, 17] and of the generalized associahedra [11]. Using a computer, one could check it for most of the exceptional types. Rather than doing that, we prefer to give now conceptual evidence for Conjecture 1.

3.1 First Evidence

Let us consider the value of (25) at x = 0. The left-hand side becomes (1 − y)^{n}F (\frac{y}{1−y}, \frac{y}{1−y}), which is nothing but the h-vector of the simplicial fan Δ(Φ). The right-hand side is

∑_{a} y^{rk(a)},  (27)

which is known to coincide with the h-vector for all root systems, see [1, 2, 4]. These h-vectors are sometimes called the generalized Narayana numbers. Note that there is no uniform proof of this fact known so far.

3.2 Second evidence

Let us compute the coefficient of x^{n} in the constant term of (25) with respect to y. On the left-hand side, this is the number f_{n,0} of positive clusters, which is known by [11, Proposition 3.9] to be given by

∏_{i=1}^{n} \frac{h + e_{i} − 1}{e_{i} + 1}.  (28)

On the right-hand-side, one gets (−1)^{n} times the Möbius number μ(ˆ0, ˆ1), which is given by (23).

3.3 Third evidence

It is known that the lattice L_{W} is self-dual [4, §2.3]. This fact implies the following symmetry of the M-triangle:

M(x, y) = (xy)^{n}M(1/y, 1/x).  (29)

Claim 1 Assuming Conjecture 1, this symmetry is equivalent to Proposition 5.

Indeed, the symmetry of the M-triangle is equivalent to

M(−x, −y/x) = y^{n}M(−x/y, −1/x).  (30)

Now applying Conjecture 1 to the right-hand side, one gets (26), which is the same as (25) thanks to Proposition 5. This proves the claim.

3.4 Fourth evidence

Consider the value of (25) at x = −1. The left-hand side is computed using (26) to be

(y − 1)^{n}F (0, \frac{1}{y − 1}).  (31)

But this is just y^{n} by Corollary 2. That the right-hand side is also y^{n} is a standard property of the M-triangle for graded posets of rank n with ˆ0 and ˆ1.

3.5 Fifth evidence

By Proposition 3, the F -triangle has a multiplicative behavior with respect to product of root systems. It is classical that the M-triangle is also multiplicative for the product of lattices. These multiplicative behaviors are compatible with Formula (25).

4 Computation for type A

In this section, the F -triangle is computed for root systems of type A. This can serve as a first step towards the proof of Conjecture 1 in type A. Before entering into details of type A, let us say a word on the other types. Type B is treated in the next section and is known to coincide with type C. In type D, there is a slightly more complicated conjectural formula for the F -triangle that we will not consider in the present article. Exceptional cases have been computed using Prop. 3 and Prop. 4. As the results have no special meaning, they are not printed here. Let us first recall the known expression for the f-vector in type A [13, 19].

Proposition 10 The f-vector for A_{n} is given by

∑_{k=0}^{n} \frac{1}{k + 1}\binom{n}{k}\binom{n + k + 2}{k}x^{k}.  (32)

Let us define a generating function for f-vectors of type A. First the f-vector for A_{n} is made homogeneous of degree n using a new variable z, then all homogenized f-vectors are added. Let

f = ∑_{m=0}^{∞} ∑_{k=0}^{∞} \frac{1}{k + 1}\binom{m + k}{k}\binom{2k + m + 2}{k}x^{k}z^{m}.  (33)

Our aim is now to prove the following Proposition.

Proposition 11 The F -triangle for A_{n} is given by

∑_{k=0}^{n} ∑_{ℓ=0}^{n} \frac{ℓ + 1}{k + ℓ + 1}\binom{n}{k + ℓ}\binom{n + k}{n}x^{k}y^{ℓ}.  (34)

Let us define similarly a generating function for the functions (34). Let

F = ∑_{ℓ=0}^{∞} ∑_{m=0}^{∞} ∑_{k=0}^{∞} \frac{ℓ + 1}{k + ℓ + 1}\binom{k + ℓ + m}{k + ℓ}\binom{2k + ℓ + m}{k + ℓ + m}x^{k}y^{ℓ}z^{m}.  (35)

Recall that Proposition 3 and Formula (5) give a recursion for computing the F - triangle assuming that the f-vector is known. In type A, the induction given by Proposition 3 is easily seen to be equivalent to the equation ∂_{y}F = F^{2}. Hence, to prove Proposition 11, it is enough to prove that ∂_{y}F = F^{2} and that the substitution of y by x in F is f. This is done in the next two Lemmas.

Lemma 3 The partial derivative ∂_{y}F equals F^{2}.

Proof. Let us fix k, ℓ, m and consider the coefficient of x^{k}y^{ℓ}z^{m} in F^{2}. It is given by

∑_{k_{1},ℓ_{1},m_{1}} \frac{(ℓ_{1} + 1) (2k_{1} + ℓ_{1} + m_{1})!}{(k_{1} + ℓ_{1} + 1)! m_{1}! k_{1}!} \frac{(ℓ − ℓ_{1} + 1) (2k − 2k_{1} + ℓ − ℓ_{1} + m − m_{1})!}{(k − k_{1} + ℓ − ℓ_{1} + 1)! (m − m_{1})! (k − k_{1})!}.

(36)

One can first do the summation with respect to m_{1} using the Chu-Vandermonde identity. The result is

\binom{2k + ℓ + m + 1}{m} ∑_{k_{1},ℓ_{1}} \frac{ℓ_{1} + 1}{2k_{1} + ℓ_{1} + 1}\binom{2k_{1} + ℓ_{1} + 1}{k_{1}}

· \frac{ℓ − ℓ_{1} + 1}{2k − 2k_{1} + ℓ − ℓ_{1} + 1}\binom{2k − 2k_{1} + ℓ − ℓ_{1} + 1}{k − k_{1}}. (37)

Then using a result of Carlitz [7, Theorem 6, Formula (5.14)] with parameters a = 2, c = 1, α = α′ = 1, b = 0, d = 0, β = β′ = −1, the remaining double sum can be computed. The result is

\binom{2k + ℓ + m + 1}{m}(−1)^{ℓ} \frac{−2ℓ − 4}{(2k + ℓ + 2)(−2)}\binom{2k + ℓ + 2}{k}\binom{−2}{ℓ}.  (38)

This can be rewritten as

\frac{(2k + ℓ + m + 1)! (ℓ + 2)(ℓ + 1)}{m! k! (k + ℓ + 2)!},  (39)

which is exactly the coefficient of x^{k}y^{ℓ}z^{m} in ∂_{y}F. The Lemma is proved.

Lemma 4 The substitution of y by x in F equals f.

Proof. Let us fix K, m and compute the coefficient of x^{K}z^{m} in this substituted F. This is given by

\frac{1}{(K + 1)! m!} ∑_{ℓ} \frac{(ℓ + 1)(2K − ℓ + m)!}{(K − ℓ)!}.  (40)

This is rewritten as

\frac{(K + m)!}{(K + 1)! m!} ∑_{ℓ} \binom{ℓ + 1}{ℓ}\binom{2K + m − ℓ}{K − ℓ}.  (41)

Using the Chu-Vandermonde identity, this equals

\frac{(K + m)!}{(K + 1)! m!}\binom{2K + m + 2}{K},  (42)

which in turn is equal to

\frac{(K + m)! (2K + m + 2)!}{m! K! (K + 1)! (K + m + 2)!}.  (43)

This is exactly the coefficient of x^{K}y^{ℓ} in f. The Lemma is proved.

5 Computation for type B

In this section, the F -triangle is computed for root systems of type B. Let us first recall the known expression for the f-vector in type B [19].

Proposition 12 The f-vector for B_{n} is given by

∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k}x^{k}.  (44)

Let us define a generating function for f-vectors of type B as we did before for type A. By convention, B_{0} is A_{0} and B_{1} is A_{1}. Let

g = ∑_{m=0}^{∞} ∑_{k=0}^{∞} \binom{m + k}{k}\binom{2k + m}{k}x^{k}z^{m}.  (45)

Our aim is now to prove the following Proposition.

Proposition 13 The F -triangle for B_{n} is given by

∑_{k=0}^{n} ∑_{ℓ=0}^{n} \binom{n}{k + ℓ}\binom{n + k − 1}{n − 1}x^{k}y^{ℓ}.  (46)

Let us define similarly a generating function for the functions (46). Let

G = ∑_{ℓ=0}^{∞} ∑_{m=0}^{∞} ∑_{k=0}^{∞} \binom{k + ℓ + m}{k + ℓ}\binom{2k + ℓ + m − 1}{k + ℓ + m − 1}x^{k}y^{ℓ}z^{m}.  (47)

Recall again that Proposition 3 and Formula (5) give a recursion for computing the F -triangle assuming that the f-vector is known. In type B, the induction given by Proposition 3 is easily seen to be equivalent to the equation ∂_{y}G = F G. Hence, to prove Proposition 13, it is enough to prove that ∂_{y}G = F G and that the substitution of y by x in G is g. This is done in the next two Lemmas.

Lemma 5 The partial derivative ∂_{y}G equals F G.

Proof. The proof is very similar to the type A case and will be more sketchy. Let us fix k, ℓ, m and consider the coefficient of x^{k}y^{ℓ}z^{m} in F G. It is given by

∑_{k_{1},ℓ_{1},m_{1}} \frac{(ℓ_{1} + 1)(2k_{1} + ℓ_{1} + m_{1})!}{(k_{1} + ℓ_{1} + 1)! m_{1}! k_{1}!}

· \frac{(k − k_{1} + ℓ − ℓ_{1} + m − m_{1})(2k − 2k_{1} + ℓ − ℓ_{1} + m − m_{1} − 1)!}{(k − k_{1} + ℓ − ℓ_{1})! (m − m_{1})! (k − k_{1})!}. (48)

Let us consider separately the summation of factors depending on m_{1} with respect to m_{1}:

∑_{m_{1}}(k − k_{1} + ℓ − ℓ_{1} + m − m_{1})(2k_{1} + ℓ_{1} + m_{1})!

· \frac{(2k − 2k_{1} + ℓ − ℓ_{1} + m − m_{1} − 1)!}{m_{1}! (m − m_{1})!}. (49)

This sum can be split in two terms:

∑_{m_{1}} \frac{(k − k_{1} + ℓ − ℓ_{1})(2k_{1} + ℓ_{1} + m_{1})! (2k − 2k_{1} + ℓ − ℓ_{1} + m − m_{1} − 1)!}{m_{1}! (m − m_{1})!}

+ ∑_{m_{1}} \frac{(2k_{1} + ℓ_{1} + m_{1})! (2k − 2k_{1} + ℓ − ℓ_{1} + m − m_{1} − 1)!}{m_{1}! (m − m_{1} − 1)!}. (50)

Rewriting the summations with binomial coefficients gives

(k − k_{1} + ℓ − ℓ_{1}) (2k_{1} + ℓ_{1})! (2k − 2k_{1} + ℓ − ℓ_{1} − 1)!

× ∑_{m_{1}} \binom{2k_{1} + ℓ_{1} + m_{1}}{m_{1}}\binom{2k − 2k_{1} + ℓ − ℓ_{1} + m − m_{1} − 1}{m − m_{1}}

+ (2k_{1} + ℓ_{1})! (2k − 2k_{1} + ℓ − ℓ_{1})!

× ∑_{m_{1}} \binom{2k_{1} + ℓ_{1} + m_{1}}{m_{1}}\binom{2k − 2k_{1} + ℓ − ℓ_{1} + m − m_{1} − 1}{m − m_{1} − 1}. (51)

Using the Chu-Vandermonde identity for each of these two terms gives

(k − k_{1} + ℓ − ℓ_{1}) (2k_{1} + ℓ_{1})! (2k − 2k_{1} + ℓ − ℓ_{1} − 1)!\binom{2k + ℓ + m}{m}

+ (2k_{1} + ℓ_{1})! (2k − 2k_{1} + ℓ − ℓ_{1})!\binom{2k + ℓ + m}{m − 1}. (52)

Now it is time to plug this result into the full summation (48). Let us do this separately for the the two terms of (52). The first term of (52) plugged into (48) gives

\binom{2k + ℓ + m}{m} ∑_{k_{1},ℓ_{1}} \binom{2(k − k_{1}) + (ℓ − ℓ_{1}) − 1}{k − k_{1}} \frac{ℓ_{1} + 1}{2k_{1} + ℓ_{1} + 1}\binom{2k_{1} + ℓ_{1} + 1}{k_{1}}.

(53)

Using another formula of Carlitz [7, (5.15)] with parameters a = 2, c = 1, b = 0, d = 0, α = 0, β = 0, α′ = 1, β′ = −1, this becomes

\binom{2k + ℓ + m}{m}\binom{2k + ℓ}{k}(ℓ + 1).  (54)

The second term of (52) plugged into (48) gives

\binom{2k + ℓ + m}{m − 1} ∑_{k_{1},ℓ_{1}} \binom{2(k − k_{1}) + (ℓ − ℓ_{1})}{k − k_{1}} \frac{ℓ_{1} + 1}{2k_{1} + ℓ_{1} + 1}\binom{2k_{1} + ℓ_{1} + 1}{k_{1}}. (55)

Using again [7, (5.15)] with parameters a = 2, c = 1, b = 0, d = 0, α = 1, β = 0, α′ = 1, β′ = −1, this becomes

\binom{2k + ℓ + m}{m − 1}\binom{2k + ℓ + 1}{k}(ℓ + 1).  (56)

Summing (54) and (56) gives

\frac{(ℓ + 1)(2k + ℓ + m)! (k + ℓ + m + 1)}{k! m! (k + ℓ + 1)!}.  (57)

This is exactly the coefficient of x^{k}y^{ℓ}z^{m} in ∂_{y}G. The Lemma is proved.

Lemma 6 The substitution of y by x in G equals g.

Proof. Let us fix K, m and compute the coefficient of x^{K}z^{m} in this substituted G. This is given by

\binom{K + m}{K} ∑_{k=0}^{K} \binom{K + k + m − 1}{K + m − 1}.  (58)

This is rewritten using the standard column summation property of binomial coefficients as

\binom{K + m}{K}\binom{2K + m}{K + m}.  (59)

This is exactly the coefficient of x^{K}y^{ℓ} in g. The Lemma is proved.

References

[1] C. A. Athanasiadis. On a refinement of the generalized Catalan numbers for Weyl groups. Trans. Amer. Math. Soc., 2004.

[2] C. A. Athanasiadis and V. Reiner. Noncrossing partitions for the group D_{n}. SIAM J. Discrete Math. (to appear).

[3] M. M. Bayer and L. J. Billera. Counting faces and chains in polytopes and posets. In Combinatorics and algebra (Boulder, Colo., 1983), volume 34 of Contemp. Math., pages 207–252. Amer. Math. Soc., Providence, RI, 1984.

[4] D. Bessis. The dual braid monoid. Ann. Sci. École Norm. Sup. (4), 36(5):647–683, 2003.

[5] P. Biane. Some properties of crossings and partitions. Discrete Math., 175(1-3):41–53, 1997.

[6] T. Brady and C. Watt. K(π, 1)’s for Artin groups of finite type. In Proceedings of the Conference on Geometric and Combinatorial Group Theory, Part I (Haifa, 2000), Geom. Dedicata, volume 94, pages 225–250, 2002.

[7] L. Carlitz. Some expansions and convolution formulas related to MacMahon’s master theorem. SIAM J. Math. Anal., 8(2):320–336, 1977.

[8] F. Chapoton, S. Fomin, and A. Zelevinsky. Polytopal realizations of generalized associahedra. Canad. Math. Bull., 45(4):537–566, 2002. Dedicated to Robert V. Moody.

[9] S. Fomin and A. Zelevinsky. Cluster algebras. I. Foundations. J. Amer. Math. Soc., 15(2):497–529, 2002.

[10] S. Fomin and A. Zelevinsky. Cluster algebras. II. Finite type classification. Inventiones Mathematicae, 154:63–121, 2003.

[11] S. Fomin and A. Zelevinsky. Y -systems and generalized associahedra. Annals of Math., 158(3):977–1018, 2003.

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

[13] C. W. Lee. The associahedron and triangulations of the n-gon. European J. Combin., 10(6):551–560, 1989.

[14] J. McCammond. Noncrossing partitions in surprising locations. 14 pages, 2003.

[15] M. Picantin. Explicit presentations for the dual braid monoids. C. R. Math. Acad. Sci. Paris, 334(10):843–848, 2002.

[16] V. Reiner. private communication.

[17] V. Reiner. Non-crossing partitions for classical reflection groups. Discrete Math., 177(1-3):195–222, 1997.

[18] R. Simion. Noncrossing partitions. Discrete Math., 217(1-3):367–409, 2000. Formal power series and algebraic combinatorics (Vienna, 1997).

[19] R. Simion. A type-B associahedron. Adv. in Appl. Math., 30(1-2):2–25, 2003. Formal power series and algebraic combinatorics (Scottsdale, AZ,

16 Frédéric Chapoton

Figure 1: The F -triangle for A_{3}