Counting Circles

Here’s one of my favorite problems: How many ways are there to arrange 3 red marbles and 2 blue marbles into a circle?

1. Intro to combinatorics

Let’s start with something simpler: Arranging the same marbles into a sequence.
Imagine 5 empty boxes with numbers from 1 to 5 written on them. The ways of arranging the 3 red and 2 blue marbles into a sequence correspond one-to-one to the ways to put them (one each) into these boxes.
We’ll do that by first placing all the red ones and then the blue ones. For the first one, we have 5 possible boxes to put it into; For the second one, there are only 4 left and for the third one there are 3 choices. After that, the rest of the boxes has to be filled with blue marbles.

You might be inclined to say that the answer must thus be $5\times 4\times 3$, but that’s not quite right because the red marbles are indistinguishable from each other. For example, placing the first red marble into box 1 and the second one into box 2 results in the same thing as placing the first one into box 2 and the second one into box 1.

But what if they were distinguishable? Say we write numbers onto the red marbles. The exact numbers don’t really matter (only that no two red marbles have the same number), but let’s just go with 1, 2, and 3. Simple and easy.
Now that we’ve numbered them, the number of ways to place these three marbles into 5 boxes is actually $5\times 4\times 3$.

But consider such a placement with the numbered marbles already in the boxes. We could also have got there by placing our original, indistinguishable marbles into the boxes first and then writing the numbers onto them.
Let’s do that in order: For each possible placement of the indistinguishable marbles, there are 3 possible choices for the number 1, then 2 possible choices for the number 2, then the final number 3 has to be the remaining one.
Thus, the total number of ways to write the numbers 1, 2, 3 onto the three marbles is $3\times 2\times 1=6$.

So, if we call the number of ways to place 3 indistinguishable marbles into 5 numbered boxes $𝑁$, we know that the number of ways to place 3 distinguishable marbles into the same boxes is $6\times 𝑁$.
But from before, we also know that this number must be equal to $5\times 4\times 3$, so we can deduce that$$\begin{array}{cc}6\times 𝑁& =5\times 4\times 3\\ ⟺𝑁& =\frac{5\times 4\times 3}{6}=10.\end{array}$$Let’s clean this up a bit with some notation:

• An expression like $5\times 4\times 3$ is called a falling power and written as $5^{\underline{3}}$. Other examples would be ${10}^{\underline{2}}=10\times 9$ or $7^{\underline{4}}=7\times 6\times 5\times 4$.
  In general, ${𝑛}^{\underline{𝑘}}=𝑛\times \dots \times \left(𝑛-𝑘+1\right)$.

• A special case of the falling power is the factorial $𝑛!≔{𝑛}^{\underline{𝑛}}$. We encountered this for the number of ways to write numbers onto the red marbles, $3!=6$.

So, using this, we can write$$𝑁=\frac{5^{\underline{3}}}{3!}.$$This number $𝑁$ is also called a binomial coefficient, or “5 choose 3”. There are varying notations for it, but I’ll go with$$𝑁=𝐶\left(5,3\right).$$Note that nothing in this argument actually relied on any properties of the numbers 3 and 5, so, in general, the number of ways to put $𝑘$ red and $\left(𝑛-𝑘\right)$ blue marbles into a sequence is$$𝐶\left(𝑛,𝑘\right)=\frac{{𝑛}^{\underline{𝑘}}}{𝑘!}.$$

By the way, here’s the list of possible sequences: RRRBB, RRBRB, RRBBR, RBRRB, RBRBR, RBBRR, BRRRB, BRRBR, BRBRR, BBRRR.
We can be sure that that’s all of them by just confirming that there’re no duplicates and that there’s really 10 of them.

2. Counting with Symmetry

That was for a sequence of marbles, but what about a row of them?

You might say “that’s the same”, but the difference is that a row has reflection symmetry.
In particular, imagine a row of marbles lying on the ground. You can just look at them from the opposite side and thus swap what you see as the left and right end, but the row is still the same.

So, in general, there are up to two sequences corresponding to any given row. For example, the sequences RRBBR and RBBRR are the same row because they’re just mirror images of each other.

But it gets more complicated when you consider RBRBR. This row is a palindrome, meaning it is its own mirror image. The existence of rows like that means we can’t just divide by two to go from the number of sequences to the number of rows.

But we can split the sequences into palindromes and non-palindromes. Then, each palindrome counts as one row and each non-palindrome counts as half a row. So, $𝑃$ being the number of palindromes and $\overline{𝑃}$ being the number of non-palindromes, we’d have$$\begin{array}{cc}{𝑁}_{\text{row}}& =𝑃+\frac{1}{2}\overline{𝑃}\\ & =\frac{1}{2}\left(𝑃+𝑃+\overline{𝑃}\right)\\ & =\frac{1}{2}\left(𝑃+{𝑁}_{\text{seq}}\right),\end{array}$$where ${𝑁}_{\text{seq}}=𝐶\left(5,3\right)$ is the number of sequences.

So how many palindromes are there?
Since we have an even number of blue and an odd number of red marbles, the marble in the middle must be red.
The remaining four marbles are split into a left and right half and the right half must be the mirror image of the left half. So we are free to choose the left half, but that’s it. In other words, our freedom of choice corresponds to placing one blue and one red marble into a sequence:$$𝑃=𝐶\left(2,1\right).$$

So the total comes out to$${𝑁}_{\text{row}}=\frac{1}{2}\left[𝐶\left(2,1\right)+𝐶\left(5,3\right)\right]=6.$$Here’s the list:

• Palindromes: RBRBR, BRRRB

• Non-palindromes: RRRBB/BBRRR, RRBRB/BRBRR, RRBBR/RBBRR, RBRRB/BRRBR

Generalizing this is somewhat easy, but depends on the parity of $𝑛$ and $𝑘$.

• If the total number of marbles is odd, then we always have an odd number of one type of marble and an even number of the other type. This is the same situation as the previous example, so the general formula is$$\frac{1}{2}\left[𝐶\left(\lfloor \frac{𝑛}{2}\rfloor ,\lfloor \frac{𝑘}{2}\rfloor \right)+𝐶\left(𝑛,𝑘\right)\right],$$where $\lfloor 𝑥\rfloor$ is the largest integer less than or equal to $𝑥$; In particular, $\lfloor \frac{𝑛}{2}\rfloor =\frac{𝑛-1}{2}$ since $𝑛$ is odd.
  It doesn’t matter if we pick $𝑘$ to be odd or even, since¹$$𝐶\left(\lfloor \frac{𝑛}{2}\rfloor ,\lfloor \frac{𝑘}{2}\rfloor \right)=𝐶\left(\lfloor \frac{𝑛}{2}\rfloor ,\lfloor \frac{𝑛-𝑘}{2}\rfloor \right).$$
• If the total number of marbles is even, then it’s even easier. Either there’s an odd number of both red and blue marbles, in which case there are zero palindromes, or there’s an even number of both, in which case the number of palindromes is again$$𝑃=𝐶\left(\lfloor \frac{𝑛}{2}\rfloor ,\lfloor \frac{𝑘}{2}\rfloor \right),$$where now $\lfloor \frac{𝑛}{2}\rfloor =\frac{𝑛}{2}$ and $\lfloor \frac{𝑘}{2}\rfloor =\frac{𝑘}{2}$.

I’ll use the Iverson Bracket to unify these three cases. Its definition is that $⟦𝜑⟧=1$ if $𝜑$ is true and $⟦𝜑⟧=0$ if $𝜑$ is false.

So the general formula for $𝑃$ is$$𝑃=⟦𝑛\text{odd or}𝑘\text{even}⟧𝐶\left(\lfloor \frac{𝑛}{2}\rfloor ,\lfloor \frac{𝑘}{2}\rfloor \right).$$

Thus, the general formula for the number of ways to place $𝑘$ red marbles and $\left(𝑛-𝑘\right)$ blue marbles into a row is$${𝑁}_{\text{row}}=\frac{1}{2}\left[𝐶\left(𝑛,𝑘\right)+⟦𝑛\text{odd or}𝑘\text{even}⟧𝐶\left(\lfloor \frac{𝑛}{2}\rfloor ,\lfloor \frac{𝑘}{2}\rfloor \right)\right].$$

3. Group Theory

The general study of symmetries as part of abstract algebra is called group theory.

I’ll introduce the parts of it we will need in a sort-of unconventional way.

To start with, consider the idea of a symmetry transformation. The most well-known symmetry transformations are reflections and rotations.
Something is symmetric if it stays the same after performing some symmetry transformation.

To get to a general definition of symmetry transformations, one can think long and hard about what reflections and rotations have in common, but I’ll cut it short here and just tell you that the deciding property is invertibility.

• Reflections are their own inverses: Perform the same reflection twice and you always end up with what you started with.

• Rotations always have an inverse. For example, rotating the minute hand of a clock 20° clockwise is undone by rotating it 20° counterclockwise.

You might be a bit confused since, if something is symmetric, you already end up with what you started with after performing one symmetry transformation, but the important thing is that the description of invertibility also holds for non-symmetric things.
For example, reversing the letters in a palindrome like “wow” results in the same word, but for a non-palindrome like “word”, you get “drow”, and only after performing the inverse transformation (in this case “reversing again”), you end up back where you started.

Now let’s think about formalizing this using the example of the minute hand on a special clock. The clock isn’t really useful for telling the time; It is basically a circular image with a singular hand on top of it.

The reason for this example over just a regular clock is that it gives us a reason to call rotating the hand a symmetry operation. Namely, if the image behind the hand has some rotational symmetry, for example if it’s the image of a playing card with 180° rotational symmetry, then rotating the hand by that amount is basically the same as rotating the entire clock by that amount, which means that the clock hasn’t really changed. ²

In math, basically everything we deal with is a set, so we need a set $𝑋$ to perform symmetry operations on. In particular, the elements of $𝑋$ will be the input/output states of the symmetry operations, so that we can model the operations themselves as functions $𝑋\to 𝑋$.

In our example, the symmetry operations are rotations of the hand, so the input/output states of that can be taken to just be the position of the hand on the clock, which can be modeled as an angle measured in degrees, so a real number in the interval $\left[0,360\right)$.

Then, as stated before, symmetry transformations need to be invertible, so we’re looking at the invertible functions (aka. “bijections”) from $𝑋$ to $𝑋$.
The set of those bijections will be denoted $𝑆\left(𝑋\right)$ here; It underlies what’s called the symmetric group of $𝑋$.

I won’t define the term “group” in general, since it’s more abstract than we need. Instead, we’ll be working with subgroups of $𝑆\left(𝑋\right)$, which are defined as a subset $𝐺$ of $𝑆\left(𝑋\right)$ such that

1. For any functions $𝑓,𝑔\in 𝐺$, the composition $𝑓\circ 𝑔$ is also in $𝐺$.

2. For any function $𝑓\in 𝐺$, the inverse ${𝑓}^{-1}$ is also in $𝐺$.

Note that a combination of the two requirements implies $𝑓\circ {𝑓}^{-1}=\mathrm{<mtext>id</mtext>}\in 𝐺$, so a subgroup of $𝑆\left(𝑋\right)$ always contains the identity function.

These conditions basically mean that $𝐺$ is a “self-contained” set of symmetry operations. For example:

• Condition 1 means that, if I can rotate by 20° ($𝑓$), I should also be able to rotate by 40° ($𝑓\circ 𝑓$).

• Condition 2 means that, if I can rotate by 20° clockwise ($𝑓$), I should also be able to rotate by 20° counterclockwise (${𝑓}^{-1}$).

Now we can recontextualize the previous section: We had a set $𝑋$ of sequences of 3 red and 2 blue marbles and a subgroup $𝐺=\left\{\mathrm{<mtext>id</mtext>},𝑠\right\}$ of $𝑆\left(𝑋\right)$, where $𝑠$ is the function that reverses a sequence. The conditions are easily confirmed:

1. For any $𝑓\in 𝐺$, $𝑓\circ \mathrm{<mtext>id</mtext>}=𝑓\in 𝐺$ and $\mathrm{<mtext>id</mtext>}\circ 𝑓=𝑓\in 𝐺$. Additionally, $𝑠\circ 𝑠=\mathrm{<mtext>id</mtext>}\in 𝐺$.

2. ${\mathrm{<mtext>id</mtext>}}^{-1}=\mathrm{<mtext>id</mtext>}\in 𝐺$ and ${𝑠}^{-1}=𝑠\in 𝐺$.

4. Burnside’s Lemma

We’re close to the payoff of all that group theory.

First, we need another definition: Given a set $𝑋$ and a subgroup $𝐺$ of $𝑆\left(𝑋\right)$,

• For each element $𝑓\in 𝐺$, the set of fixpoints of $𝑓$ is defined as$${\text{fix}}_{𝑋}\left(𝑓\right)=\left\{𝑥\in 𝑋|𝑓\left(𝑥\right)=𝑥\right\}.$$
• For each element $𝑥\in 𝑋$, the orbit ${\left[𝑥\right]}_{𝐺}$ of $𝑥$ is the set of possible outcomes from performing one of the symmetry transformations from $𝐺$ on $𝑥$:$${\left[𝑥\right]}_{𝐺}=\left\{𝑓\left(𝑥\right)|𝑓\in 𝐺\right\}.$$These orbits cleanly partition $𝑋$: Each $𝑥\in 𝑋$ is part of one and only one orbit.
  The set of orbits is denoted $𝑋/𝐺$:$$𝑋/𝐺=\left\{{\left[𝑥\right]}_{𝐺}|𝑥\in 𝑋\right\}.$$

In Section 2, the orbits corresponded to the rows of marbles: For a sequence $𝑥$ of marbles, we had ${\left[𝑥\right]}_{𝐺}=\left\{𝑥,𝑠\left(𝑥\right)\right\}$. For non-palindromes, this set has two elements; For palindromes, $𝑠\left(𝑥\right)=𝑥$ by definition.

In general, our problem becomes finding the number of orbits, i.e. $\left|𝑋/𝐺\right|$.

This is solved by something called Burnside’s Lemma, which states that$$\left|𝑋/𝐺\right|=\frac{1}{\left|𝐺\right|}\sum _{𝑓\in 𝐺}\left|{\text{fix}}_{𝑋}\left(𝑓\right)\right|.$$

For a small example, recall $𝐺=\left\{\mathrm{<mtext>id</mtext>},𝑠\right\}$ from Section 2. For this, the formula becomes$$\left|𝑋/𝐺\right|=\frac{1}{2}\left(\left|{\text{fix}}_{𝑋}\left(\mathrm{<mtext>id</mtext>}\right)\right|+\left|{\text{fix}}_{𝑋}\left(𝑠\right)\right|\right),$$where ${\text{fix}}_{𝑋}\left(\mathrm{<mtext>id</mtext>}\right)=𝑋$ and ${\text{fix}}_{𝑋}\left(𝑠\right)$ is the set of palindromes. Setting ${𝑁}_{\text{seq}}=\left|𝑋\right|$ and $𝑃=\left|{\text{fix}}_{𝑋}\left(𝑠\right)\right|$, we can see that this is exactly the formula we had arrived at:$$\left|𝑋/𝐺\right|=\frac{1}{2}\left({𝑁}_{\text{seq}}+𝑃\right).$$

4.1. Proof

The following is a proof of Burnside’s Lemma, adapted from Wikipedia. ³

Start with the right-hand side and notice that$$\begin{array}{cc}\sum _{𝑓\in 𝐺}\left|{\text{fix}}_{𝑋}\left(𝑓\right)\right|& =\sum _{𝑓\in 𝐺}\left|\left\{𝑥\in 𝑋|𝑓\left(𝑥\right)=𝑥\right\}\right|\\ & =\left|\left\{\left(𝑓,𝑥\right)\in 𝐺\times 𝑋|𝑓\left(𝑥\right)=𝑥\right\}\right|\\ & =\sum _{𝑥\in 𝑋}\left|\left\{𝑓\in 𝐺|𝑓\left(𝑥\right)=𝑥\right\}\right|\\ & =\sum _{𝑥\in 𝑋}\left|{\left[\mathrm{<mtext>id</mtext>}\right]}^{𝑥}\right|,\end{array}$$where we have defined$${\left[𝑔\right]}^{𝑥}≔\left\{𝑓\in 𝐺|𝑓\left(𝑥\right)=𝑔\left(𝑥\right)\right\}$$for any $𝑔\in 𝐺$.

Note that this partitions $𝐺$, which is proven as follows: Consider the set$${\left[𝑔\right]}^{𝑥}\cap {\left[ℎ\right]}^{𝑥}=\left\{𝑓\in 𝐺|𝑓\left(𝑥\right)=𝑔\left(𝑥\right)\text{and}𝑓\left(𝑥\right)=ℎ\left(𝑥\right)\right\}.$$Either $𝑔\left(𝑥\right)=ℎ\left(𝑥\right)$ and ${\left[𝑔\right]}^{𝑥}={\left[ℎ\right]}^{𝑥}$, or $𝑔\left(𝑥\right)\ne ℎ\left(𝑥\right)$ and ${\left[𝑔\right]}^{𝑥}\cap {\left[ℎ\right]}^{𝑥}=\varnothing$.

Next, for any $𝑔\in 𝐺$, consider the precomposition map ${𝑔}_{\ast }:𝐺\to 𝐺$ defined by ${𝑔}_{\ast }\left(𝑓\right)≔𝑔\circ 𝑓$. It is a bijection with inverse ${\left({𝑔}^{-1}\right)}_{\ast }$. This implies that, for any set $𝐻\subseteq 𝐺$,$$\left|\left\{{𝑔}_{\ast }\left(𝑓\right)|𝑓\in 𝐻\right\}\right|=\left|𝐻\right|.$$

In particular, let $𝐻={\left[\mathrm{<mtext>id</mtext>}\right]}^{𝑥}$, then we have proven that, for any $𝑔\in 𝐺$,$$\begin{array}{cc}\left|{\left[\mathrm{<mtext>id</mtext>}\right]}^{𝑥}\right|& =\left|\left\{{𝑔}_{\ast }\left(𝑓\right)|𝑓\in {\left[\mathrm{<mtext>id</mtext>}\right]}^{𝑥}\right\}\right|\\ & =\left|\left\{𝑔\circ 𝑓|𝑓\in {\left[\mathrm{<mtext>id</mtext>}\right]}^{𝑥}\right\}\right|\\ & =\left|\left\{ℎ|{𝑔}^{-1}\circ ℎ\in {\left[\mathrm{<mtext>id</mtext>}\right]}^{𝑥}\right\}\right|.\end{array}$$Now note that$${𝑔}^{-1}\circ ℎ\in {\left[\mathrm{<mtext>id</mtext>}\right]}^{𝑥}⟺{𝑔}^{-1}\left(ℎ\left(𝑥\right)\right)=𝑥⟺ℎ\left(𝑥\right)=𝑔\left(𝑥\right),$$which implies$$\left|{\left[\mathrm{<mtext>id</mtext>}\right]}^{𝑥}\right|=\left|\left\{ℎ|ℎ\left(𝑥\right)=𝑔\left(𝑥\right)\right\}\right|=\left|{\left[𝑔\right]}^{𝑥}\right|.$$Recall that this holds for all $𝑔\in 𝐺$.

Now we want to find the number of distinct sets ${\left[𝑔\right]}^{𝑥}$. This is easily done by noticing that there is a bijection between ${\left[𝑔\right]}^{𝑥}$ and $𝑔\left(𝑥\right)$: Each ${\left[𝑔\right]}^{𝑥}$ uniquely defines $𝑔\left(𝑥\right)$ and each $𝑎=𝑔\left(𝑥\right)$ uniquely defines ${\left[𝑔\right]}^{𝑥}=\left\{𝑓\in 𝐺|𝑓\left(𝑥\right)=𝑎\right\}$.
Thus, the number of distinct sets ${\left[𝑔\right]}^{𝑥}$ is equal to the number of distinct values $𝑔\left(𝑥\right)$, i.e.$$\left|\left\{𝑔\left(𝑥\right)|𝑔\in 𝐺\right\}\right|=\left|{\left[𝑥\right]}_{𝐺}\right|.$$

Since $𝐺$ is partitioned into the ${\left[𝑔\right]}^{𝑥}$, which all have the same size $\left|{\left[𝑔\right]}^{𝑥}\right|=\left|{\left[\mathrm{<mtext>id</mtext>}\right]}^{𝑥}\right|$, and there are $\left|{\left[𝑥\right]}_{𝐺}\right|$ of them, it follows that the cardinality of $𝐺$ satisfies$$\left|𝐺\right|=\left|{\left[𝑥\right]}_{𝐺}\right|\cdot \left|{\left[\mathrm{<mtext>id</mtext>}\right]}^{𝑥}\right|.$$

Now recall the sum from the start and apply this:$$\begin{array}{cc}\sum _{𝑓\in 𝐺}\left|{\text{fix}}_{𝑋}\left(𝑓\right)\right|& =\sum _{𝑥\in 𝑋}\left|{\left[\mathrm{<mtext>id</mtext>}\right]}^{𝑥}\right|\\ & =\sum _{𝑥\in 𝑋}\left|𝐺\right|/\left|{\left[𝑥\right]}_{𝐺}\right|.\end{array}$$Split the sum over $𝑋$ along the orbits $𝑂\in 𝑋/𝐺$, noting that $𝑥\in 𝑂$ implies ${\left[𝑥\right]}_{𝐺}=𝑂$,$$\begin{array}{cc}\sum _{𝑓\in 𝐺}\left|{\text{fix}}_{𝑋}\left(𝑓\right)\right|& =\sum _{𝑥\in 𝑋}\left|𝐺\right|/\left|{\left[𝑥\right]}_{𝐺}\right|\\ & =\sum _{𝑂\in 𝑋/𝐺}\sum _{𝑥\in 𝑂}\left|𝐺\right|/\left|{\left[𝑥\right]}_{𝐺}\right|\\ & =\sum _{𝑂\in 𝑋/𝐺}\sum _{𝑥\in 𝑂}\left|𝐺\right|/\left|𝑂\right|\\ & =\sum _{𝑂\in 𝑋/𝐺}\left|𝐺\right|\\ & =\left|𝑋/𝐺\right|\cdot \left|𝐺\right|.\end{array}$$This immediately implies$$\left|𝑋/𝐺\right|=\frac{1}{\left|𝐺\right|}\sum _{𝑓\in 𝐺}\left|{\text{fix}}_{𝑋}\left(𝑓\right)\right|.$$Q.E.D.

5. Counting Circular Configurations

Now we’re technically ready to answer the original question of arranging 3 red and 2 blue marbles into a circle, but let’s warm up with a slightly easier one: “How many ways are there to arrange 5 marbles, any of which may be red or blue, into a circle?”

Restating this question into more formal language, we’re asking about the number of orbits, $\left|𝑌/𝐺\right|$, where $𝑌$ is the set of 5-long sequences of red and blue marbles, and $𝐺$ is one of two subgroups of $𝑆\left(𝑌\right)$:

1. The symmetry transformations that correspond to rotations of the circle. Since we encode the “circle” as a sequence, this means that these are functions that split the sequence into two contiguous subsequences and put those back together in the opposite order. For example, “ABCDE → CDEAB” or “ABCDE → EABCD”.
   In the jargon, this is called the cyclic group of order 5.

2. All of the previous transformations, together with reflections across either an element or a gap between elements. The number of these reflections is also equal to 5. (And in general equal to the number of elements in the sequence).
   In the jargon, this is called the dihedral group of order 10.

Call these ${𝐺}_1$ and ${𝐺}_2$.

All of these symmetry transformations can be generated from two basic elements:

• The simple rotation by one place: “ABCDE → BCDEA”, denoted $𝑟$.
  Formally, it is defined as ${𝑟\left(𝑥\right)}_{𝑖}≔{𝑥}_{𝑖+1}$ for $𝑖<5$ and ${𝑟\left(𝑥\right)}_5≔{𝑥}_1$.
  Alternatively, we can use the remainder operation: $𝑑\%𝑛$ is the non-negative remainder from dividing $𝑑$ by $𝑛$.⁴
  Using that, we can see that ${𝑟\left(𝑥\right)}_{𝑖}≔{𝑥}_{\left(𝑖\%5\right)+1}$ for all $𝑖$. For this, zero-based indexing is more convenient; With sequence index $𝑗\in \left\{0,\dots ,𝑛-1\right\}$, we get ${𝑟\left(𝑥\right)}_{𝑗}≔{𝑥}_{\left(𝑗+1\right)\%5}$.

• The simple reflection across a standard axis, again denoted $𝑠$.
  For simplicity, this is the exact same operation as was used in Section 2.
  Formally, it can be defined as ${𝑠\left(𝑥\right)}_{𝑖}≔{𝑥}_{6-𝑖}$. With zero-based indexing, this becomes ${𝑠\left(𝑥\right)}_{𝑗}≔{𝑥}_{5-𝑗}$.

In the first case, we can reach each of the possible transformations by applying $𝑟$ some number of times: ${𝑟}^0=\mathrm{<mtext>id</mtext>},{𝑟}^1=𝑟,{𝑟}^2,{𝑟}^3,{𝑟}^4$. Applying $𝑟$ 5 times always leaves the input untouched (${𝑟}^5=\mathrm{<mtext>id</mtext>}$), so ${𝑟}^{-1}={𝑟}^4$.

In the second case, we have the same thing with $𝑟$, and the reflections are all of the form ${𝑟}^{𝑘}\circ 𝑠\circ {𝑟}^{-𝑘}$, which should make intuitive sense: To reflect across some arbitrary axis, first rotate such that that axis moves to a standard position, then perform the standard reflection, then rotate back.

The first answer is then$$\left|𝑌/{𝐺}_1\right|=\frac{1}{5}\sum _{𝑘=0}^4\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\right)\right|.$$We still need to find ${\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\right)$, but since $\left|{\text{fix}}_{𝑌}\left(𝑓\right)\right|=\left|{\text{fix}}_{𝑌}\left({𝑓}^{-1}\right)\right|$, ${𝑟}^4={\left({𝑟}^1\right)}^{-1}$ and ${𝑟}^3={\left({𝑟}^2\right)}^{-1}$, we only need to find this for $𝑘=0$, $𝑘=1$, and $𝑘=2$.

• For $𝑘=0$, this is easy: $\left|{\text{fix}}_{𝑌}\left({𝑟}^0\right)\right|=\left|{\text{fix}}_{𝑌}\left(\mathrm{<mtext>id</mtext>}\right)\right|=\left|𝑌\right|=2^5=32$.

• For $𝑘=1$, ${𝑟}^1=𝑟$ moves each element of the sequence by one: ${𝑟\left(𝑥\right)}_{𝑖}={𝑥}_{𝑖+1}$ for $𝑖<5$ and ${𝑟\left(𝑥\right)}_5={𝑥}_1$. Thus, $𝑟\left(𝑥\right)=𝑥$ decomposes into ${𝑥}_{𝑖+1}={𝑥}_{𝑖}$ for $𝑖<5$ and ${𝑥}_1={𝑥}_5$, which results in ${𝑥}_{𝑖}={𝑥}_1$ for all $𝑖$, so there are only two choices: RRRRR and BBBBB, i.e. $\left|{\text{fix}}_{𝑌}\left(𝑟\right)\right|=2$.

• For $𝑘=2$, ${𝑟}^2$ moves each element of the sequence by two: ${𝑟\left(𝑥\right)}_{𝑖}={𝑥}_{\left(𝑖+2\right)\%5}$. Concretely, we decompose this into ${𝑥}_3={𝑥}_1,{𝑥}_4={𝑥}_2,{𝑥}_5={𝑥}_3,{𝑥}_1={𝑥}_4,{𝑥}_2={𝑥}_5$, which again results in ${𝑥}_{𝑖}={𝑥}_1$ for all $𝑖$, so $\left|{\text{fix}}_{𝑌}\left({𝑟}^2\right)\right|=2$.

This implies that$$\left|𝑌/{𝐺}_1\right|=\frac{1}{5}\sum _{𝑘=0}^4\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\right)\right|=\frac{1}{5}\left(32+4\cdot 2\right)=8.$$

The second answer is found similarly, by also considering $\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}𝑠{𝑟}^{-𝑘}\right)\right|$ for $𝑘=0\dots 4$.
This is even easier because all of those reflections are just rotations of each other, so their fixpoint sets have to be rotations of each other and in particular have to be the same size. Thus, we only need to find $\left|{\text{fix}}_{𝑌}\left(𝑠\right)\right|$.

• $𝑠$ is defined as ${𝑠\left(𝑥\right)}_{𝑖}={𝑥}_{6-𝑖}$, which decomposes into ${𝑥}_1={𝑥}_5$ and ${𝑥}_2={𝑥}_4$, so we can assign 3 of the 5 elements freely, giving $\left|{\text{fix}}_{𝑌}\left(𝑠\right)\right|=2^3=8$.

This implies that$$\left|𝑌/{𝐺}_2\right|=\frac{1}{10}\sum _{𝑘=0}^4\left(\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\right)\right|+\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\circ 𝑠\circ {𝑟}^{-𝑘}\right)\right|\right)=\frac{1}{10}\left(32+4\cdot 2+5\cdot 8\right)=8,$$meaning that the ${𝐺}_1$-orbits of $𝑌$ are already reflection-symmetric.

We can now find a general formula that gives the number of ways to arrange $𝑛$ marbles, each red or blue, into a circle.

First of all, some caution is highly necessary with the definition of ${𝐺}_2$. To rotate the axis of mirror symmetry by ${𝑟}^{𝑘}$, you use the formula ${𝑟}^{𝑘}\circ 𝑠\circ {𝑟}^{-𝑘}$, but for even $𝑛$, this only reaches half of the possible symmetry axes: Since $𝑠$ mirrors across an axis that doesn’t touch any marbles, all of its rotations by ${𝑟}^{𝑘}$ will also only mirror across such an axis.
In this case, we also need rotations of $𝑠$ by ${𝑟}^{\frac{2𝑘+1}{2}}$, which are the missing reflections across axes that each go through two marbles. Strictly speaking, ${𝑟}^{\frac{2𝑘+1}{2}}$ isn’t defined in ${𝐺}_2$, but we can save ourselves by noting that$${𝑟}^{𝑘}\circ 𝑠\circ {𝑟}^{-𝑘}={𝑟}^{2𝑘}\circ 𝑠$$for all $𝑘$, so if we set $𝑘\leftarrow \frac{2𝑘+1}{2}$, we get that these reflections are given by$${𝑟}^{2𝑘+1}\circ 𝑠.$$This means that we should work with the definition $\left\{{𝑟}^{𝑘}\circ 𝑠|𝑘\in \mathbb{Z}\right\}$ for the set of reflections, which always works, including when $𝑛$ is even.

Now let $𝑌$ be the set of sequences of $𝑛$ marbles, each red or blue. We now index these sequences starting at zero to keep the logic a bit simpler.

• We first find $\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\right)\right|$ for $𝑘=0\dots \left(𝑛-1\right)$. Note that ${𝑟}^{𝑘}$ is defined as$${𝑟}^{𝑘}{\left(𝑥\right)}_{𝑗}={𝑥}_{\left(𝑗+𝑘\right)\%𝑛},$$so the equation ${𝑟}^{𝑘}\left(𝑥\right)=𝑥$ decomposes into$${𝑥}_{\left(𝑗+𝑘\right)\%𝑛}={𝑥}_{𝑗}$$for all $𝑗=0\dots \left(𝑛-1\right)$. Substitute $𝑗\leftarrow \left(𝑗+𝑘\right)\%𝑛$ and note that $\left(\left(𝑗+𝑘\right)\%𝑛+𝑘\right)\%𝑛=\left(𝑗+2𝑘\right)\%𝑛$ to further find$${𝑥}_{\left(𝑗+2𝑘\right)\%𝑛}={𝑥}_{\left(𝑗+𝑘\right)\%𝑛},$$which implies$${𝑥}_{\left(𝑗+2𝑘\right)\%𝑛}={𝑥}_{𝑗}.$$We can repeat this process indefinitely to arrive at$${𝑥}_{\left(𝑗+𝑚𝑘\right)\%𝑛}={𝑥}_{𝑗}$$for all $𝑚\in \mathbb{N}$.

  Since there are only finitely many indices, but $\left(𝑗+𝑚𝑘\right)\%𝑛$ is an infinite sequence in $𝑚$, there must be a first $𝑚$ for which $\left(𝑗+𝑚𝑘\right)\%𝑛=\left(𝑗+𝑙𝑘\right)\%𝑛$ with some $𝑙<𝑚$.
  This equation of remainders can also be written as $𝑗+𝑚𝑘\equiv 𝑗+𝑙𝑘\left(\text{mod}𝑛\right)$.
  It must then be the case that $𝑙=0$, because otherwise we would have $𝑗+\left(𝑚-1\right)𝑘\equiv 𝑗+\left(𝑙-1\right)𝑘\left(\text{mod}𝑛\right)$, which would contradict the assumption that $𝑚$ was the first number with the desired property.

  This means that there is an $𝑚$ such that, for some $𝑙\in \mathbb{Z}$,$$𝑗+𝑚𝑘=𝑙𝑛+𝑗.$$Subtract $𝑗$ on both sides and divide by $𝑘$ to get$$𝑚=\frac{𝑙𝑛}{𝑘}.$$We want the smallest $𝑚$ for which this equation holds; In other words, we need $𝑙𝑛$ to be the smallest multiple of $𝑛$ that is divisible by $𝑘$.
  This is, by definition, the least common multiple of $𝑘$ and $𝑛$, so$$𝑚=\frac{\text{lcm}\left(𝑘,𝑛\right)}{𝑘}=\frac{𝑛}{\mathrm{<mtext>gcd</mtext>}\left(𝑘,𝑛\right)},$$where the second equality follows from $𝑘𝑛=\mathrm{<mtext>gcd</mtext>}\left(𝑘,𝑛\right)\text{lcm}\left(𝑘,𝑛\right)$.

  With this, we have shown that each chain of equalities contains $\frac{𝑛}{\mathrm{<mtext>gcd</mtext>}\left(𝑘,𝑛\right)}$ entries, and since they form a partition of the elements of the sequence, there are $\frac{𝑛}{\frac{𝑛}{\mathrm{<mtext>gcd</mtext>}\left(𝑘,𝑛\right)}}=\mathrm{<mtext>gcd</mtext>}\left(𝑘,𝑛\right)$ of them.

  Each of these chains leaves one choice of red or blue, so we get$$\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\right)\right|=2^{\mathrm{<mtext>gcd</mtext>}\left(𝑘,𝑛\right)}.$$

• Now we find $\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\circ 𝑠\right)\right|$, but since we redefined ${𝐺}_2$, it’s better to not appeal to the previous argument here. (And it would also be wrong to do that, as we will shortly see.)

  There are three cases to consider:

  • If $𝑘$ is even, we have ${𝑟}^{𝑘}\circ 𝑠={𝑟}^{\frac{𝑘}{2}}\circ 𝑠\circ {𝑟}^{-\frac{𝑘}{2}}$ and thus$$\begin{array}{cc}{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\circ 𝑠\right)& =\left\{𝑦\in 𝑌|{𝑟}^{\frac{𝑘}{2}}\left(𝑠\left({𝑟}^{-\frac{𝑘}{2}}\left(𝑦\right)\right)\right)=𝑦\right\}\\ & =\left\{{𝑟}^{\frac{𝑘}{2}}\left(𝑧\right)|𝑧\in 𝑌,𝑠\left(𝑧\right)=𝑧\right\}\\ & =\left\{{𝑟}^{\frac{𝑘}{2}}\left(𝑧\right)|𝑧\in {\text{fix}}_{𝑌}\left(𝑠\right)\right\}.\end{array}$$Note that ${𝑟}^{\frac{𝑘}{2}}$ is a bijection, which immediately implies$$\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\circ 𝑠\right)\right|=\left|{\text{fix}}_{𝑌}\left(𝑠\right)\right|$$and the same logic from before gives us$$\left|{\text{fix}}_{𝑌}\left(𝑠\right)\right|=2^{\lceil \frac{𝑛}{2}\rceil },$$where $\lceil 𝑟\rceil$ is the smallest integer greater than or equal to $𝑟$. This comes from the fact that we can freely choose the middle element for odd $𝑛$.

  • If $𝑘$ is odd and $𝑛$ is odd, we have that $𝑛+𝑘$ is even and ${𝑟}^{𝑘}={𝑟}^{𝑛+𝑘}$, so this just reduces to the previous case for $𝑘\leftarrow 𝑛+𝑘$.

  • If $𝑘$ is odd and $𝑛$ is even, we have ${𝑟}^{𝑘}\circ 𝑠={𝑟}^{\frac{𝑘-1}{2}}\circ 𝑟\circ 𝑠\circ {𝑟}^{-\frac{𝑘-1}{2}}$ and thus$$\begin{array}{cc}{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\circ 𝑠\right)& =\left\{𝑦\in 𝑌|{𝑟}^{\frac{𝑘-1}{2}}\left(𝑟\left(𝑠\left({𝑟}^{-\frac{𝑘-1}{2}}\left(𝑦\right)\right)\right)\right)=𝑦\right\}\\ & =\left\{{𝑟}^{\frac{𝑘-1}{2}}\left(𝑧\right)|𝑧\in 𝑌,𝑟\left(𝑠\left(𝑧\right)\right)=𝑧\right\}\\ & =\left\{{𝑟}^{\frac{𝑘-1}{2}}\left(𝑧\right)|𝑧\in {\text{fix}}_{𝑌}\left(𝑟\circ 𝑠\right)\right\}.\end{array}$$Note that ${𝑟}^{\frac{𝑘-1}{2}}$ is a bijection, which immediately implies$$\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\circ 𝑠\right)\right|=\left|{\text{fix}}_{𝑌}\left(𝑟\circ 𝑠\right)\right|.$$Then note that $𝑟\circ 𝑠$ is defined by$${𝑟\left(𝑠\left(𝑥\right)\right)}_{𝑗}={𝑠\left(𝑥\right)}_{\left(𝑗+1\right)\%𝑛}={𝑥}_{𝑛-\left(𝑗+1\right)\%𝑛},$$which is equal to ${𝑥}_{𝑛-1-𝑗}$ for $𝑗=0\dots 𝑛-2$ and to ${𝑥}_{𝑛-1}$ for $𝑗=𝑛-1$.
    This means that $𝑟\left(𝑠\left(𝑥\right)\right)=𝑥$ decomposes into ${𝑥}_{𝑛-1-𝑖}={𝑥}_{𝑖}$ for all $𝑗=0\dots 𝑛-2$, which leaves ${𝑥}_{\frac{𝑛}{2}}$ and ${𝑥}_{𝑛}$ completely free and arranges the other elements into pairs.

    Thus, there are $2+\frac{𝑛-2}{2}=\frac{𝑛}{2}+1$ places where we can choose either red or blue, so we get$$\left|{\text{fix}}_{𝑌}\left(𝑟\circ 𝑠\right)\right|=2^{\frac{𝑛}{2}+1}$$

  We can summarize all these cases by saying that$$\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\circ 𝑠\right)\right|=2^{\lceil \frac{𝑛}{2}\rceil +⟦𝑛\text{even and}𝑘\text{odd}⟧}.$$

For the answers, this gives us$$\begin{array}{cc}\left|𝑌/{𝐺}_1\right|& =\frac{1}{𝑛}\sum _{𝑘=0}^{𝑛-1}\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\right)\right|\\ & =\frac{1}{𝑛}\sum _{𝑘=0}^{𝑛-1}{2}^{\mathrm{<mtext>gcd</mtext>}\left(𝑘,𝑛\right)}\\ & =\frac{1}{𝑛}\sum _{𝑑\mid 𝑛}\left|\left\{𝑘\in \left\{0,\dots ,𝑛-1\right\}|\mathrm{<mtext>gcd</mtext>}\left(𝑘,𝑛\right)=𝑑\right\}\right|2^{𝑑},\\ \left|𝑌/{𝐺}_2\right|& =\frac{1}{2𝑛}\sum _{𝑘=0}^{𝑛-1}\left(\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\right)\right|+\left|{\text{fix}}_{𝑌}\left({𝑟}^{𝑘}\circ 𝑠\right)\right|\right)\\ & =\frac{1}{2}\left(\left|𝑌/{𝐺}_1\right|+2^{\lceil \frac{𝑛}{2}\rceil +⟦𝑛\text{even and}𝑘\text{odd}⟧}\right).\end{array}$$There’s a special case to look out for: If $𝑛=2$, then $𝑟=𝑠$, so the ${𝐺}_2$ formula breaks down, but that’s fine, since the ${𝐺}_1$ formula already respects all the wanted symmetries included in this case.
Thus, let the second formula require $𝑛\ge 3$.⁵

The ${𝐺}_1$ formula can be simplified a bit further:
We find $\left|\left\{𝑘\in \left\{0,\dots ,𝑛-1\right\}|\mathrm{<mtext>gcd</mtext>}\left(𝑘,𝑛\right)=𝑑\right\}\right|$ by first noting that the set being measured is a subset of $\left\{𝑘\in \left\{0,\dots ,𝑛-1\right\}:𝑑\mid \mathrm{<mtext>gcd</mtext>}\left(𝑘,𝑛\right)\right\}$. Then note that $𝑑\mid 𝑛$ is a given, so $𝑑\mid \mathrm{<mtext>gcd</mtext>}\left(𝑘,𝑛\right)⟺𝑑\mid 𝑘$, so the second set is just $\left\{𝑘\in \left\{0,\dots ,𝑛-1\right\}:𝑑\mid 𝑘\right\}$, i.e. the set of multiples of $𝑑$ below $𝑛$.
All of these take the form $\ell 𝑑$ and the condition on $\ell$ can be read off from$$\ell 𝑑<𝑛⟺\ell <\frac{𝑛}{𝑑}.$$Thus, we find that$$\begin{array}{cc}\left|\left\{𝑘\in \left\{0,\dots ,𝑛-1\right\}|\mathrm{<mtext>gcd</mtext>}\left(𝑘,𝑛\right)=𝑑\right\}\right|& =\left|\left\{\ell \in \left\{0,\dots ,\frac{𝑛}{𝑑}-1\right\}|\mathrm{<mtext>gcd</mtext>}\left(\ell 𝑑,𝑛\right)=𝑑\right\}\right|\\ & =\left|\left\{\ell \in \left\{0,\dots ,\frac{𝑛}{𝑑}-1\right\}|\mathrm{<mtext>gcd</mtext>}\left(\ell ,\frac{𝑛}{𝑑}\right)=1\right\}\right|\\ & =𝜑\left(\frac{𝑛}{𝑑}\right),\end{array}$$where $𝜑$ is Euler’s totient function and the last equality is by its definition.

This gives us$$\left|𝑌/{𝐺}_1\right|=\frac{1}{𝑛}\sum _{𝑑\mid 𝑛}𝜑\left(\frac{𝑛}{𝑑}\right)2^{𝑑}.$$

More concretely, we have$$𝜑\left(𝑚\right)=𝑚\prod \left(1-\frac{1}{𝑝}\right),$$where the product is over primes $𝑝$ dividing $𝑚$.

We thus use the prime factorization $𝑛={\prod }_{𝑖=1}^{𝑚}{𝑝}_{𝑖}^{{𝑘}_{𝑖}}$, where ${\left({𝑝}_{𝑖}\right)}_{𝑖=1}^{𝑚}$ is some finite sequence of prime numbers and ${\left({𝑘}_{𝑖}\right)}_{𝑖=1}^{𝑚}$ some finite sequence of positive integers.
Then, the sum over the divisors of $𝑛$ splits into $𝑚$ sums over the exponents of the ${𝑝}_{𝑖}$:$$\begin{array}{cc}\left|𝑌/{𝐺}_1\right|& =\frac{1}{𝑛}\sum _{{𝑎}_1=0}^{{𝑘}_1}\dots \sum _{{𝑎}_{𝑚}=0}^{{𝑘}_{𝑚}}𝜑\left(\prod _{𝑖=1}^{𝑚}{𝑝}_{𝑖}^{{𝑘}_{𝑖}-{𝑎}_{𝑖}}\right)2^{\prod _{𝑖=1}^{𝑚}{𝑝}_{𝑖}^{{𝑎}_{𝑖}}}\\ & =\frac{1}{𝑛}\sum _{{𝑎}_1=0}^{{𝑘}_1}\dots \sum _{{𝑎}_{𝑚}=0}^{{𝑘}_{𝑚}}\prod _{𝑖=1}^{𝑚}\left({𝑝}_{𝑖}^{{𝑘}_{𝑖}-{𝑎}_{𝑖}}\left(1-⟦{𝑎}_{𝑖}<{𝑘}_{𝑖}⟧\frac{1}{{𝑝}_{𝑖}}\right)\right)2^{\prod _{𝑖=1}^{𝑚}{𝑝}_{𝑖}^{{𝑎}_{𝑖}}}\\ & =\frac{1}{𝑛}\sum _{{𝑎}_1=0}^{{𝑘}_1}\dots \sum _{{𝑎}_{𝑚}=0}^{{𝑘}_{𝑚}}\prod _{𝑖=1}^{𝑚}\left(\left({𝑝}_{𝑖}-⟦{𝑎}_{𝑖}<{𝑘}_{𝑖}⟧\right){𝑝}_{𝑖}^{{𝑘}_{𝑖}-{𝑎}_{𝑖}-1}\right)2^{\prod _{𝑖=1}^{𝑚}{𝑝}_{𝑖}^{{𝑎}_{𝑖}}}.\end{array}$$

As a nice example with applications to music theory, let’s take $𝑛=12$. In western music theory, it’s typical to work with 12-tone equal temperament, which is a tuning system with 12 notes per octave. Notes an octave apart are considered the same note, so we’re effectively working with a circle with 12 elements.

A scale can then be defined as any subset of these 12 notes. It corresponds to an arrangement of 12 marbles, each red or blue, into a circle: Just take a red marble for all notes that aren’t in the subset and a blue one for those that are.

Different scales related to each other by rotation of the circle are called modes of each other, and the reflection of a scale across a certain axis is called its inversion.

This means that counting the number of different scales, considering modes and/or inversions to be the same scale, can be done with our two formulae. Concretely, $12=2^2{3}^1$, so there are$$\begin{array}{cc}\left|𝑌/{𝐺}_1\right|& =\frac{1}{12}\sum _{𝑎=0}^2\sum _{𝑏=0}^1\left(\left(2-⟦𝑎<2⟧\right)2^{2-𝑎-1}\right)\left(\left(3-⟦𝑏<1⟧\right)3^{1-𝑏-1}\right)2^{2^{𝑎}{3}^{𝑏}}\\ & =\frac{1}{12}\left(\left(8+16\right)+\left(8+64\right)+\left(32+4096\right)\right)\\ & =352.\end{array}$$scales when considering different modes as the same scale.

Further, when also considering inversions as the same scale, the number drops to$$\begin{array}{cc}\left|𝑌/{𝐺}_2\right|& =\frac{1}{2}\left(\left|𝑌/{𝐺}_1\right|+2^{\lceil \frac{12}{2}\rceil }\right)\\ & =\frac{1}{2}\left(352+64\right)\\ & =208.\end{array}$$

5.1. Final Answer

Let’s directly start with the general form of the original question: How many ways are there to arrange $𝑘$ red and $\left(𝑛-𝑘\right)$ blue marbles into a circle?

Again, we have $𝑋$, the set of sequences of $𝑘$ red and $\left(𝑛-𝑘\right)$ blue marbles and ${𝐺}_1$ and ${𝐺}_2$ like before.

For the fixpoint set sizes, we can reuse some of the logic from the previous section:

• For $\left|{\text{fix}}_{𝑋}\left({𝑟}^{𝑎}\right)\right|$, we still have $\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right)$ chains of equalities, each involving $𝑛/\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right)$ sequence elements. To be able to assign the marbles to these, both $𝑘$ and $\left(𝑛-𝑘\right)$ need to be multiples of $𝑛/\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right)$. This condition is actually equivalent to only $𝑘$ being a multiple of $𝑛/\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right)$ (or alternatively to only $\left(𝑛-𝑘\right)$ being one), ⁶

  If this is satisfied, we can assign red to $𝑘/\left(𝑛/\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right)\right)=\frac{𝑘}{𝑛}\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right)$ of the chains and blue to the rest. This gives a factor of $𝐶\left(\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right),\frac{𝑘}{𝑛}\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right)\right)$. If the condition isn’t satisfied, it’s impossible to satisfy the equality chains created from ${𝑟}^{𝑘}\left(𝑥\right)=𝑥$, so $\left|{\text{fix}}_{𝑋}\left({𝑟}^{𝑘}\right)\right|=0$.
  Thus, we get$$\left|{\text{fix}}_{𝑋}\left({𝑟}^{𝑘}\right)\right|=⟦𝑛/\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right)\mid 𝑘⟧𝐶\left(\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right),\frac{𝑘}{𝑛}\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right)\right).$$

• For $\left|{\text{fix}}_{𝑋}\left({𝑟}^{𝑎}\circ 𝑠\right)\right|$, the same logic about rotations applies, so we only need to look at $𝑎=0$ and $𝑎=1$.

  • For $\left|{\text{fix}}_{𝑋}\left(𝑠\right)\right|$, the logic is actually identical to Section 2, so we have$$\left|{\text{fix}}_{𝑋}\left(𝑠\right)\right|=⟦𝑛\text{odd or}𝑘\text{even}⟧𝐶\left(\lfloor \frac{𝑛}{2}\rfloor ,\lfloor \frac{𝑘}{2}\rfloor \right)$$

  • For even $𝑛$, we need to consider $\left|{\text{fix}}_{𝑋}\left(𝑟\circ 𝑠\right)\right|$. There, like in the last section, we have two single slots and $\frac{𝑛}{2}-1$ pairs to fill.

    • If $𝑘$ is even, then so is $𝑛-𝑘$, so the two free slots are forced to also be the same as each other, so we end up with $\frac{𝑛}{2}$ pairs, which just gives an easy factor of$$𝐶\left(\frac{𝑛}{2},\frac{𝑘}{2}\right).$$
    • If $𝑘$ is odd, then so is $𝑛-𝑘$, so the two free slots are forced to be opposites of each other, so we end up with one choice of which is which, followed by the choice of putting the remaining $𝑘-1$ red marbles into the $\frac{𝑛}{2}-1$ pairs. This therefore gives a factor of$$2𝐶\left(\frac{𝑛}{2}-1,\frac{𝑘-1}{2}\right).$$

    In total, we therefore get$$\left|{\text{fix}}_{𝑋}\left(𝑟\circ 𝑠\right)\right|=\left(1+⟦𝑘\text{odd}⟧\right)𝐶\left(\frac{𝑛}{2}-⟦𝑘\text{odd}⟧,\lfloor \frac{𝑘}{2}\rfloor \right).$$

  These can be consolidated as follows:$$\begin{array}{cc}\left|{\text{fix}}_{𝑋}\left({𝑟}^{𝑎}\circ 𝑠\right)\right|& =\{\begin{array}{cc}𝐶\left(\lfloor \frac{𝑛}{2}\rfloor ,\lfloor \frac{𝑘}{2}\rfloor \right),& 𝑛\text{odd}\\ ⟦𝑘\text{even}⟧𝐶\left(\lfloor \frac{𝑛}{2}\rfloor ,\lfloor \frac{𝑘}{2}\rfloor \right),& 𝑛\text{even,}𝑎\text{even}\\ 𝐶\left(\frac{𝑛}{2},\frac{𝑘}{2}\right),& 𝑛\text{even,}𝑎\text{odd,}𝑘\text{even}\\ 2𝐶\left(\frac{𝑛}{2}-1,\frac{𝑘-1}{2}\right),& 𝑛\text{even,}𝑎\text{odd,}𝑘\text{odd}\end{array}\\ & =\{\begin{array}{cc}2⟦𝑎\text{odd}⟧𝐶\left(\frac{𝑛}{2}-1,\frac{𝑘-1}{2}\right),& 𝑛\text{even,}𝑘\text{odd}\\ 𝐶\left(\lfloor \frac{𝑛}{2}\rfloor ,\lfloor \frac{𝑘}{2}\rfloor \right),& \text{otherwise}\end{array}.\end{array}$$The sum of this over all $𝑎\in \left\{0,\dots ,𝑛-1\right\}$ is therefore$$\begin{array}{cc}\sum _{𝑎=0}^{𝑛-1}\left|{\text{fix}}_{𝑋}\left({𝑟}^{𝑎}\circ 𝑠\right)\right|& =\{\begin{array}{cc}𝑛𝐶\left(\frac{𝑛}{2}-1,\frac{𝑘-1}{2}\right),& 𝑛\text{even,}𝑘\text{odd}\\ 𝑛𝐶\left(\lfloor \frac{𝑛}{2}\rfloor ,\lfloor \frac{𝑘}{2}\rfloor \right),& \text{otherwise}\end{array}\\ & =𝑛\{\begin{array}{cc}𝐶\left(\lfloor \frac{𝑛}{2}\rfloor -1,\lfloor \frac{𝑘}{2}\rfloor \right),& 𝑛\text{even,}𝑘\text{odd}\\ 𝐶\left(\lfloor \frac{𝑛}{2}\rfloor ,\lfloor \frac{𝑘}{2}\rfloor \right),& \text{otherwise}\end{array}\\ & =𝑛𝐶\left(\lfloor \frac{𝑛}{2}\rfloor -⟦𝑛\text{even and}𝑘\text{odd}⟧,\lfloor \frac{𝑘}{2}\rfloor \right).\end{array}$$

Thus, we get$$\begin{array}{cc}\left|𝑋/{𝐺}_1\right|& =\frac{1}{𝑛}\sum _{𝑎=0}^{𝑛-1}⟦𝑛/\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right)\mid 𝑘⟧𝐶\left(\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right),\frac{𝑘}{𝑛}\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right)\right)\\ & =\frac{1}{𝑛}\sum _{𝑑\mid 𝑛}\left|\left\{𝑎\in \left\{0,\dots ,𝑛-1\right\}|\mathrm{<mtext>gcd</mtext>}\left(𝑎,𝑛\right)=𝑑\right\}\right|⟦\frac{𝑛}{𝑑}\mid 𝑘⟧𝐶\left(𝑑,\frac{𝑘}{𝑛}𝑑\right)\\ & =\frac{1}{𝑛}\sum _{𝑑\mid 𝑛}⟦\frac{𝑛}{𝑑}\mid 𝑘⟧𝜑\left(\frac{𝑛}{𝑑}\right)𝐶\left(𝑑,\frac{𝑘}{𝑛}𝑑\right),\\ & =\frac{1}{𝑛}\sum _{𝑑\mid 𝑛}⟦𝑑\mid 𝑘⟧𝜑\left(𝑑\right)𝐶\left(\frac{𝑛}{𝑑},\frac{𝑘}{𝑑}\right)\\ & =\frac{1}{𝑛}\sum _{𝑑\mid \mathrm{<mtext>gcd</mtext>}\left(𝑘,𝑛\right)}𝜑\left(𝑑\right)𝐶\left(\frac{𝑛}{𝑑},\frac{𝑘}{𝑑}\right),\\ \left|𝑋/{𝐺}_2\right|& =\frac{1}{2}\left(\left|𝑋/{𝐺}_1\right|+\frac{1}{𝑛}\sum _{𝑎=0}^{𝑛-1}\left|{\text{fix}}_{𝑋}\left({𝑟}^{𝑎}\circ 𝑠\right)\right|\right)\\ & =\frac{1}{2}\left(\left|𝑋/{𝐺}_1\right|+𝐶\left(\lfloor \frac{𝑛}{2}\rfloor -⟦𝑛\text{even and}𝑘\text{odd}⟧,\lfloor \frac{𝑘}{2}\rfloor \right)\right).\end{array}$$

Concretely, for the introductory example ($𝑛=5,𝑘=3$), this gives$$\begin{array}{cc}\left|𝑋/{𝐺}_1\right|& =\frac{1}{5}𝜑\left(1\right)𝐶\left(5,3\right)=\frac{10}{5}=2,\\ \left|𝑋/{𝐺}_2\right|& =\frac{1}{2}\left(2+𝐶\left(2,1\right)\right)=\frac{1}{2}\left(2+2\right)=2.\end{array}$$Concretely, these orbits are {RRRBB, RRBBR, RBBRR, BBRRR, BRRRB} and {RRBRB, RBRBR, BRBRR, RBRRB, BRRBR}.

Finally, this problem also has an application in music theory, when considering a more conservative definition of a scale: Here, a scale is defined by an arrangement of 5 whole steps and 2 half steps into a circle. This lets us apply the formula with $𝑛=7$ and $𝑘=2$, which gives$$\begin{array}{cc}\left|𝑋/{𝐺}_1\right|& =\frac{1}{7}𝜑\left(1\right)𝐶\left(7,2\right)=\frac{21}{7}=3,\\ \left|𝑋/{𝐺}_2\right|& =\frac{1}{2}\left(3+𝐶\left(3,1\right)\right)=\frac{1}{2}\left(3+3\right)=3.\end{array}$$Concretely, these orbits are

• {WWWWWHH, WWWWHHW, WWWHHWW, WWHHWWW, WHHWWWW, HHWWWWW, HWWWWWH},

• {WWWWHWH, WWWHWHW, WWHWHWW, WHWHWWW, HWHWWWW, WHWWWWH, HWWWWHW}, and

• {WWWHWWH, WWHWWHW, WHWWHWW, HWWHWWW, WWHWWWH, WHWWWHW, HWWWHWW}.

The last of them corresponds to the well-known modes of the major/minor scale:

• {Lydian, Mixolydian, Aeolian, Locrian, Ionian, Dorian, Phrygian}.

The second-to-last of them corresponds to the modes of the also somewhat well-known melodic minor scale, WHWWWWH. The mode HWHWWWW is also known as the superlocrian scale.

Alternatively, we can also use the formula to find the size of specific subsets of the set of scales (now using the previous 12-based definition again). For example, the numbers of 7-tone scales are$$\begin{array}{cc}\left|𝑋/{𝐺}_1\right|& =\frac{1}{12}𝜑\left(1\right)𝐶\left(12,7\right)=66,\\ \left|𝑋/{𝐺}_2\right|& =\frac{1}{2}\left(66+𝐶\left(5,3\right)\right)=38.\end{array}$$That’s already way more than the measly 3 we got above.

6. Conclusion

This has been a journey from a simple-sounding question to combinatorics, group theory, back to combinatorics with Burnside’s Lemma, and finally to the answer of that question.

There are lots of related questions I didn’t bring up here, such as considering more than two colors for the marbles, or asking about the size of more specific subsets, but if you followed along well, you’re probably equipped to answer those on your own now.

Most of all, I hope you had fun with this. I certainly did.