About A Toy Combinatorial Application of Burnside’s Lemma

Recently, a classmate posed to me the following problem: given $4$ red balls and $4$ blue balls, how many ways are there to arrange them into a circle? As usual, the red balls and blue balls respectively are identical, and we count configurations identical up to rotation to be the same. In the present case, a bit of thinking and casework shows that the answer is $10$.

This prompts the following generalisation. Given $m$ red balls and $n−m$ blue balls, how many ways are there to arrange them into a circle? I solved this problem in around 1.5 hours during a school lesson; I record the solution here.

The solution utilises a nice counting tool from group theory, Burnside's lemma.

Burnside’s Lemma. Given a finite group $G$ acting on a set $X$, the number of orbits $|X/G|$ is given by$$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g| $$where $X^g$ denotes the subset of $X$ fixed by the action of $g$.

I claim that this is the solution to the generalised problem.

Theorem. The number of ways $\gamma (m,n)$ to arrange $m$ red balls and $n−m$ blue balls into a circle is given by $$\gamma (m,n)=\frac{1}{n}\sum_{d\mid n}\phi(d)\binom{n/d}{m/d}$$ where $\phi$ is the Euler totient function, and the binomial coefficient $\binom{a}{b}$ is understood to be zero whenever $b$ is not an integer.

Proof. We reframe the original problem as follows. Let $X=\{0,1\}^n$ be the space of $n$-strings comprised of two digits, one of which represents each colour. Let $G=C_n$ act on $X$ by translation: identifying $G\cong \mathbb{Z}/n\mathbb{Z}$, let $k$ act by

$$ k(x_1,x_2,…,x_n)=(x_{1+k},x_{2+k},…,x_{n+k}) $$ where subscripts are considered modulo $n$. Then the action of $G$ precisely quantifies the rotational symmetry in the problem. The desired value is then $\gamma (m,n)=|X/G|$.

For each $k\in [n]$, it now suffices to count the size of $|X^k|$, upon which a direct application of Burnside's Lemma solves the problem. This is the same as asking for the number of $n$-strings fixed by rotation by $k$. This requires that, for all indices $i$, we have $$ x_{i+kℓ}=x_i $$ for all integers $\ell $. By Bezout's identity, this is equivalent to saying that $$ x_{i+dℓ′}=x_i $$ for all integers $\ell ’$, where $d=\mathrm{gcd}(m,n)$. Hence an equivalent problem is to count the number of ways to pick a $d$-string satisfying the conditions of the problem for the values of $(x_1,…,x_d)$, which now fixes the rest of $x$. We are free to choose any configuration so long as the total number of red balls, say, is correct, which translates to choosing precisely $m/(n/d)$ red balls within this d-string, of which there are $$\binom{d}{dm/n}$$ ways. Now, note that the number of integers in $[n]$ having gcd $d$ with $n$ is precisely given by $\phi(n/d)$. This shows that the desired sum using Burnside's lemma is $$\gamma (m,n)=\frac{1}{n}\sum_{d\mid n}\phi\left(\frac{n}{d}\right)\binom{d}{dm/n}=\frac{1}{n}\sum_{d\mid n}\phi(d)\binom{n/d}{m/d}$$ as desired. ◻

This prompts, perhaps, study of generalisations of this problem with more colours than 2, and of properties of $\gamma(m,n)$ --- perhaps considering their generating functions may be fruitful.