I'm looking at OEIS:A000046, whose definition states:
Number of primitive n-bead necklaces (turning over is allowed) where complements are equivalent.
I can't quite understand this. This is what I have so far:
- The necklace should have 2 types of beads (i.e. it is binary (?))
- The necklace should have $n$ beads
- Two necklaces are identical if one can be rotated, reflected, or complemented (all beads' types are flipped), or have any combination of those operations applied to it and become equal to the other
However, this doesn't seem to match A46, or A11 for that matter. Can someone finish the explanation or explain where it's wrong?
Also, what does "primitive" mean?
Edit
It was actually because I forgot the return statement in one of the functions in my Python interpretation...
So the question becomes, what does "primitive" mean in this case?
In this case, primitive means it's not the concatenation of two or more copies of the same necklace.
For example, with $n=4$, we count only $0111$ and $0011$. The former counts all necklaces with one zero (anywhere), and (by taking complements) three zeroes. The latter counts all necklaces with two adjacent zeroes, and two adjacent ones.
What we don't count are $1111$ and $1010$. The former is four copies of the primitive necklace $1$, while the latter is two copies of the primitive necklace $10$.
With $n=5$, we count $01111$, $00111$, and $10101$. By considering complements, we may look at just zero, one, or two $0$'s. If zero, we have the nonprimitive $11111$. If one, we have $01111$. If two, the zeroes could either be adjacent or nonadjacent. By rotation and reflection this covers all the cases.
With $n=6$, we count $011111$, $001111$, $010111$, $000111$, $010011$. Note that $011011$ and $010101$ are not primitive.