cp's OEIS Frontend

A329398 Number of compositions of n with uniform Lyndon factorization and uniform co-Lyndon factorization.

%I A329398 #15 Jun 20 2021 11:07:37
%S A329398 1,2,4,7,12,18,28,40,57,80,110,148,200,266,348,457,592,764,978,1248,
%T A329398 1580,2000,2508,3142,3913
%N A329398 Number of compositions of n with uniform Lyndon factorization and uniform co-Lyndon factorization.
%C A329398 We define the Lyndon product of two or more finite sequences to be the lexicographically maximal sequence obtainable by shuffling the sequences together. For example, the Lyndon product of (231) with (213) is (232131), the product of (221) with (213) is (222131), and the product of (122) with (2121) is (2122121). A Lyndon word is a finite sequence that is prime with respect to the Lyndon product. Equivalently, a Lyndon word is a finite sequence that is lexicographically strictly less than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into Lyndon words, and if these factors are arranged in lexicographically decreasing order, their concatenation is equal to their Lyndon product. For example, (1001) has sorted Lyndon factorization (001)(1).
%C A329398 Similarly, the co-Lyndon product is the lexicographically minimal sequence obtainable by shuffling the sequences together, and a co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product, or, equivalently, a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. For example, (1001) has sorted co-Lyndon factorization (1)(100).
%C A329398 A sequence of words is uniform if they all have the same length.
%C A329398 Conjecture: Also the number of compositions of n that are either weakly increasing or weakly decreasing. Hence a(n) = 2 * A000041(n) - A000005(n). - _Gus Wiseman_, Mar 05 2020
%e A329398 The a(1) = 1 through a(6) = 18 compositions:
%e A329398   (1)  (2)   (3)    (4)     (5)      (6)
%e A329398        (11)  (12)   (13)    (14)     (15)
%e A329398              (21)   (22)    (23)     (24)
%e A329398              (111)  (31)    (32)     (33)
%e A329398                     (112)   (41)     (42)
%e A329398                     (211)   (113)    (51)
%e A329398                     (1111)  (122)    (114)
%e A329398                             (221)    (123)
%e A329398                             (311)    (222)
%e A329398                             (1112)   (321)
%e A329398                             (2111)   (411)
%e A329398                             (11111)  (1113)
%e A329398                                      (1122)
%e A329398                                      (2211)
%e A329398                                      (3111)
%e A329398                                      (11112)
%e A329398                                      (21111)
%e A329398                                      (111111)
%t A329398 lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
%t A329398 lynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[lynfac[Drop[q,i]],Take[q,i]]][Last[Select[Range[Length[q]],lynQ[Take[q,#]]&]]]];
%t A329398 colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
%t A329398 colynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[colynfac[Drop[q,i]],Take[q,i]]]@Last[Select[Range[Length[q]],colynQ[Take[q,#]]&]]];
%t A329398 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],SameQ@@Length/@lynfac[#]&&SameQ@@Length/@colynfac[#]&]],{n,10}]
%Y A329398 Lyndon and co-Lyndon compositions are (both) counted by A059966.
%Y A329398 Lyndon compositions that are not weakly increasing are A329141.
%Y A329398 Lyndon compositions whose reverse is not co-Lyndon are A329324.
%Y A329398 Cf. A000740, A001037, A001523, A008965, A059204, A060223, A211100, A328596, A329312, A329318, A329396, A329397, A329399, A332578, A332669, A332834.
%K A329398 nonn,more
%O A329398 1,2
%A A329398 _Gus Wiseman_, Nov 13 2019
%E A329398 a(19)-a(25) from _Robert Price_, Jun 20 2021