Combinatorics: Finding recurrence relation

Question

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?

Answer 1

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)$

Answer 2

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

Answer 3

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*}$