Path to Combinatorics Problem [$1.11$] 
Problem: Let n be a positive integer greater than four and let $P_1P_2P_3..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 vertices of the polygon. In addition, he wants each triangular region to have at least one side that is a side of the polygon. In how many different ways can Zachary do this?

My attempt: I began with the case $n=5.$ I observed that the number of ways in which $3$ triangular regions can be constructed is $5$. I then went on to consider a hexagon and observed that the number of ways to partition was $(6-1)*5.$ Furthermore, I deduced for $n$ sided polygons we must have $(n-1)(n-2)...5*5$ ways to partition the polygon. I would like to know whether this answer is correct and if not, then a proof or a sketch would be much appreciated. 
 A: I have found that the number is $n \times 2^{n-5}$. I begin: I choose a vertice $P_i$ of the polygon (the number of ways is $n$). I draw a triangular region $P_iP_{i+1} P_{i-1}$. Then, I have two choices: draw $P_{i+1}P_{i+2}P_{i-1}$ or $P_{i-1}P_{i-2}P_{i+1}$,...
If I just draw $P_aP_bP_c$ (with $b>c$), I have two choices: $P_bP_{b+1}P_c$ or $P_cP_{c-1}P_b$. 
A: This is a slightly different analysis confirming marco2013’s result. Any such triangulation must have two triangles, each of which has two edges in common with the $n$-gon; say that the vertices adjacent to these edges are $u$ and $v$, and call these the poles of the partition. Let $P$ be the path consisting of the vertices of the $n$-gon between $u$ and $v$ going clockwise from $u$ to $v$ and the edges of the $n$-gon between those vertices, and let $Q$ be the path consisting of the vertices between $u$ and $v$ going counterclockwise from $u$ to $v$ and the edges of the $n$-gon between them.
Every internal edge of the triangulation must join a vertex in $P$ with a vertex in $Q$, and the triangles are in a loose sense parallel: the line segment $\overline{uv}$ passes through each of them exactly once. Each of the triangles not containing $u$ or $v$ has exactly one edge in common with the $n$-gon; some of these edges are in $P$, and some are in $Q$. If we label each of the triangles not containing $u$ or $v$ with $p$ if it has an edge in $P$ and with $q$ if it has an edge in $Q$, traversing the line segment $\overline{uv}$ from $u$ to $v$ uniquely determines a sequence of $p$s and $q$s.
If there are $k$ edges of the $n$-gon in $P$, there are $n-4-k$ edges of it in $Q$, there are $\binom{n-4}k$ possible sequences, each corresponding to a unique partition with poles $u$ and $v$, and each partition with poles $u$ and $v$ corresponds to a unique one of these sequences. For a fixed choice of pole $u$ there are therefore
$$\sum_{k=0}^{n-4}\binom{n-4}k=2^{n-4}$$
possible partitions. There are $n$ possible choices for $u$, and each partition has two poles, so there are
$$\frac{1}2n\cdot 2^{n-4}=n2^{n-5}$$
possible partitions of the desired type. (Note that the analysis is actually correct even for $n=4$.) The following rough sketch may be helpful.

A: (Copied from a duplicate of this question, in case it gets deleted there.)
It has been proven above by Brian M. Scott  that there are $n\cdot2^{n-5}$ admissible triangulations. A  simpler proof goes as follows:
There are exactly two triangles $\triangle_1$, $\triangle_{n-2}$ having two sides on $\partial P$, and the remaining $n-4$  triangles form an ordered chain in between them. The structure of this chain can be encoded as an $\{L, R\}$-word of length $n-4$, supplemented with $\triangle_1$ and $\triangle_{n-2}$ at the ends, whereby $L$ (resp., $R$) means that the corresponding triangle has its $\partial P$-side   to the left (resp., to the right) of the "virtual backbone" connecting $\triangle_1$ with $\triangle_{n-2}$. 
An example: When $n=9$ then such  a codeword could look like $\ \triangle_1\,RRLRL\>\triangle_7$. 
Given such a codeword the corresponding chain of triangles can be embedded in $n$ ways into $P$. Since reversing the orientation of the "backbone" and at the same time interchanging $L$ and $R$ leads to equal triangulations we have to divide the obtained total $n\cdot 2^{n-4}$ by $2$ in order to get the correct number of triangulations.
