problem with a necklace sequence

[lloyd]

A sequence came up in a puzzle I was working on, that appears to agree
with A066313 in Sloane's online encyclopedia of integer sequences. My
context was completely unrelated to the one that appears in the OEIS.
In trying to understand the correspondence I realised I didn't
understand the definition of A066313. Can anyone help? It says:

"Number of aperiodic bracelets (or necklaces) with n red or blue beads
such that the beads switch colors when bracelet is turned over."

The sequence starts (with n=1):

1, 1, 1, 2, 3, 6, 9, 18, 28, 57, 93, 181, 315 ...

here's an example, as far as I understand it, for n=6:

r r b b r b "turned over" becomes (read starting from the same bead)
r b r b b r which is a rotation of
b b r r b r which is the original with the colours switched.

These two, along with rrrbbb, must be the three cases the OEIS means
for
n=6, as far as I can tell.

But here's my question: how can you ever have such a necklace for odd
n?
For red and blue to switch roles there must be the same number of each,

no? A066313 has positive values for all n though, so I must be missing
something. Can anyone tell me what?

Thanks --Lloyd

[mensa...@aol.com]

lloyd wrote:
> A sequence came up in a puzzle I was working on, that appears to agree
> with A066313 in Sloane's online encyclopedia of integer sequences. My
> context was completely unrelated to the one that appears in the OEIS.
> In trying to understand the correspondence I realised I didn't
> understand the definition of A066313. Can anyone help? It says:
>
> "Number of aperiodic bracelets (or necklaces) with n red or blue beads
> such that the beads switch colors when bracelet is turned over."
>
> The sequence starts (with n=1):
>
> 1, 1, 1, 2, 3, 6, 9, 18, 28, 57, 93, 181, 315 ...
>
> here's an example, as far as I understand it, for n=6:
>
> r r b b r b "turned over" becomes (read starting from the same bead)
> r b r b b r which is a rotation of
> b b r r b r which is the original with the colours switched.
>
> These two, along with rrrbbb, must be the three cases the OEIS means
> for
> n=6, as far as I can tell.

Count again. It's 6 for n=6.

[matt271...@yahoo.co.uk]

mensa...@aol.compost wrote:
> lloyd wrote:
> > A sequence came up in a puzzle I was working on, that appears to agree
> > with A066313 in Sloane's online encyclopedia of integer sequences. My
> > context was completely unrelated to the one that appears in the OEIS.
> > In trying to understand the correspondence I realised I didn't
> > understand the definition of A066313. Can anyone help? It says:
> >
> > "Number of aperiodic bracelets (or necklaces) with n red or blue beads
> > such that the beads switch colors when bracelet is turned over."
> >
> > The sequence starts (with n=1):
> >
> > 1, 1, 1, 2, 3, 6, 9, 18, 28, 57, 93, 181, 315 ...
> >
> > here's an example, as far as I understand it, for n=6:
> >
> > r r b b r b "turned over" becomes (read starting from the same bead)
> > r b r b b r which is a rotation of
> > b b r r b r which is the original with the colours switched.
> >
> > These two, along with rrrbbb, must be the three cases the OEIS means
> > for
> > n=6, as far as I can tell.
>
> Count again. It's 6 for n=6.

I too can find only these three - though it's unclear if rrbbrb should
be considered the same necklace as bbrrbr (being its mirror image, i.e.
the same when turned over). If it is then there seem to be only two
possibilities. And FWIW I can't make any sense of the OEIS explanation
either.

Did you actually find 6, or did you just take that number from the OEIS
sequence?

[jaapsch]

> > lloyd wrote:
> > > A sequence came up in a puzzle I was working on, that appears to agree
> > > with A066313 in Sloane's online encyclopedia of integer sequences. My
> > > context was completely unrelated to the one that appears in the OEIS.
> > > In trying to understand the correspondence I realised I didn't
> > > understand the definition of A066313. Can anyone help? It says:
> > >
> > > "Number of aperiodic bracelets (or necklaces) with n red or blue beads
> > > such that the beads switch colors when bracelet is turned over."
> > >
> > > The sequence starts (with n=1):
> > >
> > > 1, 1, 1, 2, 3, 6, 9, 18, 28, 57, 93, 181, 315 ...
> > >
> > > here's an example, as far as I understand it, for n=6:
> > >
> > > r r b b r b "turned over" becomes (read starting from the same bead)
> > > r b r b b r which is a rotation of
> > > b b r r b r which is the original with the colours switched.
> > >
> > > These two, along with rrrbbb, must be the three cases the OEIS means
> > > for
> > > n=6, as far as I can tell.
> >
> > Count again. It's 6 for n=6.

It is a very misleading description in the OEIS. When I looked at:
http://www.research.att.com/~njas/sequences/A053656
it began to make a bit more sense.

Let's look again at the 3 necklaces you mention:

r r b b r b "turned over" becomes (read starting from the same bead)
r b r b b r which is a rotation of
b b r r b r which is the original with the colours switched.

All these three are to be considered identical. Now how many aperiodic
necklaces are there if necklaces that differ by rotation and/or by
(flip-over + swap colours) are considered identical?

Let's list them all:
r r r r r r (=b b b b b b ) Ignore this as it is periodic.
r r r r r b (=r b b b b b )
r r r r b b (=r r b b b b )
r r r b r b (=r b r b b b )
r r r b b b
r r b r r b (=b b r b b r ) Ignore this as it is periodic.
r r b r b b

r r b b r b

For a total of 6.
Jaap

[mensa...@aol.com]

Of course not, do I look like a genius.

> or did you just take that number from the OEIS
> sequence?

Well, yeah. But the OP said "must be the three cases the OEIS means".
Whether there are actually 3 cases or 6 cases is irrelevent because
the OEIS said there were 6. When I said "count again", I meant count
from the start of the OEIS list where you find that the 6th entry is 6.

[lloyd]

matt271...@yahoo.co.uk wrote:

> I too can find only these three - though it's unclear if rrbbrb should
> be considered the same necklace as bbrrbr (being its mirror image, i.e.
> the same when turned over). If it is then there seem to be only two
> possibilities. And FWIW I can't make any sense of the OEIS explanation
> either.

I understand them to be distinct necklaces, but they're equivalent
"bracelets" - a bracelet is a necklace that you're allowed to turn
over.

Lloyd

[lloyd]

right you are.

[lloyd]

Ok, I think you must be right. The description in the OEIS is downright
wrong, in this case. It should read something like "non-periodic
necklaces of n beads of 2 colours, distinct up to turning over and
exchanging colours". The rotating is part of the definition of a
necklace; we could make the definition shorter by referring to
bracelets which are necklaces you are allowed to turn over. In that
case we'd have "non-periodic necklaces of n beads of 2 colours,
distinct up to exchanging colours"

[lloyd]

Arg, I wrote "non-periodic necklaces of n beads of 2 colours, distinct
up to exchanging colours", but I meant:

"non-periodic bracelets of n beads of 2 colours, distinct up to
exchanging colours"

[matt271...@yahoo.co.uk]

Yes, I tried a few other small values of n using your method, and I do
indeed get the same numbers as in the OEIS sequence.

[matt271...@yahoo.co.uk]

Right. I wasn't aware of that distinction. I'm not sure if the OEIS
explanation should rely on people knowing it; at the moment they seem
to be saying that necklaces and bracelets are the same thing. But
anyway I might mail them a link to this thread and perhaps they'll
agree that the description should be clarified...

[matt271...@yahoo.co.uk]

But wouldn't that definition make r r b r b b and r r b b r b
identical, whereas they need to be distinct to get the six count as per
jaapsch's post? If you swap colours then you *have* to turn the thing
over?

[lloyd]

Matt wrote:

> But wouldn't that definition make r r b r b b and r r b b r b
> identical, whereas they need to be distinct to get the six count as per
> jaapsch's post? If you swap colours then you *have* to turn the thing
> over?

Yes, agreed. It's a funny group of operations. And I'm no closer to
seeing how it connects to my problem. Thanks to all anyway.

--Lloyd

[dwas...@earthlink.net]

Actually A066313 shows 3 necklaces for n = 5, and 6 necklaces for n =
6.

I believe it means that if you take any necklace, reverse its order,
and reverse the color of each bead, the result is considered equivalent
to the original necklace. This make sense physically if each bead is
red on the top and blue on the bottom, or vice versa. More likely, the
two colors are metaphors for objects that spin clockwise or
counterclockwise, or have magnetic fields in opposite directions, or
some such thing.

So the 6 necklaces with 6 beads are
a a a a a b (equivalent to a b b b b b)
a a a a b b (equivalent to a a b b b b)
a a a b a b (equivalent to a b a b b b)
a a b b a b
b b a a b a
a a a b b b

"Aperiodic" apparently means that the n-bead sequence may not consist
of a shorter sequence that repeats, e.g. a b a b a b, or a a b a a b.
This restriction makes sense physically if you think of an infinite
periodic sequence instead of a finite loop. ...ababababab... doesn't
need to be counted for n = 6 because it is counted at n = 2. In
contrast, a necklace with 6 beads ababab is physically distinguishable
from a necklace with 2 beads ab.