# Combinations of red and black balls

Given $$N$$ Identical Red balls and $$M$$ Identical Black balls, in how many ways we can arrange them such that not more than $$K$$ adjacent balls are of same color.

Example : For $$1$$ Red ball and $$1$$ black ball, with $$K=1$$, there are $$2$$ ways $$[RB,BR]$$

Can there be a general formula for given $$N$$,$$M$$ and $$K$$ ?

I have read about Dutch flag problem to find number of ways to find such that no adjacent balls are of same color. I am bit stuck on how to find for at max K balls.

• I'm pretty sure there is no closed form. – Don Thousand Jan 4 '19 at 17:09
• @DonThousand No closed form as in ? – Gaurav Gupta Jan 4 '19 at 17:19
• No general formula – Don Thousand Jan 4 '19 at 17:20
• @DonThousand Ah I see. I was thinking of something like, if 1 adjacent ball can be of same color then how many ways + if 2 adjacent balls can be of same color then how manys and so on upto K. Wasn't able to have a general solution :( – Gaurav Gupta Jan 4 '19 at 17:23
• @DonThousand Looks like there exist a dynamic programming solution to this to find it. – Gaurav Gupta Jan 4 '19 at 17:43

$$f(n,k) =$$ number of sequences with $$n$$ balls and exactly $$k$$ repeats, which is exactly this:
$$f(n,k) = 2 \binom{n-1}{k}$$
Essentially, there are two sequences with 0 repeats and $$n-k$$ length. Given a string with no repeats, we choose how many extra balls are added into each spot, which is equivalent to multiplying by the multichoose $$\left( \binom{n-k}{k} \right) = \binom{n-1}{k}$$.