Computing orbit representatives for a group action Consider the following classic problem in combinatorics: how many neckleces with  $n$ black/white beds are there up to rotations? You can formulate the question in the language of group theory: acting with $\mathbb{Z}/n\mathbb{Z}$ on $\{0,1\}^n$ by circular shift, how many orbits are there?
I'm looking for an algorithm that lists representatives for the orbits. In particular I'd like to have the source code of a working, self-contained implementation of it (or a precise link to the relevant code in some big package as GAP).
This question looks similar in nature, but the particular problem it's different and I don't see a natural way to adapt the answer given there.
 A: If $X$ is a necklace with $n$ beads (i.e. an elment of $\{0,1\}^n$) and $k$ is an element of $\mathbb{Z}/n\mathbb{Z}$, then $X+k$ will be the sum of $X$ and $k$, or the result of rotating $X$ by $k$ terms. For a given $n>0$, we will say say that the degree of a necklace $X$ with $n$ beads is the size of the orbit of $X$, or equivalently, the least positive integer $k$ such that $X+k=X$; by the orbit-stabilizer theorem, the degree of $X$ divides $n$. We will call a necklace $X$ with $n$ beads primitive if its degree is $n$.
Our first task is to show that there is a bijection between the necklaces with $n$ beads of degree $k$ and the primitive necklaces with $k$ beads. If $X$ is a primitive necklace with $k$ beads, we may concatenate $X$ with itself $n/k$ times to get a necklace $X'$ with $n$ beads, so $X'[i]=X[i\text{ mod }k]$. Clearly this operation is injective, and also $(X'+k)[i]=X'[i+k\text{ mod }n]=X[i+k\text{ mod }k]=X[i\text{ mod m}k]=X'[i]$ for all $i$, so the degree of $X'$--call it $l$--divides $k$. But we have that $(X'+l)[i]=X'[i+l\text{ mod }n]=X[i+l\text{ mod }k]=X'[i]=X[i\text{ mod }k]$ for all $i$, so $X+l=X$ and $l$ divides $k$. Therefore $k=l$. Also, if $Y$ is a necklace with $n$ beads of degree $k$, then let $X$ be the necklace with $k$ beads given by $X[i]=Y[i]$. Let $l$ be the degree of $X$, so $l$ divides $k$. Then $X[i+l\text{ mod }k]=Y[i+l\text{ mod }k]=Y[i+l\text{ mod }n]=X[i]=Y[i]$ for all $i$, so $k$ divides $l$, and thus $k=l$, so $X$ is primitive. Also, $Y[i]=Y[i\text{ mod }k]=X[i]$, so the initial-segment operation is the inverse of the concatenation operation, and we have just shown the latter to be surjective. Therefore the concatenation operation is a bijection.
Now let $P(n)$ be the number of primitive necklaces with $n$ beads. We know that there are a total of $2^n$ necklaces with $n$ beads. Each of these has a unique degree $k$ that divides $n$, and there are $P(k)$ necklaces with $n$ beads of degree $k$. Therefore we have
$\sum_{k|n} P(k)=2^n$
and by Möbius inversion,
$P(k)=\sum_{k|n} \mu(\frac{n}{k})2^k$
where $\mu(x)$ is the Möbius function. By Burnside's Lemma, the number of orbits $T(n)$--which is effectively the answer to your question--is given by
$T(n)=\frac{1}{n}\sum_{k=0}^{n-1} P(\text{gcd}(k,n))=\frac{1}{n}\sum_{d|n} \frac{n}{d}P(d)=\sum_{d|n} \frac{1}{d}\sum_{k|d} \mu(\frac{d}{k})2^k$
This can further be simplified by setting $d'=\frac{d}{k}$ to get
$T(n)=\sum_{kd'|n} \frac{1}{kd'}\mu(d')2^k=\sum_{k|n} 2^k\sum_{d'|n/k} \frac{1}{kd'}\mu(d')$
and then setting $d''=\frac{n/k}{d'}=\frac{n}{kd'}$ to get
$T(n)=\sum_{k|n} 2^k\sum_{d''|n/k} \frac{1}{k\frac{n/k}{d''}}\mu(\frac{n/k}{d''})=\frac{1}{n}\sum_{k|n} 2^k\sum_{d''|n/k} d''\mu(\frac{n/k}{d''})=\frac{1}{n}\sum_{k|n} 2^k\phi(\frac{n}{k})$
where $\phi(x)$ is Euler's totient function. I don't believe that this can be simplified much further.
A: By way of enrichment here is a solution that is brief. We will use the Polya Enumeration Theorem. Recall that the cycle index of the cyclic group $C_n$ (which represents rotational symmetries as needed here) is given by
$$Z(C_n) = \frac{1}{n} \sum_{d|n} \varphi(d) a_d^{n/d}.$$
In the present case we seek to compute
$$Z(C_{n})(B+W)_{B=1, W=1}$$
which is 
$$\left.\frac{1}{n} \sum_{d|n} \varphi(d) (B^d+W^d)^{n/d}\right|_{B=1, W=1}
= \frac{1}{n} \sum_{d|n} \varphi(d) 2^{n/d}
= \frac{1}{n} \sum_{d|n} 2^d \varphi\left(\frac{n}{d}\right).$$
The following META MSE Link contains many more calculations of this type and of varying difficulty.
