What is the number of ways of arranging two colours such that no more than $k$ pieces of same colour are together?

Question

Given that we have $x$ number of $A$'s and $y$ number of $B$'s. How can I find the number of ways of arranging them in a line, such that no more than $k$ pieces of the same colour are adjacent?

Constraints: x,y<=1000

I first thought it could be ${x+y \choose x}-{x+y-k \choose x}$. Based on total combinations - combinations having a group with greater than $k$ pieces of the same color together. Then for the latter part, we can combine $k+1$ pieces of the same color (say $A$) as a single piece, so that the total number of pieces reduces to $(x+y-(k+1)+1) $ and the number of pieces of color A reduces to $x-(k+1)+1$. Now each combination of this scheme will be invalid. Total combinations like these will be ${x+y-k \choose x}$ But we can also inject some color $B$ pieces into the combined $k+1$ pieces of color $A$ and still get invalid combination. How to add these? Is there some simpler way of solving the problem?

A recursive solution will also work. The question appeared on a programming contest.

Answer 1

Since this task comes from programming contest, please update the post by giving the limits on $x$ and $y$.

Let's define a dynamic programming function $F[i][j][0/1]$. Where $F[i][j][0]$ is the number of ways to arrange $i$ A's and $j$ B's, the number $0$ means that the last letter in the arrangement is A. Similarly, $F[i][j][1]$ means the same while the $1$ shows us that the last letter is B.

The base cases would be $F[1][0][0] = 1, F[0][0][0 \text{ or } 1] = 1, F[0][1][1] = 1$.

For the transitions consider adding $d$ letters to the end, make sure that $d < k$ $$F[i][j][0] = F[i-1][j][1] + F[i-2][j][1] + ... + F[i-(k-1)][j][1]\\F[i][j][1] = F[i][j-1][0] + F[i][j-2][0] + ... + F[i][j-(k-1)][0]$$

The result is $F[x][y][0] + F[x][y][1]$. The computational complexity of the algorithm would be $O(x \cdot y \cdot K)$

Answer 2

First, let's assume you have to start with $A's$ and end with $B's$. Then the number of those configurations is the number of decomposition of $A$ and $B$ into sums of equal size of bounded parts : $$ x_1,y_1, x_2 , y_2,.......,x_m,y_m \\ \begin{array}{ccc} x_1 + x_2 +.......+x_m &= x &0<x_i \leq k \\ y_1 + y_2 +.......+y_m &= y &0<y_i\leq k\\ 0<m\leq \max(x,y) \end{array} $$ Now if we denote by $p_k(n,m)$ the number of decomposition of some integer $n$ into $m$ positive parts less than $k$. Then we have :

$$N(x,y,k)=\sum_{m=1}^{\max(x,y)}\Big(2p_k(x,m)p_k(y,m)+p_k(x,m+1)p_k(y,m)+p_k(x,m)p_k(y,m+1) \Big) $$

The first term counts the number of configurations where you start with $A$'s and end with $B$'s or start with $B$'s and end with $A$'s. The second term those starting with $A$'s and ending with $B$'s. The last term those starting with $B$'s and end with $B$'s.

Now the remaining question how can we compute $p_k(x,m) = \big \{(x_1 ,....,x_m)\in [0,k-1]^m, x_1 + x_2 +.......+x_m = x -m \big\}$ ?

Based on the same argument as you did then

$$p_k(x,m)={x-1 \choose m-1}-m {x-1-k \choose m-1}$$

If we tried first to construct two $array$s for the value of the last function at $x$ and $y$ respectively and using the memoisation technique for the binomial coefficients then this construction can be done with complexity $O((x+y)\max(x,y))$. The sum above is linear in $\max(x,y))$.