clusters of coloured particles

2010-11-03T17:20:05Z

Is the following a standard problem in combinatorics? Where can I find reference for it?

Consider $n$ particles in a circle, $k$ white and $n-k$ black, otherwise indistinguishable so that the number of dispositions is $n!/(n-k)!k!$. Different dispositions will have a different number of white/black/white/black... clusters. How many dispositions $d(N,K,C)$ have C clusters?

Example. $n=4, k=2$ I get:

$d(4,2,2) = 4$

$d(4,2,4) = 2.$

Answer by Peter Shor for clusters of coloured particles

2010-11-03T18:35:27Z

We will let $k_1=k$ and $k_2=n-k$, and $\tilde{c}=c/2$. I believe the answer is then

$\frac{k_1 + k_2}{\tilde{c}} {k_1-1 \choose \tilde{c}-1} {k_2-1 \choose \tilde{c}-1}$.

I have no idea whether there is a reference for this anywhere.

Here's how it works. First we solve (nearly) the same problem on a line. There are $k_1$ white balls and $k_2$ black balls, and we want to count how many ways there are of arranging the balls so you have $c$ clusters, starting with a white ball on the left and ending with a black ball on the right. What we do is to make $c/2$ clusters of white balls and $c/2$ clusters of balls balls, and interleave them. To make $\tilde{c} = c/2$ clusters of white balls, we start with $k_1$ white balls, and put in $\tilde{c}-1$ dividing lines in any of the $k_1-1$ spots between two balls. We can do the same for the black balls. This means that we have

${k_1-1 \choose \tilde{c}-1} {k_2-1 \choose \tilde{c}-1}$.

ways of arranging these balls into $c$ clusters on a line (with a white on the left and a black on the right). Now, we join them into a circle. There are $n=k_1+k_2$ positions on the circle where we could place the left endpoint of the line. But once we have a circle with $c$ clusters, there are $\tilde{c}=c/2$ ways we could have gotten to this disposition of balls in the circle; we can go back to a line by cutting the circle between any (black,white) pair of balls and there are $c/2$ of them. We thus obtain the above answer.

clusters of coloured particles - MathOverflow

clusters of coloured particles

Answer by Peter Shor for clusters of coloured particles