A6. Counting Triangulations

Here is a counting problem that was solved a long time ago. Feel free to try your hand at it.

Given P, a convex n-gon, a triangulation of P is a subdivision of P into n - 2 non-overlapping triangles. A triangulation is obtained by drawing n - 3 non-intersecting diagonals. Let f(n) be the number of different triangulations. Clearly, f(3) = 1, f(4) = 2, and f(5) = 5. Careful counting shows f(6) = 14. Find an expression for f(n).