Problem
COM-B2-M03-P019 Catalan Objects
Construct a bijection between correct parenthesis sequences with \(n\) pairs of parentheses and triangulations of a convex \((n+2)\)-gon, using the recursive description: the first pair of parentheses determines the triangle adjacent to a fixed side.
Use the same recursion: the object splits into a left and a right part.
Fix a side of the polygon. In any triangulation, there is a unique triangle adjacent to this side; its third vertex splits the polygon into two smaller parts. Similarly, every correct parenthesis sequence is uniquely written as \((A)B\), where \(A\) and \(B\) are correct sequences. Choose the third vertex so that the number of pairs in \(A\) equals the number of triangles in the left part, and \(B\) corresponds to the right part. Applying the same rule recursively gives a bijection. The base case \(n=0\) is clear.
No need to draw all cases; the key is the shared recursive structure.