4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm pretty sure there is no closed form. $\endgroup$ – Don Thousand Jan 4 '19 at 17:09
  • $\begingroup$ @DonThousand No closed form as in ? $\endgroup$ – Gaurav Gupta Jan 4 '19 at 17:19
  • $\begingroup$ No general formula $\endgroup$ – Don Thousand Jan 4 '19 at 17:20
  • $\begingroup$ @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 :( $\endgroup$ – Gaurav Gupta Jan 4 '19 at 17:23
  • $\begingroup$ @DonThousand Looks like there exist a dynamic programming solution to this to find it. $\endgroup$ – Gaurav Gupta Jan 4 '19 at 17:43
0
$\begingroup$

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

I guess you’d want to sum this function for all k less than K, but that’s the nicest idea I could come up with. Apologies for my sloppy phrasing, I can clarify where needed.

$\endgroup$

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.