Recurrence relation for the number of ways to arrange $3$ different types of flags

Question

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.

Answer 1

Just for kicks, let's see if we can get a concrete number out of this. Your recurrence is $a_{n + 4} = a_{n + 2} + 2 a_{n + 1} + 4 a_n$. We also have $a_0 = 1$, $a_1 = 2$ (R or Y), $a_2 = 5$ (RR, RY, YR, YY, G), $a_3 = 4$ (RG, YG, GR, GY). Define the ordinary generating function $A(z) = \sum_{n \ge 0} a_n z^n$. Using the respective properties: $$ \frac{A(z) - 1 - 2 z - 5 z^2 - 4 z^3}{z^4} = \frac{A(z) - 1 - 2 z}{z^2} + 2 \frac{A(z) - 1}{z} + 4 A(z) $$ This gives: $$ A(z) = \frac{(1 + 2 z)^2}{1 - z^2 - 2 z^3 - 4 z^4} $$ The roots of the denominator are all real, but extremely ugly looking expressions. Sorry.

Answer 2

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