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?

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

This is A177790 “Number of paths from (0,0) to (n,n) avoiding 3 or more consecutive east steps and 3 or more consecutive north steps” on OEIS. The closest thing to a formula given there is

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.