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|=1|G|∑g∈G|Xg| $$where Xg 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 γ(m,n) to arrange m red balls and n−m blue balls into a circle is given by γ(m,n)=1n∑d∣nϕ(d)(n/dm/d) where ϕ is the Euler totient function, and the binomial coefficient (ab) 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=Cn act on X by translation: identifying G≅Z/nZ, let k act by k(x1,x2,…,xn)=(x1+k,x2+k,…,xn+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 γ(m,n)=|X/G|.

For each k∈[n], it now suffices to count the size of |Xk|, 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 havexi+kℓ=xi for all integers ℓ. By B\'ezout's identity, this is equivalent to saying that [xi+dℓ′=xi for all integers ℓ′, where d=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 (x1,…,xd), 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 (ddm/n) ways. Now, note that the number of integers in [n] having gcd d with n is precisely given by ϕ(n/d). This shows that the desired sum using Burnside's lemma is γ(m,n)=1n∑d∣nϕ(nd)(ddm/n)=1n∑d∣nϕ(d)(n/dm/d) as desired. ◻

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