**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.