arrangement of $n$ oranges and $n$ apples around a circle

what is the total number of distinct arrangements of $n$ oranges and $n$ apples around a round table? I have no idea how to go about.

Solution 1:

Approach via Burnside's Lemma (or more accurately, "the lemma which is not Burnside's").

$$|X/G| = \frac{1}{|G|}\sum_{g\in G}|X^g|$$

Here, $G$ will refer to the group of rotations of a circular table with $2n$ spaces. $|X^g|$ counts the number of arrangements which are fixed under a particular rotation $g$. In similar problems where all people/objects are distinct, it so happens that the only surviving term in the summation is the identity rotation, however that is not the case here.

Let $\rho_i$ denote rotation by $i$ spaces clockwise.

$|X^{\rho_0}| = \frac{(2n)!}{n!n!}$ by earlier example.

$|X^{\rho_1}| = 0$ since there is at least one apple adjacent to an orange, after rotation there is at least one space containing an orange that will no longer contain an orange.

$|X^{\rho_2}| = 2$ since given a specific location, if it holds an apple, then the space two away from it must also contain an apple so that the rotation doesn't affect it. Similarly the space two from that must also have an apple. Continuing around, we see that every other space must have an apple. Since we must also place $n$ oranges, it must be that all remaining spaces have oranges. Consider the northernmost position special. We have two choices then, either the north position has an apple, or the north position has an orange.

$|X^{\rho_3}|=0$ since given a specific location, every third space must have the same type of fruit. It can be seen that you will not use the same amount of apples and oranges in any configuration that remains invariant under this rotation.

$\vdots$

$|X^{\rho_{2k}}| = \frac{(2x)!}{x!x!}$ where $2x=\gcd(2k,2n)$ since looking at the north position, the space $2k$ away will need to be the same, and the space $2k$ away from that must be the same et cetera. This will either wrap around back to start in a single pass, or multiple passes covering even more spaces. For example, if $2n=10$ and we are trying to rotate $4$ units at a time, this implies that spaces $0,4,8,2,6$ must be the same whereas if $2n=16$ and we are trying to rotate $4$ units at a time, this implies spaces $0,4,8,12$ all must be the same. This implies that the north position and the $2x-1$ additional spaces clockwise to the north position will completely determine the full arrangement, half of which must be apples and the other half oranges, we have $\frac{(2x)!}{x!x!}$ ways to place apples and oranges in those spaces. The choices of apples and oranges in those positions will force the positions of all additional apples and oranges around the circle in order to ensure the arrangement is not changed under rotation $\rho_{2k}$

$|X^{\rho_s}|=0$ whenever $s\neq 2k$ for some $k$ since otherwise there will not be an equal amount of apples and bananas in the end.

We have then the total number of arrangements is:

$$\frac{1}{2n}\left(\sum_{k=1}^{n}\frac{\gcd(2k,2n)!}{\gcd(k,n)!\gcd(k,n)!}\right)$$

(note: $\rho_{2n} = \rho_0$)

For example with $6$ apples and $6$ oranges, we have $\frac{1}{12}\left(\frac{2!}{1!1!}+\frac{4!}{2!2!}+\frac{6!}{3!3!}+\frac{4!}{2!2!}+\frac{2!}{1!1!}+\frac{12!}{6!6!}\right)=\frac{1}{12}\left(2+6+20+6+2+924\right) = 80$

With $5$ apples and $5$ oranges, we have $\frac{1}{10}\left(\frac{2!}{1!1!}+\frac{2!}{1!1!}+\frac{2!}{1!1!}+\frac{2!}{1!1!}+\frac{10!}{5!5!}\right) = \frac{1}{10}\left(8+252\right)=26$

With $4$ apples and $4$ oranges, we have $\frac{1}{8}\left(\frac{2!}{1!1!}+\frac{4!}{2!2!}+\frac{2!}{1!1!}+\frac{8!}{4!4!}\right) = \frac{1}{8}\left(2+6+2+70\right) = 10$

Once having solved the question, calculating the first several values, I was able to find the sequence on OEIS as A003239 which gives additional ways to express the final result.