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

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.

• This is a very interesting problem! Your formula failed for x=2,y=3,k=1. Your formula yields 4 when clearly yxyxy is the only allowed configuration. Commented May 11, 2019 at 4:01
• It is fairly easy to derive a recurrence relation for $N(x,y,k)$. In a programming contest this may have been the intention i.e. derive a recurrence relation, implement it in an efficient manner and provide proof of correctness by determining $N(x,y,k)$ for given values of $x,y,k$. Finding a closed-form expression will be much more difficult. Commented May 13, 2019 at 11:24

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)$$

• Thanks! We can also compute sum for each window of size k when building up dp table and complexity reduces x*y. Commented Jan 5, 2020 at 14:17
• That's great optimization! Commented Jan 5, 2020 at 14:35

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