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

%I #6 Apr 25 2020 08:41:29

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

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

%C 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.

%e The a(1) = 1 through a(4) = 12 normal sequences:

%e (1) (1,1) (1,1,1) (1,1,1,1)

%e (2,1) (2,1,1) (2,1,1,1)

%e (2,2,1) (2,1,2,1)

%e (3,2,1) (2,2,1,1)

%e (2,2,2,1)

%e (3,1,2,1)

%e (3,2,1,1)

%e (3,2,2,1)

%e (3,2,3,1)

%e (3,3,2,1)

%e (4,2,3,1)

%e (4,3,2,1)

%t neckQ[q_]:=Length[q]==0||Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];

%t coneckQ[q_]:=Length[q]==0||Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];

%t allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];

%t Table[Length[Select[Join@@Permutations/@allnorm[n],neckQ[Reverse[#]]&&coneckQ[#]&]],{n,0,8}]

%Y Dominates A334270 (the aperiodic case).

%Y Compositions of this type are counted by A334271.

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

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

%Y Normal sequences are counted by A000670.

%Y Necklace compositions are counted by A008965.

%Y Normal Lyndon words are counted by A060223.

%Y Normal necklaces are counted by A019536.

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

%Y - Necklaces are A065609.

%Y - Reversed necklaces are A333943.

%Y - Co-necklaces are A333764.

%Y - Reversed co-necklaces are A328595.

%Y - Lyndon words are A275692.

%Y - Co-Lyndon words are A326774.

%Y - Reversed Lyndon words are A334265.

%Y - Reversed co-Lyndon words are A328596.

%Y - Reversed Lyndon co-Lyndon compositions are A334266.

%Y - Aperiodic compositions are A328594.

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

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Apr 25 2020