1 of 2

Recurrence Relation for the Number of Ways to Arrange $3$ different types of flags

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.