Consider the $n-3$ diagonals. Since no diagonals intersect, for any diagonal there can be at most one diagonal directly to the left or right, so it makes sense to say two diagonals are adjacent. Two adjacent diagonals create a sub-polygon within the $n$-gon - two sides being diagonals and the rest being sides of the $n$-gon. If we start with any diagonal then move to the diagonal to the left, and to the left again we will eventually find a diagonal that has no other diagonals to its left, hence it must form a sub-polygon with one diagonal (itself) and some edges of the $n$-gon. Similary for the right side. Now all together the diagonals form $n-2$ sub-polygons. Each edge of the $n$-gon has a unique sub-polygon, and every diagonal is an edge in two sub-polygons. So we have a total of $n + 2(n-3) = 3(n-2)$ edges for $n-2$ sub-polygons, so all the sub-polygons are triangles. To find the number of triangulations we first select one vertex, $v_{i}$, in the $n$-gon to form a triangle at the end. Then connect the two vertecies either side of this vertex, $(v_{i-1},v_{i+1})$. Now when ever we have a diagonal $(v_j,v_k)$ we can either connect $(v_j,v_{k-1})$ or $(v_{j+1},v_k)$ but not both. We start with three vertecies already selected the last vertex is determined the previous $n-4$ decisions. We also double counted because there are two end triangles. Finally we have $n2^{n-5}$ Edit: yes sorry, i made a mistake working the case $n=6$ which messed me up. I believe it is correct now

ocha wrote: Finally we have $n2^{n-5}$ for n odd and $n2^{n-6}$ for n even. Actually the answer for all $n\in\mathbb{N}$ is $n\cdot 2^{n-5}$.

Hello, why isn't the answer the (n-2)nd Catalan number?