%I #8 May 28 2020 05:00:39
%S 1,1,1,2,1,1,2,3,1,1,2,1,2,2,4,5,1,1,1,1,2,1,2,1,2,2,4,2,4,4,7,7,1,1,
%T 1,1,2,1,1,1,2,2,3,1,2,2,2,1,2,2,2,2,5,2,5,2,4,4,9,4,7,7,12,11,1,1,1,
%U 1,1,1,1,1,2,1,1,1,2,1,1,1,2,2,2,2,4,1
%N Number of co-Lyndon factorizations of the k-th composition in standard order.
%C We define the co-Lyndon product of two or more finite sequences to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (2,3,1) with (2,1,3) is (2,1,2,3,1,3), the product of (2,2,1) with (2,1,3) is (2,1,2,2,1,3), and the product of (1,2,2) with (2,1,2,1) is (1,2,1,2,1,2,2). A co-Lyndon factorization of a composition c is a multiset of compositions whose co-Lyndon product is c.
%C A composition of n is a finite sequence of positive integers summing to n. 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.
%C Also the number of multiset partitions of the co-Lyndon-word factorization of the n-th composition in standard order.
%F For n > 0, Sum_{k = 2^(n-1)..2^n-1} a(k) = A034691(n).
%e The a(54) = 5, a(61) = 7, and a(237) = 9 factorizations:
%e ((1,2,1,2)) ((1,1,1,2,1)) ((1,1,2,1,2,1))
%e ((1),(2,1,2)) ((1),(1,1,2,1)) ((1),(1,2,1,2,1))
%e ((1,2),(2,1)) ((1,1),(1,2,1)) ((1,1),(2,1,2,1))
%e ((2),(1,2,1)) ((2,1),(1,1,1)) ((1,2,1),(1,2,1))
%e ((1),(2),(2,1)) ((1),(1),(1,2,1)) ((2,1),(1,1,2,1))
%e ((1),(1,1),(2,1)) ((1),(1),(2,1,2,1))
%e ((1),(1),(1),(2,1)) ((1,1),(2,1),(2,1))
%e ((1),(2,1),(1,2,1))
%e ((1),(1),(2,1),(2,1))
%t stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
%t colynprod[]:={};colynprod[{},b_List]:=b;colynprod[a_List,{}]:=a;colynprod[a_List]:=a;
%t colynprod[{x_,a___},{y_,b___}]:=Switch[Ordering[If[x=!=y,{x,y},{colynprod[{a},{x,b}],colynprod[{x,a},{b}]}]],{1,2},Prepend[colynprod[{a},{y,b}],x],{2,1},Prepend[colynprod[{x,a},{b}],y]];
%t colynprod[a_List,b_List,c__List]:=colynprod[a,colynprod[b,c]];
%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];
%t dealings[q_]:=Union[Function[ptn,Sort[q[[#]]&/@ptn]]/@sps[Range[Length[q]]]];
%t Table[Length[Select[dealings[stc[n]],colynprod@@#==stc[n]&]],{n,0,100}]
%Y The dual version is A333940.
%Y Binary necklaces are counted by A000031.
%Y Necklace compositions are counted by A008965.
%Y Necklaces covering an initial interval are counted by A019536.
%Y Lyndon compositions are counted by A059966.
%Y Numbers whose reversed binary expansion is a necklace are A328595.
%Y Numbers whose prime signature is a necklace are A329138.
%Y Length of Lyndon factorization of binary expansion is A211100.
%Y Length of co-Lyndon factorization of binary expansion is A329312.
%Y Length of co-Lyndon factorization of reversed binary expansion is A329326.
%Y Length of Lyndon factorization of reversed binary expansion is A329313.
%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 - Runs are counted by A124767.
%Y - Rotational symmetries are counted by A138904.
%Y - Strict compositions are A233564.
%Y - Constant compositions are A272919.
%Y - Lyndon compositions are A275692.
%Y - Co-Lyndon compositions are A326774.
%Y - Aperiodic compositions are A328594.
%Y - Reversed co-necklaces are A328595.
%Y - Length of Lyndon factorization is A329312.
%Y - Rotational period is A333632.
%Y - Co-necklaces are A333764.
%Y - Dealings are counted by A333939.
%Y - Reversed necklaces are A333943.
%Y - Length of co-Lyndon factorization is A334029.
%Y - Combinatory separations are A334030.
%Y Cf. A000740, A001037, A034691, A060223, A211100, A269134, A292884, A328596.
%K nonn
%O 0,4
%A _Gus Wiseman_, Apr 13 2020
|