We have a sequence of length $n$.
We can use three colors: $red$, $green$, $blue$.
-
Two elements of the same color must not be adjacent.
-
The blue stripe must be directly between the strips, one of which is green and the other – red (i.e. the incorrect flag is RGBG).
What is the number of sequences of length $n$?
Best Answer
Make a recurrence. For any $n > 0$ let $s_n$ be the number of sequences. $s_1$ = $s_2$ = 2 (check).
For $s_{n + 1}$ with $n > 1$, note that every valid $s_n$ corresponds to exactly one sequence of length $n + 1$; the $n$-length sequence ended in either red or green, so by appending the other one, we get $n + 1$. The only $n + 1$ cases we haven't accounted for, then, are those whose second-to-last element is blue, since these do not come from a valid $n$-coloring. Note that each element of $s_{n - 1}$ corresponds to exactly one such string; it ends in either red or green, so we append blue and then the complementary color. Thus the recurrence is $s_n = s_{n - 1} + s_{n - 2}$ with initial conditions $s_1 = s_2 = 2$, a Fibonacci-like sequence for which you can use similar techniques to find a closed-form formula.