0
$\begingroup$

Find the number of ways to arrange three types of flags on an $n$ foot flag pole: red flags ($1$ foot high), white flags ($1$ foot high), blue flags ($3$ feet high)

Find a recurrence relation for this number with one condition that there cannot be three $1$ foot flags in a row (regardless of their color).

R= Red, W=White, B=Blue

$a_1 = 2$, R, W

$a_2 = 4$, RW, WR, WW, RR

$a_3 = 1$, B

$a_4 = 4$, B($a_1$), W($a_3$), R($a_3$)

$a_5 = 12$, B($a_2$), W($a_4$), R($a_4$)

$a_6 = 21$, B($a_3$), W($a_5-2(a_3)$), R($a_5-2(a_3)$)

$a_7 = 30$, B($a_4$), W($a_6-2(a_4)$), R($a_6-2(a_4)$)

$a_8 = 24$, B($a_5$), W($a_7-2(a_5)$), R($a_7-2(a_5)$)

$a_9 =$ -number, B($a_6$), W($a_8-2(a_6)$), R($a_8-2(a_6)$)

Since there is a negative number, I do not think this is right...could anyone point out what I did wrong?

$\endgroup$
1
$\begingroup$

In $a_6$ with $W(a_5-2a_3)$ you are trying to add a white flag to all the length $5$ strings but claiming that there are $2a_3$ ones that end with two one foot flags, so must be deducted. In fact, it is $2a_2$, because you are deducting the ones that are blue plus two one foot flags.

I would define $N(n)$ as the number of flag series of length $n, P(n)$ as the number of series of length $n$ ending in a blue flag, $Q(n)$ the number of series of length $n$ ending in one non-blue flag, $R(n)$ the number of series of length $n$ ending in two non-blue flags. You then have a set of coupled recurrences.

added: for example, $N(n)=P(n)+Q(n)+R(n), R(n)=N(n-3)$ where the second comes because you can put a blue on top of any string, extending it three feet. now you need to write recurrences for $P(n),Q(n)$

$\endgroup$
  • $\begingroup$ How can be 2(a_2)? a_2 = 4, RW, WR, WW, RR a_3 = 1, B a_4 = 4, B(a_1), W(a_3), R(a_3) a_5 = 12, B(a_2), W(a_4), R(a_4) W(a_5-2(a_3)) = this is part of the a_5 >>>> W(W(a_4) = this is part of the a_4 W(W(W(a_3))...should not we deduct a_3? Could you show me your step such as a_4, a_5.....so for $\endgroup$ – afsdf dfsaf Nov 27 '13 at 6:45
  • $\begingroup$ Let a_n be the arrangement of flags at n feet. Just figure it out...is it a_n = a_(n-3)+2*a_(n-4)+4*a_(n-5). The initial value is a_2= 1, a_2 = 4, a_3 = 1, a_4 = 4,a_5 = 12. Is it right? $\endgroup$ – afsdf dfsaf Nov 27 '13 at 19:55
  • $\begingroup$ You should edit your post or post answer showing the logic behind this. Just looking at the formula, I am not sure. It looks right and in this case I can identify where each term comes from. $\endgroup$ – Ross Millikan Nov 28 '13 at 17:29
0
$\begingroup$

Call $a_n$ the number of poles ending in a no 1-foot flag, $b_n$ if it ends in one 1-foot flag, $c_n$ if it ends in 2 1-foot flags. Clearly:

$a_0 = 1, a_1 = 0, b_0 = 0, c_0 = 0$

Also, as we can add a 2-foot flag to anything, and adding a 1-foot flag changes the number of 1-foot flags at the end:

$\begin{align*} a_n &= a_{n - 2} + b_{n - 2} + c_{n - 2} \\ b_n &= 2 a_{n - 1} \\ c_n &= 2 b_{n - 1} \end{align*}$

The total number of $n$ feet poles is $a_n + b_n + c_n$.

Set up generating functions $A(z) = \sum_{n \ge 0} a_n z^n$, $B(z) = \sum_{n \ge 0} b_n z^n$ and $C(z) = \sum_{n \ge 0} c_n z^n$. Multiply shifted recurrences by $z^n$, sum over $n \ge 0$ and recognize resulting sums:

$\begin{align*} \sum_{n \ge 0} a_{n + 2} z^n &= \sum_{n \ge 0} a_n z^n + \sum_{n \ge 0} b_n z^n + \sum_{n \ge 0} c_n z^n \\ \sum_{n \ge 0} b_{n + 1} z^n &= \sum_{n \ge 0} a_n z^n \\ \sum_{n \ge 0} c_n z^n &= \sum_{n \ge 0} b_n z^n \end{align*}$

$\begin{align*} \frac{A(z) - a_0 - a_1 z}{z^2} &= A(z) + B(z) + C(z) \\ \frac{B(z) - b_0}{z} &= 2 A(z) \\ \frac{C(z) -c_0}{z} &= 2 B(z) \end{align*}$

Solve this system to get:

$\begin{align*} A(z) &= \frac{1}{1 - z^2 - 2 z^3 - 4 z^4} \\ B(z) &= \frac{z}{1 - z^2 - 2 z^3 - 4 z^4} \\ C(z) &= \frac{z^2}{1 - z^2 - 2 z^3 - 4 z^4} \end{align*}$

We want:

$\begin{align*} F(z) &= A(z) + B(z) + C(z) \\ &= \frac{1 + 2 z + 4 z^2}{1 - z^2 - 2 z^3 - 4 z^4} \end{align*}$

We want the coeficient of $z^n$ in this. The zeroes of the denominator are quite horrible, though.

We can glean the recurrence from the denominator: It is $F_n = F_{n - 2} + 2 F_{n - 3} + 4 F_{n - 4}$, with initial values $F_0 = 1, F_1 = 2, F_2 = 3$.

$\endgroup$
0
$\begingroup$

Use generating functions. You can write the allowed flags as a regular expression:

$\begin{equation*} ((\epsilon + (r + w) + (r + w)^2) b)^* (\epsilon + (r + w) + (r + w)^2) \end{equation*}$

I.e., it is a sequence of up to two 1-foot flags followed by a 2-feet flag, all finished by at most two 1-foot flags. For the building block you have the generating function:

$\begin{equation*} (1 + 2 z + 4 z^2) z^2 \end{equation*}$

A sequence of those is:

$\begin{align*} 1 + (1 + 2 z + 4 z^2) z^2 + (1 + 2 z + 4 z^2)^2 z^4 + \dotsb &= \frac{1}{1 - (1 + 2 z + 4 z^2) z^2} \\ &= \frac{1}{1 - z^2 - 2 z^3 - 4 z^4} \end{align*}$

Adding in the tail gives:

$\begin{align*} \frac{1 + 2 z + 4 z^2}{1 - z^2 - 2 z^3 - 4 z^4} \end{align*}$

$\endgroup$

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.