Arranging 3 types of balls.

157 Views Asked by At

There are $b$ black balls, $w$ white balls and $g$ green balls. Find the number of ways of arranging them such that no two white balls are consecutive and no two green balls are consecutive. (Black balls can be consecutive).

Currently, according to my approach, there are two cases if black balls are more than white balls and green balls, then I would basically put $b$ black balls and there would be $b+1$ spaces, I would choose $w$ spaces and put $w$ white balls and now there are $b+w$ balls so $b+w+1$ spaces, now choosing $g$ spaces from them.

1

There are 1 best solutions below

4
On

First we arrange the white and the green balls in a row. We then see alternating runs ${}^*)$ of white and green balls. Let an $r\geq1$ be given. Then the $w$ white balls can be partitioned in ${w-1\choose r-1}$ ways into $r$ runs. In the interior of these runs there remain $w-r$ forbidden adjacencies, and we have to use $w-r$ black balls to remove these. Similarly for the $g$ green balls. It follows that there are $$2{w-1\choose r-1}{g-1\choose r-1}$$ arrangements of the white and green balls containing exactly $r$ runs of each kind. For each such arrangement we have used $w+g-2r$ "compulsory" black balls, so that $b':=b+2r-w-g$ black balls are left over. These can be distributed arbitrarily in the $g+w+1$ spaces present in the original arrangement of the white and green balls (and are then clearly recognizable as "optional"). By "stars and bars" there are ${b'+w+g\choose w+g}={b+2r\choose w+g}$ ways to distribute these "optional" black balls. In this way we obtain a total of $$2{w-1\choose r-1}{g-1\choose r-1}{b+2r\choose w+g}$$ admissible arrangements with $r$ runs each of white and green balls.

Treat in the same way the case of $r$ and $r+1$, resp. $r+1$ and $r$, runs of white and green balls, and finally sum over $r$.

${}^*)$ A run in a string is a maximal subsequence of equal letters.