# Loday's characterization and enumeration of faces of associahedra (Stasheff polytopes)

From "The multiple facets of the associahedra" by Loday:

Let us consider the formal power series

$$f(x) = x+a_1 x^2 +a_2 x^3 + \cdots+ a_n x^{n+1} + \cdots$$

and let

$$g(x) = x+b_1 x^2 + b_2 x^3 + \cdots + b_n x^{n+1} + \cdots$$

be its inverse for composition, that is,

$$f(g(x)) = x.$$

The coefficient $b_n$ is a polynomial in $a_1$ to $a_n$. In low dimension, one gets

$$b_1 = a_1$$ $$b_2 = 2a_1^2 - a_2$$ $$b_3 = -5a_1^3+5a_1 a_2-a_3$$ $$b_4 = 14a_1^4 -21 a_1^2 a_2 +6a_1 a_3 +3a_2^2 -a_4$$

and more generally

$$b_n = \sum (-1)^{\sum n_i} \lambda(n_1,...,n_k) a_1^{n_1} \cdots a_n^{n_k},$$

where the sum is extended to all the k-tuples of integers $(n_1,...,n_k)$ so that $n_1 +2n_2 + \cdots +k n_k =n$. Here the coefficient $\lambda(n_1,...,n_k)$ is the number of cells of the associahedron $K^{n-1}$ that are isomorphic to the cartesian product $(K^0)^{n_1} \times \cdots \times(K^{k-1})^{n_k}$.

In other words, for example, $b_4$ is related to a refined f-vector (face-vector) for the 3-D Stasheff polytope, or 3-D associahedron, with 14 vertices (0-D faces), 21 edges (1-D faces), 6 pentagons (2-D faces), 3 rectangles (2-D faces), 1 3-D polytope (3-D faces). Subtracting one from the index of $a_n$, and ignoring the resulting indeterminates with indices with values less than one, allows one to read off the geometry of the associahedron from cartesian products of the lower dimensional associahedra, e.g., $3\: a^2_2$ becomes $3\: a^2_1$, the cartesian product of the 1-D associahedron with itself, which is a tetragon, or square in some reps.

Loday further asserts:

There exists a short operadic proof of the above formula which explicitly involves the parenthesizings, but it would be interesting to find one which involves the topological structure of the associahedron.

QUESTION: What references contain proofs of the above argument relating the monomials of the inversion formula to distinct faces of an associahedron as cartesian products of the lower dimensional associahedra?

Similar relationships hold, with a shift in indices, for the permutahedra (see this MSE-Q) and noncrossing partitions (see OEIS A134264).

• Btw, this same reversion of series was developed by Newton, so mathematicians stared at the faces of the associahedra for about 300 years before recognizing them. – Tom Copeland Jun 20 '17 at 17:14
• Also Fomin and Reading on pg. 31 of "Root systems and generalized associahedra " state, "For example, each face (of an associahedron) is the direct product of smaller associahedra." arxiv.org/abs/math/0505518 – Tom Copeland Jun 28 '17 at 0:45
• Also see Schobel and Veselov, "Separation coordinates, moduli spaces, and Stasheff polytopes" arxiv.org/abs/1307.6132 – Tom Copeland Nov 21 '17 at 12:30
• See "Hopf monoids and generalized permutohedra" by Aguiar and Ardila arxiv.org/abs/1709.07504 – Tom Copeland Dec 1 '17 at 18:25
• See "The diagonal of the associahedra" by Naruki Masuda, Hugh Thomas, Andy Tonks, Bruno Vallette arxiv.org/abs/1902.08059 – Tom Copeland Sep 7 at 13:42

I believe that the proof to which Loday is referring is the one that appears for Proposition 13.11.7 in Algebraic Operads. In this book, the coefficients $\lambda(n_1,\dots,n_k)$ are described as the number of planar rooted trees with certain properties. Such trees are in bijection with the Cartesian products of interest. Also, you might find the example following Corollary 9.2 of this paper helpful.