Recursion, Catalan Numbers & Generating Functions · Hard problem

How many strings of length $8$ over the alphabet $\{0,1,2\}$ have no two adjacent characters equal and also have first character different from last?