# How many ways can we place two types of balls on a circle?

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.

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

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.

$$\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}}$$