A334272 Number of sequences of length n that cover an initial interval of positive integers and are both a reversed necklace and a co-necklace.

1, 1, 2, 4, 12, 43, 229, 1506, 12392, 120443

Offset

0,3

Comments

A necklace is a finite sequence of positive integers that is lexicographically strictly less than or equal to any cyclic rotation. Co-necklace is defined similarly, except with strictly greater instead of strictly less.

Links

Table of n, a(n) for n=0..9.

Example

The a(1) = 1 through a(4) = 12 normal sequences:
  (1)  (1,1)  (1,1,1)  (1,1,1,1)
       (2,1)  (2,1,1)  (2,1,1,1)
              (2,2,1)  (2,1,2,1)
              (3,2,1)  (2,2,1,1)
                       (2,2,2,1)
                       (3,1,2,1)
                       (3,2,1,1)
                       (3,2,2,1)
                       (3,2,3,1)
                       (3,3,2,1)
                       (4,2,3,1)
                       (4,3,2,1)

Mathematica

neckQ[q_]:=Length[q]==0||Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
coneckQ[q_]:=Length[q]==0||Array[OrderedQ[{RotateRight[q, #], q}]&, Length[q]-1, 1, And];
allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n], neckQ[Reverse[#]]&&coneckQ[#]&]], {n, 0, 8}]

Crossrefs

Dominates A334270 (the aperiodic case).

Compositions of this type are counted by A334271.

These compositions are ranked by A334273 (standard) and A334274 (binary).

Binary (or reversed binary) necklaces are counted by A000031.

Normal sequences are counted by A000670.

Necklace compositions are counted by A008965.

Normal Lyndon words are counted by A060223.

Normal necklaces are counted by A019536.

All of the following pertain to compositions in standard order (A066099):

- Necklaces are A065609.

- Reversed necklaces are A333943.

- Co-necklaces are A333764.

- Reversed co-necklaces are A328595.

- Lyndon words are A275692.

- Co-Lyndon words are A326774.

- Reversed Lyndon words are A334265.

- Reversed co-Lyndon words are A328596.

- Reversed Lyndon co-Lyndon compositions are A334266.

- Aperiodic compositions are A328594.

Cf. A034691, A059966, A296372, A296975, A329138, A334269.

Sequence in context: A139669 A179973 A275780 * A348926 A039301 A346505

Adjacent sequences: A334269 A334270 A334271 * A334273 A334274 A334275

Keyword

nonn,more

Author

Gus Wiseman, Apr 25 2020

Status

approved