# On the H-triangle of generalised nonnesting partitions

Marko Thiel*

*Department of Mathematics, University of Vienna, Austria*

**Abstract.** With a crystallographic root system $\Phi$, there are associated two Catalan objects, the set of nonnesting partitions $NN(\Phi)$, and the cluster complex $\Delta(\Phi)$. These possess a number of enumerative coincidences, many of which are captured in a surprising identity, first conjectured by Chapoton. We prove this conjecture, and indicate its generalisation for the Fuß-Catalan objects $NN^{(k)}(\Phi)$ and $\Delta^{(k)}(\Phi)$, conjectured by Armstrong.

**Résumé.** À un système de racines cristallographique, on associe deux objets de Catalan: l'ensemble des partitions non-emboîtées $NN(\Phi)$, et le complexe d'amas $\Delta(\Phi)$. Ils possèdent de nombreuses coïncidences énumératives, plusieurs d'entre elles étant capturées dans une identité surprenante, conjecturée par Chapoton. Nous démontrons cette conjecture, et indiquons sa généralisation pour les objets de Fuß-Catalan $NN^{(k)}(\Phi)$ et $\Delta^{(k)}(\Phi)$, conjecturée par Armstrong.

**Keywords:** nonnesting partitions, noncrossing partitions, cluster complex, Coxeter-Catalan objects

## 1 Introduction

For a crystallographic root system $\Phi$, there are three well-known Coxeter-Catalan objects [Arm09]: the set of noncrossing partitions $NC(\Phi)$, the set of nonnesting partitions $NN(\Phi)$ and the cluster complex $\Delta(\Phi)$. The former two and the set of facets of the latter are all counted by the same numbers, the Coxeter-Catalan numbers $Cat(\Phi)$. For the root system of type $A_{n-1}$, these reduce to objects counted by the classical Catalan numbers $C_n = \frac{1}{n+1} \binom{2n}{n}$, namely the set of noncrossing partitions of $[n] = \{1, 2, \dots, n\}$, the set of nonnesting partitions of $[n]$ and the set of triangulations of a convex $(n+2)$-gon, respectively.

Each of these Coxeter-Catalan objects has a generalisation [Arm09], a Fuß-Catalan object defined for each positive integer $k$. These are the set of $k$-divisible noncrossing partitions $NC_{(k)}(\Phi)$, the set of $k$-generalised nonnesting partitions $NN^{(k)}(\Phi)$ and the generalised cluster complex $\Delta^{(k)}(\Phi)$. They specialise to the corresponding Coxeter-Catalan objects when $k=1$. The former two and the set of facets of the latter are counted by Fuß-Catalan numbers $Cat^{(k)}(\Phi)$, which specialise to the classical Fuß-Catalan numbers $C_n^{(k)} = \frac{1}{kn+1} \binom{(k+1)n}{n}$ in type $A_{n-1}$.

<footnote>*Email: marko.thiel@univie.ac.at</footnote>
The enumerative coincidences do not end here. Chapoton defined the *M*-triangle, the *H*-triangle and the *F*-triangle, which are polynomials in two variables that encode refined enumerative information on $NC(\Phi)$, $NN(\Phi)$ and $\Delta(\Phi)$ respectively [Cha04, Cha06]. This allowed him to formulate the $M = F$ conjecture [Cha04, Conjecture 1] and the $H = F$ conjecture [Cha06, Conjecture 6.1] relating these polynomials through invertible transformations of variables. These conjectures were later generalised to the corresponding Fuß-Catalan objects by Armstrong [Arm09, Conjecture 5.3.2.]. The $M = F$ conjecture was first proven by Athanasiadis [Ath07] for $k = 1$, and later by Krattenthaler [Kra06a, Kra06b] and Tzanaki [Tza08] for $k > 1$. In this extended abstract, we prove the $H = F$ conjecture in the $k = 1$ case. The proof of the generalised conjecture of Armstrong can be found in the full version [Thi14].

## 2 Definitions and the Main Result

Let $\Phi = \Phi(S)$ be a crystallographic root system with a simple system $S$. Then $\Phi = \Phi^+ \sqcup -\Phi^+$ is the disjoint union of the set of positive roots $\Phi^+$ and the set of negative roots $-\Phi^+$. Every positive root can be written uniquely as a linear combination of the simple roots and all coefficients of this linear combination are nonnegative integers. For further background on root systems, see [Hum90]. Define the *root order* on $\Phi^+$ by

$$ \beta \ge \alpha \text{ if and only if } \beta - \alpha \in \langle S \rangle_{\mathbb{N}}, $$

that is, $\beta \ge \alpha$ if and only if $\beta - \alpha$ can be written as a linear combination of simple roots with nonnegative integer coefficients. The set of positive roots $\Phi^+$ with this partial order is called the *root poset*. A set of pairwise incomparable elements of the root poset is called an *antichain*. The *support* of a root $\beta \in \Phi^+$ is the set of all $\alpha \in S$ with $\alpha \le \beta$.

We define the set of *nonnesting partitions* $NN(\Phi)$ of $\Phi$ as the set of antichains in the root poset of $\Phi$.

Let us define the *H-triangle* [Cha06, Section 6] as

$$ H_{\Phi}(x, y) = \sum_{A \in NN(\Phi)} x^{|A|} y^{|A \cap S|}. $$

Let $\Phi_{\ge -1} = \Phi^+ \cup -S$ be the set of *almost positive roots* of $\Phi$. Then there exists a symmetric binary relation called *compatibility* [FZ03, Definition 3.4] on $\Phi_{\ge -1}$ such that all negative simple roots are pairwise compatible and for $\alpha \in S$ and $\beta \in \Phi^+$, $-\alpha$ is compatible with $\beta$ if and only if $\alpha$ is not in the support of $\beta$.

Define a simplicial complex $\Delta(\Phi)$ as the set of all subsets $A \subseteq \Phi_{\ge -1}$ such that all almost positive roots in $A$ are pairwise compatible. This is the *cluster complex* of $\Phi$. This simplicial complex is *pure*, all facets have cardinality $n$, where $n = |S|$ is the rank of $\Phi$.

Let us define the *F-triangle* [Cha04, Section 2] as

$$ F_{\Phi}(x, y) = \sum_{F \in \Delta(\Phi)} x^{|F \cap \Phi^+|} y^{|F \cap -S|} = \sum_{l,m} f_{l,m}(\Phi) x^l y^m. $$

Consider the Weyl group $W = W(\Phi)$ of the root system $\Phi$. A *standard Coxeter element* in $W$ is a
product of all the simple reflections of W in some order. A Coxeter element is any element of W that is conjugate to a standard Coxeter element. Let T denote the set of reflections in W. For $w \in W$, define the absolute length $l_T(w)$ of $w$ as the minimal $l$ such that $w = t_1t_2 \cdots t_l$ for some $t_1, t_2, \ldots, t_l \in T$. Define the absolute order on W by

$$u \leq_T v \text{ if and only if } l_T(u) + l_T(u^{-1}v) = l_T(v).$$

Fix a Coxeter element $c \in W$. We define the set of noncrossing partitions $NC(\Phi)$ of $\Phi$ as the interval $[e, c]$ in the absolute order. We drop the choice of the Coxeter element $c$ from the notation, since a different choice of Coxeter element results in a different but isomorphic poset.

Let us define the M-triangle [Cha04, Section 3] as

$$M_{\Phi}(x, y) = \sum_{u,v \in NC(\Phi)} \mu(u, v) x^{rk(u)} y^{rk(v)},$$

where $rk$ is the rank function of the graded poset $NC(\Phi)$ and $\mu$ is its Möbius function.

As mentioned in the introduction, $NC(\Phi)$, $NN(\Phi)$ and the set of facets of $\Delta(\Phi)$ are all counted by the same number $Cat(\Phi)$. But more is true: define the Narayana number $Nar(\Phi, i)$ as the number of elements of $NC(\Phi)$ of rank $i$ [Arm09, Definition 3.5.4]. The number of antichains in the root poset of cardinality $i$ also equals $Nar(\Phi, i)$ [Ath05, Proposition 5.1, Remark 5.2]. Let $(h_0, h_1, \ldots, h_n)$ be the $h$-vector of $\Delta(\Phi)$, defined by the relation

$$\sum_{i=0}^{n} h_i x^{n-i} = \sum_{l,m} f_{l,m} (x-1)^{n-(l+m)}.$$

Then $h_{n-i} = Nar(\Phi, i)$ for all $i \in \{0, 1, \ldots, n\}$ [FR05, Theorem 3.2].

The main result of this extended abstract is the following theorem, conjectured by Chapoton.

**Theorem 1** If $\Phi$ is a crystallographic root system of rank $n$, then

$$H_{\Phi}(x, y) = (x-1)^n F_{\Phi} \left( \frac{1}{x-1}, \frac{1+(y-1)x}{x-1} \right).$$

In order to prove Theorem 1, we first find a combinatorial bijection for nonnesting partitions that leads to a differential equation for the H-triangle analogous to one known for the F-triangle. Using both of these differential equations and induction on the rank $n$, we prove Theorem 1 by showing that the derivatives with respect to $y$ of both sides of the equation as well as their specialisations at $y = 1$ agree. After proving Theorem 1, we use it together with the $M = F$ (ex-)conjecture to relate the H-triangle to the M-triangle.

## 3 Proof of the Main Result

To prove Theorem 1, we show that the derivatives with respect to $y$ of both sides of the equation agree, as well as their specialisations at $y = 1$. To do this, we need the following lemmas.
**Lemma 1** If $\Phi$ is a crystallographic root system of rank $n$, then

$$H_{\Phi}(x, 1) = (x - 1)^n F_{\Phi} \left( \frac{1}{x - 1}, \frac{1}{x - 1} \right).$$

**Proof:** We have

$$(x - 1)^n F_{\Phi} \left( \frac{1}{x - 1}, \frac{1}{x - 1} \right) = \sum_{l,m} f_{l,m} (x - 1)^{n - (l+m)} = \sum_{i=0}^{n} h_i x^{n-i},$$

where $(h_0, h_1, \dots, h_n)$ is the $h$-vector of $\Delta(\Phi)$. So

$$[x^i](x - 1)^n F_{\Phi} \left( \frac{1}{x - 1}, \frac{1}{x - 1} \right) = h_{n-i} = \mathrm{Nar}(\Phi, i),$$

by [FR05, Theorem 3.2]. But

$$[x^i] H_{\Phi}(x, 1) = \mathrm{Nar}(\Phi, i),$$

by [Ath05, Proposition 5.1, Remark 5.2]. □

**Lemma 2 ([Cha04, Proposition 3])** If $\Phi$ is a crystallographic root system of rank $n$, then

$$\frac{\partial}{\partial y} F_{\Phi(S)}(x, y) = \sum_{\alpha \in S} F_{\Phi(S \setminus \{\alpha\})}(x, y).$$

**Lemma 3** For every simple root $\alpha \in S$, there exists a bijection $\Theta$ from the set of nonnesting partitions $A \in NN(\Phi(S))$ with $\alpha \in A$ to $NN(\Phi(S \setminus \{\alpha\}))$, such that $|\Theta(A)| = |A| - 1$ and $|\Theta(A) \cap S \setminus \{\alpha\}| = |A \cap S| - 1$ for all $A \in NN(\Phi(S))$.

**Proof:** Define $\Theta(A) = A \setminus \{\alpha\}$. If $\beta \in A$ and $\beta \neq \alpha$, then $\beta$ and $\alpha$ are incomparable, since $A$ is an antichain. So $\alpha$ is not in the support of $\beta$. So $\beta \in \Phi(S \setminus \{\alpha\})$. Clearly $\Theta(A) = A \setminus \{\alpha\}$ is an antichain in the root poset of $\Phi(S \setminus \{\alpha\})$, so $\Theta$ is well defined. It is also clear that $|\Theta(A)| = |A| - 1$ and $|\Theta(A) \cap S \setminus \{\alpha\}| = |A \cap S| - 1$ for all $A \in NN(\Phi(S))$.

Define the map $\Psi: NN(\Phi(S \setminus \{\alpha\})) \to NN(\Phi(S))$ by $\Psi(A) = A \cup \{\alpha\}$. If $A \in NN(\Phi(S \setminus \{\alpha\}))$ and $\beta \in A$, then $\alpha$ is not in the support of $\beta$, so $\alpha$ and $\beta$ are incomparable. Thus $\Psi(A) = A \cup \{\alpha\}$ is an antichain in the root poset of $\Phi(S)$, so $\Psi$ is well-defined. Clearly $\Psi$ is the inverse of $\Theta$, so $\Theta$ is a bijection. □

**Lemma 4** If $\Phi$ is a crystallographic root system of rank $n$, then

$$\frac{\partial}{\partial y} H_{\Phi(S)}(x, y) = x \sum_{\alpha \in S} H_{\Phi(S \setminus \{\alpha\})}(x, y).$$
**Proof:** Say $h_{l,m}(\Phi) = [x^l y^m] H_{\Phi}(x, y)$. We wish to show that

$$mh_{l,m}(\Phi(S)) = \sum_{\alpha \in S} h_{l-1,m-1}(\Phi(S \setminus \{\alpha\})).$$

So we seek a bijection $\Theta$ from the set of pairs $(A, \alpha)$ with $A \in NN(\Phi(S))$ and $\alpha \in A \cap S$ to the set of pairs $(\alpha', A')$ with $\alpha' \in S$ and $A' \in NN(\Phi(S \setminus \{\alpha'\}))$ such that if $\Theta(A, \alpha) = (A', \alpha')$, then $|A'| = |A| - 1$ and $|A' \cap S \setminus \{\alpha'\}| = |A \cap S| - 1$. Such a bijection is given in Lemma 3. $\square$

We are now in a position to prove Theorem 1.

**Proof of Theorem 1:** We proceed by induction on $n$. If $n = 0$, both sides are equal to 1, so the result holds. If $n > 0$,

$$\frac{\partial}{\partial y} H_{\Phi(S)}(x, y) = x \sum_{\alpha \in S} H_{\Phi(S \setminus \{\alpha\})}(x, y),$$

by Lemma 4. By induction hypothesis, this is further equal to

$$x \sum_{\alpha \in S} (x-1)^{n-1} F_{\Phi(S \setminus \{\alpha\})} \left( \frac{1}{x-1}, \frac{1+(y-1)x}{x-1} \right),$$

which equals

$$\frac{\partial}{\partial y} (x-1)^n F_{\Phi(S)} \left( \frac{1}{x-1}, \frac{1+(y-1)x}{x-1} \right)$$

by Lemma 2. But

$$H_{\Phi}(x, 1) = (x-1)^n F_{\Phi} \left( \frac{1}{x-1}, \frac{1}{x-1} \right)$$

by Lemma 1, so

$$H_{\Phi}(x, y) = (x-1)^n F_{\Phi} \left( \frac{1}{x-1}, \frac{1+(y-1)x}{x-1} \right),$$

since the derivatives with respect to $y$ as well as the specialisations at $y = 1$ of both sides agree. $\square$

# 4 Consequences and generalisations

We may also recover the original statement of the conjecture, due to Chapoton.

**Corollary 1 ([Cha06, Conjecture 6.1]** If $\Phi$ is a crystallographic root system of rank $n$, then

$$H_{\Phi}(x, y) = (1-x)^n F_{\Phi} \left( \frac{x}{1-x}, \frac{xy}{1-x} \right).$$

**Proof:** We have [Cha04, Proposition 5]

$$F_{\Phi}(x, y) = (-1)^n F_{\Phi}(-1-x, -1-y). \qquad (1)$$

Substitute (1) into Theorem 1 to get the result. $\square$

Using the $M = F$ (ex-)conjecture, we can also relate the H-triangle to the M-triangle.
**Corollary 2** If $\Phi$ is a crystallographic root system of rank $n$, then

$$H_{\Phi}(x, y) = (1 + (y - 1)x)^n M_{\Phi} \left( \frac{y}{y - 1}, \frac{(y - 1)x}{1 + (y - 1)x} \right).$$

**Proof:** We have [Kra06a, Conjecture FM] [Ath07, Theorem 1.1]

$$F_{\Phi}(x, y) = y^n M_{\Phi} \left( \frac{1+y}{y-x}, \frac{y-x}{y} \right). \qquad (2)$$

Substitute (2) into Theorem 1 to get the result. $\square$

Lemma 1, Lemma 2, Lemma 4, Theorem 1 and Corollary 2 all generalise to the corresponding Fuß-Catalan objects $NN^{(k)}(\Phi)$, $NC^{(k)}(\Phi)$ and $\Delta^{(k)}(\Phi)$. For proofs of these more general results and further consequences, see the full version of the article [Thi14].

## References

[Arm09] Drew Armstrong. Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups. *Memoirs of the American Mathematical Society*, 202, 2009.

[Ath05] Christos A. Athanasiadis. On a Refinement of the Generalized Catalan Numbers for Weyl Groups. *Transactions of the American Mathematical Society*, 357:179–196, 2005.

[Ath07] Christos A. Athanasiadis. On some enumerative aspects of generalized associahedra. *European Journal of Combinatorics*, 28:1208–1215, 2007.

[Cha04] Frédéric Chapoton. Enumerative Properties of Generalized Associahedra. *Séminaire Lotharingien de Combinatoire*, 51, 2004.

[Cha06] Frédéric Chapoton. Sur le nombre de réflexions pleines dans les groupes de coxeter finis. *Bulletin of the Belgian Mathematical Society*, 13:585–596, 2006.

[FR05] Sergey Fomin and Nathan Reading. Generalized Cluster Complexes and Coxeter Combinatorics. *International Mathematics Research Notices*, 44:2709–2757, 2005.

[FZ03] Sergey Fomin and Andrei Zelevinsky. Y-Systems and Generalized Associahedra. *Annals of Mathematics*, 158:977–1018, 2003.

[Hum90] James E. Humphreys. *Reflection Groups and Coxeter Groups*. Cambridge University Press, Cambridge, 1990.

[Kra06a] Christian Krattenthaler. The F-triangle of the generalised cluster complex. *Topics in Discrete Mathematics*, pages 93–126, 2006.

[Kra06b] Christian Krattenthaler. The M-triangle of generalised non-crossing partitions for the types $E_7$ and $E_8$. *Séminaire Lotharingien de Combinatoire*, 54, 2006.
[Thi14] Marko Thiel. On the H-triangle of generalised nonnesting partitions. *European Journal of Combinatorics*, 39:244–255, 2014.

[Tza08] Eleni Tzanaki. Faces of Generalized Cluster Complexes and Noncrossing Partitions. *SIAM Journal on Discrete Mathematics*, 22:15–30, 2008.