How to count necklaces with this additional requirement? I've recently dug into the idea of necklaces for a project I'm working on, and it's almost exactly what I'm looking for. The way I understand it, the general necklace-counting function is essentially cyclic permutations with repetition. However, for the particular situation I am trying to evaluate, there is one additional requirement.
So for this necklace-counting function, there are $n$ beads and $3$ colors. However, for each counted necklace, it must also be the case that the (absolute) difference between the number of beads of the $2^{nd}$ color and the number of beads of the $3^{rd}$ color, is divisible by $3$. There can be any number of beads of the $1^{st}$ color. I haven't the slightest idea how to subtract cases that fail this test from the original general necklace-counting function. Any suggestions?
 A: For a divisor $d\mid n$, there are $\phi(d)$ elements of $C_n$ of order $d$ that have $\frac nd$ orbits. In the usual count without your constraint, they leave $3^\frac nd$ necklaces invariant, since you can independently choose one of $3$ colours for each orbit.
If $3\mid d$, then all colour counts are divisible by $3$ so the constraint has no effect.
If $3\not\mid d$, consider the three necklaces you get if you pick one orbit and colour it in each of the three colours, with the same arbitrary colours in each case for the remaining orbits. The constraint is fulfilled in exactly one of these $3$ cases. Thus the number of admissible invariant necklaces is $3^{\frac nd-1}$.
Then by Burnside’s lemma the total count of admissible necklaces is
$$
\frac1n\left(\sum_{3\mid d\mid n}\phi(d)3^\frac nd+\frac13\sum_{3\not\mid d\mid n}\phi(d)3^\frac nd\right)\;.
$$
For $3\not\mid n$, this is just one third of the usual necklace count. For $3\mid n$, if you write $n=3^rs$ with $3\not\mid s$, this is
$$
\frac1n\left(\sum_{d\mid\frac n3}\phi(3d)3^\frac n{3d}+\frac13\sum_{d\mid s}\phi(d)3^\frac nd\right)\;.
$$
