Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Looks fine to me. –  vonbrand Mar 29 '13 at 4:03

2 Answers 2

Think of it this way:

Let $G_n$ be the number of ways to arrange flags on an $n$ foot pole assuming the last flag is a green flag. Let $Y_n$ be the equivalent for yellow/red flags. We're going to count the total, which is $T_n=G_n+Y_n$.

Now, a sequence ending in green can have any sequence two less prior to it. So

$$ G_n = T_{n-2} $$ A sequence ending in red or yellow cannot have two such flags before it. So it must have a green either one (followed by a red or yellow) or two before it. And either red or yellow can be the final flag. That is,

$$ Y_n = 4G_{n-1}+2G_{n-2} $$ So we have that $$ T_n = T_{n-2}+4G_{n-1}+2G_{n-2} $$ Substituting in our $G_n$ equation into $T_n$ gives $$ T_n = T_{n-2} + 4T_{n-3}+2T_{n-4} $$ where $T_0=1$, $T_1=2$, $T_2=5$, and $T_3=4$.

share|improve this answer
    
Oops, just realised it doesn't say that it can't have three of the SAME 1-foot flag, just that it can't have three 1-foot flags. Correcting my solution now. –  Glen O Mar 29 '13 at 4:28

Just for kicks, let's see if we can get a concrete number out of this. Your recurrence is $a_{n + 4} = a_{n + 2} + 2 a_{n + 1} + 4 a_n$. We also have $a_0 = 1$, $a_1 = 2$ (R or Y), $a_2 = 5$ (RR, RY, YR, YY, G), $a_3 = 4$ (RG, YG, GR, GY). Define the ordinary generating function $A(z) = \sum_{n \ge 0} a_n z^n$. Using the respective properties: $$ \frac{A(z) - 1 - 2 z - 5 z^2 - 4 z^3}{z^4} = \frac{A(z) - 1 - 2 z}{z^2} + 2 \frac{A(z) - 1}{z} + 4 A(z) $$ This gives: $$ A(z) = \frac{(1 + 2 z)^2}{1 - z^2 - 2 z^3 - 4 z^4} $$ The roots of the denominator are all real, but extremely ugly looking expressions. Sorry.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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