23.4.2. Recurrence Relation for Triangulations

Try these first

1. 1.

   What is the initial condition for T(0)?

   Hint

   Think about the number of ways to form a triangulation when there are no sides.

2. 2.

   How many structurally different full binary trees are there with three leaves?

   Hint

   Consider the arrangements of branches.

3. 3.

   How many full binary trees exist with 4 leaves?

   • 1
   • 2
   • 5

   Hint

   Think about how arrangements can change.

4. 4.

   True or False: The 3rd Catalan number is 5.

   • True
   • False

   Hint

   Recall the list of Catalan numbers.

5. 5.

   Prove that the number of triangulations of a convex polygon with n sides corresponds to the nth Catalan number.

   Hint

   Start by showing simple cases and building up.

6. 6.

   If a polygon's triangulation patterns were altered, hypothesize how the changes could affect the corresponding Catalan number.

   Hint

   Think about howpolygonal shapes change the arrangement.