# Reccurence Relations for Arranging Flags

(a) Find a recurrence relation for the number of ways to arrange three types of flags on a flagpole n feet high: red flags (1 foot high), gold flags (1 foot high), and green flags (2 feet high).

(b) Repeat part (a) with the added condition that there may not be three 1-foot flags (red or gold) in a row.

(c) Repeat part (a) with the condition of no red above gold above green (in a row).

The parts i am struggling with are parts b and c.

## 1 Answer

For part a: Suppose $S(n)$ be the number of ways to arrange the flags on flagpole of height $n$. Clearly $S(1)=2,S(2)=5$. Now for a flagpole of height $n$, We can start with a red or gold flag and continue the rest like the way we arrange the flags on a flagpole of height $n-1$, or we can use a green flag and continue the way we arrange the flags on a flagpole of length n-2. So we can write: $S(n)=S(n-1)+S(n-1)+S(n-2)=2S(n-1)+S(n-2)$.

For part b: We can either start with a green flag and continue with $S(n-2)$, or with three flags like this Red-Red-Green,Red-Gold-Green,Gold-Red-Green,Gold-Gold-Green, and continue with $S(n-4)$, Or We can start with Red-Green or Gold-Green and continue with $S(n-3)$ So we can write:$S(n)=S(n-2)+2S(n-3)+4S(n-4),S(1)=2,S(2)=5,S(3)=4,S(4)=12$.

Can you do part c yourself now?

• My previous answer was not correct so I updated it. – hhsaffar Nov 20 '13 at 22:32