1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ I want to say that there is an assumption here that is not non-trivial: for any triangulation of a polygon, there is always at least one triangle that has two adjacent vertices. This is assumed in the explanation, but it is not obvious, even though it is true. $\endgroup$ – Joey Kilpatrick Nov 6 '18 at 3:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.