## clusters of coloured particles

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 2010 at 18:34
@Nathann: Are rotations of the circle allowed? I expect not. – Peter Shor Nov 3 2010 at 18:53

## 1 Answer

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 2010 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 2010 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 2010 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 2010 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 2010 at 9:41
show 4 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 31, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9349619746208191, "perplexity_flag": "head"}