Figure 1: The Catalan Numbers

The nth Catalan number counts the ways of dissecting a polygon with n+2 sides into triangles by drawing nonintersecting diagonals. All such dissections are shown here for polygons with three, four, five and six sides; the next polygon, the heptagon, has 42 dissections, and the octagon has 132. The Catalan numbers also appear in many other areas of graph theory and combinatorics. For example, the nth Catalan number is the number of planar binary trees with n nodes.