Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I'm hoping there's a more efficient method in GAP, but you can do it brute-force by n:=5;; g:=CyclicGroup(IsPermGroup,n);; OrbitsDomain(g,Tuples([0,1],n),Permuted); This will, in fact, partition the necklaces into orbits. –  Douglas S. Stones Nov 2 '12 at 5:13
    
@Douglas: I'm interested in how the algorithm works, do you know how GAP does the work? –  Marco Castronovo Nov 2 '12 at 9:17
    
Not really, I'm afraid. If you're after a general algorithm, however, you might get some mileage out of the paper "Isomorph-free exhaustive generation" by Brendan McKay; here: cs.anu.edu.au/~bdm/papers/orderly.pdf. –  Douglas S. Stones Nov 2 '12 at 9:21
    
In the example by @DouglasS.Stones GAP uses OrbitsDomain method for arbitrary domains from gap4r6p5/lib/oprt.gi. Since GAP is open-source, you can look at it (search for "for arbitrary domains" substring in that file). Please ask GAP Forum or GAP Support if you will be interested in further details. –  Alexander Konovalov Nov 6 '13 at 14:01

2 Answers 2

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.

share|improve this answer
    
The question is: is there an algorithm that lists representatives for the orbits? However, thank you for your answer. –  Marco Castronovo Nov 2 '12 at 9:13

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.