OFFSET
1,2
COMMENTS
The co-Lyndon product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (231) and (213) is (212313), the product of (221) and (213) is (212213), and the product of (122) and (2121) is (1212122). A co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product. Equivalently, a co-Lyndon word is a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into co-Lyndon words, and if these factors are arranged in a certain order, their concatenation is equal to their co-Lyndon product. For example, (1001) has sorted co-Lyndon factorization (1)(100).
EXAMPLE
Triangle begins:
1: (1) 21: (221) 41: (51) 61: (51)
2: (2) 22: (23) 42: (222) 62: (6)
3: (11) 23: (2111) 43: (2211) 63: (111111)
4: (3) 24: (5) 44: (24) 64: (7)
5: (21) 25: (41) 45: (231) 65: (61)
6: (3) 26: (5) 46: (24) 66: (52)
7: (111) 27: (311) 47: (21111) 67: (511)
8: (4) 28: (5) 48: (6) 68: (43)
9: (31) 29: (41) 49: (51) 69: (421)
10: (22) 30: (5) 50: (6) 70: (43)
11: (211) 31: (11111) 51: (411) 71: (4111)
12: (4) 32: (6) 52: (6) 72: (7)
13: (31) 33: (51) 53: (51) 73: (331)
14: (4) 34: (42) 54: (33) 74: (322)
15: (1111) 35: (411) 55: (3111) 75: (3211)
16: (5) 36: (33) 56: (6) 76: (34)
17: (41) 37: (321) 57: (51) 77: (331)
18: (32) 38: (33) 58: (6) 78: (34)
19: (311) 39: (3111) 59: (411) 79: (31111)
20: (5) 40: (6) 60: (6) 80: (7)
For example, 45 has binary expansion (101101), with co-Lyndon factorization (10)(110)(1), so row n = 45 is (2,3,1).
MATHEMATICA
colynQ[q_]:=Array[Union[{RotateRight[q, #], q}]=={RotateRight[q, #], q}&, Length[q]-1, 1, And];
colynfac[q_]:=If[Length[q]==0, {}, Function[i, Prepend[colynfac[Drop[q, i]], Take[q, i]]]@Last[Select[Range[Length[q]], colynQ[Take[q, #]]&]]];
Table[Length/@colynfac[If[n==0, {}, IntegerDigits[n, 2]]], {n, 30}]
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Gus Wiseman, Nov 12 2019
STATUS
approved