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.
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.)