Solution
Triangulating an Octagon
Show the problem again
A convex octagon is to be divided into triangles by drawing diagonals that do not cross in the interior. (Any such triangulation uses exactly 5 diagonals.) Different sets of diagonals count as different triangulations, even if one is a rotation of another. How many triangulations are there? Give an integer.
Worked solution
**Answer: 132.** Let T(n) be the number of triangulations of a convex (n + 2)-gon, with T(0) = 1 for a degenerate "2-gon". Fix one side of the polygon. In any triangulation it lies in exactly one triangle, whose third vertex splits the rest of the polygon into two smaller polygons that are triangulated independently. This gives Segner's recurrence T(n) = Σ_{k=0..n−1} T(k) T(n − 1 − k). That is the Catalan recurrence, so T(n) = C_n = (1/(n+1)) C(2n, n): 1, 1, 2, 5, 14, 42, 132. An octagon has n = 6, giving 132.
Source: Euler's polygon-division problem (1751), solved via Segner's recurrence. Statement written for AxiomIQ.