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.