1
$\begingroup$

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

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

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – tomate
    Nov 3, 2010 at 23:19
  • $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Nov 3, 2010 at 23:25
  • $\begingroup$ 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 ? $\endgroup$ Nov 4, 2010 at 8:58
  • $\begingroup$ > 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? $\endgroup$
    – tomate
    Nov 4, 2010 at 9:39
  • $\begingroup$ 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. $\endgroup$
    – tomate
    Nov 4, 2010 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.