In how many ways can $m$ white and $n$ black balls be arranged in a circle so that there shall be 2$r$ contacts between white and black balls? Suppose the balls are identical, but the positions on the circle are distinguishable.
If I am not mistaken, the total number of arrangements is
$$N=\frac{\left(n+m\right)!}{n!\cdot m!}.$$
Now, my question is how to split $N$ in $N_r$, where $N_r$ would be the number of arrangements with $2r$ contacts of unequal color.
I have calculated a few examples:
- $m=0$ and $n=6$: $N=1$, with $N_0=1$
- $m=2$ and $n=5$: $N=21$, with $N_1=7,N_2=14$
- $m=4$ and $n=4$: $N=70$, with $N_1=8,N_2=36,N_3=24,N_4=2$
- $m=6$ and $n=3$: $N=84$, with $N_1=9,N_2=45,N_3=30$
- $m=8$ and $n=2$: $N=45$, with $N_1=10,N_2=35$
- $m=10$ and $n=1$: $N=11$, with $N_1=11$
- $m=12$ and $n=0$: $N=1$, with $N_0=1$
Finding an analytical expression for $N_r$ would already be of great help. However, in reality, I am even more interested in the following question:
How does this result change if we suppose that black balls occur only in pairs?
For this case, I think I also already found an expression for the total number of arrangements (assuming that there is at least one ball of either color; a general solution would be preferred, but it's not a priority):
$$N=\binom{n/2+m-1}{m-1}+2\binom{n/2+m-1}{n/2-1}$$
I can also give some numerical results for $N_r$ in this case, however, I am lacking the analytical expression:
- $m=0$ and $n=12$: $N=1$, with $N_0=1$ (formula above does not work)
- $m=2$ and $n=10$: $N=36$, with $N_1=12,N_2=24$
- $m=4$ and $n=8$: $N=105$, with $N_1=12,N_2=54,N_3=36,N_4=3$
- $m=6$ and $n=6$: $N=112$, with $N_1=12,N_2=60,N_3=40$
- $m=8$ and $n=4$: $N=54$, with $N_1=12,N_2=42$
- $m=10$ and $n=2$: $N=12$, with $N_1=12$
- $m=12$ and $n=0$: $N=1$, with $N_0=1$ (formula above does not work)
Any help is appreciated, thank you in advance!
I found an answer to the first part of the question:
$$N_r = \binom{m}{r}\binom{n-1}{r-1} +\binom{n}{r}\binom{m-1}{r-1} $$
for $r$ in the range from 1 to $\min\left(m,n\right)$.
It can be understood by considering that there are $m$ spots between the white balls that can be filled with one or more black balls. For $r$ filled spots, we get 2$r$ contacts between white and black balls. For $2r$ contacts, we can choose therefore $r$ spots out of $m$ available spots, which leads to the prefactor $\binom{m}{r}$ of the first term. This prefactor is multiplied by the number of possibilities of filling these spots. The question is in how many distinct ways can $n$ black balls be distributed over $r$ spots under the assumption that there is at least one black ball in each of the $r$ spots. In order to get $r$ groups of black balls, we use $r-1$ dividers that can be placed at $n-1$ one spots between the black balls (no periodic boundaries here), which leads to the second factor of the first term. Inverting the colors gives the second term of the sum.