# Diagonals of Permutahedra and Associahedra

Alin Bostan, Frédéric Chyzak, Bérénice Delcroix-Oger, Guillaume Laplante-Anfossi, Vincent Pilaud, Kurt Stoeckl

► To cite this version:

Alin Bostan, Frédéric Chyzak, Bérénice Delcroix-Oger, Guillaume Laplante-Anfossi, Vincent Pilaud, et al.. Diagonals of Permutahedra and Associahedra. FPSAC 2025 - 37th International Conference on "Formal Power Series and Algebraic Combinatorics, Jul 2025, Sapporo, Japan. pp.12, Art. 136. hal-05468595

HAL Id: hal-05468595

https://inria.hal.science/hal-05468595v1

Submitted on 20 Jan 2026

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Diagonals of permutahedra and associahedra

Alin Bostan*¹, Frédéric Chyzak†¹, Bérénice Delcroix-Oger§²,
Guillaume Laplante-Anfossi¶³, Vincent Pilaud<fnref n="11" />‡, and Kurt Stoeckl**⁵

¹Institut National de Recherche en Informatique et en Automatique, Palaiseau, France

²Institut Montpelliérain Alexander Grothendieck, Université de Montpellier, France

³Institut for Matematik og Datalogi, Syddansk Universitet, Odense, Denmark

⁴Universitat de Barcelona & Centre de Recerca Matemàtica, Barcelona, Spain

⁵School of Mathematics and Statistics, The University of Melbourne, Victoria, Australia

**Abstract.** We present enumeration formulas for the faces of cellular diagonals of the permutahedra and associahedra. For the former, we use Zaslavsky's theory to count the faces of the hyperplane arrangement obtained as the union of $ℓ$ generically translated copies of the braid arrangement. This yields in particular nice formulas for the number of regions and bounded regions in terms of exponentials of generating functions of Fuss-Catalan numbers. For the latter, we use analytic or bijective methods to enumerate Tamari intervals weighted by certain binomial coefficients, leading to a surprisingly simple product formula.

**Résumé.** Nous présentons des formules d'énumération pour les faces de diagonales cellulaires des permutaèdres et des associaèdres. Pour les premiers, nous utilisons la théorie de Zaslavsky pour dénombrer les faces de l'arrangement d'hyperplans obtenu comme union de $ℓ$ copies de l'arrangement de tresses translatées génériquement. Cela donne en particulier de belles formules pour le nombre de régions et de régions bornées en termes d'exponentielles de fonctions génératrices de nombres de Fuss-Catalan. Pour les seconds, nous utilisons des méthodes analytiques ou bijectives pour énumérer les intervalles de Tamari pondérés par certains coefficients binomiaux, conduisant à une formule produit étonnamment simple.

**Keywords:** Diagonals, $f$-vectors, permutahedra, associahedra

<footnote>*alin.bostan@inria.fr. Supported by the French ANR grant DeRerumNatura (ANR-19-CE40-0018) and by the French-Austrian project EAGLES (ANR-22-CE91-0007 & FWF I6130-N).</footnote>

<footnote>†frederic.chyzak@inria.fr. Supported by the French ANR grant DeRerumNatura (ANR-19-CE40-0018) and by the French-Austrian project EAGLES (ANR-22-CE91-0007 & FWF I6130-N).</footnote>

<footnote>§berenice.delcroix-oger@umontpellier.fr. Supported by the French ANR grants CARPLO (ANR-20-CE40-0007), HighAGT (ANR-20-CE40-0016) and S3 (ANR-20-CE48-0010).</footnote>

<footnote>¶guillaume.laplanteanfossi@unimelb.edu.au. Supported by the Australian Research Council Future Fellowship FT210100256 and by the Andrew Sisson Fund.</footnote>

<footnote n="11">¹¹vincent.pilaud@ub.edu. Supported by the French-Austrian grant PAGCAP (ANR-21-CE48-0020 & FWF I 5788), by the Spanish-German project COMPOTE (AEI PCI2024-155081-2 & DFG 541393733), and by the Spanish grants PID2022-137283NB-C21, 2021 SGR 00697 and CEX2020-001084-M.</footnote>

<footnote>**kstoeckl@student.unimelb.edu.au. Supported by the Australian Research Council Future Fellowship FT210100256 and an Australian Government Research Training Program (RTP) Scholarship.</footnote>
# 1 Introduction

Cellular diagonals (Definition 2.2) for face-coherent families of polytopes are a fundamental object in algebraic topology. The Alexander-Whitney diagonal for simplices [7], and the Serre map for cubes [20], allow one to define the cup product in singular simplicial and cubical cohomology. These two diagonals are also needed in the study of iterated loop spaces [1], while other diagonals are needed in the study of the homology of fibered spaces [18]. In another direction, cellular diagonals allow one to define universal tensor products in homotopical algebra [12]. In the present paper, we study enumerative properties of the diagonals of permutahedra and associahedra.

For the associahedra, the first algebraic diagonals were found in [19] and later in [16, 15], while the first topological diagonal was given in [17] for the realizations of the associahedra of [14, 21]. The powerful technique of [10] using fiber polytopes [3] was reintroduced in [17] to define a topological diagonal of the associahedra. We shall call such a diagonal a *geometric diagonal* (Definition 2.5). One of these geometric diagonals, that we call “the” diagonal of the associahedra, has two remarkable features. First, it respects the operadic structure of the associahedra (each face of an associahedron is isomorphic to a product of lower-dimensional associahedra). Second, it satisfies the *magical formula*: the faces in the image of the diagonal are given by the pairs of faces which are comparable in the Tamari order (see Proposition 4.1 for a precise statement).

For the permutahedra, the first algebraic diagonal was found in [19], while the first topological diagonal was defined in [12], building on [17] and the theory of fiber polytopes [3]. In fact, this approach was extended to a general theory of geometric diagonals in [12] and applied to the family of operahedra, which contains the family of permutahedra, and encodes the notion of homotopy operad. Cellular diagonals of the operahedra do not satisfy the magical formula, and the combinatorial difficulty of describing their image is what prompted the development of the theory in [12].

This extended abstract presents enumerative formulas for the number of faces of diagonals of permutahedra and associahedra, borrowed from the two preprints [6, 4] and summarized in Table 1. While both formulas are combinatorially appealing, the approaches to find and prove these formulas are quite different.

For the associahedra, we exploit the magical formula (Propositions 4.1 and 2.8). Computing the *f*-vector of the diagonal of the associahedron boils down to enumerating intervals in the Tamari lattice weighted by a binomial coefficient involving some natural additional parameters. This in turn can be achieved either by analytic methods following a decomposition of Tamari intervals from [5], or by bijective methods exploiting existing bijections between Tamari intervals and planar maps [2, 11] (Theorem 4.2).

For the permutahedra, we exploit the duality between diagonals of a polytope *P* and common refinements of two translated copies of the normal fan of *P* (Proposition 2.7). The *f*-vector of any geometric diagonal of the permutahedron is thus the (reverse of) the
<table><caption>**Table 1:** Numbers $f_k$ of $k$-dim. faces in the diagonals of the $(n-1)$-dim. simplex, cube, associahedron, and permutahedron (for the latter, we just report here $f_0$ and $f_{n-1}$).</caption><thead><tr><th>Simplex</th><th>Cube</th><th>Associahedron</th><th>Permutahedron</th></tr></thead><tbody><tr><td>(k + 1) <table style="font-size: smaller; vertical-align: middle; line-height: 1.2;"><tbody><tr><td style="border-bottom: 1px solid black; padding: 0 0.2em;">n + 1</td></tr><tr><td style="padding: 0 0.2em;">k + 2</td></tr></tbody></table></td><td>(n - 1) <table style="font-size: smaller; vertical-align: middle; line-height: 1.2;"><tbody><tr><td style="border-bottom: 1px solid black; padding: 0 0.2em;">k</td></tr><tr><td style="padding: 0 0.2em;">k</td></tr></tbody></table> 2<sup>k</sup>3<sup>n-1-k</sup></td><td>2 <table style="font-size: smaller; vertical-align: middle; line-height: 1.2;"><tbody><tr><td style="border-bottom: 1px solid black; padding: 0 0.2em;">n - 1</td></tr><tr><td style="padding: 0 0.2em;">k</td></tr></tbody></table> <table style="font-size: smaller; vertical-align: middle; line-height: 1.2;"><tbody><tr><td style="border-bottom: 1px solid black; padding: 0 0.2em;">4n + 1 - k</td></tr><tr><td style="padding: 0 0.2em;">n + 1</td></tr></tbody></table> <table style="font-size: smaller; vertical-align: middle; line-height: 1.2;"><tbody><tr><td style="border-bottom: 1px solid black; padding: 0 0.2em;">(3n + 1)(3n + 2)</td></tr><tr><td style="padding: 0 0.2em;">(3n + 1)(3n + 2)</td></tr></tbody></table></td><td>f<sub>0</sub> = n! [z<sup>n</sup>] exp(&Sigma;<sub>m&ge;1</sub> (C<sub>m</sub> z<sup>m</sup>)/m)<br>f<sub>n-1</sub> = 2(n + 1)<sup>n-2</sup></td></tr><tr><td>Remark 2.9</td><td>Remark 2.9</td><td>Theorem 4.2</td><td>Theorems 3.1, 3.9, 3.10 and 3.11</td></tr></tbody></table>

$f$-vector of the hyperplane arrangement obtained as the union of two generically translated copies of the braid arrangement. At no additional cost, we study the arrangement $\mathcal{B}_n^\ell$ obtained as the union of $\ell$ generically translated copies of the braid arrangement $\mathcal{B}_n$ (Definition 3.2), using Zaslavsky's enumerative theory [24] (Theorem 3.5). We first observe that the flats of $\mathcal{B}_n^\ell$ are in bijection with $(\ell, n)$-partition forests, defined as $\ell$-tuples of (unordered) partitions of $[n]$ whose intersection hypergraph is a hyperforest (Definition 3.7). We then derive a summation formula for the Möbius polynomial of the arrangement $\mathcal{B}_n^\ell$, hence for its number of faces and bounded faces (Theorem 3.9) by [24]. It simplifies to short closed formulas for the number of vertices and facets of $\mathcal{B}_n^\ell$, involving exponentials of generating functions of Fuss-Catalan numbers (Theorems 3.10 and 3.11).

Note we must use these two distinct approaches. On the one hand, the normal fan of the associahedron (and thus the common refinement of two translated copies of this fan) is not defined by a hyperplane arrangement, so that the enumerative tools of [24] do not apply. On the other hand, diagonals of the permutahedra do not satisfy the magical formula so that it does not suffice to enumerate intervals of the weak order (and in fact, the latter do not yield nice enumerative formulas).

We refer to [6, 4] for many details and all proofs omitted in this extended abstract.

## 2 Cellular diagonals of polytopes

We now proceed to define thin, cellular, and geometric diagonals.

**Definition 2.1.** The thin diagonal of a set $X$ is the map $\delta : \begin{cases} X \to X \times X \\ x \mapsto (x, x) \end{cases}$. See Figure 1 (left).

**Definition 2.2.** A cellular diagonal of a $d$-polytope $P$ is a continuous map $\Delta : P \to P \times P$ where

* its image is a union of $d$-dimensional faces of $P \times P$ (i.e. it is cellular),

* it agrees with the thin diagonal of $P$ on the vertices of $P$, and

* it is homotopic to the thin diagonal of $P$, relative to the image of the vertices of $P$.

See Figure 1 (mid. left). A cellular diagonal is said to be face coherent if its restriction to a face of $P$ is itself a cellular diagonal for that face.
<figure><img src="image_2.png" /><figcaption>**Figure 1:** Cellular diagonals of the segment (top), the triangle (middle) and the square (bottom). For each of them, we have represented the thin diagonal of $P$ (left, in blue) and a cellular diagonal of $P$ (mid. left, in red) both represented in $P \times P$, the associated polytopal subdivision of $P$ (mid. right) and the common refinement of the two copies of the normal fan of $P$ (right) both represented in $P$.</figcaption></figure>

A powerful geometric technique to define face coherent cellular diagonals on polytopes first appeared in [10], was presented in [17], and was fully developed in [12]. We give in Theorem 2.4 the precise (but technical) definition of these diagonals, even though we will only use the characterizations of the faces in their image in Propositions 2.7 and 2.8.

The key idea is that any vector $v$ in generic position with respect to $P$ defines a cellular diagonal of $P$. For a point $z$ of $P$, we denote by $\rho_z P := 2z - P$ the reflection of $P$ with respect to the point $z$. We first define a notion of genericity with respect to $P$.

**Definition 2.3.** The fundamental hyperplane arrangement $\mathcal{H}_P$ of a polytope $P \subset \mathbb{R}^d$ is the set of all linear hyperplanes of $\mathbb{R}^d$ orthogonal to the edges of $P \cap \rho_z P$ for all $z \in P$. See Figure 2. A vector is generic with respect to $P$ if it does not belong to the union of the hyperplanes of the fundamental hyperplane arrangement $\mathcal{H}_P$.
<figure><img src="image_3.png" /><figcaption>**Figure 2:** The fundamental hyperplane arrangements of the 3-dimensional simplex (left), cube (mid. left), associahedron (mid. right) and permutahedron (right). The hyperplanes perpendicular to edges of some intersection $P \cap \rho_z P$, which are *not* edges of the polytope $P$, are colored in blue. Left and rightmost illustrations from [12, Figure 12].</figcaption></figure>

In particular, such a vector is not perpendicular to any edge of $P$, and we denote by $\min_v(P)$ (resp. $\max_v(P)$) the unique vertex of $P$ which minimizes (resp. maximizes) the scalar product with $v$.

**Theorem 2.4.** For any vector $v \in \mathbb{R}^d$ generic with respect to $P$, the tight coherent section $\Delta_{(P,v)}$ of the projection $P \times P \to P$ given by $(x, y) \mapsto (x+y)/2$ selected by the vector $(-v, v)$ defines a cellular diagonal of $P$. Said differently, we have $\Delta_{(P,v)}(z) := (\min_v(P \cap \rho_z P), \max_v(P \cap \rho_z P))$, where $\rho_z P := 2z - P$ denotes the reflection of $P$ with respect to the point $z$.

**Definition 2.5.** A *geometric diagonal* of a polytope $P$ is a diagonal of the form $\Delta_{(P,v)}$ for some vector $v \in \mathbb{R}^d$ generic with respect to $P$.

Note that the geometric diagonal $\Delta_{(P,v)}$ only depends on the region of $H_P$ containing $v$, see [12, Proposition 1.23].

Now the following *universal formula* [12, Theorem 1.26] expresses combinatorially the faces in the image of the geometric diagonal $\Delta_{(P,v)}$. Recall that the *normal cone* of a face $F$ of a polytope $P$ in $\mathbb{R}^d$ is the cone of directions $c \in \mathbb{R}^d$ such that the maximum of the scalar product $\langle c | x \rangle$ over $P$ is attained for some $x$ in $F$.

**Theorem 2.6 ([12, Theorem 1.26]).** Fix a vector $v \in \mathbb{R}^d$ generic with respect to $P$. For each hyperplane $H$ of the fundamental hyperplane arrangement $H_P$, denote by $H^v$ the open half space defined by $H$ and containing $v$. The faces of $P \times P$ in the image of the geometric diagonal $\Delta_{(P,v)}$ are the faces $F \times G$ where $F$ and $G$ are faces of $P$ such that either the normal cone of $F$ intersects $H^{-v}$ or the normal cone of $G$ intersects $H^v$, for each $H \in H_P$.

The image of $\Delta_{(P,v)}$ is a union of pairs of faces $F \times G$ of the Cartesian product $P \times P$. By drawing the polytopes $(F+G)/2$ for all pairs of faces $(F,G) \in \Delta_{(P,v)}$, we can visualize $\Delta_{(P,v)}$ as a polytopal subdivision of $P$. See Figure 1 (mid. right) and Figure 3.
<figure><img src="image_4.png" /><figcaption>**Figure 3:** The subdivisions induced by cellular diagonals of the 3-dimensional simplex (left), cube (mid. left), associahedron (mid. right), and permutahedron (right). Illustrations from [12, Figure 13].</figcaption></figure>

It turns out that the dual of this complex is just the common refinement of two translated copies of the normal fan of P. See Figure 1 (right). Recall that the normal fan of P is the fan formed by the normal cones of all faces of P. We thus obtain the following statement, which will be instrumental in Section 3.

**Proposition 2.7** ([12, Corollary 1.4]). The inclusion poset on the faces in the image of the diagonal $\Delta_{(P,v)}$ is isomorphic to the reverse inclusion poset on the faces of the common refinement of two copies of the normal fan of P, translated from each other by the vector $v$.

Finally, the following statement relates the image of the diagonal $\Delta_{(P,v)}$ to the intervals of the poset obtained by orienting the graph of P in direction $v$. This statement and its converse will be fundamental in Section 4.

**Proposition 2.8** ([12, Proposition 1.17]). For any vector $v$ generic with respect to P, the image of the diagonal $\Delta_{(P,v)}$ is contained in $\bigcup F \times G$ where the union ranges over all pairs $(F, G)$ of faces of P such that $\max_v(F) \le \min_v(G)$.

**Remark 2.9.** For some polytopes such as the simplices [7], the cubes [20], the freehedra [18], and the associahedra [17], the reverse inclusion also holds. According to [17], the resulting equality enhancing Proposition 2.8 was called the *magical formula* by J.-L. Loday. This equality simplifies the computation of the f-vectors of diagonals. For instance, the reader is invited to derive that the f-vectors of the diagonals of the $(n-1)$-dimensional simplex and cube are given by

$$f_k(\Delta_{\text{Simplex}(n)}) = (k+1) \binom{n+1}{k+2} \quad \text{and} \quad f_k(\Delta_{\text{Cube}(n)}) = \binom{n-1}{k} 2^k 3^{n-1-k}.$$

(The latter diagonals are known as the Alexander-Whitney map [7] and Serre map [20]). Polytopes of greater complexity such as the multiplihedra [13] or the operahedra [12], which include the permutahedra [6], do not possess this exceptional property, and the f-vectors of their diagonals are harder to compute.
## 3 Cellular diagonals of permutahedra

Recall that the *permutahedron* $\text{Perm}(n)$ is the polytope defined equivalently as

* the convex hull of the points $\sum_{i \in [n]} i e_{\sigma(i)}$ for all permutations $\sigma$ of $[n]$,

* the intersection of the hyperplane $\mathbb{H}_n := \{x \in \mathbb{R}^n \mid \sum_{i \in [n]} x_i = \binom{n+1}{2}\}$ with the half-spaces $\{x \in \mathbb{R}^n \mid \sum_{i \in [I]} x_i \ge \binom{I+1}{2}\}$ for $\emptyset \ne I \subsetneq [n]$.

The normal fan of the permutahedron $\text{Perm}(n)$ is the *braid fan*, defined by the *braid arrangement* $\mathcal{B}_n$ formed by the hyperplanes $\{x \in \mathbb{R}^n \mid x_i = x_j\}$ for all $1 \le i < j \le n$. See on the right.

When oriented in the direction $\omega_n := (n, \dots, 1) - (1, \dots, n)$, the graph of $\text{Perm}(n)$ is the Hasse diagram of the *weak order* on permutations of $[n]$, whose cover relations are transpositions of adjacent letters.

The study of geometric diagonals of the permutahedron was initiated in [12]. Such a diagonal does not satisfy the magical formula: some intervals of the weak order do not correspond to faces of the diagonal. However, we have the following statement.

**Theorem 3.1** ([6, Corollary 4.22]). The f-vector of any geometric diagonal $\Delta\text{Perm}(n)$ is the reverse of the f-vector of the arrangement $\mathcal{B}_n^2$ obtained as the union of two generically translated copies of the braid arrangement $\mathcal{B}_n$. Hence, the number of vertices and facets of $\Delta\text{Perm}(n)$ are

<figure><img src="image_5.png" /></figure>

$$f_0(\Delta\text{Perm}(n)) = n![z^n] \exp\left(\sum_{m \ge 1} \frac{C_m z^m}{m}\right) \quad \text{and} \quad f_{n-1}(\Delta\text{Perm}(n)) = 2(n+1)^{n-2},$$

where $C_m := \frac{1}{m+1} \binom{2m}{m}$ is the Catalan number. See Table 2.

<table><caption>**Table 2:** The numbers of vertices and facets of $\Delta\text{Perm}(n)$ for $n \in [9]$.</caption><thead><tr><th>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>...</th><th>OEIS</th></tr></thead><tbody><tr><th>vertices</th><td>1</td><td>3</td><td>17</td><td>149</td><td>1809</td><td>28399</td><td>550297</td><td>12732873</td><td>343231361</td><td>...</td><td>[23, A213507]</td></tr><tr><th>facets</th><td>1</td><td>2</td><td>8</td><td>50</td><td>432</td><td>4802</td><td>65536</td><td>1062882</td><td>20000000</td><td>...</td><td>[23, A007334]</td></tr></tbody></table>

In fact, the second part of Theorem 3.1 extends to $\ell$ copies of the braid arrangement $\mathcal{B}_n$, and involves relevant combinatorial objects and surprising formulas that we briefly present below.

**Definition 3.2** ([6, Section 1.3]). The $(\ell, n)$-braid arrangement $\mathcal{B}_n^\ell$ is the arrangement obtained as the union of $\ell$ generically translated copies of the braid arrangement $\mathcal{B}_n$. See on the right for an illustration of $\mathcal{B}_2^3$.

<figure><img src="image_6.png" /></figure>
**Definition 3.3.** Consider a (affine real) hyperplane arrangement $\mathcal{A}$. The faces of $\mathcal{A}$ are the closures of the regions of $\mathcal{A}$ and all their intersections with a hyperplane of $\mathcal{A}$. The f-polynomial and b-polynomial of $\mathcal{A}$ are the polynomials $f_{\mathcal{A}}(x) := \sum_{k=0}^{d} f_k(\mathcal{A}) x^k$ and $b_{\mathcal{A}}(x) := \sum_{k=0}^{d} b_k(\mathcal{A}) x^k$, where $f_k(\mathcal{A})$ and $b_k(\mathcal{A})$ respectively denote the numbers of k-faces and bounded k-faces of $\mathcal{A}$.

**Definition 3.4.** Consider an arrangement $\mathcal{A}$. A flat of $\mathcal{A}$ is a non-empty affine subspace of $\mathbb{R}^d$ that can be obtained as the intersection of some hyperplanes of $\mathcal{A}$. The flat poset of $\mathcal{A}$ is the poset of flats of $\mathcal{A}$ ordered by reverse inclusion. The Möbius polynomial of $\mathcal{A}$ is the polynomial

$$ \mu_{\mathcal{A}}(x, y) := \sum_{F \supseteq G} \mu(F, G) x^{\dim(F)} y^{\dim(G)}, $$

where $F \supseteq G$ ranges over all intervals of the flat poset of $\mathcal{A}$, and $\mu(F, G)$ is the Möbius function on the flat poset of $\mathcal{A}$ defined by $\mu(F, F) = 1$ and $\sum_{F \supseteq G \supseteq H} \mu(F, G) = 0$ for all $F \supsetneq H$. The characteristic polynomial of $\mathcal{A}$ is the coefficient of $x^d$ in $\mu_{\mathcal{A}}(x, y)$, i.e. $\chi_{\mathcal{A}}(y) := \sum_F \mu(\mathbb{R}^d, F) y^{\dim(F)}$.

**Theorem 3.5 ([24, Theorem A]).** The f-polynomial, the b-polynomial, and the Möbius polynomial of an arrangement $\mathcal{A}$ are related by $f_{\mathcal{A}}(x) = \mu_{\mathcal{A}}(-x, -1)$ and $b_{\mathcal{A}}(x) = \mu_{\mathcal{A}}(-x, 1)$. In particular, $f_d(\mathcal{A}) = (-1)^d \chi_{\mathcal{A}}(-1)$ and $b_d(\mathcal{A}) = (-1)^d \chi_{\mathcal{A}}(1)$.

**Example 3.6.** The braid arrangement $B_n$ has

* a k-face for each ordered partition of $[n]$ into $k+1$ parts,

* a k-flat for each unordered partition of $[n]$ into $k+1$ parts.

See Figure 4. The Möbius function of the set partitions poset is given by $\mu(\pi, \omega) = \prod_{p \in \omega} (-1)^{\#\pi[p]-1} (\#\pi[p] - 1)!$, where $\pi[p]$ denotes the restriction of $\pi$ to the part $p$ of $\omega$, and $\#\pi[p]$ denotes its number of parts. The Möbius polynomial of $B_n$ is given by $\mu_{B_n}(x, y) = \sum_{k \in [n]} x^{k-1} S(n, k) \prod_{i \in [k-1]} (y - i)$, where $S(n, k)$ denotes the Stirling number of the second kind [23, A008277], i.e. the number of set partitions of $[n]$ into $k$ parts.

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /><figcaption>**Figure 4:** The face poset of $B_3$ labeled by faces (left) and ordered partitions (mid. left), and the flat poset of $B_3$ labeled by flats (mid. right) and unordered partitions (right).</figcaption></figure>
We now consider the arrangement $\mathcal{B}_n^\ell$ of Definition 3.2 and describe its flat poset.

**Definition 3.7 ([6, Section 2.1]).** The intersection hypergraph of a $\ell$-tuple $\mathbf{F} := (F_1, \dots, F_\ell)$ of set partitions of $[n]$ is the $\ell$-regular $\ell$-partite hypergraph on all parts of all the partitions $F_i$ for $i \in [\ell]$, with a hyperedge connecting the parts containing $j$ for each $j \in [n]$. An $(\ell, n)$-partition forest is a $\ell$-tuple $\mathbf{F} := (F_1, \dots, F_\ell)$ of set partitions of $[n]$ whose intersection hypergraph is a hyperforest. For instance, the picture on the right represents a (3,6)-partition forest on top, and its intersection hyperforest on bottom. The $(\ell, n)$-partition forest poset is the poset $\mathbf{\Phi}_n^\ell$ on $(\ell, n)$-partition forests ordered by componentwise refinement.

**Proposition 3.8 ([6, Proposition 2.3]).** The flat poset of $\mathcal{B}_n^\ell$ is isomorphic to the $(\ell, n)$-partition forest poset $\mathbf{\Phi}_n^\ell$.

From this description of the flat poset of $\mathcal{B}_n^\ell$, we derive the following enumerative results by Theorem 3.5.

**Theorem 3.9 ([6, Theorem 2.4 & Corollary 2.6]).** The Möbius polynomial of $\mathcal{B}_n^\ell$ is given by

$$ \mu_{\mathcal{B}_n^\ell}(x, y) = x^{n-1-\ell n} y^{n-1-\ell n} \sum_{\mathbf{F} \le \mathbf{G}} \prod_{i \in [\ell]} x^{\#F_i} y^{\#G_i} \prod_{p \in G_i} (-1)^{\#F_i[p]-1} (\#F_i[p]-1)! $$

where $\mathbf{F} \le \mathbf{G}$ ranges over all intervals of the $(\ell, n)$-partition forest poset $\mathbf{\Phi}_n^\ell$, and $F_i[p]$ denotes the restriction of the partition $F_i$ to the part $p$ of $G_i$. Hence, the $f$- and $b$-polynomials of $\mathcal{B}_n^\ell$ are

$$ \begin{gathered} f_{\mathcal{B}_n^\ell}(x) = x^{n-1-\ell n} \sum_{\mathbf{F} \le \mathbf{G}} \prod_{i \in [\ell]} x^{\#F_i} \prod_{p \in G_i} (\#F_i[p] - 1)! \\ \text{and} \\ b_{\mathcal{B}_n^\ell}(x) = (-1)^\ell x^{n-1-\ell n} \sum_{\mathbf{F} \le \mathbf{G}} \prod_{i \in [\ell]} x^{\#F_i} \prod_{p \in G_i} -(\#F_i[p] - 1)! \end{gathered} $$

**Theorem 3.10 ([6, Theorems 2.18 & 2.19]).** The number of vertices of $\mathcal{B}_n^\ell$ is $\ell((\ell-1)n+1)^{n-2}$. In fact, the number of vertices $v$ of $\mathcal{B}_n^\ell$ such that the smallest flat of the $i^{th}$ copy of $\mathcal{B}_n$ containing $v$ has dimension $n - k_i - 1$ is given by $n^{\ell-1}(\binom{n-1}{k_1, \dots, k_\ell}) \prod_{i \in [\ell]} (n-k_i)^{k_i-1}$.

**Theorem 3.11 ([6, Theorems 2.20 & 2.21]).** The characteristic polynomial of $\mathcal{B}_n^\ell$ is given by

$$ \chi_{\mathcal{B}_n^\ell}(y) = \frac{(-1)^n n!}{y} [z^n] \exp \left( - \sum_{m \ge 1} \frac{F_{\ell,m} y z^m}{m} \right), $$

where $F_{\ell,m} := \frac{1}{(\ell-1)m+1} \binom{\ell m}{m}$ is the Fuss-Catalan number. Hence, the numbers of regions and of bounded regions of $\mathcal{B}_n^\ell$ are

$$ f_{n-1}(\mathcal{B}_n^\ell) = n! [z^n] \exp \left( \sum_{m \ge 1} \frac{F_{\ell,m} z^m}{m} \right) \quad \text{and} \quad b_{n-1}(\mathcal{B}_n^\ell) = (n-1)! [z^{n-1}] \exp \left( (\ell-1) \sum_{m \ge 1} F_{\ell,m} z^m \right). $$

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>
# 4 Cellular diagonals of associahedra

Recall that the *associahedron* $\mathcal{Asso}(n)$ is the polytope defined equivalently as

* the convex hull of the points $\sum_{i \in [n]} \ell(T, i) r(T, i) e_i$ for all binary trees $T$ with $n$ internal nodes, where $\ell(T, i)$ and $r(T, i)$ respectively denote the numbers of leaves in the left and right subtrees of the $i$th node of $T$ in infix labeling, see [14],

* the intersection of the hyperplane $\mathbb{H}_n := \{x \in \mathbb{R}^n \mid \sum_{i \in [n]} x_i = \binom{n+1}{2}\}$ with the half-spaces $\{x \in \mathbb{R}^n \mid \sum_{i \le l \le j} x_l \ge \binom{j-1}{2}\}$ for all $1 \le i \le j \le n$, see [21].

When oriented in the direction $\omega_n$, its graph is the Hasse diagram of the *Tamari lattice* [22] on binary trees with $n$ internal nodes, whose cover relations are right rotations. See on the right.

There is one specific geometric diagonal $\Delta\mathcal{Asso}(n)$ of the associahedra which respects the Tamari lattice and satisfies the magical formula [19, 16, 15, 17, 12].

<figure><img src="image_11.png" /></figure>

**Proposition 4.1 ([17, Theorem 2]).** The $k$-faces of the diagonal $\Delta\mathcal{Asso}(n)$ correspond to the pairs $(F, G)$ of faces of $\mathcal{Asso}(n)$ with $\dim(F) + \dim(G) = k$ and $\max(F) \le \min(G)$ (where $\le$, $max$ and $min$ refer to the order given by the Tamari lattice).

**Theorem 4.2 ([4, Proposition 7 & Theorem 2]).** The number of $k$-faces of $\Delta\mathcal{Asso}(n)$ is

$$f_k(\Delta\mathcal{Asso}(n)) = \frac{2}{(3n+1)(3n+2)} \binom{n-1}{k} \binom{4n+1-k}{n+1}.$$

**Remark 4.3.** (i) *Tamari intervals* are enumerated by $f_0(\Delta\mathcal{Asso}(n)) = \frac{2}{(3n+1)(3n+2)} \binom{4n+1}{n+1}$. This formula was proved in [5] and appears as [23, A000260]. It also counts the rooted 3-connected planar triangulations with $2n+2$ faces, and explicit bijections between Tamari intervals and 3-connected triangulations were given in [2, 8].

(ii) *Synchronized Tamari intervals* are enumerated by $f_{n-1}(\Delta\mathcal{Asso}(n)) = \frac{2}{n(n+1)} \binom{3n}{n-1}$. This formula was proved in [9] and appears as [23, A000139]. It also counts the rooted non-separable planar maps with $n+1$ edges, and the 2-stackable permutations of $[n]$.

We finally briefly discuss the ideas behind Theorem 4.2. For a binary tree $T$, let $\text{des}(T)$ (resp. $\text{asc}(T)$) denote the number of binary trees covered by $T$ (resp. covering $T$) in the Tamari lattice. As the associahedron is a simple polytope, there are precisely $(\text{des}(T))$ (resp. $(\text{asc}(T))$) $\ell$-faces of the associahedron whose maximal (resp. minimal) vertex is $T$. We thus directly derive from the magical formula of Proposition 2.8 that the number of $k$-faces of $\Delta\mathcal{Asso}(n)$ is

$$\sum_{S \le T} \sum_{0 \le \ell \le k} \binom{\text{des}(S)}{\ell} \binom{\text{asc}(T)}{k-\ell} = \sum_{S \le T} \binom{\text{des}(S) + \text{asc}(T)}{k}.$$
<table><caption>**Table 3:** The first few values of $f_k(\Delta\mathfrak{Asso}(n)) = \frac{2}{(3n+1)(3n+2)} \binom{n-1}{k} \binom{4n+1-k}{n+1}$. Note that the first column is [23, A000260] while the diagonal is [23, A000139].</caption><thead><tr><th>n\k</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>1</td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>2</td><td>3</td><td>2</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>3</td><td>13</td><td>18</td><td>6</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>4</td><td>68</td><td>144</td><td>99</td><td>22</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>5</td><td>399</td><td>1140</td><td>1197</td><td>546</td><td>91</td><td></td><td></td><td></td><td></td></tr><tr><td>6</td><td>2530</td><td>9108</td><td>12903</td><td>8976</td><td>3060</td><td>408</td><td></td><td></td><td></td></tr><tr><td>7</td><td>16965</td><td>73710</td><td>131625</td><td>123500</td><td>64125</td><td>17442</td><td>1938</td><td></td><td></td></tr><tr><td>8</td><td>118668</td><td>604128</td><td>1302651</td><td>1540770</td><td>1078539</td><td>446292</td><td>100947</td><td>9614</td><td></td></tr><tr><td>9</td><td>857956</td><td>5008608</td><td>12660648</td><td>18086640</td><td>15958800</td><td>8898240</td><td>3058770</td><td>592020</td><td>49335</td></tr></tbody></table>

At this point, there are at least two possible proofs for Theorem 4.2, discussed in [4]:

* The first proof is analytic. Using a natural recursive decomposition, one obtains a quadratic equation on the generating function of Tamari intervals with one additional catalytic variable [5]. By the quadratic method, this equation can be transformed into a polynomial equation on $A(t,z) := \sum_{n,k} \sum_{S \le T} \binom{\mathrm{des}(S)+\mathrm{asc}(T)}{k} t^n z^k$. One then obtains Theorem 4.2 by extracting the coefficients of $A(t,z)$ by Lagrange inversion after an adequate reparameterization of our polynomial equation.

* The second proof is bijective. For a Tamari interval $S \le T$, the statistics $\mathrm{des}(S)$ and $\mathrm{asc}(T)$ can be translated in terms of canopy agreement between $S$ and $T$. Through the bijection of [2], a simple expression for the generating function of Tamari intervals with variables recording the canopy patterns of the two trees was obtained in [11]. We then obtain Theorem 4.2 by specializing variables in this generating function and extracting coefficients by Lagrange inversion again.

## References

[1] H. J. Baues. "Geometry of loop spaces and the cobar construction". Mem. Amer. Math. Soc. 25.230 (1980), pp. ix+171. DOI.

[2] O. Bernardi and N. Bonichon. "Intervals in Catalan lattices and realizers of triangulations". J. Combin. Theory Ser. A 116.1 (2009), pp. 55-75. DOI.

[3] L. J. Billera and B. Sturmfels. "Fiber polytopes". Ann. of Math. (2) 135.3 (1992), pp. 527-549. DOI.

[4] A. Bostan, F. Chyzak, and V. Pilaud. "Refined product formulas for Tamari intervals". 2023. arXiv:2303.10986.

[5] F. Chapoton. "Sur le nombre d'intervalle dans les treillis de Tamari". Sém. Lothar. Combin. 55 (2005/07), Art. B55f, 18.
[6] B. Delcroix-Oger, G. Laplante-Anfossi, V. Pilaud, and K. Stoeckl. “Cellular diagonals of permutahedra”. 2023. arXiv:2308.12119.

[7] S. Eilenberg and S. MacLane. “On the groups $H(\Pi, n)$. III”. *Ann. of Math.* **(2)** **60** (1954), pp. 513–557. DOI.

[8] W. Fang, É. Fusy, and P. Nadeau. “Bijections between Tamari intervals and blossoming trees”. 2023. arXiv:2312.13159.

[9] W. Fang and L.-F. Préville-Ratelle. “The enumeration of generalized Tamari intervals”. *European J. Combin.* **61** (2017), pp. 69–84. DOI.

[10] W. Fulton and B. Sturmfels. “Intersection theory on toric varieties”. *Topology* **36.2** (1997), pp. 335–353. DOI.

[11] E. Fusy and A. Humbert. “Bijections for generalized Tamari intervals via orientations”. *European J. Combin.* **117** (2024), Paper No. 103826, 19. DOI.

[12] G. Laplante-Anfossi. “The diagonal of the operahedra”. *Adv. Math.* **405** (2022), Paper No. 108494, 50. DOI.

[13] G. Laplante-Anfossi and T. Mazuir. “The diagonal of the multiplihedra and the tensor product of $A_\infty$-morphisms”. *J. Éc. polytech. Math.* **10** (2023), pp. 405–446. DOI.

[14] J.-L. Loday. “Realization of the Stasheff polytope”. *Arch. Math.* **83.3** (2004), pp. 267–278. DOI.

[15] J.-L. Loday. “The diagonal of the Stasheff polytope”. *Higher structures in geometry and physics*. Vol. 287. Progr. Math. Birkhäuser/Springer, New York, 2011, pp. 269–292. DOI.

[16] M. Markl and S. Shnider. “Associahedra, cellular $W$-construction and products of $A_\infty$-algebras”. *Trans. Amer. Math. Soc.* **358.6** (2006), pp. 2353–2372. DOI.

[17] N. Masuda, H. Thomas, A. Tonks, and B. Vallette. “The diagonal of the associahedra”. *J. Éc. polytech. Math.* **8** (2021), pp. 121–146. DOI.

[18] S. Saneblidze. “The bitwisted Cartesian model for the free loop fibration”. *Topology Appl.* **156.5** (2009), pp. 897–910. DOI.

[19] S. Saneblidze and R. Umble. “Diagonals on the permutahedra, multiplihedra and associahedra”. *Homology Homotopy Appl.* **6.1** (2004), pp. 363–411.

[20] J.-P. Serre. “Homologie singulière des espaces fibrés. Applications”. *Ann. of Math.* **(2)** **54** (1951), pp. 425–505. DOI.

[21] S. Shnider and S. Sternberg. *Quantum groups: From coalgebras to Drinfeld algebras*. Series in Mathematical Physics. Cambridge, MA: International Press, 1993, p. 592.

[22] D. Tamari. “Monoïdes préordonnés et chaînes de Malcev”. PhD thesis. Université Paris Sorbonne, 1951.

[23] “The On-Line Encyclopedia of Integer Sequences”. http://oeis.org. 2010.

[24] T. Zaslavsky. “Facing up to arrangements: face-count formulas for partitions of space by hyperplanes”. *Mem. Amer. Math. Soc.* **1**.issue 1, 154 (1975), pp. vii+102. DOI.