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