I got $n \cdot 2^{n-9}\cdot \binom{n-4}{4}$ for $n \ge 8$. Is that correct? I think I have got a proof for that, but it is easy to make mistakes when counting possibilities...

Lemma 1: A polygon with $ n$ vertices has all its sides colored red except one which is blue. Then the number of triangulations of the polygon such that each triangle contains at least one red side is $ 2^{n-3}$. The proof is by induction on $ n$. $ n=3$ is obvious. Now for $ n>4$ the triangle that contains the blue side must also contain exactly one of the red sides adjacent to it. We get two cases. In each case by removing this triangle we can apply the induction step to get $ 2^{n-4}$ possibilities, for a total of $ 2^{n-3}$. Lemma 2: A polygon with $ n$ vertices has all its sides colored red except two which are blue. It is known that we have $ k$, respectively $ l$ consecutive red sides ($ k+l=n-2$). Then the number of triangulations such that each triangle contains at least one red side if $ \binom{k+l}{k}$. The proof may be done by induction on $ n=k+l+2$. If we denote by $ f(k,l)$ the given function then as the triangle containing one of the blue sides must contain one of the red adjacent sides we get $ f(k,l)=f(k,l-1)+f(k,l-1)$. A combinatorial proof is also possible: Assign plus to a triangle that contains one red side from the $ k$ and minus to a triangle that contains one red side from the $ l$. Starting from the blue side, we can visit all triangles (we go from one triangle to the next that shares a diagonal with it and was not already visited). We shall encounter a defining sequence of $ k$ pluses and $ l$ minuses in some order which may be chosen in $ \binom{k+l}k$ ways. Also note that lemma 1 follows from lemma 2 if we cut the unique triangle containing two consecutive red sides. These two lemmas provide the key to the solution. Color the sides of the polygon red and the diagonals of the two interior triangles blue. The polygon will be split into the two interior triangles, four regions that have one blue side and one region with two blue sides (all the other sides are red, the last region may be empty). Let the four regions considered have $ a,b,c,d$ red sides and the last region have $ i$ and $ j$ consecutive red sides, $ a+b+c+d+i+j=n$. Then according to the lemmas we have $ 2^{a-2}2^{b-2}2^{c-2}2^{d-2}\binom{i+j}{j}=2^{n-i-j-8}\binom{i+j}{j}$ ways to complete the triangulation. We also design a plan to count the triangulations. We can firstly find the $ i$ sides then find $ j$ then compute $ a+b$ then $ c+d$ and finally get $ a,b,c,d$. Each triangulation will occur exactly two times (namely, we could swap the two interior triangles and get the same configuration). So let's compute the total number of possibilities following the plan. Now assume that we've found the two blue sides. We thus know $ k=a+b, l=c+d, i, j$. It is clear that $ a,b$ and $ c,d$ may be chosen in $ k-3, l-3$ ways because $ a,b,c,d\geq 2$. So we get $ (k-3)(l-3)2^{n-i-j-8}\binom{i+j}{j}$ ways. Now set $ h=i+j$, then $ l=n-h-k$ so $ (k-3)(l-3)=(k-3)(n-h-k-3)=-k^{2}+k(n-h)-3(n-h-3)$. Also $ 4\leq k \leq n-h-4$. Next, we can place the $ i$ consecutive red sides in $ n$ ways, then we may choose $ 4\leq k\leq n-h-4$. The next $ j$ red sides will form the next group and the remaining will form the last group. So we shall have a total of $ n\cdot 2^{n-h-8}\binom{h}{i}\sum_{k=4}^{k=n-h-4}(-k^{2}+k(n-h)-3(n-h-3))$ ways. It can be computed as $ n\cdot 2^{n-h-8}\binom{h}{i}\frac{s(s-1)(s+1)}6$ where $ s=n-h-6$ (we may prove that $ \sum_{a+b=s, a,b \in N}ab=\frac{s(s-1)(s+1)}6$). So we get $ n\cdot 2^{n-h-8}\binom{h}{i}\frac{s(s-1)(s+1)}6$. Next as $ i$ may take values from 0 to $ h$ and $ \sum_{i=0}^{h}\binom{h}{i}=2^{h}$, the sum over all $ i$ will be $ \cdot n2^{n-h-8}2^{h}\frac{s(s-1)(s+1)}6=n\cdot 2^{n-8}\binom{s+1}3$. Finally $ s$ may take values from $ 2$ to $ n-6$. And we know $ \sum_{s=0}{m}\binom{s}{3}=\binom{m+1}{4}$. So we get from here that the total sum is $ n\cdot 2^{n-8}(\binom{n-4}{4}-\binom{3}{4})$. Next we need to divide by 2 because every triangulation was computed twice, as we could start with either of the two sets of consecutive red sides. We get $ n\cdot 2^{n-9}\cdot \binom{n-4}{4}$. The same result as yours

My solution avoids calculations almost completely: First some notation: Denote the interior triangles by $ A_{1}A_{2}A_{3}$ and $ B_{1}B_{2}B_{3}$ such that the sides $ A_{1}A_{2}$ and $ B_{1}B_{2}$ are facing each other. There is a tower of (say $ i$) triangles in between $ A_{1}A_{2}$ and $ B_{1}B_{2}$ and there are towers of triangles on each of the remaining sides $ A_{2}A_{3}$, $ A_{3}A_{1}$, $ B_{2}B_{3}$ and $ B_{3}B_{1}$, say consisting of $ j+1,k+1,m+1$ and $ l+1$ triangles (every such tower contains at least one triangle. Otherwise the triangles $ A_{1}A_{2}A_{3}$ and $ B_{1}B_{2}B_{3}$ wold not be interior triangles.) Now first choose $ A_{3}$. This can be done in $ n$ ways. Furthermore we have to keep in mind that we will count each triangulation twice (interchanging the roles of the two interior triangles.) Now let us fix values of $ i,j,k,m,l$. The only condition these numbers are required to satisfy is that they should be integers $ \ge 0$ and that the resulting polygon should have $ n$ points. By simple counting this can be seen to be equivalent to the condition \[ 1+(j+1)+(k+1)+(i+2)+(l+1)+(m+1)+1 = n, \] i.e. \[ i+j+k+l+m = n-8. \] For fixed $ i,j,k,m,l$ satisfying these conditions the number of triangulations can easily be calculated: Each tower of triangles can be constructed from the bottom line by addinga triangle in each step and determining which of the remaining two sides will be the outer side (= side of the given polygon) (the other one has to be the interior side = diagonal of the given polygon), for the topmost triangle both remaining sides have to be outer sides. (Of course for the triangulation in between the two interior triangles there is no topmost triangle.) Thus altogether the number of triangulations is \[ 2^{i}\cdot 2^{j}\cdot 2^{k}\cdot 2^{l}\cdot 2^{m}= 2^{i+j+k+l+m}= 2^{n-8}. \] However the number of possible choices for $ i,j,k,l,m$ is just the number of partitions of $ n-8$ into a sum of 5 natural numbers, which is just \[ \binom{n-8+4}{4}= \binom{n-4}{4}. \] To summarize the number of triangulations of the given polygon with the given properties is \[ n \binom{n-4}{4}2^{n-8}/ 2 = n \binom{n-4}{4}2^{n-9}. \]