Number of ways of not placing k same color balls together ??

Question

there are n red balls and m white balls .How to find number of ways to place the balls such that at max k balls of same color are together.How to understand and solve these kind of problems .I have been away from maths for a long while.Can somebody please explain

Answer 1

As you tagged this as computational-mathematics, I suppose you are ok with an algorithm instead of a closed formula.

Let $f(n,m,r,w)$ denote the number of ways to place $n$ red and $m$ white balls with at most $k$ balls of the same colour in sequence and such that the sequence ends in $r$ white balls / $w$ white balls (obviously, this means that exactly one of $r,w$ is $=0$ and the other is $\ge1$ and $\le k$). We have the recursion $$ f(n,m,r,0)=\begin{cases}f(n-1,m,r-1,0)&r>1\\ \sum_{w=1}^kf(n-1,m,0,w)&r=1\end{cases}$$ $$ f(n,m,0,w)=\begin{cases}f(n,m-1,0, w-1)&w>1\\ \sum_{r=1}^kf(n,m-1,r,0)&w=1\end{cases}$$ with base cases $f(n,m,r,w)=0$ if $n<r$ or $m<w$. You want to compute $\sum_{r=1}^k f(n,m,r,0)+\sum_{w=1}^k f(n,m,0,w)$, and this can be done with filling an array of values from "bottom" to "top".