Intereting Posts

Boy Born on a Tuesday – is it just a language trick?
Does $|f|$ locally constant imply $f$ constant globally?
Bijective proof for equal number of odd-sized/even-sized subsets of a finite set
Proving that any rational number can be represented as the sum of the cubes of three rational numbers
Let $f$ be a continuous function satisfying $\lim \limits_{n \to \infty}f(x+n) = \infty$ for all $x$. Does $f$ satisfy $f(x) \to \infty$?
Sitting in chairs with empty space
What Is The Limit Of The Sequence: $\frac{n^3}{{((3n)!)^\frac{1}{n}}}$
Does the following have a solution for f(x,y)?
How to compute eigenvalues of big $5×5$ matrix (symmetric matrix) .
Factorial of 0 – a convenience?
What is the exact definition of a reflexive relation?
Polynomial $P(a)=b,P(b)=c,P(c)=a$
Presheaf image of a monomorphism of sheaves is a sheaf
Circular determinant problem
Munkres Topology, page 102, question 19:a

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.

- Monochromatic Rectangle of a 2-Colored 8 by 8 Lattice Grid
- Finding a generating function of a series
- How do I compute binomial coefficients efficiently?
- Transforming a latin square into a sudoku
- Prove that $n! \equiv \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k+r)^{n} $
- Check my answer: A slight modification to the 'hat-check' problem.
- (combinatorics) prove that on average, n-permutations have Hn cycles without mathematical induction.
- Solutions to $\binom{n}{5} = 2 \binom{m}{5}$
- Calculating probability with n choose k
- Number of decompositions of 20 into four integer parts

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.

- Ideal class group of a one-dimensional Noetherian domain
- Prove $\csc(x)=\sum_{k=-\infty}^{\infty}\frac{(-1)^k}{x+k\pi}$
- Units of polynomial rings over a field
- Is there a reason why the number of non-isomorphic graphs with $v=4$ is odd?
- Möbius transformations on $D$ such that $f(D)=D$
- Big List of Erdős' elementary proofs
- How to integrate $\frac {\cos (7x)-\cos (8x)}{1+2\cos (5x)} $ ?
- The fibers of a finite morphism of affine varieties are all finite
- Description of the Universe $V$
- Software for drawing geometry diagrams
- Algebraic Identity $a^{n}-b^{n} = (a-b) \sum\limits_{k=0}^{n-1} a^{k}b^{n-1-k}$
- Number of cycles in complete graph
- How to prove periodicity of $\sin(x)$ or $\cos(x)$ starting from the Taylor series expansion?
- A $\{0,1\}$-matrix with positive spectrum must have all eigenvalues equal to $1$
- Proof of Fourier Inverse formula for $L^1$ case