Ways to color an octagon's vertices with three colors? In how many ways can we color the 8 vertices of an octagon each red, green, or blue, so that no two adjacent vertices are the same color? 
I think there should be something to do with Catalan numbers and triangulation, but I'm not too sure how they fit in.
 A: The chromatic polynomial of the octagon is $$(x-1)^8+(x-1)$$ which when $x=3$ is $258$.
(Note: this assumes that the vertices are distinguishable.  If they're not, then we're either counting $3$-ary necklaces or bracelets of length $8$; formulas for counting these are given on the linked Wikipedia page.)
A: Let $a_n$ be the number of colorings of an $n$-gon with the desired property (where a "$2$-gon" is just two vertices considered adjacent to each other).
If $n=2$, then we have three choices for the color of the first vertex and two choices for the color of the second vertex. Thus $a_2=3\cdot 2=6$.
If $n=3$, then we must make one vertex red, one green, and one blue, but we can assign these colors in any order. This gives us $a_3=3!=6$.
If $n\ge 4$, then we consider two cases. Either vertices $1$ and $n-1$ are different colors, or they are the same color.
First case: If vertices $1$ and $n-1$ are different colors, then vertices $1$ through $n-1$ are colored in a way which would be legal for an $(n-1)$-gon, and the color of vertex $n$ is forced. Thus, within this case, we have $a_{n-1}$ legal colorings of the $n$-gon.
Second case: If vertices $1$ and $n-1$ are the same color, then vertices $1$ through $n-2$ are colored in a way which would be legal for an $(n-2)$-gon, and vertex $n$ can be either of two colors. Thus, within this case, we have $2a_{n-2}$ legal colorings of the $n$-gon.
The two cases taken are exclusive and cover all possibilities, so we obtain the recurrence
$$a_n = a_{n-1} + 2a_{n-2}\quad\text{for }n\ge 4.$$
Making a table, we obtain when $n=8$, $a_n=258$
