clusters of coloured particles - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T23:06:57Z http://mathoverflow.net/feeds/question/44703 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/44703/clusters-of-coloured-particles clusters of coloured particles tomate 2010-11-03T17:20:05Z 2010-11-03T20:22:30Z <p>Is the following a standard problem in combinatorics? Where can I find reference for it?</p> <p>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?</p> <p>Example. $n=4, k=2$ I get:</p> <p>$d(4,2,2) = 4$</p> <p>$d(4,2,4) = 2.$</p> http://mathoverflow.net/questions/44703/clusters-of-coloured-particles/44711#44711 Answer by Peter Shor for clusters of coloured particles Peter Shor 2010-11-03T18:35:27Z 2010-11-03T20:22:30Z <p>We will let $k_1=k$ and $k_2=n-k$, and $\tilde{c}=c/2$. I believe the answer is then </p> <p>$\frac{k_1 + k_2}{\tilde{c}} {k_1-1 \choose \tilde{c}-1} {k_2-1 \choose \tilde{c}-1}$.</p> <p>I have no idea whether there is a reference for this anywhere.</p> <p>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</p> <p>${k_1-1 \choose \tilde{c}-1} {k_2-1 \choose \tilde{c}-1}$.</p> <p>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.</p>