Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A convex polygon with sides is to be cut into triangles by drawing diagonals that do not cross inside it. A second question looks different. On a grid, a path goes from the corner to the corner in unit steps to the right or up. It may touch the diagonal but never go above it.
Both questions are counted by Catalan numbers. Say which Catalan number answers each one and find both counts. Use , and explain why a polygon with sides goes with .
with and , and is the whole number nearest to . The Catalan numbers are .
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. Why sides give . Fix one side of the polygon. In any triangulation it lies in one triangle, whose third corner splits the rest into two smaller polygons. This gives the Catalan recurrence , where counts the triangulations of a polygon with sides and for a single side.
Step 2. The polygon. , so the count is .
Step 3. The paths. The paths to are .
Check. A pentagon has triangulations, which a quick drawing confirms.
Answer: triangulations and paths.
Log in to join the discussion.
Loading…