# Combinatorics question involving recurrence relations and n-gon

Find a recurrence relation for the number of ways to divide an n-gon into triangles with noncrossing diagonals.

The solution to this question is: $$a_n = a_{n-1}a_3 + a_{n-2}a_4 + ... + a_3a_{n-1}$$

I understand that $$a_4 = 2$$ and $$a_5 = 5$$ and $$a_6 = 14$$, but I'm confused on how I can continue this pattern to develop the recurrence relationship presented in the solution. In other words, I'm really not sure where the solution comes from...recurrence relations is a major struggle of mine.

I suspect your $$n$$-gon is regular (or at least convex).
The correct solution is $$a_n = a_{n-1} a_2 + a_{n-2} a_3 + \ldots + a_2 a_{n-1}$$, where we put $$a_2 = 1$$.
To get it, consider an $$n$$-gon $$P$$ with $$n > 3$$, and pick any two adjacent vertices $$A, B$$ in it. Now if $$P$$ is split into triangles, consider the vertex $$C$$ such that $$ABC$$ is one of these triangles. If we remove $$ABC$$ from $$P$$, we are left either with two polygons with a common vertex $$C$$ (thus if one of these polygons contains $$k$$ vertices, the other contains $$n + 1 - k\$$ vertices), or with a single polygon with $$n - 1$$ vertices. Conversely, if we take for $$C$$ any of the remaining $$n - 2$$ vertices, remove $$ABC$$ from $$P$$, and split the remaining polygons, we obtain a splitting of $$P$$. This explains the formula stated above, with the first and the last term corresponding to a single polygon left after removing $$ABC$$, and each of the remaining terms (if any) to a pair of polygons left.
In closed form, the solution is $$a_n=C_{n-2}=\dfrac{1}{n-1}\dbinom{2n-4}{n-2}$$.