# Permutation of boxes with two colors

Given a row with $$n$$ black boxes and $$n$$ white boxes, how many permutations exist where each box can be adjacent to at most one other box of the same color?

In other words, three or more consecutive boxes with the same color are not allowed.

For $$n=3$$, I count $$14$$ permutations and for $$n=4$$, I get $$34$$ permutations, but what's the general rule?

• for n= 3, I count 12 permutations. – Doug M Jan 4 at 5:01
• Similar question, generalized for $k$ colors, but without the restriction that there be equal number of each color: painting fence... – Daniel Mathias Jan 4 at 11:53

$$a(n) = \sum_{i=0}^{\lfloor n/2\rfloor} 2\binom{n-i}{i}^2 + \binom{n-i}{i} \binom{n-i-1}{i+1} + \binom{n-i}{i}\binom{n-i+1}{i-1}.$$