0
$\begingroup$

There are $a$ red balls and $b$ blue balls, and I have to place all of these balls on circumference of a circle. The balls with the same color are indistinguishable.

I thought the answer would be $\dfrac{(a+b-1)\,!}{a\,!\, b\,!}$, but it clearly doesn't work well.

$\endgroup$
4
  • 1
    $\begingroup$ I deleted my answer for right now. $\endgroup$ – Sidd Singal Apr 23 '14 at 23:50
  • $\begingroup$ OK. I appreciate your effort, though :D $\endgroup$ – Math.StackExchange Apr 23 '14 at 23:51
  • 1
    $\begingroup$ This MSE link shows several approaches to this problem by different users, if I understand the problem correctly. $\endgroup$ – Marko Riedel Apr 24 '14 at 0:09
  • $\begingroup$ This looks pretty interesting! Thanks for your help. user3213784 thought the exactly same thing. $\endgroup$ – Math.StackExchange Apr 24 '14 at 0:10
1
$\begingroup$

We use burnside's lemma. First off number the positions of the beads, define the set $X$ of colorings of the circle (Without taking rotations into account) this set $X$ has $\binom{a+b}{a}$ elements. Now define the action of the group $\mathbb Z_{a+b}$ on the set $X$ as follows: let $m\in \mathbb Z_{a+b}$ and $x\in X$. We define $mx$ to be the coloring obtained by taking the coloring $x$ and rotating it , so that the bead that was at position $1$ now goes to position $m+1$, and more in general the bead at position $i$ goes to the position $m+i$ (or the number that is congruent to $m+i \bmod a+b$.

What we want to count is precisely the number of orbits this action has, to count this we can use Burnsides lemma.

By Burnsides lemma the number of orbits is $\frac{1}{a+b}\sum\limits_{m\in \mathbb Z_{a+b}}|X^m|$. Where $X^m$ is the set of elements $x$ in $X$ satisfying $mx=x$.

We now proceed to characterize $X^m$. when is $mx=x$? Consider the following argument: if $mx=x$ the bead with color $1$ has the same color as the bead $1+m$, and in turn the bead in position $1+m$ has the same color as the bead in position $1+2m$. continue this process until you go back to the vertex at position $1$, you will have passed through a set of vertices which all must have the same color. How many vertices? The same as the order of $m$ in $\mathbb Z_{a+b}$ which happens to be $\frac{a+b}{\gcd(m,a+b)}$. Using this reasoning the vertices are partitioned into $\dfrac{a+b}{\frac{a+b}{\gcd{m,a+b}}}=\gcd(m,a+b)$ sets of vertices that must all have the same color.

So if we want any such colorings to exist we need for $\frac{a+b}{\gcd(m,a+b)}$ to divide both $a$ and $b$.Note this happens if and only if $\frac{a+b}{\gcd(m,a+b)}$ divides $\gcd(a,b)$. Suppose $\dfrac{\gcd(a,b)}{\frac{a+b}{\gcd(m,a+b)}}=l$ This is if and only if $\gcd(m,a+b)=l\frac{a+b}{\gcd(a,b)}$. So this happens if and only if $\gcd(m,a+b)$ is a multiple of $\frac{a+b}{\gcd(a,b)}$. Clearly this happens if and only if $m$ is a multiple of $\frac{a+b}{\gcd(a,b)}$.

So suppose we do have that $m$ is a multiple of $\frac{a+b}{\gcd(a,b)}$. How many colorings are in $X^m$? well, there are $\gcd(m,a+b)$ sets of beads and we want a portion of $\frac{a}{a+b}$ of them to be red. Thus we must only select the $\frac{a(\gcd(m,a+b))}{a+b}$ we want to be red, clearly there are

$$\binom{\gcd(m,a+b)}{\frac{a(\gcd(m,a+b))}{a+b}}$$ ways to do it.

Thus the final answer is

$$\frac{1}{a+b}\sum\limits_{\substack{m\in\mathbb Z_{a+b}\\ \frac{a+b}{\gcd(a,b)}|m}}\binom{\gcd(m,a+b)}{\frac{a(\gcd(m,a+b))}{a+b}}$$

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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