Day 13: Choosing Christmas Baubles

Let us denote the number of such arrangements for $n$ baubles $R_n$ . Let us call the number of arrangements for $n$ baubles that do not satisfy the second condition $A_n$ .

By inspection $R_3 = 20$ and $A_3 = 60$ . We can then set up the following recurrence relations:

$R_{n+1} = R_{n-1} \times 4 + A_{n-1} \times 3 \\ A_{n+1} = 5 \times 4 ^ n - R_{n+1}$

The first works as we consider the first $n-1$ baubles then we add on two baubles. The second is simply the total number of arrangements minus the required ones.

Using this gives: $R_5 = 20 \times 4 + 60 \times 3 = 260 \\ A_5 = 5 \times 4 ^ 4 - 260 = 1020$

Therefore the solution is $R_7 = 260 \times 4 + 1020 \times 3 = \boxed{4100}$ .

From the recurrence relation $R_{n+1}=3R_{n}+4R_{n-1}$ , we can find the formula: $R_n=4^{n-1}+(-1)^{n-1}\times 4$ .

So $R_7=4^6+4=4100$ .