Independent calculation of A003322(20) "Necklace permutations"?

[Martin Fuller]

I have tried to extend A003322 "Necklace permutations" to n=35, but I get a difference from the last published value a(20). Could another seqfan repeat this calculation independently?

9640606422165480 : OEIS

9653395554710512 : me

Martin Fuller

[D. S. McNeil]

So I think your new a(20) value is probably correct, and if it weren't for the initials of the guy who apparently submitted the value I'd be a lot more confident. :-)

Does this match your understanding of what's going on (based on the edit history it looks like you considered these two interpretations as well)?

We can allow two bead changes to be considered the same as long as the resulting bead pattern (shape, under rotation + flips, or bracelet poset) stays the same, or we could only identify them if they preserve the original _set of black bead locations_ (not that no bead can move.)

e.g.

positions:  0 1 2 3 4 5 6 7 8
current:    B B W B W W B W W

has black beads at 0, 1, 3, 6.  We could activate 4 or 7, giving

after 4: B B W B B W B W W

after 7: B B W B W W B B W

You can rotate these two to match each other, but the same rotation doesn't preserve 0,1,3,6, it gives 0,3,6,7, and so could be distinguished.  That seems to match the text, and seems to be what's going on in most of the current terms, including your candidate new value:

 n              state-preserving          shape-only    state-shape
--------------------------------------------------------------------
 1                      1                      1                0
 2                      1                      1                0
 3                      1                      1                0
 4                      2                      2                0
 5                      4                      4                0
 6                     14                     14                0
 7                     57                     57                0
 8                    347                    347                0
 9                   2375                   2275              100
10                  20752                  20752                0
11                 200805                 200805                0
12                2293192                2239376            53816
13               28097136               28097136                0
14              381963696              381963696                0
15             5651257984             5582142632         69115352
16            87997162749            87829124289        168038460
17          1478237810536          1478237810536                0
18         26259254617337         26151806259633     107448357704
19        491527066667949        491527066667949                0
20       9653395554710512       9640606422165480   12789132545032

where the current sequence certainly _looks_ suspicious in that it seems to flip interpretations at a(20).

Doug

[Fred Lunnon]

  There follows what appears to be Knuth's definition of the "Necklace sequence"
function ---

ex https://oeis.org/A002998/a002998.pdf ,
D. E. Knuth via H. V. Gould via N. J. A. Sloane (1974) :
  << The number of different orders in which a person could change the beads
  of a necklace from all white to all black, ignoring the operation of rotating
  and/or flipping the necklace over whenever such an operation preserves the
  current black/white pattern. >>

  Following an hour or so devoted to a futile attempt to identify exactly what
one was intended to "ignore" in this context, my feeble struggles had finally
to be relieved by MF's excellent clarification.

  I do hope his material will find its way into a more comprehensive and
accurate treatment of this topic, in OEIS or elsewhere!

WFL
_

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAOX9QiBUcC%2BxeSExpmvjrgj0vXrKrOtE-pj1SG_jxHp0a5S6UA%40mail.gmail.com.

[Fred Lunnon]

<< MF's excellent clarification >>  

 

  Aaarghhh!  I intended to compliment Doug McNeil's post here.   WFL 

_

[Christian Sievers]

If I correctly understand the difference, I think it can be described in a more intuitive way like this:

imagine the beads don't instantly change from white to black, but go through a gray state.

If we take a picture each time a bead is gray (but between the pictures the necklace may be rotated or flipped),

then we can count how many essentially different sets of pictures we can get. These are the numbers under the

heading "state-preserving".

But if we take pictures when the beads are all black or white and count the possibilities, we get the numbers

under "shape-only".

(Each picture of a gray bead determines the (equivalence class of) black and white only pictures before and after it,

so taking both sets of pictures is not really different from only taking the gray ones, so there is no hidden third option.)

I think it would make sense to have both sequences.

Also, in page 3 of the "Correspondence" PDF, Knuth describes permutations a_1..a_n and b_1..b_n as equivalent

"necklace permutations" if there are eps=+-1 and 1<=j,k<=n with a_l=eps*b_l+j (mod n) for l<=k and a_l=b_l for l>k;

and then take the transitive closure of this.

I computed the number of equivalence classes of this relation for n<=10 and got the numbers of "state-preserving".

Terminology seems strange here, aren't necklaces usually things you can rotate but not flip over?

All the best

Christian

[Allan Wechsler]

The accepted terminology (see, for example, the Wikipedia article "Necklace (combinatorics)") seems to be that flipping over a bracelet never yields a different bracelet, but flipping over a necklace can yield a different necklace. Bracelets mod out all symmetries, while necklaces mod out only rotations, not reflections.

-- Allan

--

You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/250ec6ba-d398-410b-9e7c-e49a59d50439n%40googlegroups.com.

[Martin Fuller]

Shape-only sequence: https://oeis.org/draft/A397015

Clarification on the original sequence: https://oeis.org/draft/A003322

I added Doug as a coauthor. Doug, please could you make any changes you want, then submit if you are happy.

Martin

[Joerg Arndt]

Note one can mod out color permutations as well.

Here are all necklaces with 3 colors mod colors (dots for zeros):

   1:  ..... (not a Lyndon word)
   2:  ....1
   3:  ...11
   4:  ...12
   5:  ..1.1
   6:  ..1.2
   7:  ..111
   8:  ..112
   9:  ..121
  10:  ..122
  11:  .1.11
  12:  .1.12
  13:  .1.21
  14:  .1.22
  15:  .11.2
  16:  .1111
  17:  .1112
  18:  .1121
  19:  .1122
  20:  .12.2
  21:  .1211
  22:  .1212
  23:  .1221
  24:  .1222

Cf. https://jjj.de/fxt/demo/comb/#necklace-mod-color
Cf. A254036 "Number of Lyndon-Bell strings of length n.", this is for n colors

Best regards,  jj

On 6/14/26 4:46 AM, Allan Wechsler wrote:
> The accepted terminology (see, for example, the Wikipedia article "Necklace
> (combinatorics)") seems to be that flipping over a bracelet never yields a
> different bracelet, but flipping over a necklace can yield a different
> necklace. Bracelets mod out all symmetries, while necklaces mod out only
> rotations, not reflections.
>
> -- Allan
>

> [...]

[Allan Wechsler]

I'm not sure I know what you mean, JJ, by "modding out for color". If it means that permuting the colors is not considered to yield a different necklace, then your list is doing a lot of double-counting. For example, you include both 00001 and 01111, but exchanging the 1s and 0s and rotating one step shows that these instances belong to the same class. (I know you intend rotation to be allowed, because you don't list 01010 separately from 00101.)

-- Allan

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/656ed9fa-7518-45dc-b53b-9ad3e6c6ae1b%40th-nuernberg.de.

[Joerg Arndt]

I wanted to write "These are necklaces, not bracelets" but now I see your point, ouch.
Will need to document/name things better...

[Allan Wechsler]

If rotation and color permutation are both allowed, but flipping over isn't, then with three colors I can only count 9 possibilities with 5 beads. I may have missed things -- this calculation was done by staring at the ceiling Queen's Gambit style -- but I think for 1 through 5 beads the numbers are 1, 2, 3, 6, 9. Normalizing so that the lexically first representative of each class is shown, I think the lists are:

1 bead: 0

2 beads: 00, 01

3 beads: 000, 001, 012

4 beads: 0000, 0001, 0011, 0012, 0101, 0102

5 beads: 00000, 00001, 00011, 00012, 00101, 00102, 00112, 00121, 01012

If this is all correct, then it looks like we are talking about A002076. But perhaps that JJ is trying to count something different and just hasn't managed to verbalize his constraints yet. It sure looks as though there ought to be some chiral pairs, but I think that up through 5 beads there aren't any. At 6 beads we get things like 000112 and 000122 which are definitely different. The "bracelet" version of this sequence as A056353, which is indeed identical to A002076 up through n=5; at n=6 there are apparently four chiral pairs. 

As always, there are dozens of ways to stack the constraints, and dozens of possible sequences, and OEIS probably still doesn't have them all.

-- Allan

To view this discussion visit https://groups.google.com/d/msgid/seqfan/182b45bf-7c20-420b-81bf-e19bf45da0db%40th-nuernberg.de.