Find a recurrence relation for the number of ways to arrange red flags ($1$ ft. tall), yellow flags (1 ft. tall), and green flags ($2$ ft. tall) on an $n$ foot
tall pole s.t. there may not be three $1$-foot flags (red or gold) in a row.
I'm not sure if my answer is correct (no way of solution provided), could someone please let me know if my reasoning is right?
Solution: Let G be green, R be red, Y be yellow. Define a "good" sequence to be one that does not violate the proposed constraint.
Since there is no constraint on G, then G an be appended to any good $(n-1)$-sequence — giving $a_{n-2}$ ways.
If an $n$-sequence ends in R or Y, then we can have:
- R or Y in the $n$-th position and in the $(n-1)$-th position, which must be followed by G. This gives $4a_{n-4}$ ways
- R or Y in the $n$-th position and G in the $(n-1)$-th position. This gives $2a_{n-3}$ ways.
In all we have $a_n = a_{n-2} + 4a_{n-4} + 2a_{n-3}$ possible ways.
Best Answer
Think of it this way:
Let $G_n$ be the number of ways to arrange flags on an $n$ foot pole assuming the last flag is a green flag. Let $Y_n$ be the equivalent for yellow/red flags. We're going to count the total, which is $T_n=G_n+Y_n$.
Now, a sequence ending in green can have any sequence two less prior to it. So
$$ G_n = T_{n-2} $$ A sequence ending in red or yellow cannot have two such flags before it. So it must have a green either one (followed by a red or yellow) or two before it. And either red or yellow can be the final flag. That is,
$$ Y_n = 4G_{n-1}+2G_{n-2} $$ So we have that $$ T_n = T_{n-2}+4G_{n-1}+2G_{n-2} $$ Substituting in our $G_n$ equation into $T_n$ gives $$ T_n = T_{n-2} + 4T_{n-3}+2T_{n-4} $$ where $T_0=1$, $T_1=2$, $T_2=5$, and $T_3=4$.