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? –  user365 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. –  user365 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.