Воспользуемся массивом dp[n][k] - где будет храниться количество способов для последовательности длины n расставить эленменты, причем последний элемент имеет тип k(1, 2, 3). Тогда для dp[1][1], dp[1][2], dp[3][3] = 1
а формула пересчета: dp[n][1] = dp[n][2] = dp[n - 1][1] + dp[n - 1][2] + dp[n - 1][3]
dp[n][3] = dp[n - 1][1] + dp[n - 1][2];