First a little background for those unaware. The Stasheff polytopes (or associahedra) are certain convex polytopes that arise in the theory of $A\_\infty$-algebras. There is one polytope for each $n\geq 2$ and is denoted by $K\_n$. The $K\_n$'s essentially encode the homotopies, higher homotopies and so on of the associativity relation. One way to describe $K\_n$, which is has dimension $(n-2)$, is to take all rooted binary trees with $n$ leaves and take a *suitable* convex hull. For example, $K\_2=\{\ast\}$, $K\_3$ is an interval while $K\_4$ is a pentagon. 


It is known that the number of vertices $v$ of $K\_n$ is the $(n-1)^{th}$ Catalan number, i.e., $v=\frac{1}{n}{2n-2 \choose n-1}$. What can one say about the number of edges of $K\_n$ and generally about counting faces of all codimension? 



Combinatorics of the Stasheff polytopes
After a change of variables, the answer is [sequence A033282](http://www.research.att.com/~njas/sequences/A033282) in the Encyclopedia of Integer Sequences: $T(n,k)$ is the number of diagonal dissections of a convex $n$-gon into $k+1$ regions. The page gives the wonderful formula,
$$T(n,k) = \frac{1}{k+1}\binom{n-3}{k}\binom{n+k-1}{k},$$
for relevant values of $k$.


I find it easier to also keep track of the dual Stasheff polytope, which can be realized as a simplicial complex based on dissections of a convex polygon. The polytope $K\_n^\*$ has a vertex for each diagonal of an $(n+1)$-gon, and it has a face for every collection of disjoint diagonals. So, in terms of your original parameters, $K\_n$ has $T(n+1,n-2-k)$ faces of dimension $k$.


Also: One reason that I like the dual Stasheff polytope is that it has an amazing infinite generalization called the Hatcher-Thurston arc complex. You again take collections of disjoint arcs that connect marked points, but in the generalization you can take any surface with or without boundary, as long as it has at least one marked point total and at least one on each boundary component. (And I suppose in the disk case it needs at least three marked points.) Each isotopy class of arcs is a vertex, and each disjoint collection is a face. It is a combinatorial model of Teichmüller spaces or moduli spaces of curves (with the requisite marked points).




---


Gil Kalai in the comments asks for a few more details of the Hatcher-Thurston arc complex, and he gives a reference to one of the original papers, "On triangulations of surfaces, Topology Appl. 40 (1991), 189–194," by Allen Hatcher. Briefly: Suppose that $\Sigma$ is a fixed surface with some marked points. There should be enough marked points so that there exists at least one generalized triangulation of $\Sigma$ whose vertex set is the marked points. A question that could be taken as motivation is the following: Can you find a complete set of moves on triangulations, moves on moves, moves on moves on moves, etc.? Whether the set of moves is complete is not entirely a rigorous question, but there is an interesting answer. The moves and higher moves just come from erasing edges of the triangulation. The main theorem is that the resulting simplicial complex is contractible. The mapping class group acts on the complex, and it acts freely on the high-dimensional simplices.


More precisely, the arc complex has a vertex $v$ for every isotopy class of an arc between two of the marked points, among properly embedded arcs that miss all of the marked points in the interior. If a collection of arcs can be made disjoint after isotopy, then the corresponding vertices subtend a simplex. The disk case is an exception in which the arc complex is not quite contractible, but rather a sphere.


