Any colouring using all 3 colors and satisfying that any edge has two different colors should work. Counting these colorings should not be hard. To prove this is necessary; clearly we need all 3 colors. If any edge has both of the same color, note that there exists points in the polygon which, if contained in a triangle like in the question, must have that this triangle contains this edge (just take vertices super close to the middle of the edge; to rigorously prove the edges are needed, note that deleting either vertex takes a sufficiently close point out of the convex hull of the remaining points.) Hence no edge can be coloured with both the same color. To prove sufficiency; clearly there exists 3 consecutive points of all different colors. Now we will cover the polygon with disjoint triangles and quadrilaterals, all of which satisfy that all of its interior and boundary points are in a rainbow triangle. Indeed, just keep on triangulating by picking the “next consecutive vertex” on the polygon that has not been picked yet; if it is of a different color with the two vertices of the outermost diagonal or edge between chosen points then we may continue the triangulation; otherwise we have a quadrilateral with vertices coloured WLOG G B G B; but all such quadrilaterals are completely covered by rainbow triangles (consider any other red point and the four triangles it makes with the vertices of this quadrilateral); hence we may also contain this quadrilateral and continue our “triangulation”. (I am on phone right now, can make this precise later)

Another way to prove sufficiency is just by induction. The base case with $n=3$ is trivial. As above, there exists a sequence of the form RGB on the border. So, removing the G the inductive hypothesis is satisfied and we are done (and of course any point in that exterior triangle is ok because it has all three colours). Now, to find the actual number, assign red green and blue to $0,1,2\pmod{3}$. Assuming wlog the first ball is red (and then multiplying everything by three), this is like finding the sum of the coefficients of powers $x^{3k}$ in the function $(x+\frac{1}{x})^n$ (we always have to change the color, meaning we must go up or down by one $\pmod 3$). Therefore, by ROU filter, the result is $$3\cdot\frac{(1+1)^n+(\omega+\omega^{-1})^n+(\omega^{-1}+\omega)^n}{3}=2^n+2(-1)^n$$where $\omega=e^{\frac{2\pi i}{3}}$ is a third root of unity.

cadaeibf wrote: So, removing the G the inductive hypothesis is satisfied and we are done Are you sure that this works? What about $RGBRBRBRBRB$? Then if you remove the $G$, you clearly lose the property since there is no more $G$. But indeed it is easy to fix this argument: It only goes wrong if there is no other $G$. But then clearly all the triangles with the one $G$ and an opposite side $RB$ or $BR$ cover the whole polygon and we are done directly. On another note, there is a minor flaw in your final result: You only count those configurations where the edges are not of the same colour. You still need to subtract those configurations where you end up with only two colours used. If $n$ is odd, this is impossible, so your result holds, but if $n$ is even, there are six such configurations, so the correct result would be $2^n-4$ in that case.

The answer is $2^n - 3 - (-1)^n$ Label the polygon $A_1,\cdots,A_n$ with these vertices in clockwise order. One can realize that if $A_i, A_{i+1}, A_{i+2}$ have p/w different colors, we can check the thing on the polygon minus $A_{i+1}$ (ie the polygon $A_1, \cdots, A_i, A_{i+2}, \cdots, A_n$) This motivates the following characterization: If the coloring uses all three colors and no two adjacent vertices have the same color, we are okay. If two adjacent vertices have the same color, call $A_2, A_3$. Then any point outside $A_1A_3 \cdots A_n$ and $A_1A_2 A_4\cdots A_n$ are bad. This is just $\triangle A_2 A_3 (A_1A_3 \cap A_2A_4)$ Otherwise, we can proceed by induction. If $A_i, A_{i+1}, A_{i+2}$ pairwise distinct doesn't exist then the color of $A_i$ is the same as the color of $A_{i+2}$ for every $i$, which implies the polygon is 2-colorable. Hence it exists. Now we need to be careful about removing the final one of the same color. WLOG $A_{i+1}$ is the only red. Then we consider $A_{i-1}A_iA_{i+1}$ instead (indices taken modulo $n$). If $A_i$ is the only green, then this is impossible because everything else is blue, but no two adjacent stuff are blue so $n=3$. If $n\ge 4$ then we need to find the number of colorings. We find the number of ways to fill $C_1=1, \cdots, C_{n+1}=1$ where $C_i\ne C_{i+1}$, call $f(n)$, and let $g(n)$ be the number of ways to fill $C_1=1, \cdots, C_{n+1}=2$ (we just need $C_{n+1}$ is not 1, but is fixed). Then $f(n)+2g(n)=2^n$ since $C_{n+1}$ can be anything we want, so each $C_i$ have 2 choices depending on $C_{i-1}$ $f(n)=2g(n-1)$ and $g(n)=f(n-1)+g(n-1)$ by consider $C_n$. This means $(f(n)-g(n)) = - (f(n-1)-g(n-1))$ Note $f(2)=2, g(2)=1$ so $f(n)=\frac{2^n + 2 (-1)^n}{3}$ and $g(n) = \frac{2^n - (-1)^n}{3}$ Since there are three choices on the first color, there are $2^n + 2(-1)^n$ ways to color such that neighbouring colors are distinct. We need to remove those colorings with at most 2 colors satisfying neighbouring colorings are distinct. If $n$ is odd this is 0. If $n$ is even, this is 6. So the answer should be $2^n + 2(-1)^n - 3(1+(-1)^n)$