login
Numbers k such that the k-th composition in standard order is both a reversed Lyndon word and a co-Lyndon word.
8

%I #9 Apr 25 2020 08:40:34

%S 0,1,2,4,5,8,9,11,16,17,18,19,21,23,32,33,34,35,37,39,43,47,64,65,66,

%T 67,68,69,71,73,74,75,77,79,85,87,91,95,128,129,130,131,132,133,135,

%U 137,138,139,141,143,146,147,149,151,155,159,171,173,175,183,191

%N Numbers k such that the k-th composition in standard order is both a reversed Lyndon word and a co-Lyndon word.

%C A Lyndon word is a finite sequence of positive integers that is lexicographically strictly less than all of its cyclic rotations. Co-Lyndon is defined similarly, except with strictly greater instead of strictly less.

%C The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

%F Intersection of A334265 and A326774.

%e The sequence of all reversed Lyndon co-Lyndon words begins:

%e 0: () 37: (3,2,1) 91: (2,1,2,1,1)

%e 1: (1) 39: (3,1,1,1) 95: (2,1,1,1,1,1)

%e 2: (2) 43: (2,2,1,1) 128: (8)

%e 4: (3) 47: (2,1,1,1,1) 129: (7,1)

%e 5: (2,1) 64: (7) 130: (6,2)

%e 8: (4) 65: (6,1) 131: (6,1,1)

%e 9: (3,1) 66: (5,2) 132: (5,3)

%e 11: (2,1,1) 67: (5,1,1) 133: (5,2,1)

%e 16: (5) 68: (4,3) 135: (5,1,1,1)

%e 17: (4,1) 69: (4,2,1) 137: (4,3,1)

%e 18: (3,2) 71: (4,1,1,1) 138: (4,2,2)

%e 19: (3,1,1) 73: (3,3,1) 139: (4,2,1,1)

%e 21: (2,2,1) 74: (3,2,2) 141: (4,1,2,1)

%e 23: (2,1,1,1) 75: (3,2,1,1) 143: (4,1,1,1,1)

%e 32: (6) 77: (3,1,2,1) 146: (3,3,2)

%e 33: (5,1) 79: (3,1,1,1,1) 147: (3,3,1,1)

%e 34: (4,2) 85: (2,2,2,1) 149: (3,2,2,1)

%e 35: (4,1,1) 87: (2,2,1,1,1) 151: (3,2,1,1,1)

%t stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;

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

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

%t Select[Range[0,100],lynQ[Reverse[stc[#]]]&&colynQ[stc[#]]&]

%Y The version for binary expansion is A334267.

%Y Compositions of this type are counted by A334269.

%Y Normal sequences of this type are counted by A334270.

%Y Necklace compositions of this type are counted by A334271.

%Y Binary Lyndon words are counted by A001037.

%Y Lyndon compositions are counted by A059966.

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

%Y - Length is A000120.

%Y - Necklaces are A065609.

%Y - Sum is A070939.

%Y - Reverse is A228351 (triangle).

%Y - Strict compositions are A233564.

%Y - Constant compositions are A272919.

%Y - Lyndon words are A275692.

%Y - Reversed Lyndon words are A334265.

%Y - Co-Lyndon words are A326774.

%Y - Reversed co-Lyndon words are A328596.

%Y - Length of Lyndon factorization is A329312.

%Y - Length of Lyndon factorization of reverse is A334297.

%Y - Length of co-Lyndon factorization is A334029.

%Y - Length of co-Lyndon factorization of reverse is A329313.

%Y - Distinct rotations are counted by A333632.

%Y - Co-Lyndon factorizations are counted by A333765.

%Y - Lyndon factorizations are counted by A333940.

%Y Cf. A000740, A008965, A065609, A329324, A333764, A333943, A334272, A334297.

%K nonn

%O 1,3

%A _Gus Wiseman_, Apr 22 2020