I am trying to solve the following question:
How many linear arrangements of $m$ white balls and $(n-m)$ black balls are possible such that each pair of white balls is separated by at least two black balls? The white balls are indistinguishable among themselves and the black balls are indistinguishable among themselves.
Please provide the solution to this.
Thanks,
Add two more black balls, glue a black ball to either side of each white ball, choose $m$ spots for the glued blocks among the resulting $m+n-m+2-2m=n-2m+2$ objects in $\binom{n-2m+2}m$ different ways and remove the two outermost black balls.
Let $x_0,x_1,\dots,x_m$ represent the number of black balls between the respective white balls. Specifically, $x_0$ is the number of black balls to the left of the first white ball. $x_1$ is the number of black balls between the first and second white ball, etc...
$\underbrace{\bullet}_{x_0}\circ\underbrace{\bullet\bullet\bullet}_{x_1}\circ\underbrace{\bullet\bullet\bullet}_{x_2}\circ\underbrace{\bullet\bullet\bullet\bullet}_{x_3}\circ\dots\circ\underbrace{\bullet\bullet\bullet}_{x_m}$
We know there are a total of $n-m$ black balls. Thus, $x_0+x_1+\dots+x_m=n-m$
Further, the condition that there must be at least two black balls between every white ball implies that for $i\in\{1,2,\dots,m-1\}$ you must have $x_i\geq 2$.
We recognize first that there is a bijection between valid arrangements of balls and solutions to the system. We try then to count how many integral solutions there are to the system:
$\begin{cases}x_0+x_1+\dots+x_m=n-m\\ 0\leq x_0\\ 2\leq x_1\\ 2\leq x_2\\ \vdots\\ 2\leq x_{m-1}\\ 0\leq x_m\end{cases}$
Make a change of variable: $y_0=x_0, y_m=x_m, y_i=x_i-2$ for all other $i\in\{1,2,\dots,m-1\}$
This is then the system:
$\begin{cases}y_0+y_1+\dots+y_m = n-3m+2\\ 0\leq y_0\\ 0\leq y_1\\ \vdots\\ 0\leq y_m\end{cases}$
This is of a known problem form. See for example this recent related post. Note that in this scenario it is as though there are $m+1$ buckets and $n-3m+2$ balls yet to place.
There must be at least two black balls after each of the first $m - 1$ white balls in the row, so the answer is zero unless $n - m \geq 2(m - 1) \implies n \geq 3m - 2$.
Method 1: Set aside $2(m - 1) = 2m - 2$ black balls. That leaves us with $m$ white balls and $n - m - (2m - 2) = n - 3m + 2$ black balls to arrange. Choose $m$ of the $m + n - 3m + 2 = n - 2m + 2$ positions for the white balls, which can be done in $$\binom{n - 2m + 2}{m}$$ ways. Finally, insert two black balls to the immediate right of the first $m - 1$ white balls to ensure that there are at least two black balls between any two white balls.
I thought of the simpler method shown above after posting my first attempt at the problem. My original approach is shown below.
Method 2: We can represent each arrangement of black and white balls by a bit string in which a white ball is represented by a $1$ and a black ball is represented by a $0$. We consider cases depending on the position of the $m$th white ball.
Case 1: The $m$th white ball is in the last position.
We have a bit string of length $n$ that ends in $1$. We must fill the first $n - 1$ positions of the bit string with the remaining $m - 1$ ones and $n - m$ zeros. Since each of the first $m - 1$ white balls must be followed by at least two black balls, we must arrange $m - 1$ blocks of the form $100$ and $n - m - 2(m - 1) = n - 3m + 2$ zeros. The number of arrangements of this form is equal to the number of ways we can choose which $m - 1$ of the $m - 1 + n - 3m + 2 = n - 2m + 1$ objects will be filled with blocks of the form $100$, which is $$\binom{n - 2m + 1}{m - 1}$$
Case 2: The $m$th white ball is in the next to last position.
Since no two white balls can be consecutive, the last position must be filled with a black ball. Hence, we have a bit string of length $n$ that ends in $10$. We must fill the first $n - 2$ positions of the bit string with the remaining $m - 1$ ones and $n - m - 1$ zeros. Since the first $m - 1$ white balls must be followed by two black balls, we must arrange $m - 1$ blocks of the form $100$ and $n - m - 1 - 2(m - 1) = n - 3m + 1$ zeros. The number of bit strings of this form is equal to the number of ways we can choose which $m - 1$ of the $m - 1 + n - 3m + 1 = n - 2m$ objects will be filled with blocks of the form $100$, which is $$\binom{n - 2m}{m - 1}$$
Case 3: The $m$th white ball is not in the last two positions.
In this case, every white ball is followed by at least two black balls. Thus, we must arrange $m$ strings of the form $100$ and $n - m - 2m = n - 3m$ zeros. The number of arrangements of this form is equal to the number of ways we can choose which $m$ of the $m + n - 3m = n - 2m$ objects will be filled with blocks of the form $100$, which is $$\binom{n - 2m}{m}$$
Total: Since the three cases are mutually exclusive and exhaustive, we can find the total number of arrangements by adding the number of arrangements of the three cases above. \begin{align*} \binom{n - 2m + 1}{m - 1} & + \binom{n - 2m}{m - 1} + \binom{n - 2m}{m}\\ & = \binom{n - 2m + 1}{m - 1} + \binom{n - 2m + 1}{m}\\ & = \binom{n - 2m + 2}{m} \end{align*} where we have applied Pascal's Identity twice.
Make $m$ boxes as shown below (note the "short" last box )
$\boxed{\circ\bullet\bullet}\;\boxed{\circ\bullet\bullet}\;\boxed{\circ\bullet\bullet} ......... \boxed{\circ}$
Total objects have reduced to $n -2(m-1) = n-2m+2$
Place the boxes among them in $\binom{n-2m+2}{m}$ ways with the "short" box last
