Number of ways of arranging $n$ blue balls and $n$ red balls in a circle

Question

I have problems reasoning out a general formula to represent the number of possible circular orientations of the $n$ red balls and $n$ blue balls as I’m very bad at combinatorial questions and when to decide what is treated as unique and what is treated as a repetition if it is actually relevant here.

The procedure I used to find the number of ways for making a circle with the above condition for $n=3$ is as follows. I would treat the circle arrangement as a special linear arrangement with variable start points.

a) Pick a random start point, say R (I think somehow my starting point won’t matter for a circular arrangement)

b) Come up with a possibility tree incrementally by appending R or B to the right of the arrangement until I fulfill $n$ Red and $n$ Blue elements. If I do this for $6$ stages/elements, and don’t eliminate repetitions in the circular arrangement, I should get $2^{5}$ such chains if I actually model it after linear chains instead.

c)I will first complete some boundary cases like $RRRBBB,$ and reject some of the chains before they are completed if I observe that under the constraints of $n$ colour for either side, their remaining choices are forced.

d) If they hit $6$ elements long, I will try to “rotate” the leftmost element to become the rightmost element to get a common part that matches with one of the accepted cases. If that common part is not the entire length of the chain, it must be a unique case.

A diagram of my procedure.

I arrived at the conclusion that there are $4$ circular combinations for $n=3$.

Suppose this procedure is somewhat correct, I’m unable to translate this procedure in terms of a formula to find the number of circular arrangements for general n, and proceed to know the enumerations required for this problem.

Should I think of the number of ways of circular arrangement as such or is there a more convenient way to think of such a problem?

Feel free to correct me if any of my assumptions are wrong, or quote the name of the results in my algorithm if they are somehow correct since they are just based on my intuition.

Answer 1

For this type of necklace we may apply the Polya Enumeration Theorem (PET). With $Z(C_{2n})$ the cycle index of the cyclic group of order $2n$ the answer is given by

$$[R^n B^n] Z(C_{2n}; R+B).$$

The cycle index is

$$Z(C_{2n}) = \frac{1}{2n} \sum_{d|2n} \varphi(d) a_d^{2n/d}$$

so that the coefficient extractor becomes

$$[R^n B^n]Z(C_{2n}; R+B) = [R^n B^n] \frac{1}{2n} \sum_{d|2n} \varphi(d) (R^d+B^d)^{2n/d}$$

Now for a non-zero contribution the sum variable $d$ must divide $n$, and we find

$$[R^n B^n] \frac{1}{2n} \sum_{d|n} \varphi(d) (R^d+B^d)^{2n/d} = \frac{1}{2n} \sum_{d|n} \varphi(d) [R^n B^n] (R^d+B^d)^{2n/d} \\ = \frac{1}{2n} \sum_{d|n} \varphi(d) [B^n] {2n/d\choose n/d} B^{d(2n/d-n/d)} \\ = \frac{1}{2n} \sum_{d|n} \varphi(d) {2n/d\choose n/d}.$$

This may be re-written if desired, as follows,

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2n} \sum_{d|n} \varphi(n/d) {2d\choose d}.}$$

Answer 2

I think this is http://oeis.org/A003239, "number of necklaces with $2n$ beads, $n$ white and $n$ black." No closed form formula is given, just $\sum_{d|n} (\phi(n/d)\binom {2d} d)/(2n)$, where $\phi$ is the Euler phi-function, and the sum is over all divisors $d$ of $n$. Many links & references are given.