What is an associahedron?
The terms of the sequence a[n] which counts the number of ways in which we can bracket (or associate) (n+1) factors are known as the Catalan Numbers. In class we learned that the Catalan Numbers satisfy the following recurrence relation:
a[n]=a[0]a[n-1] + a[1]a[n-2] + a[2]a[n-3] + ... + a[n-1]a[0] with a[0]=1 and a[1]=1.
This allowed us to find an actual formula for the terms of this sequence, namely a[n]=C(2n,n)/(n+1).
For example, a[4]=C(8,4)/5=14. That is, there are 14 different ways to bracket 5 factors:
1. a(b((cd)e))
2. a(b(c(de)))
3. a((bc)(de))
4. a((b(cd))e)
5. a(((bc)d)e)
6. (ab)(c(de))
7. (ab)((cd)e)
8. (a(bc))(de)
9. ((ab)c)(de)
10. (a(b(cd)))e
11. (a((bc)d))e
12. ((ab)(cd))e
13. ((a(bc))d)e
14. (((ab)c)d)e
The solid called associahedron contains one vertex for each of these 14 bracketing patterns. Notice that each pattern contains three pairs of brackets. The associahedron features an edge between two vertices precisely if the two bracketing patterns that correspond to these two vertices differ by only one set of brackets. For example, Pattern 3 and Pattern 8 above differ only by one pair of brackets. Therefore, Vertex 3 and Vertex 8 are connected by an edge in the associahedron. Moreover, the collection of patterns that share one particular pair of brackets correspond to vertices of a face (i.e. a side) of the associahedron. For example, Patterns 1 through 5 all have the bracket pair a(bcde) in common. Therefore, Vertices 1 trhough 5 form a pentagonal side of the associahedron. Similarly, Patterns 8, 9, 13, 14 are the only patterns using the bracket pair (abc)de. Hence, Vertices 8, 9, 13, and 14 form the vertices of a parallelogram on the associahedron. The associahedron has 14 vertices, 21 edges, and 9 faces. It features six pentagons and three parallelograms.
Project
Build your own associahedron and match its 14 vertices with the 14
bracketing patterns listed above. Then label each face of the associahedron
with its corresponding bracket pair.