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

| cite | improve this question | | | | |

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?

| cite | improve this answer | | | | |
  • $\begingroup$ My previous answer was not correct so I updated it. $\endgroup$ – hhsaffar Nov 20 '13 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.