In mathematics, an associahedron Kn is an (n − 2)-dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a word of n letters and the edges correspond to single application of the associativity rule. Equivalently, the vertices of an associahedron correspond to the triangulations of a regular polygon with n + 1 sides and the edges correspond to edge flips in which a single diagonal is removed from a triangulation and replaced by a different diagonal. Associahedra are also called Stasheff polytopes after the work of Jim Stasheff, who rediscovered them in the early 1960s after earlier work on them by Dov Tamari.
The one-dimensional associahedron K3 represents the two parenthesizations ((xy)z) and (x(yz)) of three symbols, or the two triangulations of a square.
The two-dimensional associahedron represents the five parenthesizations of four symbols, or the five triangulations of a regular pentagon. It is itself a pentagon.
The three-dimensional associahedron K5 is an enneahedron with nine faces and fourteen vertices, and its dual is the triaugmented triangular prism.
Initially Jim Stasheff considered these objects as curvilinear polytopes. Subsequently, they were given coordinates as convex polytopes in several different ways; see the introduction of Ceballos, Santos & Ziegler (2015) for a survey.
One method of realizing the associahedron is as the secondary polytope of a regular polygon. In this construction, each triangulation of a regular polygon with n + 1 sides corresponds to a point in (n + 1)-dimensional Euclidean space, whose ith coordinate is the total area of the triangles incident to the ith vertex of the polygon. For instance, the two triangulations of the unit square give rise in this way to two four-dimensional points with coordinates (1, 1/2, 1, 1/2) and (1/2, 1, 1/2, 1). The convex hull of these two points is the realization of the associahedron K3. Although it lives in a 4-dimensional space, it forms a line segment (a 1-dimensional polytope) within that space. Similarly, the associahedron K4 can be realized in this way as a regular pentagon in five-dimensional Euclidean space, whose vertex coordinates are the cyclic permutations of the vector (1, 2 + φ, 1, 1 + φ, 1 + φ) where φ denotes the golden ratio. Because the possible triangles within a regular hexagon have areas that are integer multiples of each other, this construction can be used to give integer coordinates (in six dimensions) to the three-dimensional associahedron K5; however (as the example of K4 already shows) this construction in general leads to irrational numbers as coordinates.