I'd be interested in hearing people's viewpoints on this. Looking for an intuitive perspective. See Wikipedia for descriptions of polytopes and the Lagrange inversion theorem/formula (LIF) for compositional inversion.

**Background update** (8/2012): Consider a compositional inverse pair of functions, $h$ and $h^{-1}$, analytic at the origin with $h(0)=0=h^{-1}(0)$.

Then with $\omega=h(z)$ and $g(z)=1/[dh(z)/dz]$,

$$\exp \left[ {t \cdot g(z)\frac{d}{{dz}}} \right]f(z) = \exp \left[ {t\frac{d}{{d\omega }}} \right]f[{h^{ - 1}}(\omega )] = f[{h^{ - 1}}[t + \omega]] = f[{h^{ - 1}}[t + h(z)]],$$ so $$\exp \left[ {t \cdot g(z)\frac{d}{{dz}}} \right]z |_{z=0}=h^{-1}(t)$$

(see OEIS A145271 and A139605 for more relations).

With the power series rep $h(z)= c_1z + c_2z^2 + c_3z^3 + ... ,$

$$\frac{1}{5!}[g(z)\frac{d}{{dz}}]^{5}z|_{z=0} = \frac{1}{c_1^{9}} [14 c_2^{4} - 21 c_1 c_2^2 c_3 + c_1^2[6 c_2 c_4+ 3 c_3^2] - 1 c_1^3 c_5],$$

which is the coefficient of the fifth order term of the power series for $h^{-1}(t)$. This 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).

This correspondence between the refined f-vectors of the n-Dim Stasheff polytope, or associahedron, and the coefficients of the (n+2)-th term of the compositional inverse holds in general, (see A133437, inversion for power series, and compare with A033282, coarse f-vectors for associahedra, and with MO-6373).

(If $h(z)$ is presented as a Taylor series, the LIF A134685 is obtained, which is related to A134991 [tropical Grassmannian G(2,n)], and using the reciprocal of $h(z)$, the LIF A134264 is obtained, which is related to the Narayana triangle A001263 [h-vectors of dual of associahedra].)

*Why (morally/intuitively, vague notion) do the refined face numbers of the associahedra appear as the coeficients of Lagrange inversion/reversion for a power series, or ordinary generating fct., as presented in OEIS A133437?*

Loday expresses a similar interest on page 15 of "The Multiple Facets of the Associahedron" in Sec. 6 Inversion of Power Series. He ends with *"There exists a short operadic proof of the above formula [LIF essentially] which explicitly involves the parenthesizings [of associahedra], but it would be interesting to find one which involves the topological structure of the associahedron."*

**One viewpoint**, for example: I can derive the LIF several ways and relate the methods to rooted trees and thence to associahedra, but is there an intuitive way to relate the LIF for compositional inversion (which is related to the Legendre transformation/Legendre-Fenchel transform) to the geometry of the associahedra through a geometrical view of optimization via integer programming? Compositional inversion and the Legendre transformation have geometrical interpretations and are related to optimization as discussed by Strang in his book Intro. to Applied Mathematics (see also Mathemagical Forests and references therein in the section A Walk With Lagrange and Legendre). De Loera, Rambau and Leal in Triangulations of Set Points in Sec. 1.2 Optimization and Triangulations discuss connections of secondary polytopes to optimization.

**Edit (2/2014):** Bayer and Lagarias in "The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories" on page 560 relate power series reversion (LIF) to optimazation problems over polytope domains, but these polytopes are not restricted to associahedra.

**Second viewpoint**: Stasheff associahedra are intimately related to the moduli spaces of colliding particles (Devadoss, Devadoss/Heath/Vipismakul, Devadoss/Fehrman/Heath/Vashist). String interactions generate the moduli spaces of Riemann surfaces (Zwiebach, A First Course in String Theory, pg. 310) with punctures corresponding to particles interacting on a line segment. There is much literature on the relations among compositional inversion/Legendre transformation, Feynman functional/path/gaussian integrals representing partition functions and sums over Feynman diagrams/graphs for point particle interactions (Connes/Marcolli's "Noncommutative Geometry, Quantum Fields and Motives" pg. 51, Borcherd pg. 34, Getzler, Manin, Abdesselam, Bergstrom and Brown). Are there analogous arguments directly in terms of sums over moduli spaces for string interactions [as for the beta integral for the Veneziano amplitudes (Zwiebach, pg. 311)] that circumvent the Feynman particle/stable graph interpretations and highlight more directly the connections between compositional inverses/Legendre transforms and the face polynomials of associahedra?

(See also MOQ 22291 and make the change of variables $x=f^{-1}(y)$ in Theo's integral and maybe a Wick rotation.)

I should have stressed earlier that refined face partition polynomials characterize the LI for o.g.f.s rather than the usual coarse face polynomials and that both sets of polynomials contain the Catalan numbers only as the number of vertices for an associahedron. The coarse polynomials are not sufficient to enumerate distinct higher dimensional facets corresponding to distinct partitions of the LI, much less the Catalan numbers alone.

Edit (Dec 2017): In a comment below Ian Agol references a recent paper by Aguiar and Ardila in which the following assertion can be found applying to generalized permutahedra of which Loday's realization of the Stasheff associahedra is one example:

Generalized permutahedra arise in a multitude of settings, and can be used to model many combinatorial objects: graphs, matroids, posets, set partitions, paths, and many others. In this section we present one reason for the ubiquity of these polyhedra: generalized permutahedra are equivalent to submodular functions, which are central objects in optimization. These functions occur in numerous mathematical and real-world contexts, since they are characterized by a diminishing returns property that is natural in many settings.

Enumerative Combinatorics, vol. 2, there are two proofs showing that LIF isequivalentto certain tree enumeration problems. The basic connection is the following: it is easy to see that inverting a power series $F(x)$ is equivalent to solving an equation of the type $xG(f(x))=f(x)$ for $f(x)$. This equation is an algebraic formulation of the recursive structure of a tree. $\endgroup$ – Richard Stanley Dec 19 '11 at 14:3612more comments