I know there is a solution here: Combinatorics question involving recurrence relations and n-gon
I am having trouble understanding it though.
Find a recurrence relation for the number of ways to divide an $n$-gon into triangles with non-crossing diagonals.
I know that when $n=4$, there are $2$ ways to do this.
When $n=5$, I found there are $8$ ways of doing this.
So far for $n=6$, I have $10$ ways of doing this.
I am stuck on finding the recurrence relation.
On
I am going to try to expand upon and clarify the linked solution for you. I want to give credit where credit is due to @metamorphy. If you give this an upvote, make sure to give them one too.
We are going to divide an $n$-gon into triangles. In any such triangulation there is always at least one triangle that has two vertices that are adjacent on the $n$-gon. This is not obvious, but I will prove it at the bottom. Let the two adjacent vertices be $A$ and $B$. In the triangulation, we'll call the third vertex of the triangle $C$. This triangle could divide the $n$-gon into two others polygons (as in the left figure below), or if $C$ is adjacent to either $A$ or $B$, the triangle $ABC$ will not divide the polygon (as in the right figure below).
$\hskip2in$
We know that $ABC$ is a triangle in our triangulation so now we just need to triangulate the remaining (one or two) polygon(s). If our choice for $C$ did $\textit{not}$ divide the polygon (like the right figure above), then the number of triangulations is just $a_{n-1}$, as the remaining polygon is just an $(n-1)$-gon. This situation occurs two different ways: if $C$ is adjacent to $B$ (as in the figure) or if $C$ is adjacent to $A$. So the number of triangulations is $$ 2(a_{n-1}) $$ If our choice of $C$ $\textit{did}$ divide the polygon into two remaining polygons, then we must triangulate the remaining polygons. The polygon's sides will add up to $(n+1)$, but depending on our choice of $C$ this could divide the $n$-gon into an $(n-2)$-gon and a $3$-gon, an $(n-3)$-gon and a $4$-gon, ... , or a $3$-gon and a $(n-2)$-gon. These are all distinct possible triangulations, so the number of triangulations is $$a_{n-2}a_3+a_{n-3}a_4+...+a_4a_{n-3}+a_3a_{n-2}$$ Adding these two possibilities we get $$ a_n=2(a_{n-1})+(a_{n-2}a_3+a_{n-3}a_4+...+a_4a_{n-3}+a_3a_{n-2}) $$ If we define $a_2=1$ and $a_1=0$ (it makes no sense to triangulate a shape with two or less sides since these shapes don't exists), then we can rearrange the sum into$$ a_n=a_{n-1}a_2+a_{n-2}a_3+...+a_3a_{n-2}+a_2a_{n-1}=\sum^{n-1}_{i=2}a_ia_{n-i+1} $$ These are a well studied group of numbers called the Catalan numbers $C_n$. Here, $$ a_n=C_{n-2} $$
If we choose one vertex against one side, reminders are $n-i-1$ and $i-1$ polygons. From this, we get asked recurrence.