Triangulation of a convex n-gon so that all triangles share a side with the polygon So I was reading A Path to Combinatorics for Undergraduates by Titu Andreescu and Zuming Feng, and I came across this question:

Let n be an integer greater than $4$, and let $P_1 P_2 \ldots P_n$ be a convex $n$ sided polygon. Zachary wants to draw $n-3$ diagonals that partition the region enclosed by the polygon into $n-2$ triangular regions and that may intersect only at the vertices of the polygon, In addition, he wants each triangular region to have at least $1$ side that is also a side of the polygon. In how many ways can Zachary do this?

After researching a bit i found out that $C_{n-2}$ (the $(n-2)^{\text{th}}$ Catalan number) counts the number of triangulations for a convex n-sided polygon, but I don't know how to account for the triangulations that have triangles which don't have a side in common with the polygon. I would really appreciate it if someone could help me solve the problem.
 A: The answer is $n \cdot 2^{n-5}$. Fix the side $P_1P_2$ and we first observe that this side must appear in one of the triangles. Let's say that it appears in the triangle $P_1P_2P_i$, with $3 \le i \le n$. This triangle divides the $n$-agon in two polygons (or one when $i = 3$ or $i = n$), one with $i - 1$ sides and the other with $n - i - 2$ sides.
Assume first that $i = 3$ (the case $i = n$ is similar). The remaining polygon is $P_1P_3P_4 \ldots P_n$ and we should triangulate it. The side $P_1P_3$ should be present in one of the triangles and the third vertex of this triangle must be $P_4$ or $P_n$, otherwise, we would get a triangle without any side in common with the original polygon. So we have $2$ possibilities at this point and if we continue with a similar reasoning, it's easy to see that we will have $2^{n-4}$ possibilities if $i = 3$.
If $i = n$, we also have $2^{n-4}$ possibilities and if $3 < i < n$, we now have indeed two polygons and by a similar argument, we have $2^{i-4} \cdot 2^{n-i-1} = 2^{n-5}$ possibilities for each $i$.
Therefore the total number of triangulations with the required property is
$$
2^{n-4} + (n-4)2^{n-5} + 2^{n-4} = n \cdot 2^{n-5}.
$$
