(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.
Best 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?