The f-polynomials, $F_n(x)$ (cf. OEIS A126216, A033282, and A086810), and the h-polynomials, $H_n(x)$ (cf. A001263, the Narayana polynomials), of the family of simple convex polytopes the associahedra for the Coxeter group $A_n$, or Stasheff polytopes, are related by the simple analytic equation

$$F_n(x-1) = H_n(x).$$

McCammond in "Noncrossing partitions in surprising locations" presents a geometric/combinatoric path between the f- and h-polynomials of associahedra.

The f-polynomial $F_n(x)$ enumerates (is the o.g.f. of) the number of k-dimensional faces of the n-dimensional associahedron. Refined, signed versions of the f-polynomials for the associahedra, enumerating and labelling to a finer degree the faces of the associahedra, are given in A133437 as

$$FP_n(a_1,a_2,...) = (1/n!) [g(x)D_x]^n x|_{x=0}$$


$$g(x) = 1 / D_x f(x)= 1/ [a_1 + 2a_2 x + \cdots].$$

These partition polynomials give the coefficients of the power series that is the formal compositional inverse of the formal power series, or ordinary generating functions (o.g.f.s),

$$f(x) = a_1 x + a_2 x^2 + \cdots $$

and also correspond to enumerating dissections by polygons of polygons (see "Polygonal dissections and reversions" by Schuetz and Whieldon) as well as aspects of other combinatorial constructs, such as the Dyck lattice paths of A126216. For some more details see A145271, MO-Q, and MO-A.

The corresponding h-polynomials for the associahedra enumerate noncrossing partitions, and the corresponding refinement A134264 gives the partition polynomials $HP_n(b_0,b_1,...)$ for the compositional inverse of $f(x)$ in terms of the coefficients of the power series for the reciprocal

$$h(x) = x / f(x) = b_0 + b_1x + b_2 x^2 z + \cdots .$$

These partition polynomials are generated by

$$HP_n = (1/n!)[g(x)D_x]^n x|_{x=0}$$


$$g(x) = 1 / D_x [f(x)] = 1/ D_x[x/b(x)]$$

$$ = 1 /D_x [x/[b_0 + b_1 x + \cdots]]$$

and enumerate and label to a finer degree the noncrossing partitions as well as the Dyck lattice paths A125181. For examples of the enumeration and labelling, see "Appell polynomials, cumulants, noncrossing partitions, Dyck paths, and inversion" at my blog site.

Analytically, the refined f- and h-partition polynomials are related by the partition transformation A263633, a refined binomial convolution, connecting the indeterminates $a_n$ to $b_n$.

Question: What are some purely geometric/combinatoric paths/transformations, as opposed to the analytic path/transformation just skeched, between the refined f-an h-partition polynomials?

  • 1
    $\begingroup$ I am not sure I understand you correctly: would an answer to the question "why is the h-polynomial of the associahedron equal to the generating function of noncrossing set partitions according to the number of blocks?" be satisfying? $\endgroup$ – Christian Stump Jun 5 '18 at 7:53
  • $\begingroup$ @ChristianStump, I revised and generalized the question. Hope it's clearer now. $\endgroup$ – Tom Copeland Jun 6 '18 at 0:22
  • $\begingroup$ Okay, I don't know about these refined versions, sorry -- I plan to take a closer look over the summer... $\endgroup$ – Christian Stump Jun 6 '18 at 8:49
  • $\begingroup$ @ChristianStump, the description of the enumeration and labelling of noncrossing partitions and Dyck paths in my blog post might be helpful. $\endgroup$ – Tom Copeland Jun 6 '18 at 17:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.