# Why do polytopes pop up in Lagrange inversion?

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 the recent paper "Hopf monoids and generalized permutahedra" 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.

• Tom- This could expanded on a lot. I think asking a question like "Why do X show up in Y?" without explaining or providing a link for your audience to find out how X shows up in Y is both generally not cool and brings down the probability that you will get an answer or any back and forth at all. People who don't instantly know what connection you have in mind just ignore you, or leave long aggrieved comments (at best). You don't have to explain every detail, but providing more links (Don't mention your previous questions, link to them!) would be a good start. Oct 11, 2011 at 0:39
• I find this question potentially interesting, and I have some knowledge of various potentially relevant things. However, I agree with other commenters that more effort from the OP is required to summarise the phenomena for which he seeks insight. In fact, I suspect that the process of writing such a summary would help him to find that insight. Oct 11, 2011 at 4:29
• Rather than echo the previous sentiments (although I agree with them), let me ask: have you read anything about Lagrange inversion in terms of combinatorial species? The original paper, Une theorie combinatoire des series formelles by Joyal (Adv. Math. 42, 1-82, 1981), gives a combinatorial interpretation of Lagrange inversion which does involve rooted trees. I'd have a look there, perhaps. Oct 11, 2011 at 10:46
• I don't think this is very deep, one just needs to sit down and examine the role trees play in the LIF and with associahedron face numbers you mentioned. From looking at A133437 it seems you are counting dissections of a polygon. I don't know about partial dissections into regions, but if you completely dissect into triangles than there is an obvious bijection with planar binary trees. It is one of the zillion ways Catalan numbers appear in combinatorial enumeration. I did not check that, but dissections into regions seem to involve trees with vertices of arbitrary degree and so does the LIF. Oct 11, 2011 at 17:02
• Echoing the sentiments of Abdelmalek, in Section 5.4 of my book Enumerative Combinatorics, vol. 2, there are two proofs showing that LIF is equivalent to 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. Dec 19, 2011 at 14:36