# Combinatorics: Finding recurrence relation

1. Nov 27, 2013

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?

2. Nov 27, 2013

### Office_Shredder

Staff Emeritus
doesn't look like the right way to count the number of flags that are six high and have a red on top. For starters, you are claiming there are ten such flags, and really you can only do (I think)

R
R/W
B
R/W

or
R
B
R/W
R/W

of which there are only eight such flags. Instead of trying to subtract away flags that you originally constructed that are actually illegal, just think about if you start with a R on top, what are the only possible chains you can have before you reach a B? Once you know that you have placed B everything underneath it is counted using your recurrence relation.

3. Nov 27, 2013

### haruspex

I approach this sort of problem by creating several related recurrence terms. You can have the total number of height n, the number of height n with at most one 1-foot flag on top, and the number that have a 3-foot flag on top. Then you can construct three recurrence relations that connect them.

4. Nov 27, 2013