# Combinatorics: Finding recurrence relation

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?

## 3 Answers

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

• 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 – afsdf dfsaf Nov 27 '13 at 6:45
• 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? – afsdf dfsaf Nov 27 '13 at 19:55
• 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. – Ross Millikan Nov 28 '13 at 17:29

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

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