# clusters of coloured particles

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.$

-
I do not get why you say that there are $n!/(n-k)!k!$ different configurations : If the particles are indistinguishable, there are only 2 dispositions with 4 particles and 2 white ones : they are adjacent or they are not, and rotation of your circle gives all of them from 2 such configurations. – Nathann Cohen Nov 3 '10 at 18:34
@Nathann: Are rotations of the circle allowed? I expect not. – Peter Shor Nov 3 '10 at 18:53

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.

-
It seems like it works well, great and timely answer indeed! Thank you a lot. I feared that the answer would have to do with partions of integer numbers, instead it's nice to have a simple solution. – tomate Nov 3 '10 at 23:19
This indeed would be a great homework problem for a combinatorics class. As I said, I don't know whether it's in the literature or not. – Peter Shor Nov 3 '10 at 23:25
Hello !! There is something I still don't get : once you have your line arrangement, you can place the left endpoint in $n$ different ways on the cycle, but this does not means the $n$ coloring you thus produce are different. For example with all the clusters of size 1, you would only produce 2 different colorings. Of course you then divide by $c/2$ but it sounds too rough for me to solve symmetry problems. If your clusters are : 3 + 1 + 3 + 1 + 3 + 1 + 3 + 1 in one case, and 2 + 1 + 4 + 1 + 2 + 1 + 4 + 1, wouldn't you get a different numbers of distinct copies in each case ? – Nathann Cohen Nov 4 '10 at 8:58
> you can place the left endpoint in n different ways on the cycle, but this does not means the n coloring you thus produce are different That's true, but I think Shor's argument does not treat symmetry that way (otherwise he would have multiplied by n instead of n/2). In fact, if if you take k_1 = k_2 and clusters of size 1, that is c = k_1, the formula gives 2 as you expect. I don't understand your last question: the two dispositions you give correspond to the same clustering W-B-W-B-W-B-W-B. How many other dispositions of 16 particles, 12 white and 4 black, give this very same clustering? – tomate Nov 4 '10 at 9:39
It might be interesting to generalize to clusters of particles of many colours. This problem arose in the calculation of the Von Neumann entropy of a quantum mixed state. – tomate Nov 4 '10 at 9:41