Arrangements and Combinations · Catalan Numbers: Various Manifestations

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Triangulations. In the problem of counting the number \(T(n)\) of ways to triangulate a regular \(n\)-gon, the recurrence relation is slightly different. Fix one of the sides of the \(n\)-gon and consider which triangle it belongs to.

To the left and right of this triangle, there are \(l\) and \(r\) vertices. Here, \(l+r=n+1\): the vertex of the triangle opposite the fixed side is part of both new polygons. Thus, \[T(n) =\sum_{l=2}^{n-1}T(l)T(n+1-l)\] Also, \(T(0)=T(1)=T(2)=T(3)=1\). Therefore, \(T(n)=C(n-2)\).

Note that we glossed over an important detail above: when transitioning to smaller subproblems, the resulting \(l\)-gon and \(r\)-gon are no longer regular. To make the reasoning rigorous, \(T(n)\) must be redefined as the number of ways to triangulate a convex \(n\)-gon.